暗号アルゴリズムに重大な欠陥発見の報告相次ぐ

　一般的なセキュリティ用アプリケーションに含まれる数学アルゴリズムに、これまで知られていなかった脆弱性が存在する可能性があるとのニュースに、暗号専門家のコミュニティが大騒ぎになっている。

　事の発端は、フランスのコンピュータ科学者Antoine Jouxが12日に、デジタル署名によく利用される「MD5」アルゴリズムに欠陥があることを発表したことだった。続いて、4人の中国人研究者が論文を発表し、「SHA-0」という別のアルゴリズムを迂回する方法を明らかにした。

　これらの報告は予備的なものだが、別のもっと安全なアルゴリズムを採用しなければ、今回発見された欠陥が悪用され、コンピュータコードに検知不可能な裏口を設けられたり、電子署名を偽造されたりする可能性がある。

　第3の発表は、カリフォルニア州サンタバーバラで開かれた「Crypto 2004」カンファレンスで17日夜（米国時間）に行われた。同カンファレンスでは、これ以外の論文も発表された。

　Israel Institute of Technologyの研究者、Eli BihamとRafi Chenは当初、欠陥の存在が知られている「SHA-0アルゴリズム」のセキュリティ攻撃方法を示す論文を発表する予定だった。しかしBihamは予定を変更し、同日夜の発表では、SHA-1アルゴリズムのなかにある脆弱性の特定に向けた取り組みに関する初期の成果の一部を報告した。SHA-1アルゴリズムはこれまで安全だと考えられていた。

　Bihamの発表内容が本当だとまだ認められたわけではないが、しかし、今回の発表により非常に高い人気を誇るSHA-1アルゴリズムの長期的な展望に疑問が投げかけられた。今後、研究者は別の選択肢を探す必要に迫られる可能性がある。

　SHA-1は現在、暗号化通信でも標準的に使用されているアルゴリズムで、PGPやSSLなどの人気プログラムでも採用されている。またSHA-1は、米国立標準技術研究所（NIST）で承認されており、米国政府がデジタル署名の標準技術として使用を認めている唯一のデジタル署名アルゴリズムでもある。SHA-1では、MD5の128ビットよりも長い、160ビットのメッセージダイジェストが出力されるため、その分安全度が高いと考えられている。

　Crypto 2004カンファレンス主催者のJim Hughesは17日午前、このニュースがあまりに重要なものであることから、カンファレンスの24年の歴史上初めてウェブキャストによる講演の中継を行うことになったと述べた。Jouxの発見に関する最新情報を含め、「ハッシュ衝突に関する重大な発表が3件ある」とHughesは暗号関連のメーリングリストへの投稿で記している。

　MD5やSHA-0、SHA-1といったアルゴリズムは、コンピュータ科学者の間ではハッシュ関数として知られているもので、これらは電子メールのメッセージからオペレーティングシステムのカーネルまであらゆる種類の入力信号を受け取り、ユニークなハッシュ値を生成する。この入力信号の文字列を1つでも変えると、それだけで全く別のハッシュ値が出力される。

　各種のセキュリティアプリケーションは、ユニークなハッシュ値が生成されるという特性を持つこれらのアルゴリズムを利用している。だが、悪質な攻撃者が、別の入力信号からまったく同じハッシュ値を作れてしまうとなると、ねつ造されたハッシュ値（ハッシュ衝突）を悪用できるようになってしまう。そうすると、悪質なソフトウェアを安全なものに見せかけることが可能になり、ユーザーが誤ってこれをダウンロードして実行してしまうこになりかねない。また、電子署名をねつ造して他人になりすまし、他人の銀行口座を空にしてしまうことも考えられる。

　研究者の間では、100％安全といえる暗号アルゴリズムなど存在し得ないという考え方が常識となっているため、彼らは膨大な時間をかけなくてはハッシュ値の複製ができないようなアルゴリズムを設計しようと試みている。SHA-1は、既存の技術ではハッシュ衝突を引き起こせないため、安全だとされてきた。

　SHA-1アルゴリズムは、ユニークなハッシュ値を生成するのに80ステップからなる処理をコンピュータ上でほどこす必要があるが、Bihamによれば今回は、36ステップまでのハッシュ値を複製できたという。

　もしSHA-0で見つかった脆弱性と似たものがこの先SHA-1でも見つかるようなことがあれば、ハッシュ値偽造の脅威がおよそ5億倍にもなり、理論上、高速なPCが接続されたネットワーク上でハッシュ値を偽造することが可能になってしまう。

　一方、MD5で見つかった脆弱性は、SHA-1の場合よりも差し迫った脅威となるかもしれない。オープンソースのApacheウェブサーバはMD5のハッシュを使って、数十のミラーサイトにあるソースコードが改ざんされてないものであり、実行しても安全であることを保証している。SunのSolaris Fingerprint Databaseも同様の仕組みで、同社では「正式なバイナリーディストリビューションのなかにある本物のファイルが使われていることを証明できる」としている。

　今回見つかったMD5の欠陥を攻撃者が悪用すれば、普通のPCでも数時間でハッシュ衝突を引き起こせてしまう。ただし、悪質なコードを書き、それにねつ造したハッシュ値を持たせるには、多少の時間がかかる可能性がある。

　Hughesはプログラマに対し、MD5を使わないようにすべきだと述べている。「このアルゴリズムに弱点があることが判明した今、有効な攻撃が仕掛けられるまえに、他のアルゴリズム（の使用）に移行するべきだ」（Hughes）