2004年8月，カリフォルニア州サンタバーバラで開催されたCRYPTOカンファレンスにおいて，広く普及しているハッシュ関数に複数の弱点があるという発表があった。数学的には大きな意味を持つ発表だが，すぐに問題になることはない。とはいえ，そろそろ，暗号コミュニティは新しいハッシュ標準の開発に一致団結して取り組むべきだろう。
一方向ハッシュ関数は暗号技術の要素の1つで，さまざまな目的に使われる。例えば，暗号化および電子署名の両方に，公開鍵暗号アルゴリズムと組み合わせて利用される。内容が改ざんされていないか検証するために使われるし，認証目的にも使われる。さまざまなプロトコルにおいて，あらゆる目的に使用されているのだ。一方向ハッシュ関数の現代暗号への“貢献度”は，暗号アルゴリズムそのものよりずっと大きい。
1990年，Ron Rivest氏がMD4と呼ばれるハッシュ関数を発明した。彼は1992年にMD4を改良し，別のハッシュ関数MD5も開発した。1993年には，米国家安全保障局（NSA）がMD5によく似たハッシュ関数SHA（Secure Hash Algorithm）を公開した。そして1995年，新たに見つかった弱点により，NSAはSHAに変更を施した。ただし，弱点の詳細は明らかにされていない。この新しいアルゴリズムは，SHA-1と呼ばれた。現在，最も広く利用されているハッシュ関数はSHA-1だが，古いアプリケーションではMD5もまだ使われている。
一方向ハッシュ関数には2つの特性がある。1つは一方向性だ。一方向性とは，メッセージのハッシュ値を計算することは容易だが，ハッシュ値から元のメッセージを作り直すことは不可能という性質だ。2つ目は，“衝突”しない点である。これは，同じハッシュ値を持つ2つのメッセージを見つけることが不可能という性質だ。なお，ここでの“不可能”とは，“現実的な時間内では無理”という意味だ。これらの特性の背後にある暗号理論は分かりにくいので，興味のある方は私の著書「Applied Cryptography」（訳注：邦題は「暗号技術大全」）を読んでほしい。
「あるハッシュ関数が破られる」ということは，そのハッシュ関数が2つの特性のどちらか一方，もしくは両方を持ち合わせていないことを意味する。MD4“系列”のハッシュ関数の解読は，過去10年間に何度も試みられてきた。そして，MD4アルゴリズムを単純化させた“簡易版”や，MD4アルゴリズムの一部分に関する解析結果が得られてきた。そして2004年，Eli Biham氏とRafi Chen氏のチームと，さらにAntoine Joux氏が単独で，MD5およびSHAに関する極めて興味深い結果を発表した。SHAで衝突が示されたのだ。さらに，当コラムの執筆時点では未確認だが，SHA-1でも衝突が見つかったらしい。
これらの結果が及ぼす影響の大きさは，人によって異なる。暗号研究者にとっては極めて大きな出来事だ。革新的とまでは言えなくても，暗号分野においては確かな進歩である。衝突を見つけた研究者の手法はほかの用途にも使えるだろう。最終的には，より安全なシステムの設計に役立つ。暗号分野の研究は，このようにして進歩してきた。つまり，ほかのアルゴリズムを破ることで新たなアルゴリズムを設計する手法を学ぶのである。さらに，NSAのアルゴリズムには何らかの異なる技術が使われているはずだ。こうした技術は，非公開の研究活動で生み出される。NSAのアルゴリズムが解読できれば，「NSAの暗号技術がどの程度優れているのか」という永遠の疑問を解く大きな手がかりになる。
暗号システムの利用者，つまり，ほとんどの読者にとって，一方向ハッシュ関数の衝突が見つかったことは大ニュースだが，それほど心配する必要はない。MD5とSHAの安全性が直ちに失われるわけではないからだ。これらの手法を使っても，すぐに電子署名を破ったり暗号化メッセージを読んだりできるようにはならない。このニュースによって，電脳世界の安全性が低下したわけではない。
しかしNSAの内部では昔から「攻撃は常に進歩する。後退することはない」と言われてきた。今回の手法の改良が進めば，いつの日か，その手法を基にした実際の攻撃が可能になるだろう。
SHA-1以外のアルゴリズムに移行すべき時期が来ている。
幸いなことに，代替手段はいくつもある。これまで米国立標準技術研究所（NIST）は，ビット長がより長い――つまり，破られにくい――SHA-224やSHA-256，SHA-384，SHA-512などを標準のハッシュ関数として採用してきた。これらは既に米国政府標準として指定されており，もう使える状態にある。これでも当座の間に合わせには十分だが，NISTにはもっとがんばってもらいたい。
NISTには，新たなハッシュ関数を募る世界規模のコンテストを開催してほしいのだ。ちょうど，DESの代替として新しい暗号アルゴリズムAESを募集したときのように。ハッシュ関数のアルゴリズムを募集し，暗号コミュニティが実施する一連の分析作業を指揮してほしい。新しい標準策定を願うコミュニティは，さまざまな候補アルゴリズムを喜んで解析するだろう。
現在利用可能なほとんどのハッシュ関数と，実際に普及しているすべてのハッシュ関数が，MD4の原理に基づいている。過去10年間でハッシュ関数はよく研究されたので，こうした研究成果はより安全なハッシュ関数の開発に役立てられるだろう。
SHA-1の安全性がまだ問題になっていない今こそ，新しいハッシュ関数の開発に取り掛かるべきだ。実際に問題になり始めてから取り掛かるよりもずっとよいはずだ。
＜http://news.com.com/...＞＜http://www.freedom-to-tinker.com/archives/000661.html＞＜http://www.mail-archive.com/...＞
技術情報：＜http://www.cs.technion.ac.il/users/wwwb/cgi-bin/...＞＜http://www.cs.technion.ac.il/~biham/Reports/Slides/...＞
NISTのSHAサイト：＜http://csrc.nist.gov/CryptoToolkit/tkhash.html＞
Computerworldに掲載されたオリジナル記事：＜http://www.computerworld.com/printthis/2004/...＞
Copyright (c) 2004 by Bruce Schneier.
◆オリジナル記事「Cryptanalysis of MD5 and SHA」
◆「CRYPTO-GRAM September 15, 2004」
◆「CRYPTO-GRAM September 15, 2004」日本語訳ページ
◆「CRYPTO-GRAM」日本語訳のバックナンバー・ページ
◆この記事は，Bruce Schneier氏の許可を得て，同氏が執筆および発行するフリーのニュース・レター「CRYPTO-GRAM」の記事を抜粋して日本語化したものです。
◆オリジナルの記事は，「Crypto-Gram Back Issues」でお読みいただけます。CRYPTO-GRAMの購読は「Crypto-Gram Newsletter」のページから申し込めます。
◆日本語訳のバックナンバーは「Crypto-Gram日本語訳」のページからお読みいただけます。
◆Bruce Schneier氏は米Counterpane Internet Securityの創業者およびCTO（最高技術責任者）です。Counterpane Internet Securityはセキュリティ監視の専業ベンダーであり，国内ではインテック コミュニケーションズと提携し，監視サービス「EINS/MSS+」を提供しています。
