||A Collision Attack on a Double-Block-Length Compression Function Instantiated with Round-Reduced AES-256
Chen, Jiageng ,
Hirose, Shoichi ,
Kuwakado, HidenoriMiyaji, Atsuko
Lecture Notes in Computer Science
285 , 2015-03-17 , Springer
This paper presents the first non-trivial collision attack on the double-block-length compression function presented at FSE 2006 instantiated with round-reduced AES-256: f_0(h_0∥h_1,M)∥f_1(h_0∥h_1,M) such that f_0(h_0∥h_1,M) =E_<h1∥M>(h_0)⊕h_0, f_1(h_0∥h_1,M) =E_<h_1∥M>(h_0⊕c)⊕h_0⊕c, where ∥ represents concatenation, E is AES-256 and c is a non-zero constant. The proposed attack is a free-start collision attack. It uses the rebound attack proposed by Mendel et al. It finds a collision with time complexity 2^8 , 2^<64> and 2^<120> for the instantiation with 6-round, 8-round and 9-round AES-256, respectively. The space complexity is negligible. The attack is effective against the instantiation with 6-/8-round AES-256 if the 16-byte constant c has a single non-zero byte. It is effective against the instantiation with 9-round AES-256 if the constant c has four non-zero bytes at some specific positions.
17th International Conference, Seoul, South Korea, December 3-5, 2014, Revised Selected Papers