Abstract
We observe the slow diffusion of the AES key schedule for 256-bit keys and find weakness which can be used in the preimage attack on its Davies-Meyer mode. Our preimage attack works for 8 rounds of AES-256 with the computational complexity of 2124.9. It is comparable with Bogdanov et al.’s biclique-based preimage attack on AES-256, which is applicable up to full rounds but has the computational complexity more than 2126.5. We also extend our result to the preimage attack on some well-known double-block-length hash modes assuming the underlying block cipher is 8-round AES-256, whose computational complexity is 2252.9.
Similar content being viewed by others
References
Advanced Encryption Standard (AES) , Federal Information Processing Standards Publication 197, November 26, 2001
Aoki K, Guo J, Matusiewicz K, Sasaki Y, Wang L (2009) Preimages for step-reduced SHA-2. In: Matsui M (ed) ASIACRYPT 2009, LNCS 5912. Springer, pp 578–597
Aoki K, Sasaki Y (2009) Meet-in-the-middle preimage attacks against reduced SHA-0 and SHA-1. In: Halevi S (ed) CRYPTO 2009, LNCS 5677. Springer, pp 70–89
Aoki K, Sasaki Y (2009) Preimage attacks on one-block MD4, 63-Step MD5 and more. In: Avanzi RM, Keliher L, Sica F (eds) SAC 2008, LNCS 5381. Springer, pp 103–119
Armknecht F, Fleischmann E, Krause M, Lee J, Stam M, Steinberger J (2011) The preimage security of double-block-length compression functions. In: Lee DH, Wang X (eds) ASIACRYPT 2011, LNCS 7073. Springer, pp 233–251
Black J, Rogaway P, Shrimpton T (2002) Black-box analysis of the block-cipher-based hash-function construction from PGV. In: Yung M (ed) CRYPTO 2002, LNCS 2442. Springer, pp 320–335
Bogdanov A, Khovratovich D, Rechberger C (2011) Biclique cryptanalysis of the full AES. ASIACRYPT 2011, LNCS 7073. Springer, pp 344–371
Daemen J, Knudsen LR, Rijmen V (1997) The block cipher square. In: Biham E (ed) FSE’97, LNCS 1267. Springer, pp 149–165
Dean RD (1999) Formal aspects of mobile code security. Ph. D Dissertation, Princeton University
Hirose S (2006) Some plausible constructions of double-block-length hash functions. In: Robshaw MJB (ed) FSE 2006, LNCS 4047. Springer, pp 231–246
Hong D, Koo B, Kim D-C (2012) Preimage and second-preimage attacks on PGV hashing modes of round-reduced ARIA, Camellia, and Serpent. IEICE Trans Fundam Electron Commun Comput Sci 95-A(1):372–380
Kelsey J, Schneier B (2005) Second preimages in n-bit hash functions for much less than 2n work. In: Cramer R (ed) EUROCRYPT 2005, LNCS 3494. Springer, pp 474–490
Lai X, Massey JL (1993) Hash function based on block ciphers. In: Rueppel RA (ed) EUROCRYPT’92, LNCS 658. Springer, pp 55–70
Lee J, Kwon D (2011) The security of abreast-DM in the ideal cipher model. IEICE Trans Fundam Electron Commun Comput Sci 94-A(1):104–109
Lee J, Stam M (2011) MJH: a faster alternative to MDC-2. In: Kiayias A (ed) CT-RSA 2011, LNCS 6558. Springer, pp 213–236
Lee J, Stam M, Steinberger JP (2011) The collision security of tandem-DM in the ideal cipher model. In: Rogaway P (ed) CRYPTO 2011, LNCS 6841. Springer, pp 561–577
Leurent G (2008) MD4 is not one-way. In: Nyberg K (ed) FSE 2008, LNCS 5086. Springer, pp 412–428
Lim CH (1999) A revised version of crypton—crypton V1.0. In: Knudsen LR (ed) FSE’99, LNCS 1636. Springer, pp 31–45
Menezes AJ, Oorschot PC, Vanstone SA (1997) Handbook of applied cryptography. CRC Press
Moon D, Hong D, Koo B, Hong S Security evaluation of double-block-length hash modes with preimage attacks on PGV schemes. In: The 2011 FTRA international symposium on advances in cryptography, security and applications for future computing
Moon D, Hong D, Kwon D, Hong S (2012) Meet-in-the-middle preimage attacks on hash modes of generalized feistel and misty schemes with SP round function. IEICE Trans Fundam Electron Commun Comput Sci 95-A(8)
Preneel B, Govaerts R, Vandewalle J (1994) Hash functions based on block ciphers: a synthetic approach. In: Stinson DR (ed) CRYPTO 1993, LNCS 773. Springer, pp 363–378
Sasaki Y (2011) Meet-in-the-middle preimage attacks on AES hashing modes and an application to whirlpool. In: Joux A (ed), FSE 2011, LNCS 6733. Springer, pp 378–396
Sasaki Y, Aoki K (2009) Finding preimages in full MD5 faster than exhaustive search. In: Joux A (ed) EUROCRYPT 2009, LNCS 5479. Springer, pp 134–152
Secure Hash Standard (SHS) , Federal Information Processing Standards Publication 180-2, August 1, 2002. Amended February 25, 2004
Acknowledgments
This research was supported by Basic Science Research Program through the National Research Foundation of Korea (NRF) funded by the Ministry of Education (Grant No. 2013R1A1A2059864).
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Hong, D., Kim, DC., Kwon, D. et al. Improved preimage attacks on hash modes of 8-round AES-256. Multimed Tools Appl 75, 14525–14539 (2016). https://doi.org/10.1007/s11042-015-2769-0
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11042-015-2769-0