流密码Grain-128密钥恢复攻击及改进

汤永利　韩　娣　李子臣,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一种基于密钥流生成器中间内部状态的密钥恢复攻击。该攻击的计算复杂度和空间复杂度都为O(256)。为了抵抗该攻击，对Grain-128密钥流生成器的设计进行了改进。安全性分析表明，改进后的流密码Grain-128能够抵抗所提出的密钥恢复攻击。

关键词流密码Grain-128密钥恢复攻击密钥流生成器布尔函数

0引言

为了加大推进流密码的研究，2004年欧洲启动流密码征集项目eSTREAM工程[1]。主要目的是收集安全快速的流密码算法，eSTREAM工程一共收集了34个序列密码算法。经过连续3个阶段的连续评选，选出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]提出利用动态立方攻击(Dynamic Cube Attack)对Grain-128进行安全性分析；在文献[7]中，Lee等人提出Grain v1和Grain-128的相关密钥选择IV攻击。

在对流密码进行安全性分析时，经常会用到密钥恢复攻击。密钥恢复攻击就是利用某种方法获得密钥流生成器(KG)在某个时刻的内部状态，即密钥流产生过程中的内部存储单元(如记忆单元、线性及非线性移位寄存器等)中的值。攻击者就是利用密钥流生成器的设计缺陷和一个已知的内部状态来获得密钥[8]。

本文在对流密码Grain-128工作原理分析时，发现其密钥流生成器的3个函数(初始化函数、状态转换函数、密钥流生成函数)存在设计缺陷。利用这3个设计缺陷给出了流密码Grain-128一种基于密钥流生成器某一时刻中间内部状态的密钥恢复攻击。为了进一步提高流密码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相应的状态更新函数为：

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相应的状态更新函数为：

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)的某个时刻的中间内部状态。因此我们可以利用某个已知的中间内部状态和密钥流生成器来推断密钥。

在攻击假设条件下，攻击者已经知道密钥流生成器在某一时刻的中间内部状态，即攻击者已知i=t(t>0)时刻时的Bt=(bt,bt+1,…,bt+127)和St=(st,st+1,…,st+127)。通过观察Grain-128的密钥流生成器的工作过程，可以发现密钥流生成器有以下几个设计缺点[13]：

(1) 密钥流生成阶段和初始化阶段的状态转换函数很相似。

(2) LFSR及NFSR状态Si和Bi最高位的值si、bi在密钥流生成阶段和密钥初始化阶段线性参与下一个状态Si+1、Bi+1的产生。

(3) 第i拍密钥流输出函数值zi与LFSR及NFSR内部状态最高位的值si、bi无关。

由于密钥流生成器存在上述缺陷，我们可以进行下面的攻击过程：首先，对密钥流生成阶段进行攻击，利用LFSR和NFSR在这个阶段的状态转换函数进行逆向推理，求出该阶段的初始状态S0及B0；然后，对密钥初始化阶段进行攻击，利用LFSR和NFSR在这个阶段的状态转换函数进行逆向推理，求出该阶段的初始状态B-256和S-256，其中NFSR的初态B-256就是我们需要求出的密钥。因此对Grain-128算法具体的密钥恢复攻击过程如下。

2.1密钥流生成阶段的攻击

根据密钥流生成阶段(i>0)LFSR及NFSR的状态转换关系逆向递推出S0和B0，攻击过程如下：

步骤1对LFSR的状态更新关系表达式(1)进行逆向递推得到i-1时刻的状态Si-1最高位的值si-1:

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

LFSR进行逆向反馈移位之后的状态Si-1=(si-1,si,…,si+126)。

步骤2对NFSR的更新关系表达式(2)进行逆向递推得到i-1时刻状态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进行逆向反馈移位后的状态：

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

由前面的密钥恢复攻击假设可知，当攻击者知道密钥流生成器在某一时刻的状态Bt、St时，按照步骤1和步骤2的顺序进行逆向递推，直到i=0时，即可得到密钥流生成阶段的初始状态B0=(b0,b1,…,b127),S0=(s0,s1,…,s127)。

2.2初始化阶段的攻击

利用2.1节求出的密钥流生成阶段的初始状态B0和S0，然后对该阶段的状态转换函数做逆向递推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的状态Si-1最高位si-1：

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

因此，LFSR进行一次逆向反馈移位后得到i-1时刻的状态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时刻的状态Bi-1=(bi-1,bi,…,bi+126)。

利用2.1节得到的初态B0和S0，按照步骤1-步骤3的顺序依次进行逆推，便可得到i=-256时刻的状态S-256=(s-256,s-255,…,s-129)和B-256=(b-256,b-255,…,b-129)。其中NFSR的状态B-256就是密钥K。

