Mixture Differential Cryptanalysis and Structural Truncated Differential Attacks on Round-Reduced AES

Abstract

At Eurocrypt 2017 the first secret-key distinguisher for 5-round AES – based on the “multiple-of-8” property – has been presented. Although it allows to distinguish a random permutation from an AES-like one, it seems rather hard to implement a key-recovery attack different than brute-force like using such a distinguisher.

In this paper we introduce Mixture Differential Cryptanalysis on round-reduced AES-like ciphers, a way to translate the (complex) “multiple-of-8” 5-round distinguisher into a simpler and more convenient one (though, on a smaller number of rounds). Given a pair of chosen plaintexts, the idea is to construct new pairs of plaintexts by mixing the generating variables of the original pair of plaintexts. Here we theoretically prove that for 4-round AES the corresponding ciphertexts of the original pair of plaintexts lie in a particular subspace if and only if the corresponding pairs of ciphertexts of the new pairs of plaintexts have the same property. Such secret-key distinguisher – which is independent of the secret-key, of the details of the S-Box and of the MixColumns matrix (except for the branch number equal to 5) – can be used as starting point to set up new key-recovery attacks on round-reduced AES.

As a second contribution, we show how to combine this new 4-round distinguisher with a modified version of a truncated differential distinguisher in order to set up new 5-round distinguishers, that exploit properties which are independent of the secret key, of the details of the S-Box and of the MixColumns matrix.

Even if such 5-round distinguishers have higher complexity than e.g. the “multiple-of-8” one present in the literature, one of them can be used as starting point to set up the first key-recovery attack on 6-round AES that exploits directly a 5-round secret-key distinguisher.

Keywords: AES · Secret-Key Distinguisher · Key-Recovery Attack · Mixture Differential Cryptanalysis · Truncated Differential · Subspace Trail Cryptanalysis

1   Introduction

Block ciphers are certainly among the most important cryptographic primitives. They are designed by iterating an efficiently implementable round function many times in the hope that the resulting composition behaves like a randomly drawn permutation.

One of the most important tools that a cryptanalyst has at hand when trying to evaluate the security of ciphers or hash functions is – without doubt – differential cryptanalysis. Since its conception by Biham and Shamir [BS90, BS91], it has been successfully applied in many cases.

The methodology of differential cryptanalysis has been extended several times with a number of attack vectors, most importantly truncated differentials [Knu95], impossible differentials [Knu98, BBS99], higher-order differentials [Knu95], boomerang attacks [Wag99] and differential-linear attacks [LH94].

With today’s knowledge, designing a secure block cipher is a problem that is largely considered solved. Especially with the AES we have at hand a very well analyzed and studied cipher that, after more than 20 years of investigation still withstands all cryptanalytic attacks. However, new results on the AES still appear regularly, especially within the last couple of years (e.g. polytopic cryptanalysis [Tie16], “multiple-of-8” distinguisher [GRR17a] and yoyo distinguisher [RBH17]).

The “multiple-of-8” distinguisher [GRR17a] proposed at Eurocrypt 2017 by Grassi, Rechberger and Rønjom is the first 5-round secret-key distinguisher for AES that exploits a property which is independent of the secret key and of the details of the S-Box. This distinguisher is based on a new structural property for up to 5 rounds of AES: by appropriate choices of a number of input pairs it is possible to make sure that the number of times that the difference of the resulting output pairs lie in a particular subspace is always a multiple of 8. This distinguisher allows to distinguish an AES permutation from a random one with a success probability greater than 99% using 2^{32} chosen texts and a computational cost of 2^{35.6} look-ups.

In this paper we introduce mixture differential cryptanalysis on round-reduced AES-like ciphers, a way to translate the (complex) “multiple-of-8” 5-round distinguisher [GRR17a] into a simpler and more convenient one (though, on a smaller number of rounds). As we are going to show, such new proposed technique leads to a new distinguisher and key-recovery attacks on 4- and 5-round AES (respectively) with data and computational complexity similar to other attacks in literature.

1.1   Related Work

To the best of our knowledge, the concept of mixture differential cryptanalysis is new and has not been used in cryptanalysis before.

Differential Attacks. Differential attacks [BS90] exploit the fact that couples of plaintexts with certain differences yield other differences in the corresponding ciphertexts with a non-uniform probability distribution. The resulting pair of differences is called a differential.

