Paper 2019/852

Weak-Key Subspace Trails and Applications to AES

Lorenzo Grassi and Gregor Leander and Christian Rechberger and Cihangir Tezcan and Friedrich Wiemer

Abstract

Invariant subspaces (Crypto'11) and subspace trails (FSE'17) are two related recent cryptanalytic approaches that led to new results on, e. g. PRINTCipher and AES. We extend the invariant subspace approach to allow for different subspaces in every round, something that so far only the subspace trail approach and a generalization for invariant subspace and invariant set attacks (Asiacrypt'18) were able to do. For an easier detection, we provide an algorithm which finds these weak-key subspace trails. Using this framework, we perform an extensive analysis of weak-key distinguishers (in the single-key setting) for AES with several key schedule variants. Among others, we show that for the new key-schedule proposed at ToSC/FSE'18 - which is faster than the standard key schedule and ensures a higher number of active S-Boxes - it is possible to set up an invariant subspace distinguisher for any number of rounds. Finally, we describe a property for full AES-128 and AES-256 in the chosen-key setting with complexity 2^64 without requiring related keys. These chosen-key distinguishers are set up by exploiting the multiple-of-n property introduced at Eurocrypt'17, adapted to the case of AES instantiated with weak-keys.