Truncated Differential Properties of the Diagonal Set of Inputs for 5-round AES (2018/182)

Abstract

In the last couple of years, a new wave of results appeared, proposing and exploiting new properties of round-reduced AES. In this paper we survey and combine some of these results (namely, the multiple-of-n property and the mixture differential cryptanalysis) in a systematic way in order to answer more general questions regarding the probability distribution of encrypted diagonal sets. This allows to analyze this special set of inputs, and report on new properties regarding the probability distribution of the number of different pairs of corresponding ciphertexts are equal in certain anti-diagonal(s) after 5 rounds.

An immediate corollary of the multiple-of-8 property is that the variance of such a distribution can be shown to be higher than for a random permutation. Surprisingly, also the mean of the distribution is significantly different from random, something which cannot be explained by the multiple-of-8 property. We propose a theoretical explanation of this, by assuming an APN-like assumption on the S-Box which closely resembles the AES-Sbox. By combining the multiple-of-8 property, the mixture differential approach, and the results just mentioned about the mean and the variance, we are finally able to formulate the probability distribution of the diagonal set after 5-round AES as a sum of independent binomial distributions.

Keywords: AES – Truncated-Differential Cryptanalysis – Distinguisher

1. Introduction

AES (Advanced Encryption Standard) [DaemenRijmen02] is probably the most used and studied block cipher. Since the development of cryptanalysis of AES and AES-like constructions in the late 1990s, the set of input which differ only in one diagonal has special importance. Indeed, it appears in several attacks and distinguishers, including various (truncated) differential [Lai94, Knudsen95], integral [DaemenKnudsenRijmen97], and impossible differential attacks [BihamBiryukovShamir99], among others. In particular, given a diagonal set of plaintexts and the corresponding ciphertexts after 4 rounds, it is well known that the XOR-sum of the ciphertexts is equal to zero [DaemenKnudsenRijmen97], or that each pair of ciphertexts cannot be equal in any of the four anti-diagonals, as shown by Biham and Keller in [BihamKeller01].

While a lot is known about the encryption of a diagonal set of plaintexts for up to 4-round AES, an analysis for 5 or more rounds AES is still missing. At Eurocrypt 2017, a new property which is independent of the secret key has been found for 5-round AES [GrassiRechbergerRonjom17]. 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 \mathcal{ID} is always a multiple of 8.

In this paper, given a diagonal set of plaintexts, we consider the probability distribution of the corresponding number of pairs of ciphertexts that are equal in one fixed anti-diagonal after 5-round AES (without the final MixColumns operation).

1.1 Contributions

As the main contribution, we perform for the first time a differential analysis of such distribution after 5-round AES, and find significant deviations from random, supported by practical implementations and verification. For a theoretical explanation we have to resort to an APN-like assumption on the S-Box, which closely resembles the AES-Sbox.

Mean of 5-round AES. By an appropriate choice of 2^{32} plaintexts in a diagonal space \mathcal{D}, the authors prove that the average number of times that the resulting output pairs are equal in one fixed anti-diagonal is slightly bigger for 5-round AES than for a random permutation, independently of the secret key.

Variance of 5-round AES. The variance of the probability distribution is shown to be higher (by a factor of approximately 36) for 5-round AES than for a random permutation, mainly due to the “multiple-of-8” result [GrassiRechbergerRonjom17].

Probability Distribution of 5-round AES. By combining the multiple-of-8 property, the mixture differential cryptanalysis, and the results about the mean and the variance, the probability distribution is shown to be well described by a sum of independent binomial distributions.

1.2 Follow-Up Works: Truncated Differentials for 5-/6-round AES

In [BaoGuoList20], Bao, Guo and List presented “extended expectation cryptanalysis” on round-reduced AES. The technique is based on results by Patarin [Patarin13], who observed that the expected number of collisions differs slightly for a sum of permutations from the ideal. In [BardehRonjom19], Bardeh and Rønjom developed the “exchange equivalence attack” for up to 6-round AES, with complexity of about 2^{88.2} computations and chosen texts.

2. Preliminary

2.1 Advanced Encryption Standard (AES)