Recent Results. Recently, new differential distinguishers have been proposed in the literature, precisely the polytopic cryptanalysis [Tie16] at Eurocrypt 2016 and the yoyo distinguisher on SPN constructions [RBH17] at Asiacrypt 2017, which present an important difference with respect to the previously recalled attacks. Instead of working on each couple of two (plaintext, ciphertext) pairs independently of the others as in the previous scenario, in these cases the attacker works on the relations that hold among the couples of pairs of texts.

1.2   Our Contribution

“Mixture Differential Cryptanalysis” on 4-round AES

As first contribution, in this paper we present “mixture differential cryptanalysis” on 4-round AES. Given plaintexts in the same coset of a subspace \mathcal{C}, the attacker first divides the couples of two (plaintext, ciphertext) pairs into sets of N \geq 2 non-independent couples. These sets are defined such that particular relationships (that involve differential and linear relationships) hold among the plaintexts of the couples that belong to the same set.

Such sets have the property that the two ciphertexts of a certain couple belong to the same coset of a particular subspace \mathcal{M} if and only if the two ciphertexts of all the other couples in that set have the same property. Since this last event can occur for a random permutation, it is possible to distinguish 4-round AES from a random permutation.

Properties exploited by the new proposed 5-round Secret-Key Distinguishers

Using the previous 4-round distinguisher as starting point, the paper presents three different properties that can be exploited to distinguish 5-round AES from a random permutation:

• Probabilistic Mixture Differential: the number of sets for which two ciphertexts of at least one couple belong to the same coset of \mathcal{M} is (a little) lower for 5-round AES than for a random permutation (Sect. 7).
• Threshold Mixture Differential: the number of sets for which the number of qualifying couples exceeds a threshold Z \in \mathbb{N} is higher for 5-round AES than for a random permutation (Sect. 9.1).
• Impossible Mixture Differential: for 5-round AES there exists at least one set for which no couple has ciphertexts in the same coset of \mathcal{M}; for a random permutation every set has at least one qualifying couple (Sect. 9.2).

2   Preliminary – Description of AES

The Advanced Encryption Standard [DR02] is a Substitution-Permutation network that supports key sizes of 128, 192 and 256 bits. The 128-bit plaintext initializes the internal state represented by a 4 \times 4 matrix of bytes seen as values in the finite field \mathbb{F}_{256}, defined using the irreducible polynomial x^8 + x^4 + x^3 + x + 1. Depending on the version of AES, N_r rounds are applied to the state: N_r = 10 for AES-128, N_r = 12 for AES-192 and N_r = 14 for AES-256. An AES round applies four operations to the state matrix:

• SubBytes (S-Box) – 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 (i-th row is shifted by i bytes to the left);
• MixColumns (MC) – multiplication of each column by a constant 4 \times 4 invertible matrix over GF(2^{8});
• AddRoundKey (ARK) – XORing the state with a 128-bit subkey.

One round of AES can be described as R(x) = K \oplus MC \circ SR \circ \text{S-Box}(x). In the first round an additional AddRoundKey operation (using a whitening key) is applied, and in the last round the MixColumns operation is omitted.

3   Subspace Trails

3.1   Subspace Trails of AES

Here we recall the subspace trails of AES presented in [GRR17b], working with vectors and vector spaces over \mathbb{F}_{2^8}^{4 \times 4}.

3.2   Intersections of Subspaces and Useful Probabilities

The probability p_{|I|} that a random element x belongs to the subspace \mathcal{M}_I for a certain I \subseteq \{0,1,2,3\} with |I| = l fixed is well approximated by:

where c_{2,3} = 3 and c_{|I|,i} = 1 for \{|I|, i\} \neq \{2, 3\}.

4   “Multiple-of-8” Secret-Key Distinguisher for 5-round AES

The 5-round AES distinguisher proposed in [GRR17a] exploits the fact that the number of different pairs of ciphertexts that belong to the same coset of \mathcal{M}_J for a fixed J is always a multiple of 8 with probability 1 independently of the secret key, of the details of the S-Box and of the MixColumns matrix.

5   New 4-round Secret-Key Distinguisher for AES

5.1   Mixture Differential Distinguisher for 4-round AES

The proof uses the “super-Sbox” notation introduced in [DR06]: \text{super-Sbox}(\cdot) = \text{S-Box} \circ ARK \circ MC \circ \text{S-Box}(\cdot). Since each column of the ShiftRows output depends on different and independent variables, since the super-Sbox works independently on each column and since the XOR-sum is commutative, the thesis follows.

