Applying cube attacks to stream ciphers in realistic scenarios. (English) Zbl 1285.94057

Summary: Cube attacks were introduced in [I. Dinur and A. Shamir, Lect. Notes Comput. Sci. 5479, 278–299 (2009; Zbl 1239.94045)] as a cryptanalytic technique that requires only black box access to the underlying cryptosystem. The attack exploits the existence of low degree polynomial representation of a single output bit (as a function of the key and plaintext bits) in order to recover the secret key. Although cube attacks can be applied in principle to almost any cryptosystem, most block ciphers iteratively apply a highly nonlinear round function (based on S-boxes or arithmetic operations) a large number of times which makes them resistant to cube attacks. On the other hand, many stream ciphers (such as Trivium [C. De Cannière and B. Preneel, New stream cipher designs. Lect. Notes Comput. Sci. 4986, 244–266 (2008; Zbl 1285.94054)]), are built using linear or low degree components and are natural targets for cube attacks. In this paper, we describe in detail how to apply cube attacks to stream ciphers in various settings with different assumptions on the target stream cipher and on the data available to the attacker.


94A60 Cryptography


Full Text: DOI


[1] 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. Lecture Notes in Computer Science, vol. 5665, pp. 1–22. Springer (2009) · Zbl 1291.94051
[2] Blum, M., Luby, M., Rubinfeld, R.: Self-testing/correcting with applications to numerical problems. In: STOC, pp. 73–83. ACM (1990) · Zbl 0795.68131
[3] Courtois, N., Klimov, A., Patarin, J., Shamir, A.: Efficient algorithms for solving overdefined systems of multivariate polynomial equations. In: Preneel, B. (ed.) EUROCRYPT. Lecture Notes in Computer Science, vol. 1807, pp. 392–407. Springer (2000) · Zbl 1082.94514
[4] De Cannière, C., Preneel, B.: Trivium. In: New Stream Cipher Designs. LNCS, vol. 4986, pp. 84–97. Springer (2008)
[5] Dinur, I., Shamir, A.: Cube attacks on tweakable black box polynomials. In: Joux, A. (ed.) EUROCRYPT. Lecture Notes in Computer Science, vol. 5479, pp. 278–299. Springer (2009) · Zbl 1239.94045
[6] Dinur, I., Shamir, A.: Generic analysis of small cryptographic leaks. In: Breveglieri, L., Joye, M., Koren, I., Naccache, D., Verbauwhede, I. (eds.) FDTC, IEEE Computer Society, pp. 39–48 (2010)
[7] Faugère, J.C.: A new efficient algorithm for computing Grø”bner bases without reduction to zero (F5). In: Proceedings of the 2002 International Symposium on Symbolic and Algebraic Computation, ISSAC ’02, pp. 75–83. ACM, New York, NY, USA (2002) · Zbl 1072.68664
[8] Gaborit, P., Ruatta, O.: Efficient erasure list-decoding of Reed-Muller codes. In: 2006 IEEE International Symposium on Information Theory, pp. 148–152 (2006)
[9] Goldreich, O., Goldwasser, S., Lehman, E., Ron, D., Samorodnitsky, A.: Testing monotonicity. Combinatorica 20(3), 301–337 (2000) · Zbl 0964.68148 · doi:10.1007/s004930070011
[10] Kaufman, T., Litsyn, S., Xie, N.: Breaking the epsilon-soundness bound of the linearity test over GF(2). SIAM J. Comput. 39(5), 1988–2003 (2010) · Zbl 1202.68178 · doi:10.1137/080715548
[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] Luby, M., Mitzenmacher, M., Shokrollahi, M.A., Spielman, D.A.: Efficient erasure correcting codes. IEEE Trans. Inf. Theory 47(2), 569–584 (2001) · Zbl 1019.94032 · doi:10.1109/18.910575
[13] Reed, I.S.: A class of multiple-error-correcting codes and the decoding scheme. IEEE Trans. Inf. Theory 4(4), 38–49 (1954)
[14] Vielhaber, M.: Breaking ONE.FIVIUM by AIDA an Algebraic IV Differential Attack. Cryptology ePrint Archive, Report 2007/413 (2007)
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.