すべてはここから始まった〜SHA-1の脆弱化：デファクトスタンダード暗号技術の大移行（1）（1/2 ページ）

米国は、現在利用されているすべての米国政府標準の暗号技術を2010年までにより安全な暗号技術へ交代させていく方針を明確に打ち出している。現在、世界中で使われているデファクトスタンダードの暗号技術は、そのほとんどすべてが米国政府標準の暗号技術に準じているため影響は極めて大きい。2010年に向けて現在使われている暗号技術はどのように変わっていくのだろうか（編集部）

[神田雅透，NTT情報流通プラットフォーム研究所]

SHA-1 Broken

「Schneier on Security」

　2005年2月15日、世界的な暗号の権威であるBruce Schneier氏のBlog「Schneier on Security」で公表された「SHA-1 Broken」という情報は、驚きをもって世界中を駆け回った。現在、ハッシュ関数のデファクトスタンダードとして最も広く利用されているSHA-1に対して、中国・山東大学のXiaoyun Wang氏とHongbo Yu氏、セキュリティコンサルタントのYiqun Lisa Yin氏のチームが攻撃に成功したらしいというものであった。

　Wang氏とYu氏は、2004年8月にも同じハッシュ関数の仲間であるMD4、MD5、HAVAL-128、RIPEMDの攻撃に相次いで成功［参考文献1］した実績があり、またYin氏もRSAセキュリティ社在職中にRC5やRC6の開発・評価に携わるなど世界的にも有名な暗号研究者の1人である。そのため、「SHA-1 Broken」という報に接した大方の暗号研究者の反応は、彼女らがいっているというのであればまず結果に間違いはないだろう、というものであった。

　つまり、暗号研究者の興味は「本当にSHA-1の攻撃に成功したのか」ではなく、「彼女らがどのような攻撃方法を発見したのか」、さらには「SHA-1の攻撃に必要な計算量が削減できるのか」に向けられ、2005年8月に開催された世界最高峰の暗号学会であるCRYPTOでの発表［参考文献2］に注目が集まった。だが、あろうことかWang氏の米国入国ビザが下りなかったため学会不参加となり、そのときは攻撃手法の詳細が分からず、Chinese magicとさえいわれた。

　一方、米国政府の情報システムに利用する米国政府標準の暗号技術を策定する米国商務省国立標準技術研究所（NIST）は、SHA-1はまだしばらく大丈夫と思っていた節があり、それがあっさり覆った今回のWang氏の結果に少なからず衝撃を受けた形跡が見られる。ただ、幸運なことにというか先見の明があるかというか、Wang氏らの攻撃をはじめ、MD4やMD5、SHA-0などのハッシュ関数への攻撃に関する論文が多数発表されていた2004年8月時点で、すでに「SHA-1は2010年までに運用を終了し、SHA-2（SHA-224、SHA-256、SHA-384、SHA-512の総称）に移行」する計画を公表していた。

【NIST Brief Comments on Recent Cryptanalytic Attacks on Secure Hashing Functions and the Continued Security Provided by SHA-1】

http://csrc.nist.gov/NIST%20Brief%20Comments%20on%20Hash%20Standards%208-25-2004.pdf

　その意味では、今回の結果はその方針を強力に後押しすることとなった。実際、SHA-1への攻撃成功の報が流れた直後の2005年2月25日にはSHA-2への移行を実施するよう強いコメントを公表しており、その後に発行されたガイダンスにもそのことが反映されている。

【NIST Brief Comments on Recent Cryptanalytic Attacks on SHA-1】

http://csrc.nist.gov/news-highlights/NIST-Brief-Comments-on-SHA1-attack.pdf

SHA-1の脆弱性とは何か

　SHA-1は、1993年に米国国家安全保障局（NSA）が設計したハッシュ関数SHA-0の規格修正版【注1】として1995年に再設計され、NISTが規格化した米国政府標準ハッシュ関数（FIPS 180-2【注2】）である。ハッシュ長は160ビットであり、基本的な設計方法としてはメッセージ拡張関数と圧縮関数（撹拌関数の集合）とからなる構造をしている。

