Paper 2023/398

A New Linear Distinguisher for Four-Round AES

Abstract

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 $inv: GF(2^8) \to GF(2^8) : x \to 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 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.

Note: Most significantly, we updated Section 5.3 to leverage Blondeau and Nyberg's data complexity formula, achieving a slightly more accurate bound for the distinguishing attack. Moreover, we expanded the related works section, rewrote and reorganized several sections to improve the readability and flow of the paper, and updated the discussion and conclusion.