A Key-Independent Distinguisher for 6-round AES in an Adaptive Setting

Abstract

In this paper, we study the results of the recently proposed exchange attack in an adaptive setting. As expected, it leads to present a better 6-round key-independent distinguisher in terms of data and computational complexities. More specifically, our 6-round adaptive distinguisher requires 2^{83} chosen plaintexts and 2^{83} adaptively chosen ciphertexts and has a computational cost of 2^{83} encryption.

Keywords: SPN, AES, Exchange Attack, Secret-Key model, Difference Cryptanalysis

1   Introduction

In 2000, Rijndael block cipher is accepted as AES (Advance Encryption Standard) by NIST. AES is provably resistant against differential and linear cryptanalysis. During the last 20 years, among to large amount researches [Rij97, BK00, KW02, DR06, DR07, Bou+12, DF16]), there is only the biclique attack [BKR11] which can break AES faster than exhaustive search. Up to now, the best known key recovery attack in secret key model can break 7-round of AES.

Integral and impossible differential distinguishers on 4-round AES, in secret key model, were best distinguishers (in term of reaching highest rounds) for several years. Recently, since 2016, new developments has been presented for round-reduced AES. These developments showed several basic and unexplored properties for round-reduced AES. First 5-round distinguishers have been appeared in several studies [Sun+16, GRR16, RBH17, BR19b, GR18, BGL19, BR19a]. Some of these 5-round distinguishers have gained more attentions since they can be extended to 6-round distinguishers.

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} . The matrix representation is for the most part purely representational as the actual properties of the matrix (e.g. rank, order etc.) are not actually exploited for anything. 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. The key addition adds a secret round-dependent value to the state. One full round is composed as R = AK \circ MC \circ SR \circ SB . We follow standard convention and simplify notation by writing R^t(x) to mean t rounds of AES where each round key is fixed to some random value.

We recall the exchange attack presented in [BR19a]. Here, we recall the basic definitions and Theorems presented in the exchange attack to use them for presenting our results.

A pair of states define a set of 2^{wt_c(\alpha \oplus \beta)} possible column exchange differences where wt_c(x) denotes the number of non-zero columns of x. We can now define three related operators that exchange diagonal, column and mixed values between a pair of AES states.

To indicate the zero column(s) of a state x \in \mathbb{F}_{2^8}^{4 \times 4} , we define \nu(x) which denotes the binary indicator vector which is 0 in position i if the i-th column of x is zero and 1 otherwise. We also are interested to know the zero column of a state after/before the first and last linear layer so we define, L = SR \circ MC, \nu_m(x) = \nu(L^{-1}(x)) and \nu_d(x) = \nu(SR(x)). For a subset I \subset \{0, 1, 2, 3\} , we write v^I \in \mathbb{F}_2^4 to mean the indicator vector which has value v^I_i = 1 if i \in I and 0 otherwise.

We remark that the result of previous Theorem works as well in decryption direction by applying an appropriate exchange operation considering the corresponding linear layer.

3   5-round ACC Distinguisher

In this section we show how one can use the result of Theorem 2 in an adaptive setting.

Since ciphertexts are random, we consider only the case |K| = 0 in Theorem 3. We can set up a 5-round distinguisher based on the result of Theorem 3. The idea is to generate a new plaintext pair adaptively such that:

Let \operatorname{wt}(\nu_d(p^0 \oplus p^1)) = d , then if p_5(|I|, 0) is higher than 2^{-32 \cdot (4 - d)}, the probability of this event at random, we can distinguish 5-round AES from a random permutation. If we set d = 2 (i.e. the difference of the plaintexts is zero in two diagonals) and |I| = 1 then we get that p_5(|I|, 0) = 2^{-46} while it is 2^{-64} for random case.

Now, to set up a 5-round distinguisher, adversary prepares 2^{23.5} plaintexts where bytes in the first two diagonals take random values and other diagonals take a random constant. Then he can generate 2^{46} pairs and at least one of them verifies the upper trail of Figure 1. Then he applies the Mixed exchange operator to all ciphertext pairs and decrypts new ciphertext pairs. So he expects to observe a new plaintext pair such that

