A5/1はストリーム暗号の一種で、GSM携帯電話規格における通信プライバシー保護手段として採用されている。当初、秘密にされていたが、リークやリバースエンジニアリングによって徐々に明らかとなってきた。この暗号について、いくつかの深刻な弱点が指摘されている。
歴史と使用が他の地域で使われている[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番号ビット数帰還多項式クロック用ビット入力ビット
119 x 18 + x 17 + x 16 + x 13 + 1 {\displaystyle x^{18}+x^{17}+x^{16}+x^{13}+1} 813, 16, 17, 18
222 x 21 + x 20 + 1 {\displaystyle x^{21}+x^{20}+1} 1020, 21
323 x 22 + x 21 + x 20 + x 7 + 1 {\displaystyle x^{22}+x^{21}+x^{20}+x^{7}+1} 107, 20, 21, 22
ビットの番号は最下位ビット (LSB) を0としている。
レジスタへのクロック供給は、クロックビットの多数決で決まる。それぞれのレジスタにクロックビットがひとつずつある。サイクル毎に3つのレジスタのクロックビットを調べ、多数決で0か1かを決める。そして、そのレジスタのクロックビットと多数決の結果が等しいレジスタだけにクロックが供給される。したがって、サイクル毎に2つか3つのレジスタにクロックが供給される。各レジスタがステップを進める確率は3/4である。
初期状態では、各レジスタの内容は0に設定されている。そしてここに64サイクルかけて64ビットの秘密鍵を次のように入力していく。 0 ≤ i < 64 {\displaystyle 0\leq {i}<64} のサイクル番号について、i番めの鍵のビットを各レジスタの最下位ビットにXORで入力する。 R [ 0 ] = R [ 0 ] ⊕ K [ i ] . {\displaystyle 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 は時間計算量 240.16 の連立1次方程式の解法に基づく攻撃方法を発表した（時間は必要な連立1次方程式の解の数に比例する）。 2000年、Alex Biryukov、Adi Shamir、David Wagner は、上述の Jovan Golic の成果に基づき[3]、時間メモリトレードオフ攻撃を使うことでリアルタイムでA5/1を解読可能であることを示した[4]。
既知平文攻撃
