The Exchange Attack: How to Distinguish Six Rounds of AES with 2^{88.2} Chosen Plaintexts

Abstract

In this paper we present exchange-equivalence attacks which is a new cryptanalytic attack technique suitable for SPN-like block cipher designs. Our new technique results in the first secret-key chosen plaintext distinguisher for 6-round AES. The complexity of the distinguisher is about 2^{88.2} in terms of data, memory and computational complexity. The distinguishing attack for AES reduced to six rounds is a straightforward extension of an exchange attack for 5-round AES that requires 2^{30} in terms of chosen plaintexts and computation. This is also a new record for AES reduced to five rounds. The main result of this paper is that AES up to at least six rounds is biased when restricted to exchange-invariant sets of plaintexts.

Keywords: SPN, AES, Exchange-Equivalence Attacks, Exchange-Invariant Sets, Exchange-Equivalence Class, Secret-Key model, Differential Cryptanalysis

1. Introduction

Block ciphers are typically designed by iterating an efficiently computable round function many times in the hope that the resulting composition behaves like a randomly drawn permutation. The designer is typically constrained by various practical criterion, e.g. security target, implementation boundaries, and specialized applications, that might lead the designer to introduce symmetries and structures into the round function as a compromise between efficiency and security. In the compromise, a round function is iterated enough times to make sure that any symmetries and structural properties that might exist in the round function vanish. Thus, a round function is typically designed to increasingly decorrelate with structure and symmetries after several rounds. However, what actually constitutes structure is an open question which requires continuous investigation as long as using randomly drawn codebooks is out of reach.

Low data- and computational-complexity distinguishers and key-recovery attacks on round-reduced block ciphers have recently gained renewed interest in the literature. There are several reasons for this. In one direction cryptanalysis of block ciphers has focused on maximizing the number of rounds that can be broken without exhausting the full codebook and key space. This often leads to attacks marginally close to that of pure brute-force. These are attacks that typically have been improved over time based on many years of cryptanalysis. The most successful attacks often become de-facto standard methods of cryptanalysis for a particular block cipher and might discourage anyone from pursuing new directions in cryptanalysis that do not reach the same number of rounds. This in itself might hinder new breakthroughs, thus it can be important to investigate new promising ideas that might not have reached its full potential yet. New methods of cryptanalysis that break or distinguish fewer rounds faster but with lower complexity than established cryptanalysis is therefore interesting in this process. Many constructions employ reduced round AES as part of their design. On the other hand, reduced versions of AES have nice and well-studied properties that can be favorable as components of larger designs (see for instance Simpira [GM16]).

The security of Rijndael-type block cipher designs is believed to be a well-studied topic and has been in the focus of a large group of cryptanalysts during the last 20 years (e.g. see [Rij97, BK00, KW02, DR06, DR07, BDD+12, DF16, GRR16]). Thus, it is rather surprising that new and quite fundamental results continuously appear for 2–4 rounds of AES that enables completely new types of more efficient attacks for an increasing number of rounds of AES. At Crypto 2016, the authors of [SLG+16] presented the very first secret-key 5-round distinguisher for AES. Secret-key (or key-independent) means that the attack does not care about the particular round keys (e.g. in contrast to related-key attacks). They extend a 4-round integral property to 5 rounds by exploiting properties of the AES MixColumn matrix. Although their distinguisher requires the whole codebook, it spawned a series of new fundamental results for AES. It was later improved to 2^{98.2} chosen plaintexts with 2^{107} computations by extending a 4-round impossible differential property to a 5-round property. Then, at Eurocrypt 2017, the authors of [GRR17] proposed the first 5-round secret-key chosen plaintext distinguisher which requires 2^{32} chosen texts with a computational cost of 2^{35.6} look-ups into memory of size 2^{36} bytes. They showed that by encrypting cosets of certain subspaces of the plaintext space the number of times the difference of ciphertext pairs lie in a particular subspace of the state space always is a multiple of 8.

Later, at Asiacrypt 2017, the authors of [RBH17] presented new fundamental properties for Rijndael-type block cipher designs leading to new types of 3- to 6-round secret-key distinguishers for AES that beats all previous records. The authors introduced a new deterministic 4-round property in AES, which states that sets of pairs of plaintexts that are equivalent by exchange of any subset of diagonals encrypts to a set of pairs of ciphertexts after four rounds that all have a difference of zero in exactly the same columns before the final linear layer. This was further explored in [Gra18] under the name “mixture cryptanalysis”.

