The Experts below are selected from a list of 3447 Experts worldwide ranked by ideXlab platform
Adi Shamir - One of the best experts on this subject based on the ideXlab platform.
-
improved top down techniques in Differential Cryptanalysis
International Conference on Progress in Cryptology, 2015Co-Authors: Itai Dinur, Orr Dunkelman, Masha Gutman, Adi ShamirAbstract:The fundamental problem of Differential Cryptanalysis is to find the highest entries in the Difference Distribution Table DDT of a given mapping F over n-bit values, and in particular to find the highest diagonal entries which correspond to the best iterative characteristics of F. The standard bottom-up approach to this problem is to consider all the internal components of the mapping along some Differential characteristic, and to multiply their transition probabilities. However, this can provide seriously distorted estimates since the various events can be dependent, and there can be a huge number of low probability characteristics contributing to the same high probability entry. In this paper we use a top-down approach which considers the given mapping as a black box, and uses only its input/output relations in order to obtain direct experimental estimates for its DDT entries which are likely to be much more accurate. In particular, we describe three new techniques which reduce the time complexity of three crucial aspects of this problem: Finding the exact values of all the diagonal entries in the DDT for small values of n, approximating all the diagonal entries which correspond to low Hamming weight differences for large values of n, and finding an accurate approximation for any DDT entry whose large value is obtained from many small contributions. To demonstrate the potential contribution of our new techniques, we apply them to the SIMON family of block ciphers, show experimentally that most of the previously published bottom-up estimates of the probabilities of various Differentials are off by a significant factor, and describe new Differential properties which can cover more rounds with roughly the same probability for several of its members.
-
Differential Cryptanalysis of the Data Encryption Standard
1993Co-Authors: Eli Biham, Adi ShamirAbstract:DES, the Data Encryption Standard, is one of several cryptographic standards. The authors of this text detail their cryptanalytic "attack" upon DES and several other systems, using creative and novel tactics to demonstrate how they broke DES up into 16 rounds of coding. The methodology used offers valuable insights to cryptographers and cryptanalysts alike in creating new encryption standards, strengthening current ones, and exploring new ways to test important data protection schemes. This book introduces a new cryptographic method, called Differential Cryptanalysis, which can be applied to analyze cryptosystems. It describes the Cryptanalysis of DES, deals with the influence of its building blocks on security, and analyzes modified variants. The Differential Cryptanalysis of "Feal" and several other cryptosystems is also described. This method can also be used to cryptanalyze hash functions, as is exemplified by the Cryptanalysis of "Snefru".
-
Differential Cryptanalysis of the full 16 round des
International Cryptology Conference, 1992Co-Authors: Eli Biham, Adi ShamirAbstract:In this paper we develop the first known attack which is capable of breaking the full 16 round DES in less than the 255 complexity of exhaustive search. The data analysis phase computes the key by analyzing about 236 ciphertexts in 237 time. The 236 usable ciphertexts are obtained during the data collection phase from a larger pool of 247 chosen plaintexts by a simple bit repetition criteria which discards more than 99.9% of the ciphertexts as soon as they are generated. While earlier versions of Differential attacks were based on huge counter arrays, the new attack requires negligible memory and can be carried out in parallel on up to 233 disconnected processors with linear speedup. In addition, the new attack can be carried out even if the analyzed ciphertexts are derived from up to 233 different keys due to frequent key changes during the data collection phase. The attack can be carried out incrementally with any number of available ciphertexts, and its probability of success grows linearly with this number (e.g., when 229 usable ciphertexts are generated from a smaller pool of 240 plaintexts, the analysis time decreases to 230 and the probability of success is about 1%).
Eli Biham - One of the best experts on this subject based on the ideXlab platform.
-
related key boomerang and rectangle attacks
Lecture Notes in Computer Science, 2005Co-Authors: Eli Biham, Orr Dunkelman, Nathan KellerAbstract:The boomerang attack and the rectangle attack are two attacks that utilize Differential Cryptanalysis in a larger construction. Both attacks treat the cipher as a cascade of two sub-ciphers, where there exists a good Differential for each sub-cipher, but not for the entire cipher. In this paper we combine the boomerang (and the rectangle) attack with related-key Differentials. The new combination is applicable to many ciphers, and we demonstrate its strength by introducing attacks on reduced-round versions of AES and IDEA. The attack on 192-bit key 9-round AES uses 256 different related keys. The 6.5-round attack on IDEA uses four related keys (and has time complexity of 2 88.1 encryptions). We also apply these techniques to COCONUT98 to obtain a distinguisher that requires only four related-key adaptive chosen plaintexts and ciphertexts. For these ciphers, our results attack larger number of rounds or have smaller complexities then all previously known attacks.
-
Differential Cryptanalysis of the Data Encryption Standard
1993Co-Authors: Eli Biham, Adi ShamirAbstract:DES, the Data Encryption Standard, is one of several cryptographic standards. The authors of this text detail their cryptanalytic "attack" upon DES and several other systems, using creative and novel tactics to demonstrate how they broke DES up into 16 rounds of coding. The methodology used offers valuable insights to cryptographers and cryptanalysts alike in creating new encryption standards, strengthening current ones, and exploring new ways to test important data protection schemes. This book introduces a new cryptographic method, called Differential Cryptanalysis, which can be applied to analyze cryptosystems. It describes the Cryptanalysis of DES, deals with the influence of its building blocks on security, and analyzes modified variants. The Differential Cryptanalysis of "Feal" and several other cryptosystems is also described. This method can also be used to cryptanalyze hash functions, as is exemplified by the Cryptanalysis of "Snefru".
-
Differential Cryptanalysis of the full 16 round des
International Cryptology Conference, 1992Co-Authors: Eli Biham, Adi ShamirAbstract:In this paper we develop the first known attack which is capable of breaking the full 16 round DES in less than the 255 complexity of exhaustive search. The data analysis phase computes the key by analyzing about 236 ciphertexts in 237 time. The 236 usable ciphertexts are obtained during the data collection phase from a larger pool of 247 chosen plaintexts by a simple bit repetition criteria which discards more than 99.9% of the ciphertexts as soon as they are generated. While earlier versions of Differential attacks were based on huge counter arrays, the new attack requires negligible memory and can be carried out in parallel on up to 233 disconnected processors with linear speedup. In addition, the new attack can be carried out even if the analyzed ciphertexts are derived from up to 233 different keys due to frequent key changes during the data collection phase. The attack can be carried out incrementally with any number of available ciphertexts, and its probability of success grows linearly with this number (e.g., when 229 usable ciphertexts are generated from a smaller pool of 240 plaintexts, the analysis time decreases to 230 and the probability of success is about 1%).
Qingju Wang - One of the best experts on this subject based on the ideXlab platform.
-
links among impossible Differential integral and zero correlation linear Cryptanalysis
International Cryptology Conference, 2015Co-Authors: Qingju Wang, Vincent Rijmen, Zhiqiang Liu, Bing Sun, Lei Cheng, Hoda AlkhzaimiAbstract:As two important cryptanalytic methods, impossible Differential and integral Cryptanalysis have attracted much attention in recent years. Although relations among other cryptanalytic approaches have been investigated, the link between these two methods has been missing. The motivation in this paper is to fix this gap and establish links between impossible Differential Cryptanalysis and integral Cryptanalysis.
-
Cryptanalysis of reduced round simon32 and simon48
International Conference on Cryptology in India, 2014Co-Authors: Qingju Wang, Vincent Rijmen, Zhiqiang Liu, Kerem Varici, Yu Sasaki, Yosuke TodoAbstract:SIMON family is one of the recent lightweight block cipher designs introduced by NSA. So far there have been several cryptanalytic results on this cipher by means of Differential, linear and impossible Differential Cryptanalysis. In this paper, we study the security of SIMON32, SIMON48/72 and SIMON48/96 by using integral, zero-correlation linear and impossible Differential Cryptanalysis. Firstly, we present a novel experimental approach to construct the best known integral distinguishers of SIMON32. The small block size, 32 bits, of SIMON32 enables us to experimentally find a 15-round integral distinguisher, based on which we present a key recovery attack on 21-round SIMON32, while previous best results only achieved 19 rounds. Moreover, we attack 20-round SIMON32, 20-round SIMON48/72 and 21-round SIMON48/96 based on 11 and 12-round zero-correlation linear hulls of SIMON32 and SIMON48 respectively. Finally, we propose new impossible Differential attacks which improve the previous impossible Differential attacks. Our analysis shows that SIMON maintains enough security margin.
-
Differential and linear Cryptanalysis using mixed integer linear programming
International Conference on Information Security and Cryptology, 2011Co-Authors: Nicky Mouha, Qingju Wang, Dawu Gu, Bart PreneelAbstract:Differential and linear Cryptanalysis are two of the most powerful techniques to analyze symmetric-key primitives. For modern ciphers, resistance against these attacks is therefore a mandatory design criterion. In this paper, we propose a novel technique to prove security bounds against both Differential and linear Cryptanalysis. We use mixed-integer linear programming (MILP), a method that is frequently used in business and economics to solve optimization problems. Our technique significantly reduces the workload of designers and cryptanalysts, because it only involves writing out simple equations that are input into an MILP solver. As very little programming is required, both the time spent on Cryptanalysis and the possibility of human errors are greatly reduced. Our method is used to analyze Enocoro-128v2, a stream cipher that consists of 96 rounds. We prove that 38 rounds are sufficient for security against Differential Cryptanalysis, and 61 rounds for security against linear Cryptanalysis. We also illustrate our technique by calculating the number of active S-boxes for AES.
Meiqin Wang - One of the best experts on this subject based on the ideXlab platform.
-
impossible Differential Cryptanalysis of the lightweight block ciphers tea xtea and hight
International Conference on Cryptology in Africa, 2012Co-Authors: Jiazhe Chen, Meiqin Wang, Bart PreneelAbstract:TEA, XTEA and HIGHT are lightweight block ciphers with 64-bit block sizes and 128-bit keys. The round functions of the three ciphers are based on the simple operations XOR, modular addition and shift/rotation. TEA and XTEA are Feistel ciphers with 64 rounds designed by Needham and Wheeler, where XTEA is a successor of TEA, which was proposed by the same authors as an enhanced version of TEA. HIGHT, which is designed by Hong et al., is a generalized Feistel cipher with 32 rounds. These block ciphers are simple and easy to implement but their diffusion is slow, which allows us to find some impossible properties. This paper proposes a method to identify the impossible Differentials for TEA and XTEA by using the weak diffusion, where the impossible Differential comes from a bit contradiction. Our method finds a 14-round impossible Differential of XTEA and a 13-round impossible Differential of TEA, which result in impossible Differential attacks on 23-round XTEA and 17-round TEA, respectively. These attacks significantly improve the previous impossible Differential attacks on 14-round XTEA and 11-round TEA given by Moon et al. from FSE 2002. For HIGHT, we improve the 26-round impossible Differential attack proposed by Ozen et al.; an impossible Differential attack on 27-round HIGHT that is slightly faster than the exhaustive search is also given.
-
zero correlation linear Cryptanalysis with reduced data complexity
Fast Software Encryption, 2012Co-Authors: Andrey Bogdanov, Meiqin WangAbstract:Zero correlation linear Cryptanalysis is a novel key recovery technique for block ciphers proposed in [5]. It is based on linear approximations with probability of exactly 1/2 (which corresponds to the zero correlation). Some block ciphers turn out to have multiple linear approximations with correlation zero for each key over a considerable number of rounds. Zero correlation linear Cryptanalysis is the counterpart of impossible Differential Cryptanalysis in the domain of linear Cryptanalysis, though having many technical distinctions and sometimes resulting in stronger attacks. In this paper, we propose a statistical technique to significantly reduce the data complexity using the high number of zero correlation linear approximations available. We also identify zero correlation linear approximations for 14 and 15 rounds of TEA and XTEA. Those result in key-recovery attacks for 21-round TEA and 25-round XTEA, while requiring less data than the full code book. In the single secret key setting, these are structural attacks breaking the highest number of rounds for both ciphers. The findings of this paper demonstrate that the prohibitive data complexity requirements are not inherent in the zero correlation linear Cryptanalysis and can be overcome. Moreover, our results suggest that zero correlation linear Cryptanalysis can actually break more rounds than the best known impossible Differential Cryptanalysis does for relevant block ciphers. This might make a security re-evaluation of some ciphers necessary in the view of the new attack.
Zhiqiang Liu - One of the best experts on this subject based on the ideXlab platform.
-
links among impossible Differential integral and zero correlation linear Cryptanalysis
International Cryptology Conference, 2015Co-Authors: Qingju Wang, Vincent Rijmen, Zhiqiang Liu, Bing Sun, Lei Cheng, Hoda AlkhzaimiAbstract:As two important cryptanalytic methods, impossible Differential and integral Cryptanalysis have attracted much attention in recent years. Although relations among other cryptanalytic approaches have been investigated, the link between these two methods has been missing. The motivation in this paper is to fix this gap and establish links between impossible Differential Cryptanalysis and integral Cryptanalysis.
-
Cryptanalysis of reduced round simon32 and simon48
International Conference on Cryptology in India, 2014Co-Authors: Qingju Wang, Vincent Rijmen, Zhiqiang Liu, Kerem Varici, Yu Sasaki, Yosuke TodoAbstract:SIMON family is one of the recent lightweight block cipher designs introduced by NSA. So far there have been several cryptanalytic results on this cipher by means of Differential, linear and impossible Differential Cryptanalysis. In this paper, we study the security of SIMON32, SIMON48/72 and SIMON48/96 by using integral, zero-correlation linear and impossible Differential Cryptanalysis. Firstly, we present a novel experimental approach to construct the best known integral distinguishers of SIMON32. The small block size, 32 bits, of SIMON32 enables us to experimentally find a 15-round integral distinguisher, based on which we present a key recovery attack on 21-round SIMON32, while previous best results only achieved 19 rounds. Moreover, we attack 20-round SIMON32, 20-round SIMON48/72 and 21-round SIMON48/96 based on 11 and 12-round zero-correlation linear hulls of SIMON32 and SIMON48 respectively. Finally, we propose new impossible Differential attacks which improve the previous impossible Differential attacks. Our analysis shows that SIMON maintains enough security margin.