【作者】 王璐；

【导师】 胡予濮；

【作者基本信息】 西安电子科技大学 ， 信息安全， 2011， 硕士

【摘要】 Grain算法作为eSTREAM计划的最终候选算法之一，是由瑞典学者M.Hell、T.Johansson和W.Meier共同提交的面向硬件实现的二进制同步流密码。由于其硬件实现简单，且单位时钟输出地密钥量可以调节等优点，Grain受到了密码学界的广泛关注。Grain算法共有三个版本：Grain v0、Grain v1和Grain-128，三个版本结构基本相同，其中Grain v0和Grain v1的LFSR和NFSR均为80位，内部状态变量为160位；Grain-128的LFSR和NFSR均为80位，其内部状态变量为256位。Grainv0算法提出后，许多学者对其进行了深入研究。S. Khazaei、M. Hassanzadeh和M.Kiaei利用线性时序电路逼近方法，找到了一个相关系数约为2^-63.7的关于连续密钥流比特的线性函数，从而构造了一个区分攻击，在（?）2^61.4比特密钥流和复杂度的情况下，成功地将密钥流序列与真正的随机序列进行了区分。A. Maximov对Grain v0进行了密钥恢复攻击，该攻击仅需要2⁴³次计算、2⁴²比特的内存和2³⁸比特的密钥流，并且对Grain算法的设计提出了一些建议，且后续参加了Grain-128算法的设计。基于Grain的现有研究成果，本文主要对如下方面进行了讨论。通过分析流密码算法Grain v1，提出了一种针对密钥流生成器的差分错误攻击。该攻击利用了前17轮密钥流次数较低的弱点，向LFSR的指定位置引入错误，通过差分得到17个线性无关的线性方程和80个内部状态信息，只需要62bits的初始内部状态变量就可得到密钥种子。整个过程的计算复杂度为（?）2^74.26。结果表明，Grain v1抗差分错误攻击的计算复杂度低于设计者宣称的（?）2⁸⁰，也就是说，算法存在安全漏洞。更多还原

【Abstract】 Grain is one of the final winner algorithms in the project of E-STREAM whichwas designed by M. Hell , T. Johansson and W. Meier. Grain is designed for hardwareimplementation of binary synchronous stream cipher. As the algorithm is designed tobe simple and the adjustable key quantity, Grain has widely concerned in cryptography.Grain has three versions：Grain v0, Grain v1 and Grain-128.These constructionsare basically similar to each other. In Grain v0 and Grain v1,both shift registers are 80bits in sizes, and the internal state variable are 160 bits. In Grain-128, both shiftregisters are 128 bits in sizes, and the internal state variable are 256 bits respectively.After Grain v0 was submitted, many scholars have conducted the deep research to it.By the approach of linear sequence circuit, S.Khazaei, M. Hassanzadeh and M. Kiaeifind a linear function whose correlation is about 2^-63.7 . Then they make a distinguishattack. A.Maximov presented a key recovery attack of Grain v0. The attack needs only2⁴³ computation and 2⁴² bits memory and 2³⁸ bits keystream. A.Maximov made greatadvice to the design of Grain, and then he joined the design of Grain-128.On the basis of existing research result, this paper is discussed on the followingaspects.By analyzing the weakness in design of the stream cipher Grain-v1, adifferential fault attack is presented. The attack makes use of the weakness that the keystream equations in the first 17 times have comparatively low orders. The attackerneeds to inject faults to the specified positions of LFSR at the stage of generating keystream. By differentiating, the attacker is able to acquire 17 linear equations which arelinear independent and 80 initial states of the stream cipher directly. The attacker justneeds to guess 62bits internal states, and then all the internal state can be achieved. Theproposed attack algorithm can reduce the complexity to O(2^74.26).The result shows that the algorithm which has been analyzed exists securityvulnerabilities, and the computational complexity of attacks is lower than that thedesigners claimed O(2⁸⁰).更多还原