New Impossible Differential Attacks on AES

Please download to get full document.

View again

of 18
All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
Information Report
Category:

Legal forms

Published:

Views: 0 | Pages: 18

Extension: PDF | Download: 0

Share
Related documents
Description
New Impossible Differential Attacks on AES Jiqiang Lu 1,, Orr Dunkelman 2,, Nathan Keller 3,, and Jongsung Kim 4, 1 Department of Mathematics and Computer Science, Eindhoven University of Technology, 5600
Transcript
New Impossible Differential Attacks on AES Jiqiang Lu 1,, Orr Dunkelman 2,, Nathan Keller 3,, and Jongsung Kim 4, 1 Department of Mathematics and Computer Science, Eindhoven University of Technology, 5600 MB Eindhoven, The Netherlands 2 École Normale Supérieure Département d Informatique, 45 rue d Ulm, Paris, France. 3 Einstein Institute of Mathematics, Hebrew University. Jerusalem 91904, Israel 4 Center for Information Security Technologies(CIST), Korea University Anam Dong, Sungbuk Gu, Seoul, Korea Abstract. In this paper we apply impossible differential attacks to reduced round AES. Using various techniques, including the early abort approach and key schedule considerations, we significantly improve previously known attacks due to Bahrak-Aref and Phan. The improvement of these attacks leads to the best known impossible differential attacks on 7-round AES-128 and AES-192, as well as to the best known impossible differential attacks on 8-round AES Keywords: AES, Impossible differential cryptanalysis 1 Introduction The Advanced Encryption Standard (AES) [13] is a 128-bit block cipher with a variable key length (128, 192, and 256-bit keys are supported). Since its selection, AES gradually became one of the most widely used block ciphers. AES has received a great deal of cryptanalytic attention, both during the AES process, and even more after its selection. In the single-key model, previous results can attack up to 7 rounds of AES-128 (i.e., AES with 128-bit key). The first attack is a SQUARE attack suggested in [15] The work was done when this author wasa Ph.D. student at Royal Holloway, University of London. The first author was supported by the France Telecome Chaire. Some of the work presented in this paper was done while the first author was staying at K.U. Leuven. This author is supported by the Adams Fellowship Program of the Israel Academy of Sciences and Humanities. This author was supported by the Second Brain Korea 21 Project. which uses chosen plaintexts and encryptions. The second attack is a meet-in-the-middle attack proposed in [16] that requires 2 32 chosen plaintexts and has a time complexity equivalent to almost encryptions. Recently, another attack on 7-round AES-128 was presented in [1]. The new attack is an impossible differential attack that requires chosen plaintexts and has a running time of encryptions. Similar results, but with better attack algorithms and lower complexities were reported in [20]. The resulting impossible differential attack on 7-round AES-192 has a data complexity of 2 92 chosen plaintexts and time complexity of encryptions, while the attack on AES-256 uses chosen plaintexts and running time of encryptions. There are several attacks on AES-192 [1, 14,15,18 20]. The two most notable ones are the SQUARE attack on 8-round AES-192 presented in [15] that requires almost the entire code book and has a running time of encryptions and the meet in the middle attack on 7-round AES-192 in [14] that requires 2 34+n chosen plaintexts and has a running time of n n encryptions. Legitimate values for n in the meet in the middle attack on AES-192 are 94 n 17, thus, the minimal data complexity is 2 51 chosen plaintexts (with time complexity equivalent to exhaustive search), and the minimal time complexity is (with data complexity of 2 97 chosen plaintexts). AES-256 is analyzed in [1,14,15,18,20]. The best attack is the meet in the middle attack in [14] which uses 2 32 chosen plaintexts and has a total running time of encryptions. Finally, we would like to note the existence of many related-key attacks on AES- 192 and AES-256. As the main issue of this paper is not related-key attacks, and as we deal with the single key model, we do not elaborate on the matter here, but the reader is referred to [21] for the latest results on related-key impossible differential attacks on AES and to [17] for the latest results on related-key rectangle attacks on AES. The strength of AES with respect to impossible differentials was challenged several times. The first attack of this kind is a 5-round attack presented in [5]. This attack is improved in [11] to a 6-round attack. In [19], an impossible differential attack on 7-round AES-192 and AES-256 is presented. The latter attack uses 2 92 chosen plaintexts (or chosen plaintexts for AES-256) and has a running time of encryptions (or encryptions for AES-256). The time complexity of the latter attack was improved in [20] to encryptions for AES-192. In [1] a new 7-round impossible differential attack was presented. The new attack uses a different impossible differential, which is of the same general type as the one used in previous attacks (but has a slightly different structure). Using the new impossible differential leads to an attack that requires chosen plaintexts and has a running time of encryptions. This attack was later improved in [2,20] to use chosen plaintexts with time complexity of encryptions. The last application of impossible differential cryptanalysis to AES was the extension of the 7-round attack from [1] to 8-round AES-256 in [20]. The extended attack has a data complexity of chosen plaintexts and time complexity of encryptions. 2 We note that there were three more claimed impossible differential attacks on AES in [8 10]. However, as all these attacks are flawed [7]. In this paper we present a new attack on 7-round AES-128, a new attack on 7- round AES-192, and two attacks on 8-round AES-256. The attacks are based on the attacks proposed in [1, 19] but use additional techniques, including the early abort technique and key schedule considerations. Our improvement to the attacks on 7-round AES-128 from [1, 20] requires chosen plaintexts, and has a running time of memory accesses. Our improvement to the attack on 7-round AES-192 from [19] has a data complexity of chosen plaintexts and a time complexity of encryptions. Since the first attack is also applicable to AES-192, the two attacks provide a data-time tradeoff for attacks on 7-round AES-192. The best attack we present on 8-round AES-256 requires chosen plaintexts and has a time complexity of memory accesses. These results are significantly better than any previously published impossible differential attack on AES. We summarize our results along with previously known results in Table 1. Although the attacks presented in the paper are not the best known attacks on AES, the results are important, both due to the significance of the AES, and since the techniques used in the paper can be useful in other works as well. This paper is organized as follows: In Section 2 we briefly describe the structure of AES. In Section 3 we discuss the previous impossible differential attacks. In Section 4 we describe the possible improvements and extensions (to 8-round AES-256) of the Bahrak and Aref attack. The improvement of Phan s attack on 7-round AES-192 along with its extension to 8-round AES-256 is presented in Section 5. In Appendix A we describe a technique which is repeatedly used in impossible differential attacks on AES. Appendix B outlines the impossible differentials used in this paper for the sake of completeness. We conclude the paper in Section 6. 2 Description of AES The advanced encryption standard [13] is an SP-network that supports key sizes of 128, 192, and 256 bits. A 128-bit plaintext is treated as a byte matrix of size 4x4, where each byte represents a value in GF(2 8 ). An AES round applies four operations to the state matrix: SubBytes (SB) applying the same 8-bit to 8-bit invertible S-box 16 times in parallel on each byte of the state, ShiftRows (SR) cyclic shift of each row (the i th row is shifted by i bytes to the left), MixColumns (MC) multiplication of each column by a constant 4x4 matrix over the field GF(2 8 ), and AddRoundKey (ARK) XORing the state with a 128-bit subkey. We outline an AES round in Figure 1. In the first round, an additional AddRoundKey operation (using a whitening key) is applied, and in the last round the MixColumns 3 Key Number of Complexity Attack Type & Source Size Rounds Data (CP) Time SQUARE [15] Impossible Differential [1] Impossible Differential [2, 20] Meet in the Middle [16] MA Impossible Differential (App. 4.1) SQUARE [18] SQUARE [15] Impossible Differential [19] Impossible Differential [20] Impossible Differential [20] n n n Meet in the Middle [14] SQUARE [15] MA Impossible Differential (Sect. 4.1) Impossible Differential (Sect. 5.1) SQUARE [18] SQUARE [15] Impossible Differential [19] Meet in the Middle [14] n n n Meet in the Middle [14] Impossible Differential [20] Impossible Differential [20] SQUARE [15] Meet in the Middle [14] MA Impossible Differential (Sect. 4.1) MA Impossible Differential (Sect. 5.1) MA Impossible Differential (Sect. 4.2) MA Impossible Differential (Sect. 5.2) CP Chosen plaintext, MA Memory Accesses Time complexity is measured in encryption units unless mentioned otherwise Table 1. A Summary of the Previous Attacks and Our New Attacks operation is omitted. As all other works on AES, we shall assume that reduced-round variants also have the MixColumns operation omitted from the last round. The number of rounds depends on the key length: 10 rounds for 128-bit keys, 12 rounds for 192-bit keys, and 14 rounds for 256-bit keys. The rounds are numbered 0,...,Nr 1, where Nr is the number of rounds (Nr {10, 12, 14}). For the sake of simplicity we shall denote AES with n-bit keys by AES-n, i.e., AES with 192-bit keys (and thus with 12 rounds) is denoted by AES-192. The key schedule of AES takes the user key and transforms it into 11, 13, or 15 subkeys of 128 bits each. The subkey array is denoted by W[0,...,59], where each word of W[ ] consists of 32 bits. The first Nk words of W[ ] are loaded with the user supplied key, i.e., Nk = 4 words for 128-bit keys, Nk = 6 words for 192-bit keys, and 4 x I i SubBytes x SB i x SR i x MC i SB SR MC ARK ShiftRows MixColumns Fig.1. An AES round Nk = 8 for 256-bit keys. The remaining words of W[ ] are updated according to the following rule: For i = Nk,..., 43/51/59, do If i 0 mod Nk then W[i] = W[i Nk] SB(W[i 1] 8) RCON[i/Nk], Otherwise W[i] = W[i 1] W[i Nk], where RCON[ ] is an array of predetermined constants, and denotes rotation of the word by 8 bits to the left. We also note that for 256-bit keys, when i 4 mod 8 the update rule is W[i] = W[i 8] SB(W[i 1] 8). 2.1 The Notations Used in the Paper In our attacks we use the following notations: x I i denotes the input of round i, while x SB i, x SR i, x MC i, and x O i denote the intermediate values after the application of Sub- Bytes, ShiftRows, MixColumns, and AddRoundKey operations of round i, respectively. Of course, the relation x O i 1 = xi i holds. We denote the subkey of round i by k i, and the first (whitening) key is k 1, i.e., the subkey of the first round is k 0. In some cases, we are interested in interchanging the order of the MixColumns operation and the subkey addition. As these operations are linear they can be interchanged, by first XORing the data with an equivalent key and only then applying the MixColumns operation. We denote the equivalent subkey for the altered version by w i, i.e., w i = MC 1 (k i ). We denote bytes of some intermediate state x i or a key k i (or w i ) by an enumeration {0, 1, 2,..., 15} where the byte 4m + n corresponds to the n th byte in the m th row of x i, and is denoted by x i,4 m+n. We denote the z th column of x i by x i,col(z), i.e., w 0,Col(0) = MC 1 (k 0,Col(0) ). Similarly, by x i,col(y,z) we denote columns y and z of x i. We define two more column related sets. The first is x i,sr(col(z)) which is the bytes in x i corresponding to the places after the ShiftRows operation on column z, e.g., x i,sr(col(0)) is composed of bytes 0,7,10,13. The second is x i,sr 1 (Col(z)) which is the bytes in the positions of column z after having applied the inverse ShiftRows operation. 3 Previous Impossible Differential Attacks on AES The security of AES against impossible differential attacks was challenged in two lines of research. The first presented in [5, 11,19,20], and the second in [1,20]. Both lines 5 use very similar impossible differentials as well as similar algorithms. In this section we present the previously known results: All known impossible differential attacks on the AES, are based on the following 4-round impossible differential of AES, first observed in [5]: Proposition 1. Let (x I i ) denote the input difference to round i, and let (xsr i+3 ) denote the difference after the ShiftRows operation of round i + 3. If the following two conditions hold: 1. (x I i ) has only one non-zero byte, 2. In (x SR i+3 ), at least one of the four sets of bytes SR(Col(i)), for the four different possible columns, is equal to zero, then (x I i ) (xsr i+3 ) is an impossible differential for any four consecutive rounds of AES. We outline one of these impossible differentials in Figure 4 (in Appendix B). We also note that if in round i + 3 the order of MixColumns and AddRoundKey is swapped, then, one can consider the impossible differential (x I i ) (xo i+3 ). Proof. On the one hand, if (x I i ) has only one non-zero byte then (xi i+1 ) has nonzero values in a single column, and therefore, (x I i+2 ) has non-zero values in all the 16 bytes of the table (following the basic diffusion properties of AES, a fact used in many attacks on AES). On the other hand, if Condition (2) holds then (x I i+3 ) has at least one zero column, and hence at least one of the four sets of bytes SR 1 (Col(i)) in (x I i+2 ) is equal to zero, a contradiction. 3.1 The Original Bahrak-Aref Attack on 7-round AES-128 The algorithm of the BA attack, as described in [1], is the following (depicted in Figure 2): 1 1. Encrypt structures of 2 32 plaintexts each, such that in every structure, bytes SR 1 (Col(0)) assume all the 2 32 possible values and the rest of the bytes are fixed. 2. In each structure, look for ciphertext pairs with zero difference in bytes SR(Col(1, 2)) and discard the other pairs. 3. Guess the values of k 6,SR(Col(3)) and partially decrypt all the remaining ciphertext pairs through round 6 to obtain the difference (x SR 5,Col(3) ). Select only the pairs for which (x SR 5,Col(3) ) has a non-zero value only in byte Guess the values of bytes k 6,SR(Col(0)) and partially decrypt all the remaining ciphertext pairs through round 6 to get the difference (x SR 5,Col(0) ). Select only the pairs for which (x SR 5,Col(0) ) has a non-zero value only in byte Guess the values of bytes (0, 7) of the equivalent key w 5 and partially decrypt all the remaining ciphertext pairs through round 5 to get the difference (x SR Select only the pairs for which (x SR 4,Col(0) ) has one zero byte value. 4,Col(0) ). 1 Note that different notations are used in [1]. We adapted their attack to the standard notations used in AES. 6 ARK SB SR MC ARK k 1 k 0 Impossible Differential MC SB SR SR ARK w 5 MC SB SR ARK k 6 A gray box stands for a non-zero difference in the byte, while a white box stands for a zero difference. Fig.2. The 7-Round Impossible Differential Attack on AES by Bahrak and Aref 6. For each of the remaining pairs, consider the corresponding plaintext pair and discard all the values of k 1,SR 1 (Col(0)) that lead to the input difference of the impossible differential in the input of round 1. If a guess for these bytes remains, guess all the remaining key bytes and check the guess using trial encryption. Otherwise, repeat Steps 4 6 for a different guess of k 6. Step 1 of the attack consists of encryption of chosen plaintexts. Step 2 requires memory accesses, and suggests pairs to Step 3. Step 3 takes partial decryptions and passes pairs, for a given subkey guess, to Step 4, which in turn takes partial decryptions and outputs pairs to Step 5. Step 5 requires partial decryptions, and leaves pairs to Step 6, which uses memory accesses. Hence, the total time complexity of the attack is round AES encryptions. 2 The data complexity of the attack is chosen plaintexts, and the memory complexity is bytes of memory required for storing the list of discarded key values. 3.2 The Phan Attack Algorithm on 7-Round AES-192 The algorithm of the Phan attack, as described in [19], is the following (depicted in Figure 3): 1. Encrypt 2 60 structures of 2 32 plaintexts each such that in every structure, the bytes of SR 1 (Col(0)) assume all the 2 32 possible values and the rest of the bytes are fixed. 2. Select only the ciphertext pairs, corresponding to plaintexts in the same structure, for which the difference in bytes SR(Col(2, 3)) is zero. 2 In [1] Step 4 was considered as a full one-round decryption, while it is only 1/4 round in reality. 7 ARK SB SR MC ARK k 1 k 0 Impossible Differential MC SB SR SR MC ARK k 5 SB SR ARK k 6 Fig.3. The 7-Round Impossible Differential Attack on AES-192 by Phan 3. Guess k 6 and partially decrypt the remaining ciphertext pairs through round 6 to get x I Using the guessed value of k 6, retrieve k 5,Col(0,1) by the key schedule algorithm. For each remaining pair, decrypt x I 6 through ARK 1 MC 1 SR 1 SB 1 MC 1 to get the difference (x SR 4 ). 3 If the difference does not satisfy Condition (2) of Proposition 1, discard the pair. 5. Consider the plaintext pairs corresponding to the remaining ciphertext pairs. Guess the value of k 1,SR 1 (Col(0)) and partially encrypt each plaintext pair through ARK SB SR MC to get the difference (x I 1 ). If the difference satisfies Condition (1) of Proposition 1, discard the guess of k 1,SR 1 (Col(0)). 6. If all the guesses of k 1,SR 1 (Col(0)) are discarded for a guess of k 6, repeat Steps 3 5 with another guess of k 6. If a candidate of k 1,SR 1 (Col(0)) remains, the rest of the key bits (or their equivalent) are exhaustively searched. Step 1 of the attack consists of the encryption of 2 92 chosen plaintexts. Step 2 of the attack takes 2 92 memory accesses and proposes 2 59 pairs for further analysis. Steps 3 and 4 take together two-round decryptions, and suggest 2 29 pairs for Step 5 (for a given key guess). Step 5 takes round encryptions. Therefore, the data complexity of the attack is 2 92 chosen plaintexts, and the time complexity is round AES-192 encryptions. The attack requires bytes of memory, used for storing the discarded guesses of k 6 and k 1,SR 1 (Col(0)). 4 Improvement of the Bahrak-Aref Attack 4.1 Improvement of the Bahrak-Aref Attack on 7-Round AES-128 Our improvements to the 7-round attack are based on several techniques and observations. First, instead of partially decrypting each candidate pair under many possible 3 Note that the ARK 1 operation in the end of round 4 can be skipped since it does not affect the difference (x SR 4 ). 8 key guesses, we use table look ups to deduce which key it suggests. The second improvement is based on re-using the data, i.e., repeating the attack several times by using a slightly different impossible differential. Using these two ideas along with several additional techniques, we succeed in reducing the data and time complexities of the BA attack. We first discuss the improvement of the time complexity of the attack. However, as we demonstrate later, the data complexity of the attack can be reduced to chosen plaintexts. Hence, we use this figure in the computation of the time complexity as well. Improving the Time Complexity of the BA Attack Steps 1 and 2 of the attack remain unchanged, except for the reduction in the number of plaintexts. As a result, the time complexity of Step 2 is memory accesses, and the number of pairs remaining after Step 2 is In Step 3 of the BA attack the attacker decrypts a full column through round 6 by guessing 32 subkey bits. This step is significantly improved by using a wellknown observation related to differential cryptanalysis: Given an input and an output differences of the SubBytes operation, there is on average one pair of actual values that satisfies these differences. 4 Since for any ciphertext pair, the differenc
We Need Your Support
Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks
SAVE OUR EARTH

We need your sign to support Project to invent "SMART AND CONTROLLABLE REFLECTIVE BALLOONS" to cover the Sun and Save Our Earth.

More details...

Sign Now!

We are very appreciated for your Prompt Action!

x