Cryptology ePrint Archive: Report 2009/242
Examples of differential multicollisions for 13 and 14 rounds of AES-256
Alex Biryukov and Dmitry Khovratovich and Ivica Nikolić
Abstract: Here we present practical differential $q$-multicollisions for AES-256, which can be tested on any implementation of AES-256. In our paper "Distinguisher and Related-Key Attack on the Full AES-256" $q$-multicollisions are found with complexity $q\cdot 2^{67}$. We relax conditions on the plaintext
difference $\Delta_P$ allowing some bytes to vary and find multicollisions for 13 and 14 round AES with complexity $q\cdot 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.
Category / Keywords: secret-key cryptography / AES, chosen key distinguisher,
Date: received 28 May 2009
Contact author: khovratovich at gmail com
Available format(s): PDF | BibTeX Citation
Version: 20090530:124029 (All versions of this report)
Short URL: ia.cr/2009/242
[ Cryptology ePrint archive ]