Data Cost. The distinguisher requires 2^{17} chosen plaintexts (2 cosets of \mathcal{C}_0 \cap \mathcal{D}_{0,3}). The computational cost is approximately 2^{23.09} table look-ups, or approximately 2^{16.75} four-round encryptions.

5.2   Generic Mixture Differential Distinguishers for 4-round AES

5.3   Comparison with Other 4-round Secret-Key Distinguishers

The paper compares the mixture differential distinguisher with existing 4-round distinguishers:

• Impossible Differential: exploits \mathcal{M}_I \cap \mathcal{D}_J = \{0\} for |I| + |J| \leq 4, which does not apply here since the paper works with |I| + |J| \geq 5.
• Truncated Differential: works on single couples independently; the mixture differential works on sets of non-independent couples.
• Polytopic Cryptanalysis: considers interdependencies in sets of couples with one plaintext in common; the mixture differential exploits generating variable relationships.
• “Multiple-of-8”: the mixture differential has lower data/computational costs (2^{17} vs 2^{33} CP).
• Yoyo Distinguisher: similar in spirit but requires adaptive chosen ciphertexts; the mixture differential uses only chosen plaintexts.

6   New Key-Recovery Attack on 5-round AES

The 4-round distinguisher from Theorem 4 can be used to set up a key-recovery attack on 5-round AES. Given plaintexts in the same coset of \mathcal{D}_0, the attacker guesses 4 bytes of the first diagonal of the secret key k_{i,i} for each i \in \{0,1,2,3\}, partially computes one round, and exploits the mixture differential distinguisher: for the right key the property must be satisfied; for wrong keys the behavior is that of a random permutation (wrong-key randomization hypothesis).

6.1   Data and Computational Costs

The attack requires 2^{33.6} chosen plaintexts and has a computational cost of 2^{33.28} five-round encryptions. The probability that at least one wrong key passes the test is approximately 2^{-192}, so a single couple of texts (together with two additional generated couples) is sufficient to discard all wrong key candidates.

6.2   Practical Verification

The attack has been practically verified on the small scale AES [CMR05]. A single coset of a diagonal space is largely sufficient to find one diagonal of the key. The practical computational cost matches the theoretical prediction of 2^{21.5} table look-ups for the small scale case.

7   A New 5-round Secret-Key Distinguisher for AES

7.1   5-round Probabilistic Mixture Differential Secret-Key Distinguisher

Consider 2^{32} chosen plaintexts with one active column (a coset of \mathcal{C}_0) and the corresponding ciphertexts after 5 rounds. For each pair (x_0, x_1), (y_0, y_1) \in \mathbb{F}_{2^8}^2 with x_0 \neq y_0 and x_1 \neq y_1, define sets \mathcal{S}^{0,1}_{(x_0,x_1),(y_0,y_1)} of couples of plaintexts where the generating variables are “mixed.”

The key result: the probability that a set \mathcal{S} contains at least one couple whose ciphertexts belong to the same coset of \mathcal{M}_J for |J| = 3 differs between AES and a random permutation:

The distinguisher requires n \geq 2^{71.243} sets to achieve 95% success probability.

7.2   Data and Computational Complexity

Data Cost. Approximately 2^{70.67} chosen plaintexts (in 2^{38.669} initial cosets of \mathcal{C}_I for |I| = 1). A variant (App. C.2) requires only 2^{52} chosen plaintexts in a single coset of \mathcal{C}_I for |I| = 2.

Computational Cost. Approximately 2^{77.73} table look-ups (equivalently 2^{71.1} five-round encryptions). The variant requires 2^{71.5} table look-ups (equivalently 2^{64.9} five-round encryptions).

7.3   Practical Verification on Small Scale AES

Using 2^{16} different initial cosets of \mathcal{C}_0 on small scale AES, the theoretical and practical numbers of qualifying sets match closely:

confirming that the number of qualifying sets for AES is lower than for the random case, as predicted.

8   Key-Recovery Attack on 6 Rounds of AES-128

Using the 5-round probabilistic mixture differential distinguisher as starting point, this is the first key-recovery attack on 6 rounds of AES that exploits a 5-round secret-key distinguisher. The strategy is similar to linear and differential cryptanalysis: start with cosets of \mathcal{D}_I, guess 4 bytes of the key, and count the number of qualifying sets \mathcal{S}. The count is minimum for the right key.

For a wrongly guessed key, the probability that a set satisfies the property is:

which is approximately equal to the random case and higher than the right-key probability.

