卫星电话GMR-2流密码算法碰撞特性分析

李瑞林，胡娇，唐朝京



卫星电话GMR-2流密码算法碰撞特性分析

李瑞林，胡娇，唐朝京

（国防科技大学电子科学学院，湖南 长沙 410073）

研究了卫星电话GMR-2流密码算法的碰撞特性，以算法的组件为桥梁，通过分析密钥差分与算法组件输出碰撞以及组件输出碰撞与密钥流字节碰撞之间的联系，最终得到密钥差分与密钥流碰撞之间的关系。研究表明，对于相同的帧号，当密钥对只在某一个字节上有差分，且差分的前4 bit与后4 bit相等时，该密钥对将以高概率使密钥流发生碰撞。实验结果显示，密钥流碰撞概率为2−8.248，远远高于理想碰撞概率2−120。这再次证明了GMR-2加密算法存在较大的安全隐患。

卫星电话；流密码；GMR-2；碰撞分析

1 引言

伴随着2G、3G和4G技术的快速发展，移动通信已经十分普遍，但在某些偏远地区如沙漠地带、海洋、高山等，仍然难以构建完整的移动蜂窝网络。卫星移动通信的出现很好地弥补了陆地蜂窝网络通信的缺点，能够在某些极端环境下提供可靠的通信。随着军民融合卫星移动通信系统的建设[1]，中国正式迈入卫星移动通信的“手机时代”[2]。

在传统的蜂窝移动通信中，为实现安全通信，人们往往采用加密算法来抵御各种窃听风险。比较著名的密码算法包括A5、SNOW和ZUC等，人们对这些算法进行了深入的安全性评估[3~11]。随着卫星移动通信的发展，卫星电话所采用的加密机制的可靠性也备受关注。目前，国际上常用的卫星通信标准主要由国际标准组织ETSI提出，包括GMR-1和GMR-2。但ETSI官方发布的GMR标准并未公开相关密码算法的具体信息，无法对其安全性进行评估。2012年1月，德国Driessen等[12,13]学者使用逆向工程的方法恢复出GMR-1和GMR-2加密算法。结果显示，2种算法均属于流密码算法，其中，GMR-1加密算法是GSM标准中A5/2加密算法的变种版本，因此，许多针对A5/2算法的攻击方法也适用于GMR-1加密算法；GMR-2加密算法则是全新设计的，但该算法的安全性无法达到预期标准，目前，已有学者提出并实现了2种针对该加密算法的攻击方法。文献[13]根据算法的密钥编排特性，提出了基于“读碰撞技术”的攻击方法，该攻击方法需要50~65 B的明文。文献[14]提出了动态猜测决定攻击方法，根据每一次的分析结果动态地猜测下一次的分析状态，仅需要15 B的明文。

2 GMR-2流密码算法简介

2.1 GMR-2流密码算法结构

本文主要符号对照如表1所示。

图1 GMR-2流密码算法结构

表1 符号对照

2.2 GMR-2流密码算法的组件

2.2.1组件

图2组件内部结构

表2 τ1(α)和τ2(τ1(α))的取值

2.2.3组件

图3 G组件内部结构

图4 H组件内部结构

2.3 工作模式

如文献[2]中所述，GMR-2加密过程分为2个阶段：初始化阶段和密钥流生成阶段。

1) 初始化阶段

主要完成各寄存器的初始化工作。

③将该装置运行8拍，直至移位寄存器中的值全部更新，但这8拍不生成密钥流。

2) 密钥流生成阶段

假设加密过程运行完第拍，GMR-2的状态将发生如下变化。

3 F组件碰撞与密钥流碰撞关系

为更好地利用概率模型研究GMR-2流密码算法的密钥流碰撞特性，本文给出以下定义。

根据上述定义，本文有以下结论。

根据GMR-2流密码算法的加密过程及文献[4]，本文有以下2条性质。

根据上述2条性质，本文给出如下命题。

综上所述，命题1得证。

4 F组件碰撞特性分析

将式(1)按位重写为

表3 当输出差分为0时，输入差分的概率分布

其中，

根据表3，本文可以得出以下命题。

c=0c=1c=2c=3c=4c=5c=6c=7 811110.5110.5 911111101 1101111111 1210.510.51111 1311111011 1511011111 其他00000000

综合上述2种情况，命题2得证。

4.2 第拍F组件输出碰撞概率

5 GMR-2流密码算法强密钥流碰撞特性分析

根据上述内部关系，本文给出以下命题。

其中，

最终得到

6 实验分析

表5碰撞概率对比

c 02−8.5442−8.4562−8.4552−19.488 12−9.0772−8.9962−8.9942−18.899 22−8.5442−8.4562−8.4552−19.488 32−9.0772−9.0002−8.9982−19.209 42−9.0772−8.9402−8.9382−18.950 52−8.5442−8.4922−8.4912−19.508 62−8.5442−8.4542−8.4532−19.536 72−6.8172−6.7952−6.7912−15.230 平均值2−8.3142−8.2502−8.2482−17.719

3) 密钥流碰撞概率与强密钥流碰撞概率差距微弱，说明GMR-2流密码算法强密钥流碰撞是密钥流碰撞的主概率事件。

