A5/1

A5/1はストリーム暗号の一種で、GSM 携帯電話規格における通信プライバシー保護手段として採用されている。当初、秘密にされていたが、リークやリバースエンジニアリングによって徐々に明らかとなってきた。この暗号について、いくつかの深刻な弱点が指摘されている。

歴史と使用

A5/1 はヨーロッパとアメリカ合衆国で使われている。これを若干弱めた派生アルゴリズムであるA5/2が他の地域で使われている^[1]。A5/1は1987年に開発されたもので、当時GSMはヨーロッパ以外で使用することは考慮されていない。A5/2は1989年に開発された。当初どちらもその詳細は秘密にされた。しかし設計の概要は1994年にリークされ、アルゴリズム全体は1999年、Marc Briceno がGSM携帯電話を使ってリバースエンジニアリングで明らかにした。2000年当時、1億3000万のGSM利用者が音声通信の機密保護手段としてA5/1に依存していた。

セキュリティ研究家 Ross Anderson は1994年、「1980年代中ごろ、GSMの暗号強度をどうすべきかについてNATO各国の信号諜報機関の間で激しい議論があった。ドイツはワルシャワ条約機構と地理的に接していることから、強い暗号を主張した。しかし他国は強い暗号が必要とは考えなかった。現在実際に使われているアルゴリズムはフランスの設計によるものだ」と公表した^[2]。

技術的解説

A5/1ストリーム暗号は3つのLFSRを使用。各レジスタにはクロックビット（オレンジ色）があり、これらの多数決の結果と自身のクロックビットが等しい場合のみステップが進行する。

GSM転送は一連のバースト (burst) で構成される。典型的な通信路の片方向では、1つのバーストは4.614ミリ秒ごとに送信され、その中に114ビットの有効な情報が格納されている。A5/1はその114ビットに対応した鍵ストリームを生成するもので、それを平文にXORで結合してから変調する。A5/1の初期化には64ビットの鍵と公開されている22ビットのフレーム番号を用いる。GSMで実際に使用されている実装では、鍵のうち10ビットが0に固定されていて、実質的な鍵の長さは54ビットになっている。

A5/1は、3つの線形帰還シフトレジスタ (LFSR) を組み合わせ、不規則にクロック供給することで構成されている。3つのシフトレジスタの詳細は次の通り:

LFSR番号	ビット数	帰還多項式	クロック用ビット	入力ビット
1	19	$x^{18}+x^{17}+x^{16}+x^{13}+1$	8	13, 16, 17, 18
2	22	$x^{21}+x^{20}+1$	10	20, 21
3	23	$x^{22}+x^{21}+x^{20}+x^{7}+1$	10	7, 20, 21, 22

ビットの番号は最下位ビット (LSB) を0としている。

レジスタへのクロック供給は、クロックビットの多数決で決まる。それぞれのレジスタにクロックビットがひとつずつある。サイクル毎に3つのレジスタのクロックビットを調べ、多数決で0か1かを決める。そして、そのレジスタのクロックビットと多数決の結果が等しいレジスタだけにクロックが供給される。したがって、サイクル毎に2つか3つのレジスタにクロックが供給される。各レジスタがステップを進める確率は3/4である。

初期状態では、各レジスタの内容は0に設定されている。そしてここに64サイクルかけて64ビットの秘密鍵を次のように入力していく。 $0\leq {i}<64$ のサイクル番号について、i番めの鍵のビットを各レジスタの最下位ビットにXORで入力する。

R[0]=R[0]\oplus K[i].

そして、各レジスタにクロックを供給する（最下位ビットの内容は1つ上のビットに移動する）。

同様に、22ビットのフレーム番号を22サイクルかけて追加していく。次に100サイクルの間ステップを進め（その間クロック供給は上述の多数決方式による）、その間の出力は捨てる。以上が完了すると、次のサイクルから114ビットの鍵ストリームを2つ出力する。1つめの114ビットはダウンリンク用、次の114ビットはアップリンク用である。

セキュリティ

A5/1への攻撃方法のいくつかが公表されている。一部は前処理に秒単位から分単位の時間がかかる。当初、既知の平文から推定する攻撃しか知られていなかった。2003年、暗号文のみから解読できる重大な脆弱性が判明した。2006年、Elad Barkan、Eli Biham、Nathan Keller の3人は、A5/1、A5/3、GPRSに対する攻撃方法を公開し、GSM携帯電話の会話を実時間で解読したり、記録しておいて後で解読する方法があることを示した。