AES [DaemenRijmen02] is a Substitution-Permutation network based on the “Wide Trail Design” strategy [DaemenRijmen02a], that supports key sizes of 128, 192 and 256 bits. The 128-bit plaintext initializes the internal state as a 4 \times 4 matrix of bytes as values in the finite field \mathbb{F}_{2^8}. 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 to the left;
MixColumns (MC) multiplication of each column by a constant 4 \times 4 invertible matrix;
AddRoundKey (ARK) XORing the state with a 128-bit subkey k.

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 is applied, and in the last round the MixColumns operation is omitted.

Notation. Let x denote a plaintext, ciphertext, or intermediate state. Then x_{i,j} with i,j \in \{0,\ldots,3\} denotes the byte in row i and column j. We denote by R one round of AES (and R_f if MixColumns is omitted), while R^r denotes r rounds. The i-th diagonal of a 4 \times 4 matrix A is defined as the elements on row r and column c such that r - c \equiv_4 i. The i-th anti-diagonal is defined by r + c \equiv_4 i.

2.2 Properties of an S-Box

Given a bijective S-Box function on \mathbb{F}_{2^n}, let \Delta_I, \Delta_O \in \mathbb{F}_{2^n}. Let N_{\Delta_I, \Delta_O} denote the number of solutions of the equation

\text{S-Box}(x \oplus \Delta_I) \oplus \text{S-Box}(x) = \Delta_O

for each \Delta_I \neq 0 and \Delta_O \neq 0.

Mean Value. Independently of the details of the S-Box, the mean value of N_{\Delta_I,\Delta_O} is equal to \mathbb{E}[N_{\Delta_I,\Delta_O}] = \frac{2^n}{2^n - 1}.

Variance. The variance \text{Var}(N_{\Delta_I,\Delta_O}) depends on the details of the S-Box. For the AES S-Box, for each \Delta_I \neq 0 there are 128 values of \Delta_O \neq 0 for which the equation has no solution, 126 values with 2 solutions, and 1 value with 4 solutions. The variance for the AES S-Box is \text{Var}_{AES}(N_{\Delta_I,\Delta_O}) = \frac{67064}{65025}.

Maximum Differential Probability. The Maximum Differential Probability \text{DP}_{\max} of an S-Box is defined as

\text{DP}_{\max} = 2^{-n} \cdot \max_{\Delta_I \neq 0, \Delta_O} N_{\Delta_I, \Delta_O}.

Since \max_{\Delta_I \neq 0, \Delta_O} N_{\Delta_I, \Delta_O} \geq 2, \text{DP}_{\max} is always at least 2^{-n+1}. Permutations with \text{DP}_{\max} = 2^{-n+1} are called Almost Perfect Nonlinear (APN).

“Homogeneous” S-Box. Given \Delta_I \neq 0, we say the S-Box is (differential) “homogeneous” if the probability distribution of N_{\Delta_I,\Delta_O} with respect to \Delta_O \neq 0 is independent of \Delta_I. The AES S-Box is differential “homogeneous”, while the PRINCE S-Box is not.

3. Probability Distribution for 5-round AES

In this section, we first recall some results already published in the literature about round-reduced AES. Then, given a diagonal space of 2^{32} plaintexts with one active diagonal, we present the probability distribution of the number of different pairs of ciphertexts which are equal in one fixed anti-diagonal after 5-round AES (without the final MixColumns operation).

3.1 Truncated Differentials for 2-round AES

Definition 1

For each i \in \{0, 1, 2, 3\}:

The column spaces \mathcal{C}_i are defined as \mathcal{C}_i = \langle e_{0,i}, e_{1,i}, e_{2,i}, e_{3,i} \rangle.
The diagonal spaces \mathcal{D}_i are defined as \mathcal{D}_i = SR^{-1}(\mathcal{C}_i). Similarly, the inverse-diagonal spaces \mathcal{ID}_i are defined as \mathcal{ID}_i = SR(\mathcal{C}_i).
The i-th mixed spaces \mathcal{M}_i are defined as \mathcal{M}_i = MC(\mathcal{ID}_i).

Definition 2

For each I \subseteq \{0, 1, 2, 3\}, let \mathcal{C}_I, \mathcal{D}_I, \mathcal{ID}_I and \mathcal{M}_I be defined as

\mathcal{C}_I = \bigoplus_{i \in I} \mathcal{C}_i, \quad \mathcal{D}_I = \bigoplus_{i \in I} \mathcal{D}_i, \quad \mathcal{ID}_I = \bigoplus_{i \in I} \mathcal{ID}_i, \quad \mathcal{M}_I = \bigoplus_{i \in I} \mathcal{M}_i.

