Improved “Partial Sums”-based Square Attack on AES

Abstract

The Square attack as a means of attacking reduced round variants of AES was described in the initial description of the Rijndael block cipher. This attack can be applied to AES, with a relatively small number of chosen plaintext-ciphertext pairs, reduced to less than six rounds in the case of AES-128 and seven rounds otherwise and several extensions to this attack have been described in the literature. In this paper we describe new variants of these attacks that have a smaller time complexity than those present in the literature. Specifically, we demonstrate that the quantity of chosen plaintext-ciphertext pairs can be halved producing the same reduction in the time complexity. We also demonstrate that the time complexity can be halved again for attacks applied to AES-128 and reduced by a smaller factor for attacks applied to AES-192. This is achieved by eliminating hypotheses on-the-fly when bytes in consecutive subkeys are related because of the key schedule.

Keywords: Cryptanalysis, Square Attack, Advanced Encryption Standard.

1. Introduction

The Advanced Encryption Standard (AES) [FIPS01] was standardized in 2001 from a proposal by Daemen and Rijmen [DaeRij98]. It has since been analyzed with regard to numerous attacks ranging from purely theoretical cryptanalysis to attacks that require some extra information, e.g. from some side channel [ManOswPop07], to succeed.

In Daemen and Rijmen’s AES proposal an attack is described that is referred to as the Square attack [DaeRij98]. This attack was so-called since it was first presented in the description of the block cipher Square [DaeKnuRij97]. The Square attack is based on a particular property arising from the structure of AES. That is, for a set of 256 plaintexts where each byte at an arbitrary index is a distinct value and all the other bytes are equal, the XOR sum of the 256 intermediate states after three rounds of AES will be zero.

Some optimizations to this attack have been proposed in the literature. Ferguson et al. proposed a way of conducting the Square attack referred to as the “partial sums” method [Fer+01]. This allowed the Square attack to be conducted with a relatively low time complexity for reduced round variants of AES. The time complexity of these attacks was further reduced following an observation made by Lucks. He noted that given a known last subkey in AES-192 then information on previous subkeys can be derived.

In this paper we describe how the attacks proposed by Ferguson et al. and Lucks can be improved. Specifically, we show that the number of chosen plaintext-ciphertext pairs required to conduct the Square attack can be halved and therefore halve the time complexity of the attack. Moreover, we demonstrate that the time complexity of the Square attack can be halved again when applied to AES-128, and reduced to a lesser extent for AES-192, by exploiting relationships between key bytes as they are derived. In this paper we restrict ourselves to attacks that require a relatively small number of chosen plaintext-ciphertext pairs. The attacks proposed by Ferguson et al., based on the Square attack, that require around 2^{128} chosen plaintext-ciphertext pairs are beyond the scope of this paper [Fer+01].

This paper is organized as follows. In Section 2 we define the notation we use to describe AES. In Section 3 we describe the property that the Square attack is based on. In Section 4 we describe how the Square attack can be applied to AES-128, and in Section 5 we describe how the Square can be applied to AES-192 and AES-256. We summarize our contribution and conclude in Section 6.

2. Preliminaries

In this paper, multiplications in \mathbb{F}_{2^8} are considered to be polynomial multiplications modulo the irreducible polynomial x^8 + x^4 + x^3 + x + 1. It should be clear from the context when a mathematical expression contains integer multiplication.

2.1 The Advanced Encryption Standard

The structure of the Advanced Encryption Standard (AES), as used to perform encryption, is illustrated in Algorithm 1. In discussing the AES we consider that all intermediate variables of the encryption operation variables are arranged in a 4 \times 4 array of bytes, referred to as the state matrix. For example, the 128-bit plaintext P = (p_1, p_2, \dots, p_{16}), where each p_i \in \{1, \dots, 16\} is one byte, is arranged as:

The encryption itself is conducted by the repeated use of a round function that comprises the following operations executed in sequence:

The AddRoundKey operation XORs each byte of the array with a byte from a corresponding subkey. In each instance of the AddRoundKey a fresh 16-byte subkey is used from the subkey bytes generated by the key schedule.

The SubBytes operation is the only nonlinear step of the block cipher, consisting of a substitution table applied to each byte of the state. This replaces each byte of the state matrix by its multiplicative inverse, followed by an affine mapping. In the remainder of this paper we will refer to the function S as this substitution table and S^{-1} as its inverse.

