Impossible 4-Tuple Attack: A New Mixture-Based Cryptanalysis Applied to Reduced-Round AES-128

Mixture differential cryptanalysis is a powerful technique for evaluating the robustness of Substitution-Permutation Network (SPN)-structured block ciphers, including the Advanced Encryption Standard (AES). In this work, we propose a novel mixture-based cryptanalysis and apply it successfully to reduced-round AES-128 to recover the master key. Accordingly, we initially define several 4-tuple categories. Based on these definitions, we construct a new distinguisher, referred to as the ‘‘impossible 4-tuple property.’’ Exploiting this property enables us to recover the master key using a new technique called ‘‘impossible 4-tuple cryptanalysis.’’ To evaluate the effectiveness of the proposed method, we apply impossible 4-tuple cryptanalysis to the 5-round AES-128. We first introduce the proposed impossible 4-tuple property, which covers four rounds of AES. Subsequently, impossible 4-tuple cryptanalysis is applied to recover the 5-round AES-128 master key using 2<sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">34</sup> chosen plaintexts, 2<sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">33.2</sup> encryptions, and 2<sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">36</sup> bytes of memory. Furthermore, we propose a specific version of the method, "fast impossible 4-tuple cryptanalysis," which utilizes a time-memory trade-off. This version can recover the master key using 2<sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">36</sup> chosen plaintexts, 2<sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">30.2</sup> encryptions, and 2<sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">38</sup> bytes of memory, making it the fastest attack among differential-based and mixture-based cryptanalysis methods applied to 5-round AES. Finally, to demonstrate the validity of the proposed impossible 4-tuple cryptanalysis methods, a simplified version of the methods was applied to the miniAES algorithm. Accordingly, two corresponding open-source tools, ‘‘miniAES_Typical_Imp_4tuple.py’’ and ‘‘miniAES_Fast_Imp_4tuple.py,’’ were developed to recover the master key of the miniAES block cipher.