既知平文攻撃

1997年、Golic は時間計算量 2^40.16 の連立1次方程式の解法に基づく攻撃方法を発表した（時間は必要な連立1次方程式の解の数に比例する）。

2000年、Alex Biryukov、Adi Shamir、David Wagner は、上述の Jovan Golic の成果に基づき^[3]、時間メモリトレードオフ攻撃を使うことでリアルタイムでA5/1を解読可能であることを示した^[4]。例えば2分間ぶんの平文があれば1秒で鍵を再構築でき、2秒間ぶんの平文なら数分で鍵を再構築できるが、その前に300GBのデータについて2⁴⁸ステップを要する多大な前処理を完了しておく必要がある。前処理量、データ量、攻撃時間、メモリ使用量はトレードオフの関係にある。

同年、Eli Biham と Orr Dunkelman もA5/1への攻撃方法を発表した。これは32GBのデータを使用した 2³⁸ ステップの前処理を必要とする^[5]。

EkdahlとJohannsonは、2分間から5分間の平文を使い、数分でA5/1を破る攻撃方法を発表した^[6]。この攻撃法は前処理が不要である。2004年、Maximovらはその成果を改良し、数秒の平文から1分以内に暗号を解読する攻撃法を得た。2005年、その攻撃法をさらに Elad Barkan と Eli Biham が改良した^[7]。

GSMで使われているA5/1への攻撃

2003年、BarkanらはGSMの暗号へのいくつかの攻撃法を発表した^[8]。第一の攻撃法は基地局を装う能動的攻撃法である。おおまかに言えば、より弱いA5/2を使っているとGSM携帯に信じ込ませる。A5/2の解読は容易であり、秘密鍵にはA5/1と同じものを使っている。第二の攻撃法は、暗号文のみの時間メモリトレードオフ攻撃であり、多大な前処理を必要とする。

2006年、Elad Barkan、Eli Biham、Nathan Keller は2003年の論文の全文を公開した。そこにはA5/X暗号全般に対する攻撃法が含まれている^[9]。

2007年、ボーフム大学とキール大学は、FPGAを大量に使った暗号解読アクセラレータ COPACOBANA を開発する研究プロジェクトを開始した。これは時間メモリトレードオフ攻撃を加速し、A5/1およびA5/2アルゴリズムやDESの解読を支援する^[10]。また、総当り攻撃に使うこともでき、その場合は前処理が不要となる。

2008年、The Hackers Choice という団体がA5/1の実用的解読法を開発するプロジェクトを立ち上げた^[11]。攻撃には約3テラバイトの参照テーブルを構築する必要がある。このような巨大な参照テーブルを現実的な時間内に構築することは不可能だが、同団体は既に構築を開始しており、1年以内に完了するとしていた。2008年7月現在、完了したという発表はない。テーブルが完成し、並行して開発している検索機能が完成すれば、GSMの通信内容を盗聴し、そのデータから数分で暗号鍵を抽出し、会話の内容を知ることができるようになる。

脚注・出典

^ Quirke, Jeremy (2004年5月1日). “Security in the GSM system”. AusMobile. 2004年7月12日時点のオリジナルよりアーカイブ。2009年7月2日閲覧。
^ Ross Anderson (17 June 1994). "A5 (Was: HACKING DIGITAL PHONES)". Newsgroup: uk.telecom. Usenet: 2ts9a0$95r@lyra.csx.cam.ac.uk. 2009年7月2日閲覧。
^ Golic, Jovan Dj. (1997). “Cryptanalysis of Alleged A5 Stream Cipher”. EUROCRYPT 1997: 239–55. http://jya.com/a5-hack.htm.
^ Biryukov, Alex; Adi Shamir; David Wagner. “Real Time Cryptanalysis of A5/1 on a PC”. Fast Software Encryption—FSE 2000: 1–18.
^ Biham, Eli; Orr Dunkelman (2000). “Cryptanalysis of the A5/1 GSM Stream Cipher”. Indocrypt 2000: 43–51.
^ Ekdahl, Patrik; Thomas Johansson (2003). “Another attack on A5/1”. IEEE Transactions on Information Theory 49 (1): 284–89. doi:10.1109/TIT.2002.806129.
^ Barkan, Elad; Eli Biham (2005). “Conditional Estimators: An Effective Attack on A5/1”. Selected Areas in Cryptography 2005: 1–19.
^ Barkan, Elad; Eli Biham; Nathan Keller (2003). “Instant Ciphertext-Only Cryptanalysis of GSM Encrypted Communication”. Crypto 2003: 600–16. http://cryptome.org/gsm-crack-bbk.pdf.
^ Barkan, Elad; Eli Biham; Nathan Keller. “Instant Ciphertext-Only Cryptanalysis of GSM Encrypted Communication by Barkan and Biham of Technion (Full Version)”. 2009年7月2日閲覧。
^ Gueneysu, Tim; Tim Gueneysu; Timo Kasper; Martin Novotniy; Christof Paar, Member, IEEE;Andy Ruppe (2008). “Cryptanalysis with COPACOBANA”. Transactions on Computers Nov. 2008: 1498–1513.
^ The GSM Software Project The Hacker's Chice

