A5/1

A5/1是用于在GSM标准中提供行动通信保密性的流密码，它是指定用于GSM的七个加密算法之一^[1]。A5/1的设计最初没有对外公开，但由于泄漏和逆向工程而广为人知。已经确定了A5/1中存在许多严重缺陷。

A5/1

概述
首次发布	1994年对外泄漏总体设计 1999年通过反向工程破解并公开 （1987年开发）
系列	A5/2、A5/3（KASUMI）
密码细节
密钥长度	64或54位
状态长度	114位
最佳公开破解
通过对初始化密钥程序的攻击，可以利用数秒钟的已知明文在少于一分钟的时间内攻破 针对GSM协议的攻击可在个人电脑的处理能力下，在数秒钟内分析出密钥。

历史和用法

A5/1在欧洲和美国使用。A5/2为A5/1削弱过的版本，用于出口到某些地区^[2]。A5/1是在1987年开发的，当时尚未考虑在欧洲以外使用GSM，而A5/2是在1989年开发的。尽管设计最初都是保密的，但总体设计在1994年被泄露。该算法完全由Marc Briceno于1999年从GSM电话利用反向工程取得。在2000年时，大约1.3亿个GSM客户端依赖A5/1来保护其语音通信的机密性；到2014年，这一数字增加为72亿。^[3]

安全研究人员Ross Anderson在1994年报导说：“在1980年代中期，北约讯号情报机构之间就GSM的加密是否应该拥有较高的安全性，有着激烈的争论。德国方面认为应该如此，因为的德国边界有很长一部分与华沙公约组织接壤，但其他北约成员国没有这个状况，目前采用的算法是法国设计。”^[4]

A5/2

A5/2是用于出口，相对于A5/1比较弱。它是指定用于用于GSM的七种A5加密算法之一。^[5]

该密码基于具有不规则时钟的四个线性反馈移位寄存器和非线性组合器的组合。

1999年，Ian Goldberg和David A. Wagner在发布A5/2的同一个月中对其进行了加密分析，结果表明该A5/2非常脆弱，以至于低端设备都可能会实时地破解它。

自2006年7月1日起，GSMA（GSM协会）强制要求GSM移动电话不再支持A5/2密码，这是因为它的弱点以及3GPP协会认为A5/1是强制性的。2007年7月，3GPP批准了一项更改请求，以禁止在任何新手机中使用A5/2。如果网络不支持电话所实现的A5/1或任何其他A5算法时，则可以使用未加密的连接。^[5]

说明

A5/1流密码使用三个LFSR。如果某个寄存器的钟控位（橙色）和另一个寄存器的钟控位相同或著三个寄存器的钟控位都相同，则对该寄存器作移位操作

GSM传输使用突发脉冲序列（Bursts）。一个典型的信道在一个方向上，每4.615毫秒发送一个突发脉冲（帧），每一帧包含114个可用于信息的位元。A5/1用于为每个帧产生密钥流的114位序列，该序列在调制之前与114位进行异或 。使用64位密钥和公开的22位帧号初始化A5/1。 早期的GSM使用Comp128v1生成密钥，将10个密钥位固定为零，因此有效密钥长度为54位。通过引入Comp128v3（可产生正确的64位密钥）可以纠正此缺陷。 当以GPRS/EDGE模式工作时，更高带宽的无线电调制允许更大的348位帧，然后在流密码模式下使用A5/3（KASUMI）来保持机密性。

A5/1基于具有不规则钟控的三个线性反馈移位寄存器 （LFSR）的组合。 三个移位寄存器的指定如下：

寄存器编号	寄存器位数	反馈方程	钟控位	抽头
1	19	${\displaystyle x^{19}+x^{18}+x^{17}+x^{14}+1}$	8	13, 16, 17, 18
2	22	${\displaystyle x^{22}+x^{21}+1}$	10	20, 21
3	23	${\displaystyle x^{23}+x^{22}+x^{21}+x^{8}+1}$	10	7, 20, 21, 22

最低有效位的索引为0。

钟控会使用择多原则来决定是否对寄存器作移位操作。每个寄存器都有一个相关的钟控位。在每个周期，检查三个寄存器的钟控位，并确定多数位（0或者1）。如果钟控位与多数位一致，则对寄存器作移位操作。因此，在每个步骤中至少要对两个或三个寄存器进行移位，并且每个寄存器移位的概率是3/4。

比如，三个寄存器的钟控位为分别为0、0、1。此时0为多数位，钟控便会移位钟控位为0的第一和二个寄存器，而第三个寄存器维持不变。

