SHA-1が解読されてしまった。ラウンド数を減らしたバージョンやアルゴリズムを単純化させた簡易バージョンではない。“本物”のSHA-1が解読されたのだ。
大きな話題にはなっていないものの，Xiaoyun Wang氏，Yiqun Lisa Yin氏，Hongbo Yu氏による（中国の山東大学出身者が中心の）研究チームが，同チームの成果を記した論文を配布している。その内容は以下の通り。
・完全版のSHA-1において，2の69乗回の演算で衝突を発生させる手法が明らかとなった。これは，ブルート・フォース攻撃（総当たり攻撃）で必要な2の80乗回の演算と比較すると，相当少ない
・（同チームの手法を使えば）SHA-0では，2の39乗回の演算で衝突が発生する
・（同チームの手法を使えば）ラウンド数58回のSHA-1では，2の33乗回の演算で衝突が発生する
今回発表された攻撃方法は，以前発表されたSHA-0およびSHA-1への攻撃をベースにしている。SHA-1に対して，ブルート・フォース攻撃よりも短時間で衝突を発見できる手法を発見したことは，暗号解読分野において非常に大きな成果である。
私は2004年9月にSHAに関する記事を書き，別のハッシュ・アルゴリズムに移行する必要性を訴えた。新しい攻撃手法の詳細を除けば，9月に書いた記事の内容は今でもすべて通用する。そこで，必要に応じて新しい情報を追加しながら，9月の記事を引用する（訳注：以下，9月の記事からそのまま引用したパラグラフについては“『”および“』”で囲む）。
『一方向ハッシュ関数は暗号技術の要素の1つで，さまざまな目的に使われる。例えば，暗号化および電子署名の両方に，公開鍵暗号アルゴリズムと組み合わせて利用される。内容が改ざんされていないか検証するために使われるし，認証目的にも使われる。さまざまなプロトコルにおいて，あらゆる目的に使用されているのだ。一方向ハッシュ関数の現代暗号への“貢献度”は，暗号アルゴリズムそのものよりずっと大きい。』
『1990年，Ron Rivest氏がMD4と呼ばれるハッシュ関数を発明した。彼は1992年にMD4を改良し，別のハッシュ関数MD5も開発した。1993年には，米国家安全保障局（NSA）がMD5によく似たハッシュ関数Secure Hash Algorithm（SHA）を公開した。そして1995年，新たに見つかった弱点により，NSAはSHAに変更を施した。ただし，弱点の詳細は明らかにされていない。この新しいアルゴリズムは，SHA-1と呼ばれた。現在，最も広く利用されているハッシュ関数はSHA-1だが，古いアプリケーションではMD5もまだ使われている。 』
『一方向ハッシュ関数には2つの特性がある。1つは一方向性だ。一方向性とは，メッセージのハッシュ値を計算することは容易だが，ハッシュ値から元のメッセージを作り直すことは不可能という性質だ。2つ目は，“衝突”しない点である。これは，同じハッシュ値を持つ2つのメッセージを見つけることが不可能という性質だ。なお，ここでの“不可能”とは，“現実的な時間内では無理”という意味だ。これらの特性の背後にある暗号理論は分かりにくいので，興味のある方は私の著書「Applied Cryptography」（訳注：邦題は「暗号技術大全」）を読んでほしい。 』
『「あるハッシュ関数が破られる」ということは，そのハッシュ関数が持つ2つの特性のどちらか一方，もしくは両方が正しくなかったことが明らかになることを意味する。』
先月，中国の暗号研究者3人が，SHA-1に衝突が存在することを示した。すなわち，ブルート・フォース攻撃よりも迅速に衝突を発見するアルゴリズムを開発したのだ。
SHA-1は160ビット長のハッシュ値を生成する。つまり，あらゆるメッセージを160ビット長の数値に変換する。一つのメッセージからは一つのハッシュ値が計算できるので，メッセージが無限にあれば，衝突も無限に発生することになる。しかし，ハッシュ値がとりうる値は非常に多いので，衝突が偶然起きる確率は無視できるほど小さい（正確には，2の80乗個に1個の割合だ）。2の80乗個のメッセージからそれぞれハッシュ値を計算すると，同じハッシュ値を持つメッセージが1組みつかる。これは衝突を力業（ブルート・フォース）で見つける方法で，発見までに必要な演算回数はハッシュ値の長さのみに依存する。ハッシュ関数を“解読”するということは，ブルート・フォース攻撃よりも少ない手順で衝突を見つけるということだ。中国の研究チームが実現したのは，まさにこのことだ。
同チームの攻撃手法だと，SHA-1の衝突を2の69乗回の演算で発見できる。ブルート・フォース攻撃に比べ約2000倍高速だ。ただし，この手法で衝突を発見（計算）することは，現在の技術ではすぐに実現できるものではない。大規模な類似の計算例を2つ挙げ，実現の可能性が高くないことを示そう。
1999年に，ある暗号研究者のグループが暗号アルゴリズムDES（Data Encryption Standard）用の解読システムを開発した。このシステムは，2の56乗回の演算を56時間で処理できた。開発にかかったコストは25万ドルだが，同じシステムを作るだけなら5万～7万5000ドルで済むという。現在の技術で同様のシステムを作ったとしよう。ムーアの法則を適用してその性能を見積もると，56時間で2の60乗回の演算が可能だろう。2の69乗回の演算には3年3カ月を要する。開発に2500万～3800万ドルをかけられるならば，56時間に2の69乗回の演算を処理できるシステムも実現できるだろう。
ソフトウエアの観点からは，2002年に，2の64乗個の鍵を探索した分散処理ネットワーク「distributed.net」の例が比較対象になる。ある記事はこれを次のように紹介した――「コンテストには，プロセサのアイドル時間を鍵探索に貸し出そうというユーザーが33万1252人ほど参加した。探索開始から1757日（4.81年）後に，日本からの参加者が鍵を探し当てた」。ムーアの法則を当てはめると，現在なら同じ鍵探索処理が4分の1の時間で済む――言い換えれば，コンピュータの台数が4分の1になっても同じ時間で処理できる――。つまり，現在において2の69乗回の演算を行うなら，その8倍長い時間または8倍多くのコンピュータを使えばよい。
