湯永利　韓　娣　李子臣,2

1(河南理工大學計算機科學與技術學院　河南 焦作 454000)2(北京電子科技學院　北京 100070)

?

流密碼Grain-128密鑰恢復攻擊及改進

湯永利1韓娣1李子臣1,2

1(河南理工大學計算機科學與技術學院河南 焦作 454000)2(北京電子科技學院北京 100070)

摘要流密碼Grain-128是Grain v1算法的密鑰增長版本。為探討流密碼Grain-128的安全性，指出Grain-128密鑰流生成器的3個布爾函數的設計缺陷,在此基礎上給出流密碼Grain-128一種基于密鑰流生成器中間內部狀態(tài)的密鑰恢復攻擊。該攻擊的計算復雜度和空間復雜度都為O(256)。為了抵抗該攻擊，對Grain-128密鑰流生成器的設計進行了改進。安全性分析表明，改進后的流密碼Grain-128能夠抵抗所提出的密鑰恢復攻擊。

關鍵詞流密碼Grain-128密鑰恢復攻擊密鑰流生成器布爾函數

0引言

為了加大推進流密碼的研究，2004年歐洲啟動流密碼征集項目eSTREAM工程[1]。主要目的是收集安全快速的流密碼算法，eSTREAM工程一共收集了34個序列密碼算法。經過連續(xù)3個階段的連續(xù)評選，選出4個面向硬件實現的算法和4個面向軟件實現的算法。因為適合硬件實現的算法F-FCSR-H已被破譯，現在還有7個算法。

Grain 算法是由Martin Hell等人設計的一種流密碼算法，也是eSTREAM工程最終評選的3個面向硬件實現的流密碼算法之一。Grain v1版本的密鑰長度為80比特，初始向量(IV)為64比特，初始化160個時鐘周期后產生密鑰流[2]。為提高Grain v1算法的安全性，文獻[3]設計了Grain-v1的密鑰增長版本—Grain-128，其密鑰長度為128比特，初始向量為96比特，具有更高的安全性；文獻[4]首次提出了利用Grain-128的布爾函數來進行密鑰恢復攻擊；文獻[5，6]提出利用動態(tài)立方攻擊(Dynamic Cube Attack)對Grain-128進行安全性分析；在文獻[7]中，Lee等人提出Grain v1和Grain-128的相關密鑰選擇IV攻擊。

在對流密碼進行安全性分析時，經常會用到密鑰恢復攻擊。密鑰恢復攻擊就是利用某種方法獲得密鑰流生成器(KG)在某個時刻的內部狀態(tài)，即密鑰流產生過程中的內部存儲單元(如記憶單元、線性及非線性移位寄存器等)中的值。攻擊者就是利用密鑰流生成器的設計缺陷和一個已知的內部狀態(tài)來獲得密鑰[8]。

本文在對流密碼Grain-128工作原理分析時，發(fā)現其密鑰流生成器的3個函數(初始化函數、狀態(tài)轉換函數、密鑰流生成函數)存在設計缺陷。利用這3個設計缺陷給出了流密碼Grain-128一種基于密鑰流生成器某一時刻中間內部狀態(tài)的密鑰恢復攻擊。為了進一步提高流密碼Grain-128的安全性，抵抗該密鑰恢復攻擊，本文對Grain-128的密鑰流生成器進行了改進，并證明了改進后的Grain-128算法能抵抗本文提出的密鑰恢復攻擊。

1Grain-128算法

1.1算法描述

流密碼Grain-128的128位密鑰記為k=(k0,k1,…,k127)，64位初始化向量記為IV=(iv0,iv1,…,iv63)。該算法主要是由3個部件組成：128位的線性反饋移位寄存器(LFSR)s0,s1,…,s127、128位的非線性反饋移位移存器(NFSR)b0,b1,…,b127以及過濾函數h(x)組成，如圖1所示。

圖1　Grain-128算法框圖

1.2線性反饋移位寄存器(LFSR)

LFSR是128級的線性反饋移位寄存器，在域GF(2)上進行運算，其反饋多項式為：

f(x)=1+x32+x47+x58+x90+x121+x128

LFSR相應的狀態(tài)更新函數為：

si+128=si+si+7+si+38+si+70+si+81+si+96

(1)

1.3非線性反饋移位寄存器(NFSR)

NFSR是128級的線性反饋移位寄存器，在域GF(2)上進行運算，其反饋多項式為：

