×

Breaking Grain-128 with dynamic cube attacks. (English) Zbl 1282.94042

Joux, Antoine (ed.), Fast software encryption. 18th international workshop, FSE 2011, Lyngby, Denmark, February 13–16, 2011. Revised selected papers. Berlin: Springer (ISBN 978-3-642-21701-2/pbk). Lecture Notes in Computer Science 6733, 167-187 (2011).
Summary: We present a new variant of cube attacks called a dynamic cube attack. Whereas standard cube attacks [I. Dinur and A. Shamir, EUROCRYPT 2009. Lect. Notes Comput. Sci. 5479, 278– 299 (2009; Zbl 1239.94045)] find the key by solving a system of linear equations in the key bits, the new attack recovers the secret key by exploiting distinguishers obtained from cube testers. Dynamic cube attacks can create lower degree representations of the given cipher, which makes it possible to attack schemes that resist all previously known attacks. In this paper we concentrate on the well-known stream cipher Grain-128 [M. Hell et al., A stream cipher proposal: Grain-128. In: IEEE ISIT 2006 (2006) http://www.ecrypt.eu.org/stream/p3ciphers/grain/Grain128_p3.pdf], on which the best known key recovery attack [S. Knellwolf et al., ASIACRYPT 2010. Lect. Notes Comput. Sci. 6477, 130–145 (2010; Zbl 1253.94056)] can recover only 2 key bits when the number of initialization rounds is decreased from 256 to 213. Our first attack runs in practical time complexity and recovers the full 128-bit key when the number of initialization rounds in Grain-128 is reduced to 207. Our second attack breaks a Grain-128 variant with 250 initialization rounds and is faster than exhaustive search by a factor of about \(2^{28}\). Finally, we present an attack on the full version of Grain-128 which can recover the full key but only when it belongs to a large subset of \(2^{-10}\) of the possible keys. This attack is faster than exhaustive search over the \(2^{118}\) possible keys by a factor of about \(2^{15}\). All of our key recovery attacks are the best known so far, and their correctness was experimentally verified rather than extrapolated from smaller variants of the cipher. This is the first time that a cube attack was shown to be effective against the full version of a well known cipher which resisted all previous attacks.
For the entire collection see [Zbl 1217.68011].

MSC:

94A60 Cryptography

Software:

Grain; Trivium
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] Biham, E., Shamir, A.: Differential cryptanalysis of DES-like cryptosystems. In: Menezes, A., Vanstone, S.A. (eds.) CRYPTO 1990. LNCS, vol. 537, pp. 2–21. Springer, Heidelberg (1991) · Zbl 0787.94014
[2] Matsui, M.: Linear cryptanalysis method for DES cipher. In: Helleseth, T. (ed.) EUROCRYPT 1993. LNCS, vol. 765, pp. 386–397. Springer, Heidelberg (1994) · Zbl 0951.94519
[3] Aumasson, J.-P., Dinur, I., Meier, W., Shamir, A.: Cube Testers and Key Recovery Attacks on Reduced-Round MD6 and Trivium. In: Dunkelman, O. (ed.) FSE 2009. LNCS, vol. 5665, pp. 1–22. Springer, Heidelberg (2009) · Zbl 1291.94051
[4] Dinur, I., Shamir, A.: Cube attacks on tweakable black box polynomials. In: Joux, A. (ed.) EUROCRYPT 2009. LNCS, vol. 5479, pp. 278–299. Springer, Heidelberg (2009) · Zbl 1239.94045
[5] 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. In: SHARCS - Special-purpose Hardware for Attacking Cryptographic Systems (2009)
[6] Hell, M., Johansson, T., Maximov, A., Meier, W.: A stream cipher proposal: Grain-128. In: IEEE International Symposium on Information Theory, ISIT 2006 (2006)
[7] Englund, H., Johansson, T., Sönmez Turan, M.: A framework for chosen IV statistical analysis of stream ciphers. In: Srinathan, K., Rangan, C.P., Yung, M. (eds.) INDOCRYPT 2007. LNCS, vol. 4859, pp. 268–281. Springer, Heidelberg (2007) · Zbl 1153.94373
[8] Fischer, S., Khazaei, S., Meier, W.: Chosen IV statistical analysis for key recovery attacks on stream ciphers. In: Vaudenay, S. (ed.) AFRICACRYPT 2008. LNCS, vol. 5023, pp. 236–245. Springer, Heidelberg (2008) · Zbl 1142.94343
[9] De Cannière, C., Kücük, Ö., Preneel, B.: Analysis of Grain’s initialization algorithm. In: SASC 2008 (2008) · Zbl 1142.94340
[10] Lee, Y., Jeong, K., Sung, J., Hong, S.H.: Related-key chosen IV attacks on grain-v1 and grain-128. In: Mu, Y., Susilo, W., Seberry, J. (eds.) ACISP 2008. LNCS, vol. 5107, pp. 321–335. Springer, Heidelberg (2008) · Zbl 1285.94076
[11] Lai, X.: Higher order derivatives and differential cryptanalysis. In: Symposium on Communication, Coding and Cryptography, in Honor of James L. Massey on the Occasion of His 60’th Birthday, pp. 227–233 (1994) · Zbl 0840.94017
[12] Vielhaber, M.: Breaking ONE.FIVIUM by AIDA an algebraic IV differential attack. Cryptology ePrint Archive, Report 2007/413 (2007)
[13] Joux, A.: Algorithmic Cryptanalysis, pp. 285–286. Chapman & Hall, Boca Raton · Zbl 1172.94008
[14] De Cannière, C., Preneel, B.: Trivium - a stream cipher construction inspired by block cipher design principles. estream, ecrypt stream cipher. Technical report of Lecture Notes in Computer Science · Zbl 1156.94345
[15] Knellwolf, S., Meier, W., Naya-Plasencia, M.: Conditional Differential Cryptanalysis of NLFSR-Based Cryptosystems. In: Abe, M. (ed.) ASIACRYPT 2010. LNCS, vol. 6477, pp. 130–145. Springer, Heidelberg (2010) · Zbl 1253.94056
[16] Stankovski, P.: Greedy Distinguishers and Nonrandomness Detectors. In: Gong, G., Gupta, K.C. (eds.) INDOCRYPT 2010. LNCS, vol. 6498, pp. 210–226. Springer, Heidelberg (2010) · Zbl 1294.94078
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.