Paper 2017/118

A New Structural-Differential Property of 5-Round AES

Lorenzo Grassi, Christian Rechberger, and Sondre Rønjom

Abstract

AES is probably the most widely studied and used block cipher. Also versions with a reduced number of rounds are used as a building block in many cryptographic schemes, e.g. several candidates of the CAESAR competition are based on it. So far, non-random properties which are independent of the secret key are known for up to 4 rounds of AES. These include differential, impossible differential, and integral properties. In this paper we describe a new structural property for up to 5 rounds of AES, differential in nature and which is independent of the secret key, of the details of the MixColumns matrix (with the exception that the branch number must be maximal) and of the SubBytes operation. It is very simple: By appropriate choices of difference for a number of input pairs it is possible to make sure that the number of times that the difference of the resulting output pairs lie in a particular subspace is always a multiple of 8. We not only observe this property experimentally (using a small-scale version of AES), we also give a detailed proof as to why it has to exist. As a first application of this property, we describe a way to distinguish the 5-round AES permutation (or its inverse) from a random permutation with only $2^{32}$ chosen texts that has a computational cost of $2^{35.6}$ look-ups into memory of size $2^{36}$ bytes which has a success probability greater than 99%.

Metadata
Available format(s)
PDF
Publication info
A major revision of an IACR publication in EUROCRYPT 2017
Keywords
Block cipherPermutationAESSecret-Key Distinguisher
Contact author(s)
lorenzo grassi @ iaik tugraz at
History
2017-02-22: revised
2017-02-15: received
See all versions
Short URL
https://ia.cr/2017/118
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/118,
      author = {Lorenzo Grassi and Christian Rechberger and Sondre Rønjom},
      title = {A New Structural-Differential Property of 5-Round AES},
      howpublished = {Cryptology ePrint Archive, Paper 2017/118},
      year = {2017},
      note = {\url{https://eprint.iacr.org/2017/118}},
      url = {https://eprint.iacr.org/2017/118}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.