我们可以将密钥恢复攻击的过程描述如图3所示。

图3　密钥恢复攻击流程图

从上面的攻击算法可以看出，如果攻击者获得密钥流生成器一中间时刻的内部状态，就很容易求出对应的密钥。该攻击的空间复杂度和计算复杂度分别跟密钥流生成器的空间复杂度和计算复杂度相同。而密钥流生成器的空间复杂度和计算复杂度相等，且都等于O(L)，L=256是密钥流生成器的存储单元。因此所提出的密钥恢复攻击的计算复杂度和空间复杂度都等于O(256)。因为在复杂度方面该攻击算法与加密算法等价，因此该攻击算法对Grain-128的安全性造成了很大的威胁。为了抵抗该类攻击，我们需要对Grain-128的密钥流生成器进行改进。

3Grain-128算法的改进与安全性分析

在第2节中已经说明了Grain-128的密钥流生成器的3个缺陷，密钥恢复攻击主要是利用了上述的3个缺陷；进一步分析证明，造成这3个缺陷的主原因是NFSR更新函数式(2)和密钥流输出函数式(3)的输入变量选取不当。针对上述分析，我们对Grain-128的密钥流生成器做如下两方面改进。

改进一针对NFSR的更新函数式(2)的输入变量不当，采用将NFSR的状态更新函数式(2)中的项bi与bi+40互换位置，其它项的位置不变，则NFSR的状态更新表达式(2)变为如下形式：

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节的步骤2和2.2节的步骤3可以看出，攻击者利用式(2)中bi的线性参与i+1时刻NFSR的状态Bi+1的生成。假如采用这个改进，NFSR的状态Bi-1=(bi-1,bi,bi+1,…,bi+126)的最高位的值bi-1和后一状态Bi=(bi,bi+1,…,bi+127)的最低位的分量bi+127是非线性关系。在某些情况下即使攻击者获得了密钥流生成器的某一个中间内部状态也不能实施上文2.1节的步骤2和2.2节的步骤3。下文将对这种情况做进一步说明。

对式(4)中的项简记成：

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

因此，状态Bi=(bi,bi=1,…,bi+127)的最低位为：

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

从上式可以看出，当已知内部状态Bi时，也就知道了bi+127和f(·)还有g(·)。如果f(bi,bi+1,…,bi+126)=0，攻击者即使知道Bi，也不能得到bi-1，因此也就无法实施2.1节中的步骤2和2.2节中的步骤3，也就无法得到Bi-1。

因此当发生f(bi,bi+1,…,bi+126)=0时，即使攻击者得到密钥流生成器的内部状态Bi，不能获得bi-1。因为无法实施第2.1节中的步骤2和2.2节中的步骤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节初始化阶段攻击中的步骤1，得到zi-1，当已知内部状态Bi和Si时，还需要获得i-1时刻的LFSR的状态Si-1最高位的值si-1和i-1时刻的NFSR的状态Bi-1最高位的值bi-1。从2.2节中的攻击步骤2可知，获得si-1的前提是已知zi-1。通过2.2节中的攻击步骤3可知，获得bi-1的前提是已知zi-1和si-1。因此，经过改进后，即使已知密钥流生成器的某一中间内部状态Bi和Si时，因为无法实施2.2节初始化阶段攻击的步骤1—步骤3，导致最终攻击失败。

从攻击算法可知，我们进行攻击的步骤是严格按照2.1节和2.2节中顺序执行的。由上面进行的分析可知，对Grain-128的密钥流生成器进行改进后，即使攻击获得密钥流生成器的某一状态也不会对密钥的安全构成威胁。

Grain-128算法有很好的硬件环境，比如较小的门电路，较低的能量消耗，面积较小的芯片。由于改进后的Grain-128算法并没有以牺牲硬件为代价来获得较高的运行速度，没有改变LFSR和NFSR的数目，也没有增加门电路。因此改进后的Grain-128算法在没有增加硬件开销的情况下，提高了安全性。

4结语

通过深入研究分析流密码Grain-128的密钥流生成器工作过程，发现了密钥流生成器的3个缺点。虽然只有3个设计缺陷不能实施完整的密钥恢复攻击，但是当攻击者获得密钥流生成器的某一中间内部状态就可以利用这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)；北京市支持中央高校共建项目—青年英才计划；中央高校基本科研业务费专项资金资助课题(2014CLJH09)。汤永利，博士，主研领域：密码学，信息安全。韩娣，硕士生。李子臣，博士。

中图分类号TP3

文献标识码A

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