g(x)=1+x32+x37+x72+x102+x128+x44x66+x61x125+

x63x67+x69x101+x80x88+x110x111+x115x117

NFSR相應的狀態(tài)更新函數為：

bi+128=si+bi+bi+26+bi+56+bi+91+bi+96+bi+3bi+67+

bi+11bi+13+bi+17bi+18+bi+27bi+59+bi+40bi+48+

bi+61bi+65+bi+68bi+84

(2)

1.4過濾函數

對h(x)的定義如下：

h(x)=x0x1+x2x3+x4x5+x6x7+x0x4x8

其中，x0、x1、x2、x3、x4、x5、x6、x7、x8分別對應bi+12,si+8,si+13,si+20,bi+95,si+42,si+60,si+79和si+95。

1.5初始化過程

首先將128比特載入NFSR，即bt+i=ki(0≤i≤127)。LFSR前96位用初始向量IV載入，即st+i=IVi(0≤i≤95)。將LFSR后32比特用1填充，即st+i=1(96≤i≤127)。

加載密鑰和初始化向量完成后，算法運行256個時鐘周期不產生密鑰流。在這256個時鐘周期內，將兩個寄存器的反饋和密鑰流KS做模2加運算，完成LFSR和NFSR的初始化過程，如圖2所示。

圖2　Grain-128算法初始化過程

1.6密鑰流產生過程

從LFSR中取出1個比特si+93,從NFSR中取出7個比特分別為bi+2、bi+15、bi+36、bi+45、bi+64、bi+73、bi+89，還有1比特h一共9比特做模2加運算，得到1比特密鑰流，記作zi，如下式所示：

zi=∑j∈Abi+j+h(x)+si+93

(3)

其中，A={2,15,36,45,64,73,89}。

2Grain-128的密鑰恢復攻擊

密鑰恢復攻擊是指通過代數攻擊[9]、錯誤攻擊[10]、時間空間數據折衷(TMD)[11]還有立方攻擊[12]等手段獲得密鑰流生成器(KG)的某個時刻的中間內部狀態(tài)。因此我們可以利用某個已知的中間內部狀態(tài)和密鑰流生成器來推斷密鑰。

在攻擊假設條件下，攻擊者已經知道密鑰流生成器在某一時刻的中間內部狀態(tài)，即攻擊者已知i=t(t>0)時刻時的Bt=(bt,bt+1,…,bt+127)和St=(st,st+1,…,st+127)。通過觀察Grain-128的密鑰流生成器的工作過程，可以發(fā)現密鑰流生成器有以下幾個設計缺點[13]：

(1) 密鑰流生成階段和初始化階段的狀態(tài)轉換函數很相似。

(2) LFSR及NFSR狀態(tài)Si和Bi最高位的值si、bi在密鑰流生成階段和密鑰初始化階段線性參與下一個狀態(tài)Si+1、Bi+1的產生。

(3) 第i拍密鑰流輸出函數值zi與LFSR及NFSR內部狀態(tài)最高位的值si、bi無關。

由于密鑰流生成器存在上述缺陷，我們可以進行下面的攻擊過程：首先，對密鑰流生成階段進行攻擊，利用LFSR和NFSR在這個階段的狀態(tài)轉換函數進行逆向推理，求出該階段的初始狀態(tài)S0及B0；然后，對密鑰初始化階段進行攻擊，利用LFSR和NFSR在這個階段的狀態(tài)轉換函數進行逆向推理，求出該階段的初始狀態(tài)B-256和S-256，其中NFSR的初態(tài)B-256就是我們需要求出的密鑰。因此對Grain-128算法具體的密鑰恢復攻擊過程如下。

2.1密鑰流生成階段的攻擊

根據密鑰流生成階段(i>0)LFSR及NFSR的狀態(tài)轉換關系逆向遞推出S0和B0，攻擊過程如下：

步驟1對LFSR的狀態(tài)更新關系表達式(1)進行逆向遞推得到i-1時刻的狀態(tài)Si-1最高位的值si-1:

si-1=si+6+si+37+si+69+si+80+si+96+si+127

LFSR進行逆向反饋移位之后的狀態(tài)Si-1=(si-1,si,…,si+126)。

步驟2對NFSR的更新關系表達式(2)進行逆向遞推得到i-1時刻狀態(tài)B最高位的值bi-1：

bi-1=si-1+bi+25+bi+55+bi+90+bi+95+bi+127+bi+2bi+66+

