The Meet-in-the-Middle Preimage Attack On AES Hashing

Since the National Institute of Standards and Technology（NIST）published the Advanced Encryption Standard（AES）in 2001,AES has become the most widely used block cipher in the world due to long-standing security against massive cryptanalysis and efficiency in both software and hardware.AES hashing refers to those hash functions constructed from the block cipher AES through the hash modes（e.g.PGV mode）,which inherits the reliable security and performance efficiency from AES.A cryptographic hash function should fulfill three basic se-curity requirements:collision resistance,preimage resistance and second-preimage resistance.In this paper,we focus on the preimage resistance and the second preimage resistance of AES hashing,and the specific work is as follows:We improve the preimage attack based on the Meet-in-the-Middle（MITM）approach.Based on MITM preimage attack and its variant biclique cryptanalysis,we propose the concept of neu-tral words in different positions and equivalent keys,which allow two computational（truncated differential）paths to start from different subkeys or states,thus making the attack with more fea-sible schemes.Further,we put the problem of searching for the optimal attack schemes down to finding two truncated differential trials with the minimum number of common active S-boxes and built a simple MILP model in our way to solve this.We present for the first preimage attack on full AES-128 in 12 PGV modes.The preim-age attack in various PGV modes is the same or similar,so we choose the MMO-mode and DM-mode as examples to illustrate our attack.For the preimage attack on AES-128-MMO,its time complexity is 2^125.72AES-128 encryption without the key schedul and its memory com-plexity is 2¹⁶.For the preimage attack on AES-128-DM,its time complexity is 2^126.53AES-128encryption without the key schedul and its memory complexity is 2⁸.This attack also can be directly converted into a key recovery attack on AES-128 with the same complexity in terms of time and memory,and with a data complexity of 2.The above preiamge attack on the hash mode be directly converted into the preiamge attack on the hash function to generate one-block preimages without padding or three-block second-preimages with padding.