Definition 3

Let t \in \mathbb{F}_{2^n}^{4 \times 4} be a text in a coset of a space \mathcal{X} \subseteq \mathbb{F}_{2^n}^{4 \times 4} such that \mathcal{X} = \langle x_0, x_1, \dots, x_{d-1} \rangle where \dim(\mathcal{X}) = d, namely t \in \mathcal{X} \oplus \gamma. Given \gamma, (t_0, t_1, \ldots, t_{d-1}) \in \mathbb{F}_{2^n}^d are the generating variables of t if

t \equiv (t_0, t_1, \dots, t_{d-1}) \quad \text{if and only if} \quad t = \gamma \oplus \bigoplus_{j=0}^{d-1} t_j \cdot x_j.

Theorem 1 [GrassiRechbergerRonjom17a]

For each I \subseteq \{0,1,2,3\} and for each \alpha \in \mathbb{F}_{2^8}^{4 \times 4}, there exists \beta \in \mathbb{F}_{2^8}^{4 \times 4} such that R^2(\mathcal{D}_I \oplus \alpha) = \mathcal{M}_I \oplus \beta. Equivalently:

\Pr(R^2(x) \oplus R^2(y) \in \mathcal{M}_I \mid x \oplus y \in \mathcal{D}_I) = 1.

3.2 Multiple-of-8 Property and Mixture Differential Cryptanalysis

Theorem 2 [GrassiRechbergerRonjom17]

Let \{p^i\}_{i \in \{0,1,\ldots,2^{32 \cdot d}-1\}\} be 2^{32 \cdot d} plaintexts with 1 \leq d \leq 3 active diagonals, or equivalently in the same coset of a diagonal subspace \mathcal{D}_I for a certain I \subseteq \{0,1,2,3\} with |I| = d. Consider the corresponding ciphertexts after 5 rounds (without the final MixColumns operation), that is, (p^i, c^i) for i \in \{0,\ldots,2^{32 \cdot |I|}-1\} where c^i = R_f^5(p^i). The number of different pairs of ciphertexts (c^i, c^j) that are equal in 1 \le a \le 3 anti-diagonals (i.e., that belong to the same coset of a subspace \mathcal{ID}_J for a certain J \subseteq \{0,1,2,3\} with |J| = 4 - a) is always a multiple of 8, independently of the secret key, of the details of the S-Box and of the MixColumns matrix.

Theorem 3 [Grassi18]

Let t^1, t^2 be two texts in \mathcal{C}_i \oplus \gamma for a certain i \in \{0, 1, 2, 3\}, namely two plaintexts that differ in the i-th column only. Let t^1 \equiv (x_0^1, x_1^1, x_2^1, x_3^1) and t^2 \equiv (x_0^2, x_1^2, x_2^2, x_3^2) be their generating variables. Let s^1, s^2 \in \mathcal{C}_i \oplus \gamma be defined such that for each i:

if x_i^1 \neq x_i^2: the i-th generating variable s_i^1 of s^1 is either x_i^1 or x_i^2, and the i-th generating variable of s^2 is \{x_i^1, x_i^2\} \setminus s_i^1;
if x_i^1 = x_i^2: the i-th generating variable s_i^1 of s^1 is equal to the i-th generating variable of s^2.

The following holds:

R^2(t^1) \oplus R^2(t^2) = R^2(s^1) \oplus R^2(s^2);
for each J \subseteq \{0, 1, 2, 3\}: R^4(t^1) \oplus R^4(t^2) \in \mathcal{M}_J if and only if R^4(s^1) \oplus R^4(s^2) \in \mathcal{M}_J.

3.3 Main Result: Probability Distribution for 5-round AES

Theorem 4

Given an AES-like cipher that works with texts in \mathbb{F}_{2^8}^{4 \times 4}, assume that (1st) the MixColumns matrix is an MDS matrix and that (2nd) the solutions of the equation \text{S-Box}(x \oplus \Delta_I) \oplus \text{S-Box}(x) = \Delta_O are uniformly distributed for each non-zero input/output difference \Delta_I \neq 0 and \Delta_O \neq 0.

