Correlation cube attacks: from weak-key distinguisher to key recovery. (English) Zbl 1428.94086

Nielsen, Jesper Buus (ed.) et al., Advances in cryptology – EUROCRYPT 2018. 37th annual international conference on the theory and applications of cryptographic techniques, Tel Aviv, Israel, April 29 – May 3, 2018. Proceedings. Part II. Cham: Springer. Lect. Notes Comput. Sci. 10821, 715-744 (2018).
Summary: In this paper, we describe a new variant of cube attacks called correlation cube attack. The new attack recovers the secret key of a cryptosystem by exploiting conditional correlation properties between the superpoly of a cube and a specific set of low-degree polynomials that we call a basis, which satisfies that the superpoly is a zero constant when all the polynomials in the basis are zeros. We present a detailed procedure of correlation cube attack for the general case, including how to find a basis of the superpoly of a given cube. One of the most significant advantages of this new analysis technique over other variants of cube attacks is that it converts from a weak-key distinguisher to a key recovery attack.{
}As an illustration, we apply the attack to round-reduced variants of the stream cipher Trivium. Based on the tool of numeric mapping introduced by M. Liu [Crypto 2017, Lect. Notes Comput. Sci. 10403, 227–249 (2017; Zbl 1406.94073)] , we develop a specific technique to efficiently find a basis of the superpoly of a given cube as well as a large set of potentially good cubes used in the attack on Trivium variants, and further set up deterministic or probabilistic equations on the key bits according to the conditional correlation properties between the superpolys of the cubes and their bases. For a variant when the number of initialization rounds is reduced from 1152 to 805, we can recover about 7-bit key information on average with time complexity \(2^{44}\), using \(2^{45}\) keystream bits and preprocessing time \(2^{51}\). For a variant of Trivium reduced to 835 rounds, we can recover about 5-bit key information on average with the same complexity. All the attacks are practical and fully verified by experiments. To the best of our knowledge, they are thus far the best known key recovery attacks for these variants of Trivium, and this is the first time that a weak-key distinguisher on Trivium stream cipher can be converted to a key recovery attack.
For the entire collection see [Zbl 1387.94007].


94A60 Cryptography


Zbl 1406.94073
Full Text: DOI


