| 講演抄録／キーワード |
| 講演名 |
2005-11-15 13:15
Improved Collision Attack on MD5
○Yu Sasaki・Yusuke Naito・Noboru Kunihiro・Kazuo Ohta（Univ. of Electro-Comm.） |
| 抄録 |
（和） |
EUROCRYPT2005でWangらによりMD5への攻撃が提案された．この攻撃はコリジョンを作るための十分条件 (sufficient condition) を求め，確定的に条件を満たすようにメッセージを変更して攻撃の成功確率を上げている．この攻撃ではメッセージを変更しても満たせない条件が37個残る．よって攻撃の計算量は$2^{37}$である．その後KlimaはWangらの条件を33個に減らし，攻撃の計算量を$2^{33}$に改良した．
本稿では，より多くの条件を満たすことができるメッセージの変更法を提案し，満たすことのできない条件の数を29個にする．この修正は確率的で，修正が
成功する確率は全体でおよそ1/2である．よって我々の提案する攻撃の計算量は$2^{30}$となる．さらにWangらのコリジョン探索アルゴリズムを改良し，
計算量を5/8程度に抑える方法を提案する |
| （英） |
In EUROCRYPT2005, a collision attack on MD5 was proposed by Wang et al.
In this attack, conditions which are sufficient to generate collisions (called ``sufficient condition") are introduced. This attack raises the success probability by modifing messages to satisfy these conditions. In this attack, 37 conditions cannot be satisfied even messages are modified. Therefore, the complexity is $2^{37}$. After that, Klima improved this result. Since 33 conditions cannot be satisfied in his method, the complexity is $2^{33}$.
In this paper, we propose new message modification techniques which are more efficient than attacks proposed so far. In this method, 29 conditions cannot be satisfied. However, this method is probabilistic, and the probability that this method work correctly is roughly 1/2. Therefore, the complexity of this attack is $2^{30}$. Furthermore, we propose a more efficient collision search algorithm than that of Wang et al. By using this algorithm, the total complexity is reduced into roughly 5/8. |
| キーワード |
（和） |
MD5 / コリジョン攻撃 / メッセージ変更 / sufficient condition / / / / |
| （英） |
MD5 / collision attack / message modification / sufficient condition / / / / |
| 文献情報 |
信学技報, vol. 105, no. 396, ISEC2005-104, pp. 35-42, 2005年11月. |
| 資料番号 |
ISEC2005-104 |
| 発行日 |
2005-11-08 (ISEC, OIS) |
| ISSN |
Print edition: ISSN 0913-5685 |
| PDFダウンロード |
|
|