移动通信网中的密码算法演进 (一)：机密性保护

全球大规模商用的移动通信始于20世纪80年代。由于空口的开放性，认证、机密性保护、完整性保护等安全要素在系统设计时就被充分考虑，并纳入到全球标准，通信设备厂商和终端厂商都按标准实现安全特性。从上世纪90年代到现在，数字蜂窝移动通信系统所采用的密码算法被人反复研究，用于攻击的算力也今非昔比。与之对应的，蜂窝移动通信的密码算法在不断地完善，相关的标准也在不断地更新。本文将以GSM所采用的密码算法作为起点，介绍各代移动通信系统中所采用密码算法的变迁与演进。5G的安全标准还在制定之中，我们也会介绍下5G密码算法的一些考虑和标准进展。

在3GPP定义的蜂窝无线通信系统中，密码算法主要用于空口的机密性和完整性保护、网络与终端之间的相互认证、以及网络域的安全保护等场景。本公众号将分别从机密性保护、完整性保护、身份认证等角度深入探讨移动通信网的密码算法。

作为一个系列的第一篇，本文将从用于机密性保护的加密算法开始谈起。

2G（GSM）

GSM网络中使用的加密算法并未正式公开，在标准的文本中被称为A5系列的算法[1]。A5系列算法包含A5/1，A5/2，A5/3算法，以及近两年新出现的A5/4算法。A5/1，A5/2，A5/3的密钥长度为64bit，A5/4是A5/3算法的另一种模式，密钥长度为128bit。

A5/1算法产生于1987年，为流密码算法。A5/1算法曾经是使用最广泛的GSM加密算法，在设备中的支持程度也是几种算法中最高的。由于受巴统限制，该算法作为出口管制技术无法集成到在中国境内使用的设备中。该算法在1994年被初步泄露，在1999年通过逆向工程的方式被公布出来[2]，从2000年开始即被逐步破解。2000年Alex Biryukov等通过构造庞大的具备初步彩虹表概念的数据库，通过查表取代计算的方式，以空间换时间，对A5/1实施已知明文攻击，但该方法需要首先通过大约2⁴⁸次运算，处理约300GB的数据[3]。2007年，德国Bochum大学搭建了具有120个FPGA节点的阵列加速器，对包括A5/1算法在内的多种算法进行破解[4]，由于采用FPGA成本较低，使A5/1算法破解在商业上成为可能。2009年黑帽大会上，Karsten Nohl等人利用3个月时间制作了2TB的彩虹表，并宣布利用P2P分布式网络下的Nvidia GPU显卡阵列即可破解A5/1算法[5]。2016年，新加坡科技研究局用约55天创建了一个984GB的彩虹表，通过使用3块Nvidia GPU显卡构成的计算装置在9秒内完成对A5/1算法的破解[6]。此外，根据斯诺登披露的文件显示，美国NSA是可以破解A5/1算法的。

A5/2算法产生于1989年，算法存在缺陷，一经公布即被发现算法弱点[7]，使得采用A5/2算法加密的数据可以被实时破解，因此A5/2算法被弃用，在3GPP标准TS 33.020[1]里明确禁止（forbidden）使用该算法。

A5/3算法，其核心算法是KASUMI分组加密算法[8]，由ETSI SAGE基于三菱电机的MISTY1[9]算法，针对移动设备进行了部分修改而提出的。加密方式采用流加密的形式。A5/3算法的安全性不断受到挑战，2001年，Kühn Ulrich在欧洲密码会议上提出了针对MISTY1六轮计算的理论攻击方法[10]，2005年，以色列研究员提出了一种理论攻击的方法[11]，可以在构造了2⁵⁵数量级的选择明文情况下，经过2⁷⁶次运算破解算法。2010年Dunkelman, Keller和Shamir的论文论证了一种对KASUMI可实施的攻击[12]，其可以在一台装有因特尔酷睿2双核处理器的电脑上在2个小时内破解KASUMI算法。由于攻击实施之前需要事先构造出百万个已知明文，并获取这些明文经过运营商网络加密之后的密文，在现实中很难做到，这种攻击并未对电信系统中的A5/3算法造成实质的威胁，但仍揭示了算法的不安全性。因此，负责管理GSM后续进展的3GPP（第三代通信网络合作伙伴计划）在2010年定义了新的A5/4算法。A5/4算法与A5/3相同，但密钥长度由64bit扩展到了128bit。随之在2015年，KASUMI算法的原型算法MISTY1（采用128bit）也遭到破解，使得其计算强度从2¹²⁸降至2⁷⁰左右[13]。此攻击需要2⁶⁴选择密文和2⁷⁰次加密运算，因此只是理论上有意义。

