流密码算法Trivium的安全性研究
摘要
Trivium作为一种基于硬件的流密码算法,是欧洲流密码工程eSTREAM的最终胜选算法之一,它是由Christophe De Canniere和Bart Preneel提出的,由于其设计简单优美,受到很多人的青睐,因此,有很多专家学者对Trivium的安全性做了分析。
本文对Trivium的安全性进行分析,分析了Trivium的生成密钥方程,通过选择差分和猜测确定攻击的方法,求解这个非线性多变量方程组,从而求解出其余的内部状态,达到破解Trivium的目的。
本文在综述已有的安全性分析的基础上,取得了如下新的分析结果:
首先进行错误注入,即改变内部状态的某特定52比特,生成错误密钥流,再和原始密钥流进行差分,获得了内部状态的若干额外的低次方程。然后猜测内部状态的某45比特,就可以通过使用高斯消元法求解线性方程组,得出其余的243比特,从而破解Trivium,总的复杂度约为266.8。
Trivium as a hardware-oriented stream cipher was designed by Christophe De Canniere and Bart Preneel, which is one of the final winners of the European stream project eSTREAM. Because of its simple and elegant structure, it has attached a lot of interest. There have been a lot of experts and scholars to analyze and research its security.
In this paper we analyze the Trivium’s key stream generation algorithm and its key stream generation equations, then through guess and determine attack based on chosen differential attack, we can solve nonlinear multivariate equations and get remaining bits of internal state so as to break Trivium.
In this paper some new analyses are proposed as follows based on the summary of available analyses of the security of Trivium.
Firstly, make use of fault injections, i.e. alter special 52 bits of internal state to generate the faulty key stream; Secondly, compute the difference between the faulty key stream and the original key stream to get many extra equations with low degree of internal state; Finally, 45 bits of internal state are guessed to get remaining 243 bits by using the method of Gaussian elimination for solving the linear equations so as to break Trivium. The total complexity is about 266.8.
本文对Trivium的安全性进行分析,分析了Trivium的生成密钥方程,通过选择差分和猜测确定攻击的方法,求解这个非线性多变量方程组,从而求解出其余的内部状态,达到破解Trivium的目的。
本文在综述已有的安全性分析的基础上,取得了如下新的分析结果:
首先进行错误注入,即改变内部状态的某特定52比特,生成错误密钥流,再和原始密钥流进行差分,获得了内部状态的若干额外的低次方程。然后猜测内部状态的某45比特,就可以通过使用高斯消元法求解线性方程组,得出其余的243比特,从而破解Trivium,总的复杂度约为266.8。
Trivium as a hardware-oriented stream cipher was designed by Christophe De Canniere and Bart Preneel, which is one of the final winners of the European stream project eSTREAM. Because of its simple and elegant structure, it has attached a lot of interest. There have been a lot of experts and scholars to analyze and research its security.
In this paper we analyze the Trivium’s key stream generation algorithm and its key stream generation equations, then through guess and determine attack based on chosen differential attack, we can solve nonlinear multivariate equations and get remaining bits of internal state so as to break Trivium.
In this paper some new analyses are proposed as follows based on the summary of available analyses of the security of Trivium.
Firstly, make use of fault injections, i.e. alter special 52 bits of internal state to generate the faulty key stream; Secondly, compute the difference between the faulty key stream and the original key stream to get many extra equations with low degree of internal state; Finally, 45 bits of internal state are guessed to get remaining 243 bits by using the method of Gaussian elimination for solving the linear equations so as to break Trivium. The total complexity is about 266.8.
引文
[1] Bruce Schneier. Applied cryptography: protocols, algorithms, and source code in C. 2nd ed. New York : Wiley, 1996.
[2] J. D. Golic. Cryptanalysis of Alleged A5 Stream Cipher. Advances in Cryptology- EUROCRYPT’97. LNCS. 1997. Volume 1233. pp239-255.
[3] eSTREAM: ECRYPT Stream Cipher Project, IST-2002-507932 (2005) (accessed September 29, 2005), http://www.ecrypt.eu.org/stream/.
[4] Wu Hongjun. The Stream Cipher HC-128. New Stream Cipher Designs. LNCS. 2008.Volume 4986, pp39-47.
[5] Martin Boesgaard, Mette Vesterager and Thomas Christensen. etc. The Stream Cipher Rabbit. New Stream Cipher Designs. LNCS. 2008.Volume 4986, pp69-83
[6] Daniel J. Bernstein. The Salsa20 Family of Stream Ciphers. New Stream Cipher Designs. LNCS. 2008. Volume 4986. pp84-97.
[7] C. Berbain, O. Billet1, A. Canteaut. etc. Sosemanuk, a fast software-oriented stream cipher. New Stream Cipher Designs. LNCS, 2008.Volume 4986, pp98-118.
[8] Martin Hell1, Thomas Johansson, Alexander Maximov. etc. The Grain Family of Stream Ciphers. New Stream Cipher Designs.LNCS. 2008.Volume 4986. pp179-190
[9] Martin Hell1, Thomas Johansson1 and Willi Meier. Grain - A Stream Cipher for Constrained Environments. http://www.ecrypt.eu.org/stream/p3ciphers/grain/Grain_p3.pdf.
[10] Steve Babbage and Matthew Dodd. The MICKEY Stream Ciphers. New Stream Cipher Designs. LNCS. 2008. Volume 4986. pp191-209.
[11] Steve Babbage and Matthew Dodd. The stream cipher MICKEY-128 v2.0. http://www.ecrypt.eu.org/stream/p3ciphers/mickey/mickey128_p3.pdf.
[12] C. De Canniere, B. Preneel. TRIVIUM– a stream cipher construction inspired by block cipher design principles. http://www.ecrypt.eu.org/stream/papersdir/2006/021.pdf.
[13] Havard Raddum. Cryptanalytic Results on Trivium. Cryptology ePrint Archive. Report 2006/039. http://eprint.iacr.org/2006/039.ps.
[14]Tian Yun,Chen Gongliang and Li jianhua. On the Design of Trivium. Crytology eprint Archive 2009/431. http://eprint.iacr.org/2009/431.pdf.
[15] S. Khazaei. Re: A reformulation of TRIVIUM. Posted on the eSTREAM Forum(2006),http://www.ecrypt.eu.org/stream/phorum/read.php?1,448.
[16] Deike Priemuth-Schmid and Alex Biryukov. Slid Pairs in Salsa20 and TRIVIUM [C]. Progress in Cryptology - INDOCRYPT 2008, LNCS, 2008.Volume 5365.pp1-14.
[17] Enes Pasalic. Key differentiation attacks on stream ciphers. Cryptology ePrint Archive, Report 2008/443. http://eprint.iacr.org/.
[18]丁存生,肖国镇.流密码学及其应用[M].北京:国防工业出版社.1994.
[19]胡予濮,张玉清,肖国镇.对称密码学[M].北京:机械工业出版社.2002. pp64~80
[20] C.De Cannière and Bart Preneel. Trivium Specifications. www.ecrypt.eu.org/stream/p3ciphers/trivium/trivium_p3.pdf.
[21]冯登国.密码分析学.北京:清华大学出版社. pp15-38.
[22]E. Biham, A. Biryukov, A. Shamir. Cryptanalysis of skipjack reduced to 31 rounds using impossible differentials. Journal of Cryptology. 2005, 09, Volume 18(4) . pp291-311.
[23]吴文玲.张蕾.不可能差分密码分析研究进展.系统科学与数学.2008, 08, 28(8). pp971-983.
[24]李超,黄建忠和项攀攀.差分分析在序列密码攻击中的应用.应用科学学报.2004,06, 22(2).pp127-131.
[25] S.Babbage. Some Thoughts on Trivium. eSTREAM, ECRYPT Stream Cipher Project, Report 2007/007 (2007), http://www.ecrypt.eu.org/stream.
[26] Shahram Khazaei and Mehdi Hassanzadeh. Linear Sequential Circuit Approximation of the TRIVIUM Stream Cipher. Cryptology ePrint Archive, http://www.ecrypt.eu.org/stream/papersdir/063.pdf.
[27] Alexander Maximov and Alex Biryukov. Two Trivial Attacks on TRIVIUM. Selected Areas in Cryptography. LNCS. Selected Areas in Cryptography. 2007, Volume 4876. pp36-55.
[28] W. Fisher, B.M. Gammel, O. Kniffler, etc. Differential power analysis of stream ciphers. eSTREAM, ECRYPT Stream Cipher Project, Report 2007/014 (2007),http://www.ecrypt.eu.org/stream.
[29] P. C. Kocher, J. Jaffe, and B. Jun. Differential Power Analysis. Advances in Cryptology– CRYPTO’99, Lecture Notes in Computer Science, 1999.vol. 1666, pp388-397.
[30] J.J. Hoch, Shamir. Fault Analysis of Stream Ciphers. CHES 2004. LNCS, 2004. vol. 3156. pp1-20.
[31] Sergei SKorobogatov and Ross Anderson. Optical Fault Induction attack. ches2002 http://www.cl.cam.ac.uk/~rja14/Papers/faultpap3.pdf.
[32] Boneh, Demillo and Lipton. On the Importance of Checking Cryptographic Protocols for Faults, http://dsns.csie.nctu.edu.tw/research/crypto/HTML/PDF/E97/37.PDF.
[33] Biham, Shamir. Differential Fault Analysis of Secret Key Cryptosystems. Cryptology - CRYPT0 '97, LNCS .1997.Volume 1294. pp513-525.
[34] J.Hoch Jonathan and Adi Shamir. Fault analysis of stream ciphers. M. Joye, J.-J. Quisquater (eds.) CHES 2004. LNCS, 2004.vol. 3156. pp240-253.
[35] M. Hojsik, B. Rudolf. Differential fault analysis of Trivium. K. Nyberg (ed.) FSE 2008. LNCS. 2008. vol. 5086. pp158-172.
[36] M.S.Turan, O. Kara. Linear Approximations for 2-round Trivium. eSTREAM, ECRYPT Stream Cipher Project, Report 2007/008 (2007).
[37] E. Biham, O.Dunkelman. Differential Cryptanalysis in Stream Ciphers. COSIC internal report (2007). pp1-22. http://www.cosic.esat.kuleuven.be/publications/article-935.pdf.
[38]Simon Fischer, S. Khazaei and Willi Meier. Chosen IV Statistical Analysis for Key Recovery Attacks on Stream Ciphers. Progress in Cryptology– AFRICACRYPT 2008. LNCS 2008.Volume 5023. pp236-245.
[39] H. Englund, T. Johansson, M.S. Turan. A Framework for Chosen IV Statistical Analysis of Stream Ciphers. In: Srinathan, K., Rangan, C.P., Yung, M. (eds.) INDOCRYPT 2007. LNCS. 2007. vol. 4859. pp268-281.
[40] T. Cover, J.A.Thomas. Elements of Information Theory. 2nd. Hoboken, N.J. : Wiley-Interscience. 2006.
[41] J. Aumasson, S. Fischer and S. Khazaei. Etc. New Features of Latin Dances: Analysis of Salsa, ChaCha, and Rumba. FSE 2008 (2008). LNCS.2008. Volume 5086. pp470-488.
[42] Jean-Philippe Aumasson, Itai Dinur, and Adi Shamir. Cube Testers and Key Recovery Attacks on Reduced-Round MD6 and Trivium. Fast Software Encryption. LNCS. 2009. Volume 5665. pp1-12.
[43] S. S. Bedi and N. Rajesh Pillai. Cube Attacks on Trivium. Cryptology ePrint Archive, Report 2009/015. http://eprint.iacr.org/2009/015.pdf.
[44] Itai Dinur and Adi Shamir. Side Channel Cube Attacks on Block Ciphers. Cryptology ePrint Archive, Report 2009/127. http://eprint.iacr.org/2009/127.pdf
[45] Itai Dinur and Adi Shamir. Cube Attacks on Tweakable Black Box Polynomials.Cryptology ePrint Archive, Report 2008/385. http://eprint.iacr.org/2008/385.pdf.
[46] Michal Hojsík and Bohuslav Rudolf . Floating Fault Analysis of Trivium. Progress in Cryptology - INDOCRYPT 2008. LNCS. 2008.Volume 5365. pp239-250.
[47] Hu Yupu and Gao Juntao and Liu Qing. Floating Fault Analysis of Trivium under Weaker Assumptions1.Cryptology ePrint Archive, Report 2009/169. http://eprint.iacr.org/2009/169.pdf.
[48] Yupu Hu and Fengrong Zhang and Yiwei Zhang. Hard Fault Analysis of Trivium .Cryptology ePrint Archive, Report 2009/333. http://eprint.iacr.org/2009/333.pdf.
[2] J. D. Golic. Cryptanalysis of Alleged A5 Stream Cipher. Advances in Cryptology- EUROCRYPT’97. LNCS. 1997. Volume 1233. pp239-255.
[3] eSTREAM: ECRYPT Stream Cipher Project, IST-2002-507932 (2005) (accessed September 29, 2005), http://www.ecrypt.eu.org/stream/.
[4] Wu Hongjun. The Stream Cipher HC-128. New Stream Cipher Designs. LNCS. 2008.Volume 4986, pp39-47.
[5] Martin Boesgaard, Mette Vesterager and Thomas Christensen. etc. The Stream Cipher Rabbit. New Stream Cipher Designs. LNCS. 2008.Volume 4986, pp69-83
[6] Daniel J. Bernstein. The Salsa20 Family of Stream Ciphers. New Stream Cipher Designs. LNCS. 2008. Volume 4986. pp84-97.
[7] C. Berbain, O. Billet1, A. Canteaut. etc. Sosemanuk, a fast software-oriented stream cipher. New Stream Cipher Designs. LNCS, 2008.Volume 4986, pp98-118.
[8] Martin Hell1, Thomas Johansson, Alexander Maximov. etc. The Grain Family of Stream Ciphers. New Stream Cipher Designs.LNCS. 2008.Volume 4986. pp179-190
[9] Martin Hell1, Thomas Johansson1 and Willi Meier. Grain - A Stream Cipher for Constrained Environments. http://www.ecrypt.eu.org/stream/p3ciphers/grain/Grain_p3.pdf.
[10] Steve Babbage and Matthew Dodd. The MICKEY Stream Ciphers. New Stream Cipher Designs. LNCS. 2008. Volume 4986. pp191-209.
[11] Steve Babbage and Matthew Dodd. The stream cipher MICKEY-128 v2.0. http://www.ecrypt.eu.org/stream/p3ciphers/mickey/mickey128_p3.pdf.
[12] C. De Canniere, B. Preneel. TRIVIUM– a stream cipher construction inspired by block cipher design principles. http://www.ecrypt.eu.org/stream/papersdir/2006/021.pdf.
[13] Havard Raddum. Cryptanalytic Results on Trivium. Cryptology ePrint Archive. Report 2006/039. http://eprint.iacr.org/2006/039.ps.
[14]Tian Yun,Chen Gongliang and Li jianhua. On the Design of Trivium. Crytology eprint Archive 2009/431. http://eprint.iacr.org/2009/431.pdf.
[15] S. Khazaei. Re: A reformulation of TRIVIUM. Posted on the eSTREAM Forum(2006),http://www.ecrypt.eu.org/stream/phorum/read.php?1,448.
[16] Deike Priemuth-Schmid and Alex Biryukov. Slid Pairs in Salsa20 and TRIVIUM [C]. Progress in Cryptology - INDOCRYPT 2008, LNCS, 2008.Volume 5365.pp1-14.
[17] Enes Pasalic. Key differentiation attacks on stream ciphers. Cryptology ePrint Archive, Report 2008/443. http://eprint.iacr.org/.
[18]丁存生,肖国镇.流密码学及其应用[M].北京:国防工业出版社.1994.
[19]胡予濮,张玉清,肖国镇.对称密码学[M].北京:机械工业出版社.2002. pp64~80
[20] C.De Cannière and Bart Preneel. Trivium Specifications. www.ecrypt.eu.org/stream/p3ciphers/trivium/trivium_p3.pdf.
[21]冯登国.密码分析学.北京:清华大学出版社. pp15-38.
[22]E. Biham, A. Biryukov, A. Shamir. Cryptanalysis of skipjack reduced to 31 rounds using impossible differentials. Journal of Cryptology. 2005, 09, Volume 18(4) . pp291-311.
[23]吴文玲.张蕾.不可能差分密码分析研究进展.系统科学与数学.2008, 08, 28(8). pp971-983.
[24]李超,黄建忠和项攀攀.差分分析在序列密码攻击中的应用.应用科学学报.2004,06, 22(2).pp127-131.
[25] S.Babbage. Some Thoughts on Trivium. eSTREAM, ECRYPT Stream Cipher Project, Report 2007/007 (2007), http://www.ecrypt.eu.org/stream.
[26] Shahram Khazaei and Mehdi Hassanzadeh. Linear Sequential Circuit Approximation of the TRIVIUM Stream Cipher. Cryptology ePrint Archive, http://www.ecrypt.eu.org/stream/papersdir/063.pdf.
[27] Alexander Maximov and Alex Biryukov. Two Trivial Attacks on TRIVIUM. Selected Areas in Cryptography. LNCS. Selected Areas in Cryptography. 2007, Volume 4876. pp36-55.
[28] W. Fisher, B.M. Gammel, O. Kniffler, etc. Differential power analysis of stream ciphers. eSTREAM, ECRYPT Stream Cipher Project, Report 2007/014 (2007),http://www.ecrypt.eu.org/stream.
[29] P. C. Kocher, J. Jaffe, and B. Jun. Differential Power Analysis. Advances in Cryptology– CRYPTO’99, Lecture Notes in Computer Science, 1999.vol. 1666, pp388-397.
[30] J.J. Hoch, Shamir. Fault Analysis of Stream Ciphers. CHES 2004. LNCS, 2004. vol. 3156. pp1-20.
[31] Sergei SKorobogatov and Ross Anderson. Optical Fault Induction attack. ches2002 http://www.cl.cam.ac.uk/~rja14/Papers/faultpap3.pdf.
[32] Boneh, Demillo and Lipton. On the Importance of Checking Cryptographic Protocols for Faults, http://dsns.csie.nctu.edu.tw/research/crypto/HTML/PDF/E97/37.PDF.
[33] Biham, Shamir. Differential Fault Analysis of Secret Key Cryptosystems. Cryptology - CRYPT0 '97, LNCS .1997.Volume 1294. pp513-525.
[34] J.Hoch Jonathan and Adi Shamir. Fault analysis of stream ciphers. M. Joye, J.-J. Quisquater (eds.) CHES 2004. LNCS, 2004.vol. 3156. pp240-253.
[35] M. Hojsik, B. Rudolf. Differential fault analysis of Trivium. K. Nyberg (ed.) FSE 2008. LNCS. 2008. vol. 5086. pp158-172.
[36] M.S.Turan, O. Kara. Linear Approximations for 2-round Trivium. eSTREAM, ECRYPT Stream Cipher Project, Report 2007/008 (2007).
[37] E. Biham, O.Dunkelman. Differential Cryptanalysis in Stream Ciphers. COSIC internal report (2007). pp1-22. http://www.cosic.esat.kuleuven.be/publications/article-935.pdf.
[38]Simon Fischer, S. Khazaei and Willi Meier. Chosen IV Statistical Analysis for Key Recovery Attacks on Stream Ciphers. Progress in Cryptology– AFRICACRYPT 2008. LNCS 2008.Volume 5023. pp236-245.
[39] H. Englund, T. Johansson, M.S. Turan. A Framework for Chosen IV Statistical Analysis of Stream Ciphers. In: Srinathan, K., Rangan, C.P., Yung, M. (eds.) INDOCRYPT 2007. LNCS. 2007. vol. 4859. pp268-281.
[40] T. Cover, J.A.Thomas. Elements of Information Theory. 2nd. Hoboken, N.J. : Wiley-Interscience. 2006.
[41] J. Aumasson, S. Fischer and S. Khazaei. Etc. New Features of Latin Dances: Analysis of Salsa, ChaCha, and Rumba. FSE 2008 (2008). LNCS.2008. Volume 5086. pp470-488.
[42] Jean-Philippe Aumasson, Itai Dinur, and Adi Shamir. Cube Testers and Key Recovery Attacks on Reduced-Round MD6 and Trivium. Fast Software Encryption. LNCS. 2009. Volume 5665. pp1-12.
[43] S. S. Bedi and N. Rajesh Pillai. Cube Attacks on Trivium. Cryptology ePrint Archive, Report 2009/015. http://eprint.iacr.org/2009/015.pdf.
[44] Itai Dinur and Adi Shamir. Side Channel Cube Attacks on Block Ciphers. Cryptology ePrint Archive, Report 2009/127. http://eprint.iacr.org/2009/127.pdf
[45] Itai Dinur and Adi Shamir. Cube Attacks on Tweakable Black Box Polynomials.Cryptology ePrint Archive, Report 2008/385. http://eprint.iacr.org/2008/385.pdf.
[46] Michal Hojsík and Bohuslav Rudolf . Floating Fault Analysis of Trivium. Progress in Cryptology - INDOCRYPT 2008. LNCS. 2008.Volume 5365. pp239-250.
[47] Hu Yupu and Gao Juntao and Liu Qing. Floating Fault Analysis of Trivium under Weaker Assumptions1.Cryptology ePrint Archive, Report 2009/169. http://eprint.iacr.org/2009/169.pdf.
[48] Yupu Hu and Fengrong Zhang and Yiwei Zhang. Hard Fault Analysis of Trivium .Cryptology ePrint Archive, Report 2009/333. http://eprint.iacr.org/2009/333.pdf.