| 講演抄録／キーワード |
| 講演名 |
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ダウンロード |
|
| 研究会情報 |
| 研究会 |
ISEC LOIS |
| 開催期間 |
2005-11-14 - 2005-11-15 |
| 開催地（和） |
北九州学術研究都市 |
| 開催地（英） |
Kitakyushu Science and Research Park |
| テーマ（和） |
一般 |
| テーマ（英） |
|
| 講演論文情報の詳細 |
| 申込み研究会 |
ISEC |
| 会議コード |
2005-11-ISEC-OIS |
| 本文の言語 |
英語 |
| タイトル（和） |
|
| サブタイトル（和） |
|
| タイトル（英） |
Improved Collision Attack on MD5 |
| サブタイトル（英） |
|
| キーワード(1)（和/英） |
MD5 / MD5 |
| キーワード(2)（和/英） |
コリジョン攻撃 / collision attack |
| キーワード(3)（和/英） |
メッセージ変更 / message modification |
| キーワード(4)（和/英） |
sufficient condition / sufficient condition |
| キーワード(5)（和/英） |
/ |
| キーワード(6)（和/英） |
/ |
| キーワード(7)（和/英） |
/ |
| キーワード(8)（和/英） |
/ |
| 第1著者 氏名（和/英/ヨミ） |
佐々木 悠 / Yu Sasaki / ササキ ユウ |
| 第1著者 所属（和/英） |
電気通信大学 (略称： 電通大)
The University of Electro-Communications (略称： Univ. of Electro-Comm.) |
| 第2著者 氏名（和/英/ヨミ） |
内藤 祐介 / Yusuke Naito / ナイトウ ユウスケ |
| 第2著者 所属（和/英） |
電気通信大学 (略称： 電通大)
The University of Electro-Communications (略称： Univ. of Electro-Comm.) |
| 第3著者 氏名（和/英/ヨミ） |
國廣 昇 / Noboru Kunihiro / |
| 第3著者 所属（和/英） |
電気通信大学 (略称： 電通大)
The University of Electro-Communications (略称： Univ. of Electro-Comm.) |
| 第4著者 氏名（和/英/ヨミ） |
太田 和夫 / Kazuo Ohta / |
| 第4著者 所属（和/英） |
電気通信大学 (略称： 電通大)
The University of Electro-Communications (略称： Univ. of Electro-Comm.) |
| 第5著者 氏名（和/英/ヨミ） |
/ / |
| 第5著者 所属（和/英） |
(略称： )
(略称： ) |
| 第6著者 氏名（和/英/ヨミ） |
/ / |
| 第6著者 所属（和/英） |
(略称： )
(略称： ) |
| 第7著者 氏名（和/英/ヨミ） |
/ / |
| 第7著者 所属（和/英） |
(略称： )
(略称： ) |
| 第8著者 氏名（和/英/ヨミ） |
/ / |
| 第8著者 所属（和/英） |
(略称： )
(略称： ) |
| 第9著者 氏名（和/英/ヨミ） |
/ / |
| 第9著者 所属（和/英） |
(略称： )
(略称： ) |
| 第10著者 氏名（和/英/ヨミ） |
/ / |
| 第10著者 所属（和/英） |
(略称： )
(略称： ) |
| 第11著者 氏名（和/英/ヨミ） |
/ / |
| 第11著者 所属（和/英） |
(略称： )
(略称： ) |
| 第12著者 氏名（和/英/ヨミ） |
/ / |
| 第12著者 所属（和/英） |
(略称： )
(略称： ) |
| 第13著者 氏名（和/英/ヨミ） |
/ / |
| 第13著者 所属（和/英） |
(略称： )
(略称： ) |
| 第14著者 氏名（和/英/ヨミ） |
/ / |
| 第14著者 所属（和/英） |
(略称： )
(略称： ) |
| 第15著者 氏名（和/英/ヨミ） |
/ / |
| 第15著者 所属（和/英） |
(略称： )
(略称： ) |
| 第16著者 氏名（和/英/ヨミ） |
/ / |
| 第16著者 所属（和/英） |
(略称： )
(略称： ) |
| 第17著者 氏名（和/英/ヨミ） |
/ / |
| 第17著者 所属（和/英） |
(略称： )
(略称： ) |
| 第18著者 氏名（和/英/ヨミ） |
/ / |
| 第18著者 所属（和/英） |
(略称： )
(略称： ) |
| 第19著者 氏名（和/英/ヨミ） |
/ / |
| 第19著者 所属（和/英） |
(略称： )
(略称： ) |
| 第20著者 氏名（和/英/ヨミ） |
/ / |
| 第20著者 所属（和/英） |
(略称： )
(略称： ) |
| 第21著者 氏名（和/英/ヨミ） |
/ / |
| 第21著者 所属（和/英） |
(略称： )
(略称： ) |
| 第22著者 氏名（和/英/ヨミ） |
/ / |
| 第22著者 所属（和/英） |
(略称： )
(略称： ) |
| 第23著者 氏名（和/英/ヨミ） |
/ / |
| 第23著者 所属（和/英） |
(略称： )
(略称： ) |
| 第24著者 氏名（和/英/ヨミ） |
/ / |
| 第24著者 所属（和/英） |
(略称： )
(略称： ) |
| 第25著者 氏名（和/英/ヨミ） |
/ / |
| 第25著者 所属（和/英） |
(略称： )
(略称： ) |
| 第26著者 氏名（和/英/ヨミ） |
/ / |
| 第26著者 所属（和/英） |
(略称： )
(略称： ) |
| 第27著者 氏名（和/英/ヨミ） |
/ / |
| 第27著者 所属（和/英） |
(略称： )
(略称： ) |
| 第28著者 氏名（和/英/ヨミ） |
/ / |
| 第28著者 所属（和/英） |
(略称： )
(略称： ) |
| 第29著者 氏名（和/英/ヨミ） |
/ / |
| 第29著者 所属（和/英） |
(略称： )
(略称： ) |
| 第30著者 氏名（和/英/ヨミ） |
/ / |
| 第30著者 所属（和/英） |
(略称： )
(略称： ) |
| 第31著者 氏名（和/英/ヨミ） |
/ / |
| 第31著者 所属（和/英） |
(略称： )
(略称： ) |
| 第32著者 氏名（和/英/ヨミ） |
/ / |
| 第32著者 所属（和/英） |
(略称： )
(略称： ) |
| 第33著者 氏名（和/英/ヨミ） |
/ / |
| 第33著者 所属（和/英） |
(略称： )
(略称： ) |
| 第34著者 氏名（和/英/ヨミ） |
/ / |
| 第34著者 所属（和/英） |
(略称： )
(略称： ) |
| 第35著者 氏名（和/英/ヨミ） |
/ / |
| 第35著者 所属（和/英） |
(略称： )
(略称： ) |
| 第36著者 氏名（和/英/ヨミ） |
/ / |
| 第36著者 所属（和/英） |
(略称： )
(略称： ) |
| 講演者 |
第1著者 |
| 発表日時 |
2005-11-15 13:15:00 |
| 発表時間 |
25分 |
| 申込先研究会 |
ISEC |
| 資料番号 |
ISEC2005-104, OIS2005-67 |
| 巻番号（vol） |
vol.105 |
| 号番号（no） |
no.396(ISEC), no.398(OIS) |
| ページ範囲 |
pp.35-42 |
| ページ数 |
8 |
| 発行日 |
2005-11-08 (ISEC, OIS) |
|