The ShiftRows operation is a byte-wise permutation of the state that operates on each row.

The MixColumns operation operates on the state column by column. Each column of the state matrix is considered as a vector where each of its four elements belong to \mathbb{F}_{2^8}. A 4 \times 4 matrix M whose elements are also in \mathbb{F}_{2^8} is used to map this column into a new vector. Here M and its inverse M^{-1} are defined as:

All the elements in M and M^{-1} are elements of \mathbb{F}_{2^8} expressed in decimal.

In Algorithm 1 we can see that the last round does not include the execution of a MixColumns operation. In all the attacks considered in this paper we will assume that the last round does not include a MixColumns operation. This is important to note since it has been shown that the presence of a MixColumns operation in the last round would affect the security of AES [DunKel10].

2.2 The Key Schedule

The key schedule generates a series of subkeys from the secret key. There are three variants of the AES corresponding to the three possible bit lengths of the secret key used, i.e. 128, 192 or 256 bits. The function S is the substitution function used in the SubBytes operation described above. The function f is, for the most part, the identity function. However, when K is a 256-bit key and f is the substitution function, f is a round constant that changes for each loop.

For AES-128, knowing one subkey will allow the original key to be derived. For AES-192 and AES-256 there will still be some ambiguity and two subkeys are required to derive the original key.

3. The Square Attack

If we consider two plaintexts that have a XOR difference that is non-zero in one byte, then this difference will expand in a known manner. After one round the XOR difference between the intermediate states would show that one column of the state matrix has a non-zero difference. This property will then propagate to all the bytes in the state matrix after the second round by the same reasoning.

It is therefore impossible that the XOR difference between two such plaintexts will be zero in any byte after two rounds. This property will persist until the next MixColumns operation, and is used for impossible differential cryptanalysis since the XOR difference after two rounds cannot be zero [BihKel99].

This property is also used to construct the Square attack (so-called since it was first presented in the description of the block cipher Square [DaeKnuRij97]) and was first presented in the original description of AES [DaeRij98]. We consider 256 distinct plaintexts that are equal in fifteen bytes. After computing two rounds of AES the property described above will be valid between all possible pairs, i.e. across all 256 intermediate states the bytes at each index will contain one of each possible value. The XOR sum of the 256 bytes at each index will therefore be equal to zero. There will not be one instance of each possible value across the 256 bytes at each index after the next MixColumns operation. However, the XOR sum of the bytes at each index will still be zero after the MixColumns operation, and this property will remain true until the next SubBytes operation. In the remainder of this paper we will refer to a set of 256 chosen plaintext-ciphertext pairs where the 256 distinct plaintexts are equal in fifteen bytes as a \delta-set.

4. Applying the Square Attack to AES-128

Attacks based on the Square attack applicable to AES-128 are presented in this section.

4.1 Analyzing Four-Round AES

An attack based on the property described in Section 3 was originally detailed by Daemen and Rijmen in their AES proposal [DaeRij98]. If we consider one \delta-set, the XOR sum of the intermediate states at the end of the third round is equal to zero. For a four-round variant of AES an attacker can use this observation to validate hypotheses on the last subkey byte-by-byte, where an attacker checks that the XOR sum of the input to the final round is equal to zero. For each byte this will return the correct subkey byte and one additional incorrect hypothesis per byte with a probability of 255/256. That is, any random sequence of bytes will have an XOR sum equal to zero with a probability of 1/256 and there are 255 such sequences. This will result in an expected total number of key hypotheses for the last subkey of \left(1 + \frac{255}{256}\right)^{16} \approx 2^{16}, since the length of the lists of hypotheses are mutually independent. One can determine the key if one repeats the analysis, i.e. one takes 2^9 chosen plaintexts and conducts the above analysis twice. This would have a time complexity of 2^9 one-round decryptions (2^7 encryptions of a four-round AES).

Biham and Keller observed the sum of a sequence of random bytes can be computed by only considering one example of values that occur with an odd-numbered frequency. Since values that occur with an even-numbered frequency will have no effect on the XOR sum across all 256 intermediate values [BihKel99].

We define Z as the number of instances of a given value that occur in a sequence of 256 bytes. The probability of observing a given value n times is

