ハッシュ値の衝突問題

（この記事は「もっと辺境から戯れ言」に投稿した記事からの転載です）

「やばいかも」の続き。 追加の情報と併せてもう一度関連記事を挙げておきます。

• Collisions for Hash Functions MD4, MD5, HAVAL-128 and RIPEMD （差し替え版が出ているようです）
• 暗号アルゴリズムに重大な欠陥発見の報告相次ぐ
• SHA-0、MD5、 MD4にコリジョン発見、reduced SHA-1も
• 「Educated Guesswork」にも情報あり
• 「結城浩の日記」にも検証記事があります

（以降、最新情報はこちらのページでフォローしてます）

e-Print 版は速報性が優先されているせいか間違いが結構あるようですね。 詳細な検証はこれからのようです。

MD4/5 とか SHA-0/1/2 などは「一方向ハッシュ関数」とか「メッセージ要約関数」などと呼ばれていて暗号技術、特に電子署名において重要な役割を果たします。 一方向ハッシュ関数では任意のデータを小さなデータ列（MD5 では 128bit、 SHA-1 や RIPEMD160 では 160bit など）に「要約」します。

「要約」されたデータ（「ハッシュ値」と呼ばれます）から元のデータを復元することはできません。 またデータを「要約」する際、 異なる元データから同じハッシュ値が生成されないことが要求されます。（異なる元データから同じハッシュ値が生成されてしまうことを「衝突（Collision）」と呼びます）

しかし数学的には「衝突」が起きる確率をゼロにすることはできません。 したがって「衝突」が起きる確率が「実用上ほぼ」ゼロとなるロジックを検討することになります。 こうしてできたのが MD4/5 や SHA-0/1/2 などのアルゴリズムです。

今回の論文で指摘されているのは、 同じハッシュ値を持つデータ群を簡単に生成できてしまう方法です。 頻繁に「衝突」を起こせるということは暗号技術の要件（「機密性」「完全性」「認証」「否認防止」）のうちのひとつ「完全性」を損なうことになります。 また「完全性」は「認証」「否認防止」の要件のひとつになっているため、 「認証」「否認防止」も損なわれることになります。

ハッシュ値の衝突問題がどの程度のインパクトを与えるのか、 また既存のアルゴリズムに対して回避策があるのかないのかといった点は今後の専門家による検証に委ねられることになります。 今後も注目して情報を追いかけていく必要がありそうです。