International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

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

Authors:
Zhenzhen Bao , Division of Mathematical Sciences, School of Physical and Mathematical Sciences, Nanyang Technological University; Strategic Centre for Research in Privacy-Preserving Technologies and Systems, Nanyang Technological University, Singapore
Lin Ding , Department of Computer Science and Engineering, Shanghai Jiao Tong University, Shanghai, China
Jian Guo , Division of Mathematical Sciences, School of Physical and Mathematical Sciences, Nanyang Technological University, Singapore
Haoyang Wang , Division of Mathematical Sciences, School of Physical and Mathematical Sciences, Nanyang Technological University, Singapore
Wenying Zhang , Division of Mathematical Sciences, School of Physical and Mathematical Sciences; School of Information Science and Engineering, Shandong Normal University, Jinan, China Nanyang Technological University, Singapore
Download:
DOI: 10.13154/tosc.v2019.i4.318-347
URL: https://tosc.iacr.org/index.php/ToSC/article/view/8467
Search ePrint
Search Google
Abstract: 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 2120 to 2104, 296, and 296 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 2112 and 296. 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.
Video from TOSC 2020
BibTeX
@article{tosc-2020-30097,
  title={Improved Meet-in-the-Middle Preimage Attacks against AES Hashing Modes},
  journal={IACR Transactions on Symmetric Cryptology},
  publisher={Ruhr-Universität Bochum},
  volume={2019, Issue 4},
  pages={318-347},
  url={https://tosc.iacr.org/index.php/ToSC/article/view/8467},
  doi={10.13154/tosc.v2019.i4.318-347},
  author={Zhenzhen Bao and Lin Ding and Jian Guo and Haoyang Wang and Wenying Zhang},
  year=2020
}