Subspace Trail Cryptanalysis and its Applications to AES

Authors

  • Lorenzo Grassi Institute of Applied Information Processing and Communications (IAIK), Graz University of Technology, Graz, Austria
  • Christian Rechberger Department of Applied Mathematics and Computer Science (DTU Compute), Technical University of Denmark, Kongens Lyngby, Denmark; Institute of Applied Information Processing and Communications (IAIK), Graz University of Technology, Graz, Austria
  • Sondre Rønjom Norwegian National Security Authority (NSM), Sandvika, Norway;Department of Informatics, University of Bergen, Bergen, Norway

DOI:

https://doi.org/10.13154/tosc.v2016.i2.192-225

Keywords:

AES, Invariant Subspace, Subspace Trail, Secret-Key Distinguisher, Key-Recovery Attack, Truncated Differential, Impossible Differential, Integral, Secret S-Box

Abstract

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

Downloads

Published

2017-02-03

Issue

Section

Articles

How to Cite

Subspace Trail Cryptanalysis and its Applications to AES. (2017). IACR Transactions on Symmetric Cryptology, 2016(2), 192-225. https://doi.org/10.13154/tosc.v2016.i2.192-225