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 34 chosen plaintexts, 2 33.2 encryptions, and 2 36 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 36 chosen plaintexts, 2 30.2 encryptions, and 2 38 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.