for 1 \le n \le 256. The probability of observing an odd number of a given value is therefore \Pr(X = 1) + \Pr(X = 3) + \ldots + \Pr(X = 255) = 0.43, and therefore the number of values that need to be treated decreases to 256 \times 0.43 = 110.

We define Y as the number of distinct values that occur in a sequence of 256 bytes. The probability of observing m distinct values is

for 1 \le m \le 256. We define r_{(m)} = r(r-1)\cdots(r-m+1) and \left\{\begin{smallmatrix} n \\ i \end{smallmatrix}\right\} as a function that returns the Stirling numbers of the second kind. That is, the number of ways of partitioning n elements into i non-empty sets. The expectation of Y is simply \sum_{i=1}^{256} i\,\Pr(Y=i) = 162.

For a sequence of 256 bytes that consist of m distinct values, the probability of observing a given value n times given that there are m distinct values is

for 1 \le m, n \le 256. We define A as the number of distinct values that occur with an odd-numbered frequency. Then the expectation of A is:

That is, the sum of the number of distinct values occurring with an odd-numbered frequency multiplied by the probability of it occurring. This would reduce the time complexity of an attack requiring two \delta-sets to 156 one-round decryptions (approximately 2^5 encryptions of a four-round AES).

4.2 Analyzing Five-Round AES

An extension to the above attack was also first presented in the original description of AES [DaeRij98]. This attack allowed an extra round to be analyzed with an increase in the time complexity. Rather than analyzing the final subkey byte-by-byte, one analyzes the penultimate subkey.

In order to do this one is obliged to guess 32 bits of the final subkey to determine one column of the state matrix before the XOR with the penultimate subkey. One can then compute the MixColumns operation on this column, and validate hypotheses on a byte of a subkey equivalent to the penultimate subkey. Each evaluation reduces the potential key space of five bytes being analyzed by a factor of 256, and one would need to conduct this analysis five times to determine 32 bits of the final subkey [DaeRij98].

Ferguson et al. present a way of conducting this attack that is referred to as the “partial sums” method [Fer+01]. They observe that conducting the attack involves computing

where S_\lambda, for \lambda \in \{0, \ldots, 3\}, are bijective look-up tables that consist of the function S and a multiplication by a field element from \mathbb{F}_{2^8}. These are evaluated efficiently by associating a “partial sum” x_k to each ciphertext where x_k is defined as

This gives a map from (c_0, c_1, c_2, c_3) \mapsto (x_k, c_{k+1}, \ldots, c_3). In order to conduct an attack one can compute (x_1, c_2, c_3) for all the ciphertexts in a \delta-set for all possible values of k_0 and k_1. This will take 2^{24} executions of the function S resulting in 2^{24} values for (x_1, c_2, c_3). Using the estimate provided by Ferguson et al., that the time complexity of one AES encryption is equivalent to 2^8 executions of the function S [Fer+01], implementing the attack described above will have a time complexity equivalent to approximately 2^{40} five-round AES encryption operations.

The analysis of the hypotheses can be further optimized if the relationship between the last and penultimate subkey are verified as the attack progresses. If we consider one \delta-set, one can analyze two columns of the penultimate subkey by guessing eight bytes of the last subkey (in two sets of four bytes). This will produce two sets of 2^{32} hypotheses with a time complexity equivalent to 2^{36} five-round AES encryption operations. One can then eliminate hypotheses in each set that are inconsistent, given that we have hypotheses on eight bytes of the penultimate key and eight bytes of the last subkey.

From the AES key schedule we can see that any subkey byte can be computed from two specific bytes in either the previous or following subkey. From the two sets of hypotheses generated, there will be three cases where known relationships between these sets of hypotheses can be verified. Given that the probability that all three bytes of a given hypothesis can be verified will be 1/2^{24}, one would expect that the two sets of 2^{32} hypotheses can be reduced to one set of 2^{40} hypotheses. Continuing in this fashion, one generates additional sets and verifies relationships until the full key is recovered.

The time complexity of the entire attack will be 2^{38} five-round AES encryption operations and require 2^{40} hypotheses to be stored in memory. If a second \delta-set is included the time complexity will increase, but the memory requirements will become negligible.

Table 1. Summary of the Square Attack on Five-Round AES-128.