还需要补充一点，GSM是一个面向语音通信的网络，在GSM的基础上，通过增加分组交换的核心网，建立了GPRS（General Packet Radio Service），GPRS采用的加密算法仍然是A5系列算法，但在标准的命名中称为GEA（GPRS Encryption Algorithm）系列，即，GEA1-GEA4，分别对应于A5/1-A5/4。

3G（UMTS）

3G（UMTS，Universal Mobile Telecommunication System）网络中有2种加密算法，分别为上文提到的KASUMI和SNOW 3G[14]，这两种算法采用的密钥长度均为128bit，在标准中被命名为UEA（UMTS Encryption Algorithm）系列，名称分别为UEA1和UEA2。SNOW 3G是在欧洲的NESSIE（New European Schemes for Signatures, Integrity and Encryption，新的欧洲加密、完整性以及签名保护方案）项目中产生的候选算法SNOW 1.0的基础上逐步演进而来，是一种流加密算法。SNOW 1.0算法在公开后，被发现存在一些算法缺陷，之后经过不断修订和增强，从SNOW 1.0，SNOW 2.0直到SNOW 3G被认可作为3G使用的第二种算法。由于KASUMI算法在2005年就已经存在公开的理论攻击方法，所以在3GPP制定4G标准（LTE）的时候，放弃了KASUMI，转而使用新的密码算法。

4G（LTE）

4G（LTE，Long Term Evolution）网络中有3种加密算法，称为EEA（EPS Encryption Algorithm）系列。

在LTE初始Rel-8版本中有2种加密算法，分别为3G标准中已经采纳的SNOW 3G算法，以及取代了KASUMI的AES算法，两种算法密钥长度均采用128bit。

采用AES取代KASUMI主要有以下原因：4G的基站需要实现NDS/IP[15]的保护，而NDS/IP中需要使用AES，所以4G的基站天然支持AES算法；KASUMI算法有授权费用，虽然使用KASUMI进行完整性保护不需要缴费，但若用于加密则需要缴费；此外，4G支持非3GPP接入，而AES在非3GPP接入（例如WLAN）场景中的应用更广。

此外，考虑到中国自主加密算法的需求，在工信部和国家密码局的领导下，由信通院牵头，中国移动、中国联通、大唐、华为、中兴、中科院软件所等参与成立中国自主加密算法推进工作组，经过多年酝酿，于2009年在3GPP SA3立项讨论，最终于2011年将中科院软件所设计的祖冲之算法（代号ZUC）推入3GPP标准，在LTE Rel-11版本中成为可选的第3种加密算法。祖冲之算法为流加密算法，具备与SNOW 3G基本等同的性能和加密强度。

截止到目前为止，还没有公开资料显示AES、SNOW 3G和ZUC存在安全问题。

5G

5G的标准化始于2016年，5G被通信产业界寄予厚望，在不断增加空口速率（eMBB, enhanced Mobile BroadBand）的基础上，5G还将作为大规模蜂窝物联网（mIoT, massive IoT）、高可靠超低时延通信（uRLLC, ultra Reliable and Low Latency Control）等应用场景的解决方案。由于这3个场景愿景宏大，而各个场景对技术指标的要求又各不相同甚至有所矛盾，所以5G的标准制定过程非常复杂。考虑到韩国希望在2018年冬奥会，日本希望在2020年奥运会上启用5G，对5G应用的需求比较急迫。为满足时间计划，3GPP把5G的标准分为两个阶段：Phase1和Phase2。其中Phase1主要制定eMBB场景所需要的标准，而Phase2将聚焦于制定mIoT和uRLLC相关的标准。这三种场景对密码算法的要求有所不同。

