HOME
MD5を含む各種ハッシュアルゴリズムに欠陥か
2004/8/24
(随時更新)
アメリカ・カリフォルニア州サンタバーバラで2004年8月15日から行われた暗号専門家のカンファレンス"Crypto 2004"で、MD5を含む各種のハッシュアルゴリズムに、異なる内容で同一のハッシュ値を作成できてしまう欠陥--ハッシュ衝突またはハッシュコリジョンと呼ばれる--があると発表された。
MD5の欠陥は「同一でないが、ハッシュ値は同じになる値を計算するのに、普通のPCで1時間程度ですむ」レベルだという。
原論文に「IBM P690を使用した」と書かれていたため「普通のPCで1時間程度」などと報道されたのかもしれないが、調べてみるとIBM P690は最大搭載RAMが1TB(!)というマルチプロセッサマシンで、とても「普通のPC」とはいえない。
改ざんの有無を検証する手段としてのMD5
今のところ、
- 「テキストデータの場合、文書として意味のある改ざんや、スクリプトとして意味のある改ざん」
- 「バイナリデータの場合、バックドアとして機能する改ざん」
を行って、ハッシュ値を同じにできたという報告はないようだ。...だがバイナリデータの方は､MD5を同じにしたバックドア付きの改ざんが可能だろうという意見が、専門家から出ている。
だが「プレーンテキストに文書として意味のある改ざんをして、MD5を同じにする」のはムリなんじゃないか...と思うのだが。テキストの末尾に多量のゴミ文字列でもつけない限り。...メールについては、ひょっとするとMIMEのアタッチメントを偽装して可能か?...でもメール本文の電子署名はアタッチメントとは別だし...。
スクリプトの場合は、改ざんの有無はソースを見れば一目瞭然だろうが、その逆も真--ソースを確かめるまで改ざんがわからない--かもしれない。
それから、公開鍵のフィンガープリントとしては、SHA-1以上のハッシュ関数を使うのがすでに一般的になっていて、MD5はほとんど使われないようだが、今回の衝突発見によってMD5は決定的に使われなくなるかもしれない。
パスワードを照合する手段としてのMD5
UNIX系OSではパスワードの暗号化方式にMD5を選択すると、/etc/shadowにパスワードのMD5値が保存される。
今回のMD5ハッシュ衝突を計算するには、MD5と、そのもとになる値の両方が必要らしいので、MD5パスワードについては直接の影響はないのではないか。ただしこれについては、まだはっきりしたことはいえない。
チャレンジ・レスポンス方式でのMD5
OTP(One Time Password)、SSH、APOP、Apacheのダイジェスト認証などでは、毎回異なるチャレンジ文字列とパスワードを連結してMD5値をとり、それをネットワークに流す。チャレンジ文字列が毎回異なるので、MD5値も毎回異なる。この仕組に対して、今回のハッシュ衝突が影響を与えるかというと、ほとんど関連がないのではないだろうか。
解説記事など
詳細は以下を参照。
- 「今こそ新しい暗号化標準が必要だ」(ITmediaアンカーデスク)
http://www.itmedia.co.jp/anchordesk/articles/0408/20/news063.html
暗号ソフト開発の原典ともいうべき"Applied Cryptography"(邦題『暗号技術大全』)の著者、ブルース・シュナイアー氏による解説。まず、この解説を読むとよいだろう。
- 「暗号アルゴリズムに重大な欠陥発見の報告相次ぐ」(CNET Japan)
http://japan.cnet.com/news/sec/story/0,2000050480,20070525,00.htm
速報的な記事。
- 同記事の原文："Crypto researchers abuzz over flaws" (CNET)
http://news.com.com/2100-1002-5313655.html
速報的な記事。
- SHA-0、MD5、MD4にコリジョン発見、reduced SHA-1も(スラッシュドット・ジャパン)
http://slashdot.jp/article.pl?sid=04/08/18/0257220
ここにはCrypto 2004に参加していた、すずきひろのぶ氏からの投稿、解説があります。
- 発表者自身による文書"Collisions for Hash Functions MD4, MD5, HAVAL-128 and RIPEMD"(Cryptology ePrint Archive)
http://eprint.iacr.org/2004/199/
前半512ビットが同一、後半512ビットが同一でないが、ハッシュ値は同じになる値のペアが例として記載されている。読んだ専門家からは、不明瞭な部分があるという意見も。このペーパーの質はともかく、Crypto 2004での発表自体は大喝采だったそうな。
- Crypto 2004のサイト
http://www.iacr.org/conferences/crypto2004/
http://www.iacr.org/conferences/crypto2004/rump.htmlからは、ハッシュ衝突の発表をWebcastしたものをWMVファイル(Windows Media Player)でダウンロードできる。
- 「ハッシュ関数SHA-1及びRIPEMD-160の安全性について」(情報処理推進機構 CRYPTREC暗号技術監視委員会)
http://www.ipa.go.jp/security/enc/CRYPTREC/fy16/cryptrec20040914_report01.html
「電子政府推奨暗号リストに掲載されているSHA-1およびRIPEMD-160については、本件のハッシュ衝突から、まず影響は受けない」という見解。
- 「暗号技術入門」の著者、結城浩氏の日記
http://www.hyuki.com/diary/dia0408.html#i20_14
- 「CRYPTO 2004 レポート ハッシュの厄日」(すずきひろのぶ氏)
http://h2np.net/docs/crypto2004.html
HOME
Copyright (C) Cybernetic Survival Network. All Rights Reserved.