Cryptanalysis Of Two Symmetric Encryption Algorithms ARIA And SALSA20

Symmetric cryptography is an important branch of cryptography. It includes block cipher and stream cipher. Symmetric encryption algorithm has many attractive features such as high rates and small memory space for both software and hardware implementation . In this thesis, we research on the security of block cipher and stream cipher.Approved in 1977, DES [51] was the early standard for block cipher, which has been widely used in the world. The block size and the key length are respectively 64 bits and 56 bits, which became the main security disadvantages. So DES has been unsecured and needs to be replaced. To this end the National Institute of Standards and Technology (NIST) has been holding a competition to develop the Advanced Encryption Standard (AES) as a replacement for DES. In 1997, NIST announced the initiation of the AES and called for new algorithms. In 1998, NIST announced fifteen AES candidate algorithms at the First AES Candidate Conference. The Second AES Candidate Conference was held in 1999 to discuss the results of the analysis by the global cryptanalyzers on the candidate algorithms. At last, NIST selected five algorithms from the original fifteen submissions. The AES finalist candidate algorithms were MARS, RC6 [59], Rijndael [25], Serpent [1], and Twofish [56]. The third AES Candidate Conference announced Rijndael designed by J. Daemen and V. Rijmen was the winner.The security of block cipher is difficult to be proved. It is risk to introduce an unproved cipher. So many countries dedicate to design cryptosystems for themselves. Now some countries have standardized encryption algorithms for themselves.ARIA version 0.8 [52] was first announced at an annual conference on security in Korea. It had 10/12/14 rounds for key sizes of 128/192/256, and only two kinds of S-boxes were used. A. Biryukov et al. evaluated the security of it with different types of attacks [17]. One of these attacks is dedicated linear attack and they indicated that this attack can be avoided by using four different kinds of S-boxes. ARIA version 0.9 [40] which four different S-boxes are used in its substitution was announced later. ARIA version 1.0 [53], the current one, was announced and distributed on its official website at http://www.nsri.re.kr/ARIA/ in mid 2004. The number of rounds was increased to 12/14/16, and there were some modifications to the key expansion. In December 2004, ATS(Agency for Technology and Standards) of Korea standardized ARIA as 128-bit Block Encryption Algorithm ARIA (KS X 1213). In addition, an impossible differential analysis of ARIA was proposed by W. L. Wu et al. in 2007 [66].There are a variety of efficient and trusted block ciphers. Unfortunately the same is not true for stream ciphers. As a response to the lack of efficient ciphers, ECRYPT (a 4-year Network of Excellence funded by the European Union) manages and coordinates a multi-year effort called eSTREAM to identify new stream ciphers suitable for widespread adoption. This master's project began in September 2005. The initial call for algorithms resulted in 34 candidates. The first evaluation phase was ended in February, 2006. The second phase was ended in April, 2007. Now is the third phase and there remain 16 ciphers. Salsa20 [3, 4] is one of them.Salsa20 is designed by D. J. Bernstein in 2005. It was highly praised in the first and second phase of eSTREAM Project. In 2005, P. Crowley proposed five round truncated differential eryptanalysis [21]. S. Fischer et al. researched the non-randomness of Salsa20 [29].In this thesis, we provide some cryptanalysis on ARIA and Salsa20 and have the following results.(1) Improved impossible differential cryptanalysis of ARIA reduced to six roundsW. L. Wu et al. proposed an impossible differential cryptanalysis of ARIA. In their cryptanalysis, they used a four-round Impossible Differential Property. It can be described as follows:(a, 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0) (?) (0, h, 0,0,0,0,0,0, h, h, h, 0,0,0, h, 0),where a and h are nonzero.We find a new impossible differential property which can be used for attacking ARIA reduced to six rounds more effectively.Impossible Differential Property of ARIA. Given a plaintext pair which is equal in all bytes except bytes (1,12), there is no ciphertext pair after four rounds satisfying the following three points:(a) The ciphertexts are not equal at bytes (3,11,12,13). (b) The ciphertexts are equal at the other bytes.(c) The difference of the ciphertexts at bytes (3,11,12,13) are equal.This four-round impossible differential property can be expressed as (0, a₁,0,0,0,0,0,0,0,0,0,0,a₁₂,0,0,0)(?)(0,0,0,f,0,0,0,0,0,0,0,f,f,f, 0,0),where a₁,a₁₂ and f are nonzero.We can also find many impossible differential properties similar to (1). For example:(0, 0, 0, a₃, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, a₁4), 0) (?) (0, f, 0, 0, 0, 0, 0, 0, 0, 7,0, 0, 0, 0, f,f), (0, 0, 0, 0, 0, 0, a₆, 0, 0, 0, 0, 0, 0, a₁₃, 0, 0)(?)(0, 0, 0, 0, f, 0, 0, 0, f, 0, 0, 0, 0, f,f, 0),(0,0,0,0,0,0,0, a₇, 0,0,0,0, a₁₂,0,0,0) (?) (0,0,0,0,0, f, 0,0,0, f, 0,0, f, 0,0,f).Then we propose an attack on ARIA reduced to six rounds based on Property1. In our attack, 10 bytes of round keys are needed to be guessed instead of 12 bytes in the previous one, so the time complexity is reduced by 2¹⁶ times. It needs 2¹²⁰ chosen plaintexts and 2⁹⁶ encryptions in our attack.(2) Linear attack on ARIA version 1.0A. Biryukov et al. proposed a dedicated linear attack on ARIA version 0.8 which used two different kinds of S-boxes in substitution layer. They advised that ARIA should be improved by using four different kinds of S-boxes in order to resist this attack. The designers of ARIA accepted this advice in version 0.9 and 1.0. However, we propose a new linear attack on version 0.9 and 1.0 and prove that the new versions of ARIA are weak to linear attack.For the substitution layer of ARIA, we have the following property:Property of substitution layer.P(S_i(x₀)⊕S_i(x₁)⊕S_j(x₂)⊕S_j(x₃)=0|x₀⊕x₁⊕x₂⊕x₃=0)≈2×2^-8．(3)where S_i, S_j are two different S-boxes used in the substitution layer.For the diffusion layer of ARIA, we have the following properties.Property of diffusion layer. For the transform DL, there are twelve conclusions which are (a)y₈⊕y₁₀⊕y₁₂⊕y₁₄=x₈⊕x₁₀⊕x₁₂⊕x₁₄,(b)y₉⊕y₁₁⊕y₁₃⊕y₁₅=x₉⊕x₁₁⊕x₁₃⊕x₁₅,(c)y₄⊕y₅⊕y₁₂⊕y₁₃=x₄⊕x₅⊕x₁₂⊕x₁₃,(d)y₆⊕y₇⊕y₁₄⊕y₁₅=x₆⊕x₇⊕x₁₄⊕x₁₅,(e)y₁⊕y₂⊕y₁₃⊕y₁₄=x₁⊕x₂⊕x₁₃⊕x₁₄,(f)y₀⊕y₃⊕y₁₂⊕y₁₅=x₀⊕x₃⊕x₁₂⊕x₁₅,(g)y₁⊕y₃⊕y₅⊕y₇=x₀⊕x₂⊕x₄⊕x₆,(h)y₂⊕y₃⊕y₁₀⊕y₁₁=x₀⊕x₁⊕x₈⊕x₉,(i)y₅⊕y₆⊕y₉⊕y₁₀=x₄⊕x₇⊕x₈⊕x₁₁,(j)y₀⊕y₂⊕y₄⊕y₆=x₁⊕x₃⊕x₅⊕x₇,(k)y₀⊕y₁⊕y₈⊕y₉=x₂⊕x₃⊕x₁₀⊕x₁₁,(l)y₄⊕y₇⊕y₈⊕y₁₁=x₅⊕x₆⊕x₉⊕x₁₀．By these properties of substitution layer and diffusion layer, we can build 12 routes for linear attack on ARIA version 1.0. That is to say, based on each of the 12 routes, a distinguisher can be builded for linear attack.For example, an r rounds distinguisher is P(y₉^r⊕y₁₁^r⊕y₁₃^r⊕y₁₅^r=0|x₉¹âŠ•x₁₁¹âŠ•x₁₃¹âŠ•x₁₅¹=0)≈2^-8+2^-8r．(4)We succeed in attacking on ARIA version 1.0 reduced 7/9/9/ rounds for key sizes of 128/192/256 by using any of these approximations. These results are similar to the dedicated linear attack on ARIA version 0.8 and reveal that the improved version is also weak to resist the dedicated linear attack. Table 1 gives the comparison between the result of our attack on ARIA version 1.0 and the attack on ARIA version 0.8 in [17]. (3) The differential of Salsa20The core of Salsa20 is an Hash function with 64-byte input and 64-byte output. Although there are some results of differential analysis of Salsa20, the properties on the differential of basic function of Salsa20 have not been given. We investigate the differential of quarterround function and round function. We find some important properties of quarterround function, for example: (0,â–³y₁[t+7],0,â–³y₃[t+0])→(â–³z₀[t+18],0,0,â–³z₃[t+0]),if t = 31 p=1;if t≠31 p=1/4.These properties can be used in analysis of the round function. In Chapter 6, we give a four rounds differential with probability 2^-50. In addition, we research on related key attack on Salsa20. We build a model of related key attack on Salsa20 reduced to six rounds based on the truncated differential cryptanalysis of five-round Salsa20.(4) Differential fault analysis of Salsa20We propose two differential fault analysis of Salsa20 with two fault models. In the first one, fault is induced on a bit of the middle states in the memory when a plaintext is encrypted by Salsa20. In the second one, fault is induced on a whole byte. With the first model, the computational complexity of the attack on Salsa20-256 is 2⁷⁰ by using 186 faulty ciphertexts, and the computational complexity of attack on Salsa20-128 is 2²⁰ by using 124 faulty ciphertexts. With the second model, if 4n (n > 5) faulty ciphertexts are chosen for k_i, i = 0,1,2,3, the 31 bits of k_i are recovered with the respective probability p = 1 - (1/2ⁿ×31).In the fault analysis of Salsa20, we research on the relation between addition and exclusive-or. The combination of the two operations is one of the widely used symmetric cipher components. Phelix, Mars, RC6, Twofish and the MD-family of hash functions are the applications of addition and exclusive-or. It is important for cryptology to research on the relation between them.