算法的考量

对于eMBB而言，主要的终端形态仍以手机、MiFi，或者其他有一定计算能力且带有5G模组的智能硬件为主。由于AES，SNOW 3G和ZUC没有公开的安全风险，且在通信芯片中的实现也非常成熟，所以在eMBB场景下，也就很自然地沿用了4G的这3种算法，这也是目前Phase1标准过程的一个初步结论。

对于Phase2，情况可能有所不同。如在mIoT场景中，终端可能是计算能力比较弱的传感器，且从其服务寿命来看，在保证一定安全性的前提下，加解密上的开销越小越好。举一个极端一点的例子，以RFID（Radio Frequency Identification）为例，RFID中提供给安全的空间仅2000GE（Gate Equivalent）[16]，AES算法需要大约3500GE，前面提到的KASUMI更是需要6000GE，均无法应用于RFID。所以在mIoT的场景中，可能会引入轻量级的算法。目前ISO中已经有一些轻量级算法的标准[17]，但3GPP在现阶段并没有提出具体的需求和候选算法的情况。

密钥长度的考量

对于eMBB场景来说，目前5G将沿用4G的算法，密钥长度也保持128bit。但关于是否要采用256bit的密钥长度是有争议的，主要是因为5G的商用时间预计为2020年到2040年，期间量子计算机的发展可能会对目前密码算法的安全性形成实质性的威胁。移动通信的机密性是基于对称密钥的，而对称密钥的分发是基于USIM卡的制卡和分发过程，所以在这种流程下，基于量子计算机Shor算法[18]对非对称密钥的致命攻击不会影响到移动通信密钥分发。而基于量子计算机的Grover搜索算法[19]能将对称密钥算法的蛮力破解复杂度降至，意味着256bit的密钥长度，在量子计算时代，其密钥空间等效于传统计算机的128bit密钥长度。正是由于这个原因，有人建议在5G时代应支持256bit密钥长度。但反对者认为，量子计算机距离成熟商用、快捷有效地破解移动通信密钥还为时尚早，所以不建议这么早支持256bit，毕竟支持256bit的密钥将影响芯片、终端、设备的实现。基于这些原因，目前标准的讨论进展是，Phase1仅支持128bit的密钥长度，在Phase2再考虑256bit的密钥长度。

新的加密需求

除了传统意义上的对信令和用户数据的机密性保护之外，5G安全提出了一个新的诉求，即对可能出现在空口上的IMSI（5G中称为SUPI）进行隐私保护。一般在认证过程之后，在用户终端和网络之间就会生成会话密钥来用于加解密。这个过程也称为安全上下文建立的过程。在安全上下文建立之后，就可以对空口的信令和用户数据加密。这个思路从2G到5G都是如此。但5G标准提供了一个新的、之前各代均不具备的加密特性，即，在安全上下文建立之前，就可以对空口上出现的IMSI进行加密。

一般情况下，空口上都不会出现IMSI，而是临时标识符TMSI，这本身可以等同于为一种加密的方式，但当网络没有存储与用户IMSI对应的TSMI的时候，就需要用户将IMSI发送给网络，这个少有的场景下，IMSI会暴露在空中接口，IMSI catcher就可以截获IMSI[20]。

5G对SUPI的加密保护引入了一个新的保护方式，即通过利用归属网络的公钥对SUPI进行加密。在用户的USIM卡中存放一个归属网络的公钥，一旦需要向空中接口发送SUPI，就用该公钥对SUPI进行加密，加密后的数据称为SUCI。拜访网络收到这个加密后的SUCI后，将其送回到归属网络，用归属网络的私钥进行解密。这其中涉及的公钥加密算法目前尚未完成定义，只是限定了需要采用ECIES(Eliptic Curve Integrated Encryption System)[21]的方式进行计算。ECIES包含密钥生成模块和数据加密模块两部分，密钥生成模块使用发送方的私钥和接收方的公钥在椭圆曲线上进行多倍点运算，进而生成会话密钥；数据加密模块使用生成的会话密钥对数据进行加密。