Given 2^{32} plaintexts \{p^i\}_{i \in \{0,1,\ldots,2^{32}-1\}\} with one active diagonal (i.e., in a coset of a diagonal subspace \mathcal{D}_i for i \in \{0,1,2,3\}), consider the number of different pairs of ciphertexts (c^h, c^j) for h \neq j that belong into the same coset of \mathcal{ID}_J for any fixed J \subseteq \{0,1,2,3\} with |J| = 3. The corresponding probability distribution — denoted by \mathfrak{D}_{5\text{-}AES} — with respect to all possible initial cosets and all possible secret keys is given by

\mathfrak{D}_{5\text{-}AES} = 2^3 \times \mathfrak{B}(n_3, p_3) + 2^{10} \times \mathfrak{B}(n_{10}, p_{10}) + 2^{17} \times \mathfrak{B}(n_{17}, p_{17}),

where \mathfrak{B}_i \sim \mathfrak{B}(n_i, p_i) for i \in \{3, 10, 17\} are binomial distributions, and where

n_3 = 2^{28} \cdot (2^8 - 1)^4, \quad p_3 = 2^{-32} + 2^{-53.983};

n_{10} = 2^{23} \cdot (2^8 - 1)^3, \quad p_{10} = 2^{-32} - 2^{-45.989};

n_{17} = 3 \cdot 2^{15} \cdot (2^8 - 1)^2, \quad p_{17} = 2^{-32} + 2^{-37.986}.

Such distribution has mean value \mu = 2\,147\,484\,685.6, and standard deviation \sigma = 277\,204.426.

Corollary 1

Given an AES-like cipher that works with texts in \mathbb{F}_{2^8}^{4 \times 4}, assume that (1st) the MixColumns matrix is an MDS matrix and that (2nd) the solutions of the equation \text{S-Box}(x \oplus \Delta_I) \oplus \text{S-Box}(x) = \Delta_O are uniformly distributed for each non-zero input/output difference \Delta_I \neq 0 and \Delta_O \neq 0.

Given 2^{32} plaintexts with one active diagonal, the probability that n \in \mathbb{N} different pairs of ciphertexts are equal in one fixed anti-diagonal is given by:

\Pr(n) = \begin{cases} 0 & \text{if } n \bmod 8 \neq 0 \\ \displaystyle\sum_{(x_3, x_{10}, x_{17}) \in X_n} \left( \prod_{i \in \{3, 10, 17\}} \binom{n_i}{x_i} \cdot (p_i)^{x_i} \cdot (1 - p_i)^{n_i - x_i} \right) & \text{otherwise} \end{cases}

where

X_n = \left\{ (x_3, x_{10}, x_{17}) \in \mathbb{N} \times \mathbb{N} \times \mathbb{N} \;\middle|\; 0 \le x_i \le n_i \text{ and } 2^3 \cdot x_3 + 2^{10} \cdot x_{10} + 2^{17} \cdot x_{17} = n \right\}

and where n_i and p_i for i \in \{3, 10, 17\} are as in Theorem 4.

4. Initial Considerations

The assumption that “the solutions of the differential equation are uniformly distributed for each \Delta_I \neq 0 and \Delta_O \neq 0” basically corresponds to an S-Box that is “homogeneous” and whose variance \text{Var}(N_{\Delta_I,\Delta_O}) is as low as possible. This is close to being true if the S-Box is APN, or if the S-Box is “close” to being APN. The AES S-Box is not APN but differentially 4-uniform, and approximately matches the assumptions.

Proposition 1

Consider 2^{32} plaintexts \{p^i\}_{i \in \{0,1,\dots,2^{32}-1\}\} with one active diagonal, and the corresponding (cipher)texts generated by a random permutation \Pi, that is c^i = \Pi(p^i). The probability distribution of the number of different pairs of ciphertexts (c^h, c^j) that belong to the same coset of \mathcal{ID}_J for any fixed J \subseteq \{0,1,2,3\} with |J| = 3 is given by a binomial distribution \mathfrak{B}(n,p), where n = \binom{2^{32}}{2} = 2^{31} \cdot (2^{32} - 1) and p = \frac{2^{96} - 1}{2^{128} - 1} \approx 2^{-32}. The average number of collisions is equal to 2^{31} - 0.5 = 2\,147\,483\,647.5, while its variance is approximately 2^{31}.

It follows that, independently of the secret key, the average number of pairs of ciphertexts equal in one fixed anti-diagonal is slightly bigger for 5-round AES than for a random permutation (approximately 1038.1 more collisions), and the variance is much bigger (approximately a factor of 36).

