Improved meet-in-the-middle preimage attacks against AES hashing modes

Hashing modes are ways to convert a block cipher into a hash function, and those with AES as the underlying block cipher are referred to as AES hashing modes. Sasaki in 2011, introduced the first preimage attack against AES hashing modes with the AES block cipher reduced to 7 rounds, by the method o...

Full description

Saved in:
Bibliographic Details
Main Authors: Bao, Zhenzhen, Ding, Lin, Guo, Jian, Wang, Haoyang, Zhang, Wenying
Other Authors: School of Physical and Mathematical Sciences
Format: Article
Language:English
Published: 2020
Subjects:
AES
Online Access:https://hdl.handle.net/10356/145131
Tags: Add Tag
No Tags, Be the first to tag this record!
Institution: Nanyang Technological University
Language: English
id sg-ntu-dr.10356-145131
record_format dspace
spelling sg-ntu-dr.10356-1451312023-02-28T19:36:22Z Improved meet-in-the-middle preimage attacks against AES hashing modes Bao, Zhenzhen Ding, Lin Guo, Jian Wang, Haoyang Zhang, Wenying School of Physical and Mathematical Sciences Strategic Centre for Research in Privacy-Preserving Technologies and Systems Library and information science::Cryptography AES MITM Hashing modes are ways to convert a block cipher into a hash function, and those with AES as the underlying block cipher are referred to as AES hashing modes. Sasaki in 2011, introduced the first preimage attack against AES hashing modes with the AES block cipher reduced to 7 rounds, by the method of meet-in-the-middle. In his attack, the key-schedules are not taken into account. Hence, the same attack applies to all three versions of AES. In this paper, by introducing neutral bits from the key, extra degree of freedom is gained, which is utilized in two ways, i.e., to reduce the time complexity and to extend the attack to more rounds. As an immediate result, the complexities of 7-round pseudo-preimage attacks are reduced from 2^120 to 2^104, 2^96, and 2^96 for AES-128, AES-192, and AES-256, respectively. By carefully choosing the neutral bits from the key to cancel those from the state, the attack is extended to 8 rounds for AES-192 and AES-256 with complexities 2^112 and 2^96. Similar results are obtained for Kiasu-BC, a tweakable block cipher based on AES-128, and interestingly the additional input tweak helps reduce the complexity and extend the attack to one more round. To the best of our knowledge, these are the first preimage attacks against 8-round AES hashing modes. Ministry of Education (MOE) Nanyang Technological University National Research Foundation (NRF) Published version We thank Lei Wang for helpful discussions during the early phase of this work. We would like to thank all the reviewers of ToSC 2019 for their valuable comments and suggestions, and would like to specially thank Yu Sasaki for willing to be our shepherd. This research is supported by the National Research Foundation, Prime Minister’s Office, Singapore, under its Strategic Capability Research Centres Funding Initiative (Grant No. M4062510.J30), Nanyang Technological University under grant M4082123, and Singapore’s Ministry of Education under grants M4012049, M4012153, and M4020466. Wenying Zhang is supported by the National Natural Science Foundation of China (Grant No. 61672330). 2020-12-14T01:29:39Z 2020-12-14T01:29:39Z 2020 Journal Article Bao, Z., Ding, L., Guo, J., Wang, H., & Zhang, W. (2020). Improved meet-in-the-middle preimage attacks against AES hashing modes. IACR Transactions on Symmetric Cryptology, 2019(4), 318-347. doi:10.13154/tosc.v2019.i4.318-347 2519-173X https://hdl.handle.net/10356/145131 10.13154/tosc.v2019.i4.318-347 4 2019 318 347 en M4062510.J30 M4082123 M4012049 M4012153 M4020466 IACR Transactions on Symmetric Cryptology © 2020 Zhenzhen Bao, Lin Ding, Jian Guo, Haoyang Wang, Wenying Zhang. This work is licensed under a Creative Commons Attribution 4.0 International License. application/pdf
institution Nanyang Technological University
building NTU Library
continent Asia
country Singapore
Singapore
content_provider NTU Library
collection DR-NTU
language English
topic Library and information science::Cryptography
AES
MITM
spellingShingle Library and information science::Cryptography
AES
MITM
Bao, Zhenzhen
Ding, Lin
Guo, Jian
Wang, Haoyang
Zhang, Wenying
Improved meet-in-the-middle preimage attacks against AES hashing modes
description Hashing modes are ways to convert a block cipher into a hash function, and those with AES as the underlying block cipher are referred to as AES hashing modes. Sasaki in 2011, introduced the first preimage attack against AES hashing modes with the AES block cipher reduced to 7 rounds, by the method of meet-in-the-middle. In his attack, the key-schedules are not taken into account. Hence, the same attack applies to all three versions of AES. In this paper, by introducing neutral bits from the key, extra degree of freedom is gained, which is utilized in two ways, i.e., to reduce the time complexity and to extend the attack to more rounds. As an immediate result, the complexities of 7-round pseudo-preimage attacks are reduced from 2^120 to 2^104, 2^96, and 2^96 for AES-128, AES-192, and AES-256, respectively. By carefully choosing the neutral bits from the key to cancel those from the state, the attack is extended to 8 rounds for AES-192 and AES-256 with complexities 2^112 and 2^96. Similar results are obtained for Kiasu-BC, a tweakable block cipher based on AES-128, and interestingly the additional input tweak helps reduce the complexity and extend the attack to one more round. To the best of our knowledge, these are the first preimage attacks against 8-round AES hashing modes.
author2 School of Physical and Mathematical Sciences
author_facet School of Physical and Mathematical Sciences
Bao, Zhenzhen
Ding, Lin
Guo, Jian
Wang, Haoyang
Zhang, Wenying
format Article
author Bao, Zhenzhen
Ding, Lin
Guo, Jian
Wang, Haoyang
Zhang, Wenying
author_sort Bao, Zhenzhen
title Improved meet-in-the-middle preimage attacks against AES hashing modes
title_short Improved meet-in-the-middle preimage attacks against AES hashing modes
title_full Improved meet-in-the-middle preimage attacks against AES hashing modes
title_fullStr Improved meet-in-the-middle preimage attacks against AES hashing modes
title_full_unstemmed Improved meet-in-the-middle preimage attacks against AES hashing modes
title_sort improved meet-in-the-middle preimage attacks against aes hashing modes
publishDate 2020
url https://hdl.handle.net/10356/145131
_version_ 1759854328526405632