Thus adversary can distinguish 5-round AES from a random permutation using 2^{23.5} chosen plaintexts and 2 \cdot 2^{46} = 2^{47} adaptively chosen ciphertexts. The data complexity can be reduced by adding a certain condition on the ciphertext pairs. Suppose that after 3-round encryption, the k-th diagonal in the difference of states, R^3(p^i) \oplus R^3(p^j) , is zero then adversary can filter ciphertext pairs which have a zero column in their difference before last linear layer. So the probability of exchange trail is 2^{-46-24} = 2^{-70} . Now adversary prepares 2^{35.5} plaintexts where the first two diagonals take 2^{35.5} random values, and the remaining diagonals are fixed to a constant. Thus he can construct 2^{70} ciphertext pairs and filter the ciphertext pairs such that only 2^{70-32} = 2^{38} of them are remained. For each of remaining pairs, he decrypts the new ciphertext pair formed by applying the mixed exchange operation on them, \rho_m^{v^I}, and estimates one of new generated plaintext pair is differ in the first two diagonals. Hence, he can distinguish 5-round AES from a random permutation using 2^{35.5} chosen plaintexts and 2 \cdot 2^{38} = 2^{39} adaptively chosen ciphertexts.

4   6-round ACC Distinguisher

In this section we present a 6-round key-independent distinguisher for AES in an adaptive setting. We extend the 5-round distinguisher to 6-round one by adding one round at beginning of it. Now, the idea of setting up a distinguisher is as follows. Suppose a plaintext pair, which differ in only a diagonal, verifies the upper trail in Figure 2. Then we generate two new ciphertexts by

and decrypt them. Then according to Theorem 3, we have that

with probability 2^{-46}. Also we are interested in the following condition:

This condition happens with probability 2^{-22} \cdot 2^{-22} (2^{-22} for each pair). So, in total, with probability (2^{-22})^2 \cdot 2^{-46} = 2^{-90} we expect that we have two new plaintexts, p'^{0} and p'^{1}, such that they differ in only one diagonal. For a random permutation, the probability that two plaintexts differ in only one diagonal is 4 \cdot 2^{-96} = 2^{-94} . Now, we prepare a structure of 2^{32} plaintexts where the first diagonal takes all possible 2^{32} values, and the remaining diagonals are fixed to some constants. Thus we can construct 2^{63} plaintext pairs and thus we will need to encrypt 2^{90-63} = 2^{27} structures. Hence, we can distinguish 6-round AES from a random permutation using 2^{32+27} = 2^{59} chosen plaintexts and 2 \cdot 2^{90} = 2^{91} adaptively chosen ciphertexts.

Similar to the 5-round distinguisher, the data complexity can be reduced by adding a certain condition on the ciphertext pairs. Suppose that after 4-round encryption, the k-th diagonal in state difference is zero. Then we can decrypt ciphertext pairs which the k-th column of L^{-1}(c^i \oplus c^j) is zero. So the total probability changes to (2^{-22})^2 \cdot 2^{-46} \cdot 2^{-24} = 2^{-114} . The structure of plaintexts can take 2^{32} values, and so we can construct 2^{63} pairs. Now we need to encrypt 2^{114-63} = 2^{51} structures and filter the ciphertext pairs such that only 2^{114-32} = 2^{82} of them are remained. For each of remaining pairs we decrypt the new pair formed by applying the mixed exchange operation on them, \rho_m^{v^I}. Now, we expect that there is a new plaintext pair which differ in a diagonal and thus we can distinguish 6-round AES from a random permutation using 2^{32+51} = 2^{83} chosen plaintexts and 2 \cdot 2^{82} = 2^{83} adaptive chosen ciphertexts.

for each structure do
  C ← {}
  T = {};  // empty hash table containing
            // unordered sets (e.g. unordered multisets)

  Ask for a structure P of 2^32 plaintexts p^i
  where bytes in diagonal 0 take all values

  C ← C ∪ {c^i}
  z ← |L^(-1)(c^i)_k|
    // |L^(-1)(c^i)_k| is an integer value of k-th column
  T[z] ← T[z] ∪ {i}

  for each c^i in C do    // 2^31 pairs are remained
    for a in T[|c^i|] do
      j ← T[|c^i|][a]
      c'^i = rho_m^(v^I)(c^i, c^j)
      c'^j = rho_m^(v^I)(c^j, c^i) for a fixed I with |I|=1

      Ask for decryption of c'^i and c'^j
      if wt(nu_d(p'^i xor p'^j)) equals 1 then
        return 1
      end
    end
  end