参考文献

Rose, Greg (2003年9月10日). “A precis of the new attacks on GSM encryption”. QUALCOMM Australia. 2009年7月2日閲覧。
Maximov, Alexander; Thomas Johansson; Steve Babbage (2004). “An Improved Correlation Attack on A5/1”. Selected Areas in Cryptography 2004: 1–18.

外部リンク

Briceno, Marc; Ian Goldberg; David Wagner (1999年10月23日). “A pedagogical implementation of the GSM A5/1 and A5/2 "voice privacy" encryption algorithms”. 2009年7月2日閲覧。
Horesh, Hadar (2003年9月3日). “Technion team cracks GSM cellular phone encryption”. Haaretz 2009年7月2日閲覧。
Barkan, Elad; Eli Biham; Nathan Keller (2006年7月). “Instant Ciphertext-Only Cryptanalysis of GSM Encrypted Communication (Technical Report CS-2006-07)”. 2009年7月2日閲覧。
“Nathan Keller's Homepage”. 2009年7月2日閲覧。

[1] Quirke, Jeremy (2004年5月1日). “Security in the GSM system”. AusMobile. 2004年7月12日時点のオリジナルよりアーカイブ。2009年7月2日閲覧。

[2] Ross Anderson (17 June 1994). "A5 (Was: HACKING DIGITAL PHONES)". Newsgroup: uk.telecom. Usenet: 2ts9a0$95r@lyra.csx.cam.ac.uk. 2009年7月2日閲覧。

[3] Golic, Jovan Dj. (1997). “Cryptanalysis of Alleged A5 Stream Cipher”. EUROCRYPT 1997: 239–55. http://jya.com/a5-hack.htm.

[4] Biryukov, Alex; Adi Shamir; David Wagner. “Real Time Cryptanalysis of A5/1 on a PC”. Fast Software Encryption—FSE 2000: 1–18.

[5] Biham, Eli; Orr Dunkelman (2000). “Cryptanalysis of the A5/1 GSM Stream Cipher”. Indocrypt 2000: 43–51.

[6] Ekdahl, Patrik; Thomas Johansson (2003). “Another attack on A5/1”. IEEE Transactions on Information Theory 49 (1): 284–89. doi:10.1109/TIT.2002.806129.

[7] Barkan, Elad; Eli Biham (2005). “Conditional Estimators: An Effective Attack on A5/1”. Selected Areas in Cryptography 2005: 1–19.

[8] Barkan, Elad; Eli Biham; Nathan Keller (2003). “Instant Ciphertext-Only Cryptanalysis of GSM Encrypted Communication”. Crypto 2003: 600–16. http://cryptome.org/gsm-crack-bbk.pdf.

[9] Barkan, Elad; Eli Biham; Nathan Keller. “Instant Ciphertext-Only Cryptanalysis of GSM Encrypted Communication by Barkan and Biham of Technion (Full Version)”. 2009年7月2日閲覧。

[10] Gueneysu, Tim; Tim Gueneysu; Timo Kasper; Martin Novotniy; Christof Paar, Member, IEEE;Andy Ruppe (2008). “Cryptanalysis with COPACOBANA”. Transactions on Computers Nov. 2008: 1498–1513.

[11] The GSM Software Project The Hacker's Chice

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]