Cryptology ePrint Archive: Report 2016/592

Subspace Trail Cryptanalysis and its Applications to AES

Lorenzo Grassi and Christian Rechberger and Sondre RÝnjom

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.

Category / Keywords: AES, Invariant Subspace, Subspace Trail, Secret-Key Distinguisher, Key-Recovery Attack, Truncated Differential, Impossible Differential\and Integral, Secret S-Box

Original Publication (with major differences): FSE 2017

Date: received 6 Jun 2016, last revised 22 Mar 2017

Contact author: lorenzo grassi at iaik tugraz at

Available format(s): PDF | BibTeX Citation

Note: Acknowledgments updated

Version: 20170322:162745 (All versions of this report)

Short URL: ia.cr/2016/592

Discussion forum: Show discussion | Start new discussion


[ Cryptology ePrint archive ]