Cryptanalysis Of Advanced Encryption Standard

The most widely used encryption scheme is based on the Data Encryption Standard (DES) [46] adopted in 1977 by the National Bureau of Standards, now the National Institute of Standards and Technology (NIST), as Federal Information Processing Standard 46 (FIPS PUB 46). For DES, data are encrypted in 64-bit blocks using a 56-bit key. The algorithm transforms 64-bit input in a series of steps into a 64-bit output. The same steps, with the same key, are used to reverse the encryption. The DES is a refined version of LUCIFER (a Feistel block cipher that operates on blocks of 64 bits, using a key size of 128 bits) and is more resistant to cryptanalysis.In 1999, NIST issued a new version of its standard (FIPS PUB 46-3) that indicated that DES should only be used for legacy systems and that triple DES (which in essence involves repeating the DES algorithm three times on the plaintext using two or three different keys to produce the ciphertext) be used.On January 2, 1997, NIST announced the initiation of a new symmetric-key block cipher algorithm as the new encryption standard to replace the DES. The new algorithm would be named the Advanced Encryption Standard (AES). Unlike the closed design process for the DES, an open call for the AES algorithms was formally made on September 12, 1997. The call stipulated that the AES would specify an unclassified, publicly disclosed symmetric-key encryption algorithm(s); the algorithm(s) must support (at a minimum) block sizes of 128-bits, key sizes of 128-, 192-, and 256-bits, and should have a strength at the level of the triple DES, but should be more efficient then the triple DES. In addition, the algorithm(s), if selected, must be available royalty-free, worldwide. On August 20,1998, NIST announced a group of fifteen AES candidate algorithms. These algorithms had been submitted by members of the cryptographic community from around the world. Public comments on the fifteen candidates were solicited as the initial review of these algorithms (the period for the initial public comments was also called the Round 1). The Round 1 closed on April 15, 1999. Using the analyses and comments received, NIST selected five algorithms from the fifteen. The five AES finalist candidate algorithms were MARS [8], RC6 [50], Rijndael [25], Serpent [1], and Twofish [49]. These finalist algorithms received further analysis during a second, more in-depth review period (the Round 2). In the Round 2, comments and analysis were sought on any aspect of the candidate algorithms, including, but not limited to, the following topics: cryptanalysis, intellectual property, cross-cutting analyses of all of the AES finalists, overall recommendations and implementation issues. After the close of the Round 2 public analysis period on May 15, 2000, NIST studied all available information in order to make a selection for the AES. On October 2, 2000, NIST announced that it has selected Rijndael, developed by Joan Daemen and Vincent Rijmen [24], to propose for the AES. In November 2001 the AES effort came to its conclusion with the publication of FIPS 197 [27], and today the AES is fast becoming a vital component of the digital infrastructure.In this thesis, we study some properties and cryptanalysis methods on the Advanced Encryption Standard. Based on these properties of the AES, we present some new properties of the AES which is very important in the analysis of the AES. Also we present our new cryptanalysis results on the AES based on these previous results. The thesis is organised as follows. In chapter 1 we introduce some knowledge of the background of the AES. We summarize our most important conclusions at the end of this chapter. In chapter 2 we describe the AES algorithm. First the four basic transformations of the AES are introduced, after that the key schedule of the AES is given. Then we describe the AES cipher by the pseudo code of the algorithm.Part of our main results are presented in chapter 3. In the first section we introduce some previous properties of the S-box itself. Although there's no attack based on these properties is presented, these properties are still very important to help us to analysis the AES cipher. Based on an observation from the properties given, we present a new property, that is there are only two pairs of bytes, 'EC and 'CE', '32' and '23' that satisfyS(xy) = yx.This property can be viewed that the effection of the S-box is equivalent to a cyclic permutation to the left by 4 bits. Comprehend this property as the equivalence between cyclic permutation and the S-box, we give a table with all elements satisfy such relations listed in it. Each element in this table satisfy that the effection of the S-box is equivalent to a cyclic permutation with the number of shifts this element is corresponding to. As we all know that the S-box of the AES has no fixed points, i.e., there's no elements such that S(x) = x, therefore this new property is very important in the analysis of the AES cipher. In the second section a few previous properties of the key schedule of the AES are given, these properties can be used in various cryptanalysis methods. We also deduce new properties thatThess properties will be used in our new cryptanalysis results of the AES. Some design aspects of the AES are discussed in the third section, mainly about the design of the S-box. To explain the design principles, we list some properties of the differential distribution table of the S-box of the AES, which can help us to understand the design principles of the AES better.Differential cryptanalysis [14] and linear cryptanalysis [38] is the two basic tools in cryptanalysis on block ciphers. As the development of the design theory, more new ciphers resist traditional cryptanalysis method, and more cryptanalysis tools were presented, such as [4], [6], [9], [15], [31] and [52]. In chapter 4, we introduce some previous cryptanalysis results on the AES, first is the square attack. The square attack is a dedicated attack on square that exploits the byte-oriented structure of square cipher and was published in the paper presenting the square cipher itself [19]. This attack is also valid for the AES, as Rijndael inherits many properties from Square. The author of Rijndael proposed square attack on the AES in [22]. Biham and Keller improved the author's attack by a factor 2 in [13]. Lucks extended the square attack on AES-192 and AES-256 to 7 round [34]. His attack utilizes some properties of the key schedule of AES-192 and AES-256. The best square attack is the partial sum technique proposed by Ferguson, Kelsey, Lucks etc. in [26]. We describe the above attacks briefly in the first section of chapter 4. In the second section of chapter 4, we describe the impossible differential attack on the AES. The impossible differential cryptanalysis on the AES was first proposed by Biham and Keller in [13]. Then impossible differential attack on 6 round AES was given by Cheon, Kim, Kimin etc. in [17]. Phan extended the impossible differential attack on the AES to 7 round in [48]. We discuss the collision attack and the boomerang attack on the AES seperately in the last two sections of this chapter. The collision attack on the AES was first proposed by Gilbert and Minier in [28]. Biryukov presented his boomerang attack on 5 and 6 round AES in [3]. We summarize the results of these attacks, including time and data complexities and memory needed in a table.The new cryptanalysis results are in chapter 5. In the first section of this chapter, we describe a new three-rounds property proposed by Xiaoyun Wang which is based on a three-rounds property used in the collision attack proposed in [28]. Based on the some results within this new three-rounds property, my Ph. D advisor Xiaoyun Wang raise this property to a high level, and thus we propose a new class of collisions within three-rounds of the AES. In particular, the average probability of this word collision is at least about 2^-16, where the idea of the proof of the probability also come from my advisor Xiaoyun Wang. Based on the collision attack, in the second section we give an improved collision attack on 7-round AES-192. The improvement is mainly by utilizing some properties of the key schedule for the 192-bit key derived in chapter 3, and with a more carefully guess, the complexity of the attack is decreased further. In the third section we extend the boomerang attack on AES-192 to 7 rounds, which is based on Biryukov's 5 and 6 round attack on the AES.We summarize our main cryptanalysis results of the AES as follows:1. A few properties of the S-box and the key schedule of the AES are proposed. Some properties of the differential distribution table of the S-box of the AES are also listed, which can help us to understand the design principles of the AES.2. A new three-rounds property is given. In this property, a new class of collision within three-rounds of the AES is first proposed. In particular, the probability of this kind of collision is discussed.3. An improved collision attack on 7-round AES-192 is presented. This attack can recovery the main key by about 2¹²⁰ operations and 2¹²³ bytes of memory. Compared with Gilbert-Minier attack [28], the time complexity of our attack decreases 2²⁴ times with 2⁸ times memory increase. If we keep the same memory with that of Gilbert-Minier attack, the time complexity is about 2¹²⁷ operations.4. We extend the boomerang attack on 5 and 6 round AES [3] to 7 rounds for AES-192 version. The complexity of this attack is 2³⁹ chosen plaintexts, 2¹⁸³ adaptively chosen ciphertexts, 2¹⁸³ time steps spent mainly encrypting the texts and 2³⁷ bytes of memory.Finally we summarize our results, and give some open problems for further research in chapter 6.