5. Proof of Theorem 4: Sum of Binomial Distributions

Consider a set of 2^{32} plaintexts with one active diagonal and the corresponding ciphertexts after 5-round AES. As shown by the multiple-of-8 property [GrassiRechbergerRonjom17] and by the mixture differential cryptanalysis [Grassi18], the pairs of ciphertexts are not independent. These pairs can be divided into n_3 + n_{10} + n_{17} + n_{24} sets such that:

for each i \in \{3, 10, 17, 24\}, exactly n_i sets have cardinality 2^i;
each set contains pairs of texts for which i out of the four generating variables are equal after 1-round encryption;
within each set, either all pairs of ciphertexts satisfy the anti-diagonal equality or none do;
pairs of texts in different sets are independent.

The values of n_3, n_{10}, n_{17} are given by

\forall v \in \{0, 1, 2\}: \quad n_{7v + 3} = \binom{4}{v} \cdot \frac{2^{31} \cdot (2^8 - 1)^{4-v}}{2^{7v + 3}}.

Due to the impossible differential trail on 4-round AES, if three out of four generating variables are equal after 1-round encryption, then the corresponding ciphertexts cannot be equal in any anti-diagonal. Therefore p_{24} = 0.

Mean Value and Variance. The mean value \mu is

\mu = \mathbb{E}[\mathfrak{D}_{5\text{-}AES}] = 2^3 \cdot n_3 \cdot p_3 + 2^{10} \cdot n_{10} \cdot p_{10} + 2^{17} \cdot n_{17} \cdot p_{17},

and the variance \sigma^2 is

\sigma^2 = 2^6 \cdot n_3 \cdot p_3 \cdot (1 - p_3) + 2^{20} \cdot n_{10} \cdot p_{10} \cdot (1 - p_{10}) + 2^{34} \cdot n_{17} \cdot p_{17} \cdot (1 - p_{17}).

6. Proof of Theorem 4: About the Probabilities p_3, p_{10}, p_{17}

6.1 Reduction to the Middle Round

Due to the 2-round truncated differential with probability 1, the 5-round chain decomposes as

\mathcal{D}_i \oplus \delta \xrightarrow{R^2} \mathcal{M}_i \oplus \omega \xrightarrow{R} \mathcal{D}_J \oplus \delta' \xrightarrow{R_f^2} \mathcal{ID}_J \oplus \omega'.

It is therefore sufficient to focus on the middle round \mathcal{M}_i \oplus \omega \xrightarrow{R} \mathcal{D}_J \oplus \delta' in order to compute the desired result. The proof proceeds first for a simpler case of 2^{16} texts with two equal generating variables, then extends to the generic case of 2^{32} texts.

6.2 A “Simpler” Case: 2^{16} Texts with Two Equal Generating Variables

Consider 2^{16} texts for which two generating variables are equal, e.g., z^1 = z^2 and w^1 = w^2. Two such texts are equal in the first diagonal after one round if and only if four equations of the form

A \cdot \left( \text{S-Box}(B \cdot x^1 \oplus a) \oplus \text{S-Box}(B \cdot x^2 \oplus a) \right) \oplus C \cdot \left( \text{S-Box}(D \cdot y^1 \oplus c) \oplus \text{S-Box}(D \cdot y^2 \oplus c) \right) = 0

are satisfied, where A, B, C, D \in \mathbb{F}_{2^8} depend on the MixColumns matrix, while a, c \in \mathbb{F}_{2^8} depend on the secret key and on the initial constant \omega.

Each such equation has exactly 255 \cdot 2^{15} different non-null solutions. Under the APN-like assumption and the MDS property, the probability that two equations share a common solution is 255^{-2} \cdot 2^{-15}. The average number of common solutions of 4 such equations is

(255 \cdot 2^{15})^4 \cdot (255^{-2} \cdot 2^{-15})^3 = \frac{2^{15}}{255^2} \simeq 0.503929 \simeq 2^{-1} + 2^{-7.992}.

This leads to the probability

p_{17} = 2^{-32} + 2^{-37.986}.

6.3 Generic Case: 2^{32} Texts

The generic case extends the analysis to 2^{32} texts, where four equations of the form

