流密码算法Grain的安全性研究
|
摘要
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~(43)次计算、2~(42)比特的内存和2~(38)比特的密钥流，并且对Grain算法的设计提出了一些建议，且后续参加了Grain-128算法的设计。
基于Grain的现有研究成果，本文主要对如下方面进行了讨论。通过分析流密码算法Grain v1，提出了一种针对密钥流生成器的差分错误攻击。该攻击利用了前17轮密钥流次数较低的弱点，向LFSR的指定位置引入错误，通过差分得到17个线性无关的线性方程和80个内部状态信息，只需要62bits的初始内部状态变量就可得到密钥种子。整个过程的计算复杂度为(?)2~(74.26)。
结果表明，Grain v1抗差分错误攻击的计算复杂度低于设计者宣称的(?)2~(80)，也就是说，算法存在安全漏洞。
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~(43) computation and 2~(42) bits memory and 2~(38) 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~(80)).
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~(43)次计算、2~(42)比特的内存和2~(38)比特的密钥流，并且对Grain算法的设计提出了一些建议，且后续参加了Grain-128算法的设计。
基于Grain的现有研究成果，本文主要对如下方面进行了讨论。通过分析流密码算法Grain v1，提出了一种针对密钥流生成器的差分错误攻击。该攻击利用了前17轮密钥流次数较低的弱点，向LFSR的指定位置引入错误，通过差分得到17个线性无关的线性方程和80个内部状态信息，只需要62bits的初始内部状态变量就可得到密钥种子。整个过程的计算复杂度为(?)2~(74.26)。
结果表明，Grain v1抗差分错误攻击的计算复杂度低于设计者宣称的(?)2~(80)，也就是说，算法存在安全漏洞。
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~(43) computation and 2~(42) bits memory and 2~(38) 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~(80)).
引文
[1]C.E.Shannon. A Mathematical Theory of Communication, Bell SystemTechnical Journal,27(1948),Part 1,479-523.
[2]W. Difie, M.E.Hellman. New Direction in Cryptography, IEEE Transaction onInformation Thery,1976,Vol.IT22,No.6,pp.644-654.
[3]NBS.Data Encryption Standard, FIPS PUB 46.National Bureau of Standards,Washington,D.C,Jan,1977.
[4]R.L.Rivest, A.Shamir, and L.Adleman, A Method for Obtaining DigitalSignatures and Public-Key Cryptosystems, Comm. Of the ACM(Feb. 1978), 120-126
[5]National Institute of Standards and Technology (NIST), USA, AdvancedEncryption Standards (AES), FIPS-197, 2001.
[6]丁存生，肖国镇.流密码学及其应用.北京：国防工业出版社，1994.
[7]章照止.现代密码学基础.北京：北京邮电大学出版社，2004.
[8]冯登国.频谱理论及其在密码学中应用.北京：科学出版社，2000.
[9]R.A.Rueppel. Linear Complexity and Random Sequesces. Advances inCryptology-EUROCRYPT85(LNS219),1986,pp.167-188.
[10]冯登国.布尔函数的相关免疫阶和非线性度之间的关系.信息安全与通信保密，1994年03期.
[11]N.Courtois, W.Meier. Algebraic Attacks on Stream Ciphers with LinearFeedback. Advance in Cryptology Eurocrypt 2003, LNCS 2656. Berlin:Springer-Verlag,2003:345-359.
[12]N.Courtois. Fast algebraic attack on stream ciphers with linear feedback.Advances in Cryptology-Crypto 2003, LNCS 2729, Springer-Verlag, 2003. 176-194.
[13]A.Mohammad, R.Mirghadri. A Distinguish attack on COSvd Cipher, WorldAcademy of Science, Engineering and Technology,11,2005.
[14]Jin Hong and Palash Sarkar, Rediscovery of the Time Memory Tradeoff,Cryptology ePrint Archive, Report 2005/090, 2005.
[15]Rechberger, Oswald. Stream Ciphers and Side-Channel Analysis. In:SASC2004-The State of the Art of Stream Ciphers, Workshop Record, pp 320-326(2004),http//www.ecrypt.eu.org/stream.
[16]E.J.Groth. Generation of Binary Sequences with Controllable Complexity.IEEE Trans. On Inform. Th., 1971.
[17]罗启彬，张健.流密码的现状和发展.信息与电子工程，2006，Vo1.4,No.1.
[18]Thiegenthaler T, Decrypting a class of stream ciphers using ciphertext only1985(01).
[19]eSTREAM: ECRYPT Stream Cipher Project, IST-2002-507932. Available athttp//www.ecrypt.eu.org/stream.
[20]M.Hell, T.Johansson, W.Meier. Grain–a stream cipher for constrainedenvironments. International Journal of Wireless and Mobile Computing, Special Issueon Security of Computer Network and Mobile Systems, 2006.
[21]Hell, M., Johansson, T., Maximov, A., Meier, W. A Stream Cipher Proposal:Grain-128. In: ISIT 2006, 2006.
[22]S. Khazaei, M. Hassanzadeh and M. Kiaei. Distinguishing Attack on Grain,post on eSTREAM webpage. www.ecrypt.eu.org/stream/, 2005.
[23]A. Maximov. Cryptanalysis of the“Grain”family of Stream Ciphers, draft.Private communication, 2005.
[24]Biham E, Shamir A. Differential cryptanalysis of DES-like cryptosystems [A].Advances in Cryptology-CRYPTO’90 Proceedings [C]. Springer-Verlag, 1991. 2-21.
[25]Biham E, Shamir A. Differential Cryptanalysis of the Data EncryptionStandard [M]. Spring-Verlag, 1993.
[26]李超，黄建忠，项攀攀.差分分析在序列密码攻击中的应用.应用科学学报，2004，Vol.22，No.2.
[27]Johannes Bl?mer, Jean-Pierre Seifert, Fault Based Cryptanalysis ofthe Advanced Encryption Standard, Springer, Lecture Notes in ComputerScience,2003,vo1.2742，PP.162—181
[28]Boneh, DeMillo, and Lipton, On th Importance of Checking CryptographicProtocols for Faults, Advances in Cryptology, proceedings of EUROCRYPT’97,Lecture Notes in Computer Science, 1997, vol.1294, pp.37-51.
[29]E.Biham and A.Shamir, Differential Fault Analysis of Secret KeyCryptosystems, Lecture Notes in Computer Science, 1997, vol.1294, pp.513-525.
[30]J.J.Hoch and A.shamir, Fault analysis of Stream Cipher, Lectures Notes inComputer Science, 1997, vol.3156, pp.240-253.
[31]杜育松.对几种分组密码体制的基于错误的密码分析.广州大学.2007.
[32]仵丽花.一种新型流密码结构的区分攻击研究.西安电子科技大学.2008.
[33]杨文峰，胡予濮，高军涛.流密码Grain v1的密钥恢复攻击及其改进.西南交通大学学报.2010，vol.45，No.5.
[2]W. Difie, M.E.Hellman. New Direction in Cryptography, IEEE Transaction onInformation Thery,1976,Vol.IT22,No.6,pp.644-654.
[3]NBS.Data Encryption Standard, FIPS PUB 46.National Bureau of Standards,Washington,D.C,Jan,1977.
[4]R.L.Rivest, A.Shamir, and L.Adleman, A Method for Obtaining DigitalSignatures and Public-Key Cryptosystems, Comm. Of the ACM(Feb. 1978), 120-126
[5]National Institute of Standards and Technology (NIST), USA, AdvancedEncryption Standards (AES), FIPS-197, 2001.
[6]丁存生，肖国镇.流密码学及其应用.北京：国防工业出版社，1994.
[7]章照止.现代密码学基础.北京：北京邮电大学出版社，2004.
[8]冯登国.频谱理论及其在密码学中应用.北京：科学出版社，2000.
[9]R.A.Rueppel. Linear Complexity and Random Sequesces. Advances inCryptology-EUROCRYPT85(LNS219),1986,pp.167-188.
[10]冯登国.布尔函数的相关免疫阶和非线性度之间的关系.信息安全与通信保密，1994年03期.
[11]N.Courtois, W.Meier. Algebraic Attacks on Stream Ciphers with LinearFeedback. Advance in Cryptology Eurocrypt 2003, LNCS 2656. Berlin:Springer-Verlag,2003:345-359.
[12]N.Courtois. Fast algebraic attack on stream ciphers with linear feedback.Advances in Cryptology-Crypto 2003, LNCS 2729, Springer-Verlag, 2003. 176-194.
[13]A.Mohammad, R.Mirghadri. A Distinguish attack on COSvd Cipher, WorldAcademy of Science, Engineering and Technology,11,2005.
[14]Jin Hong and Palash Sarkar, Rediscovery of the Time Memory Tradeoff,Cryptology ePrint Archive, Report 2005/090, 2005.
[15]Rechberger, Oswald. Stream Ciphers and Side-Channel Analysis. In:SASC2004-The State of the Art of Stream Ciphers, Workshop Record, pp 320-326(2004),http//www.ecrypt.eu.org/stream.
[16]E.J.Groth. Generation of Binary Sequences with Controllable Complexity.IEEE Trans. On Inform. Th., 1971.
[17]罗启彬，张健.流密码的现状和发展.信息与电子工程，2006，Vo1.4,No.1.
[18]Thiegenthaler T, Decrypting a class of stream ciphers using ciphertext only1985(01).
[19]eSTREAM: ECRYPT Stream Cipher Project, IST-2002-507932. Available athttp//www.ecrypt.eu.org/stream.
[20]M.Hell, T.Johansson, W.Meier. Grain–a stream cipher for constrainedenvironments. International Journal of Wireless and Mobile Computing, Special Issueon Security of Computer Network and Mobile Systems, 2006.
[21]Hell, M., Johansson, T., Maximov, A., Meier, W. A Stream Cipher Proposal:Grain-128. In: ISIT 2006, 2006.
[22]S. Khazaei, M. Hassanzadeh and M. Kiaei. Distinguishing Attack on Grain,post on eSTREAM webpage. www.ecrypt.eu.org/stream/, 2005.
[23]A. Maximov. Cryptanalysis of the“Grain”family of Stream Ciphers, draft.Private communication, 2005.
[24]Biham E, Shamir A. Differential cryptanalysis of DES-like cryptosystems [A].Advances in Cryptology-CRYPTO’90 Proceedings [C]. Springer-Verlag, 1991. 2-21.
[25]Biham E, Shamir A. Differential Cryptanalysis of the Data EncryptionStandard [M]. Spring-Verlag, 1993.
[26]李超，黄建忠，项攀攀.差分分析在序列密码攻击中的应用.应用科学学报，2004，Vol.22，No.2.
[27]Johannes Bl?mer, Jean-Pierre Seifert, Fault Based Cryptanalysis ofthe Advanced Encryption Standard, Springer, Lecture Notes in ComputerScience,2003,vo1.2742，PP.162—181
[28]Boneh, DeMillo, and Lipton, On th Importance of Checking CryptographicProtocols for Faults, Advances in Cryptology, proceedings of EUROCRYPT’97,Lecture Notes in Computer Science, 1997, vol.1294, pp.37-51.
[29]E.Biham and A.Shamir, Differential Fault Analysis of Secret KeyCryptosystems, Lecture Notes in Computer Science, 1997, vol.1294, pp.513-525.
[30]J.J.Hoch and A.shamir, Fault analysis of Stream Cipher, Lectures Notes inComputer Science, 1997, vol.3156, pp.240-253.
[31]杜育松.对几种分组密码体制的基于错误的密码分析.广州大学.2007.
[32]仵丽花.一种新型流密码结构的区分攻击研究.西安电子科技大学.2008.
[33]杨文峰，胡予濮，高军涛.流密码Grain v1的密钥恢复攻击及其改进.西南交通大学学报.2010，vol.45，No.5.