More than two decades of attacks on the AES cryptosystem

Eddahmani, Said

doi:10.47974/JDMSC-1834

Open Access Research Article

More than two decades of attacks on the AES cryptosystem

^*Said EddahmaniCorresponding authorsaid.eddahmani@etud.univ-paris8.frAffiliation 1Department of MathematicsLaboratory Geometry Analysis and ApplicationsUniversity of Paris VIIISaint-Denis, F-93526, FranceAffiliation 2CNRS, UMR 7539, F-93430University Sorbonne Paris NordVilletaneuse, FranceView full profile →

* Corresponding author · click or hover a name for details

pp. 667–683Vol. 28Issue 3April 2025DOI: 10.47974/JDMSC-1834 Crossmark XML

Received:: 08 Feb 2023
Published Online:: 26 Feb 2025
Article type:: Research Article
Language:: EN
Article no.:: JDMSC-1834
Pages:: 667–683

Abstract

In 2001, the National Institute for Standards and Technology (NIST) chose AES to secure sensitive information. Since then, AES has become the most widely used symmetric cryptosystem and has been intensively studied for vulnerabilities. In this survey, we celebrate twenty years of the AES by presenting an overview of cryptographers’ work on it. We describe the main cryptanalytic techniques on AES, including linear cryptanalysis, differential cryptanalysis, boomerang cryptanalysis, differential-linear cryptanalysis cryptanalysis, and many other techniques of cryptanalysis.

Keywords

Symmetric cryptography AES cryptosystem Cryptanalysis Substitution boxes Vectorial boolean function

Subject Classifications

94A60

References

