誕生日攻撃と衝突攻撃

23人のグループでは、2人の誕生日が一致する確率が50%を超えます。70人では99.9%を超えます。数学的には、サイズNの集合では、約√N個のサンプルを取得すると衝突確率が50%を超えます。これが誕生日限界です。

nビットのハッシュ関数では、衝突（H(m1) = H(m2)、m1 ≠ m2）を約2^{n/2}回のランダム試行で見つけられます。SHA-256（256ビット）の衝突には約2^{128}の計算量が必要で、計算上実行不可能です。MD5（128ビット）では約2^{64}であり、かろうじて実行可能な範囲です。

一般的な衝突発見では、2^{n/2}個のランダムなメッセージを生成し、ハッシュを計算して、ハッシュ値でソートし、重複を探します。メモリ計算量はO(2^{n/2})です。Rhoアルゴリズム（Floydのサイクル検出法）を使うと、同じ時間計算量のままメモリをO(1)に削減できます。van Oorschot-Wienerの並列衝突探索を使うと、ハードウェアによって時間を短縮できます。

MD5の実用的な衝突は、誕生日攻撃ではなく、差分解読を使ってWangらが2004年に発見しました。異なる2つの1024ビットメッセージが、数秒で同一のMD5ハッシュを持つようになります。Hertzbleed/chosen-prefix collisionsにより、証明書の衝突も可能になります。MD5は衝突耐性に関して完全に破られています。

より強力な攻撃では、任意の2つのプレフィックスP1、P2に対して、H(P1||S1) = H(P2||S2) となるサフィックスS1、S2を見つけます。Stevensらは2017年に、選択プレフィックスによるMD5衝突を発見しました。これは、有効なMD5署名を持つ悪意のあるCA証明書の作成に使われました。その結果、証明書でのMD5の利用は廃止されました。

GoogleのSHAttered（2017年）は、SHA-1に対する初の実用的な衝突攻撃です。異なる2つのPDFファイルが同じSHA-1ハッシュを持ちます。SHA-1の圧縮関数を2^{63.1}回計算する必要があり、CPU換算で6,500年、GPU換算で110年に相当します。費用は約110,000ドルでした。ブラウザーは2017年にSHA-1証明書を非推奨にしました。

Merkle-Damgard型ハッシュ関数（MD5、SHA-1、SHA-2）では、H(m) を知っていれば、m を知らなくても H(m||padding||m') を計算できます。これは H(secret||message) のようなMAC構成を破ります。対策としては、内部パディングと外部パディングを使用するHMAC、または長さ拡張攻撃の影響を受けないスポンジ構造のSHA-3を使用します。

衝突耐性とは、同じハッシュ値を持つ異なる2つのメッセージを見つけることです（必要な計算量は 2^{n/2}）。第二原像耐性とは、m が与えられたときに、同じハッシュ値を持つ m' ≠ m を見つけることです（必要な計算量は 2^n）。原像耐性とは、あるハッシュ値に対応する任意のメッセージを見つけることです（必要な計算量は 2^n）。衝突耐性が常に最も弱い性質です。

MACが衝突に対して脆弱なハッシュ関数を使用している場合、Hの衝突を見つけられる攻撃者はMACを偽造できる可能性があります。HMAC-MD5は、HMACの構成が単なる衝突攻撃ではなく原像攻撃を必要とするため、MD5に衝突があるにもかかわらず安全だと考えられています。ただし、新しいシステムではHMAC-MD5から移行してください。

Joux（2004）は、Merkle-Damgard型ハッシュでは、2^k 通りの衝突（同じハッシュ値を持つ 2^k 個のメッセージ）を見つけるために必要な作業量が、単一の衝突を見つける作業量の k 倍にすぎず、2^k 倍ではないことを示しました。これは連結ハッシュ（H1(m)||H2(m) は思ったほど強固ではありません）の脆弱性をさらに深刻にします。

衝突耐性のあるハッシュにはSHA-256またはSHA-3を使用してください。セキュリティ目的ではMD5とSHA-1を使用しないでください。MACにはHMAC-SHA-256またはHMAC-SHA-3を使用します。パスワードのハッシュには、SHA-2を直接使わずArgon2を使用します。長さ拡張攻撃への耐性が必要な場合は、必ずSHA-3を使用してください。

nビットのハッシュ関数で衝突を見つけるには、ハッシュ値の計算が概ね何回必要ですか。

誕生日攻撃では、2^{n/2} の計算量でハッシュの衝突を見つけられます。MD5では実用的な選択プレフィックス衝突が可能で、SHA-1は2017年に破られました。長さ拡張攻撃は、単純な H(key||msg) 形式のMACを破ります。SHA-256またはSHA-3を使用し、メッセージ認証にはHMACを使用してください。次は中間一致攻撃です。