A \cdot (\text{S-Box}(B \cdot x^1 \oplus b) \oplus \text{S-Box}(B \cdot x^2 \oplus b)) \oplus C \cdot (\text{S-Box}(D \cdot y^1 \oplus d) \oplus \text{S-Box}(D \cdot y^2 \oplus d)) \oplus E \cdot (\text{S-Box}(F \cdot z^1 \oplus f) \oplus \text{S-Box}(F \cdot z^2 \oplus f)) \oplus G \cdot (\text{S-Box}(H \cdot w^1 \oplus h) \oplus \text{S-Box}(H \cdot w^2 \oplus h)) = 0

must be satisfied. The proof splits into three cases depending on how many of \Delta_O, \Delta_O', \Delta_O'', \Delta_O''' are zero, yielding:

First case (two equal generating variables): average common solutions \binom{4}{2} \cdot 256^2 \cdot \frac{2^{15}}{255^2} = \frac{2^{32}}{21675} \simeq 198\,153.047, giving p_{17} = 2^{-32} + 2^{-37.986}.
Second case (one equal generating variable): average common solutions \simeq 33\,160\,710.047, giving p_{10} = 2^{-32} - 2^{-45.989}.
Third case (no equal generating variables): average common solutions \simeq 2\,114\,125\,822.5, giving p_3 = 2^{-32} + 2^{-53.983}.

The total number of collisions is

2\,114\,125\,822.5 + 33\,160\,710.047 + 198\,153.047 \simeq 2\,147\,484\,685.594 \simeq 2^{31} + 2^{10.02}.

7. Practical Results for 5-round AES

The mean and variance have been practically verified using a C/C++ implementation. The mean value was verified on a small-scale AES as proposed in [CidMurphyRobshaw05], and the variance both on full-size and on small-scale AES.

Proposition 2

Consider an AES-like cipher that works with texts in \mathbb{F}_{2^n}^{4 \times 4}, such that (1st) the MixColumns matrix is an MDS matrix and (2nd) the solutions of the differential equation are uniformly distributed for each \Delta_I \neq 0 and \Delta_O \neq 0. Given 2^{4n} plaintexts with one active diagonal, independently of the initial coset and the secret key, the average number of different pairs of ciphertexts that belong to the same coset of \mathcal{ID}_J for any fixed J with |J| = 3 is

\frac{2^{4n-1} \cdot (2^{2n} - 3 \cdot 2^n + 3)^4}{(2^n - 1)^8} + \frac{(2^{n-1} - 1)^4 \cdot 2^{4n+5}}{(2^n - 1)^5} + 3 \cdot \frac{2^{4n}}{(2^n - 1)^2},

and the variance is

\frac{2^{4n+2} \cdot (2^{2n} - 3 \cdot 2^n + 3)^4}{(2^n - 1)^8} + \frac{(2^{n-1} - 1)^4 \cdot 2^{5n+7}}{(2^n - 1)^5} + \frac{3 \cdot 2^{6n+1}}{(2^n - 1)^2}.

Full-size AES variance: \sigma_T^2 = 76\,842\,293\,834.905 \simeq 2^{36.161} (theoretical) versus \sigma_P^2 = 73\,288\,132\,411.36 \simeq 2^{36.093} (practical).

Small-scale AES mean: \mu_{AES}^T = 32\,847.124 versus \mu_{AES}^P = 32\,848.57; \mu_{rand}^T = 32\,767.5 versus \mu_{rand}^P = 32\,768.2.

Small-scale AES standard deviation: \sigma_{AES}^T = 1036.58 versus \sigma_{AES}^P = 1027.93; \sigma_{rand}^T = 181.02 versus \sigma_{rand}^P = 182.42.

The distribution for small-scale 5-round AES has a positive skew (approximately 0.47), while the random distribution has skew approximately zero.

8. Truncated Differential Distinguishers for 5-round AES

The truncated differential distinguishers presented in this section are based on the difference in the probability distribution of the number of collisions between 5-round AES and a random permutation.

8.1 Variance-based Distinguisher. Since the variance of the AES case is approximately 36 times that of a random permutation, this can be exploited for a secret-key distinguisher. With 4 initial cosets of \mathcal{D}_i (data cost 2^{34} chosen plaintexts), the computational cost is approximately 2^{37.6} table look-ups (\approx 2^{31} five-round encryptions).

Lemma 1