[1] C. Ashokkumar, R. P. Giri, and B. Menezes, “Highly efficient algorithms for AES key retrieval in cache access attacks,” in Proc. 2016 IEEE European Symposium on Security and Privacy (EuroS&P), pp. 261-275 (2016).
[2] S. Bajrić, “Infinite families of five-valued Walsh spectrum Boolean functions,” Journal of Discrete Mathematical Sciences and Cryptography, vol. 25, no. 5, pp. 1303-1320 (2022), doi: 10.1080/09720529.2020.1756043.
[3] U. Banerjee, L. Ho, and S. Koppula, “Power-based side-channel attack for AES key extraction on the ATMega328 Microcontroller,” arXiv preprint arXiv:2203.08220 (2022).
[4] A. Bar-On, O. Dunkelman, N. Keller, and A. Weizman, “DLCT: A new tool for differential-linear cryptanalysis,” in EUROCRYPT 2019, Y. Ishai and V. Rijmen, Eds., vol. 11476 of Lecture Notes in Computer Science, pp. 313-342 (2019).
[5] E. Biham, A. Biryukov, and A. Shamir, “Cryptanalysis of Skipjack reduced to 31 rounds using impossible differentials,” J. Cryptology, vol. 18, no. 4, pp. 291-311 (2005).
[6] E. Biham and A. Shamir, “Differential cryptanalysis of DES-like cryptosystems,” Journal of Cryptology, vol. 4, no. 1, pp. 3-72 (1991).
[7] E. Biham, O. Dunkelman, and N. Keller, “The rectangle attack - rectangling the Serpent,” in EUROCRYPT 2001, B. Pfitzmann, Ed., vol. 2045 of Lecture Notes in Computer Science, pp. 340-357, Springer (2001).
[8] E. Biham, O. Dunkelman, and N. Keller, “Enhancing differential-linear cryptanalysis,” in Advances in Cryptology – ASIACRYPT 2002, vol. 2501 of Lecture Notes in Computer Science, pp. 254-266, Springer (2002).
[9] A. Biryukov, “The Boomerang attack on 5 and 6-Round AES,” in Advanced Encryption Standard - AES, H. Dobbertin, V. Rijmen, and A. Sowa, Eds., vol. 3373 of Lecture Notes in Computer Science, pp. 11-16, Springer, Heidelberg (2005).
[10] A. Bogdanov, D. Khovratovich, and C. Rechberger, “Biclique cryptanalysis of the full AES,” in Asiacrypt 2011, D. H. Lee and X. Wang, Eds., vol. 7073 of Lecture Notes in Computer Science, pp. 344-371, Springer (2011).
[11] X. Bonnetain, M. Naya-Plasencia, and A. Schrottenloher, “Quantum security analysis of AES,” Cryptology ePrint Archive, Report 2019/272 (2019). [Online]. Available: https://eprint.iacr.org/2019/272.
[12] C. Boura and A. Canteaut, “On the boomerang uniformity of cryptographic S-boxes,” IACR Transactions on Symmetric Cryptology, Ruhr Universität Bochum, vol. 2018, no. 3, pp. 290-310 (2018).
[13] A. Canteaut, L. Kölsch, C. Li, C. Li, K. Li, L. Qu, and F. Wiemer, “On the differential-linear connectivity table of vectorial Boolean functions,” (2019). [Online]. Available: https://arxiv.org/abs/1908.07445v1.
[14] C. Cid, T. Huang, T. Peyrin, Y. Sasaki, and L. Song, “Boomerang connectivity table: a new cryptanalysis tool,” in Advances in Cryptology - EUROCRYPT 2018 - Proceedings, Part II, J. B. Nielsen and V. Rijmen, Eds., vol. 10821 of Lecture Notes in Computer Science, pp. 683-714, Springer (2018).
[15] C. Carlet, “Boolean functions for cryptography and error-correcting codes,” in Boolean Models and Methods in Mathematics, Computer Science, and Engineering, Y. Crama and P. L. Hammer, Eds., pp. 257-397, Cambridge University Press (2010).
[16] C. Carlet, Boolean Functions for Cryptography and Coding Theory, Cambridge University Press, Cambridge (2021).
[17] C. Carlet and S. Mesnager, “Four decades of research on bent functions,” Des. Codes Cryptogr., vol. 78, pp. 5-50 (2016).
[18] J. Daemen and V. Rijmen, The Design of Rijndael: AES - The Advanced Encryption Standard, Springer Verlag (2002).
[19] H. Demirci and A. A. Selçuk, “A meet-in-the-middle attack on 8-round AES,” in Proc. of Fast Software Encryption 15, vol. 5806 of Lecture Notes in Computer Science, pp. 116-126, Springer (2008).
[20] P. Derbez, P. Fouque, and J. Jean, “Improved key recovery attacks on reduced-round AES in the single-key setting,” in Advances in Cryptology - EUROCRYPT 2013, T. Johansson and P. Q. Nguyen, Eds., vol. 7881 of Lecture Notes in Computer Science, pp. 371-387, Springer (2013).
[21] O. Dunkelman, K. Keller, E. Ronen, and A. Shamir, “The retracing boomerang attack,” Cryptology ePrint Archive, Report 2019/1154 (2019). [Online]. Available: https://eprint.iacr.org/2019/1154.
[22] O. Dunkelman, S. Indesteege, and N. Keller, “A differential-linear attack on 12-round Serpent,” in Progress in Cryptology - INDOCRYPT 2008, D. R. Chowdhury, V. Rijmen, and A. Das, Eds., vol. 5365 of Lecture Notes in Computer Science, pp. 174-188, Springer, Berlin, Heidelberg (2008).
[23] N. Ferguson, J. Kelsey, S. Lucks, B. Schneier, M. Stay, D. Wagner, and D. Whiting, “Improved cryptanalysis of Rijndael,” in Fast Software Encryption: FSE 2000, G. Goos, J. Hartmanis, J. van Leeuwen, and B. Schneier, Eds., vol. 1978 of Lecture Notes in Computer Science, pp. 213-230, Springer, Berlin, Heidelberg (2001).
[24] H. Gilbert and M. Minier, “A collision attack on 7 rounds of Rijndael,” in AES Candidate Conference, pp. 230-241 (2000).
[25] M. Gorski and L. Lucks, “New related-key boomerang attacks on AES,” in Progress in Cryptology - INDOCRYPT 2008, D. R. Chowdhury, V. Rijmen, and A. Das, Eds., vol. 5365 of Lecture Notes in Computer Science, Springer, Berlin, Heidelberg (2008).
[26] L. K. Grover, “A fast quantum mechanical algorithm for database search,” in Proc. of the 28th Annual ACM Symposium on the Theory of Computing, Philadelphia, PA, USA, May 22-24, 1996, G. L. Miller, Ed., pp. 21-29 (1996).
[27] J. Kim, S. Hong, and B. Preneel, “Related-key rectangle attacks on reduced AES-192 and AES-256,” in Fast Software Encryption: FSE 2007, A. Biryukov, Ed., vol. 4593 of Lecture Notes in Computer Science, Springer, Berlin, Heidelberg (2007).
[28] H. Kim, S. Kim, D. Hong, J. Sung, and S. Hong, “Improved differential-linear cryptanalysis using DLCT,” Journal of The Korean Institute of Information Security & Cryptology, vol. 28, no. 6, pp. 733-748, Dec. (2018).
[29] L. R. Knudsen, “Truncated and higher order differentials,” in Fast Software Encryption, B. Preneel, Ed., vol. 1008 of Lecture Notes in Computer Science, pp. 196-211, Springer (1994).
[30] S. K. Langford and M. E. Hellman, “Differential-linear cryptanalysis,” in CRYPTO, Y. Desmedt, Ed., vol. 839 of Lecture Notes in Computer Science, pp. 17-25, Springer (1994).
[31] K. Li, L. Qu, B. Sun, and C. Li, “New results about the boomerang uniformity of permutation polynomials,” IEEE Transactions on Information Theory, vol. 65, no. 11, pp. 7292-7303 (2019).
[32] J. Lu, “A methodology for differential-linear cryptanalysis and its applications,” Des. Codes Cryptogr., vol. 77, no. 1, pp. 11-48 (2015).
[33] J. Lu, O. Dunkelman, N. Keller, and J. Kim, “New Impossible Differential Attacks on AES,” in Progress in Cryptology - INDOCRYPT 2008, D. R. Chowdhury, V. Rijmen, and A. Das, Eds., vol. 5365 of Lecture Notes in Computer Science, Springer, Berlin, Heidelberg (2008).
[34] M. Matsui, “Linear cryptanalysis method for DES cipher,” in Advances in Cryptology - EUROCRYPT ’93, Springer-Verlag, Berlin, pp. 386-397 (1994).
[35] S. Mesnager, Bent Functions: Fundamentals and Results, Springer, Switzerland (2016).
[36] K. Nyberg, “Differentially uniform mappings for cryptography,” in Proc. of EUROCRYPT ’93, vol. 765 of Lecture Notes in Computer Science, pp. 55-64 (1994).
[37] K. Nyberg and L. R. Knudsen, “Provable security against differential cryptanalysis,” in Advances in Cryptology — CRYPTO ’92, E. F. Brickell, Ed., vol. 740 of Lecture Notes in Computer Science, Springer, Berlin, Heidelberg (1992).
[38] K. Nyberg and L. R. Knudsen, “Provable security against a differential attack,” Journal of Cryptology, vol. 8, no. 1, pp. 27-37 (1995).
[39] National Institute of Standards and Technology, Federal Information Processing Standards Publication 197: Announcing the Advanced Encryption Standard (AES). [Online]. Available: http://csrc.nist.gov/publications/fips/fips197/fips-197.pdf.
[40] S. B. Ors, F. Gurkaynak, E. Oswald, and B. Preneel, “Power-analysis attack on an ASIC AES implementation,” in Proc. International Conference on Information Technology: Coding and Computing (ITCC 2004), vol. 2, pp. 546-552 (2004).
[41] Y. Shin, J. Kim, G. Kim, S. Hong, and S. Lee, “Differential-linear type attacks on reduced rounds of SHACAL-2,” in Proc. of ACISP ’04, H. Wang, J. Pieprzyk, and V. Varadharajan, Eds., vol. 3108 of Lecture Notes in Computer Science, pp. 110-122, Springer-Verlag (2004).
[42] L. Song, X. Qin, and L. Hu, “Boomerang connectivity table revisited,” Cryptology ePrint Archive, Report 2019/146 (2019). [Online]. Available: https://eprint.iacr.org/2019/146.
[43] U.S. National Bureau of Standards, Data Encryption Standard, Federal Information Processing Standards Publications No. 46 (1977).
[44] D. Wagner, “The Boomerang attack,” in Fast Software Encryption, L. R. Knudsen, Ed., vol. 1636 of Lecture Notes in Computer Science, pp. 156-170, Springer (1999).
[45] G. Yellapu, “Improved lower bound for algebraic immunity of a subclass of MM bent Boolean functions,” Journal of Discrete Mathematical Sciences and Cryptography, vol. 24, no. 4, pp. 965-973 (2021), doi: 10.1080/09720529.2019.1701268.

Views: 183Downloads: 27Citations: 0