| 講演名 | 2005-11-15 MD5に対するコリジョンアタックの改良 佐々木 悠, 内藤 祐介, 國廣 昇, 太田 和夫, |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | 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 / collision attack / message modification / sufficient condition |
| 資料番号 | ISEC2005-104,OIS2005-67 |
| 発行日 |
| 研究会情報 | |
| 研究会 | ISEC |
|---|---|
| 開催期間 | 2005/11/8(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Information Security (ISEC) |
|---|---|
| 本文の言語 | ENG |
| タイトル（和） | MD5に対するコリジョンアタックの改良 |
| サブタイトル（和） | |
| タイトル（英） | Improved Collision Attack on MD5 |
| サブタイトル（和） | |
| キーワード(1)（和/英） | コリジョンアタック / MD5 |
| キーワード(2)（和/英） | メッセージ変更 / collision attack |
| 第 1 著者 氏名（和/英） | 佐々木 悠 / Yu SASAKI |
| 第 1 著者 所属（和/英） | 電気通信大学 The University of Electro-Communications |
| 第 2 著者 氏名（和/英） | 内藤 祐介 / Yusuke NAITO |
| 第 2 著者 所属（和/英） | 電気通信大学 The University of Electro-Communications |
| 第 3 著者 氏名（和/英） | 國廣 昇 / Noboru KUNIHIRO |
| 第 3 著者 所属（和/英） | 電気通信大学 The University of Electro-Communications |
| 第 4 著者 氏名（和/英） | 太田 和夫 / Kazuo OHTA |
| 第 4 著者 所属（和/英） | 電気通信大学 The University of Electro-Communications |
| 発表年月日 | 2005-11-15 |
| 資料番号 | ISEC2005-104,OIS2005-67 |
| 巻番号（vol） | vol.105 |
| 号番号（no） | 396 |
| ページ範囲 | pp.- |
| ページ数 | 8 |
| 発行日 | |