Consider an AES-like cipher that works with texts in \mathbb{F}_{2^8}^{4 \times 4} and for which the assumptions of Theorem 4 hold. Consider 2^{32} plaintexts with one active diagonal. The probability distribution of the number of different pairs of ciphertexts that are equal in one anti-diagonal after 5 rounds is approximated by a normal distribution \mathfrak{N}(\mu, \sigma^2), where the mean value is \mu = 2\,147\,484\,685.6 = 2^{32} + 1\,037.6 and the standard deviation is \sigma = 277\,204.426.

8.3 Mean-based Distinguisher. Using the normal approximation, the difference of the two distributions (AES and random) is again a normal distribution. In order to have a probability of success greater than 95%, the number of pairs must satisfy n \geq 2^{78.374}. Given 2^{32} chosen plaintexts per coset (approximately 2^{63} pairs of texts), the distinguisher requires 2^{16.96} initial cosets for a data cost of 2^{48.96} chosen plaintexts and a computational cost of 2^{52.6} table look-ups (\approx 2^{46} five-round encryptions).

Acknowledgements

This work was accomplished when L. Grassi was at IAIK, Graz University of Technology, Austria. Authors thank anonymous reviewers for their valuable comments and suggestions. Authors thank Matthias Niel for implementing on C/C++ the truncated differential distinguishers on 6- and 8-bit AES presented in this paper. Authors also thank Anne Canteaut for pointing out the constant of the ratio between the variances for 5-round AES and for a random permutation. L. Grassi is currently supported by the European Research Council under the ERC advanced grant agreement under grant ERC-2017-ADG Nr. 788980 ESCADA.

References

