ストリーム暗号 A5/1 の解読

2009年12月27日～30日にベルリンで開催された 26th Caos Communication Congress (26C3) という国際会議において、GSM 携帯で使用されているストリーム暗号 A5/1 の解読に関する講演がありました。講演者の Karsten Nohl は Mifare Classics のクラッキングで有名な研究者です。何となく内容が理解できたので、以下に要点をメモしておきたいと思います。

GSM とは携帯電話の通信規格の一つで、世界中の多くの国で使用されています（日本では使用されていません）。GSM 携帯では、通信内容の秘密保持のために、ストリーム暗号 A5/1 が使用されています。A5/1 は 1987 年に開発されたのですが、アルゴリズムは秘匿にされていました。しかし 1994 年には設計概要がリークされ、さらに 1999 年にはリバースエンジニアリングされたため、現在ではアルゴリズムは特定されています。A5/1 の鍵長は 64 ビットですが、うち 10 ビットは 0 に固定されているらしく、実質的な鍵長は 54 ビットとなっています。

現在の暗号解析の世界では、鍵長 54 ビットの暗号は安全とは見なされません。というのも、鍵の全数検索が十分に可能だからです。全くの個人的な感覚なのですが、１台のPCを用て数十時間から数百時間が必要になるのではないでしょうか。今回の Nohl の講演は "A5/1 Security Project" というプロジェクトの紹介なのですが、このプロジェクトは、鍵の全数検索による A5/1 の瞬間的な解読を最終目標に据えています。それを実現するために、事前計算テーブル（レインボーテーブル）を作成することが当面の目標となっています。レインボーテーブルの高速計算を実現するために、このプロジェクトは GPU コンピューティング用のコードを開発・配布しています。レインボーテーブルは現在も計算中ですので、いくつかの記事にあるような「新たな解読に成功」には至っていないようです。しかしながら、数ヶ月のうちには計算を完了させる予定とのことなので、実際に完了した頃にはまた騒ぎが起こるのではないでしょうか。なお A5/1 は過去にも何回も攻撃されていますが、過去の攻撃では、攻撃者は暗号文とそれに対応する平文を入手する必要がありました（既知平文攻撃）。それに対し今回の攻撃は、暗号文だけを入手できればよいので、攻撃の脅威は大きくなっています（暗号文単独攻撃）。

GSM には他にも A5/2, A5/3 という暗号アルゴリズムが用意されています。A5/2 は輸出規制に対応するために A5/1 の鍵長を短くしたもので、従って安全性も低くなっています。A5/3 は A5/1 の代替として三菱電機が開発したアルゴリズムで、KASUMI という暗号アルゴリズムがベースになっています。現在の GSM では A5/3 への移行が進められているのですが、残念ながら A5/3 における暗号鍵も特定できてしまうようです。ただしこれは GSM の脆弱性が原因であって、A5/3 のアルゴリズム自体が問題なわけではありません。

そもそも GSM の安全性にはもっと大きな問題（こちらを参照下さい）があるため、今回の A5/1 の解読は新しい脆弱性にはなっていない気がします。なのにこんなに話題になるのは何故なのでしょうか...