Paper 2016/592

Subspace Trail Cryptanalysis and its Applications to AES

Lorenzo Grassi, Christian Rechberger, and Sondre Rønjom


We introduce subspace trail cryptanalysis, a generalization of invariant subspace cryptanalysis. With this more generic treatment of subspaces we do no longer rely on specific choices of round constants or subkeys, and the resulting method is as such a potentially more powerful attack vector. Interestingly, subspace trail cryptanalysis in fact includes techniques based on impossible or truncated differentials and integrals as special cases. Choosing AES-128 as the perhaps most studied cipher, we describe distinguishers up to 5-round AES with a single unknown key. We report (and practically verify) competitive key-recovery attacks with very low data-complexity on 2, 3 and 4 rounds of AES. Additionally, we consider AES with a secret S-Box and we present a (generic) technique that allows to directly recover the secret key without finding any information about the secret S-Box. This approach allows to use e.g. truncated differential, impossible differential and integral attacks to find the secret key. Moreover, this technique works also for other AES-like constructions, if some very common conditions on the S-Box and on the MixColumns matrix (or its inverse) hold. As a consequence, such attacks allow to better highlight the security impact of linear mappings inside an AES-like block cipher. Finally, we show that our impossible differential attack on 5 rounds of AES with secret S-Box can be turned into a distinguisher for AES in the same setting as the one recently proposed by Sun, Liu, Guo, Qu and Rijmen at CRYPTO 2016.

Note: App. A - Subspace definitions and example

Available format(s)
Publication info
Published elsewhere. MAJOR revision.FSE 2017
AESInvariant SubspaceSubspace TrailSecret-Key DistinguisherKey-Recovery AttackTruncated DifferentialImpossible Differential\and IntegralSecret S-Box
Contact author(s)
lorenzo grassi @ iaik tugraz at
2017-03-31: last of 7 revisions
2016-06-07: received
See all versions
Short URL
Creative Commons Attribution


      author = {Lorenzo Grassi and Christian Rechberger and Sondre Rønjom},
      title = {Subspace Trail Cryptanalysis and its Applications to AES},
      howpublished = {Cryptology ePrint Archive, Paper 2016/592},
      year = {2016},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.