最初，寄存器每一位设置为零。然后在64个周期中，根据以下方案混合64位密钥：在周期${\displaystyle 0\leq {i}<64}$，第${\displaystyle {i}}$位使用异或将密钥位添加到每个寄存器的最低有效位—

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

然后将寄存器移位。

接着在用同样的方案混合22位的帧号。然后，整个系统使用前述的钟控机制循环100个周期，并丢弃输出。完成此操作后，密码已准备好生成输出密钥流的两个114位序列，下行（从基地台接收到的讯号）使用前114位，上行（回传给基地台的讯号）使用后114位。

安全

手机屏幕上的消息，带有关于未加密的警告

A5/1已经有许多公开破解，根据已披露的内部文档，美国国家安全局（NSA）能够对A5/1消息进行例行解密。^[6]

某些攻击需要昂贵的预处理阶段，在此阶段之后几分钟或几秒钟即可破解密码。早期发现的漏洞只能在已知明文的前提下利用，并且是被动攻击。2003年，发现了更严重的漏洞，可以在唯密文的前提下利用，或采用主动攻击。在2006年，Elad Barkan、Eli Biham和Nathan Keller展示了针对A5/1， A5/3甚至是GPRS的攻击，攻击者可以窃听GSM手机讯号，实时解密或保存讯息，以在未来任何时间解密。

根据Jan Arild Audestad教授的说法，在1982年开始的标准化过程中，最初提出A5/1的密钥长度为128位。当时，预计128位的安全性足以满足为来十五年的需求。现在的研究人员相信，在量子计算出现之前，128位实际上仍然是安全的。Audestad、Peter van der Arend和Thomas Haug表示英国坚持使用较弱的加密，Haug表示英国代表告诉他这是安全的。为了让英国的特勤人员更容易窃听，英国建议使用48位的密钥长度，而西德则希望使用安全性更高的加密的来防止东德间谍活动。最后折衷方案是54位的密钥长度^[7]。

已知明文攻击

1994年， Ross Anderson提出了对A5/1的首次攻击。安德森的基本思想是猜测寄存器R1和R2的完整内容以及寄存器R3的一半。 这样，就可以确定所有三个寄存器的时钟，并且可以计算R3的后一半。^[4]

在1997年，Jovan Golic提出了一种基于求解线性方程组的攻击，该方法具有${\displaystyle 2^{40.16}}$的时间复杂度下破解（单位表示为所需线性方程组解的个数）。

在2000年， Alex Biryukov、Adi Shamir和David Wagner表明，可以基于时间—记忆体权衡攻击对A5/1进行实时破密^[8]，这是基于Jovan Golic的早期工作^[9]。权衡取舍允许攻击者利用长度为两分钟的已知明文，在一秒钟内分析出密钥，或著利用一秒钟的已知明文在数分钟内分析出密钥，但是攻击者必须首先完成一个昂贵的预处理程序，该阶段需要${\displaystyle 2^{48}}$步来计算300GB的数据。在预处理，数据需求，攻击时间和内存复杂度之间可能要进行一些折衷。

同年， Eli Biham和Orr Dunkelman公开了另一个对A5/1的攻击，通过A5/1钟控给出${\displaystyle 2^{20.8}}$位的已知明文，其总工作复杂度为${\displaystyle 2^{39.91}}$。在${\displaystyle 2^{38}}$的预计算阶段之后，此攻击需要共需要32GB的内存。^[10]

Ekdahl和Johansson发表了有关初始化过程的攻击，该攻击可通过两到五分钟的已知明文在几分钟内破解A5/1。此攻击不需要预处理阶段^[11]。2004年，包含Maximov的几名研究人员将该结果改进为需要“少于一分钟的计算时间和几秒钟的已知明文”的攻击。 Elad Barkan和Eli Biham在2005年进一步改善了这一攻击。^[12]

针对GSM系统的攻击

在2003年，Barkan 等人。发表了一些有关GSM加密的攻击，是首次发现主动攻击^[13]。可以说服GSM手机短暂使用弱得多的A5/2密码。在使用同样的密钥下，相比于比较强健的A5/1，A5/2更容易被攻破。在针对A5/1的第二次攻击中概述，唯密文的前提下可以使用时间—记忆体权衡攻击，这需要大量的预计算。

2006年， Elad Barkan、Eli Biham和Nathan Keller出版了他们2003年论文的完整版本，其中包括针对A5/X密码的攻击。 作者声称^[13]：