4.3 Analyzing an Extra Round

The attack described above applied to a five-round AES can be extended to attack a six-round AES. In order to permit an extra round to be analyzed a set of 2^{32} plaintexts are chosen that give all the possible ciphertexts that differ at indexes 1, 6, 11, and 16. An attacker will then seek to choose the 256 plaintext-ciphertext pairs that produce intermediate states that differ in only one byte after one round, i.e. the input required to attack a five-round AES.

Ferguson et al. observed that all 2^{32} can be used as a set of acquisitions to conduct the Square attack [Fer+01]. That is, a set of 2^{32} distinct plaintexts differing at, for example, indexes 1, 6, 11, and 16 can be viewed as 2^{24} \delta-sets. An attacker can treat all 2^{32} acquisitions together. We refer to a set of 2^{32} plaintext-ciphertext pairs that are equivalent to 2^{24} \delta-sets as a \Delta-set.

An attack would proceed in the same manner as described in Section 4.2. Using the same notation the computation of the sets of (x_1, c_2, c_3) will require 2^{48} executions of the function S. This would result in 2^{32} triples, but a maximum of 2^{24} distinct values are possible. As described in Section 4.1, one only needs to keep one example of the triplets that occur with an odd-numbered frequency. The time complexity of the entire analysis requires 2^{50} executions of the function S for all four 32-bit sets for the final subkey, which corresponds to 2^{42} AES encryption operations.

We can reduce the time complexity further if we exploit the relationships between key bytes in adjacent subkeys, using the attack described in Section 4.2 to reduce the number of key hypotheses. Given one set of 2^{32} plaintext-ciphertext pairs an attack has time complexity equivalent to 2^{42} six-round AES encryption operations and requires 2^{40} key hypotheses to be stored in memory.

Table 2. Summary of the Square Attack on Six-Round AES-128.

5. Applying the Square Attack to AES-192 and AES-256

In this section we describe how the attacks described in Section 4 are applicable to AES-192 and AES-256.

5.1 Analyzing Five-Round AES

Attacking a five-round AES-192 will function using a time complexity equivalent to 2^{39} AES encryption operations using the attack described in Section 4.2 based on the attack proposed by Ferguson et al. [Fer+01]. That is, two \delta-sets would be sufficient to determine the last two subkeys of a five-round instance of AES-192 or AES-256.

An attack on an instance of AES-256 cannot be made more efficient by analyzing two consecutive subkeys since there are no direct relationships. However, one can exploit the relationships between two consecutive subkeys when attacking an AES-192. This would follow a similar technique to that presented in Section 4.2.

Table 3. Summary of the Square Attack on Five-Round AES-192.

Table 4. Summary of the Square Attack on Five-Round AES-256.

5.2 Analyzing Six-Round AES

The attacks on five rounds of AES-192 and AES-256 can be extended by assuming that an attacker knows the last subkey. The time complexity of the five-round attack does increase by a factor of 2^{128} when it is applied to a six round variant of AES-256. However, Lucks observed that knowledge of the last subkey would allow an attacker to directly derive bytes in previous subkeys when attacking AES-192 [Luc00]. That is, 64 bits of the penultimate subkey and 32 bits of the antepenultimate subkey.

Following the reasoning in Section 4.2, a computational effort equivalent to 2^{22} (i.e. a factor of 2^{16} less than the standard attack) six-round AES-192 encryption operations to treat each \delta-set. As previously, two \delta-sets would be sufficient to determine the penultimate and antepenultimate subkeys.

Table 5. Summary of the Square Attack on Six-Round AES-192 using \delta-sets.

Table 6. Summary of the Square Attack on Six-Round AES-256 using \delta-sets.

We can also note that introducing an extra round before, and acquiring \Delta-sets will lead to a more efficient attack. This involves conducting the five-round attack described in Section 5.1 on a six-round AES using \Delta-sets rather than \delta-sets.

Table 7. Summary of the Square Attack on Six-Round AES-192 using \Delta-sets.

Table 8. Summary of the Square Attack on Six-Round AES-256 using \Delta-sets.

5.3 Analyzing an Extra Round