1.1 Our Contribution

The first 5-round secret-key chosen-plaintext distinguisher for AES was introduced at Crypto 2016, almost 20 years after Rijndael was first proposed as a candidate in the AES-competition, and required the whole codebook. In this paper, only three years later, we introduce the first 6-round secret-key distinguisher for AES that has complexity of about 2^{88.2} computations and ciphertexts. This is a giant leap for cryptanalysis of AES. Our distinguishers are based on simple techniques which are easy to verify theoretically and in practice. Moreover, we prove that AES up to at least 6 rounds is biased on exchange-invariant sets. The 5-round distinguisher has been practically verified on a scaled down version in C/C++ on a standard laptop.

1.2 Overview of This Paper and Main Results

In Section 2 we briefly describe results and notation that makes up the machinery for the rest of this paper. In particular, we describe what we call exchange operators, exchange-invariant sets and exchange-equivalence classes, and their relations to AES. In Section 3, we prove that five full rounds of AES is biased on exchange-invariant sets and in Section 4 and Section 5 we turn this result into simple distinguishers for AES reduced to five and six rounds.

The currently best secret-key distinguishers for 5- and 6-round AES are given in Table 1. We adopt that data complexity is measured in a minimum number of chosen plaintexts/ciphertexts CP/CC or adaptively chosen plaintexts/ciphertexts ACP/ACC. Time complexity is measured in equivalent number of AES encryptions (E), memory accesses (M) and/or XOR operations (XOR) — adopting that 20M \approx 1 round of AES.

2. Preliminaries

The Advanced Encryption Standard (AES) [DR02] is the most widely adopted block cipher in the world today and is a critical component in protecting information in both commercial and high-assurance communication. The AES internal state is typically represented by a 4 by 4 matrix in \mathbb{F}_{2^8}^{4 \times 4}. One full round of AES consists of SubBytes (SB), ShiftRows (SR), MixColumns (MC) and AddKey (AK). The SB-layer applies a fixed permutation over \mathbb{F}_{2^8} independently to each byte of the state, the SR-layer cyclically shifts the i-th row by i positions, while the MC-layer applies a fixed linear transformation to each column. One full round is composed as R = AK \circ MC \circ SR \circ SB. We write R^t(x) to mean t rounds of AES where each round key is fixed to some random value.

2.1 Collision and Multicollision in a Set

The expected number of collision and multicollision in a set are computed in [Jou09]. Suppose m objects taken uniformly at random from a given set of size N. Then the expected number of collisions is \frac{m(m-1)}{2N}. The expected number of multicollisions is:

3. When Column Exchange Equals Diagonal Exchange

In this section we describe the intersection of column exchange and diagonal exchange, i.e. the probabilistic case when exchange of some diagonals between a pair of plaintexts is equal to exchange of (possibly some other) diagonals after one round. We combine this with Theorem 3 to form a probabilistic version that instructs us how to construct a chosen-plaintext distinguisher for five rounds of AES.

It is easy to see that |D_I \cap C_J| = |I| \cdot |J| and |D_I \cup C_J| = 4(|I| + |J|) - |I| \cdot |J|.

For instance, if |K| = 2 and |I| = 1, the relation holds with probability P_5(1,2) \approx 2^{-28.2}.

4. The Exchange Attack on Five Rounds AES

Theorem 6 can be used directly to show that AES limited to five full rounds is biased when plaintexts are closed under the action of diagonal exchange operations. For a random permutation f(x), the probability that both the original and exchanged ciphertext pairs satisfy the same column-zero pattern is

But for AES, by Theorem 6:

Setting |I| = 1, |K| = 2 gives P_5(1,2) > 2^{-28.2} versus 2^{-32} for random. With m = 2^{15}:

Thus, by encrypting |A| \approx 2^{30} plaintexts from a diagonal exchange-invariant set, we distinguish AES from random.

4.1 Complexity of Distinguisher

The algorithm consists of two parts. In part 1, the adversary encrypts D = m^2 = 2^{30} plaintexts and inserts indices into hash tables T_k. The complexity is roughly C_{\text{part1}} \approx D. For part 2, finding collisions:

Hence, five rounds of AES can be distinguished with D = 2^{30} chosen plaintexts and about the same computational complexity.

5. The Exchange Attack on Six Rounds AES

In this section we present the first 6-round secret-key chosen plaintext distinguisher for AES. Assume the following two conditions:

