« セ〇ム、してますか? | メイン | 「クリエイティブ・コモンズ」は誰のもの? »

ハッシュ値の衝突問題

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

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

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

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

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

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

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

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

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

(8/24 追記)

その後の記事をいくつか見る限り(CollisionsForHashFunctions 参照)、 現行で使われている一方向ハッシュ関数のアルゴリズムに今すぐインパクトを与えるものではないようです。 しかし引き続いて情報を追いかけていく必要がありそうです。

日本では CRYPTREC による暗号技術の評価レポートがあります。 このレポートによると MD5 はすでに推奨されていません(MD5 には今回の事例以外にもいくつかの脆弱性が発見されています)。 またハッシュ値の bit 長についても 「新たな電子政府用システムを構築する場合、より長いハッシュ値のものが使用できるのであれば、256ビット以上のハッシュ関数を選択することが望ましい」 とあります。(実際にそういう設計になっているかどうかは怪しいですが)

ちなみに NESSIE (New European Schemes for Signatures, Integrity, and Encryption) では SHA-1 は既にリストから外れています。

なお暗号および暗号技術については、 まず結城浩さんの『暗号技術入門 ―― 秘密の国のアリス』を読まれることをお薦めします。

暗号技術入門
暗号技術入門
posted with 簡単リンクくん at 2006. 7. 4
結城 浩著
ソフトバンクパブリッシング (2003.9)
通常2-3日以内に発送します。

Tags: [security] [cryptgraphy] [hash] [collision] [MD5] [SHA-1]
2004-08-19T14:14:30+09:00 Spiegel (licensed) [暗号・セキュリティ] このエントリーを含むはてなブックマーク

トラックバック

現在 spam 対策のため Trackback Auto Discovery を無効にしています。 あしからずご了承ください。

トラックバック URL:

» 暗号の危殆化と新しいアルゴリズム from 戯れ言++
先日 GnuPG 1.4.4 がリリースされました。 このバージョンではセキュリティ脆弱性の修正のほかに新しいアルゴリズムが2つ追加されています。 この記... [続きを読む]

トラックバック時刻: 2006年7月 7日 09:37

コメント