A5/1
1997年、Golic は時間計算量 2 の連立1次方程式の解法に基づく攻撃方法を発表した(時間は必要な連立1次方程式の解の数に比例する)。
2000年、Alex Biryukov、Adi Shamir、David Wagner は、上述の Jovan Golic の成果に基づき、時間メモリトレードオフ攻撃を使うことでリアルタイムでA5/1を解読可能であることを示した。例えば2分間ぶんの平文があれば1秒で鍵を再構築でき、2秒間ぶんの平文なら数分で鍵を再構築できるが、その前に300GBのデータについて2ステップを要する多大な前処理を完了しておく必要がある。前処理量、データ量、攻撃時間、メモリ使用量はトレードオフの関係にある。
同年、Eli Biham と Orr Dunkelman もA5/1への攻撃方法を発表した。これは32GBのデータを使用した 2 ステップの前処理を必要とする。
EkdahlとJohannsonは、2分間から5分間の平文を使い、数分でA5/1を破る攻撃方法を発表した。この攻撃法は前処理が不要である。2004年、Maximovらはその成果を改良し、数秒の平文から1分以内に暗号を解読する攻撃法を得た。2005年、その攻撃法をさらに Elad Barkan と Eli Biham が改良した。
A5/1への攻撃方法のいくつかが公表されている。一部は前処理に秒単位から分単位の時間がかかる。当初、既知の平文から推定する攻撃しか知られていなかった。2003年、暗号文のみから解読できる重大な脆弱性が判明した。2006年、Elad Barkan、Eli Biham、Nathan Keller の3人は、A5/1、A5/3、GPRSに対する攻撃方法を公開し、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. http://cryptome.info/0001/a51-bsw/a51-bsw.htm.
↑ Biham, Eli; Orr Dunkelman (2000).