bi+10bi+12+bi+16bi+17+bi+26bi+58+bi+39bi+47+

bi+60bi+64+bi+67bi+83

為描述方便，上式可以簡記為如下表達式：

bi-1=si-1+bi+127+I(bi+2,bi+10,bi+12,bi+16,bi+17,bi+25,

bi+26,bi+39,bi+47,bi+55,bi+58,bi+60,bi+64,bi+66,

bi+67,bi+83,bi+90,bi+95)

NFSR進行逆向反饋移位后的狀態(tài)：

Bi-1=(bi-1,bi,…,bi+126)

由前面的密鑰恢復攻擊假設可知，當攻擊者知道密鑰流生成器在某一時刻的狀態(tài)Bt、St時，按照步驟1和步驟2的順序進行逆向遞推，直到i=0時，即可得到密鑰流生成階段的初始狀態(tài)B0=(b0,b1,…,b127),S0=(s0,s1,…,s127)。

2.2初始化階段的攻擊

利用2.1節(jié)求出的密鑰流生成階段的初始狀態(tài)B0和S0，然后對該階段的狀態(tài)轉換函數做逆向遞推256步，即可得到S-256及B-256。當-256

步驟1根據密鑰流的輸出函數式(3)得到i-1時的輸出函數值zi-1:

zi-1=O(bi+1,bi+11,bi+14,bi+35,bi+44,bi+63,bi+73,bi+88,bi+94,

si+7,si+12,si+19,si+41,si+59,si+78,si+92,si+94)

步驟2利用步驟1得到的zi-1和式(1)推出i-1時刻的LFSR的狀態(tài)Si-1最高位si-1：

si-1=zi-1+si+6+si+37+si+69+si+80+si+96+si+127

因此，LFSR進行一次逆向反饋移位后得到i-1時刻的狀態(tài)Si-1=(si-1,si,…,si+126)。

步驟3利用步驟1得到的zi-1和步驟2得到的si-1以及式(2)推出：

bi-1=zi-1+si-1+bi+127+I(bi+2,bi+10,bi+12,bi+16,bi+17,bi+25,

bi+26,bi+39,bi+47,bi+55,bi+58,bi+60,bi+64,bi+66,bi+67,bi+83,

bi+90,bi+95)

因此，NFSR進行一次逆向反饋移位得到i-1時刻的狀態(tài)Bi-1=(bi-1,bi,…,bi+126)。

利用2.1節(jié)得到的初態(tài)B0和S0，按照步驟1-步驟3的順序依次進行逆推，便可得到i=-256時刻的狀態(tài)S-256=(s-256,s-255,…,s-129)和B-256=(b-256,b-255,…,b-129)。其中NFSR的狀態(tài)B-256就是密鑰K。

我們可以將密鑰恢復攻擊的過程描述如圖3所示。

圖3　密鑰恢復攻擊流程圖

從上面的攻擊算法可以看出，如果攻擊者獲得密鑰流生成器一中間時刻的內部狀態(tài)，就很容易求出對應的密鑰。該攻擊的空間復雜度和計算復雜度分別跟密鑰流生成器的空間復雜度和計算復雜度相同。而密鑰流生成器的空間復雜度和計算復雜度相等，且都等于O(L)，L=256是密鑰流生成器的存儲單元。因此所提出的密鑰恢復攻擊的計算復雜度和空間復雜度都等于O(256)。因為在復雜度方面該攻擊算法與加密算法等價，因此該攻擊算法對Grain-128的安全性造成了很大的威脅。為了抵抗該類攻擊，我們需要對Grain-128的密鑰流生成器進行改進。

3Grain-128算法的改進與安全性分析

在第2節(jié)中已經說明了Grain-128的密鑰流生成器的3個缺陷，密鑰恢復攻擊主要是利用了上述的3個缺陷；進一步分析證明，造成這3個缺陷的主原因是NFSR更新函數式(2)和密鑰流輸出函數式(3)的輸入變量選取不當。針對上述分析，我們對Grain-128的密鑰流生成器做如下兩方面改進。

改進一針對NFSR的更新函數式(2)的輸入變量不當，采用將NFSR的狀態(tài)更新函數式(2)中的項bi與bi+40互換位置，其它項的位置不變，則NFSR的狀態(tài)更新表達式(2)變?yōu)槿缦滦问剑?/p>

bi+128=si+bi+40+bi+26+bi+56+bi+91+bi+17bi+18+