end
return -1

5   Acknowledgments

The author would like thank Sondre Rønjom for fruitful discussions and helpful comments.

6   Conclusion

In this paper we have investigated the results of exchange attack in an adaptive setting. So, we improve the current best 6-round key-independent distinguisher. Our proposed distinguisher requires 2^{83} chosen plaintexts and 2^{83} adaptively chosen ciphertexts and has a computational cost of 2^{83} encryption.

References

• [BGL19] Zhenzhen Bao, Jian Guo, and Eik List. Extended expectation cryptanalysis on round-reduced AES. Cryptology ePrint Archive, Report 2019/622, 2019.
• [BR19a] Navid Ghaedi Bardeh and Sondre Rønjom. The exchange attack: How to distinguish 6 rounds of AES with 2^{88.2} chosen plaintexts. Cryptology ePrint Archive, Report 2019/652, 2019. [page on this site]
• [BR19b] Navid Ghaedi Bardeh and Sondre Rønjom. Practical attacks on reduced-round AES. Cryptology ePrint Archive, Report 2019/770, 2019.
• [BK00] Eli Biham and Nathan Keller. Cryptanalysis of reduced variants of Rijndael. In 3rd AES Conference, volume 230, 2000.
• [BKR11] Andrey Bogdanov, Dmitry Khovratovich, and Christian Rechberger. Biclique cryptanalysis of the full AES. In Advances in Cryptology – ASIACRYPT 2011, pages 344–371, 2011.
• [Bou+12] C. Bouillaguet, P. Derbez, O. Dunkelman, P. A. Fouque, N. Keller, and V. Rijmen. Low-data complexity attacks on AES. Volume 58, pages 7002–7017, Nov 2012.
• [DR07] J. Daemen and V. Rijmen. Plateau characteristics. Volume 1, pages 11–17, 2007.
• [DR02] Joan Daemen and Vincent Rijmen. The design of Rijndael: AES – the Advanced Encryption Standard. Springer, 2002.
• [DR06] Joan Daemen and Vincent Rijmen. Understanding two-round differentials in AES. In Security and Cryptography for Networks: 5th International Conference, SCN 2006, pages 78–94, 2006.
• [DF16] Patrick Derbez and Pierre-Alain Fouque. Automatic search of meet-in-the-middle and impossible differential attacks. In Advances in Cryptology – CRYPTO 2016, pages 157–184, 2016.
• [GR18] Lorenzo Grassi and Christian Rechberger. Rigorous analysis of truncated differentials for 5-round AES. Cryptology ePrint Archive, Report 2018/182, 2018. [page on this site]
• [GRR16] Lorenzo Grassi, Christian Rechberger, and Sondre Rønjom. Subspace trail cryptanalysis and its applications to AES. IACR Trans. Symmetric Cryptol., 2016(2):192–225, 2016. [page on this site]
• [GRR17] Lorenzo Grassi, Christian Rechberger, and Sondre Rønjom. A new structural-differential property of 5-round AES. In Advances in Cryptology – EUROCRYPT 2017, pages 289–317, 2017.
• [KW02] Lars R. Knudsen and David Wagner. Integral cryptanalysis. In Fast Software Encryption, FSE 2002, pages 112–127, 2002.
• [Rij97] Vincent Rijmen. Cryptanalysis and design of iterated block ciphers. Doctoral Dissertation, K.U.Leuven, 1997.
• [RBH17] Sondre Rønjom, Navid Ghaedi Bardeh, and Tor Helleseth. Yoyo tricks with AES. In Advances in Cryptology – ASIACRYPT 2017, pages 217–243, 2017.
• [Sun+16] Bing Sun, Meicheng Liu, Jian Guo, Longjiang Qu, and Vincent Rijmen. New insights on AES-like SPN ciphers. In Advances in Cryptology – CRYPTO 2016, pages 605–624, 2016.