Eli Biham, Vladimir Furman · 2000
Twofish is one of the AES finalists. The best up-to-date analysis of Twofish was presented by its designers, whose complexity on 6-round Twofish with 128-bit keys is 4.6 2128 one-round computations. In this paper we present m improvement of the attack on 6-round Twofish, whose complexity is 1.84 2128 one-round computations. For other key sizes our results have the complexity 13. 2 it one-round computations for 192-bit keys md 24.2. 2192 one-round computations for 256-bit keys. For 7-round Twofish, the designers mentioned m attack, md estimated its complexity to be about 22sc simple steps for 256-bit keys md for other key sizes have a complexities that exceed exhaustive search. We present an improvement of the attack on 7-round Twofish, whose complexity is 222'48 one-round computations for 256-bit keys. We also show, for the first time, that this attack is faster thm exhaustive search for 192-bit keys for which it breaks 7-round Twofish in 2.2192 one-round computations, while exhaustive search takes 7. 2192 .
Cited by 0
Patrick Derbez, Marie Euler · Lecture notes in computer science · 2026
Cited by 0Open access
Huiqin Xie, Qiqing Xia, Ke Wang et al. · Mathematics · 2024
Due to the superiority of quantum computing, traditional cryptography is facing a severe threat. This makes the security evaluation of cryptographic systems in quantum attack models both significant and urgent. For symmetric ciphers, the security analysis heavily relies on cryptanalysis tools. Thus, exploring the use of quantum algorithms in traditional cryptanalysis tools has garnered considerable attention. In this study, we utilize quantum algorithms to improve impossible differential attacks and design two quantum automated tools to search for impossible differentials. The proposed quantum algorithms exploit the idea of miss-in-the-middle and the properties of truncated differentials. We rigorously prove their validity and calculate the quantum resources required for their implementation. Compared to the existing classical automated cryptanalysis, the proposed quantum tools have the advantage of accurately characterizing S-boxes while only requiring polynomial complexity, and can take into consideration the impact of the key schedules in a single-key model.
Cited by 0Open access
Yukiyasu Tsunoo, Etsuko Tsujihara, Maki Shigeri et al. · 2008
This paper reports impossible differential cryptanalysis on the 128-bit block cipher CLEFIA that was proposed in 2007. It is known that there are the 9-round impossible differentials in CLEFIA. This paper presents the several results of impossible differential attacks using multiple impossible differentials. For key lengths of 128, 192 and 256 bits, it is possible to apply impossible differential attacks to 12-round, 13-round and 14-round CLEFIA. For the case of a 128-bit key, this attack is the most efficient compared with previous results. For key lengths of 192 and 256 bits, the numbers of chosen plaintexts are the least.
Cited by 22
Dmitriy Zakharov, Марина Александровна Пудовкина · Journal of Computer Virology and Hacking Techniques · 2023
Cited by 0
Emanuele Bellini, Alessandro De Piccoli, David Gérault et al. · Lecture notes in computer science · 2026
Cited by 0
Qing Ling, Tingting Cui, Hongtao Hu et al. · IACR Transactions on Symmetric Cryptology · 2024
Impossible differential cryptanalysis is very important in the field of symmetric ciphers. Currently, there are many automatic search approaches to find impossible differentials. However, these methods have two underlying assumptions: Markov cipher assumption and key independence assumption. Actually, these two assumptions are not true in ARX ciphers, especially lightweight ones. In this paper, we study the impossible differentials in ARX cipher under weak keys for the first time. Firstly, we propose several accurate difference propagation properties on consecutive two and three modular additions. Then, these properties are applied to four typical local constructions composed of two consecutive modular additions, two modular additions with a rotation operation, xoring secret key or constant in the middle, to find impossible differentials under weak keys or special constants. What’s more, we propose a more accurate difference propagation property on three consecutive modular additions. It can be used to find impossible differentials on more complex local constructions under weak keys or special constants. In practical ciphers, these impossible differentials on local constructions can be used to find contradictions. Lastly, combining our new findings with traditional automatic search methods for impossible differentials, we propose a framework to find impossible differentials in ARX ciphers under weak keys. As applications, we apply the framework to SPECK-32/64, LEA and CHAM-64/128. As a result, we find two 8-round impossible differentials for SPECK-32/64 under 260 weak keys, and one 11-round impossible differential for LEA under 2k−1 weak keys, where k is the key size. These impossible differentials can start from any round. Furthermore, we find two 22-round impossible differentials for CHAM-64/128 under 2127 weak keys starting from certain rounds. As far as we know, all these impossible differentials are longer than previous ones.
Cited by 3Open access
Qian Wang, Chenhui Jin · Designs Codes and Cryptography · 2017
Cited by 12
Ting Cui, Chenhui Jin, Jing Ma · Chinese Journal of Electronics · 2018
Impossible differential cryptanalysis is one of the most powerful attacks against modern block ciphers. In most cases, the resistance of a block cipher against impossible differential cryptanalysis can be measured by the length of the longest impossible differentials. By taking a closer look into the round function, we present a new method to find longer impossible differentials of wordoriented generalized Feistel structures. We conclude the existence of impossible differentials by the nonzero points of the XOR-ed masked differences in the middle round. This method uses differential style and its nonzero point to find the impossible differential, which is much easier than the classical impossible differential searching method. By applying our method, we can find several longest impossible differentials of some famous block cipher structures with SP (Substitution-permutation) round functions. If some extra conditions of the round function are taken into consideration (e.g. the permutation layer is designed as binary matrix or some sparse matrix), longer impossible differentials could be achieved by our method.
Cited by 4
X. Hu, Lin Jiao, Yongqiang Li et al. · IEEE Transactions on Information Theory · 2025
Impossible differential cryptanalysis and impossible polytopic cryptanalysis are among the most effective techniques for evaluating the security of block ciphers. However, previous automatic search methods for their distinguishers—dimpossible differentials and impossible polytopic transitions—neither account for the influence of the key schedule in single-key settings nor are applicable to block ciphers featuring large S-boxes, variable rotations, or key-dependent permutations. Furthermore, existing approaches fail to search for clusters of impossible differentials when all details of a block cipher are considered. In contrast to previous methods that focus solely on the propagation of differences or s-difference, we redefine impossible differentials and impossible (<italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">s</i> + 1)-polytopic transitions based on state propagation. This redefinition enables us to overcome the limitations inherent in earlier methodologies. Theoretically, we demonstrate that traditional definitions of impossible differentials and impossible (<italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">s</i> + 1)-polytopic transitions correspond to subsets of our redefined concepts, which offer broader analytical perspectives. Technically, we reformulate the automatic search model and develop an SAT-based tool to efficiently evaluate our redefined impossible differentials and impossible (<italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">s</i> + 1)-polytopic transitions. Building upon this foundational search method, we construct a comprehensive framework for detecting clusters of impossible differentials and impossible (<italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">s</i>+1)-polytopic transitions. This framework not only fully incorporates the details and differential properties of block ciphers but is also applicable to those employing large S-boxes while considering the full linear layer. As a result, we derive new impossible differentials for GIFT64, PRINTcipher48/96, MISTY1, RC5-32/64/128 and SPECK, as well as new clusters of impossible differentials for SPECK, DES and ARIA. In assessing resistance against impossible differentials, we apply our method to evaluate the security of GIFT64, PRINTcipher48/96, MISTY1, SPECK, SIMON, and DES while accounting for all details of the block ciphers. Moreover, we propose acceleration strategies and apply them to evaluate the security of MISTY1 and AES-128. Notably, we prove that no 5-round impossible differentials with one active input byte and one active output byte exist for AES-128, even when considering the dependencies among three consecutive round keys. Finally, in exploring new impossible (<italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">s</i>+1)-polytopic transition, we apply our approach to PRINTcipher48, GIFT64, RC5-32/64 and SIMON32-64, successfully yielding the corresponding distinguishers for the first time.
Cited by 0
Guoyong Han, Wenying Zhang, Hongluan Zhao · KSII Transactions on Internet and Information Systems · 2019
Impossible differential cryptanalysis is an essential cryptanalytic technique and its key point is whether there is an impossible differential path. The main factor of influencing impossible differential cryptanalysis is the length of the rounds of the impossible differential trail because the attack will be more close to the real encryption algorithm with the number becoming longer. We provide the upper bound of the longest impossible differential trails of several important block ciphers. We first analyse the national standard of the Russian Federation in 2015, Kuznyechik, which utilizes the 16-byte LFSR to achieve the linear transformation. We conclude that there is no any 3-round impossible differential trail of the Kuznyechik without the consideration of the specific S-boxes. Then we ascertain the longest impossible differential paths of several other important block ciphers by using the matrix method which can be extended to many other block ciphers. As a result, we show that, unless considering the details of the S-boxes, there is no any more than or equal to 5-round, 7-round and 9-round impossible differential paths for KLEIN, Midori64 and MIBS respectively.
Cited by 6Open access
Weiwei Cao, Wentao Zhang, Chunning Zhou · Lecture notes in computer science · 2023
Cited by 3
Yong Liu, Zejun Xiang, Siwei Chen et al. · Lecture notes in computer science · 2023
Cited by 12
Tingting Cui, Shiyao Chen, Kai Fu et al. · Science China Information Sciences · 2020
Cited by 19
Roman Astrakhantsev, Andrey Chuhno, Андрей Александрович Дмух et al. · Journal of Computer Virology and Hacking Techniques · 2024
Cited by 0
Jun He, Xuan Shen, Guoqiang Liu · Security and Communication Networks · 2021
Impossible differential cryptanalysis and zero-correlation linear cryptanalysis are two kinds of most effective tools for evaluating the security of block ciphers. In those attacks, the core step is to construct a distinguisher as long as possible. In this paper, we focus on the security of New Structure III, which is a kind of block cipher structure with excellent resistance against differential and linear attacks. While the best previous result can only exploit one-round linear layer P to construct impossible differential and zero-correlation linear distinguishers, we try to exploit more rounds to find longer distinguishers. Combining the Miss-in-the-Middle strategy and the characteristic matrix method proposed at EUROCRYPT 2016, we could construct 23-round impossible differentials and zero-correlation linear hulls when the linear layer P satisfies some restricted conditions. To our knowledge, both of them are 1 round longer than the best previous works concerning the two cryptanalytical methods. Furthermore, to show the effectiveness of our distinguishers, the linear layer of the round function is specified to the permutation matrix of block cipher SKINNY which was proposed at CRYPTO 2016. Our results indicate that New Structure III has weaker resistance against impossible differential and zero-correlation linear attacks, though it possesses good differential and linear properties.
Cited by 0Open access
Senpeng Wang, Dengguo Feng, Tairong Shi et al. · IEEE Transactions on Information Theory · 2024
How to evaluate the security of Substitution-Permutation Network (SPN) block ciphers against impossible differential (ID) cryptanalysis is a valuable problem. In this paper, a series of methods for bounding the length of IDs of SPN block ciphers are proposed. Firstly, we propose the definitions of minimal representative set and partition table. Therefore, an improved partition-first implementation strategy for bounding the length of IDs is given. Secondly, we introduce a new definition of ladder and propose the ladder-first implementation strategy for bounding the length of IDs. In order to be able to apply ladder-first implementation strategy in practice, the methods for determining ladders and integrating a ladder into searching models are given. Thirdly, a heuristic algorithm called dynamic-ladder-partition implementation strategy is proposed. According to our experimental results, dynamic-ladder-partition implementation strategy is more suitable for SPN ciphers whose number of elements in partition tables is little. Fourthly, rotation-equivalence ID sets of ciphers are explored to reduce the number of models that need to be considered. As applications, we show that 9-round PRESENT, 5-round AES, 6-round Rijndael-160, 7-round Rijndael-192, 7-round Rijndael-224 and 7-round Rijndael-256 do not have any ID under the sole assumption that the round keys are uniformly random. What’s more, we obtain that 8-round GIFT-64, 12-round GIFT-128 and 14-round SKINNY-128 do not have any ID under the assumptions that GIFT and SKINNY are Markov ciphers and the round keys are uniformly random. Our methods fill crucial gaps on bounding the length of IDs with the differential properties of S-boxes considered. They enhance our confidence in the security and are valuable, especially for designers.
Cited by 1
Xuan Shen, Ruilin Li, Bing Sun et al. · Lecture notes in computer science · 2017
Cited by 4
Ya HAN · SHILAP Revista de lepidopterología · 2017
Firstly,the differences and linear masks propagation equations of ARX ciphers were established.Secondly,the propagation equations were solved by SAT solver and judged valid or not.Finally,differences and linear masks were traversed to search impossible differentials and zero-correlation linear hulls automatically.The proposed algorithm was applied to TEA,XTEA and SIMON family block ciphers.The optimal impossible differentials and zero-correlation linear hulls for TEA,XTEA and SIMON family block ciphers were proposed.Moreover，with DDT and LAT,the algorithm can also be applied to search the impossible differentials and zero-correlation linear hulls of S-box based block ciphers.
Cited by 0Open access
Camellia, Wenling Wu, Wentao Zhang et al. · 2008
Abstract. This paper studies the security of the block ciphers ARIA and Camellia against impossible differential cryptanalysis. Our work improves the best impossible differential cryptanalysis of ARIA and Camellia known so far. The designers of ARIA expected no impossible differentials exist for 4-round ARIA. However, we found some nontrivial 4-round impossible differentials, which may lead to a possible attack on 6-round ARIA. Moreover, we found some nontrivial 8-round impossible differentials for Camellia, whereas only 7-round impossible differentials were previously known. By using the 8-round impossible differentials, we presented an attack on 12-round Camellia without F L/F L −1 layers.
Cited by 0