A5/1

A5/1は、 GSM携帯電話規格で無線通信のプライバシーを保護するために使用されるストリーム暗号です。これは、A5 セキュリティ プロトコルのいくつかの実装の 1 つです。当初は秘密にされていましたが、漏洩やリバース エンジニアリングによって一般に知られるようになりました。この暗号には、いくつかの重大な弱点が特定されています。

A5/1 はヨーロッパとアメリカで使用されています。A5 /2 は、特定の輸出地域向けに意図的にアルゴリズムを弱めたものでした。^[1] A5/1 は 1987 年に開発されましたが、当時は GSM がヨーロッパ以外での使用がまだ検討されていませんでした。A5 /2 は1989 年に開発されました。どちらも当初は秘密にされていましたが、1994 年に一般的な設計が漏洩し、1999 年に Marc Briceno によって GSM 電話からアルゴリズムが完全にリバース エンジニアリングされました。2000 年には、約 1 億 3000 万人の GSM 顧客が音声通信の機密性を保護するために A5/1 に依存していました。^[要出典]

セキュリティ研究者ロス・アンダーソンは1994年に「1980年代半ば、NATOの 信号諜報機関の間で、GSMの暗号化が強力であるべきか否かをめぐって激しい論争があった。ドイツはワルシャワ条約機構と長い国境を接しているため、強力であるべきだと主張したが、他の国々はそうは考えず、現在使用されているアルゴリズムはフランス設計である」と報告した。^[2]

GSM 送信は、バーストのシーケンスとして構成されます。一般的なチャネルでは、一方向で、1 つのバーストが 4.615 ミリ秒ごとに送信され、情報として使用できる 114 ビットが含まれます。A5/1 は、各バーストに対して 114 ビットのキーストリームシーケンスを生成するために使用され、変調前に 114 ビットとXOR 演算されます。A5/1 は、64 ビットのキーと公開されている 22 ビットのフレーム番号を使用して初期化されます。キー生成に Comp128v1 を使用する古いフィールド GSM 実装では、キー ビットの 10 がゼロに固定されていたため、有効なキー長は 54 ビットでした。この弱点は、適切な 64 ビット キーを生成する Comp128v3 の導入によって修正されました。GPRS/EDGE モードで動作している場合、より帯域幅の広い無線変調によって 348 ビットのより大きなフレームが可能になり、A5/3 が機密性を維持するためにストリーム暗号モードで使用されます。

A5/1 は、不規則なクロックを備えた 3 つの線形フィードバック シフト レジスタ(LFSR)の組み合わせに基づいています。3 つのシフト レジスタは次のように指定されます。

これらの次数はランダムに選択されたわけではありません。3 つのレジスタの次数は互いに素であるため、このジェネレータの周期は 3 つのレジスタの周期の積になります。したがって、A5/1 (繰り返し前) の周期は 2^64 ビット (2 の 64 乗) です。

ビットは最下位ビット(LSB) を 0 としてインデックス付けされます。

レジスタは、多数決ルールを使用して、ストップ/ゴー方式でクロックされます。各レジスタには、関連するクロック ビットがあります。各サイクルで、3 つのレジスタすべてのクロック ビットが検査され、多数決ビットが決定されます。クロック ビットが多数決ビットと一致する場合、レジスタがクロックされます。したがって、各ステップで少なくとも 2 つまたは 3 つのレジスタがクロックされ、各レジスタは 3/4 の確率でステップします。

最初に、レジスタはゼロに設定されます。その後、64サイクルにわたって、64ビットの秘密鍵Kが次の方式に従って混合されます。サイクルでは、i番目の鍵ビットが各レジスタの最下位ビットにXORを使用して追加されます。 ${\displaystyle 0\leq {i}<64}$

${\displaystyle R[0]=R[0]\oplus K[i].}$

次に各レジスタがクロックされます。

同様に、フレーム番号の 22 ビットは 22 サイクルで追加されます。次に、システム全体が通常の多数決クロッキング メカニズムを使用して 100 サイクルでクロックされ、出力は破棄されます。これが完了すると、暗号は 2 つの 114 ビットの出力キーストリーム シーケンス (最初の 114 はダウンリンク用、最後の 114 はアップリンク用) を生成する準備が整います。

A5/1に対する攻撃は数多く公開されており、公開された内部文書によると、アメリカ国家安全保障局はA5/1メッセージを日常的に解読することができる。^[3]

一部の攻撃では、コストのかかる前処理段階が必要で、その後は数分または数秒で暗号を破ることができます。当初、脆弱性は既知平文の仮定を使用した受動的な攻撃でした。2003 年には、暗号文のみのシナリオや能動的な攻撃者によって悪用される可能性のある、より深刻な脆弱性が特定されました。2006 年に Elad Barkan、Eli Biham、Nathan Keller は、A5/1、A5/3、さらには GPRS に対する攻撃を実演し、攻撃者が GSM 携帯電話の会話を盗聴し、リアルタイムまたは後でいつでも解読できるようにしました。

