hash - SHA256 / 512ハッシュを生成する場合、ハッシュするデータの最小の「安全な」量はありますか？

Question

ハッシュを作成するときに、小さなファイルや大量のデータを使用すると、結果のハッシュが衝突する可能性が高くなる可能性があると聞いています。それが本当なら、これが起こらないようにするために使用されるべき最小の「安全な」データ量はありますか？

質問は次のように表現することもできると思います。

安全かつ確実にハッシュできる最小量のデータはどれくらいですか？

Answer 1

ハッシュ関数は、任意の（または少なくとも非常に長い）長さの入力を受け入れ、固定長の出力を生成します。可能な出力よりも可能な入力の方が多いため、衝突が存在する必要があります。安全なハッシュ関数の要点は、「衝突耐性」があることです。つまり、衝突は数学的に存在する必要がありますが、実際に計算するのは非常に困難です。したがって、SHA-256とSHA-512の既知の衝突はなく、1つを計算するための最もよく知られている方法（意図的に実行することによる）は非常に高価であるため、すぐには適用されません（米国連邦予算全体世紀は、タスクの途方もなく小さな部分だけを購入するでしょう）。

したがって、意図的に現実的に実行できない場合は、（不運な）運が原因で衝突が発生しないことが期待できます。

さらに、入力を非常に短く制限すると、衝突がまったく発生しない可能性があります。たとえば、12バイトの入力を検討する場合：12バイトの2つの⁹⁶の可能なシーケンスがあります。それは巨大です（今日のテクノロジーで列挙できる以上のものです）。それでも、SHA-256は、各入力を256ビット値、つまり、はるかに広いスペース（サイズ2 ²⁵⁶）の値にマップします。正式に証明することはできませんが、2つの^96個のハッシュ値がすべて互いに異なる可能性があります。これには実際的な影響はないことに注意してください。衝突がないために衝突が見つからない場合と、衝突する可能性が非常に低いために衝突が見つからない場合との間に測定可能な違いはありません。

SHA-256との衝突のリスクがいかに低いかを説明するために、地元の動物園や個人所有者から逃げ出したゴリラに襲われるリスクを考えてみましょう。ありそうもない？はい、しかしそれはまだ起こるかもしれません：ゴリラは2004年にダラス動物園から逃げ出し、 4人を負傷させたようです。2010年に別のゴリラが同じ動物園から脱出した。地球全体（ダラス地域だけでなく）に6年ごとに暴れ回るゴリラが1頭だけいて、65億人の人口のうち、あなたがたまたま彼の道を進んでいる不運なチャップであると仮定すると、重大な危険があります-ゴリラによる身体的^危害は、 1日あたり約243.7人に1人と推定できます。今、1万を取るPCを使用して、SHA-256の衝突の検出に取り組んでもらいます。衝突にぶつかる可能性は1日あたり²⁷⁵分の1に近く、怒っている類人猿よりも10億以上少ない可能性があります。結論は、SHA-256の衝突を恐れているが、ロードされたショットガンを常に持っていないと、優先順位が間違っているということです。また、テキサスを台無しにしないでください。

Answer 2

いいえ、メッセージの長さは衝突の可能性に影響しません。

その場合、アルゴリズムは壊れています。

すべての1バイト入力に対してSHAを実行し、次にすべての2バイト入力に対して実行するなどして、自分で試してみて、衝突が発生するかどうかを確認できます。おそらくそうではないでしょう。なぜなら、SHA-256またはSHA-512の衝突を発見した人は誰もいないからです（または少なくともウィキペディアから秘密にしていたからです） 。

Answer 3

最小入力サイズはありません。SHA-256アルゴリズムは事実上ランダムマッピングであり、衝突確率は入力の長さに依存しません。1ビット入力でも「安全」です。

入力は、SHA-256の場合は512ビット（64バイト）の倍数（SHA-512の場合は1024の倍数）にパディングされることに注意してください。12バイトの入力（Thomasが彼の例で使用したように）を使用すると、SHA-256を使用する場合、長さ64バイトの2^96の可能なシーケンスがあります。

例として、12バイトの入力Hello There！（0x48656c6c6f20546865726521）には1ビットが埋め込まれ、その後に351個のゼロビットが続き、その後にビット単位の入力の長さの64ビット表現（0x0000000000000060）が続き、512ビットの埋め込みメッセージが形成されます。この512ビットのメッセージは、ハッシュを計算するための入力として使用されます。

詳細については、RFC：4634「USSecure Hash Algorithms（SHA and HMAC-SHA）」、http：//www.ietf.org/rfc/rfc4634.txtを参照してください。

Answer 4

ハッシュは256ビット長であり、256ビットより長いものには衝突があります。

衝突がなければ、何かを小さなものに圧縮することはできません。

はい、アルゴリズムと256の2の累乗のために、多くの異なるハッシュがありますが、それらは衝突がないわけではなく、それは不可能です。

Answer 5

アプリケーションに大きく依存します。「YES」と「NO」の文字列をハッシュしてネットワーク経由で送信し、$ 100,000のローンを提供する必要があるかどうかを示す場合、かなり大きな失敗になります。回答のドメインは次のようになります。それほど大きくないので、誰かがネットワーク上で観察されたハッシュを「小さな入力」ハッシュ出力のデータベースと照合して簡単にチェックできます。

日付、時刻、名前、納税者番号、要求された金額、ハッシュされるデータの量を含めると、おそらくそれほど多くはありませんが、そのデータが事前計算されたハッシュテーブルに含まれる可能性はかなり低くなります。

しかし、私の本能を超えてあなたを指摘する研究はありません。ごめん。