Examples of differential multicollisions for 13 and 14 rounds of AES-256.
Alex Biryukov, Dmitry Khovratovich, Ivica Nikolić · 2009
Here we present practical differential q-multicollisions for AES-256. In our paper [1] q-multicollisions are found with complexity q · 2 67. We relax conditions on the plaintext difference ∆P allowing some bytes to vary and find multicollisions for 13 and 14 round AES with complexity q · 2 37. Even with the relaxation there is still a large complexity gap between our algorithm and the lower bound that we have proved in Lemma 1. Moreover we believe that in practice finding even two fixed-difference collisions for a good cipher would be very challenging. The multicollision sets, presented in the tables below, are obtained using the technique described in our original paper. Our search algorithm for 13 and 14 rounds of AES-256 can be described as: 1. Build a differential trail for 14 rounds of AES-256. The trail specifies the admissible values of the active S-boxes in these rounds. 2. Using the triangulation algorithm produce one pair that satisfies all the conditions for the S-boxes in the rounds 3–7. 3. If this pair satisfies the conditions for the rounds 8-14 as well then goto step