衛(wèi)星電話GMR-2流密碼算法碰撞特性分析

李瑞林，胡嬌，唐朝京

?

衛(wèi)星電話GMR-2流密碼算法碰撞特性分析

李瑞林，胡嬌，唐朝京

（國(guó)防科技大學(xué)電子科學(xué)學(xué)院，湖南 長(zhǎng)沙 410073）

研究了衛(wèi)星電話GMR-2流密碼算法的碰撞特性，以算法的組件為橋梁，通過分析密鑰差分與算法組件輸出碰撞以及組件輸出碰撞與密鑰流字節(jié)碰撞之間的聯(lián)系，最終得到密鑰差分與密鑰流碰撞之間的關(guān)系。研究表明，對(duì)于相同的幀號(hào)，當(dāng)密鑰對(duì)只在某一個(gè)字節(jié)上有差分，且差分的前4 bit與后4 bit相等時(shí)，該密鑰對(duì)將以高概率使密鑰流發(fā)生碰撞。實(shí)驗(yàn)結(jié)果顯示，密鑰流碰撞概率為2?8.248，遠(yuǎn)遠(yuǎn)高于理想碰撞概率2?120。這再次證明了GMR-2加密算法存在較大的安全隱患。

衛(wèi)星電話；流密碼；GMR-2；碰撞分析

1 引言

伴隨著2G、3G和4G技術(shù)的快速發(fā)展，移動(dòng)通信已經(jīng)十分普遍，但在某些偏遠(yuǎn)地區(qū)如沙漠地帶、海洋、高山等，仍然難以構(gòu)建完整的移動(dòng)蜂窩網(wǎng)絡(luò)。衛(wèi)星移動(dòng)通信的出現(xiàn)很好地彌補(bǔ)了陸地蜂窩網(wǎng)絡(luò)通信的缺點(diǎn)，能夠在某些極端環(huán)境下提供可靠的通信。隨著軍民融合衛(wèi)星移動(dòng)通信系統(tǒng)的建設(shè)[1]，中國(guó)正式邁入衛(wèi)星移動(dòng)通信的“手機(jī)時(shí)代”[2]。

在傳統(tǒng)的蜂窩移動(dòng)通信中，為實(shí)現(xiàn)安全通信，人們往往采用加密算法來抵御各種竊聽風(fēng)險(xiǎn)。比較著名的密碼算法包括A5、SNOW和ZUC等，人們對(duì)這些算法進(jìn)行了深入的安全性評(píng)估[3~11]。隨著衛(wèi)星移動(dòng)通信的發(fā)展，衛(wèi)星電話所采用的加密機(jī)制的可靠性也備受關(guān)注。目前，國(guó)際上常用的衛(wèi)星通信標(biāo)準(zhǔn)主要由國(guó)際標(biāo)準(zhǔn)組織ETSI提出，包括GMR-1和GMR-2。但ETSI官方發(fā)布的GMR標(biāo)準(zhǔn)并未公開相關(guān)密碼算法的具體信息，無法對(duì)其安全性進(jìn)行評(píng)估。2012年1月，德國(guó)Driessen等[12,13]學(xué)者使用逆向工程的方法恢復(fù)出GMR-1和GMR-2加密算法。結(jié)果顯示，2種算法均屬于流密碼算法，其中，GMR-1加密算法是GSM標(biāo)準(zhǔn)中A5/2加密算法的變種版本，因此，許多針對(duì)A5/2算法的攻擊方法也適用于GMR-1加密算法；GMR-2加密算法則是全新設(shè)計(jì)的，但該算法的安全性無法達(dá)到預(yù)期標(biāo)準(zhǔn)，目前，已有學(xué)者提出并實(shí)現(xiàn)了2種針對(duì)該加密算法的攻擊方法。文獻(xiàn)[13]根據(jù)算法的密鑰編排特性，提出了基于“讀碰撞技術(shù)”的攻擊方法，該攻擊方法需要50~65 B的明文。文獻(xiàn)[14]提出了動(dòng)態(tài)猜測(cè)決定攻擊方法，根據(jù)每一次的分析結(jié)果動(dòng)態(tài)地猜測(cè)下一次的分析狀態(tài)，僅需要15 B的明文。

2 GMR-2流密碼算法簡(jiǎn)介

2.1 GMR-2流密碼算法結(jié)構(gòu)

本文主要符號(hào)對(duì)照如表1所示。

