The Experts below are selected from a list of 255 Experts worldwide ranked by ideXlab platform
Xiaoyun Wang - One of the best experts on this subject based on the ideXlab platform.
-
FSE - Improved Linear Hull Attack on Round-Reduced Simon with Dynamic Key-Guessing Techniques
Fast Software Encryption, 2016Co-Authors: Huaifeng Chen, Xiaoyun WangAbstract:Simon is a lightweight block cipher family proposed by NSA in 2013. It has drawn many cryptanalysts' attention and varieties of cryptanalysis results have been published, including differential, Linear, impossible differential, integral cryptanalysis and so on. In this paper, we give the improved Linear attacks on all reduced versions of Simon with dynamic key-guessing technique, which was proposed to improve the differential attack on Simon recently. By establishing the boolean function of parity bit in the Linear Hull distinguisher and reducing the function according to the property of AND operation, we can guess different subkeys or equivalent subkeys for different situations, which decrease the number of key bits involved in the attack and decrease the time complexity in a further step. As a result, 23-round Simon32/64, 24-round Simon48/72, 25-round Simon48/96, 30-round Simon64/96, 31-round Simon64/128, 37-round Simon96/96, 38-round Simon96/144, 49-round Simon128/128, 51-round Simon128/192 and 53-round Simon128/256 can be attacked. As far as we know, our attacks on most reduced versions of Simon are the best compared with the previous cryptanalysis results. However, this does not shake the security of Simon family with full rounds.
-
Linear Hull attack on round reduced simeck with dynamic key guessing techniques
Australasian Conference on Information Security and Privacy, 2016Co-Authors: Huaifeng Chen, Xiaoyun WangAbstract:Simeck is a new family of lightweight block cipher proposed by Yang $$et\ al.$$ in CHES'15, which performs efficiently in hardware implementation. In this paper, we search out Simeck's differentials with low Hamming weight and high probability using Kolbl's tool, then exploit the links between differentials and Linear characteristics to construct Linear Hulls for Simeck. We give improved Linear Hull attack with dynamic key-guessing techniques on Simeck on the basis of round function's property. Our results cover Simeck 32/64 reduced to 23 rounds, Simeck 48/96 reduced to 30 rounds, Simeck 64/128 reduced to 37 rounds, which are the best known results so far for any variant of Simeck.
-
ACISP (2) - Linear Hull Attack on Round-Reduced Simeck with Dynamic Key-Guessing Techniques
Information Security and Privacy, 2016Co-Authors: Huaifeng Chen, Xiaoyun WangAbstract:Simeck is a new family of lightweight block cipher proposed by Yang $$et\ al.$$ in CHES'15, which performs efficiently in hardware implementation. In this paper, we search out Simeck's differentials with low Hamming weight and high probability using Kolbl's tool, then exploit the links between differentials and Linear characteristics to construct Linear Hulls for Simeck. We give improved Linear Hull attack with dynamic key-guessing techniques on Simeck on the basis of round function's property. Our results cover Simeck 32/64 reduced to 23 rounds, Simeck 48/96 reduced to 30 rounds, Simeck 64/128 reduced to 37 rounds, which are the best known results so far for any variant of Simeck.
-
improved Linear Hull attack on round reduced simon with dynamic key guessing techniques
Fast Software Encryption, 2016Co-Authors: Huaifeng Chen, Xiaoyun WangAbstract:Simon is a lightweight block cipher family proposed by NSA in 2013. It has drawn many cryptanalysts' attention and varieties of cryptanalysis results have been published, including differential, Linear, impossible differential, integral cryptanalysis and so on. In this paper, we give the improved Linear attacks on all reduced versions of Simon with dynamic key-guessing technique, which was proposed to improve the differential attack on Simon recently. By establishing the boolean function of parity bit in the Linear Hull distinguisher and reducing the function according to the property of AND operation, we can guess different subkeys or equivalent subkeys for different situations, which decrease the number of key bits involved in the attack and decrease the time complexity in a further step. As a result, 23-round Simon32/64, 24-round Simon48/72, 25-round Simon48/96, 30-round Simon64/96, 31-round Simon64/128, 37-round Simon96/96, 38-round Simon96/144, 49-round Simon128/128, 51-round Simon128/192 and 53-round Simon128/256 can be attacked. As far as we know, our attacks on most reduced versions of Simon are the best compared with the previous cryptanalysis results. However, this does not shake the security of Simon family with full rounds.
Huaifeng Chen - One of the best experts on this subject based on the ideXlab platform.
-
FSE - Improved Linear Hull Attack on Round-Reduced Simon with Dynamic Key-Guessing Techniques
Fast Software Encryption, 2016Co-Authors: Huaifeng Chen, Xiaoyun WangAbstract:Simon is a lightweight block cipher family proposed by NSA in 2013. It has drawn many cryptanalysts' attention and varieties of cryptanalysis results have been published, including differential, Linear, impossible differential, integral cryptanalysis and so on. In this paper, we give the improved Linear attacks on all reduced versions of Simon with dynamic key-guessing technique, which was proposed to improve the differential attack on Simon recently. By establishing the boolean function of parity bit in the Linear Hull distinguisher and reducing the function according to the property of AND operation, we can guess different subkeys or equivalent subkeys for different situations, which decrease the number of key bits involved in the attack and decrease the time complexity in a further step. As a result, 23-round Simon32/64, 24-round Simon48/72, 25-round Simon48/96, 30-round Simon64/96, 31-round Simon64/128, 37-round Simon96/96, 38-round Simon96/144, 49-round Simon128/128, 51-round Simon128/192 and 53-round Simon128/256 can be attacked. As far as we know, our attacks on most reduced versions of Simon are the best compared with the previous cryptanalysis results. However, this does not shake the security of Simon family with full rounds.
-
Linear Hull attack on round reduced simeck with dynamic key guessing techniques
Australasian Conference on Information Security and Privacy, 2016Co-Authors: Huaifeng Chen, Xiaoyun WangAbstract:Simeck is a new family of lightweight block cipher proposed by Yang $$et\ al.$$ in CHES'15, which performs efficiently in hardware implementation. In this paper, we search out Simeck's differentials with low Hamming weight and high probability using Kolbl's tool, then exploit the links between differentials and Linear characteristics to construct Linear Hulls for Simeck. We give improved Linear Hull attack with dynamic key-guessing techniques on Simeck on the basis of round function's property. Our results cover Simeck 32/64 reduced to 23 rounds, Simeck 48/96 reduced to 30 rounds, Simeck 64/128 reduced to 37 rounds, which are the best known results so far for any variant of Simeck.
-
ACISP (2) - Linear Hull Attack on Round-Reduced Simeck with Dynamic Key-Guessing Techniques
Information Security and Privacy, 2016Co-Authors: Huaifeng Chen, Xiaoyun WangAbstract:Simeck is a new family of lightweight block cipher proposed by Yang $$et\ al.$$ in CHES'15, which performs efficiently in hardware implementation. In this paper, we search out Simeck's differentials with low Hamming weight and high probability using Kolbl's tool, then exploit the links between differentials and Linear characteristics to construct Linear Hulls for Simeck. We give improved Linear Hull attack with dynamic key-guessing techniques on Simeck on the basis of round function's property. Our results cover Simeck 32/64 reduced to 23 rounds, Simeck 48/96 reduced to 30 rounds, Simeck 64/128 reduced to 37 rounds, which are the best known results so far for any variant of Simeck.
-
improved Linear Hull attack on round reduced simon with dynamic key guessing techniques
Fast Software Encryption, 2016Co-Authors: Huaifeng Chen, Xiaoyun WangAbstract:Simon is a lightweight block cipher family proposed by NSA in 2013. It has drawn many cryptanalysts' attention and varieties of cryptanalysis results have been published, including differential, Linear, impossible differential, integral cryptanalysis and so on. In this paper, we give the improved Linear attacks on all reduced versions of Simon with dynamic key-guessing technique, which was proposed to improve the differential attack on Simon recently. By establishing the boolean function of parity bit in the Linear Hull distinguisher and reducing the function according to the property of AND operation, we can guess different subkeys or equivalent subkeys for different situations, which decrease the number of key bits involved in the attack and decrease the time complexity in a further step. As a result, 23-round Simon32/64, 24-round Simon48/72, 25-round Simon48/96, 30-round Simon64/96, 31-round Simon64/128, 37-round Simon96/96, 38-round Simon96/144, 49-round Simon128/128, 51-round Simon128/192 and 53-round Simon128/256 can be attacked. As far as we know, our attacks on most reduced versions of Simon are the best compared with the previous cryptanalysis results. However, this does not shake the security of Simon family with full rounds.
Soo Hak Sung - One of the best experts on this subject based on the ideXlab platform.
-
On the security of Rijndael-like structures against differential and Linear cryptanalysis
Lecture Notes in Computer Science, 2020Co-Authors: Sangwoo Park, Soo Hak Sung, Seongtaek Chee, E-joong YoonAbstract:Rijndael-like structure is a special case of SPN structure. The Linear transformation of Rijndael-like structures consists of Linear transformations of two types, the one is byte permutation π and the other is Linear transformation θ = (θ 1 ,θ 2 ,θ 3 ,θ 4 ), where each of θ i separately operates on each of the four columns of a state. Furthermore, π and 0 have some interesting properties. In this paper, we present a new method for upper bounding the maximum differential probability and the maximum Linear Hull probability for Rijndael-like structures. By applying our method to Rijndael, we obtain that the maximum differential probability and the maximum Linear Hull probability for 4 rounds of Rijndael are bounded by 1.06 × 2 -96 .
-
Differential and Linear cryptanalysis for 2-round SPNs
Information Processing Letters, 2003Co-Authors: Kilsoo Chun, Soo Hak Sung, Seonhee YoonAbstract:In this paper, we examine the security of block ciphers referred to as substitution-permutation networks (SPNs). When the SPN has 2-round, we obtain an upper bound on the maximum differential probability. We also obtain an upper bound on the maximum Linear Hull probability. Our results extend and sharpen the known results for the 2-round SPNs.
-
improving the upper bound on the maximum differential and the maximum Linear Hull probability for spn structures and aes
Fast Software Encryption, 2003Co-Authors: Sangwoo Park, Soo Hak SungAbstract:We present a new method for upper bounding the maximum differential probability and the maximum Linear Hull probability for 2 rounds of SPN structures. Our upper bound can be computed for any value of the branch number of the Linear transformation and by incorporating the distribution of differential probability values and Linear probability values for S-box. On application to AES, we obtain that the maximum differential probability and the maximum Linear Hull probability for 4 rounds of AES are bounded by 1.144 × 2− 111 and 1.075 × 2− 106, respectively.
-
FSE - Improving the upper bound on the maximum differential and the maximum Linear Hull probability for SPN structures and AES
Fast Software Encryption, 2003Co-Authors: Sangwoo Park, Soo Hak SungAbstract:We present a new method for upper bounding the maximum differential probability and the maximum Linear Hull probability for 2 rounds of SPN structures. Our upper bound can be computed for any value of the branch number of the Linear transformation and by incorporating the distribution of differential probability values and Linear probability values for S-box. On application to AES, we obtain that the maximum differential probability and the maximum Linear Hull probability for 4 rounds of AES are bounded by 1.144 × 2− 111 and 1.075 × 2− 106, respectively.
-
ASIACRYPT - On the Security of Rijndael-Like Structures against Differential and Linear Cryptanalysis
Lecture Notes in Computer Science, 2002Co-Authors: Sangwoo Park, Soo Hak Sung, Seongtaek Chee, E-joong YoonAbstract:Rijndael-like structure is a special case of SPN structure. The Linear transformation of Rijndael-like structures consists of Linear transformations of two types, the one is byte permutation ? and the other is Linear transformation ? = (?1, ?2, ?3, ?4), where each of ?i separately operates on each of the four columns of a state. Furthermore, ? and ? have some interestingprop erties. In this paper, we present a new method for upper boundingthe maximum differential probability and the maximum Linear Hull probability for Rijndael-like structures. By applyingour method to Rijndael, we obtain that the maximum differential probability and the maximum Linear Hull probability for 4 rounds of Rijndael are bounded by 1.06 × 2-96.
Diego Regruto - One of the best experts on this subject based on the ideXlab platform.
-
CDC - Polytopic outer approximations of semialgebraic sets
2012 IEEE 51st IEEE Conference on Decision and Control (CDC), 2012Co-Authors: Vito Cerone, Dario Piga, Diego RegrutoAbstract:This paper deals with the problem of finding a polytopic outer approximation P* of a compact semialgebraic set S ⊆ ℝn. The computed polytope turns out to be an approximation of the Linear Hull of the set S. The evaluation of P* is reduced to the solution of a sequence of robust optimization problems with nonconvex functional, which are efficiently solved by means of convex relaxation techniques. Properties of the presented algorithm and its possible applications in the analysis, identification and control of uncertain systems are discussed.
-
Polytopic outer approximations of semialgebraic sets
2012 IEEE 51st IEEE Conference on Decision and Control (CDC), 2012Co-Authors: Vito Cerone, Dario Piga, Diego RegrutoAbstract:This paper deals with the problem of finding a polytopic outer approximation P* of a compact semialgebraic set S ⊆ Rn. The computed polytope turns out to be an approximation of the Linear Hull of the set S. The evaluation of P* is reduced to the solution of a sequence of robust optimization problems with nonconvex functional, which are efficiently solved by means of convex relaxation techniques. Properties of the presented algorithm and its possible applications in the analysis, identification and control of uncertain systems are discussed.
Stafford E Tavares - One of the best experts on this subject based on the ideXlab platform.
-
Linear cryptanalysis of substitution-permutation networks
2020Co-Authors: Henk Meijer, Stafford E Tavares, Liam KeliherAbstract:The subject of this thesis is Linear cryptanalysis of substitution-permutation networks (SPNs). We focus on the rigorous form of Linear cryptanalysis, which requires the concept of Linear Hulls. First, we consider SPNs in which the s-boxes are selected independently and uniformly from the set of all bijective n x n s-boxes. We derive an expression for the expected Linear probability values of such an SPN, and give evidence that this expression converges to the corresponding value for the true random cipher. This adds quantitative support to the claim that the SPN structure is a good approximation to the true random cipher. We conjecture that this convergence holds for a large class of SPNs. In addition, we derive a lower bound on the probability that an SPN with randomly selected s-boxes is practically secure against Linear cryptanalysis after a given number of rounds. For common block sizes, experimental evidence indicates that this probability rapidly approaches 1 with an increasing number of rounds. We then consider SPNs with fixed s-boxes. We present two new algorithms for upper bounding the maximum average Linear Hull probability for SPNs. These algorithms, named KMT1 and KMT2, are the first completely general algorithms for this purpose—they can be applied to any SPN, and they compute an upper bound that is a function of the number of encryption rounds being evaluated. In contrast, other approaches to this problem either require that the SPN Linear transformation have a specific structure, or compute a single value independent of the number of rounds. By applying KMT1 and KMT2 to the AES, we establish the provable security of the AES against Linear cryptanalysis. As a straightforward application of our work with Linear Hulls, we analyze the Q cipher, an SPN submitted to the European Commission's NESSIE cryptographic competition. By using Linear characteristics, not Linear Hulls, the designer of Q evaluates the cipher to be secure against Linear cryptanalysis. However, we prove that Q can be broken using Linear cryptanalysis based on Linear Hulls. To our knowledge, this is the first use of Linear Hulls to break a proposed cipher.
-
High Probability Linear Hulls in Q
2020Co-Authors: Liam Keliher, Henk Meijer, Stafford E TavaresAbstract:In this paper, we demonstrate that the Linear Hull effect is significant for the Q cipher. The designer of Q performs preliminary Linear cryptanalysis by discussing Linear characteristics involving only a single active bit at each stage [14]. We present a simple algorithm that combines all such Linear characteristics with identical first and last masks into a Linear Hull. The expected Linear probability of the best such Linear Hull over 7.5 rounds (8 full rounds minus the first S-substitution) is 2−90.1. In contrast, the best known expected differential probability over the same rounds is 2−110.5 [2]. Choosing a sequence of Linear Hulls yields a straightforward attack that can recover a 128-bit key with success rate 98.4%, using 2 known 〈plaintext, ciphertext〉 pairs and 2 trial encryptions.
-
completion of computation of improved upper bound on the maximum average Linear Hull probabilty for rijndael
IACR Cryptol. ePrint Arch., 2004Co-Authors: Liam Keliher, Henk Meijer, Stafford E TavaresAbstract:This report presents the results from the completed computation of an algorithm introduced by the authors in [11] for evaluating the provable security of the AES (Rijndael) against Linear cryptanalysis. This algorithm, later named KMT2, can in fact be applied to any SPN [8]. Preliminary results in [11] were based on 43% of total computation, estimated at 200,000 hours on our benchmark machine at the time, a Sun Ultra 5. After some delay, we obtained access to the necessary computational resources, and were able to run the algorithm to completion. In addition to the above, this report presents the results from the dual version of our algorithm (KMT2-DC) as applied to the AES.
-
Selected Areas in Cryptography - Improving the Upper Bound on the Maximum Average Linear Hull Probability for Rijndael
Selected Areas in Cryptography, 2001Co-Authors: Liam Keliher, Henk Meijer, Stafford E TavaresAbstract:In [15], Keliher et al. present a new method for upper bounding the maximum average Linear Hull probability (MALHP) for SPNs, a value which is required to make claims about provable security against Linear cryptanalysis. Application of this method to Rijndael (AES) yields an upper bound of UB = 2-75 when 7 or more rounds are approximated, corresponding to a lower bound on the data complexity of 32/UB = 280 (for a 96.7% success rate). In the current paper, we improve this upper bound for Rijndael by taking into consideration the distribution of Linear probability values for the (unique) Rijndael 8×8 s-box. Our new upper bound on the MALHP when 9 rounds are approximated is 2-92, corresponding to a lower bound on the data complexity of 297 (again for a 96.7% success rate). [This is after completing 43% of the computation; however, we believe that values have stabilized--see Section 7.]
-
improving the upper bound on the maximum average Linear Hull probability for rijndael
Selected Areas in Cryptography, 2001Co-Authors: Liam Keliher, Henk Meijer, Stafford E TavaresAbstract:In [15], Keliher et al. present a new method for upper bounding the maximum average Linear Hull probability (MALHP) for SPNs, a value which is required to make claims about provable security against Linear cryptanalysis. Application of this method to Rijndael (AES) yields an upper bound of UB = 2-75 when 7 or more rounds are approximated, corresponding to a lower bound on the data complexity of 32/UB = 280 (for a 96.7% success rate). In the current paper, we improve this upper bound for Rijndael by taking into consideration the distribution of Linear probability values for the (unique) Rijndael 8×8 s-box. Our new upper bound on the MALHP when 9 rounds are approximated is 2-92, corresponding to a lower bound on the data complexity of 297 (again for a 96.7% success rate). [This is after completing 43% of the computation; however, we believe that values have stabilized--see Section 7.]