[1] Aumasson, J., Dinur, I., Henzen, L., Meier, W., Shamir, A.: Efficient FPGA implementations of high-dimensional cube testers on the stream cipher Grain-128. IACR Cryptology ePrint Archive 2009:218 (2009)
[2] Aumasson, J-P; Dinur, I.; Meier, W.; Shamir, A.; Dunkelman, O., Cube testers and key recovery attacks on reduced-round MD6 and Trivium, Fast Software Encryption, 1-22 (2009), Heidelberg: Springer, Heidelberg · Zbl 1291.94051
[3] Bertoni, G., Daemen, J., Peeters, M., Van Assche, G.: The Keccak reference, January 2011. http://keccak.noekeon.org, Version 3.0 · Zbl 1306.94028
[4] Canteaut, A.; Carpov, S.; Fontaine, C.; Lepoint, T.; Naya-Plasencia, M.; Paillier, P.; Sirdey, R.; Peyrin, T., Stream ciphers: a practical solution for efficient homomorphic-ciphertext compression, Fast Software Encryption, 313-333 (2016), Heidelberg: Springer, Heidelberg · Zbl 1387.94071
[5] Chakraborti, A.; Chattopadhyay, A.; Hassan, M.; Nandi, M.; Güneysu, T.; Handschuh, H., TriviA: a fast and secure authenticated encryption scheme, Cryptographic Hardware and Embedded Systems - CHES 2015, 330-353 (2015), Heidelberg: Springer, Heidelberg · Zbl 1380.94077
[6] Chakraborti, A., Nandi, M.: TriviA-ck-v2. CAESAR Submission (2015). http://competitions.cr.yp.to/round2/triviackv2.pdf
[7] De Cannière, C.; Dunkelman, O.; Knežević, M.; Clavier, C.; Gaj, K., KATAN and KTANTAN — a family of small and efficient hardware-oriented block ciphers, Cryptographic Hardware and Embedded Systems - CHES 2009, 272-288 (2009), Heidelberg: Springer, Heidelberg · Zbl 1290.94060
[8] De Cannière, C.; Preneel, B.; Robshaw, M.; Billet, O., Trivium, New Stream Cipher Designs, 244-266 (2008), Heidelberg: Springer, Heidelberg · Zbl 1285.94054
[9] Dinur, I.; Güneysu, T.; Paar, C.; Shamir, A.; Zimmermann, R.; Lee, DH; Wang, X., An experimentally verified attack on Full Grain-128 using dedicated reconfigurable hardware, Advances in Cryptology - ASIACRYPT 2011, 327-343 (2011), Heidelberg: Springer, Heidelberg · Zbl 1227.94042
[10] Dinur, I., Morawiecki, P., Pieprzyk, J., Srebrny, M., Straus, M.: Cube attacks and cube-attack-like cryptanalysis on the Round-Reduced Keccak Sponge Function. In: Oswald and Fischlin [26], pp. 733-761 · Zbl 1370.94506
[11] Dinur, I.; Shamir, A.; Joux, A., Cube attacks on tweakable black box polynomials, Advances in Cryptology - EUROCRYPT 2009, 278-299 (2009), Heidelberg: Springer, Heidelberg · Zbl 1239.94045
[12] Dinur, I.; Shamir, A.; Joux, A., Breaking Grain-128 with dynamic cube attacks, Fast Software Encryption, 167-187 (2011), Heidelberg: Springer, Heidelberg · Zbl 1282.94042
[13] Englund, H.; Johansson, T.; Sönmez Turan, M.; Srinathan, K.; Rangan, CP; Yung, M., A framework for chosen IV statistical analysis of stream ciphers, Progress in Cryptology - INDOCRYPT 2007, 268-281 (2007), Heidelberg: Springer, Heidelberg · Zbl 1153.94373
[14] Fischer, S.; Khazaei, S.; Meier, W.; Vaudenay, S., Chosen IV statistical analysis for key recovery attacks on stream ciphers, Progress in Cryptology - AFRICACRYPT 2008, 236-245 (2008), Heidelberg: Springer, Heidelberg · Zbl 1142.94343
[15] Fouque, P-A; Vannet, T.; Moriai, S., Improving key recovery to 784 and 799 rounds of Trivium using optimized cube attacks, Fast Software Encryption, 502-517 (2014), Heidelberg: Springer, Heidelberg · Zbl 1321.94058
[16] Hell, M., Johansson, T., Maximov, A., Meier, W.: A stream cipher proposal: grain-128. In: 2006 IEEE International Symposium on Information Theory, pp. 1614-1618. IEEE (2006)
[17] Hell, M.; Johansson, T.; Maximov, A.; Meier, W.; Robshaw, M.; Billet, O., The grain family of stream ciphers, New Stream Cipher Designs, 179-190 (2008), Heidelberg: Springer, Heidelberg
[18] Huang, S.; Wang, X.; Xu, G.; Wang, M.; Zhao, J.; Coron, J-S; Nielsen, JB, Conditional cube attack on reduced-round Keccak sponge function, Advances in Cryptology - EUROCRYPT 2017, 259-288 (2017), Cham: Springer, Cham · Zbl 1415.94439
[19] Knellwolf, S.; Meier, W.; Naya-Plasencia, M.; Abe, M., Conditional differential cryptanalysis of NLFSR-based cryptosystems, Advances in Cryptology - ASIACRYPT 2010, 130-145 (2010), Heidelberg: Springer, Heidelberg · Zbl 1253.94056
[20] Knellwolf, S.; Meier, W.; Naya-Plasencia, M.; Miri, A.; Vaudenay, S., Conditional differential cryptanalysis of Trivium and KATAN, Selected Areas in Cryptography, 200-212 (2012), Heidelberg: Springer, Heidelberg · Zbl 1292.94095
[21] Lai, X.: Higher order derivatives and differential cryptanalysis. In: Proceedings Symposium in Communications, Coding Cryptography, pp. 227-233. Kluwer Academic Publishers (1994) · Zbl 0840.94017
[22] Liu, M.; Katz, J.; Shacham, H., Degree evaluation of NFSR-based cryptosystems, Advances in Cryptology - CRYPTO 2017, 227-249 (2017), Cham: Springer, Cham · Zbl 1406.94073
[23] Liu, M., Lin, D., Wang, W.: Searching cubes for testing Boolean functions and its application to Trivium. In: IEEE International Symposium on Information Theory, ISIT 2015, Hong Kong, China, 14-19 June 2015, pp. 496-500. IEEE (2015)
[24] Maximov, A.; Biryukov, A.; Adams, C.; Miri, A.; Wiener, M., Two trivial attacks on Trivium, Selected Areas in Cryptography, 36-55 (2007), Heidelberg: Springer, Heidelberg · Zbl 1154.94418
[25] Meier, W.; Staffelbach, O., Fast correlation attacks on certain stream ciphers, J. Cryptol., 1, 3, 159-176 (1989) · Zbl 0673.94010
[26] Oswald, E.; Fischlin, M., Advances in Cryptology - EUROCRYPT 2015 (2015), Heidelberg: Springer, Heidelberg · Zbl 1321.94011
[27] Saarinen, M.O.: Chosen-IV statistical attacks on estream ciphers. In: Malek, M., Fernández-Medina, E., Hernando, J. (eds.) SECRYPT 2006, Proceedings of the International Conference on Security and Cryptography, Setúbal, Portugal, 7-10 August 2006, SECRYPT is part of ICETE - The International Joint Conference on e-Business and Telecommunications, pp. 260-266. INSTICC Press (2006)
[28] Stankovski, P.; Gong, G.; Gupta, KC, Greedy distinguishers and nonrandomness detectors, Progress in Cryptology - INDOCRYPT 2010, 210-226 (2010), Heidelberg: Springer, Heidelberg · Zbl 1294.94078
[29] Todo, Y.: Structural evaluation by generalized integral property. In: Oswald and Fischlin [26], pp. 287-314 · Zbl 1370.94545
[30] Todo, Y.; Isobe, T.; Hao, Y.; Meier, W.; Katz, J.; Shacham, H., Cube attacks on non-blackbox polynomials based on division property, Advances in Cryptology - CRYPTO 2017, 250-279 (2017), Cham: Springer, Cham · Zbl 1406.94081
[31] Todo, Y.; Morii, M.; Peyrin, T., Bit-based division property and application to Simon family, Fast Software Encryption, 357-377 (2016), Heidelberg: Springer, Heidelberg · Zbl 1387.94102
[32] Vielhaber, M.: Breaking ONE.FIVIUM by AIDA an algebraic IV differential attack. IACR Cryptology ePrint Archive, 2007:413 (2007)
[33] Rajaram, S.; Roediger, HL, Direct comparison of four implicit memory tests, J. Exp. Psychol. Learn. Mem. Cogn., 19, 4, 765 (1993)
[34] Ramos, J.: Using tf-idf to determine word relevance in document queries. In: Proceedings of 1st Instructional Conference on Machine Learning (2003)
[35] Ratcliff, R.; McKoon, G., A retrieval theory of priming in memory, Psychol. Rev., 95, 3, 385 (1988)
[36] Schmid, H.: Treetagger—a language independent part-of-speech tagger. Institut für Maschinelle Sprachverarbeitung, Universität Stuttgart 43, p. 28 (1995)
[37] Silvers, VL; Kreiner, DS, The effects of pre-existing inappropriate highlighting on reading comprehension, Lit. Res. Instr., 36, 3, 217-223 (1997)
[38] Stanovich, KE; Cunningham, AE, What reading does for the mind, J. Direct Instr., 1, 2, 137-149 (2001)
[39] Strobelt, H.; Oelke, D.; Kwon, BC; Schreck, T.; Pfister, H., Guidelines for effective usage of text highlighting techniques, IEEE Trans. Vis. Comput. Graph., 22, 1, 489-498 (2016)
[40] Strobelt, H.; Oelke, D.; Rohrdantz, C.; Stoffel, A.; Keim, D.; Deussen, O., Document cards: a top trumps visualization for documents, IEEE Trans. Vis. Comput. Graph., 15, 6, 1145-1152 (2009)
[41] Viégas, FB; Wattenberg, M., Timelines: tag clouds and the case for vernacular visualization, Interactions, 15, 4, 49-52 (2008)
[42] Wise, J.A., Thomas, J.J., Pennock, K., Lantrip, D., Pottier, M., Schur, A., Crow, V.: Visualizing the non-visual: spatial analysis and interaction with information from text documents. In: Proceedings of 1995 IEEE Symposium on Information Visualization, INFOVIS 1995, p. 51-. IEEE Computer Society, Washington, DC (1995). http://dl.acm.org/citation.cfm?id=857186.857579
[43] Zhang, F.: The application of visualization technology on knowledge management. In: Proceedings of 2008 International Conference on Intelligent Computation Technology and Automation, ICICTA 2008, vol. 02, pp. 767-771. IEEE Computer Society, Washington, DC (2008). doi:10.1109/ICICTA.2008.479
[44] Zhu, X., Goldberg, A.B., Eldawy, M., Dyer, C.R., Strock, B.: A text-to-picture synthesis system for augmenting communication. In: Proceedings of 22nd National Conference on Artificial Intelligence, AAAI 2007, vol. 2, pp. 1590-1595. AAAI Press (2007). http://dl.acm.org/citation.cfm?id=1619797.1619900
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.