衛星電話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-），男，江蘇常州人，博士，國防科技大學教授，主要研究方向為網絡空間安全與對抗。