New Representations of the AES Key Schedule

Gaëtan Leurent; Clara Pernot

Paper 2020/1253

New Representations of the AES Key Schedule

Gaëtan Leurent

, French Institute for Research in Computer Science and Automation

Clara Pernot, French Institute for Research in Computer Science and Automation

Abstract

In this paper we present a new representation of the AES key schedule, with some implications to the security of AES-based schemes. In particular, we show that the AES-128 key schedule can be split into four independent parallel computations operating on 32-bit chunks, up to linear transformation. Surprisingly, this property has not been described in the literature after more than 20 years of analysis of AES. We show two consequences of our new representation, improving previous cryptanalysis results of AES-based schemes. First, we observe that iterating an odd number of key schedule rounds results in a permutation with short cycles. This explains an observation of Khairallah on mixFeed, a second-round candidate in the NIST lightweight competition. Our analysis actually shows that his forgery attack on mixFeed succeeds with probability 0.44 (with data complexity 220GB), breaking the scheme in practice. The same observation also leads to a novel attack on ALE, another AES-based AEAD scheme. Our new representation also gives efficient ways to combine information from the first subkeys and information from the last subkeys, in order to reconstruct the corresponding master key. This results in small improvements to previous attacks: we improve impossible differential attacks against several variants of AES (and Rijndael), and a square attack against AES-192.

Note: New applications: Impossible differential attack on Rinjdael-256, Square attack on AES-192

Metadata

Available format(s): PDF
Category: Secret-key cryptography
Publication info: A major revision of an IACR publication in EUROCRYPT 2021
Keywords: AES Key schedule mixFeed ALE Impossible differential attack Square attack
Contact author(s): gaetan leurent @ inria fr
clara pernot @ inria fr
History: 2023-06-24: revised; 2020-10-14: received; See all versions
Short URL: https://ia.cr/2020/1253
License: CC BY

BibTeX

@misc{cryptoeprint:2020/1253,
      author = {Gaëtan Leurent and Clara Pernot},
      title = {New Representations of the AES Key Schedule},
      howpublished = {Cryptology ePrint Archive, Paper 2020/1253},
      year = {2020},
      note = {\url{https://eprint.iacr.org/2020/1253}},
      url = {https://eprint.iacr.org/2020/1253}
}