MD4に対するコリジョンアタックの改良

概要

論文の詳細を見る
EUROCRYPT2005でWangらによって, MD4への攻撃手法が提案された.Wangらの論文中ではこの攻撃は確率2^<-6>〜2^<-2>, 計算量が2^8回以下のMD4の演算でコリジョンメッセージを作ることができると主張している.しかし, この論文中では幾つか見落とされていた問題点があった.そこで本稿では次の3点を示す.(1) Wangらの手法には攻撃が成功するための条件の記述漏れがある.その記述漏れ部分を考慮に入れ正確な成功確率評価を得た.(2) Wangらの手順の記述漏れ部分を修正し, 成功確率を評価した.(3) 3ラウンド目のsufficient conditionを修正できる"手戻りを削減したメッセージ変更法"を提案した.(1)によって, Wangらの手法では確率およそ2^<-5.61>で攻撃に成功することが分かり, (2)によって確率2^<-2>で攻撃に成功する.さらに(2)と(3)を組み合わせると成功確率がほぼ1になる.また計算量は平均3回以下のMD4の演算になる.改良方式はWangらの手法よりおよそ85倍高速であること机上検討により確認した.
社団法人電子情報通信学会の論文
2005-07-15