【注1】

SHA-0はFIPS規格化されたものの、NSAが脆弱性を発見したとの理由で規格修正が行われた。ただ、どのような脆弱性であったのかは明らかにされなかった。

【注2】

FIPS 180-2には、SHA-1のほか、SHA-2シリーズも規格化されている。しかし、現在でも一部で使われているMD5は規格化されていない。

図1　ハッシュ関数図の設計方法

　ハッシュ関数に求められる性質として以下のものがある。

一方向性

求めるハッシュ値になるような元のメッセージを求めることが困難

第2原像計算困難性（一方向性の一種）

あるメッセージと同じハッシュ値となるような別のメッセージを求めることが困難

非衝突性

同じハッシュ値となるような2つのメッセージを求めることが困難

　ハッシュ関数に対する安全性は、非衝突性に関する安全性が上限となり、誕生日攻撃【注3】（バースデーパラドックス【注4】）による耐性によって評価される。ハッシュ関数の安全性に当てはめると、1/2^（n/2）の確率（nはハッシュ長）で衝突することになり、例えば、SHA-1の場合は1/2⁸⁰の確率で衝突が起きることになる。このため、バースデーパラドックスの理論によって、約2⁸⁰回の計算を行えば高い確率で衝突するメッセージ組を少なくとも1つ作り出せる。

【注3】

誕生日攻撃法は、同一の出力値となる異なる入力値ペアを探索する際のバースデーパラドックスに基づいたハッシュ関数の攻撃手法である。

【注4】

全候補数の平方根程度の個数のデータをランダムに選択すれば、その中に同じ値を取るものが少なくとも1組、高い確率で存在するという原理。

　ところが、Wang氏らは「2⁸⁰回の計算」をしなくても衝突するメッセージ組を見つけ出すことができる攻撃方法を発見した。この方法を使えば、誕生日攻撃よりも約2000倍も高速な「2⁶⁹回の計算」で衝突するメッセージ組を見つけ出すことができる。しかも、その後も研究が進展しており、今ではさらに約100倍高速な攻撃方法も見つかっている［参考文献3］。

　非衝突性に脆弱性があると次のような攻撃が可能になる。まず、あらかじめ同じハッシュ値になる文書Aと文書Bを用意し、その一方（文書A）に正規に署名をしてもらう。その後、その署名部分を文書Bに付け替え、文書Aは破棄する。このようにすることによって、正規の署名が付いた文書Bしか残らないことになる。

図2　非衝突性の脆弱化による攻撃例

　もっとも、現在知られているようなハッシュ関数への攻撃方法では、メッセージ組に衝突を起こすような何らかの特殊な関係をもたせることになるため、その条件を満たすような特定位置のメッセージのビットを反転させなければならない。従って、任意のメッセージについて衝突を作り出せるわけではないこと、あるいは文章として不自然なメッセージとなる可能性が高く、実際の運用でも（別の手段で）改ざんを検出できる機会はあることなどから、衝突が見つかったとしても直ちに実用上の問題になるわけではないという意見も根強い。

　その一方、ファイルの最初の方にある制御コードやパディングデータ、乱数列など、文章そのものには関係していない部分において異なる2つのメッセージがすでに衝突を起こしている場合、深刻な事例に発展する可能性も指摘されている。

　例えば、衝突が起きているそれぞれの制御データの後に付けられた文書は、その内容にかかわらず同じハッシュ値を生成する異なる2つの文書を別々に表示することができる可能性がある。実際に、2つの異なる任意の内容を表示させることができるようにPostScriptファイルやTIFFファイルなどのハッシュ値を衝突させる現実的な攻撃例が明らかにされており、MD5を利用した場合に表示されるメッセージの改ざんが行われても検知できないケースがあることが具体的に示されている［参考文献4］［参考文献5］。

図3　PostScriptファイルでの現実的な攻撃例