As described in Section 4.3, an extra round can be added where an attacker uses \Delta-sets [Fer+01]. Given that a large amount of the penultimate subkey is known the “partial sums” method of conducting the Square attack can be further optimized. We recall that the attack requires that (5) is evaluated as described in Section 4.2. Note that the attack does not proceed exactly as the six-round attack given in Section 5.2 as the relationships between the bytes of the subkeys will be different.

If, for example, an attacker wishes to evaluate (5) and knows (k_0, k_1) these values can be evaluated before the unknown (k_2, k_3). Generating 2^{24} values for (x_1, c_2, c_3) will require 2^{33} executions of the function S. Then 2^{16} values for (x_2, c_3) per hypothesis for k_2 can be generated with 2^{32} executions of the function S, and continue as per the attack described in Section 4.3. The time complexity of the entire analysis will be 2^{34} evaluations of the function S. That is, 2^{36} executions of the function S for all four 32-bit sets for the final subkey, which corresponds to 2^{28} AES encryption operations.

Table 9. Summary of the Square Attack on Seven-Round AES-192.

Table 10. Summary of the Square Attack on Seven-Round AES-256.

6. Conclusion

In this paper we have demonstrated that the “partial sums” method of conducting the Square attack can be improved by analyzing more information per \delta-set (or \Delta-set). This allows the time complexity of attacks to be halved. For AES-128 the time complexity can be halved again, and reduced by a smaller amount for AES-192, by eliminating key hypotheses on-the-fly.

In Table 11 we present a summary of the attacks presented in this paper alongside similar attacks in the literature. The memory requirements are the number of state matrices, or equivalent, that need to be stored in memory. The number of acquisitions are the number of chosen plaintexts enciphered with an unknown key, where the number is given in multiples of 2^8 or 2^{32} so that it is clear how many \delta or \Delta-sets are required to conduct the attack. The time complexity is expressed as the computational effort required to compute that many AES encryption operations.

In this paper we have focused on attacks that require relatively few chosen plaintext-ciphertext pairs. Ferguson et al. also proposed a Square attack applicable to seven rounds of AES-128 and eight rounds for AES-192 and AES-256. However, this attack requires approximately 2^{128} chosen plaintext-ciphertext pairs and is beyond the scope of this paper although one would expect the proposed strategy to aid in the analysis.

Table 11. Summary of attacks presented in this paper.

Appendix A: Using the Key Schedule to Complement the Square Attack on Five-Round AES-128

In this section we describe an example of the attack presented in Section 4.2. We assume the worst case where an attacker only has one \delta-set. We define the last two subkeys as

and

If an attacker has a \delta-set, one can guess the key bytes \{k_{5,1}, k_{5,14}, k_{5,11}, k_{5,8}\} which will allow hypotheses to be formed on each element of \{k_{4,1}, k_{4,2}, k_{4,3}, k_{4,4}\} independently. With a time complexity equivalent to 2^{18} five-round AES encryptions one would expect to obtain 2^{32} hypotheses for

which can be stored in a hash table. One can then conduct the same analysis by making hypotheses on \{k_{5,13}, k_{5,10}, k_{5,7}, k_{5,4}\} to derive hypotheses on \{k_{4,13}, k_{4,14}, k_{4,15}, k_{4,16}\}. This provides 2^{32} hypotheses for

As each element in \gamma_2 is generated the following relationships between the elements in \gamma_2 and \gamma_1 can be verified:

and

A given element of \gamma_2 will therefore have 2^8 elements in \gamma_1 that will satisfy these constraints. The resulting 2^{40} hypotheses for \{\gamma_1, \gamma_2\} can also be stored in a hash table.

One can continue to derive 2^{32} hypotheses for

For each element in \gamma_3 an attacker can verify the following relationships:

and

Again the resulting 2^{40} hypotheses for \{\gamma_1, \gamma_2, \gamma_3\} can be stored in a hash table. Lastly, one can perform the same analysis on

Each element from \gamma_4 can be used to see if a valid pair \{K_4, K_5\} has been found by searching in \{\gamma_1, \gamma_2, \gamma_3\} for values that satisfy the remaining relationships between the two subkeys:

Given that an incorrect hypothesis for \{K_4, K_5\} will validate these equations with a probability of 1/2^{8 \cdot 9} = 1/2^{72}, one would expect to have two hypotheses for \{K_4, K_5\} (i.e. the correct key and one incorrect one that fulfills the criteria by chance) and therefore two hypotheses for the AES key.

