[解決済み】SHAが衝突する可能性は、実際には無視しても大丈夫なのでしょうか？

質問

例えば、1枚1メガバイトのユニークな画像が10億枚あるとする。 各ファイルのコンテンツについてSHA-256ハッシュを計算する。 衝突の可能性は、に依存します。

• ファイル数
• <ストライク 1つのファイルのサイズ

この可能性をゼロと仮定して、どこまで無視できるのか。

どのように解決するのか？

次の瞬間、小惑星が地球に衝突して文明を破壊し、数十億人が死亡する確率はどのくらいだろうか。それよりも低い確率の不運な出来事は、実はあまり重要ではないのだと言うことができる。

完璧なハッシュ関数があり、出力サイズが n であり、かつ p ハッシュ化するメッセージ（個々のメッセージの長さは重要ではない）の衝突確率は、約 p ² /2 ⁿ⁺¹ (これは、quot;small".に対して有効な近似値です。 p よりも大幅に小さい。 2 ^n/2 ). 例えば、SHA-256では( n=256 )、10億メッセージ( p=10 ⁹ )であれば、その確率は約 4.3*10 ^-60 .

大量殺戮を行う宇宙岩石は、平均して約3000万年に一度の割合で発生します。このことから、そのような事象が次の1秒間に起こる確率は、約 10 ^-15 . それは 45 SHA-256のコリジョンよりも桁違いに高い確率で発生します。簡単に言うと、もしSHA-256の衝突を怖いと思うなら、あなたの優先順位は間違っているのです。

ハッシュ化されるメッセージを攻撃者が選べるようなセキュリティ環境では、攻撃者は10億以上のメッセージを使うかもしれません。しかし、それでも攻撃者の成功確率は驚くほど小さいことがわかります。それが、256ビット出力のハッシュ関数を使用する最大のポイントであり、衝突のリスクを無視することができるのです。

もちろん、上記はすべてSHA-256が完璧なハッシュ関数であることを前提にしていますが、証明されるにはほど遠い状態です。それでも、SHA-256はかなり堅牢だと思われる。