中国の暗号解読研究者であるXiaoyun Wang氏が，暗号をテーマとする国際カンファレンス「CRYPTO」のランプ・セッション（rump session）で，SHA-1解読に関する新たな研究成果をAndrew Yao氏およびFrances Yao氏と共同発表した（実際の発表はAdi Shamir氏が代理で行った。なぜなら，Wang氏らへの米国ビザ発給がカンファレンスに間に合わなかったからだ）。Wang氏は，SHA-0およびSHA-1の解読に成功した研究グループのメンバーである。

　Shamir氏は詳細についてはほとんど発表しなかった。論文もなかった。ただし，Wang氏の解読手法を使えば，2の63乗回の演算で衝突を発見できるという（Wang氏の研究グループが以前発表した解読手法だと2の69乗回，総当たりのブルート・フォース攻撃だと2の80乗回の演算を必要とする）。Shamir氏によると，Wang氏らのグループは数カ月後にはさらに時間計算量*を減らせるそうだ。今回発表された解読手法は，同グループが以前公表した手法に新たな改良を加えている。数カ月かければさらなる改善が可能のようだ。2の63乗回が時間計算量の下限と考える理由はどこにもない。

訳注：*衝突を見つけるのに必要な演算回数を「時間計算量（time complexity）」と呼ぶ。

　2の64乗回未満の演算で済む高速な解読手法は，大きな事件である。既に2の64乗回という演算を処理できる強力なシステムは存在する。SHA-1の衝突の探索は現実に処理可能な演算であり，複数の研究グループが探索を試みようとしている。実際に動くソフトウエアを書けば，Wang氏らの解読手法に隠された問題を明らかにすると同時に，隠された改善方法も解明できるだろう。SHA-1にとっては，攻撃手法を記述した論文があるだけでも損害だが，実際に計算できるソフトウエアが与える損害はずっと大きい。

　SHA-1の物語はまだ終わっていない。米国家安全保障局（NSA）から聞いた格言「攻撃は常に進歩する。後退することはない」を再び書いておこう。

SHA解読の詳細：
＜http://www.schneier.com/blog/archives/2005/02/...＞

10月後半開催予定の米標準技術研究所（NIST）ハッシュ関数ワークショップ：
＜http://www.csrc.nist.gov/pki/HashWorkshop/index.html＞

S/MIME，TLS，IPsecに対する攻撃の影響：
＜http://www.educatedguesswork.org/movabletype/...＞

Xiaoyun Wang氏がCRYPTOで公表した2件の論文：
SHA-0に対する効率的な衝突探索攻撃
＜http://202.194.5.130/admin/infosec/download.php?id=1＞（PDF形式）
完全版SHA-1における衝突の発見
＜http://202.194.5.130/admin/infosec/download.php?id=2＞（PDF形式）
Wang氏の執筆したそのほかの論文：
＜http://www.infosec.sdu.edu.cn/people/wangxiaoyun.htm＞

CRYPTO出席者に対するビザ発給拒否についての情報：
＜http://www.schneier.com/blog/archives/2005/08/...＞
＜http://www.navyseals.com/community/articles/...＞

Copyright (c) 2005 by Bruce Schneier.

◆オリジナル記事「New Cryptanalytic Results Against SHA-1」
◆「CRYPTO-GRAM　September 15, 2005」
◆「CRYPTO-GRAM　September 15, 2005」日本語訳ページ
◆「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+」を提供しています。