第1回　すべてはここから始まった〜SHA-1の脆弱化

神田 雅透
NTT情報流通プラットフォーム研究所
情報セキュリティプロジェクト
主任研究員 博士（工学）
2006/3/9

---

　NISTの反応

　MD4やMD5、SHA-0については実際に衝突が起きるメッセージ組の例が示されているのに対し、SHA-1については、最良の攻撃法と期待される誕生日攻撃よりも効率的に衝突を見つける攻撃法が見つかったという段階であり、Wang氏らの攻撃によっても具体的に衝突が起きる例が求まったわけではない。しかしながら、SHA-1の安全性が明らかに従来よりも大幅に低下したという意味において、現在のSHA-1の状態は、DESに対する初めての理論的な攻撃法である差分解読法が提案された1990年当時の状況と似ている。

　そこで、NISTは、SHA-1に大きな問題が生じる前に、少なくとも新規の米国政府の情報システムからはSHA-1の利用を縮小させ、2010年までにはSHA-2（具体的にはSHA-256）に移行するよう誘導している。実際、「Recommendation for Key Management」［参考文献6］や「Cryptographic Algorithms and Key Sizes for Personal Identity Verification」［参考文献7］では、ガイドラインとしてSHA-1からSHA-256に変更するよう具体的に求めている。

　その一方、大きな問題としてSHA-2がSHA-1の代替としてふさわしいハッシュ関数であるのかという議論がある。というのも、昨今、MD5やSHA-0に対する攻撃成功例が相次いでいること、またWang氏らの攻撃によって予想よりも簡単にSHA-1への攻撃が成功したことなどから、NISTや暗号研究者はMD5／SHA-1の設計方針自体に実は脆弱性があるのではないかと疑い始めている。

　そのため、MD5／SHA-1の設計方針の延長線上で設計されているSHA-2についても本当に安全なのか確信が持てなくなってきているのが現状である。2005年10月に行われたハッシュ関数に関するワークショップ（NIST Cryptographic hash workshop）の席上でも、NIST自身が今後10年間でSHA-256に対する攻撃方法が見つかる可能性はあると考えていると述べている。

　さらに、AESの選定と同じように、新しいハッシュ関数選定のための公募を実施すべきとの意見も根強く残っており、2006年8月には再度ワークショップが開催されることが決まった。ここでの議論次第では数年後にハッシュ関数コンテストの実施もあり得る。近年国際的にもハッシュ関数の設計に関する研究が活発化しており、暗号学会でもしばらくの間、ハッシュ関数の提案や解読が続くものと考えられている。

　2010年までに暗号はどのように変わるのか

　Wang氏らによるSHA-1への攻撃が成功したことを契機に、NISTは米国政府での情報システムにおいて、SHA-1を含め、現在利用されているすべての米国政府標準の暗号技術を2010年までにより安全な暗号技術へ交代させていく方針を明確に打ち出した。これを受けて、例えばIETF［参考文献8］では、SHA-2にほとんど対応していない現在のインターネットプロトコルでも早急にSHA-256に対応させるよう、ディレクター指示が2005年11月のIETF会議で発令された。

　SHA-1以外にも、1024ビットRSA暗号やRSA署名、Triple DESなど、現在世界中で使われているデファクトスタンダードの暗号技術は、そのほとんどすべてが現在の米国政府標準の暗号技術に準じているため、今回のNISTの方針が世界に与える影響は今後大きくなっていくものと考えられる。

　本シリーズでは、「デファクトスタンダード暗号技術の大移行」と題し、2010年に向けて現在使われている暗号技術がどのように変わっていこうとしているのかを解説する。

【参考文献】

［1］ Xiaoyun Wang, Dengguo Feng, Xuejia Lai, and Hongbo Yu, “Collisions for Has Functions MD4, MD5, HAVAL-128 and RIPEMD”, IACR Eprint archive 2004/199, Aug. 2004

［2］ Xiaoyun Wang, Yiqun Lisa Yin, and Hongbo Yu, “Finding Collisions in the Full SHA-1”, CRYPTO 2005, LNCS 3621, Springer

［3］ Xiaoyun Wang, Andrew C Yao, and Frances Yao, “Cryptanalysis on SHA-1”, Proceedings of Cryptographic Hash Workshop, http://www.csrc.nist.gov/pki/HashWorkshop/2005/program.htm

［4］ Max Gebhardt, Georg Illies, and Werner Schindler, “A Note on the Practical Value of Single Hash Collisions for Special File Formats”, Proceedings of Cryptographic Hash Workshop, http://www.csrc.nist.gov/pki/HashWorkshop/2005/program.htm

［5］ Stefan Lucks and Magnus Daum, “The Story of Alice and her Boss: Hash Functions and the Blind Passenger Attack”, Presented at the rump session of Eurocrypt 2005, http://www.cits.rub.de/imperia/md/content/magnus/rump_ec05.pdf

［6］ NIST, “Recommendation for Key Management”, Special Publications SP 800-57.

［7］ NIST, “Cryptographic Algorithms and Key Sizes for Personal Identity Verification”, Special Publications SP 800-78.

［8］ P. Hoffman and B. Schneier, ”Attacks on Cryptographic Hashes in Internet Protocols”, IETF RFC4270

2/2

Index
すべてはここから始まった〜SHA-1の脆弱化
	Page1 SHA-1 Broken SHA-1の脆弱性とは何か
	Page2 NISTの反応 2010年までに暗号はどのように変わるのか

Profile

神田　雅透（かんだ　まさゆき） NTT情報流通プラットフォーム研究所 情報セキュリティプロジェクト 主任研究員 博士（工学） 東京工業大学大学院修士課程、横浜国立大学大学院博士課程修了。情報セキュリティ全般、特に共通鍵暗号の研究に従事。近年では、Camelliaの設計や普及活動にかかわる。平成17年度情報処理学会業績賞受賞。最新暗号技術（NTT情報流通プラットフォーム研究所著）を執筆。 CRYPTREC共通鍵暗号評価小委員会委員、JST評価委員会分科会委員を歴任。電子情報通信学会、情報処理学会、情報セキュリティマネジメント学会会員。情報セキュリティマネジメント学会理事。

Security&Trust記事一覧

＠ITメールマガジン　新着情報やスタッフのコラムがメールで届きます（無料）