›› 2016, Vol. 31 ›› Issue (2): 317-325.doi: 10.1007/s11390-016-1629-3

Special Issue: Theory and Algorithms

• Theory and Algorithms • Previous Articles     Next Articles

Utilizing Probabilistic Linear Equations in Cube Attacks

Yuan Yao1,2, Bin Zhang1, and Wen-Ling Wu1   

  1. 1 Trusted Computing and Information Assurance Laboratory, Institute of Software, Chinese Academy of Sciences Beijing 100190, China;
    2 University of Chinese Academy of Sciences, Beijing 100190, China
  • Received:2014-09-16 Revised:2015-03-26 Online:2016-03-05 Published:2016-03-05
  • About author:Yuan Yao currently is a Ph.D. candidate in the University of Chinese Academy of Sciences, Beijing. He received his B.S. degree in information and computing science from Sichuan University, Chengdu, in 2010. His research interest is cryptanalysis of symmetric ciphers.
  • Supported by:

    This work is supported by the National Basic Research 973 Program of China under Grant No. 2013CB338002.

Cube attacks, proposed by Dinur and Shamir at EUROCRYPT 2009, have shown huge power against stream ciphers. In the original cube attacks, a linear system of secret key bits is exploited for key recovery attacks. However, we find a number of equations claimed linear in previous literature actually nonlinear and not fit into the theoretical framework of cube attacks. Moreover, cube attacks are hard to apply if linear equations are rare. Therefore, it is of significance to make use of probabilistic linear equations, namely nonlinear superpolys that can be approximated by linear expressions effectively. In this paper, we suggest a way to test out and utilize these probabilistic linear equations, thus extending cube attacks to a wider scope. Concretely, we employ the standard parameter estimation approach and the sequential probability ratio test (SPRT) for linearity test in the preprocessing phase, and use maximum likelihood decoding (MLD) for solving the probabilistic linear equations in the online phase. As an application, we exhibit our new attack against 672 rounds of Trivium and reduce the number of key bits to search by 7.

[1] Dinur I, Shamir A. Cube attacks on tweakable black box polynomials. In Lecture Notes in Computer Science 5479, Joux A (ed.), Springer Berlin Heidelberg, 2009, pp.278-299.

[2] Aumasson J P, Dinur I, Meier W, Shamir A. Cube testers and key recovery attacks on reduced-round MD6 and Trivium. In Lecture Notes in Computer Science 5665, Dunkelman O (ed.), Springer Berlin Heidelberg, 2009, pp.1-22.

[3] Dinur I, Shamir A. Breaking Grain-128 with dynamic cube attacks. In Lecture Notes in Computer Science 6733, Joux A (ed.), Springer Berlin Heidelberg, 2011, pp.167-187.

[4] Mroczkowski P, Szmidt J. The cube attack on stream cipher Trivium and quadraticity tests. Fundamenta Informaticae, 2012, 114(3/4): 309-318.

[5] Abdul-Latip S F, Reyhanitabar M R, Susilo W, Seberry J. Extended cubes: Enhancing the cube attack by extracting low-degree non-linear equations. In Proc. the 6th ACM Symposium on Information, Computer and Communications Security, March 2011, pp.296-305.

[6] Fouque P A, Vannet T. Improving key recovery to 784 and 799 rounds of Trivium using optimized cube attacks. In Lecture Notes in Computer Science 8424, Moriai S (ed.), Springer Berlin Heidelberg, 2014, pp.502-517.

[7] Dinur I, Shamir A. Side channel cube attacks on block ciphers. Cryptology ePrint Archive, Report 2009/127, 2009. http://eprint.iacr.org/2009/127.pdf, Jan. 2016.

[8] De Cannière C. Trivium: A stream cipher construction inspired by block cipher design principles. In Lecture Notes in Computer Science 4176, Katsikas S, López J, Backes M, Gritzalis S, Preneel B (eds.), Springer Berlin Heidelberg, 2006, pp.171-186.

[9] Aumasson J P, Dinur I, Henzen L, Meier W, Shamir A. Efficient FPGA implementations of high-dimensional cube testers on the stream cipher grain-128. Cryptology ePrint Archive, Report 2009/218, 2009. http://eprint.iacr.org/2009/218.pdf, Jan. 2016.

[10] Blum M, Luby M, Rubinfeld R. Selftesting/correcting with applications to numerical problems. Journal of Computer and System Sciences, 1993, 47(3): 549-595.

[11] Siegenthaler T. Correlation-immunity of nonlinear combining functions for cryptographic applications. IEEE Transactions on Information Theory, 1984, 30(5): 776-780.

[12] Chen J D, Sun S Z, Li D F, Liu L P. Mathematical Statistics Lecture Notes (2nd edition). Higher Education Press, 2007. (in Chinese)

[13] Roth R. Introduction to Coding Theory. New York, NY, USA: Cambridge University Press, 2006.

[14] Lint J. Introduction to Coding Theory (3rd edition). Springer-Verlag Berlin Heidelberg, 1999.

[15] Lu Y, Vaudenay S. Faster correlation attack on bluetooth keystream generator E0. In Lecture Notes in Computer Science 3152, Franklin M (ed.), Springer Berlin Heidelberg, 2004, pp.407-425.
No related articles found!
Full text



[1] Liu Mingye; Hong Enyu;. Some Covering Problems and Their Solutions in Automatic Logic Synthesis Systems[J]. , 1986, 1(2): 83 -92 .
[2] Chen Shihua;. On the Structure of (Weak) Inverses of an (Weakly) Invertible Finite Automaton[J]. , 1986, 1(3): 92 -100 .
[3] Gao Qingshi; Zhang Xiang; Yang Shufan; Chen Shuqing;. Vector Computer 757[J]. , 1986, 1(3): 1 -14 .
[4] Chen Zhaoxiong; Gao Qingshi;. A Substitution Based Model for the Implementation of PROLOG——The Design and Implementation of LPROLOG[J]. , 1986, 1(4): 17 -26 .
[5] Huang Heyan;. A Parallel Implementation Model of HPARLOG[J]. , 1986, 1(4): 27 -38 .
[6] Min Yinghua; Han Zhide;. A Built-in Test Pattern Generator[J]. , 1986, 1(4): 62 -74 .
[7] Tang Tonggao; Zhao Zhaokeng;. Stack Method in Program Semantics[J]. , 1987, 2(1): 51 -63 .
[8] Min Yinghua;. Easy Test Generation PLAs[J]. , 1987, 2(1): 72 -80 .
[9] Sun Yongqiang; Lu Ruzhan; Huang Xiaorong;. Termination Preserving Problem in the Transformation of Applicative Programs[J]. , 1987, 2(3): 191 -201 .
[10] Zhu Hong;. Some Mathematical Properties of the Functional Programming Language FP[J]. , 1987, 2(3): 202 -216 .

ISSN 1000-9000(Print)

CN 11-2296/TP

Editorial Board
Author Guidelines
Journal of Computer Science and Technology
Institute of Computing Technology, Chinese Academy of Sciences
P.O. Box 2704, Beijing 100190 P.R. China
E-mail: jcst@ict.ac.cn
  Copyright ©2015 JCST, All Rights Reserved