×

Improved key recovery attacks on reduced-round AES with practical data and memory complexities. (English) Zbl 1457.94097

Summary: Determining the security of AES is a central problem in cryptanalysis, but progress in this area had been slow and only a handful of cryptanalytic techniques led to significant advancements. L. Grassi et al. [EUROCRYPT 2017, Lect. Notes Comput. Sci. 10211, 289–317 (2017; Zbl 1415.94433)] presented a novel type of distinguisher for AES-like structures, but so far all the published attacks which were based on this distinguisher were inferior to previously known attacks in their complexity. In this paper we combine the technique of L. Grassi et al. [loc. cit.] with several other techniques in a novel way to obtain the best known key recovery attack on 5-round AES in the single-key model, reducing its overall complexity from about \(2^{32}\) to less than \(2^{22}\). Extending our techniques to 7-round AES, we obtain the best known attacks on reduced-round AES-192 which use practical amounts of data and memory, breaking the record for such attacks which was obtained in 2000 by the classical Square attack. In addition, we use our techniques to improve the Gilbert-Minier attack (2000) on 7-round AES, reducing its memory complexity from \(2^{80}\) to \(2^{40}\).

MSC:

94A60 Cryptography
94A62 Authentication, digital signatures and secret sharing

Citations:

Zbl 1415.94433

Software:

