×

Cube attacks on tweakable black box polynomials. (English) Zbl 1239.94045

Joux, Antoine (ed.), Advances in cryptology – EUROCRYPT 2009. 28th annual international conference on the theory and applications of cryptographic techniques, Cologne, Germany, April 26–30, 2009. Proceedings. Berlin: Springer (ISBN 978-3-642-01000-2/pbk). Lecture Notes in Computer Science 5479, 278-299 (2009).
Summary: Almost any cryptographic scheme can be described by tweakable polynomials over GF(2), which contain both secret variables (e.g., key bits) and public variables (e.g., plaintext bits or IV bits). The cryptanalyst is allowed to tweak the polynomials by choosing arbitrary values for the public variables, and his goal is to solve the resultant system of polynomial equations in terms of their common secret variables. In this paper we develop a new technique (called a cube attack) for solving such tweakable polynomials, which is a major improvement over several previously published attacks of the same type. For example, on the stream cipher Trivium with a reduced number of initialization rounds, the best previous attack (due to Fischer, Khazaei, and Meier) requires a barely practical complexity of \(2^{55}\) to attack 672 initialization rounds, whereas a cube attack can find the complete key of the same variant in \(2^{19}\) bit operations (which take less than a second on a single PC). Trivium with 735 initialization rounds (which could not be attacked by any previous technique) can now be broken with \(2^{30}\) bit operations. Trivium with 767 initialization rounds can now be broken with \(2^{45}\) bit operations, and the complexity of the attack can almost certainly be further reduced to about \(2^{36}\) bit operations. Whereas previous attacks were heuristic, had to be adapted to each cryptosystem, had no general complexity bounds, and were not expected to succeed on random looking polynomials, cube attacks are provably successful when applied to random polynomials of degree \(d\) over \(n\) secret variables whenever the number \(m\) of public variables exceeds \(d + \log _{d } n\). Their complexity is \(2^{d - 1} n + n ^{2}\) bit operations, which is polynomial in \(n\) and amazingly low when \(d\) is small. Cube attacks can be applied to any block cipher, stream cipher, or MAC which is provided as a black box (even when nothing is known about its internal structure) as long as at least one output bit can be represented by (an unknown) polynomial of relatively low degree in the secret and public variables.
For the entire collection see [Zbl 1161.94003].

MSC:

94A60 Cryptography

Software:

