Cube attackの論文が出たそうです

Cube Attacks on Tweakable Black Box Polynomials Bruce Schneierのblogで8/19に取り上げられてましたが、次数の低いストリーム暗号の鍵解読の新しい手法について、論文が公開されました。著者の一人はRSAで有名な、Adi Shamirです。

Abstructのいいかげんな抄訳（大抵の機械翻訳のほうがマシかも）

大抵の暗号化方式は、GF(2)のガロア体（つまり2進数というか０と１）上のtweakable（←これどういう意味？）な多項式で記述できる。このうち、一部は秘密鍵のビットをあらわし、残りは公開された情報（たとえば暗号化されるテキストやIV(initialization vactor:鍵の初期化(random seedとか？）データ)をあらわす。
暗号解析者は、公開情報の部分をいろいろいじって、多項式の形をtweak(変形ということか？)する。こうやって、秘密鍵の部分の情報を得るのが目的だ。
この論文では、cube攻撃という新しいテクニックを紹介する。このテクニックは、tweakableな多項式を解くのに使われる。これによって、これまで発表されてきたテクニックよりも効率よく処理できるようになる。
たとえば、Triviumというストリーム暗号方式で初期化ラウンド数が少ないケースについて、以前の方式（Fischer, Khazaei, Meierによる）では、672の初期化ラウンド数に対して2の55乗の複雑さを持つ処理が必要だったが、cube攻撃の場合はそれが2の19乗ですんだ。これを実行するには、普通のＰＣで数秒しかかからない。735の初期化ラウンド数のTriviumの場合は、これまでの手法では攻撃が現実的に不可能だったが、2の230乗(230ビット)の処理で可能になった。いくつかの結果を外挿すると、1024の初期化ラウンドまでは、cube攻撃は（手当たり次第に検索するより）有効であると思われる。
これまでの攻撃手法は発見的(heuristic)なもので、暗号化方法によって調整が必要であり、一般的な計算量の見積もりもできず、ランダムと思われる多項式(鍵)に対しては有効では無いと思われたが、cube攻撃は、ランダムな多項式に対しても、以下の条件を満たせば有効であると思われる。
その条件とは、
多項式の次数：ｄ、秘密（鍵）のビット数：ｎ、公開情報のビット数：ｍとして、
ｍ ≫　ｄ　＋　log(ｎ）
を満たす場合である。
この場合の計算量は
２の(ｄ-1)乗＊ｎ＋ｎの2乗　
である。これはｄが小さければ、非常に少なくなる。
Cube攻撃はどのようなブロック暗号、ストリーム暗号やMACにも適用できるが、その条件は、少なくとも１ビット以上の出力が多項式の演算結果として得られるブラックボックスとみなすことができることである。
特筆すべきは、この手法が、side channel攻撃と組み合わせて用いることができることである。つまり、暗号化の初期段階で得られる情報が利用できると有効なのである。こういう情報はたいてい次数が低い。例えば、暗号化ハードウェアのレジスタに記録されたデータのハミングweight(ビットが立っている桁の数)などである。

Conclusionのいい加減な抄訳

この論文では、新しい暗号攻撃法を紹介して、いくつかの応用例をしめした。
この手法は、一般的に用いられる linear, differential, algebraic, そして correlation 攻撃法をまとめたものである。
この手法の有効性を示すため、これまでの手法では破ることのできなかった標準的なストリーム暗号を破った。
そして、簡略化されたTrivium暗号の一種に対して、これまでの手法よりもずっと少ない計算量で破ることができることを示した。
この研究はあくまでも今後の研究の出発点となること、およびセキュリティシステムのよりよい理解に貢献することを期待している。

つーわけで、よく使われているこれこれの暗号はもう役に立たない！という種類の話では無いようですが、次数の低い暗号化手法で、平文の情報があるていど取得できるところ、、、という分野は結構あるような気もするので、この論文に対する反応が興味深いです。ただ、次数が低いなら、力技ですでにやられているような気もします。