LED; ELmD; Square
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] E. Biham, A. Biryukov, O. Dunkelman, E. Richardson, A. Shamir, Initial observations on skipjack: Cryptanalysis of skipjack-3xor. in S.E. Tavares, H. Meijer (eds.) Selected Areas in Cryptography ’98, SAC’98, Kingston, Ontario, Canada, August 17-18, 1998, Proceedings. Lecture Notes in Computer Science, vol. 1556, (Springer, 1998), pp. 362-376 · Zbl 0929.94009
[2] E. Biham, O. Dunkelman, N. Keller, The rectangle attack - rectangling the serpent. in B. Pfitzmann (ed.) Advances in Cryptology - EUROCRYPT 2001, International Conference on the Theory and Application of Cryptographic Techniques, Innsbruck, Austria, May 6-10, 2001, Proceeding. Lecture Notes in Computer Science, vol. 2045, (Springer, 2001), pp. 340-357 · Zbl 0981.94017
[3] E. Biham, N. Keller, Cryptanalysis of Reduced Variants of Rijndael (1999), unpublished manuscript.
[4] A. Bogdanov, D. Khovratovich, C. Rechberger, Biclique Cryptanalysis of the Full AES. in D.H. Lee, X. Wang (eds.) Advances in Cryptology - ASIACRYPT 2011 - 17th International Conference on the Theory and Application of Cryptology and Information Security, Seoul, South Korea, December 4-8, 2011. Proceedings. Lecture Notes in Computer Science, vol. 7073, (Springer, 2011), pp. 344-371. · Zbl 1227.94032
[5] Bossuet, L.; Datta, N.; Mancillas-López, C.; Nandi, M., ELmD: A Pipelineable Authenticated Encryption and Its Hardware Implementation, IEEE Trans. Computers, 65, 11, 3318-3331 (2016) · Zbl 1360.94343
[6] Bouillaguet, C.; Derbez, P.; Dunkelman, O.; Fouque, P.; Keller, N.; Rijmen, V., Low-Data Complexity Attacks on AES, IEEE Trans. Information Theory, 58, 11, 7002-7017 (2012) · Zbl 1364.94525
[7] C. Bouillaguet, P. Derbez, P. Fouque, Automatic Search of Attacks on Round-Reduced AES and Applications. in P. Rogaway (ed.) Advances in Cryptology - CRYPTO 2011 - 31st Annual Cryptology Conference, Santa Barbara, CA, USA, August 14-18, 2011. Proceedings. Lecture Notes in Computer Science, vol. 6841, (Springer, 2011), pp. 169-187 · Zbl 1287.94056
[8] Boura, C.; Lallemand, V.; Naya-Plasencia, M.; Suder, V., Making the impossible possible, J. Cryptology, 31, 1, 101-133 (2018) · Zbl 1421.94041
[9] J. Cho, K.Y. Choi, I. Dinur, O. Dunkelman, N. Keller, D. Moon, A. Veidberg, WEM: A New Family of White-Box Block Ciphers Based on the Even-Mansour Construction. in H. Handschuh (ed.) Topics in Cryptology - CT-RSA 2017 - The Cryptographers’ Track at the RSA Conference 2017, San Francisco, CA, USA, February 14-17, 2017, Proceedings. Lecture Notes in Computer Science, vol. 10159, (Springer, 2017), pp. 293-308 · Zbl 1383.94015
[10] J. Daemen, L.R. Knudsen, V. Rijmen, The Block Cipher Square. in E. Biham (ed.) Fast Software Encryption, 4th International Workshop, FSE ’97, Haifa, Israel, January 20-22, 1997, Proceedings. Lecture Notes in Computer Science, vol. 1267, (Springer, 1997), pp. 149-165 · Zbl 1385.94025
[11] J. Daemen, V. Rijmen, The Design of Rijndael: AES - The Advanced Encryption Standard. Information Security and Cryptography, (Springer, 2002) · Zbl 1065.94005
[12] H. Demirci, A.A. Selçuk, A Meet-in-the-Middle Attack on 8-Round AES. in K. Nyberg (ed.) Fast Software Encryption, 15th International Workshop, FSE 2008, Lausanne, Switzerland, February 10-13, 2008, Revised Selected Papers. Lecture Notes in Computer Science, vol. 5086, (Springer, 2008), pp. 116-126
[13] P. Derbez, Meet-in-the-middle attacks on AES. Ph.D. thesis, Ecole Normale Suprieure de Paris — ENS Paris (2013)
[14] P. Derbez, P. Fouque, Exhausting Demirci-Selçuk Meet-in-the-Middle Attacks Against Reduced-Round AES. in S. Moriai (ed.) Fast Software Encryption - 20th International Workshop, FSE 2013, Singapore, March 11-13, 2013. Revised Selected Papers. Lecture Notes in Computer Science, vol. 8424, (Springer, 2013), pp. 541-560 · Zbl 1321.94053
[15] P. Derbez, P. Fouque, J. Jean, Improved Key Recovery Attacks on Reduced-Round AES in the Single-Key Setting. in T. Johansson, P.Q. Nguyen (eds.) Advances in Cryptology - EUROCRYPT 2013, 32nd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Athens, Greece, May 26-30, 2013. Proceedings. Lecture Notes in Computer Science, vol. 7881, (Springer, 2013), pp. 371-387 · Zbl 1306.94044
[16] I. Dinur, O. Dunkelman, N. Keller, A. Shamir, Efficient Dissection of Composite Problems, with Applications to Cryptanalysis, Knapsacks, and Combinatorial Search Problems. in R. Safavi-Naini, R. Canetti (eds.) Advances in Cryptology - CRYPTO 2012 - 32nd Annual Cryptology Conference, Santa Barbara, CA, USA, August 19-23, 2012. Proceedings. Lecture Notes in Computer Science, vol. 7417, (Springer, 2012), pp. 719-740 · Zbl 1294.94042
[17] N. Ferguson, J. Kelsey, S. Lucks, B. Schneier, M. Stay, D.A. Wagner, D. Whiting, Improved Cryptanalysis of Rijndael. in Schneier [30], pp. 213-230 · Zbl 0994.68631
[18] P. Fouque, P. Karpman, P. Kirchner, B. Minaud, Efficient and Provable White-Box Primitives. in: J.H. Cheon, T. Takagi (eds.) Advances in Cryptology - ASIACRYPT 2016 - 22nd International Conference on the Theory and Application of Cryptology and Information Security, Hanoi, Vietnam, December 4-8, 2016, Proceedings, Part I. Lecture Notes in Computer Science, vol. 10031, (2016), pp. 159-188 · Zbl 1404.94069
[19] B. Gérard, V. Grosso, M. Naya-Plasencia, F. Standaert, Block Ciphers That Are Easier to Mask: How Far Can We Go? in G. Bertoni, J. Coron (eds.) Cryptographic Hardware and Embedded Systems - CHES 2013 - 15th International Workshop, Santa Barbara, CA, USA, August 20-23, 2013. Proceedings. Lecture Notes in Computer Science, vol. 8086, (Springer, 2013), pp. 383-399. · Zbl 1353.94048
[20] H. Gilbert, M. Minier, A collision attack on 7 rounds of rijndael. in AES Candidate Conference. (2000), pp. 230-241
[21] L. Grassi, Mixture Differential Cryptanalysis: New Approaches for Distinguishers and Attacks on round-reduced AES. Cryptology ePrint Archive, Report 2017/832 (2017), https://eprint.iacr.org/2017/832
[22] L. Grassi, Mixture differential cryptanalysis: a new approach to distinguishers and attacks on round-reduced aes. IACR Transactions on Symmetric Cryptology 2018(2), 133-160 (Jun 2018)
[23] L. Grassi, C. Rechberger, S. Rønjom, A New Structural-Differential Property of 5-Round AES. in J. Coron, J.B. Nielsen (eds.) Advances in Cryptology - EUROCRYPT 2017 - 36th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Paris, France, April 30-May 4, 2017, Proceedings, Part II. Lecture Notes in Computer Science, vol. 10211, (2017), pp. 289-317 · Zbl 1415.94433
[24] J. Guo, T. Peyrin, A. Poschmann, M.J.B. Robshaw, The LED Block Cipher. in B. Preneel, T. Takagi (eds.) Cryptographic Hardware and Embedded Systems - CHES 2011 - 13th International Workshop, Nara, Japan, September 28-October 1, 2011. Proceedings. Lecture Notes in Computer Science, vol. 6917, (Springer, 2011), pp. 326-341 · Zbl 1291.94092
[25] V.T. Hoang, T. Krovetz, P. Rogaway, Robust Authenticated-Encryption AEZ and the Problem That It Solves. in E. Oswald, M. Fischlin (eds.) Advances in Cryptology - EUROCRYPT 2015 - 34th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Sofia, Bulgaria, April 26-30, 2015, Proceedings, Part I. Lecture Notes in Computer Science, vol. 9056, (Springer, 2015), pp. 15-44 · Zbl 1365.94485
[26] J. Kelsey, T. Kohno, B. Schneier, Amplified boomerang attacks against reduced-round MARS and serpent. in Schneier [30], pp. 75-93 · Zbl 0994.68635
[27] X. Lai, J.L. Massey, S. Murphy, Markov ciphers and differential cryptanalysis. in: D.W. Davies (ed.) Advances in Cryptology - EUROCRYPT ’91, Workshop on the Theory and Application of of Cryptographic Techniques, Brighton, UK, April 8-11, 1991, Proceedings. Lecture Notes in Computer Science, vol. 547, (Springer, 1991), pp. 17-38 · Zbl 0777.94013
[28] H. Mala, M. Dakhilalian, V. Rijmen, M. Modarres-Hashemi, Improved Impossible Differential Cryptanalysis of 7-Round AES-128. in G. Gong, K.C. Gupta (eds.) Progress in Cryptology - INDOCRYPT 2010 - 11th International Conference on Cryptology in India, Hyderabad, India, December 12-15, 2010. Proceedings. Lecture Notes in Computer Science, vol. 6498, (Springer, 2010), pp. 282-291
[29] S. Rønjom, N.G. Bardeh, T. Helleseth, Yoyo Tricks with AES. in T. Takagi, T. Peyrin (eds.) Advances in Cryptology - ASIACRYPT 2017 - 23rd International Conference on the Theory and Applications of Cryptology and Information Security, Hong Kong, China, December 3-7, 2017, Proceedings, Part I. Lecture Notes in Computer Science, vol. 10624, (Springer, 2017), pp. 217-243 · Zbl 1420.94094
[30] B. Schneier (ed.) Fast Software Encryption, 7th International Workshop, FSE 2000, New York, NY, USA, April 10-12, 2000, Proceedings, Lecture Notes in Computer Science, vol. 1978. Springer (2001)
[31] T. Tiessen, Polytopic Cryptanalysis. in M. Fischlin, J. Coron (eds.) Advances in Cryptology - EUROCRYPT 2016 - 35th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Vienna, Austria, May 8-12, 2016, Proceedings, Part I. Lecture Notes in Computer Science, vol. 9665, (Springer, 2016), pp. 214-239
[32] M. Tunstall, Improved “Partial Sums”-based Square Attack on AES. in P. Samarati, W. Lou, J. Zhou (eds.) SECRYPT 2012 - Proceedings of the International Conference on Security and Cryptography, Rome, Italy, 24-27 July, 2012, SECRYPT is part of ICETE - The International Joint Conference on e-Business and Telecommunications. pp. 25-34. SciTePress (2012)
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.