暗号学的ハッシュ関数の衝突攻撃に対する安全性

05-01062
暗号学的ハッシュ関数の衝突攻撃に対する安全性評価
太 田 和 夫
電気通信大学電気通信学部教授
1 研究調査の目的
インターネット上で電子商取引を行うとき，デジタル情報の信憑性を保証（文書作成者と文書内容の対応
関係の保証）する技術として，デジタル署名（電子印鑑）技術が重要である。ハッシュ関数は，署名作成時
に任意長の署名対象の文書を予め定められた長さの値に圧縮する目的で使用される。圧縮値は，公開鍵暗号
の秘密鍵を用いて署名生成処理される。
ところで，ハッシュ関数（H）は情報を圧縮するという目的から，多対１の関係を与えるので，異なる文書
（M1 と M2)が同じ値（H(M1)=H(M2)）となることは避けられない。この事象は，ハッシュ値のコリジョン（衝
突）とよばれる。ハッシュ値の衝突が容易に見つかるなら，デジタル署名の信憑性が崩れてしまい，IT 社会
の脅威となる。
ハッシュ関数が安全とは，
実行可能な時間内で衝突を発見できないことである。
安全性の理論的な証明は，
現在の技術では不可能である。各種のハッシュ関数方式は安全性には不安がある。MD4，MD5，SHA-1 といっ
た方式が，RSA 社や米国標準機関（NIST）という信頼に値する組織が開発したという理由で，広く使用され
ているのが現状である。
本研究では Web ブラウザー（SSL 通信など）で広く使用されている「暗号学的ハッシュ関数
（MD4, MD5, SHA-0,
1）の安全性評価」を行う。最近（2004 年夏以降に）公表されたハッシュ値衝突攻撃法の改良法などを検討
して，ハッシュ関数の安全性を見極める。MD4,5 については，使用を続けた場合の脅威の実例を調査する。
SHA-1 については,衝突発見の可能性を見極める。
2 研究のアプローチ
本研究では「ハッシュ関数の衝突攻撃」を，二つのフェーズに分けて調査・研究を行った。
フェーズ１： 広く普及しているハッシュ方式（MD4，MD5）を研究対象にして，更に効率のよい衝突探索法
を検討する。併せて，計算機実験によって攻撃法の有効性を調べて，攻撃の感触をつかむ。
フェーズ２： SHA-0, SHA-1 に対して，現在，最強の攻撃方法である Wang らの手法の改良を試みる。
このことによって，「暗号学的ハッシュ値衝突攻撃の限界」を見極めることとする。
3 研究成果の概要
衝突攻撃は，従来は秘密鍵暗号に適用されていた「差分攻撃法」を，ハッシュ値の衝突の生成に利用した
ものである。衝突発見までの攻撃手順は，概略，次のステップに分けることができる。
ステップ１：衝突を発生しやすい文書差分（ΔM=M1-M2）の発見，
ステップ２：ΔM がハッシュ関数の計算経過で伝播する差分パス（Differential Path(DP)）の構築,
ステップ３：ΔM が構築した DP 通りに伝播するための，M1 における十分条件（Sufficient Condition (SC)）
のリストアップ
ステップ４：SC を高い確率でみたすためのメッセージ変更法（Message Modification(MM))の工夫
（１）フェーズ１
フェーズ１では，MD4 のステップ 4（MM）を改良し，従来に比較して 85 倍高速に衝突を見つける方式を提
案した（国内研究会 1 件，査読つき国際会議 1 件）
。また，その改良を MD5 にも適用し，MD5 で従来方式に比
290
べて 512 倍高速に衝突を発見する攻撃法を提案した（査読つき論文誌 1 件）。ステップ 3(SC)に関しては，従
来は手計算によって導出されていたものを，SC 自動生成アルゴリズムを提案した（国内研究会 1 件，査読つ
き国際会議 1 件）。
次に MD5 のステップ１(ΔM)の導出方法を解析し（国内研究会 1 件），その導出方法を MD4 に適用すること
で MD4 のΔM の改良を提案した（国内研究会１件，査読つき国際会議 1 件）
。さらに，MD4 で提案した改良版
のΔM に対しても，ステップ２(DP)の構築手順をアルゴリズム化した（国内研究会 1 件）。
以上，フェーズ１では 9 件（査読つき論文誌 1 件，査読つき国際会議 3 件を含む）の論文発表を行い，攻
撃技術を習得した。ここで得られた攻撃技法は，いずれも発表時点では世界最高速であった。
（２）フェーズ２
フェーズ２では，フェーズ１で習得した技術を活用して，米国標準である SHA-0, SHA-1 に対して衝突攻撃
の実行可能性を見極めることを目的とした。SHA-0,1 は実際の製品で広く使用されている。SHA-1 は SHA-0
の改良方式と位置づけられるが，その違いは僅かである。SHA-1 では，SHA-0 のメッセージ拡大関数に 1bit
の巡回シフトを追加しただけであり，メッセージ拡大関数以外は SHA-0 とまったく同じであるので，部分的
には SHA-0 の攻撃を SHA-1 に適用できる。
現在，SHA-1 に対する最速の衝突攻撃の計算量は２６２ 回の SHA-1 演算である。実環境で実行可能な計算
量は２５８ から２６０ 回と言われている。さらに 16 倍（4 ビット分）以上計算量を削減可能となると，SHA
の衝突攻撃が現実的になると言われている。よって，従来の攻撃技法の延長で実現可能と思われる削減量の
見積もり予想を，本フェーズの目的とした。
まず，既存の攻撃技術の改良による可能性を検討した。その結果，SHA-1 の攻撃計算量はステップ１の解
析が最も重要であり，既存研究ではその検討が不十分であると判断した．また，ステップ２においても，Wang
らの研究グループが手動で作成した DP の具体例が存在するのみで，体系的かつ網羅的な DP の構築技法が確
立されていないことが判明した。このことから，ΔM の発見技法の進歩と，対応する DP 構築技法の進歩によ
り，衝突攻撃が実環境で成功する可能性が残されていると判断し，この 2 つの観点から研究を行った。
（途中
経過として，国内研究会 SCIS2007 にて３件発表）。
次に，SHA-0 のステップ 4(MM)の改良を検討した結果，既存攻撃より 8 倍高速に衝突を作る攻撃を発見した
（国内研究会 1 件，査読つき国際会議 1 件）。SHA-1 は SHA-0 と構造が類似しているため，今回の SHA-0 に対
する MM の改良は，SHA-1 にも適用可能と期待できる。
最後に，SHA-0,-1 のステップ 3(SC)の解析を行った。解析では，フェーズ１で MD 向けに開発した SC 自動
生成アルゴリズムを SHA-0,SHA-1 用に改造した。その結果，Wang らの既存論文の記述に，一部，誤りがある
ことを指摘した。
現在のところ，SHA-0 の衝突は発見したものの，SHA-1 の衝突発見には至っていない。
４ 各 Hash 関数の解析状況
４-1 MD4
（１）概要と開発の経緯
MD4 は 128bit 出力のハッシュ関数であり，MD5, SHA-0 および SHA-1 の設計のベースとなっている。した
がって，MD4 に対する攻撃手法はこれらのハッシュ関数に対しても有効に働くと期待できる。また，MD5 や
SHA-1 に比べて実システムでの普及範囲は狭いが， MD4 をサポートしている製品も存在する。
MD4 はその構造が他のハッシュ関数よりもシンプルであり，攻撃技法の本質を見極め易いという，攻撃者
にとっての利点を有する。衝突探索の攻撃手法の感触をつかむために，先ず MD4 への解析に着手した。
（２）既存研究の到達点
2004 年以前の MD4 への攻撃としては，衝突攻撃と MD4 のラウンド数を減らしたバージョンへの一方向性を
破る攻撃が知られていた。2004 年 8 月，Wang らが MD4 への衝突攻撃の効率を大幅に削減することに成功した。
この攻撃は，MD4 の衝突を MD4 演算を 250 回程度走らせる程度で衝突を求めることができるとしていた。ハ
ッシュ関数への攻撃は，研究成果の概要で述べたように，ステップ１～４の４つの段階に分けることができ
るが，当時発表された内容は，ステップ１～３については攻撃に成功する値のみを理由付けなしに記述する
だけであった。加えて，ステップ４についても，MM の考え方と一例を紹介するだけにとどまっていた。すな
わち，従来研究では，攻撃技術のアイデアは読み取りにくく，他のハッシュ関数への転用可能性について，
容易に判断できない状況であった。
291
（３）本研究の到達点
はじめに，ステップ 4 について検討した。既存論文では技術の考え方と一例だけを表示しており，技術を
網羅的に適用して得られた結果なのか等の，攻撃の改良の可能性の情報は読み取れなかった。本研究では，
既存 MM 技法の適用範囲が不十分であり攻撃の改良の余地があること，また既存論文に誤りがあることを指摘
し，MM 攻撃を最適化する手法を確立した。既存技術の更なる適用法を考案し，その結果，衝突を発見するス
ピードを従来よりも 85 倍程度高速化することに成功した。
次に，ステップ３に対する技術の改良を行った。まず，既存方式が主張するステップ３の結果が誤りを含
むことを指摘し修正した。ステップ３で設定する「衝突のための十分条件（SC）」とは，ステップ１および２
の結果に依存するものである。従来手法では，ステップ３は研究者の直感と経験に基づいて実行するが，SC
の導出方法は説明されていなかった。本研究では，十分条件の役割と導出方法を明らかにし，ステップ１お
よび２の結果からステップ３の結果を自動生成するアルゴリズムを設計した。この技術により，ステップ１
および２の結果を与えると 1 秒以内に十分条件を導出することが可能になった。
最後に，ステップ１と２の記法の改良に取り組んだ。既存方式で使用しているステップ１の結果（ΔM）は
衝突発見の計算量を最小にするために最適化されていると主張されていたが，その理由や評価方法は謎だっ
た。本研究では，計算量削減を目的としたステップ１の導出方法を明らかにし，既存攻撃よりも 2 倍高速化
が可能なΔM を発見した。また，ステップ１の変更に伴い，ステップ２の DP 導出が必要になるが，本研究で
新たにステップ２の DP 構築アルゴリズムを提案した。さらにステップ３，４も新しいΔM 向けに最適化する
ことで，研究の初めに自分たちで作った衝突攻撃の最速記録をさらに上回ることに成功して，MD4 の衝突発
見に要する計算時間の世界最短（計算量最小）を実現した。
本研究で発見された MD4 の衝突の例を示す。なお，`0x’ではじまる数字は 16 進数である。
Message 1
m0=0xbcdd2674
m5=0xacc992cc
m10=0xd442b710
m15=0x4989f380
m1=0x53fce1ed
m6=0x6acfb3ea
m11=0xfca27d99
m2=0x25d202ce
m7=0x7dbb29d4
m12=0xa5f5eff1
m3=0xe87d102e
m8=0xed03bf75
m13=0xfb2ee79b
m4=0xf45be728
m9=0xc6aedc45
m14=0x0f590d68
Message A
m0=0xccdd2674
m5=0xacc992cc
m10=0xd442b710
m15=0x4989f380
m1=0x53fce1ed
m6=0x6acfb3ea
m11=0xfca27d99
m2=0xa5d202ce
m7=0x7dbb29d4
m12=0x25f5eff1
m3=0xe87d102e
m8=0x6d03bf75
m13=0xfb2ee79b
m4=0x745be728
m9=0xc6aedc45
m14=0x0f590d68
Hash
MD4(Message 1) = 0xc257b7be 324f26ef 69d3d290 b01be001
MD4(Message A) = 0xc257b7be 324f26ef 69d3d290 b01be001
４-２ MD５
（１）概要
MD5 は MD4 のセキュリティを強化したハッシュ関数であり，広く普及している，様々なプロトコルで使用
されている。特に，MD5 のみを使用可能と規定されたプロトコルも見うけられる，したがって，MD5 に脆弱性
が発見されると，学術的にとどまらず社会的なインパクトも大きい。
MD4 とは異なり MD5 については 2004 年まで攻撃の成功例は存在しなかった。2004 年の攻撃技法が，どの程
度の実際の被害にまでつながるかを見極めることに，多くのセキュリティ関係者が関心を持っている。
（２）既存研究の到達点
2004 年以前の研究では，MD5 のセキュリティを弱めたバージョンに対する攻撃は数件報告されていたが，
真のＭＤ５への攻撃は報告されていなかった。2004 年 8 月 MD5 への攻撃成功の速報が発表され，2005 年 3
月に攻撃の詳細が公表された。公表情報は，ステップ１～４(⊿M，DP，SC，MM)の情報を羅列しただけであり，
その導出方法は謎に包まれていた。また，その情報の正確さにも疑問が残されていた。その後，MD5 の衝突
攻撃について，多数の改良論文が発表されている。
292
MD5 の衝突を悪用した実際のプロトコルへの悪影響として，X.508 を用いた公開鍵証明書の内容の差し替え，
ps や pdf 形式で作成された文書の表示切替などが報告されている。
（３）本研究の到達点
本研究では，第一にステップ４(MM)の技術の改良に取り組んだ。その結果，既存研究より 256 倍程度高速
に MD5 の衝突を求めることに成功した。
（これは，発表時点では世界最速記録であった。）次に，ステップ３
(SC)の導出方法を検討した。SC は⊿M,DP が定められたときに求められるものである。我々は⊿M と DP の一
部が与えられたとき，対応する最適な SC を求めるアルゴリズムを構成し，プログラムによって自動化するこ
とにも成功した。このアルゴリズムを，Wang らによって与えられた⊿M，DP に適用したところ，彼らによっ
て提案された SC よりも効率的な SC を見つけることができた。また，彼らの誤りを指摘し修正した。
次に，Wang らが⊿M，DP を構築した戦略について検討した。その結果，⊿M に関しては，それがほぼ最適
であるという根拠を与えた。しかし，DP 構築法については，部分的には解明することができたものの，複雑
な部分については，最適性の解明には至らなかった。このことは，MD5 については，さらに効率のよい DP が
発見できる可能性を示唆している。
ところで，MD5 を使用するプロトコルの脆弱性の検討の一環として，Wang らとは異なるアプローチで衝突
を起こす⊿M を構成する方法を研究した。その結果，既存方式よりも衝突を起こすのに要する計算量は増加
するものの，他の面で優位性を持つ⊿M’の構成に成功した。⊿M を変更すると，DP，SC，MM をそれに特化す
るように変更しなければならない。そこで，我々は DP 構築アルゴリズムを再度検討した。その結果，⊿M’
が与えられたときの DP’を算出できた。SC，MM 技術については MD5 の研究の初期段階で既に身に付けてお
り，MD5 への衝突攻撃を，衝突に要する計算量を小さく抑えるのとは別の観点で最良となるように，適用の
幅を広げることに成功した。この研究成果は，
「APOP プロトコルの脆弱性」として，IPA（独立行政法人情報
処理推進機構）の脆弱性監視組織に報告した。
（2007 年 4 月 19 日読売新聞朝刊，「メールのパスワード暗号
破った--- APOP 規格解読方法発見」）
最後に，本研究で発見した MD5 の衝突の例を示す。
Message 1
m0=0x3938313c
m5=0x3433302d
m10=0x63657465
m15=0x73752e61
m1=0x37322d34
m6=0x38312d35
m11=0x5f726f74
m2=0x332d3635
m7=0x61704035
m12=0x2e636264
m3=0x2e383933
m8=0x6f777373
m13=0x6976746d
m4=0x37373936
m9=0x645f6472
m14=0x632e7765
Message 2
m0=0x986e1da4
m5=0x120ea5b3
m10=0xa9b5c51e
m15=0x7745f36a
m1=0x83707d06
m6=0x7437d3e2
m11=0xc309f623
m2=0xa86e1ddd
m7=0x600f543d
m12=0xfd534f1e
m3=0xe264eedb
m8=0x7c63c5ab
m13=0xad33c7ad
m4=0xff68e19f
m9=0xe9ead9d9
m14=0xfd0380c6
Message 3
m0=0x7cd8add1
m5=0xc2c51923
m10=0x9e871e5b
m15=0x11113e41
m1=0x1b26280c
m6=0x2dbbdf90
m11=0xbd8b465e
m2=0xcd728052
m7=0xc575212f
m12=0x8d7c0efa
m3=0x5889ece0
m8=0x4fce3af4
m13=0xaab43b06
m4=0x6bb54c37
m9=0x1abd4dd5
m14=0x170fece8
Message A
m0=0x3938313c
m5=0x3433302d
m10=0x63657465
m15=0x73752e61
m1=0x37322d34
m6=0x38312d35
m11=0x5f726f74
m2=0x332d3635
m7=0x61704035
m12=0x2e636264
m3=0x2e383933
m8=0x6f777373
m13=0x6976746d
m4=0x37373936
m9=0x645f6472
m14=0x632e7765
m1=0x83707d06
m6=0x7437d3e2
m2=0xa86e1ddd
m7=0x600f543d
m3=0xe264eedb
m8=0x7c63c5ab
m4=0xff68e19f
m9=0xe9ead9d9
Message B
m0=0x986e1da4
m5=0x120ea5b3
293
m10=0xa9b5c51e
m15=0x7745f36a
Message C
m0=0x7cd8add1
m5=0xc2c51923
m10=0x9e871e5b
m15=0x11113e41
m11=0x4309f623
m12=0xfd534f1e
m13=0xad33c7ad
m14=0xfd0380c6
m1=0x1b26280c
m6=0x2dbbdf90
m11=0xbd8b465e
m2=0xcd728052
m7=0xc575212f
m12=0x8d7c0efa
m3=0x5889ece0
m8=0x4fce3af4
m13=0xaab43b06
m4=0x6bb54c37
m9=0x1abd4dd5
m14=0x170fece8
Hash
MD5(Message 1 || Message 2 || Message 3) = 0x9ae7e687 a6537ea6 132234d3 439bbb8a
MD5(Message A || Message B || Message C) = 0x9ae7e687 a6537ea6 132234d3 439bbb8a
４-３ SHA-0
（１）概要
ハッシュ関数 SHA-0 は米政府が推奨するハッシュ関数 SHA-1 の原型として知られている。SHA-0 が発表さ
れた後，セキュリティを強化した SHA-1 が発表されたため，SHA-0 が実社会の製品で使われている例はほと
んどないと思われる。しかし，両者に構造な違いがほとんどないため，SHA-0 の研究は，SHA-1 の解析をする
上での重要なステップと考えられる。また，MD4，MD5 は出力長が 128bit であったが, SHA-0 の出力長は 160bit
なので，そのセキュリティは MD4,MD5 よりも高い。その点からも，MD 向けに提案された衝突技法の，SHA-0
への適用可能性は注目されている。
（２）既存研究の到達点
SHA-0 の衝突攻撃は 1998 年の時点で報告されていた。しかし，当時の攻撃計算量は 2６1 回の SHA-0 演算と
同程度の計算量を必要とし，現実的な時間の中で発見することはできなかった。SHA-0 の衝突発見の報告は
２つのチームによる独立な成果として，同時に発表された。一方のグループは衝突発見時の計算量２５１回の
SHA-0 演算と同程度であり，もう一つのチーム（Wang のチーム）は２３９回の SHA-0 演算回であった。後者の
研究では，⊿M の導出法は細かく説明されていたが，DP や MM については曖昧な部分を残しており，技術を網
羅的に適用しているか，論文からは読み取れなかったため，攻撃法を強化できるかの検討が必要であった。
（３）本研究の到達点
本研究では，CRYPTO2005 で提案された上記の２３９回の SHA-0 演算回で衝突を見つける攻撃について検討し
た。既存攻撃では，message modification の技術を曖昧にしか説明していなかった。そこで，本研究ではこ
の部分を改良することで衝突攻撃全体の計算量を改良する可能性があることに注目した。
その結果，我々は，
新たな MM の技術として submarine modification を提案し，コリジョン発見に必要な計算量を既存方式より
8 倍程度削減できた。
SHA-0 では，80 回ある計算を繰り返して，ハッシュ値を計算している。（1 回の計算を 1 ステップと呼ぶ。
）
このうち最初の 16 ステップは，入力されたメッセージを直接計算に用い，残りの 64 ステップについては，
入力されたメッセージから別のメッセージをメッセージ拡大という関数で処理して作成するものである。従
って，最初の 16 ステップは攻撃者がメッセージ変更することで直接に計算の途中状態を操作できるが，他の
６４ステップではそれができない。衝突攻撃の効率を上げるために，攻撃者がコントロールできるステップ
数を増やすことが必要である。
既存方式では，攻撃者が自由に関与できる最後のステップであるステップ１６のみを調整することで，そ
の後 5 ステップ分を制御しようとしていた。この方法ではステップ 21 までが制御の限界である。一方，本研
究では，メッセージ拡大関数を解析し，入力メッセージを調整して，拡大後のメッセージの値をコントロー
ルする方法を発見した。これにより，ステップ 19 の計算に使われる拡大後のメッセージをコントロールでき
るようになり，ステップ 19 の出力値を調整することでその後 5 ステップ分を制御することに成功した。これ
により，最終的にステップ 24 までがコントロール可能となり，既存攻撃よりも 8 倍速く衝突を発見すること
に成功した。これは，SHA-0 に対する攻撃の世界最速記録である。
最後に，我々の方式で発見した新しい SHA-0 の衝突の例を示す。
294
Message 1
m0=0xf459644c
m5=0x073dda8d
m10=0xc4854f6e
m15=0x01f298bc
m1=0xb87cdae1
m6=0x9f044c3a
m11=0xd57662b3
m2=0xed98d4a6
m7=0x2386c95f
m12=0xd687ebe0
m3=0x7f5c304b
m8=0x8b611aa4
m13=0xf61cefe5
m4=0xa8606648
m9=0xd66ed3b9
m14=0x6d0252c2
Message 2
m0=0x76c21fb3
m5=0xb70bbb88
m10=0x352ee1b8
m15=0x7a2449cc
m1=0x8a725c5a
m6=0x705ec5b6
m11=0x87c36500
m2=0x13a6039c
m7=0x079e5dd5
m12=0xfd012cb5
m3=0xa23c1950
m8=0xf58793f6
m13=0xa51c4269
m4=0x53e65762
m9=0xd67d305e
m14=0x6a72aabd
Message A
m0=0xf459644c
m5=0x073dda8d
m10=0xc4854f6e
m15=0x01f298bc
m1=0xb87cdae1
m6=0x9f044c3a
m11=0xd57662b3
m2=0xed98d4a6
m7=0x2386c95f
m12=0xd687ebe0
m3=0x7f5c304b
m8=0x8b611aa4
m13=0xf61cefe5
m4=0xa8606648
m9=0xd66ed3b9
m14=0x6d0252c2
Message B
m0=0xf6c21ff1
m5=0xb70bbbca
m10=0xb52ee1f8
m15=0xfa24498c
m1=0x8a725c5a
m6=0xf05ec5b4
m11=0x07c36502
m2=0x93a603de
m7=0x879e5dd7
m12=0xfd012cb7
m3=0xa23c1910
m8=0xf58793b6
m13=0x251c4229
m4=0x53e65722
m9=0x567d305e
m14=0xea72aabd
Hash
SHA-0(Message 1 || Message 2) = cad681a1 354105dc ac31607b 6ccaba44 c76d1948
SHA-0(Message A || Message B) = cad681a1 354105dc ac31607b 6ccaba44 c76d1948
４-４ SHA-１
（１）概要
SHA-1 は米政府標準暗号に指定された出力長 160bit のハッシュ関数である。SHA-0 は SHA-1 の改良版とし
て作られた。SHA-0 のメッセージ拡大関数に，1bit の巡回シフトを加えただけである。SHA-1 ではメッセー
ジ拡大関数以外は SHA-0 と同じなので，部分的には SHA-0 の攻撃を SHA-1 に応用することができる。2005 年
以前の研究でも部分的な攻撃は存在したが，SHA-1 に対する完全な攻撃は存在しなかった。2005 年，Wang ら
は SHA-1 の衝突を２６９回の SHA-1 演算で発見できる方法を発表した。これは総当りの計算量２８０回よりも
2000 倍も高速であったため，世界中のセキュリティ研究者に大きなインパクトを与えた。
（２）既存研究の到達点
既存攻撃は SHA-0 への攻撃をベースに研究されている。SHA-0 への攻撃では，攻撃者に都合の良いビット
位置に差分を立てる必要があった。既存攻撃は，SHA-1 の 1 ビットシフトが入っている場合でも，SHA-1 の
80 ステップ中 60 ステップまでは攻撃者に都合の良い状態で差分を立てられることに注目した。また，残り
の 20 ステップ分については，非常に複雑な差分パス(DP)の探索を行った。その結果，DP を満たすための十
分条件(SC)は非常に多くなってしまうが，message modification (MM)技法により，それらを確率ほぼ１で満
たすことに成功し，最終的に 80 ステップの SHA-1 全体への攻撃を成功させた。
攻撃の詳細は，⊿M の導出方法の理由も含めて公表されている。なお，DP の構築については，研究者の経
験と直感をもとに数ヶ月かけて行うもので，具体的なアルゴリズムは作られていない模様である。MM の方法
については，
具体例はあるものの一般的な方法論はなく，何ステップまで MM を適用可能か検証されていない。
６１
現在，２ ～２６２回の SHA-1 演算と同程度の計算量で衝突が見つかるとされている。
（３）本研究の到達点
- 有効な⊿M の発見
既存方式では⊿M の選定理由を述べているものの，選定理由が厳密でない。我々は，最良の⊿M を取りこぼ
している可能性を指摘し，厳密な選定アルゴリズムを提案した。提案アルゴリズムに基づいて⊿M を探索し
295
た結果，既存方式より攻撃に有効と思われる⊿M を 10 本程度発見した。また，現実的な仮定のもとで，既存
攻撃よりも 10 倍以上早く衝突を見つけられると期待できる⊿M を見つけることに成功した。
- ハッシュ関数 SHA-1 の差分パスの構築
差分パス構築技術についても，新しいアルゴリズムを検討した。これまで SHA-1 の差分パス構築は人間の
経験や直感に基づく方法しか知られていなかったため，経験を積んだ一部の人間だけが長い時間をかけて差
分パス構築を行っていた。差分パス構築法の提案により，効率的に安全性評価が行えるようになった。SHA-1
の差分パスのうち，最後 60 ステップ分については差分のビット位置が攻撃者に都合が良く選べる。この部分
については⊿M が決まると一意に決まるため，特別なアルゴリズムは必要ない。一方，最初の 20 ステップ分
については，⊿M に対応する差分パスは非常に複雑になる。我々は攻撃に有望な⊿M を見つけたので，対応す
る DP を見つけるための DP 構築アルゴリズムを検討した。基本設計を終えたが，更なる検討が必要である。
DP 構築アルゴリズムの概要は以下のとおり。Forward Search, Backward Search, Joint Algorithm の３つ
の部品から構成する。Forward Search では，ステップ１から順番に差分パスを総当りでリスト化する。とり
うるすべての差分パスを候補としてしまうと計算量が爆発してしまうため，差分の数や各差分が持つキャリ
ーの長さに上限を設け，その閾値の中で全数探索を行う。およそ 100 万本の差分パスをこのアルゴリズムで
得る。Backward Search では，ステップ 20 から逆順に差分パスを辿る。Backward Search では，後に MM を適
用するときに有利にするために，できるだけ SC の数が少なくなるように差分パスを構築する。この結果，お
よそ 500 本の差分パスを得る。Forward Search と Backward Search の各結果は５つの変数の差分値の羅列で
ある。最後に Joint Algorithm によって，これらの結果を一致させる。まず，５つの変数のうち，最初の１
つの変数が何も調整することなく一致するものを選ぶ。次に，残り 4 個の変数のうち２つの変数をキャリー
を自由に伸ばせるというアルゴリズムのもとで，4 個の変数をすべて結合可能かどうかチェックする。
- ハッシュ関数 SHA-1 の差分パス探索アルゴリズムの実装および実験
提案した DP 構築アルゴリズムを計算機実装して，差分パス構築実験を行った。具体的には，アルゴリズム
中に含まれる３つの部品をそれぞれ独立の部品として開発し，既存攻撃で用いられている⊿M に対して適用
した。その結果， SHA-1 の round1 について 384 本のパスの構築に成功し，このパスのうち 383 本が従来知
られていたものとは異なる独自パスだった。このことにより，DP 構築アルゴリズムの有効性を確認できた。
今後は，今回発見した新規⊿M について差分パスを構築し，衝突攻撃の計算量を下げることが課題である。
〈発
表
資
料〉
[国内会議]
題
名
“MD4 に対するコリジョンアタックの改良”
内藤祐介, 佐々木悠, 國廣昇, 太田和夫.
"Improved Collision Attack on MD5" Yu
Sasaki, Yusuke Naito, Noboru Kunihiro and
Kazuo Ohta.
"MD5 のコリジョン探索における差分パス
の構築法について-Wang の差分パスは最適か
-",矢嶋純, 下山武司, 佐々木悠, 内藤祐介,
國廣昇, 太田和夫.
"How to Construct Sufficient Condition
in Searching Collisions of MD5" Yu Sasaki,
Yusuke Naito, Jun Yajima,
Takeshi Shimoyama, Noboru Kunihiro and
Kazuo Ohta.
"SHA-0 に対する Message Modification の
考察" 内藤祐介, 佐々木悠, 下山武司, 矢嶋
純, 國廣昇, 太田和夫.
掲載誌・学会名等
電子情報通信学会研究会 ISEC2005-58
発表年月
2005 年 7 月
電子情報通信学会研究会 ISEC2005-104 2005 年 11 月
暗号と情報セキュリティシンポジウム,
2006 年 1 月
SCIS2006 4E1-2
暗号と情報セキュリティシンポジウム,
2006 年 1 月
SCIS2006 4E1-1
暗号と情報セキュリティシンポジウム
2006 年 1 月
SCIS2006 4E1-3
296
“SHA-1 Collision Attack における
Disturbance Vector の探索について”
岩崎輝星，内藤祐介，矢嶋純，佐々木悠，下
山武司，國廣昇，太田和夫.
“SHA-1 差分パス構築アルゴリズム”
佐々木悠，内藤祐介，矢島純，岩崎輝星，下
山武司，國廣昇, 太田和夫.
“SHA-1 差分パス自動生成ツール” 矢島純，
佐々木悠，岩崎輝星，内藤祐介，下山武司，
國廣昇, 太田和夫.
“ハッシュ関数のコリジョン探索の改
良-新たな Advanced Message
Modification の提案-” 内藤祐介,太田和
暗号と情報セキュリティシンポジウム
2007 年 1 月
SCIS2007 1A1-3
暗号と情報セキュリティシンポジウム
2007 年 1 月
SCIS2007 1A1-4
暗号と情報セキュリティシンポジウム
2007 年 1 月
SCIS2007 1A1-5
暗号と情報セキュリティシンポジウム
2007 年 1 月
SCIS2007 1A1-1
夫,國廣昇.
“Differential Path Search Algorithm for
暗号と情報セキュリティシンポジウム
2007 年 1 月
First Round of MD4” Wang Lei, Yu Sasaki,
SCIS2007 1A1-2
Kazuo Ohta, Noboru Kunihiro.
[査読つき国際会議]
題
名
"Improved Collision Attack on MD4 with
Probability Almost 1" Yusuke Naito, Yu
Sasaki, Noboru Kunihiro and Kazuo Ohta.
"How to Construct Sufficient Conditions
for Hash Functions" Yu Sasaki, Yusuke
Naito, Takeshi Shimoyama, Jun Yajima,
Noboru Kunihiro and Kazuo Ohta.
"Improved Collision Search for SHA-0”
Yusuke Naito, Yu Sasaki, Jun Yajima,
Takeshi Shimoyama, Noboru Kunihiro and
Kazuo Ohta.
“New Message Difference for MD4,” Yu
Sasaki, Lei Wang, Kazuo Ohta and Noboru
Kunihiro.
"A New Strategy for Finding a
Differential Path" Jun Yajima, Yu Sasaki,
Yusuke Naito, Terutoshi Iwasaki, Takeshi
Shimoyama, Noboru Kunihiro and Kazuo Ohta.
掲載誌・学会名等
Proceeding of ICISC2005，LNCS 3935，
pp.129-145
発表年月
2005 年 12 月
Proceeding of Vietcrypt2006，LNCS 4341，
2006 年 9 月
pp.115-130
Proceeding of Asiacrypt2006，LNCS 4284，
2006 年 12 月
pp.21-36
Fast Software Encryption 2007.
2007 年 3 月
ACISP 2007
2007 年 7 月予
定
[査読つき論文誌]
題
名
掲載誌・学会名等
IEICE Transaction on Fundamentals
"Improved Collision Attacks on MD4 and
of Electronics, Communications and
MD5” Yu Sasaki, Yusuke Naito, Noboru
Computer Sciences, Vol. E90-A, No.1,
Kunihiro, Kazuo Ohta.
pp. 36-47, 2007.
297
発表年月
2007 年 1 月