我们将介绍针对GSM加密通信非常实用的唯密文攻击，以及对GSM协议的各种主动攻击。这些攻击甚至能破坏使用所谓“牢不可破”加密的GSM网络。我们首先说到对A5/2的唯密文攻击，该攻击只需要几十毫秒的加密手机通讯，利用个人电脑在数秒钟即可分析出正确的密钥。我们将此攻击扩展为对A5/1的（更复杂的）唯密文攻击。我们接着描述针对使用了A5/1，A5/3的网络协议，或甚至是GPRS协议的（主动）攻击。这些攻击利用了GSM协议中的缺陷，并作用在使用诸如A5/2等弱较弱密码算法的手机上。我们强调这些攻击是针对协议的，所以只要手机使用了较弱的密码算法就适用，例如，它们还适用于使用A5/1的密码分析来攻击使用A5/3的网络。不像以前的GSM攻击需要不切实际的信息，例如长时间的已知明文，我们的攻击非常实用，不需要任何已知明文。此外，我们描述了如何强化攻击的容错性。我们的攻击使攻击者可以在窃听的同时解密对话，或者留存在未来的任何时间解密。

2007年，波鸿鲁尔大学和基尔大学开始了一个研究项目，以开发基于FPGA的大规模并行加密加速器COPACOBANA。COPACOBANA是第一个使用快速时间—记忆体权衡技术的商业解决方案^[14]，可用于攻击使用A5/1、A5/2算法的GSM语音加密，以及资料加密标准（DES）。 它还可以在无需预先计算大型彩虹表的情况下，对GSM进行暴力破解。

2008年， “The Hackers Choice”发起了一个项目，旨在对A5/1进行实用的攻击。攻击需要构建大约3TB的彩虹表。通过姊妹计划中的扫描算法，该小组希望能够在大约3-5分钟内，从任何使用A5/1加密的GSM通联记录，或著SMS简讯中分析出加密密钥，从而可以听取通联记录以及清楚的阅读简讯。但是这些彩虹表没有公开。^[15]

密码学家Karsten Nohl和SaschaKrißler在2009年黑帽安全会议上发表了一个类似的A5/1破解项目。通过Nvidia图形处理器通用计算和P2P分布式计算体系，创建了彩虹表。从2009年9月中旬开始，该项目运行了12个Nvidia GeForce GTX 260的运算量。根据作者的说法，此攻击可用于密钥大小最大为64位的任何加密算法。^[16]

Chris Paget和Karsten Nohl在2009年12月发布了针对A5/1的“A5/1破解计划攻击表（A5/1 Cracking Project attack tables）”。这些表结合了压缩技术，包括彩虹表和特征点链（distinguished point chains）。这些攻击表的各部分加起来只有1.7TB。攻击表在三个月内使用40个分布式的CUDA节点计算出来，然后由社区成员Farid Nasiri上传到BitTorrent和Google云端硬盘上^{[15][16][17][18][19]}。最近，该项目宣布改用速度更快的ATI Evergreen代码，并更改了表的格式。Frank A. Stevenson宣布使用ATI生成的表破解A5/1。^[20]

爱德华·斯诺登在2013年泄露的文件指出，NSA“可以处理A5/1的加密”。^[21]

参考来源