4) 若将GMR-2加密算法的密钥流生成器视为22 bit的帧号与64 bit的密钥到120 bit的密钥流的映射函数，则一个理想安全的密钥流生成器要求：对于不同的(,)，输出15 B密钥流发生碰撞的概率应该为2−120。但实验得到的密钥流碰撞概率为2−8.248，远远高于2−120。这也再一次说明GMR-2算法的碰撞特性明显，安全性较弱。

7 结束语

[1] 何元智. 军民融合重大举措—天通一号卫星移动通信系统[C]// 2016中国卫星应用大会.2016.HE Y Z. A Milestone of civil-military integrated satellite communication: tiantong-01 system[C]//China Satellite Conference 2016. 2016.

[2] 2016中国卫星应用若干重大进展[J]. 卫星应用, 2017(1):32-39.Significant progress in Chinese satellite applications in 2016 [J]. Satellite Application, 2017(1): 32-39

[3] 李磊. 移动通信GSM中密码算法安全性研究[D]. 郑州: 解放军信息工程大学, 2012. LI L. Research on security of cryptographic algorithm in GSM[D]. Zhengzhou: PLA Information Engineering University, 2012.

[4] 关杰, 丁林, 刘树凯. SNOW 3G与ZUC流密码的猜测决定攻击[J]. 软件学报, 2013(6):1324-1333. GUAN J, DING L, LIU S K. Guess and determine attack on SNOW 3G and ZUC[J]. Journal of Software, 2013(6):1324-1333.

[5] 吴泳钢，古天龙，徐周波. SNOW 3G加密算法的BDD攻击[J]. 桂林电子科技大学学报, 2016, 36 (3) :199-203. WU Y G, GU T L, XU Z B. BDD attack on SNOW 3G encryption algorithm[J]. Journal of Guilin University of Electronic Technology, 2016, 36 (3) :199-203.

[6] BARKAN P, BIHAM E, KELLER N. Instant cipher-text only cryptanalysis of GSM encrypted communication[J]. Journal of Cryptology, 2008, 21(3): 392-429.

[7] BIRYUKOV A, SHAMIR A, WAGNER D. Real time cryptanalysis of A5/1 on a PC[M]//Fast Software Encryption, Springer Berlin Heidelberg, 2000: 1-18.

[8] DUNKELMAN O, KELLER N, SHAMIR A. A practical-time attack on the A5/3 cryptosystem used in third generation GSM telephony[C]// Icar Crgptology Eprint Archive. 2010: 393-410.

[9] WU H, HUANG T, NGUYEN P, et al. Differential attacks against stream cipher ZUC[C]//International Conference on the Theory and Application of Cryptology and Information Security. 2012: 262-277.

[10] ZHANG B, XU C, MEIER W. Fast correlation attacks over extension fields, large-unit linear approximation and cryptanalysis of SNOW 2.0[C]//Cryptology Conference. 2015: 643-662.

[11] ZHOU C, FENG X, LIN D. The Initialization stage analysis of ZUC v1.5[C]//Cryptology and Network Security. 2011: 40-53.

[12] DRIESSEN B, HUND R, WILLEMS C, et al. Don't trust satellite phones: a security analysis of two satphone standards[C]//Security and Privacy (SP). 2012: 128-142.

[13] DRIESSEN B, HUND R, WILLEMS C, et al. An experimental security analysis of two satphone standards[J]. ACM Transactions on Information & System Security, 2013, 16(3):1-30.

[14] LI R, LI H, LI C, ET AL. A low data complexity attack on the GMR-2 Cipher Used in the Satellite Phones[C]//FSE. 2013: 485-501.

Collision analysis of the GMR-2 cipherused in the satellite phone

LI Ruilin, HU Jiao, TANG Chaojing

College of Electronic Science, National University of Defense Technology,Changsha 410073, China

A collision property analysis of the GMR-2 cipher used in the satellite phone was presented. By using the-component as a bridge, the link between the difference of the key byte and the collision of the output ofas well as the link between the collision of the output ofand the collision of keystream byte were analyzed, which finally revealed the relationship between the difference of the original key byte and the keystream collision. The theoretical analysis showed that for a random frame number, a special chosen key pair could lead to a keystream collision with a high probability, when the key pair has only one byte difference in which the most significant 4 bit of the difference was equal to the last significant 4 bit. The experimental result shows that the keystream collision probability is 2−8.248, which is far higher than the ideal collision probability 2−120. This proves once again, that there exists serious potential security hazards in the GMR-2 cipher.

satellite phones, stream cipher, GMR-2, collision analysis

TN918

A

10.11959/j.issn.1000-436x.2018026

2017-08-06；

2017-12-25

李瑞林，securitylrl@gmail.com

国家自然科学基金资助项目（No.61402515, No.61702536）

The National Natural Science Foundation of China (No.61402515, No.61702536)

李瑞林（1982-），男，山西太原人，博士，国防科技大学讲师，主要研究方向为密码学与信息安全。

胡娇（1993-），女，湖南岳阳人，国防科技大学硕士生，主要研究方向为密码学与信息安全。

唐朝京（1962-），男，江苏常州人，博士，国防科技大学教授，主要研究方向为网络空间安全与对抗。