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 Substitution-Permutation Networks and derive several properties. A conditional approximation is then used to approximate the \({ \texttt {inv}}:GF(2^8)\rightarrow GF(2^8):x\mapsto x^{254}\) function which forms the only source of nonlinearity in the AES. By extending the approximation to encompass the full AES round function, a linear distinguisher for 4-round AES using \(2^{125.72}\) known-plaintexts is constructed; the existence of which is often understood to be impossible. We furthermore demonstrate how to recover 32 key bits directly from this distinguisher with no data or time overhead. 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.
