The Cube Attack on Stream Cipher Trivium and Quadraticity Tests

• Autorzy: Mroczkowski P. , Szmidt J.
• Języki publikacji: EN

Abstrakty

EN

In 2008 I. Dinur and A. Shamir presented a new type of algebraic attack on symmetric ciphers named cube attack. The method has been applied to reduced variants of stream ciphers Trivium and Grain-128, reduced variants of the block ciphers Serpent and CTC and to a reduced version of the keyed hash function MD6. Previously, a very similar attack named AIDA was introduced by M. Vielhaber, in 2007. In this paper we develop quadraticity tests within the cube attack and apply them to a variant of stream cipher Trivium reduced to 709 initialization rounds. Using this method we obtain the full 80-bit secret key. In this way it eliminates the stage of brute force search of some secret key bits which occured in previous cube attacks.

Słowa kluczowe

EN

linearity and quadraticity tests; key and initial value setup; key stream generation; cube attack

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2012
• Tom: Vol. 114, nr 3/4
• Strony: 309--318
• Opis fizyczny: Bibliogr.17 poz., tab.

Twórcy

autor

Mroczkowski P.

autor

Szmidt J.

• Department of Cryptology Military Communication Institute ul. Warszawska 22A, 05-130 Zegrze, Poland,

Bibliografia

• [1] N. Alon, T. Kaufman, M. Krivelevich, S. Litsyn, and D. Ron. Testing Low-Degree Polynomials over GF(2). RANDOM 2003 and APPROX 2003, S. Arora, K. Jansen, J.D.P. Rolim, and A. Sahai, editors. LNCS, vol 2764, pp. 188-199. Springer 2003.
• [2] J-P. Aumasson, W. Meier, I. Dinur, and A. Shamir. Cube Testers and Key Recovery Attacks on Reduced RoundMD6 and Trivium. Fast Software Encryption 2009. Orr Dunkelman, editor. LNCS, vol 5665, pp. 1-22. Springer 2009.
• [3] J-P. Aumasson, I. Dinur, L. Henzen, W. Meier, and A. Shamir. Efficient FPGA Implementations of High-Dimensional Cube Testers on the Stream Cipher Grain-128. IACR Cryptology ePrint Archive, 2009/218.
• [4] S. S. Bedi and R. Pillai. Cube Attacks on Trivium. IACR Cryptology ePrint Archive, 2009/15.
• [5] M. Blum, M. Luby, and R. Rubinfeld. Self-Testing/Correcting with Applications to Numerical Problems. Journal of Computer and System Sciences, vol 47(1993), pp. 549-595.
• [6] Ch. De Cannière and B. Preneel. Trivium Specifications. www.ecrypt.eu.org/stream/p3ciphers/trivium
• [7] Ch. De Cannière and B. Preneel. Trivium.M.J.B. Robshaw and O. Bilet, editors. New Stream Cipher Designs. LNCS, vol 4817, pp. 244-246. Springer 2008.
• [8] P. Crowley. Trivium, SSE2, CorePy, and the "cube attack". Published on http://www.lshift.net/blog/
• [9] I. Dinur and A. Shamir. Cubic Attacks on Tweakable Black Box Polynomials. EUROCRYPT 2009. A. Joux, editor. LNCS, vol 5479, pp. 278-299. Springer 2009.
• [10] I. Dinur and A. Shamir. Side Channel Cube Attacks on Block Ciphers. IACR Cryptology ePrint Archive, 2009/127.
• [11] I. Dinur and A. Shamir. Breaking Grain-128 with Dynamic Cube Attacks. IACR Cryptology ePrint Archive, 2010/570. To appear in Proceedings of FSE 2011. LNCS. Springer.
• [12] P. Mroczkowski and J. Szmidt. The Cube Attack on Courtois Toy Cipher. IACR Cryptology ePrint Archive, 2009/497. To appear in Proceedings of WEWoRC 2009. LNCS. Springer.
• [13] P. Mroczkowski and J. Szmidt. The Cube Attack on Stream Cipher Trivium and Quadraticity Tests. Rump Session. CRYPTO 2010.
• [14] M. Vielhaber. Breaking ONE.FIVIUM by AIDA an Algebraic IV Differential Attack. IACR Cryptology ePrint Archive, 2007/413.
• [15] M. Vielhaber. AIDA Breaks BIVIUM (A and B) in 1 Minute Dual Core CPU Time. IACR Cryptology ePrint Archive, 2009/402.
• [16] M. Vielhaber. Speeding up AIDA, the Algebraic IV Differential Attack, by the Fast Reed-Muller Transform. Proc. ISKE 2009, Heerlen, Belgium, pp. 504-513.
• [17] Bo Zhu,Wenge Yu and Tao Wang. A Practical Platform for Cube-Attack-like Cryptanalyses. CS 758: Cryptography/ Network Security Course Project. IACR Cryptology ePrint Archive, 2010/664.