The ISC International Journal of Information Security

Abstract This paper describes a fast exhaustive search preimage attack on AIM2, an improved version of the one-way function AIM, proposed to address algebraic vulnerabilities found in its predecessor. Our attack transforms the polynomial system describing AIM2 over F2λ to a boolean polynomial system over F2, allowing for an exhaustive search by guessing input bits and solving a resulting linear system. Solving the whole system is not necessary for most incorrect guesses, and use of Gray code helps optimizing the iteration over all possible guesses. Our results show that the complexity of exhaustive search on AIM2, especially AIM2-I and AIM2-III is lower than previously estimated, though still higher than that of AES.