If we observe a ciphertext pair satisfying the second condition (probability P_{R6} = 2^{-94} at random), then by Theorem 4 the first condition holds with probability P_{R5} = 2^{-22}. By Theorem 6, the exchanged pair satisfies the same relation with probability P_5(3,1) \approx 2^{-38}. The total probability that the exchanged pair also satisfies the ciphertext condition is

Thus:

5.1 Distinguishing Attack Algorithm for Six Rounds

We pick three sets A_0, A_1, A_2, each of size \approx 2^{29.4}, to generate a diagonal exchange-invariant set of D = 2^{88.2} plaintexts where the i-th diagonal is spanned by A_i and the last diagonal is a random constant. The algorithm is the same as the 5-round distinguisher with changed parameters and collision condition.

5.2 Complexity of Distinguisher

The first part costs roughly C_{\text{part1}} \approx D. For part 2, the expected complexity is

The total complexity is dominated by D = 2^{88.2} in data, memory, and computation.

6. Conclusion

In this paper we have introduced the first 6-round secret-key chosen-plaintext distinguisher for AES using a new type of attack called exchange-equivalence attacks. The distinguisher has data and computational complexity of only 2^{88.2} and can thus be viewed as a giant leap in the cryptanalysis of AES. All of our attacks can easily be turned into chosen ciphertext attacks on the inverted block cipher due to the inherent symmetry of the properties we are using. Our results are easily generalized to any SPN-like cipher, and in particular, we note that the theory can be generalized to extend attacks for more rounds for ciphers with slower diffusion (e.g. lightweight designs). We are confident that our results lead the way to further breakthroughs on ciphers such as AES.

7. Acknowledgments

We thank the anonymous reviewers for their valuable comments and suggestions. This research was supported by the Norwegian Research Council.

References

• [BK00] Biham, E., Keller, N.: Cryptanalysis of reduced variants of Rijndael. In: 3rd AES Conference. vol. 230 (2000)
• [BDD+12] Bouillaguet, C., Derbez, P., Dunkelman, O., Fouque, P.A., Keller, N., Rijmen, V.: Low-data complexity attacks on AES. IEEE Transactions on Information Theory 58(11), 7002–7017 (2012)
• [DR07] Daemen, J., Rijmen, V.: Plateau characteristics. IET Information Security 1, 11–17 (2007)
• [DR02] Daemen, J., Rijmen, V.: The design of Rijndael: AES the Advanced Encryption Standard. Springer (2002)
• [DR06] Daemen, J., Rijmen, V.: Understanding two-round differentials in AES. In: SCN 2006, pp. 78–94. Springer (2006)
• [DF16] Derbez, P., Fouque, P.A.: Automatic search of meet-in-the-middle and impossible differential attacks. In: CRYPTO 2016, pp. 157–184. Springer (2016)
• [Gra18] Grassi, L.: Mixture differential cryptanalysis: a new approach to distinguishers and attacks on round-reduced AES. IACR Trans. Symmetric Cryptol. 2018(2), 133–160 (2018) [page on this site]
• [GRR16] Grassi, L., Rechberger, C., Rønjom, S.: Subspace trail cryptanalysis and its applications to AES. IACR Trans. Symmetric Cryptol. 2016(2), 192–225 (2016)
• [GRR17] Grassi, L., Rechberger, C., Rønjom, S.: A new structural-differential property of 5-round AES. In: EUROCRYPT 2017, pp. 289–317. Springer (2017)
• [GM16] Gueron, S., Mouha, N.: Simpira v2: A family of efficient permutations using the AES round function. In: ASIACRYPT 2016, pp. 95–125. Springer (2016)
• [Jou09] Joux, A.: Algorithmic Cryptanalysis. Chapman & Hall/CRC, 1st edn. (2009)
• [KW02] Knudsen, L.R., Wagner, D.: Integral cryptanalysis. In: FSE 2002, pp. 112–127 (2002)
• [Rij97] Rijmen, V.: Cryptanalysis and design of iterated block ciphers. Doctoral Dissertation, K.U.Leuven (1997)
• [RBH17] Rønjom, S., Bardeh, N.G., Helleseth, T.: Yoyo tricks with AES. In: ASIACRYPT 2017, pp. 217–243 (2017)
• [SLG+16] Sun, B., Liu, M., Guo, J., Qu, L., Rijmen, V.: New insights on AES-like SPN ciphers. In: CRYPTO 2016, pp. 605–624. Springer (2016)