[Albrecht+14] M. R. Albrecht, B. Driessen, E. B. Kavun, G. Leander, C. Paar, and T. Yalcin, “Block Ciphers – Focus on the Linear Layer (feat. PRIDE),” in CRYPTO 2014, ser. LNCS, vol. 8616, 2014, pp. 57–76.
[Banik+15] S. Banik, A. Bogdanov, T. Isobe, K. Shibutani, H. Hiwatari, T. Akishita, and F. Regazzoni, “Midori: A Block Cipher for Low Energy,” in ASIACRYPT 2015, ser. LNCS, vol. 9453, 2015, pp. 411–436.
[BaoGuoList20] Z. Bao, J. Guo, and E. List, “Extended Truncated-differential Distinguishers on Round-reduced AES,” IACR Trans. Symmetric Cryptol., vol. 2020, no. 3, pp. 197–261, 2020. [page on this site]
[Bar-On+18] A. Bar-On, O. Dunkelman, N. Keller, E. Ronen, and A. Shamir, “Improved Key Recovery Attacks on Reduced-Round AES with Practical Data and Memory Complexities,” in CRYPTO 2018, ser. LNCS, vol. 10992, 2018, pp. 185–212.
[BardehRonjom19] N. G. Bardeh and S. Rønjom, “The Exchange Attack: How to Distinguish 6 Rounds of AES with 2^{88.2} chosen plaintexts,” in ASIACRYPT 2019, ser. LNCS, vol. 11923, 2019, pp. 347–370.
[BihamBiryukovShamir99] E. Biham, A. Biryukov, and A. Shamir, “Cryptanalysis of Skipjack Reduced to 31 Rounds Using Impossible Differentials,” in EUROCRYPT 1999, ser. LNCS, vol. 1592, 1999, pp. 12–23.
[BihamKeller01] E. Biham and N. Keller, “Cryptanalysis of Reduced Variants of Rijndael,” 2001, unpublished.
[BihamShamir91] E. Biham and A. Shamir, “Differential cryptanalysis of DES-like cryptosystems,” Journal of Cryptology, vol. 4, no. 1, pp. 3–72, Jan 1991.
[BlondeauLeanderNyberg17] C. Blondeau, G. Leander, and K. Nyberg, “Differential-Linear Cryptanalysis Revisited,” Journal of Cryptology, vol. 30, no. 3, pp. 859–888, 2017.
[Bogdanov+07] A. Bogdanov, L. R. Knudsen, G. Leander, C. Paar, A. Poschmann, M. J. B. Robshaw, Y. Seurin, and C. Vikkelsoe, “PRESENT: An Ultra-Lightweight Block Cipher,” in CHES 2007, ser. LNCS, vol. 4727, 2007, pp. 450–466.
[Borghoff+12] J. Borghoff, A. Canteaut, T. Güneysu, E. B. Kavun, M. Knezevic, L. R. Knudsen, G. Leander, V. Nikov, C. Paar, C. Rechberger, P. Rombouts, S. S. Thomsen, and T. Yalcin, “PRINCE – A Low-Latency Block Cipher for Pervasive Computing Applications,” in ASIACRYPT 2012, ser. LNCS, vol. 7658, 2012, pp. 208–225.
[BouraCanteautCoggia19] C. Boura, A. Canteaut, and D. Coggia, “A General Proof Framework for Recent AES Distinguishers,” IACR Trans. Symmetric Cryptol., vol. 2019, no. 1, pp. 170–191, 2019.
[CidMurphyRobshaw05] C. Cid, S. Murphy, and M. J. B. Robshaw, “Small Scale Variants of the AES,” in FSE 2005, ser. LNCS, vol. 9054, 2005, pp. 145–162.
[DaemenKnudsenRijmen97] J. Daemen, L. R. Knudsen, and V. Rijmen, “The Block Cipher Square,” in FSE 1997, ser. LNCS, vol. 1267, 1997, pp. 149–165.
[Daemen+00] J. Daemen, M. Peeters, G. V. Assche, and V. Rijmen, “Nessie proposal: the block cipher Noekeon,” Nessie submission, 2000.
[DaemenRijmen02] J. Daemen and V. Rijmen, The Design of Rijndael: AES The Advanced Encryption Standard, ser. Information Security and Cryptography. Springer, 2002.
[DaemenRijmen02a] J. Daemen and V. Rijmen, “Security of a Wide Trail Design,” in INDOCRYPT 2002, ser. LNCS, vol. 2551, 2002, pp. 1–11.
[GongNikovaLaw12] Z. Gong, S. Nikova, and Y. W. Law, “KLEIN: A New Family of Lightweight Block Ciphers,” in RFID 2011, ser. LNCS, vol. 7055, 2012, pp. 1–18.
[Grassi18] L. Grassi, “Mixture Differential Cryptanalysis: a New Approach to Distinguishers and Attacks on round-reduced AES,” IACR Trans. Symmetric Cryptol., vol. 2018, no. 2, pp. 133–160, 2018. [page on this site]
[Grassi19] L. Grassi, “Probabilistic Mixture Differential Cryptanalysis on Round-Reduced AES,” in SAC 2019, ser. LNCS, vol. 11959, 2019, pp. 53–84.
[GrassiRechbergerRonjom17] L. Grassi, C. Rechberger, and S. Rønjom, “A New Structural-Differential Property of 5-Round AES,” in EUROCRYPT 2017, ser. LNCS, vol. 10211, 2017, pp. 289–317.
[GrassiRechbergerRonjom17a] L. Grassi, C. Rechberger, and S. Rønjom, “Subspace Trail Cryptanalysis and its Applications to AES,” IACR Trans. Symmetric Cryptol., vol. 2016, no. 2, pp. 192–225, 2017. [page on this site]
[Knudsen95] L. R. Knudsen, “Truncated and higher order differentials,” in FSE 1994, ser. LNCS, vol. 1008, 1995, pp. 196–211.
[Lai94] X. Lai, Higher Order Derivatives and Differential Cryptanalysis. Springer US, 1994, pp. 227–233.
[LeanderPoschmann07] G. Leander and A. Poschmann, “On the Classification of 4 Bit S-Boxes,” in Arithmetic of Finite Fields – WAIFI 2007, ser. LNCS, vol. 4547, 2007, pp. 159–176.
[Nyberg91] K. Nyberg, “Perfect nonlinear S-boxes,” in EUROCRYPT 1991, ser. LNCS, vol. 547, 1991, pp. 378–386.
[Patarin13] J. Patarin, “Generic Attacks for the Xor of k Random Permutations,” in ACNS 2013, ser. LNCS, vol. 7954, 2013, pp. 154–169.
[RonjomBardehHelleseth17] S. Rønjom, N. G. Bardeh, and T. Helleseth, “Yoyo Tricks with AES,” in ASIACRYPT 2017, ser. LNCS, vol. 10624, 2017, pp. 217–243.
[Zhang+15] W. Zhang, Z. Bao, D. Lin, V. Rijmen, B. Yang, and I. Verbauwhede, “RECTANGLE: a bit-slice lightweight block cipher suitable for multiple platforms,” Science China Information Sciences, vol. 58, no. 12, pp. 1–15, Dec 2015.