Using a structural analysis, we show that the full AES-128 cannot be proven secure unless the exact coefficients of the MDS matrix and the S-Box differential properties are taken into account since its structure is vulnerable to a related-key differential attack. We then exhibit a chosen-key distinguisher for AES-128 reduced to 9 rounds, which solves an open problem of the symmetric community. We obtain these results by revisiting algorithmic theory and graph-based ideas to compute all the best differential characteristics in SPN ciphers, with a special focus on AES-like ciphers subject to related-keys. We use a variant of Dijkstra's algorithm to efficiently find the most efficient related-key attacks on SPN ciphers with an algorithm linear in the number of rounds.
Category / Keywords: secret-key cryptography / SPN, Block Cipher, AES, Related-Key, Chosen-Key Publication Info: Extended version of a CRYPTO 2013 paper Date: received 10 Jun 2013 Contact author: Jeremy Jean at ens fr Available format(s): PDF | BibTeX Citation Version: 20130610:201646 (All versions of this report) Discussion forum: Show discussion | Start new discussion