IACR News item: 24 March 2023
Tomer Ashur, Erik Takke
ePrint Report
In SAC’14, Biham and Carmeli presented a novel attack on DES, involving
a variation of Partitioning Cryptanalysis. This was further extended in ToSC’18
by Biham and Perle into the Conditional Linear Cryptanalysis in the context of
Feistel ciphers. In this work, we formalize this cryptanalytic technique for block
ciphers in general and derive several properties. This conditional approximation is
then used to approximate the inv : GF(2^8) → GF(2^8) : x → x^254 function which
forms the only source of non-linearity in the AES. By extending the approximation to
encompass the full AES round function, a linear distinguisher for four-round AES in
the known-plaintext model is constructed; the existence of which is often understood
to be impossible. We furthermore demonstrate a key-recovery attack capable of
extracting 32 bits of information in 4-round AES using 2^125.62 data and time. In
addition to suggesting a new approach to advancing the cryptanalysis of the AES,
this result moreover demonstrates a caveat in the standard interpretation of the
Wide Trail Strategy — the design framework underlying many SPN-based ciphers
published in recent years.
Additional news items may be found on the IACR news page.