Data Cost: 2^{72.77} chosen plaintexts. Computational Cost: 2^{104.93} six-round encryptions (finding one diagonal of the key costs 2^{104.92}; remaining bytes found by brute force).

9   Other Secret-Key Distinguishers for 5-round AES

9.1   Threshold Mixture Differential Secret-Key Distinguisher

This distinguisher uses sets \mathcal{Z}_{(\mathbf{x}, \mathbf{y})} of 2^{65} couples. One counts the number of sets for which the number of couples whose ciphertexts belong to the same coset of \mathcal{M}_I for |I| = 2 exceeds a threshold Z = 3 \cdot 2^{18} = 786432.

• For 5-round AES: the number of qualifying sets is on average higher than 2^{16}.
• For a random permutation: the number of qualifying sets is on average lower than 2^{11.415}.

Costs: 2^{89} chosen plaintexts, 2^{98.1} table look-ups (equivalently 2^{91.5} five-round encryptions).

9.2   Impossible Mixture Differential Secret-Key Distinguisher

This distinguisher uses sets \mathcal{Q}_{(\mathbf{x}, \mathbf{y})} of 2^{39} couples, with all possible combinations of 16 generating variables. One checks if there exists at least one set for which the two ciphertexts of each couple do not belong to the same coset of \mathcal{M}_I for |I| = 3.

• For 5-round AES: at least one qualifying set exists with probability \approx 99.9995\%.
• For a random permutation: for each set there exists at least one couple with ciphertexts in the same coset of \mathcal{M}_I (with probability close to 1).

Costs: 2^{82} chosen plaintexts, 2^{97.8} table look-ups (equivalently 2^{91.1} five-round encryptions).

References

1. [BBS99] Biham, Biryukov, Shamir. Cryptanalysis of Skipjack Reduced to 31 Rounds Using Impossible Differentials. EUROCRYPT 1999.
2. [BEK16] Bay, Ersoy, Karakoç. Universal Forgery and Key Recovery Attacks on ELmD. ASIACRYPT 2016.
3. [BG11] Blondeau, Gérard. Multiple Differential Cryptanalysis: Theory and Practice. FSE 2011.
4. [BK01] Biham, Keller. Cryptanalysis of Reduced Variants of Rijndael. 2001.
5. [BKR11] Bogdanov, Khovratovich, Rechberger. Biclique Cryptanalysis of the Full AES. ASIACRYPT 2011.
6. [BLN17] Blondeau, Leander, Nyberg. Differential-Linear Cryptanalysis Revisited. J. Cryptology 30(3), 2017.
7. [BODK+18] Bar-On, Dunkelman, Keller, Ronen, Shamir. Improved Key-Recovery Attacks on AES. CRYPTO 2018.
8. [BS90] Biham, Shamir. Differential Cryptanalysis of DES-like Cryptosystems. CRYPTO 1990.
9. [BS91] Biham, Shamir. Differential Cryptanalysis of DES-like Cryptosystems. J. Cryptology 4(1), 1991.
10. [CMR05] Cid, Murphy, Robshaw. Small Scale Variants of the AES. FSE 2005.
11. [Der13] Derbez. Meet-in-the-middle attacks on AES. PhD Thesis, ENS Paris, 2013.
12. [DF13] Derbez, Fouque. Exhausting Demirci-Selçuk Meet-in-the-Middle Attacks Against Reduced-Round AES. FSE 2013.
13. [DKR97] Daemen, Knudsen, Rijmen. The Block Cipher Square. FSE 1997.
14. [DR02] Daemen, Rijmen. The Design of Rijndael: AES. Springer, 2002.
15. [DR06] Daemen, Rijmen. Understanding Two-Round Differentials in AES. SCN 2006.
16. [GR18] Grassi, Rechberger. New Rigorous Analysis of Truncated Differentials for 5-round AES. ePrint 2018/182. [page on this site]
17. [GRR17a] Grassi, Rechberger, Rønjom. A New Structural-Differential Property of 5-Round AES. EUROCRYPT 2017.
18. [GRR17b] Grassi, Rechberger, Rønjom. Subspace Trail Cryptanalysis and its Applications to AES. IACR ToSC 2016(2), 2017.
19. [Knu95] Knudsen. Truncated and Higher Order Differentials. FSE 1994.
20. [Knu98] Knudsen. DEAL – a 128-bit block cipher. Technical Report, 1998.
21. [LH94] Langford, Hellman. Differential-Linear Cryptanalysis. CRYPTO 1994.
22. [Mat94] Matsui. Linear Cryptanalysis Method for DES Cipher. EUROCRYPT 1993.
23. [RBH17] Rønjom, Bardeh, Helleseth. Yoyo Tricks with AES. ASIACRYPT 2017.
24. [Tie16] Tiessen. Polytopic Cryptanalysis. EUROCRYPT 2016.
25. [Tun12] Tunstall. Improved “Partial Sums”-based Square Attack on AES. SECRYPT 2012.
26. [Wag99] Wagner. The Boomerang Attack. FSE 1999.