bi+3bi+67+bi+11bi+13+bi+27bi+59+bibi+48+

bi+61bi+65+bi+68bi+84

(4)

改進后的安全性分析:

從上文2.1節(jié)的步驟2和2.2節(jié)的步驟3可以看出，攻擊者利用式(2)中bi的線性參與i+1時刻NFSR的狀態(tài)Bi+1的生成。假如采用這個改進，NFSR的狀態(tài)Bi-1=(bi-1,bi,bi+1,…,bi+126)的最高位的值bi-1和后一狀態(tài)Bi=(bi,bi+1,…,bi+127)的最低位的分量bi+127是非線性關系。在某些情況下即使攻擊者獲得了密鑰流生成器的某一個中間內部狀態(tài)也不能實施上文2.1節(jié)的步驟2和2.2節(jié)的步驟3。下文將對這種情況做進一步說明。

對式(4)中的項簡記成：

bi+128=bif(bi+1,bi+2,…,bi+127)+g(bi+1,bi+2,…,bi+127)

因此，狀態(tài)Bi=(bi,bi=1,…,bi+127)的最低位為：

bi+127=bi-1f(bi,bi+1,…,bi+126)+g(bi,bi+1,…,bi+126)

從上式可以看出，當已知內部狀態(tài)Bi時，也就知道了bi+127和f(·)還有g(·)。如果f(bi,bi+1,…,bi+126)=0，攻擊者即使知道Bi，也不能得到bi-1，因此也就無法實施2.1節(jié)中的步驟2和2.2節(jié)中的步驟3，也就無法得到Bi-1。

因此當發(fā)生f(bi,bi+1,…,bi+126)=0時，即使攻擊者得到密鑰流生成器的內部狀態(tài)Bi，不能獲得bi-1。因為無法實施第2.1節(jié)中的步驟2和2.2節(jié)中的步驟3(這兩個步驟用來獲得bi-1),也就不能得到Bi-1，導致最終攻擊失敗。

改進二針對密鑰流的輸出函數式(3)的輸入變量選取不當，分別用bi替換bi+2，用si替換si+8，其他變量不變。則密鑰流的輸出函數式(3)變成以下形式：

zi=O(bi,bi+12,bi+15,bi+36,bi+45,bi+64,bi+74,bi+89,bi+95,

si,si+13,si+20,si+42,si+60,si+79,si+93,si+95)

即：

zi=bi+bi+15+bi+36+bi+45+bi+64+bi+73+bi+89+

h(bi+12,si,si+13,si+20,bi+95,si+42,si+60,si+79,si+95)

則相對應Bi-1的輸出函數為：

zi-1=bi-1+bi+14+bi+35+bi+44+bi+63+bi+72+bi+88+

h(bi+11,si+7,si-1,si+19,bi+94,si+41,si+59,si+78,si+94)

(5)

改進后的安全性分析：

由式(5)可知，想要實施2.2節(jié)初始化階段攻擊中的步驟1，得到zi-1，當已知內部狀態(tài)Bi和Si時，還需要獲得i-1時刻的LFSR的狀態(tài)Si-1最高位的值si-1和i-1時刻的NFSR的狀態(tài)Bi-1最高位的值bi-1。從2.2節(jié)中的攻擊步驟2可知，獲得si-1的前提是已知zi-1。通過2.2節(jié)中的攻擊步驟3可知，獲得bi-1的前提是已知zi-1和si-1。因此，經過改進后，即使已知密鑰流生成器的某一中間內部狀態(tài)Bi和Si時，因為無法實施2.2節(jié)初始化階段攻擊的步驟1—步驟3，導致最終攻擊失敗。

從攻擊算法可知，我們進行攻擊的步驟是嚴格按照2.1節(jié)和2.2節(jié)中順序執(zhí)行的。由上面進行的分析可知，對Grain-128的密鑰流生成器進行改進后，即使攻擊獲得密鑰流生成器的某一狀態(tài)也不會對密鑰的安全構成威脅。

Grain-128算法有很好的硬件環(huán)境，比如較小的門電路，較低的能量消耗，面積較小的芯片。由于改進后的Grain-128算法并沒有以犧牲硬件為代價來獲得較高的運行速度，沒有改變LFSR和NFSR的數目，也沒有增加門電路。因此改進后的Grain-128算法在沒有增加硬件開銷的情況下，提高了安全性。

4結語