eSTREAM; Trivium; Square; FGb
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] Ajwa, I.A., Liu, Z., Wang, P.S.: Gröbner bases algorithm. Technical report, ICM Technical Reports Series (ICM-199502-00) (1995)
[2] Faugère, J.c.: A new efficient algorithm for computing gröbner bases (f4). Journal of Pure and Applied Algebra, 75–83 (1999) · Zbl 0930.68174
[3] Gwenole, A., Jean-Charles, F., Hideki, I., Mitsuru, K., Makoto, S.: Comparison Between XL and Groebner Basis Algorithms (2004)
[4] Courtois, N.T., Klimov, A.B., Patarin, J., Shamir, A.: Efficient algorithms for solving overdefined systems of multivariate polynomial equations. In: Preneel, B. (ed.) EUROCRYPT 2000. LNCS, vol. 1807, pp. 392–407. Springer, Heidelberg (2000) · Zbl 1082.94514
[5] Courtois, N., Patarin, J.: About the xl algorithm over gf(2). In: CT-RSA, pp. 141–157 (2003) · Zbl 1039.94511
[6] Yang, B.-Y., Chen, J.-M., Courtois, N.T.: On asymptotic security estimates in XL and gröbner bases-related algebraic cryptanalysis. In: López, J., Qing, S., Okamoto, E. (eds.) ICICS 2004. LNCS, vol. 3269, pp. 401–413. Springer, Heidelberg (2004) · Zbl 1109.94353
[7] Courtois, N.T., Pieprzyk, J.: Cryptanalysis of block ciphers with overdefined systems of equations. In: Zheng, Y. (ed.) ASIACRYPT 2002. LNCS, vol. 2501, pp. 267–287. Springer, Heidelberg (2002) · Zbl 1065.94543
[8] Daemen, J., Knudsen, L.R., Rijmen, V.: The block cipher square. In: Biham, E. (ed.) FSE 1997. LNCS, vol. 1267, pp. 149–165. Springer, Heidelberg (1997) · Zbl 1385.94025
[9] Arora, S.: Probabilistic checking of proofs: a new characterization of np. Journal of the ACM, 2–13 (1998) · Zbl 0903.68076
[10] Blum, M., Luby, M., Rubinfeld, R.: Self-testing/correcting with applications to numerical problems. Journal of Computer and System Sciences 47, 549–595 (1993) · Zbl 0795.68131
[11] Courtois, N.T., Meier, W.: Algebraic attacks on stream ciphers with linear feedback, pp. 345–359. Springer, Heidelberg (2003) · Zbl 1038.94525
[12] Golic, J.D.: On the security of nonlinear filter generators. In: Proceedings of the Third International Workshop on Fast Software Encryption, London, UK, pp. 173–188. Springer, Heidelberg (1996) · Zbl 1373.94916
[13] Courtois, N.T.: Fast algebraic attacks on stream ciphers with linear feedback. In: Boneh, D. (ed.) CRYPTO 2003. LNCS, vol. 2729, pp. 176–194. Springer, Heidelberg (2003) · Zbl 1122.94365
[14] Englund, H., Johansson, T.: A new simple technique to attack filter generators and related ciphers. In: Selected Areas in Cryptography, pp. 39–53 (2004) · Zbl 1117.94317
[15] Golic, J.D., Clark, A., Dawson, E.: Generalized inversion attack on nonlinear filter generators. IEEE Trans. Comput. 49(10), 1100–1109 (2000) · Zbl 1314.94049
[16] Johansson, T., Jnsson, F.: Fast correlation attacks through reconstruction of linear polynomials, pp. 300–315. Springer, Heidelberg (2000) · Zbl 0995.94523
[17] Jakobsen, T., Knudsen, L.R.: The interpolation attack on block ciphers. In: Fast Software Encryption, pp. 28–40. Springer, Heidelberg (1997) · Zbl 1385.94047
[18] Garey, M.R., Johnson, D.S.: Computers, and Interactibility. A guide to the theory of np-completeness. Bell Telephone Labratories, Incorporated · Zbl 0411.68039
[19] Aumasson, J.-P., Dinur, I., Meier, W., Shamir, A.: Cube Testers and Key Recovery Attacks On Reduced-Round MD6 and Trivium. In: Fast Software Encryption. Springer, Heidelberg (2009) · Zbl 1291.94051
[20] estream: Ecrypt stream cipher project, http://www.ecrypt.eu.org/stream/
[21] 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
[22] Raddum, H.: Cryptanalytic results on trivium. eSTREAM, ECRYPT Stream Cipher Project, Report 2006/039, 2006 (2006), www.ecrypt.eu.org/stream/papersdir/2006/039.ps
[23] Maximov, A., Biryukov, A.: Two trivial attacks on trivium. In: Selected Areas in Cryptography, pp. 36–55 (2007) · Zbl 1154.94418
[24] McDonald, C.C.C., Pieprzyk, J.: Attacking bivium with minisat, http://eprint.iacr.org/2007/040
[25] Sönmez Turan, M., Kara, O.: Linear approximations for 2-round trivium. In: Proc. First International Conference on Security of Information and Networks (SIN 2007), pp. 96–105. Trafford Publishing (2007)
[26] 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
[27] Vielhaber, M.: Breaking one.fivium by aida an algebraic iv differential attack. Cryptology ePrint Archive, Report 2007/413
[28] 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
[29] Joux, A., Muller, F.: A chosen iv attack against turing. In: Selected Areas in Cryptography, pp. 194–207 (2003) · Zbl 1081.94530
[30] O’Neil, S.: Algebraic structure defectoscopy. Cryptology ePrint Archive, Report 2007/378
[31] Juhani, M., Saarinen, O.: Chosen-iv statistical attacks on estream ciphers. In: Proceeding of SECRYPT 2006, pp. 260–266 (2006)
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.