Algebraic Attacks on Trivium-Like Stream Ciphers

Abstract

Abstract:

Trivium stream cipher is one of the finalists of European eSTREAM project. In order to have a better study of the design ideas of Trivium, two revised Trivium algorithms were typically chosen together with Trivium as the targets. The recovery of internal state was converted into the SAT problem to analyze the security of Trivium-like stream ciphers against algebraic attacks. Six guess strategies were tried, and then the equation systems were fed to MiniSat2.0. Finally, some suggestions for the security of Triviumlike stream ciphers against algebraic attack were given according to the results.

Key words: cryptanalysis, algebraic attacks, satisfiability problem, stream cipher

CLC Number:

TN 918.1

SUN Wenlong1,GUAN Jie1. Algebraic Attacks on Trivium-Like Stream Ciphers[J]. Journal of Shanghai Jiaotong University, 2014, 48(10): 1434-1439.

References

［1］De Cannière C, Preneel B. TRIVIUM: A stream cipher construction inspired by block cipher design principles［C］∥Proceedings of ISC2006. Heidelberg: Springer, 2006: 171186.

［2］Knellwolf S, Meier W, NayaPlasencia M. Conditional differential cryptanalysis of Trivium and KATAN［C］∥Proceedings of SAC 2011. Heidelberg: Springer, 2011: 200212.

［3］孙文龙, 关杰, 刘建东. 针对简化版Trivium算法的线性分析［J］.计算机学报, 2012, 35(9):18901896.

SUN Wenlong, GUAN Jie, LIU Jiandong. Linear cryptanalysis of simplified Trivium［J］. Chinese Journal of Computers, 2012, 35(9):18901896.

［4］SUN Wenlong, GUAN Jie. A novel technique in linear cryptanalysis［EB/OL］. (20130530) ［20131101］.http:∥eprint.iacr.org/2013/336.

［5］PrimuthSchmid D, Biryukov A. Slide pairs in Salsa20 and Trivium［C］∥Proceedings of INDOCRYPT 2008. Heidelberg: Springer, 2008: 114.

［6］Raddum H. Cryptanalytic results on Trivium［EB/OL］. (20060327) ［20131101］. http:∥www.ecrypt.eu.org/stream/triviump3.html.

［7］Simonetti I, Faugère J C, Perret L. Algebraic attack against Trivium［C］∥Proceedings of First International Conference on Symbolic Computation and Cryptography. Beijing: Beihang University Press, 2008: 95102.

［8］Wong K.K.H, Bard G. Improved algebraic cryptanalysis of QUAD, Bivium and Trivium via graph partitioning on equation systems［C］∥Proceedings of ACISP 2010. Heidelberg: Springer, 2010: 1936.

［9］Borghoff J, Knudsen L R, Matusiewicz K. Hill climbing algorithms and Trivium［C］∥Proceedings of SAC 2010. Heidelberg: Springer, 2010: 5773.

［10］Borghoff J. Mixedinteger linear programming in the analysis of Trivium and KTANTAN［EB/OL］. (2012/11/29) ［2013/11/01］. http:∥eprint.iacr.org/2012/676.

［11］Huang Z, Lin D. Attacking Bivium and Trivium with the characteristic set method［C］∥Proceedings of AFCRICACRYPT 2011. Heidelberg: Springer, 2011: 7791.

［12］McDonald C, Charnes C, Pieprzyk J. Attacking Bivium with MiniSat［EB/OL］. (20070424) ［20131101］. http:∥www.ecrypt.eu.org/stream/triviump3.html.

［13］Eibach T, Pilz E, Vlkel G. Attacking Bivium using SAT solvers［C］∥Theory and Applications Theory and Applications of Satisfiability TestingSAT 2008. Heidelberg: Springer, 2008: 6376.

［14］McDonald C, Charnes C, Pieprzyk J. An algebraic analysis of Trivium ciphers based on the Boolean satisfiability problem［EB/OL］. (20071217) ［20131101］. http:∥eprint.iacr.org/2007/129.

［15］Dinur I, Shamir A. Cube attacks on tweakable black box polynomials［C］∥Proceedings of EUROCRYPT 2009. Heidelberg: Springer, 2009: 278299.

［16］Afzal M, Masood A. Modifications in the design of Trivium to increase its security level［J］. Proceedings of Pakistan Academy of Sciences, 2010, 47(1):5163.

［17］Raj A S, Srinivasan C. Analysis of algebraic attack on Trivium and minute modification to Trivium［C］∥Proceedings of CNSA2011. Heidelberg: Springer, 2011: 3542.

［18］Bard G, Courtois N, Jefferson C. Efficient methods for conversion and solution of sparse systems of lowdegree multivariate polynomials over GF(2) via SATsolvers［EB/OL］. (20070126) ［20131101］. http:∥eprint.iacr.org/2007/024.

［19］Eén N, Srensson N. An extensible SATsolver ［C］∥Proceedings of SAT 2003. Heidelberg: Springer, 2004:502508.

[1]	ZHANG Zhongya1,2,GUAN Jie1. Differential Analysis of Stream Cipher Phelix [J]. Journal of Shanghai Jiaotong University, 2013, 47(07): 1131-1136.
[2]	CHEN Tao-1, YANG Xuan-2, DAI Zi-Bin-1, LI Wei-1, CHEN Xun-1. Design of a Reconfigurable Parallel Nonlinear Feedback Shift Register Structure Targeted at Stream Cipher [J]. Journal of Shanghai Jiaotong University, 2013, 47(01): 28-32.
[3]	ZHANG Zhong-Ya, GUAN Jie. Differential Fault Analysis on the Stream Cipher LEX [J]. Journal of Shanghai Jiaotong University, 2012, 46(06): 865-869.
[4]	GUAN Jie, DING Lin. Slide Attack on Modified Trivium Stream Cipher [J]. Journal of Shanghai Jiaotong University, 2012, 46(06): 926-930.
[5]	WANG Jing-Jing, CHEN Ke-Fei. Improvement of Discrete Fourier Transform Attack [J]. Journal of Shanghai Jiaotong University, 2012, 46(02): 285-288.
[6]	LO Nai-wei (罗乃维), YEH Kuo-hui (叶国晖). Simple Three-Party Password Authenticated Key Exchange Protocol [J]. Journal of shanghai Jiaotong University (Science), 2011, 16(5): 600-603.
[7]	ZHANG Lei, GUO Jian-Sheng. Impossible Differential Cryptanalysis of ARIA [J]. Journal of Shanghai Jiaotong University, 2011, 45(07): 1063-1067.
[8]	CHANG Ya-Qin, JIN Chen-Hui. Fast Computation of Walsh Spectrum of Affine Function over the Ring Z/2n [J]. Journal of Shanghai Jiaotong University, 2011, 45(03): 321-0326.