要約

  • RFC 1186はMD4の処理速度をSun SPARCで毎秒145万バイト、DEC MicroVAX IIで約7万バイト、20 MHzの80286で約3万2000バイトと記録した。衝突を作る難しさは推測だった。
  • 1992年のRFC 1320は移植しやすい参照実装で旧文書を置き換えた。2011年のRFC 6150は攻撃の成果を整理し、MD4をHistoricへ移した。

同じ128ビットの値が二つの異なる文書に付いたら、署名は何を保証できるのか。MD4が登場した時点で、この問いへの答えは検証中だった。Ronald Rivestが1990年10月に出したRFC 1186は、任意の長さのメッセージから短い要約値を作り、RSAによるデジタル署名などに使う構想を示した。ファイル全体を扱う前に、まず小さな指紋へまとめる。

速度については実物の名前が出てくる。Sun SPARCで毎秒1,450,000バイト、DEC MicroVAX IIで約70,000バイト、20 MHzの80286で約32,000バイト。大きな置換表を必要とせず、コードも比較的小さく書けるという。付録にはCのインターフェース、実装、試験用プログラムと実行例が入った。利用を考える技術者は、形容詞ではなく測定値とソースを手にできた。

耐衝突性の数字は性格が違う。異なる二つのメッセージから同じ指紋を得るにはおよそ2^64回、指定された指紋に合うメッセージを探すにはおよそ2^128回の操作が要る、とRFCは推測した。新しいアルゴリズムにはさらなる安全性分析が必要だとも書いた。処理時間は指定された機械で測れる。まだ誰も知らない攻撃の最短経路は、その測定からは出てこない。

仕様は32ビットの語、512ビットのブロック、詰め物と元の長さの符号化まで定めた。MD4は公開検討と標準化の可能性のためにパブリックドメインに置かれた。RFC自体は情報提供文書である。共通の手順を公開したことで、実装者も攻撃を探す研究者も同じ対象を見られるようになった。

RFC 1320が1992年4月にRFC 1186を置き換えた際、主な違いとして挙げたのは参照実装の移植性だった。OSI向けの識別子とパラメータの規則も加わった。持ち運びやすいコードは採用を助ける。一方、衝突に関する問いは暗号解析が決着させる領域に残った。

その結果を公的記録へ戻したのが2011年3月のRFC 6150だ。1996年には約2^20回のMD4計算で実用的な衝突攻撃が示され、2004年の結果では約2^8回になったと記す。IETFはRFC 1320をHistoricに移し、SHA-256など既存の代替へ移るよう勧めた。文書はMicrosoftの互換用途など残存する依存先も列挙する。規格表の状態変更は一度で済む。動いている相手との互換性を片付ける仕事は、そこで始まる。

出典