通過深入研究分析流密碼Grain-128的密鑰流生成器工作過程，發(fā)現了密鑰流生成器的3個缺點。雖然只有3個設計缺陷不能實施完整的密鑰恢復攻擊，但是當攻擊者獲得密鑰流生成器的某一中間內部狀態(tài)就可以利用這3個設計缺陷來得到相應的密鑰。為了抵抗這種攻擊，我們對Grain-128進行了改進，改進后能夠抵抗密鑰恢復攻擊。然而其綜合性仍需要我們進行進一步的討論，通過上面的研究可知，Grain-128的設計上還存在缺陷，仍需要對其安全性進行進一步分析。

參考文獻

[1] eSTREAM-ECRYPT stream cipher project[EB/OL].http://www.ecrypt.eu.org/stream/.

[2] 楊昌盛,于敬超,嚴迎建.Grain-128同步流密碼的選擇初始向量相關性能量攻擊[J].計算機應用,2014,34(5):1318-1321,1349.

[3] Hell M,Johansson T,Maximov A.A Stream Cipher Proposal:Grain-128[C]//Information Theory,2006 IEEE International Symposium on,IEEE,2006:1614-1618.

[4] Miodrag J M,Sugata G,Goutam P,et al.Generic Cryptographic Weakness of K-normal Boolean Founctions in Certain Stream Ciphers and Cryptanalysis of Grain-128[J].Periodica Mathematica Hungarica,2012,65(2):205-207.

[5] Dinur I,Shamir A.Breaking Grain-128 with Dynamic Cube Attacks[C]//Proc.16th Conf. Theory and Applicat of Cryptology and Inform SecUrity(ASLACRYPT 2010),Singapore,2010:130-146.

[6] Song H,Fan X,Wu C.Cube attack on Grain[J].Journal of Software,2012,23(1):171-176.

[7] Lee Y,Jeong K,Sung J,et al.Related-Key Chosen IV Attacks on Grain-v1 and Grain-128[M]//Information Security and Privacy,Springer Berlin Heidalberg,2008:321-335.

[8] 賈艷艷.eSTREAM候選算法的安全性研究[D].西安電子科技大學,2012.

[9] Nicolas T,Courtois Willi Meier.Algebraic Attacks on Stream Ci- phers with Linear Feedback[C]//Proc of the International Conference on the Theory and Applications of Cryptographic Techniques B-erlin Spring,2003:345-359.

[10] Biham E,Shamir A.Differential Cryptanalysis of DES-like Cryptosystems[J].Journal of Cryptology,1991,4(1):3-72.

[11] Alex Biryukov,Adi Shamir.Cryptanalytic Time/Memory/Data Tradeoffs for Stream Ciphers[C]//Proc of the 6th International Conference on Theory and Application of Cryptology and Security,Berlin Springer,2000:1-15.

[12] Dinur I,Shamir A.Cube attacks on tweakable black box polynomials[C]//Joux A,ed.Proc.of the EUROCRYPT 2009. LNCS 5479, Heidelberg: Springer-Verlag,2009:278-299.

KEY RECOVERY ATTACK ON STREAM CIPHER GRAIN-128 AND ITS IMPROVEMENT

Tang Yongli1Han Di1Li Zichen1,2

1(SchoolofComputerSciencesandTechnology,HenanPolytechnicUniversity,Jiaozuo454000,Henan,China)2(BeijingElectronicScienceandTechnologyInstitute,Beijing100070,China)

AbstractStream cipher Grain-128 is the key-growth version of Grain v1 algorithm. In order to probe the security of stream cipher Grain-128, we pointed out three design weaknesses of Boolean function in regard to Grain-128 key-stream generator. Based on that, we presented a key recovery attack on the stream cipher Grain-128, which is based on the internal state in key-stream generator. The computational complexity and spatial complexity of attack are all O (254). In order to resist the key recovery attack, we improved the design of Grain-128 key-stream generator. Security analysis showed that the improved stream cipher Grain-128I was able to resist the proposed key recovery attacks.

KeywordsStream cipher Grain-128Key recovery attackKey-stream generatorBoolean function

收稿日期：2014-11-18。國家自然科學基金項目(61370188)；北京市支持中央高校共建項目—青年英才計劃；中央高?；究蒲袠I(yè)務費專項資金資助課題(2014CLJH09)。湯永利，博士，主研領域：密碼學，信息安全。韓娣，碩士生。李子臣，博士。

中圖分類號TP3

文獻標識碼A

DOI:10.3969/j.issn.1000-386x.2016.05.074