A5/1のソースを表示

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

== 歴史と使用 ==
A5/1 は[[ヨーロッパ]]と[[アメリカ合衆国]]で使われている。これを若干弱めた派生アルゴリズムである[[A5/2]]が他の地域で使われている<ref>{{cite web | archiveurl = https://web.archive.org/web/20040712061808/www.ausmobile.com/downloads/technical/Security+in+the+GSM+system+01052004.pdf | first = Jeremy | last = Quirke | archivedate = 2004-07-12 | title = Security in the GSM system | publisher = AusMobile | date = 2004-05-01 | url = http://www.ausmobile.com/downloads/technical/Security+in+the+GSM+system+01052004.pdf|accessdate=2009-07-02}}</ref>。A5/1は1987年に開発されたもので、当時GSMはヨーロッパ以外で使用することは考慮されていない。A5/2は1989年に開発された。当初どちらもその詳細は秘密にされた。しかし設計の概要は1994年にリークされ、アルゴリズム全体は1999年、Marc Briceno がGSM携帯電話を使ってリバースエンジニアリングで明らかにした。2000年当時、1億3000万のGSM利用者が音声通信の機密保護手段としてA5/1に依存していた。

セキュリティ研究家 Ross Anderson は1994年、「1980年代中ごろ、GSMの暗号強度をどうすべきかについて[[北大西洋条約機構|NATO]]各国の[[シギント|信号諜報機関]]の間で激しい議論があった。ドイツは[[ワルシャワ条約機構]]と地理的に接していることから、強い暗号を主張した。しかし他国は強い暗号が必要とは考えなかった。現在実際に使われているアルゴリズムはフランスの設計によるものだ」と公表した<ref>{{cite newsgroup | title = A5 (Was: HACKING DIGITAL PHONES) | author = Ross Anderson | date = 1994-06-17 | newsgroup = uk.telecom | message-id = 2ts9a0$95r@lyra.csx.cam.ac.uk | url = https://groups.google.com/g/uk.telecom/c/-/m/Mroy719hdroJ|accessdate=2009-07-02}}</ref>。

== 技術的解説 ==
[[ファイル:A5-1_GSM_cipher.svg|thumbnail|350px|right|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つのシフトレジスタの詳細は次の通り:
{| class="wikitable"
!LFSR番号
!ビット数
!帰還多項式
!クロック用ビット
!入力ビット
|-
|1 || 19 || <math>x^{18} + x^{17} + x^{16} + x^{13} + 1</math> || 8 || 13, 16, 17, 18 
|-
|2 || 22 || <math>x^{21} + x^{20} + 1</math> || 10 || 20, 21
|-
|3 || 23 || <math>x^{22} + x^{21} + x^{20} + x^{7} + 1</math> || 10 || 7, 20, 21, 22
|}
ビットの番号は[[最下位ビット]] (LSB) を0としている。

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

初期状態では、各レジスタの内容は0に設定されている。そしてここに64サイクルかけて64ビットの秘密鍵を次のように入力していく。<math>0\leq{i}<64</math> のサイクル番号について、''i''番めの鍵のビットを各レジスタの最下位ビットにXORで入力する。
:<math>R[0] = R[0] \oplus K[i].</math>
そして、各レジスタにクロックを供給する（最下位ビットの内容は1つ上のビットに移動する）。

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

== セキュリティ ==
[[ファイル:CipheringNotProvided.jpg|right|thumb|200 px|暗号化されていないという警告が携帯電話に表示されている様子]]
A5/1への攻撃方法のいくつかが公表されている。一部は前処理に秒単位から分単位の時間がかかる。当初、既知の平文から推定する攻撃しか知られていなかった。2003年、暗号文のみから解読できる重大な脆弱性が判明した。2006年、Elad Barkan、Eli Biham、Nathan Keller の3人は、A5/1、[[KASUMI|A5/3]]、GPRSに対する攻撃方法を公開し、GSM携帯電話の会話を実時間で解読したり、記録しておいて後で解読する方法があることを示した。

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

2000年、Alex Biryukov、[[アディ・シャミア|Adi Shamir]]、David Wagner は、上述の Jovan Golic の成果に基づき<ref>{{cite journal | first = Jovan Dj. | last =  Golic | title =  Cryptanalysis of Alleged A5 Stream Cipher | work = EUROCRYPT 1997 | year = 1997 | pages = 239–55 | url = http://jya.com/a5-hack.htm}}</ref>、[[時間と空間のトレードオフ|時間メモリトレードオフ]]攻撃を使うことでリアルタイムでA5/1を[[暗号解読|解読可能]]であることを示した<ref> {{cite journal | authorlink = | first = Alex | last =  Biryukov | coauthors =   [[アディ・シャミア|Adi Shamir]]; David Wagner | title =  Real Time Cryptanalysis of A5/1 on a PC | journal =  Fast Software Encryption—FSE 2000 | pages = 1–18 | url = http://cryptome.info/0001/a51-bsw/a51-bsw.htm}}</ref>。例えば2分間ぶんの平文があれば1秒で鍵を再構築でき、2秒間ぶんの平文なら数分で鍵を再構築できるが、その前に300GBのデータについて2<sup>48</sup>ステップを要する多大な前処理を完了しておく必要がある。前処理量、データ量、攻撃時間、メモリ使用量はトレードオフの関係にある。

同年、Eli Biham と Orr Dunkelman もA5/1への攻撃方法を発表した。これは32GBのデータを使用した 2<sup>38</sup> ステップの前処理を必要とする<ref>{{cite journal  | first = Eli | last =  Biham | coauthors =  Orr Dunkelman | title =  Cryptanalysis of the A5/1 GSM Stream Cipher | year = 2000 | journal = Indocrypt 2000 | pages =43–51}}</ref>。

EkdahlとJohannsonは、2分間から5分間の平文を使い、数分でA5/1を破る攻撃方法を発表した<ref>{{cite journal | first = Patrik | last =  Ekdahl | coauthors = Thomas Johansson | title  = Another attack on A5/1 | journal = IEEE Transactions on Information Theory | volume = 49 | issue = 1 | pages = 284–89 | year = 2003 | url = http://ieeexplore.ieee.org/Xplore/login.jsp?url=http%3A%2F%2Fieeexplore.ieee.org%2Fiel5%2F18%2F25988%2F01159783.pdf%3Farnumber%3D1159783&authDecision=-203 | doi = 10.1109/TIT.2002.806129}}</ref>。この攻撃法は前処理が不要である。2004年、Maximovらはその成果を改良し、数秒の平文から1分以内に暗号を解読する攻撃法を得た。2005年、その攻撃法をさらに Elad Barkan と Eli Biham が改良した<ref>{{cite journal | first = Elad | last =  Barkan | coauthors = Eli Biham | title =  Conditional Estimators: An Effective Attack on A5/1 | journal =  Selected Areas in Cryptography 2005 | year = 2005 | pages = 1–19}}</ref>。

=== GSMで使われているA5/1への攻撃 ===
2003年、BarkanらはGSMの暗号へのいくつかの攻撃法を発表した<ref>{{cite journal | first = Elad | last = Barkan | coauthors = Eli Biham;  Nathan Keller | title =  Instant Ciphertext-Only Cryptanalysis of GSM Encrypted Communication | year = 2003 | journal =  Crypto 2003 | pages = 600–16  | url = http://cryptome.org/gsm-crack-bbk.pdf}}</ref>。第一の攻撃法は基地局を装う能動的攻撃法である。おおまかに言えば、より弱い[[A5/2]]を使っているとGSM携帯に信じ込ませる。A5/2の解読は容易であり、秘密鍵にはA5/1と同じものを使っている。第二の攻撃法は、暗号文のみの時間メモリトレードオフ攻撃であり、多大な前処理を必要とする。

2006年、Elad Barkan、Eli Biham、Nathan Keller は2003年の論文の全文を公開した。そこにはA5/X暗号全般に対する攻撃法が含まれている<ref>{{cite web | url = http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-get.cgi/2006/CS/CS-2006-07.pdf | title = Instant Ciphertext-Only Cryptanalysis of GSM Encrypted Communication by Barkan and Biham of Technion (Full Version) | first = Elad | last = Barkan | coauthors = Eli Biham; Nathan Keller|accessdate=2009-07-02}}</ref>。

2007年、ボーフム大学とキール大学は、[[FPGA]]を大量に使った暗号解読アクセラレータ [http://www.copacobana.org/ COPACOBANA] を開発する研究プロジェクトを開始した。これは時間メモリトレードオフ攻撃を加速し、A5/1およびA5/2アルゴリズムや[[Data Encryption Standard|DES]]の解読を支援する<ref>{{cite journal | first = Tim | last =  Gueneysu | coauthors = Tim Gueneysu; Timo Kasper; Martin Novotniy; Christof Paar, Member, IEEE;Andy Ruppe | title = Cryptanalysis with COPACOBANA | url = http://www.copacobana.org/paper/TC_COPACOBANA.pdf | journal =  Transactions on Computers Nov. 2008 | year = 2008 | Volume 57 | pages = 1498–1513}}</ref>。また、[[総当り攻撃]]に使うこともでき、その場合は前処理が不要となる。

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

== 関連項目 ==
* [[KASUMI]] - A5/3 の別名

== 脚注・出典 ==
{{Reflist}}

== 参考文献 ==
* {{cite web | first = Greg | last = Rose | title = A precis of the new attacks on GSM encryption | publisher = [[クアルコム|QUALCOMM]] Australia | date = 2003-09-10 | url = http://www.qualcomm.com.au/PublicationsDocs/GSM_Attacks.pdf|accessdate=2009-07-02}}
* {{cite journal | first = Alexander | last =  Maximov | coauthors = Thomas Johansson; Steve Babbage | title = An Improved Correlation Attack on A5/1 | journal =  Selected Areas in Cryptography 2004 | year = 2004 | pages = 1–18}}

== 外部リンク ==
* {{cite web | first = Marc | last = Briceno | coauthors = Ian Goldberg; David Wagner | date = 1999-10-23 | url = http://edipermadi.files.wordpress.com/2008/03/pedagogical_implementation_of_a5_cipher.pdf | title =  A pedagogical implementation of the GSM A5/1 and A5/2 "voice privacy" encryption algorithms|accessdate=2009-07-02}}
* {{cite news | url = http://www.cs.technion.ac.il/%7Ebarkan/GSM-Media/HaaretzInternetEnglish.pdf | title = Technion team cracks GSM cellular phone encryption | work = [[ハアレツ|Haaretz]] | first = Hadar | last = Horesh | date = 2003-09-03 |accessdate=2009-07-02}}
* {{cite web | url = http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-info.cgi?2006/CS/CS-2006-07 | title = Instant Ciphertext-Only Cryptanalysis of GSM Encrypted Communication (Technical Report CS-2006-07) | first = Elad | last =  Barkan | coauthors = Eli Biham; Nathan Keller | month =  July | year = 2006|accessdate=2009-07-02}}
* {{cite web | url = http://www.ma.huji.ac.il/~nkeller | title = Nathan Keller's Homepage|accessdate=2009-07-02}}

{{cryptography navbox|stream}}
[[Category:ストリーム暗号]]
[[Category:GSM]]