ヤン・アリルド・オーデスタッド教授によると、1982年に始まった標準化プロセスでは、A5/1の鍵長は当初128ビットと提案されていた。当時、128ビットは少なくとも15年間は安全であると予測されていた。現在では、128ビットは量子コンピューティングの出現まで実際に安全であると考えられている。オーデスタッド、ピーター・ファン・デル・アーレンド、トーマス・ハウグは、英国は弱い暗号化を主張したと述べ、ハウグは英国代表から、これは英国の諜報機関がより簡単に盗聴できるようにするためだと言われたと述べている。英国は48ビットの鍵長を提案したが、西ドイツは東ドイツのスパイ行為から保護するためにより強力な暗号化を望んだため、妥協案として鍵長は54ビットになった。^[4]

A5/1に対する最初の攻撃は、 1994年にロス・アンダーソンによって提案されました。アンダーソンの基本的なアイデアは、レジスタR1とR2の完全な内容とレジスタR3の約半分を推測することでした。この方法で、3つのレジスタすべてのクロッキングが決定され、R3の後半が計算されます。^[2]

1997 年、Golic は、時間計算量が 2 ^40.16である線形方程式のセットを解くことに基づく攻撃を発表しました(単位は、必要な線形方程式のシステムの解の数です)。

2000年に、アレックス・ビリュコフ、アディ・シャミール、デビッド・ワグナーは、ジョヴァン・ゴリックによる以前の研究^[6 ]に基づいて、時間とメモリのトレードオフ攻撃^[5]を使用してA5/1をリアルタイムで解読できることを示しました。1つのトレードオフでは、攻撃者は2分間の既知の平文から1秒で、または2秒間の既知の平文から数分でキーを再構築できますが、最初に約300GBのデータを計算するために²⁴⁸ステップを必要とする高価な前処理段階を完了する必要があります。前処理、データ要件、攻撃時間、メモリの複雑さの間では、いくつかのトレードオフが可能です。

同年、イーライ・ビハムとオール・ダンケルマンも、 ^220.8ビットの既知の平文を与えられた場合、 ^239.91 A5/1クロッキングの総作業複雑度を持つA5/1への攻撃を発表しました。この攻撃には、 ²³⁸の事前計算段階の後に32 GBのデータストレージが必要です。^[7]

エクダールとヨハンソンは、2～5分の会話の平文を使って数分でA5/1を破る初期化手順への攻撃法を発表しました。^[8]この攻撃法は前処理段階を必要としません。2004年にマクシモフらは、この結果を「1分未満の計算と数秒の既知の会話」を必要とする攻撃法に改良しました。この攻撃法は、2005年にエラッド・バルカンとイーライ・ビハムによってさらに改良されました。^[9]

2003年、BarkanらはGSM暗号化に対するいくつかの攻撃法を発表しました。^[10]最初の攻撃法は能動的な攻撃法です。GSM電話機は、はるかに弱いA5/2暗号を短時間使用するように仕向けられます。A5/2は簡単に破ることができ、電話機はより強力なA5/1アルゴリズムと同じ鍵を使用します。A5/1に対する2番目の攻撃法は、大量の事前計算を必要とする 暗号文のみの時間とメモリのトレードオフ攻撃法です。

2006年、エラッド・バーカン、イーライ・ビハム、ネイサン・ケラーは、2003年の論文の完全版を発表し、A5/X暗号に対する攻撃を公表した。著者らは次のように主張している。^[11]

GSM 暗号化通信の非常に実用的な暗号文のみの暗号解読と、GSM プロトコルに対するさまざまなアクティブ攻撃を紹介します。これらの攻撃は、「解読不可能な」暗号を使用する GSM ネットワークにも侵入できます。まず、数十ミリ秒の暗号化されたオフザエア携帯電話通話を必要とし、パーソナル コンピュータで 1 秒未満で正しいキーを見つける、A5/2 に対する暗号文のみの攻撃について説明します。この攻撃を、(より複雑な) A5/1 に対する暗号文のみの攻撃に拡張します。次に、A5/1、A5/3、または GPRS を使用するネットワークのプロトコルに対する新しい (アクティブ) 攻撃について説明します。これらの攻撃は GSM プロトコルの欠陥を悪用し、携帯電話が A5/2 などの弱い暗号をサポートしているときはいつでも機能します。これらの攻撃はプロトコルに対するものであるため、携帯電話が弱い暗号をサポートしているときはいつでも適用可能であり、たとえば、A5/1 の暗号解読を使用して A5/3 ネットワークを攻撃する場合にも適用可能であることを強調します。長い既知平文期間などの非現実的な情報を必要とする GSM に対する以前の攻撃とは異なり、私たちの攻撃は非常に実用的で、会話の内容に関する知識を必要としません。さらに、受信エラーに耐えられるように攻撃を強化する方法についても説明します。その結果、私たちの攻撃により、攻撃者は会話を盗聴し、リアルタイムまたは後でいつでも解読できるようになります。

