Paper 2019/607

Improved Meet-in-the-Middle Preimage Attacks against AES Hashing Modes

Zhenzhen Bao, Lin Ding, Jian Guo, Haoyang Wang, and Wenying Zhang


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.

Note: This is the same as the formal version in ToSC Volume 2019, Issue 4. Compared with the previous version, the attacks on 7-round AES-128 and on 8-round AES-192 hashing mode are improved.

Available format(s)
Secret-key cryptography
Publication info
Published by the IACR in FSE 2020
AESMITMpreimagehashing modekey schedule
Contact author(s)
zzbao @ ntu edu sg
dinglin @ sjtu edu cn
guojian @ ntu edu sg
wang1153 @ e ntu edu sg
zhangwenying @ sdnu edu cn
2020-10-09: revised
2019-06-02: received
See all versions
Short URL
Creative Commons Attribution


      author = {Zhenzhen Bao and Lin Ding and Jian Guo and Haoyang Wang and Wenying Zhang},
      title = {Improved Meet-in-the-Middle Preimage Attacks against {AES} Hashing Modes},
      howpublished = {Cryptology ePrint Archive, Paper 2019/607},
      year = {2019},
      doi = {10.13154/tosc.v2019.i4.318-347},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.