1. Prohibiting A5/2 in mobile stations and other clarifications regarding A5 algorithm support. [2020-02-20]. （原始内容存档于2020-06-22）.
2. Quirke, Jeremy. Security in the GSM system (PDF). 2004年5月1日 [2020年2月20日]. （原始内容 (PDF)存档于2004年7月12日）.
3. "There are officially more mobile devices than people in the world. 独立报. 2014年10月7日 [2020年2月20日]. （原始内容存档于2020年4月5日）.
4. Ross J. Anderson. A5 (Was: HACKING DIGITAL PHONES). Newsgroup: uk.telecom. 1994-06-17. Usenet: 2ts9a0$[e-mail].
5. Prohibiting A5/2 in mobile stations and other clarifications regarding A5 algorithm support. [2020-02-20]. （原始内容存档于2020-06-22）.
6. NSA Able To Crack A5/1 Cellphone Crypto. Slashdot. [2020-02-20]. （原始内容存档于2020-02-20）.
7. 存档副本. [2020-02-20]. （原始内容存档于2016-04-25）.
8. Alex Biryukov; Adi Shamir; David Wagner. Real Time Cryptanalysis of A5/1 on a PC. Fast Software Encryption—FSE 2000. 1999年12月9日: 1–18 [2020年2月20日]. （原始内容存档于2017年7月5日）.
9. Jovan Dj. Golic. Cryptanalysis of Alleged A5 Stream Cipher (PDF). Eurocrypt 1997: 239–55. [2020年2月20日]. （原始内容 (PDF)存档于2010年7月15日）.
10. Eli Biham; Orr Dunkelman. Cryptanalysis of the A5/1 GSM Stream Cipher. Indocrypt 2000. Lecture Notes in Computer Science. 2000, 1997: 43–51. ISBN 978-3-540-41452-0. doi:10.1007/3-540-44495-5_5.
11. Patrik Ekdahl; Thomas Johansson. Another attack on A5/1 (PDF). IEEE Transactions on Information Theory. 2003, 49 (1): 284–89 [2020年2月20日]. doi:10.1109/TIT.2002.806129. （原始内容 (PDF)存档于2005年5月25日）.
12. Elad Barkan; Eli Biham. Conditional Estimators: An Effective Attack on A5/1. Selected Areas in Cryptography 2005. 2005: 1–19.
13. Elad Barkan; Eli Biham; Nathan Keller. Instant Ciphertext-Only Cryptanalysis of GSM Encrypted Communication (PDF). Crypto 2003. Lecture Notes in Computer Science: 600–16. [2020-02-20]. ISBN 978-3-540-40674-7. doi:10.1007/978-3-540-45146-4_35. （原始内容存档 (PDF)于2020-01-25）.
14. Tim Gueneysu; Timo Kasper; Martin Novotný; Christof Paar; Andy Rupp. Cryptanalysis with COPACOBANA (PDF). IEEE Transactions on Computers. 57. 2008, (11): 1498–1513 [2020-02-20]. doi:10.1109/TC.2008.80. （原始内容 (PDF)存档于2016-03-15）.
15. Karsten Nohl; Chris Paget. GSM: SRSLY?. 26th Chaos Communication Congress (26C3). 2009年12月27日 [2020年2月20日]. （原始内容存档于2010年1月6日）.
16. Karsten Nohl; Sascha Krißler. Archived copy (PDF). [2020年2月20日]. （原始内容 (PDF)存档于2011年7月26日）.
17. O'Brien, Kevin. Cellphone Encryption Code Is Divulged. 纽约时报. 2009年12月28日 [2020年2月20日]. （原始内容存档于2019年4月26日）.
18. Karsten Nohl. Direct Link A5/1 rainbow Table in Google drive. [2020-02-20]. （原始内容存档于2020-02-20）.
19. Robert McMillan. Hackers Show It's Easy to Snoop on a GSM Call. IDG News Service. 2009年12月28日 [2020年2月20日]. （原始内容存档于2012年1月20日）.
20. Frank A. Stevenson. Cracks beginning to show in A5/1. 2010年5月1日 [2020年2月20日]. （原始内容存档于2012年3月6日）.
21. Craig Timberg; Ashkan Soltani. By cracking cellphone code, NSA has ability to decode private conversations. 华盛顿邮报. 2013年12月13日 [2020年2月20日]. （原始内容存档于2014年5月7日）.

其他来源

• Rose, Greg. A precis of the new attacks on GSM encryption (PDF). QUALCOMM Australia. 2003-09-10 [2020-02-21]. （原始内容 (PDF)存档于2011-09-27）.
• Maximov, Alexander; Thomas Johansson; Steve Babbage. An Improved Correlation Attack on A5/1. Selected Areas in Cryptography 2004. 2004: 1–18.

外部链接

• Briceno, Marc; Ian Goldberg; David Wagner. A pedagogical implementation of the GSM A5/1 and A5/2 "voice privacy" encryption algorithms. 1999-10-23 [2020-02-21]. （原始内容存档于2018-10-08）.
• Huge GSM flaw allows hackers to listen in on voice calls. 2009-08-25 [2020-02-21]. （原始内容存档于2009-10-14）.
• Horesh, Hadar. Technion team cracks GSM cellular phone encryption (PDF). Haaretz. 2003-09-03 [2020-02-21]. （原始内容 (PDF)存档于2016-03-03）.
• Barkan, Elad; Eli Biham; Nathan Keller. Instant Ciphertext-Only Cryptanalysis of GSM Encrypted Communication (Technical Report CS-2006-07). July 2006 [2020-09-24]. （原始内容存档于2019-12-27）.
• Nathan Keller's Homepage. [2020-02-21]. （原始内容存档于2008-06-04）.
• Animated SVG showing A5/1 stream cypher. [2020-02-21]. （原始内容存档于2012-03-26）.