2007年、ボッフム大学とキール大学は、FPGAベースの超並列暗号化アクセラレータCOPACOBANAを作成するための研究プロジェクトを開始しました。COPACOBANAは、GSM音声暗号化やデータ暗号化規格^（DES）で使用される一般的なA5/1およびA5/2アルゴリズムを攻撃するために使用できる高速な時間とメモリのトレードオフ技術を使用した最初の市販ソリューション[12]でした。また、大規模な事前計算されたルックアップテーブルを必要とせずに、GSMに対する ブルートフォース攻撃を可能にします。

2008年、The Hackers Choiceというグループは、A5/1に対する実用的な攻撃を開発するプロジェクトを立ち上げました。この攻撃には、約3テラバイトの大規模なルックアップテーブルの構築が必要です。姉妹プロジェクトの一環として開発されたスキャン機能と組み合わせることで、グループは、A5/1で暗号化されたGSM通話やSMSを記録し、約3〜5分以内に暗号化キーを導出して通話を聞き、SMSを平文で読むことができると予想しました。しかし、テーブルは公開されませんでした。^[13]

同様の取り組みである A5/1 クラッキング プロジェクトは、2009 年の Black Hat セキュリティ カンファレンスで暗号学者のKarsten Nohl 氏と Sascha Krißler 氏によって発表されました。このプロジェクトでは、ピアツーピア分散コンピューティングアーキテクチャを介してNvidia GPGPUを使用したルックアップ テーブルが作成されました。2009 年 9 月中旬に開始されたこのプロジェクトでは、12 台の Nvidia GeForce GTX 260 に相当する処理が行われました。著者らによると、このアプローチは、キー サイズが最大 64 ビットのあらゆる暗号に使用できます。^[14]

2009年12月、A5/1クラッキングプロジェクトのA5/1攻撃表がChris PagetとKarsten Nohlによって発表された。表はレインボーテーブルや識別点連鎖などの圧縮技術を組み合わせて使用​​している。これらの表は1.7TBの完成した表の一部に過ぎず、40の分散CUDAノードを使用して3か月かけて計算され、BitTorrentで公開された。^{[13] [14] [15] [16]}最近では、プロジェクトはより高速なATI Evergreenコードへの切り替えと表の形式の変更を発表し、Frank A. StevensonはATIが生成した表を使用してA5/1を破ったと発表した。^[17]

2013年にエドワード・スノーデンによって漏洩された文書には、NSAは「暗号化されたA5/1を処理できる」と記載されている。^[18]

3 つの LFSR の次数は互いに素であるため、このジェネレータの周期は 3 つの LFSR の周期の積となり、2^64 ビット (2 の 64 乗) を表します。

A5/1を64ビットの初期化シード（キーサイズ）を持つ疑似乱数ジェネレータとして使用することを考える人もいるかもしれないが、これは信頼性が低い。わずか8MB（3つのレジスタのうち最大のものの周期を表す）でランダム性が失われる。^[19]

• A5/2
• KASUMI（別名A5/3）
• セルラーメッセージ暗号化アルゴリズム

• Rose, Greg (2003 年 9 月 10 日)。「GSM 暗号化に対する新たな攻撃の概要」(PDF)。QUALCOMM Australia。2011年 9 月 27 日時点のオリジナル(PDF)からアーカイブ。2004年10 月 17日閲覧。
• Maximov, Alexander、Thomas Johansson、Steve Babbage (2004)。「A5/1 に対する改良された相関攻撃」。Selected Areas in Cryptography 2004 : 1–18。

• Briceno, Marc、Ian Goldberg、David Wagner (1999 年 10 月 23 日)。「GSM A5/1 および A5/2「音声プライバシー」暗号化アルゴリズムの教育的実装」。2018 年 10 月 8 日時点のオリジナルよりアーカイブ。2017年1 月 23 日閲覧。
• 「GSM の重大な欠陥により、ハッカーが音声通話を盗聴可能」。2009 年 8 月 25 日。2009 年 10 月 14 日時点のオリジナルよりアーカイブ。
• Horesh, Hadar (2003年9月3日). 「TechnionチームがGSM携帯電話の暗号化を解読」(PDF) . Haaretz . 2016年3月3日時点のオリジナル(PDF)からアーカイブ。 2019年9月15日閲覧。
• Barkan, Elad、Eli Biham、Nathan Keller (2006 年 7 月)。「GSM 暗号化通信の即時暗号文のみの暗号解析 (技術レポート CS-2006-07)」。2019 年 12 月 27 日時点のオリジナルよりアーカイブ。2019 年9 月 15 日閲覧。
• 「ネイサン・ケラーのホームページ」。2008年6月4日時点のオリジナルよりアーカイブ。
• 「A5/1 ストリーム暗号を示すアニメーション SVG」。2012 年 3 月 26 日時点のオリジナルよりアーカイブ。