Impossible Differential Cryptanalysis on QuadriAES and SemiAES

Abstract

Introduction: Impossible differential cryptanalysis is a powerful method in cryptanalysis that leverages differentials that cannot occur to eliminate incorrect key guesses, effectively reducing the key space. While this technique has proven effective, its application to AES typically requires substantial memory, up to 128 GB, making it impractical for many aspiring cryptanalysts. To address this challenge, this paper introduces two new derivations of the AES algorithm, named QuadriAES and SemiAES, which operate on smaller plaintext blocks of 32 bits and 64 bits, respectively.

Objectives: The primary objective of this study is to employ impossible differential cryptanalysis on these new AES derivations, which feature significantly reduced memory requirements. Specifically, the study aims to introduce QuadriAES and SemiAES, apply impossible differential cryptanalysis to these derivations, optimize the attack process to limit memory usage to 6 GB, and evaluate the success rates and efficiency of the proposed methods.

Methods: In this study, we applied impossible differential cryptanalysis to a 5-round version of QuadriAES-32 and SemiAES-64. Our approach encompassed several significant optimizations. These included implementing a concatenated pairs algorithm to minimize writing operations, which was necessitated by limited memory, leveraging multiple output differences to increase the number of desired pairs, and utilizing multi-threading to enhance the efficiency of the attack execution. The attack process entailed generating random plaintext pairs, encrypting them with a randomly selected initial key, collecting the desired pairs, and subsequently leveraging them to eliminate incorrect keys and reduce the key space.

Results: The successful execution of impossible differential cryptanalysis on QuadriAES-32 and SemiAES-64 has demonstrated the feasibility of conducting attacks using only 6 GB of RAM, compared to other implementations on different AES variants that required up to 128 GB of memory. For QuadriAES, the attack involved 1000 concatenated pairs, 10 threads, two output differences, two first-round output differences, and 8 chunks of 5 million plaintext pairs each, resulting in a total of 40 million plaintext pairs. The attack took approximately 3 hours to complete. Similarly, the attack on SemiAES utilized 1000 concatenated pairs and 10 threads, along with four output differences, four first-round output differences, and 11 chunks of 25 million plaintext pairs each, resulting in a total of 275 million plaintext pairs. This attack took nearly 29 hours to execute.

Conclusions: This study implements impossible differential cryptanalysis on two newly proposed smaller derivations of the AES algorithm, namely QuadriAES and SemiAES. To overcome the memory requirements, we used the concatenated pairs algorithm and an incremental implementation of the attack. Additionally, we examined the effect of using multiple output differences and first-round output differences on the success rate. We also suggested multi-threading to enhance execution efficiency. This research not only expands the understanding of AES security but also provides practical insights for aspiring cryptanalysts aiming to employ advanced cryptanalytic techniques on widely used encryption standards. Future work will focus on extending these methods to other AES derivations and eventually to the standard AES algorithm.