Cryptology ePrint Archive: Report 2021/575

MITM Meets Guess-and-Determine: Further Improved Preimage Attacks against AES-like Hashing

Zhenzhen Bao and Jian Guo and Danping Shi and Yi Tu

Abstract: Since the Meet-in-the-Middle preimage attack against 7-round AES hashing was found by Sasaki in 2011, the development of this research direction has never been stopped. In 2019, Bao et al. found the degree of freedom from the message (or the key of the underlying block cipher) were useful, before the Mixed-Integer-Linear-Programming (MILP) modeling was introduced to find the optimal attack configurations in 2020. In this paper, we move one step further in this research direction by introducing more techniques such as guess-and-determine, round independence, and symmetry etc. to the MILP search model. To demonstrate the power of the enhanced model, we apply it to the popular AES-like hash functions Whirlpool, GrÝstl, and AES hashing modes, and obtain general improvements over the existing best (pseudo-)preimage attacks. In particular, the number of attacked rounds on Whirlpool and AES-256 hashing modes is extended from 6 to 7 and 9 to 10, respectively. Time complexity improvements are also obtained on variants of lesser rounds, as well as the 6-round GrÝstl-256 and the 8-round GrÝstl-512. Computer experiments on trial versions of the full attack procedure have confirmed the correctness of our results.

Category / Keywords: secret-key cryptography / Whirlpool, GrÝstl, AES hashing modes, hash function, MITM, Preimage, Automatic search, Guess and Determine, MILP

Date: received 1 May 2021

Contact author: zzbao at ntu edu sg,guojian@ntu edu sg,shidanping@iie ac cn,TUYI0002@e ntu edu sg

Available format(s): PDF | BibTeX Citation

Version: 20210503:202116 (All versions of this report)

Short URL: ia.cr/2021/575


[ Cryptology ePrint archive ]