Appendix B: Using the Key Schedule to Complement the Square Attack on Five-Round AES-192

In this section we describe an example of the attack presented in Section 5.1. We assume the worst case where an attacker only has one \delta-set. We define the last two subkeys K_4 and K_5 identically to Appendix A.

As previously, one can guess \{k_{5,1}, k_{5,14}, k_{5,11}, k_{5,8}\} to obtain 2^{32} hypotheses for \gamma_1. One can then conduct the same analysis by making hypotheses on \{k_{5,13}, k_{5,10}, k_{5,7}, k_{5,4}\} to derive hypotheses on \{k_{4,5}, k_{4,6}, k_{4,7}, k_{4,8}\}. This provides 2^{32} hypotheses for

As each element in \gamma_2 is generated the following relationships can be verified:

A given element of \gamma_2 will therefore have 2^{16} elements in \gamma_1 that will satisfy these constraints. This will result in 2^{48} hypotheses for \{\gamma_1, \gamma_2\}. Continuing to derive 2^{32} hypotheses for

For each element in \gamma_3 the following relationships can be verified:

This will result in 2^{64} hypotheses for \{\gamma_1, \gamma_2, \gamma_3\} and the set

can be used to check if a valid pair \{K_4, K_5\} has been found by searching in \{\gamma_1, \gamma_2, \gamma_3\} for values satisfying the remaining relationships:

and

Given that an incorrect hypothesis for \{K_4, K_5\} will validate these equations with a probability of 1/2^{8 \cdot 4} = 1/2^{32}, one would expect to have 2^{64} hypotheses for \{K_4, K_5\}.

References

• [BahAre08] B. Bahrak and M. R. Aref. “Impossible differential attack on seven-round AES-128”. IET Information Security Journal, 2(2):28–32, 2008.
• [BihKel99] E. Biham and N. Keller. “Cryptanalysis of reduced variants of Rijndael”. Unpublished, 1999.
• [BogKhoRec11] A. Bogdanov, D. Khovratovich, and C. Rechberger. “Biclique cryptanalysis of the full AES”. In D. H. Lee and X. Wang, editors, ASIACRYPT 2011, volume 7073 of LNCS, pages 344–371. Springer, 2011.
• [DaeKnuRij97] J. Daemen, L. Knudsen, and V. Rijmen. “The block cipher Square”. In E. Biham, editor, FSE ’97, volume 1267 of LNCS, pages 149–165. Springer, 1997.
• [DaeRij98] J. Daemen and V. Rijmen. “AES proposal: Rijndael”. In AES Round 1 Technical Evaluation CD-1: Documentation. NIST, August 1998.
• [DunKel10] O. Dunkelman and N. Keller. “The effects of the omission of last round’s MixColumns on AES”. Information Processing Letters, 110(8–9):304–308, 2010.
• [Fer+01] N. Ferguson, J. Kelsey, S. Lucks, B. Schneier, M. Stay, D. Wagner, and D. Whiting. “Improved cryptanalysis of Rijndael”. In B. Schneier, editor, FSE 2000, volume 1978 of LNCS, pages 213–230. Springer, 2001.
• [FIPS01] FIPS PUB 197. “Advanced encryption standard (AES)”. Federal Information Processing Standards Publication 197, National Institute of Standards and Technology (NIST), Gaithersburg, MD, USA, November 2001.
• [Lu+08] J. Lu, O. Dunkelman, N. Keller, and J. Kim. “New impossible differential attacks on AES”. In D. R. Chowdhury, V. Rijmen, and A. Das, editors, INDOCRYPT 2008, volume 5365 of LNCS, pages 279–293. Springer, 2008.
• [Luc00] S. Lucks. “Attacking seven rounds of Rijndael under 196-bit and 256-bit keys”. In AES Candidate Conference 2000, 2000.
• [ManOswPop07] S. Mangard, E. Oswald, and T. Popp. Power Analysis Attacks: Revealing the Secrets of Smart Cards. Springer-Verlag, 2007.
• [ZhaWuFen07] W. Zhang, W. Wu, and D. Feng. “New results on impossible differential cryptanalysis of reduced AES”. In K.-H. Nam and G. Rhee, editors, ICISC 2007, volume 4817 of LNCS, pages 239–250. Springer, 2007.