How To Steal Cars − A Practical Attack on KeeLoq
http://www.cosic.esat.kuleuven.be/keeloq/
この暗号は「KeeLoq」と呼ばれるもので、NLFSR (Non-Linear Feedback Shift Register）というストリーム暗号をベースにしたブロック暗号システムだ。1980年代に開発され、Microchip Technology 社により販売されている。それぞれの鍵の暗号は「100台のPCを使って数十年かかってやっとブルートフォースできる」数であるため、これまでは、安全性の高い暗号システムだと言われてきた。
KeeLoq は KeeLoq 暗号アルゴリズムを使って、32ビットのブロック・サイズの64ビットの Hopping Code を作る。Hopping Code とは、トランスミッターに搭載された乱数生成システムを使って毎回違う暗号鍵をレシーバーに送り、レシーバー側でも搭載された同じ乱数生成システムを参照してその鍵がその時の正しい鍵かどうかを確認するもので、こうして毎回違った鍵を送受信することによって、偽キーの使用を不可能とするものだ。
しかし現実的には、もっと短い暗号鍵を使っているため、2週間かかればブルートフォースできると言われていた。これを変えたのが、Microchip Technology 社の独占技術であるアルゴリズムの仔細が、去年市場に出回ったことだ。
前述の研究者たちは、Slide Attack と Meet in the Middle と言われる暗号解析手法を用いて、AMD Athlon 64 X2 4200+ を 50台使った分散コンピューティングで、KeeLoq のアルゴリズムを約2日で解析。次に、ターゲットの鍵のそばで1時間ほど「例えば持ち主のポケットの中にある時」に探査し、偽キーを作ることに成功したのだった。
この研究結果は8月にカリフォルニア州サンタバーバラで行われた「Crypto 2007」という暗号学者コンファレンスで発表された。発表は最後に「じきに暗号学者たちは高価な車を乗り回すことになるだろう」と締めくくられていたのが面白い。【執筆：米国 笠原利香】
 | コンファレンスでの発表資料 |
CRYPTO 2007
http://www.iacr.org/conferences/crypto2007/