圖1 GMR-2流密碼算法結(jié)構(gòu)

表1 符號(hào)對(duì)照

2.2 GMR-2流密碼算法的組件

2.2.1組件

圖2組件內(nèi)部結(jié)構(gòu)

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

2.2.3組件

圖3 G組件內(nèi)部結(jié)構(gòu)

圖4 H組件內(nèi)部結(jié)構(gòu)

2.3 工作模式

如文獻(xiàn)[2]中所述，GMR-2加密過程分為2個(gè)階段：初始化階段和密鑰流生成階段。

1) 初始化階段

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

③將該裝置運(yùn)行8拍，直至移位寄存器中的值全部更新，但這8拍不生成密鑰流。

2) 密鑰流生成階段

假設(shè)加密過程運(yùn)行完第拍，GMR-2的狀態(tài)將發(fā)生如下變化。

3 F組件碰撞與密鑰流碰撞關(guān)系

為更好地利用概率模型研究GMR-2流密碼算法的密鑰流碰撞特性，本文給出以下定義。

根據(jù)上述定義，本文有以下結(jié)論。

根據(jù)GMR-2流密碼算法的加密過程及文獻(xiàn)[4]，本文有以下2條性質(zhì)。

根據(jù)上述2條性質(zhì)，本文給出如下命題。

綜上所述，命題1得證。

4 F組件碰撞特性分析

將式(1)按位重寫為

表3 當(dāng)輸出差分為0時(shí)，輸入差分的概率分布

其中，

根據(jù)表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流密碼算法強(qiáng)密鑰流碰撞特性分析

根據(jù)上述內(nèi)部關(guān)系，本文給出以下命題。

其中，

最終得到

6 實(shí)驗(yàn)分析

表5碰撞概率對(duì)比

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) 密鑰流碰撞概率與強(qiáng)密鑰流碰撞概率差距微弱，說明GMR-2流密碼算法強(qiáng)密鑰流碰撞是密鑰流碰撞的主概率事件。

4) 若將GMR-2加密算法的密鑰流生成器視為22 bit的幀號(hào)與64 bit的密鑰到120 bit的密鑰流的映射函數(shù)，則一個(gè)理想安全的密鑰流生成器要求：對(duì)于不同的(,)，輸出15 B密鑰流發(fā)生碰撞的概率應(yīng)該為2?120。但實(shí)驗(yàn)得到的密鑰流碰撞概率為2?8.248，遠(yuǎn)遠(yuǎn)高于2?120。這也再一次說明GMR-2算法的碰撞特性明顯，安全性較弱。

7 結(jié)束語

[1] 何元智. 軍民融合重大舉措—天通一號(hào)衛(wèi)星移動(dòng)通信系統(tǒng)[C]// 2016中國(guó)衛(wèi)星應(yīng)用大會(huì).2016.HE Y Z. A Milestone of civil-military integrated satellite communication: tiantong-01 system[C]//China Satellite Conference 2016. 2016.

[2] 2016中國(guó)衛(wèi)星應(yīng)用若干重大進(jìn)展[J]. 衛(wèi)星應(yīng)用, 2017(1):32-39.Significant progress in Chinese satellite applications in 2016 [J]. Satellite Application, 2017(1): 32-39

[3] 李磊. 移動(dòng)通信GSM中密碼算法安全性研究[D]. 鄭州: 解放軍信息工程大學(xué), 2012. LI L. Research on security of cryptographic algorithm in GSM[D]. Zhengzhou: PLA Information Engineering University, 2012.

[4] 關(guān)杰, 丁林, 劉樹凱. SNOW 3G與ZUC流密碼的猜測(cè)決定攻擊[J]. 軟件學(xué)報(bào), 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]. 桂林電子科技大學(xué)學(xué)報(bào), 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

國(guó)家自然科學(xué)基金資助項(xiàng)目（No.61402515, No.61702536）

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

李瑞林（1982-），男，山西太原人，博士，國(guó)防科技大學(xué)講師，主要研究方向?yàn)槊艽a學(xué)與信息安全。

胡嬌（1993-），女，湖南岳陽人，國(guó)防科技大學(xué)碩士生，主要研究方向?yàn)槊艽a學(xué)與信息安全。

唐朝京（1962-），男，江蘇常州人，博士，國(guó)防科技大學(xué)教授，主要研究方向?yàn)榫W(wǎng)絡(luò)空間安全與對(duì)抗。