总结

综上，在各代网络中，机密性算法的情况汇总如下：

总体而言，3GPP对移动通信网机密性保护算法的演进的动力主要来自于不断发展的计算能力和攻击方法对现有机制的威胁与挑战。就目前状况而言，AES、SNOW 3G和ZUC在128bit密钥的长度上能胜任要求，且在未来的几年也未见有力的挑战，但量子计算所带来的全新的计算能力，以及新的算法思维方式可能会导致形成新的格局。

参考文献

[1] 3GPP TS 43.020, Security related network functions.

[2] Briceno, Marc, Goldberg, Ian and Wagner, David (1999). A pedagogical implementation of A5/1. http://www.scard.org/gsm/a51.html

[3] Biryukov, Alex; Adi Shamir; David Wagner. Real Time Cryptanalysis of A5/1 on a PC. Fast Software Encryption—FSE 2000, 1–18, 2000.

[4] Gueneysu, Tim; Timo Kasper; Martin Novotný; Christof Paar; Andy Rupp. Cryptanalysis with COPACOBANA. Transactions on Computers. 57: 1498–1513, 2008.

[5] Nohl, Karsten; Chris Paget. GSM: SRSLY?. 26th Chaos Communication Congress. 2010.

[6] Li Z. Optimization of Rainbow Tables for Practically Cracking GSM A5/1 Based on Validated Success Rate Modeling. CT-RSA 2016. Lecture Notes in Computer Science, vol 9610, 359-377, 2016.

[7] Goldberg, Ian and Wagner, David and Green, Lucky (1999). The (Real-Time) Cryptanalysis of A5/2. Rump session of Crypto"99, 1999.

[8] 3GPP TR 33.908: General Report on the Design, Speification and Evaluation of 3GPP Standard Confidentiality and Integrity Algorithms". 2009.

[9] Matsui, Mitsuru; Tokita, Toshio (Dec 2000). "MISTY, KASUMI and Camellia Cipher Algorithm Development". Mitsibishi Electric Advance. Mitsibishi Electric corp.

[10] Kühn Ulrich, Cryptanalysis of Reduced Round MISTY. EUROCRYPT 2001

[11] Eli Biham, Orr Dunkelman, Nathan Keller. A Related-Key Rectangle Attack on the Full KASUMI. ASIACRYPT 2005. pp. 443–461.

[12] Orr Dunkelman; Nathan Keller; Adi Shamir (2010-01-10). "A Practical-Time Attack on the A5/3 Cryptosystem Used in Third Generation GSM Telephony".

[13] Achiya Bar-on: A 270 Attack on the Full MISTY1.https://eprint.iacr.org/2015/746.pdf

[14] 3GPP TS35.216: Specification of the 3GPP Confidentiality and Integrity Algorithms UEA2 & UIA2; Document 2: SNOW 3G specification

[15] 3GPP TS 33.310, Network Domain Security (NDS); Authentication Framework (AF).

[16] Juels A. and Weis S.A., Authenticating pervasive devices with human protocols. In Advances in Cryptology — CRYPTO 2005, volume 3126 of Lecture Notes in Computer Science, pages 293–198. Springer-Verlag, 2005.

[17] ISO/IEC DIS 29192 Information technology - Security techniques - Lightweight cryptography.

[18] Shor P.W., Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer. SIAM Journal on Computing 26(5), 1484–1509, 1997.

[19] Grover L.K., A fast quantum mechanical algorithm for database search, Proceedings, 28th Annual ACM Symposium on the Theory of Computing, 212-219, 1996.

[20] Low-cost IMSI catcher for 4G/LTE networks tracks phones’ precise locations.

http://arstechnica.com/security/2015/10/low-cost-imsi-catcher-for-4glte-networks-track-phones-precise-locations/

[21] ISO 18033-2: A Standard for Public-Key Encryption.

声明：本文来自禾云安全，版权归作者所有。文章内容仅代表作者独立观点，不代表安全内参立场，转载目的在于传递更多信息。如有侵权，请联系 anquanneican@163.com。