AES: Related-key Boomerang Attack

Schneier on Security の "New Attack on AES" (July 1, 2009) に書かれていたのですが、Biryukov と Khovratovich が AES-192, AES-256 に対して総当り攻撃よりも効率の良い攻撃法を提案しているようです。計算量はそれぞれ 2^176 (AES-192), 2^119 (AES-256) となっていて (AES-256 の計算量の方が AES-192 の計算量よりも小さい点は驚きですね)、確かに理論攻撃としては成功しているのですが、現実的には手の届かない計算量のため、現実的な脅威は小さそうです。また、攻撃には Related-key Boomerang Attack という攻撃法を用いているのですが、Related-key Attack の範疇なので、攻撃者にかなり有利な（つまり現実的に想定しにくい）環境を想定している点にも注意が必要です。あ、でも AES ベースのハッシュ関数の安全性は確実に影響を受けますね。

(20090703追記) 論文を斜め読みしたところ、CRYPTO 2009 で発表予定の Biryukov 等の結果の続きのようです。

今回の攻撃は local collision を使用するので、Boomerang Attack とは、てっきり共通鍵ブロック暗号への差分攻撃で培った攻撃手法がハッシュ関数のコリジョン攻撃にも適用され、さらにそこで考案された local collision を用いる解析手法がまた共通鍵ブロック暗号への攻撃に戻ってきたという意味かと思ってしまいました ^^; (念のために書いておきますが、Boomerang Attack という攻撃法は以前から知られている攻撃法です。）