Appendix A   Proof – Probabilities of Sect. 3.2

This appendix proves the probability formulas used throughout the paper, using the inclusion-exclusion principle and the property that \mathcal{M}_I \cap \mathcal{M}_J = \mathcal{M}_{I \cap J}.

A.1   Number of Pairs with n Equal Generating Variables

Given texts in the same coset of \mathcal{C}_I for I \subseteq \{0,1,2,3\}, the number of couples with n equal generating variables in (\mathbb{F}_{2^8})^{|I|} is:

A.2   Discussion about the Given Approximations

All probabilities in Sect. 3.2 are “sufficiently good” approximations assuming the elements are uniformly distributed. The appendix provides detailed discussion of error terms and the assumption’s validity.

Appendix B   4-round Secret-Key Distinguisher for AES – Details

This appendix gives full details of the computational cost of the 4-round distinguisher (Sect. 5). The key optimization is to re-order ciphertexts with respect to a partial order \preceq and work only on consecutive texts. The total cost is 2^{23.09} table look-ups, or approximately 2^{16.75} four-round encryptions, with memory cost of 2^{23} bytes.

Appendix C   Variants of the 5-round AES Secret-Key Distinguisher of Sect. 7

C.1 First Variant: Uses sets \mathcal{T}^3_{(x_0,x_1,x_2),(y_0,y_1,y_2)} with 3 different generating variables and 2^{10} couples per set. Requires 2^{77.263} CP and 2^{85.61} five-round encryptions.

C.2 Second Variant (Most Competitive): Uses 2^{64} chosen plaintexts in a coset of \mathcal{C}_{0,1} with 2^{18} couples per set. Requires only 2^{52} CP and 2^{64.86} five-round encryptions. However, it cannot be used for a key-recovery attack on 6-round AES.

C.3 Key-Recovery Attack on 6-round AES with |I| = 2: Using cosets of \mathcal{D}_I with |I| = 2 requires guessing 2^{64} key bits, leading to a total cost of 2^{176.2} six-round encryptions – much higher than brute force.

Appendix D   Other Variants of the 5-round AES Secret-Key Distinguisher

D.1 Variant with All Different Variables: Uses sets where all 4 generating variables differ, giving 8 couples per set. Requires n \geq 2^{113.84} sets. Data cost: 2^{85.84} CP (or 2^{59} CP using cosets of \mathcal{C}_I for |I| = 2). Computational cost: \approx 2^{107.2} five-round encryptions.

D.2 Key-Recovery Attack on 6-round AES can also be set up from this variant with |p_{\text{AES}}^{\text{WrongKey}} - p_{\text{AES}}| \simeq 2^{-69.2}.

D.3 Practical Verification: Verified on small scale AES with 2^{23} initial cosets. Theoretical and practical values match closely, confirming the distinguisher.

Appendix E   Different Implementation of the 5-round Distinguisher

Defines a partial order \sqsubseteq that involves both plaintexts and ciphertexts, ensuring that pairs belonging to the same coset of \mathcal{M}_J (for ciphertexts) and \mathcal{C}_0 \cap \mathcal{D}_I (for plaintexts) are consecutive in the ordering. This eliminates the need to explicitly check the plaintext condition in some cases, improving the implementation of distinguishers in Sect. 9.1 and App. C.2 (though it does not affect the overall asymptotic cost of the Sect. 7 distinguisher).

Appendix F   Integral Attack on 5-round AES

Recalls and improves the integral attack on 5-round AES. Given 2^{32} chosen plaintexts in a coset of \mathcal{D}_I, the XOR-sum of ciphertexts after 4 rounds is zero:

Improved Attack: By recording the parity of each byte value in a 2^8-bit hash table, the cost per guessed key byte reduces from 2^{32} to 2^8 S-Box operations. Total cost: 2^{32} CP, 2^{32} memory look-ups (\approx 2^{25.4} five-round encryptions), and 2^{12} bits of memory.