Extended Truncated-differential Distinguishers on Round-reduced AES

Abstract

Distinguishers on round-reduced AES have attracted considerable attention in the recent years. While the number of rounds covered in key-recovery attacks did not increase, subspace, yoyo, mixture-differential, and multiple-of-n cryptanalysis advanced the understanding of the properties of the cipher.

For substitution-permutation networks, integral attacks are a suitable target for extension since they usually end after a linear layer sums several subcomponents. Based on results by Patarin, Chen et al. already observed that the expected number of collisions for a sum of permutations differs slightly from that for a random primitive. Though, their target remained lightweight primitives.

The present work illustrates how the well-known integral distinguisher on three-round AES resembles a sum of PRPs and can be extended to truncated-differential distinguishers over 4 and 5 rounds. In contrast to previous distinguishers by Grassi et al., our approach allows to prepend a round that starts from a diagonal subspace. We demonstrate how the prepended round can be used for key recovery with a new differential key-recovery attack on six-round AES. Moreover, we show how the prepended round can also be integrated to form a six-round distinguisher. For all distinguishers and the key-recovery attack, our results are supported by implementations with Cid et al.'s established Small-AES version. While the distinguishers do not threaten the security of the AES, they try to shed more light on its properties.

Keywords: Cryptanalysis, AES, Permutation, Collision, Differential, Expectation, Distinguisher

1 Introduction

During the previous two decades, the Advanced Encryption Standard (AES) [Nat01] has withstood vast amounts of cryptanalysis. Besides the biclique-based accelerated exhaustive search [BKR11], the best-known attacks on AES-128 in the secret-key model cover seven rounds, as had been the state of the art close after its announcement [FKL+00]. However, the community's efforts led to attacks with considerably reduced resources. Among the key-recovery attacks that cover the most rounds [BLNS18, DFJ13, FKL+00, MDRM10], the meet-in-the-middle attacks by Derbez et al. possess the lowest time and data complexities since 2013 [DFJ13]. Their attacks were based on Demirci and Selcuk's [DS08] variant of the earlier collision attack by Gilbert and Minier [GM00].

Although the number of rounds covered in key-recovery attacks has stagnated, the recent years were filled with research on distinguishers on round-reduced AES that significantly raised the understanding of the cipher's components. This direction appears promising -- metaphorically, it is comparable to heuristics that sometimes also have to leave a local optimum to improve in the long run.

1.1 Distinguishers on Round-reduced AES

Negative results paved a rocky start for the search for new distinguishers. Sun et al. [SLG+16b] proved the absence of impossible differentials over more than four rounds for the AES structure, which was tantamount with the absence of zero-correlation distinguishers over more than four rounds [SLR+15]. Since [SLG+16b] ignored the details of the AES S-box and its key schedule, there remained a spark of hope for longer distinguishers of those kinds. The works by Wang and Jin [WJ18, WJ19] extinguished this spark. Under the assumption of independent random round keys, they showed the absence of any (truncated) impossible differentials over more than four-round of the AES taking also the details of the S-box into account.

Key-dependent Distinguishers. Despite the negative results, a series of works has been focusing on novel properties for distinguishers on fewer rounds than the best known attacks. First, several key-dependent distinguishers were crafted, e.g., the chosen-ciphertext zero-correlation hull on five rounds by Sun et al. [SLG+16a] exploited a known difference in two key bytes to cover five rounds. While their distinguisher required the full codebook when converted to the single-key model, it re-ignited the community's efforts on analyzing round-reduced AES. Subsequent works [CCM+18, GRR16, Gra18a, HCGW18] improved on their result and proposed further key-dependent results.

1.2 Key-independent Distinguishers on Round-reduced AES

Besides key-dependent results, several powerful key-independent distinguishers have been proposed recently. In a series of works [GRR16, GRR17, GR18, Gra18b], Grassi et al. outlined novel observations and distinguishers on five-round AES. At their core, [GRR17] observed a strong property dubbed multiple-of-n: using all pairs from a diagonal space, the number of different ciphertext pairs that belonged to the same coset of a mixed space was always a multiple of n after five rounds. Boura et al. [BCC19] revisited the multiple-of-n property and derived similar distinguishers for further AES-like primitives.

Mixture-differential Distinguishers. In [Gra17, Gra18b], Grassi proposed mixture-differential distinguishers. Mixtures are couples of pairs that start from a pair of plaintexts (P, P') that differ in multiple components, say values (x, y) in P and (x', y') in P'. A second plaintext pair (P'', P''') with byte values (x, y') and (x', y) is created from mixing the differing components such that the input difference remains invariant, and their corresponding ciphertext pairs lie in a coset of the same subspace.

To the best of our knowledge, the best previously published distinguishers on round-reduced AES-128 in terms of minimal complexity are the exchange/yoyo-based proposals by Ronjom and Bardeh [BR19b, BR19c]. They extended their earlier yoyo attacks from [RBH17] and reduced the complexity to about 2^{88} encryptions and chosen plaintexts. Bardeh [Bar19] recently proposed a variant with adaptively chosen ciphertexts with 2^{83} data and time complexity.

1.3 From Integral to Truncated-differential Distinguishers

Integral Distinguishers map multi-sets of inputs that iterate over all values to multi-sets of outputs that are balanced. Traditionally, the properties of bits or bytes are either constant (C), iterate over all values (A), are balanced (B), or unknown (U). A traditional integral distinguisher usually ends directly before all parts of the state become unknown. For the AES, the three-round integral distinguisher [DKR97] that maps sets of a single active byte to a set of states where each byte is balanced after three rounds is understood well, and so is the extension to a distinguisher on four rounds [DKR97, FKL+00] that prepends a round and starts from an active diagonal.

Extending Integrals To Truncated-differential Distinguishers. The core observation at the beginning of this work was that an integral distinguisher usually ends with a sum operation. In many Substitution-Permutation Networks (SPNs), the linear layer often consists of a sum of multiple words. At the end of an integral distinguisher, such a sum is equivalent to the sum of words that iterate over all values in the subspace -- hence, a sum of permutations. The sum still has a Balanced (i.e., zero-sum) property, which is usually destroyed by the subsequent non-linear layer. As illustrated in [Pat08, Pat13], the number of collisions induced by a sum of permutations differs slightly from that of an ideal function. The sum in the linear layer preserves this number of collisions through the subsequent S-box operation. Therefore, an integral distinguisher can be extended through the subsequent non-linear operation.

We point out that Chen et al. [CMSZ15] had already considered this approach of Patarin's analysis for extending integrals of SPNs. They considered Type-II and Nyberg-type Feistel networks and conducted experiments on lightweight ciphers for which they could confirm that this strategy can lead to extended attacks. This work, however, focuses on the AES.

Contribution. This work tries to extend the known integral to truncated-differential distinguishers. As a result, it describes a five-round distinguisher from a single byte to a mixed space. Since inputs start from single-byte differences, plaintext structures can form fewer pairs than in e.g., the structures from diagonals as in [GR18]. As a consequence, the data and computational complexity of the five-round distinguisher here are higher than those of the probabilistic distinguishers in [GR18], but our proposal allows a straightforward extension to a six-round key-recovery attack by prepending a round. We present the results of a practical implementation of the five-round distinguisher and the six-round key-recovery attacks with a small-scale variant of the AES. Finally, we propose a possible extension to a six-round truncated-differential distinguisher and report our results of its implementation for the small variant.

Outline. Section 2 revisits the necessary preliminaries. Section 3 provides a statistical model. Section 4 develops a four-round truncated distinguisher. Section 5 proceeds similarly for a five-round distinguisher. Section 6 describes a key-recovery attack on six rounds. Section 7 derives a six-round distinguisher. Section 8 discusses and concludes this work.

2 Preliminaries

General Notations. We denote by \mathbb{F}_2 the finite field of characteristic two. We employ typewriter font for hexadecimal values. Let X, Y \in \mathbb{F}_2^n for some positive integer n. Then, we denote by X \| Y the concatenation of X and Y, by X \oplus Y their bitwise XOR. We denote by \mathbb{E}[X] the expectation of a random variable X, by \sigma_X its standard deviation, and by \sigma_X^2 = \text{Var}[X] its variance.

Functions and Permutations. For sets \mathcal{X} and \mathcal{Y}, we define \text{Func}(\mathcal{X}, \mathcal{Y}) and \text{Perm}(\mathcal{X}) for the set of all permutations over \mathcal{X}. We call \pi an ideal permutation if \pi \leftarrow \text{Perm}_n, and similarly \rho an ideal function if \rho \leftarrow \text{Func}_n. We define \text{trunc}_m(X) to truncate and return only the most-significant m bits.

2.1 Distinguishers for Sums of Permutations

We recall the results by [Pat08, Pat13]. Let \pi_1, \ldots, \pi_k \leftarrow \text{Perm}_n be independent ideal random permutations, and let \rho \leftarrow \text{Func}_n. We define a k-sum of permutations as \Sigma_k[\pi_1, \ldots, \pi_k](x) = \bigoplus_{i=1}^{k} \pi_i(x).

Let N be a random variable for the number of output collisions. For a random function:

For the sum of k permutations:

The single-collision probability is:

2.2 The AES-128 and Its Subspaces

Brief Definition of The AES-128. The AES-128 is a substitution-permutation network that transforms 128-bit inputs through ten rounds, consisting of SubBytes (SB), ShiftRows (SR), MixColumns (MC), and a round-key addition with a round key K^i. We write S^i for the state after Round i, and S^i[j] for the j-th byte. We denote by R[K^i] = \text{AK}[K^i] \circ \text{MC} \circ \text{SR} \circ \text{SB} one application of the round function, and by \widehat{R}^r the sequence of r rounds without the key addition and MixColumns in the final round. We use M for the MixColumns matrix.

Subspaces of The AES. We adopt the notation from Grassi et al. [GRR16]. For i \in \{0, 1, 2, 3\}, the four families of subspaces are:

• The column spaces \mathcal{C}_{\{i\}} = \langle e_{0,i}, e_{1,i}, e_{2,i}, e_{3,i} \rangle
• The diagonal spaces \mathcal{D}_{\{i\}} = \text{SR}^{-1}(\mathcal{C}_{\{i\}})
• The inverse-diagonal spaces \mathcal{ID}_{\{i\}} = \text{SR}(\mathcal{C}_{\{i\}})
• The mixed spaces \mathcal{M}_{\{i\}} = \text{MC}(\mathcal{ID}_{\{i\}})

Small-AES. Cid et al. [CMR05] proposed small-scale variants of the AES to help cryptanalysts study attacks whose complexity prohibited tests on the full-fledged cipher. We employ the four-bit variant, which operates on a 4 \times 4-nibble state of 64 bits.

2.3 S-box Properties

Mean. For \Delta_I, \Delta_O \in \mathbb{F}_2^n, we denote the number of solutions for a differential \Delta_I \to \Delta_O through the S-box S as:

The expected number of solutions for non-zero (\Delta_I, \Delta_O) is \mathbb{E}[\delta_S(\Delta_I, \Delta_O)] = \frac{256}{255} for the AES S-box.

Variance. For the AES S-box, the variance is:

2.4 Known Integral Distinguishers on Round-reduced AES

Three-round Integral Distinguisher. Let a \delta-set be a set of 2^8 texts that iterate over all values in one byte (A) and are constant in all other bytes (C). Then, after two rounds, each byte iterates over all 2^8 values. The ALL property is preserved through SubBytes and ShiftRows of the third round, but is no longer guaranteed after MixColumns. Since MixColumns is linear, it preserves balanced input sets, yielding the B (Balanced) property after three rounds.

Four-round Integral Distinguisher. The three-round distinguisher can be extended to four rounds using a diagonal space \mathcal{D}_{\mathcal{I}} with |\mathcal{I}| = 1. The texts iterate over all 2^{32} values in each column of S^3 after almost three rounds. The ALL property is no longer guaranteed by MixColumns at the end of Round 3, but balancedness is preserved. SubBytes in the subsequent round destroys it.

3 Statistical Framework

We follow the framework by [GR19]. The binomial distribution \mathcal{B}(N, p) yields the number of successes in a sequence of N independent Boolean experiments, each successful with probability p. The mean and variance are \mu = N \cdot p and \sigma^2 = N \cdot p \cdot (1-p).

We consider two normal distributions whose difference is approximately normally distributed with \mathcal{N}(\mu, \sigma^2), where:

To obtain a success probability of at least P_S, the number of trials N must satisfy:

4 Four-round Truncated-differential Distinguisher

We extend the deterministic three-round integral distinguisher to a probabilistic four-round truncated-differential distinguisher. We consider a \delta-set of 2^8 plaintexts that iterate over all values in a single plaintext byte and leave all other plaintext bytes constant. For a \delta-set, all output bytes after \widehat{R}^3 iterate over all values. So, for each column, the MixColumns operation in Round 3 can be viewed as the sum of the results of four permutations where the inputs iterate over all values.

4.1 Adapting Patarin's Setting to Three-round AES

We approximate the expected number of byte collisions S^{3,i}_{r,c} = S^{3,j}_{r,c} using \mathbb{E}[N_4]. The probability for a byte collision is approximately:

For a random permutation:

This difference can be exploited to build a truncated-differential distinguisher on four-round AES.

4.2 Theoretical Analysis

Complexity. For Setting (1) with success probability P_S = 0.95, we obtain N > 2^{58.402} pairs. A \delta-set contains \binom{2^8}{2} \simeq 2^{15} pairs, requiring approximately 2^{43.402} \delta-sets with 2^{51.402} chosen plaintexts.

Reduced Variant. For Small-AES, the probability that a fixed nibble has zero difference after three rounds is approximately:

4.3 Index Dependencies of The Four-round Distinguisher

The mean of the four-round truncated differential depends strongly on the index of (1) the input cell that is iterated over in the \delta-sets and (2) the index of the inactive output cell after three rounds. We obtain an equation system through three full rounds. For input cell 0 and output cell 0, the collision equation becomes:

Application to The AES. We can split the equation into four terms that can be computed individually. The total approach needs O(2^{41}) lookups. The results show all deviations are in the range [0.987 \ldots 1.256] of the expected difference |p_{\text{AES}} - p_{\text{rand}}|, confirming the distinguisher works.

4.4 Verification

Experimental Verification Using Small-AES. We verified the distinguisher experimentally with 100 random keys and 2^s \delta-sets, for s \in \{20, \ldots, 23\}. As an approximation of a random permutation, we employed full-round Speck-64-96 with 100 random keys.

Transition-based Verification. Using Ronjom's [Ron19] transition-distribution matrices:

which supports our analysis.

Effects of the Variance. Our experiments with Small-AES yielded that the numbers of collisions were always multiples of 32. The variance for the original S-box of Small-AES was about 15.3 times higher in Setting (2) than in Setting (1).

5 Five-round Truncated-differential Distinguisher

We can extend the four-round distinguisher from Section 4 to five rounds.

5.1 Setting

Consider some diagonal space \mathcal{D}_{\{c\}}. The expected probability that all four bytes in that diagonal space collide for two texts in a \delta-set is approximately:

The probability to have at least one all-zero anti-diagonal in the difference is:

For a random permutation:

5.2 Theoretical Analysis

Steps. The distinguisher proceeds as follows:

1. Initialize a collision counter.
2. For i = 1 \ldots 2^s, collect a structure of 2^{32} texts iterating over all values in any four bytes. Query plaintexts and get ciphertexts. Invert the final ShiftRows to get S^{5,\text{SB}}.
3. Form 4 \cdot 2^{24} \delta-sets from a structure. For each, look for column collisions and count unique ones.
4. If the counter exceeds threshold \theta, output real; otherwise, output random.

Complexity. For Setting (1) with P_S = 0.95, we need N \ge 2^{76.406} pairs. 2^{36} structures with 2^{68} chosen plaintexts suffice. The computational complexity is approximately 2^{73.3} memory accesses and 2^{68.3} encryptions. The threshold is:

Reduced Variant. For Small-AES:

5.3 Verification

Experimental Verification. We verified with Small-AES using 100 random keys and 2^{30} random \delta-sets. Small-AES deviates significantly from the theory, in the sense that the distinguisher is stronger. The experimental mean is approximately one standard deviation higher than the theoretical prediction.

Transition-based Verification. Using 100-bit precision:

The results confirmed the biases of our five-round distinguishers.

6 Six-round Key-recovery Attack

We can extend the five-round distinguisher from Section 5 to a key-recovery attack on six-round AES that recovers 32 key bits. We apply the attack twice in a shifted form to recover 64 key bits. The remaining key bits can be recovered by exhaustive search.

Precomputation. We construct four tables \mathcal{H}_i for 0 \le i \le 3, storing pairs (X, \Delta X) such that \check{R}(X) \oplus \check{R}(X \oplus \Delta X) is non-zero only in Byte i of the output column. Each table \mathcal{H}_i contains 255 \cdot 256^4 entries. The four tables need approximately 2^{40.1} state equivalents.

Steps. The attack proceeds as follows:

1. Initialize a zeroed list \mathcal{K} for 2^{32} key candidates for K^0[0, BarOn20, Bardeh19a, Cid05].
2. Precompute the tables \mathcal{H}_i.
3. For i = 1 \ldots 2^s, collect a structure of 2^{32} texts in a coset of \mathcal{D}_{\{0\}}. Look for collisions on anti-diagonals. For each collision, derive key candidates from the hash tables.
4. Sort the list of key candidates.
5. Apply the attack from a shifted diagonal to recover another 32 bits.
6. Test keys in descending order to recover the remaining 64 bits.

6.1 Relations between Success Probability, Advantage and Data

In Step 6, we apply the key-ranking approach. Denote by a = m - \lg \ell the advantage. Using Selcuk's model [Sel08]:

Optimal Computational Complexity. With a moderate success probability 63%, using the model from [SS17], we choose the balance point with a = 25. The required number of plaintext pairs is N = 2^{80.285}, the data complexity is approximately 2^{71.285} chosen plaintexts, and the computational complexity is approximately 2^{78.695} six-round encryptions.

6.2 Experimental Verification

We verified our attack on Small-AES. We chose 2^s structures of 2^{16} texts each. Our experiments aimed at recovering the 16 key bits K^0[0, BarOn20, Bardeh19a, Cid05] from the first diagonal. The experiments yielded mean advantages of 7.070, 10.550, and 14.243 bits for 2^{15}, 2^{16}, and 2^{17} structures, respectively.

7 Six-round Truncated-differential Distinguisher

Core Idea. We derive a six-round distinguisher that shares the higher-level concept of our six-round key-recovery attack. The idea is to extend the five-round distinguisher at the beginning by starting from a single-diagonal space.

Let X, X' \in (\mathbb{F}_{2^8})^{4 \times 4} be distinct with \Delta X = X \oplus X' \in \mathcal{D}_{\{c\}}. By the law of total probability:

The probability for a single active byte after the first round is:

From simple calculation:

This implies a difference |p_{\text{rand}} - p_{6,\text{AES}}| \simeq 2^{-73.989}. This difference is very small, but may still be high enough to distinguish between the distributions.

For success probability P_S \ge 0.95, one needs approximately N \ge 2^{120.43} pairs, obtainable from 2^{57.43} structures or 2^{89.43} chosen plaintexts.

Steps. The distinguisher proceeds as follows:

1. Initialize a collision counter.
2. For i = 1 \ldots 2^s, collect a structure of 2^{32} texts iterating over all values in \mathcal{D}_{\{0\}}. Invert the final MixColumns and ShiftRows to get S^{6,\text{SB}}.
3. For each structure, index states by columns into four lists.
4. For each list, look for column collisions. Increment counter for unique collisions.
5. If the counter exceeds threshold \theta, output real; otherwise, output random.

Complexity. The computational complexity is approximately 2^{89.7} encryptions and 2^{96.52} memory accesses.

Experimental Verification. We implemented the distinguisher for Small-AES with 100 random keys, encrypting 2^{25.21} structures of 2^{16} texts each. For Small-AES, we observed a mean of \mu = 131\,067.191 pairs per structure, and \mu = 131\,066.993 for the pseudorandom permutation. The difference in the distributions is even slightly higher in our experiments than in the theory.

Transition-based Verification. The results confirmed:

8 Discussion and Conclusion

This work extends the well-known integral distinguisher on three-round AES to truncated-differential distinguishers. Our attacks exploit a small difference in the average number of byte collisions between the sum of four permutations and the number of collisions for a truncated random permutation. In the AES, this sum is approximated by almost three rounds plus the MixColumns operation. The small but significant difference allowed us to extend the integral attack to four rounds. By extending this approach to collisions in the four bytes of an inverse diagonal, we proposed a novel five-round distinguisher for the AES.

Compared to the five-round distinguisher by Grassi and Rechberger [GR19], our distinguishers start from a single active byte. Thus, they could benefit from the fact that one can easily prepend one round for an attack and start from a diagonal structure of 2^{32} texts. Although inferior to previous key-recovery results on the AES, we could extend it to a key-recovery attack on six rounds in Section 6. Moreover, Section 7 showed that even this prepended round could still be included in a secret-key distinguisher, with considerably lower but still distinguishable bias.

Verifiability. We note that it is infeasible to verify the proposed distinguishers for the AES directly. Where possible, we tried to implement small-scale variants with Cid et al.'s established version of Small-AES with four-bit cells. We employed the transition-distribution approach by Ronjom as a second means of verification. All implementations are freely available online.

Open Questions.

• Which properties in the S-box and the cipher structure lead to the position-dependent diverse distribution of means in our four- and five-round distinguishers?
• Can we predict a-priori which input-output indices yield particularly strong distinguishers for the three-round differential in our four-round distinguisher, given the S-box?
• Which property leads to the multiple-of-32 collision counts for Small-AES?
• Is it the same or a different property that leads to higher variances in our five-round distinguisher for Small-AES?
• Which property leads to the significant deviation in the variance of Small-AES with the PRIDE S-box for our four-round distinguisher?

A Alternative S-boxes

We conducted further studies with variants of Small-AES that employed different four-bit S-boxes: PRESENT [BKL+07], PRINCE [BCG+12], and PRIDE [ADK+14], as well as three artificial constructions Toy-6, Toy-8, and Toy-10 from [GR19].

B Multiple-of-n Properties

B.1 Five-round Multiple-of-Eight Property. Consider the five-round distinguisher from Setting (2), which takes pairs of plaintexts from \delta-sets of a diagonal. This section shows that this setting preserves the multiple-of-eight property of the full-diagonal distinguisher.

B.2 Four-round Multiple-of-32 Property for Small-AES. The four-round distinguisher in Setting (2) possesses a multiple-of-32 property. Our experiments confirmed this: the number of collisions is always a multiple of 32 for Small-AES with four-bit S-boxes.

B.3 Multiple-of-four Distinguisher on Five-round Small-AES. Let \mathcal{S} be a structure iterating over all 2^{16} values of one diagonal space of Small-AES. Then, after four rounds, the number of pairs that collide in any fixed byte is a multiple of four. This implies a multiple-of-four property after five rounds. This property is absent in the real AES with eight-bit S-boxes.

The distinguisher requires 2^{16} chosen plaintexts and 2^{20} memory accesses. The success probability is one for the real construction; the probability to wrongly identify a random permutation is (2^{-2})^{16} = 2^{-32}.

B.4 Multiple-of-four Key-recovery Attack on Six-round Small-AES. The five-round distinguisher extends to a six-round key-recovery attack in a straightforward manner. The computational complexity is upper bounded by 2^{32.223} encryptions.

C Expectation of The Distinguishers

C.1 Expectation of The Five-round Distinguisher. This section shows Theorem 2 in Setting (2), rooted on the existing rigorous study by Grassi and Rechberger [GR18].

Combining the results: a diagonal space has 2\,114\,125\,822.5 solutions on average, and our distinguisher considers a fraction of 4/255^3 of these. This yields:

Since there are four diagonals:

C.2 Expectation of The Four-round Distinguisher. This section shows Theorem 1 in Setting (2). A similar approach yields:

The total number of different solutions is:

Using the fraction from Lemma 2:

D Variance of The Distinguishers

D.1 Variance of The Five-round Distinguisher. Grassi and Rechberger [GR19] showed that the distribution of collisions after five rounds from a diagonal space is described by:

where X_i \sim \mathcal{B}(N_i, p_i) are binomial distributions.

Since our distinguisher starts from a single active byte, all pairs have four different generating variables. In Setting (2), the variance is:

The random binomial variance is approximately 510, so the variance is about eight times higher in Setting (2).

D.2 Variance of The Four-round Distinguisher. For Setting (2), the variance is approximately 2^{35.9887}, versus 2^{32.9887} for a random binomial, again roughly eight times higher.

For Small-AES, due to the multiple-of-32 property, the variance is approximately 32 times higher in Setting (2) in theory. Experimentally, it was found to be about 15.4 times larger. The reason for this gap is unknown.

E Index Dependencies for Small-AES

E.1 Index Dependencies of The Four-round Distinguisher. For Small-AES, we computed the theoretical index-dependent expectations for all 16 \times 16 input-output combinations. The numbers of solutions in each row are permutations of each other with strong regularity. For i_{\text{in}} = 0, position i_{\text{out}} = 15 yields the highest number of collisions.

E.2 Index Dependencies of The Five-round Distinguisher. We expect weaker deviations due to the additional round compared to our four-round distinguisher and due to the fact that it considers four cells after three full rounds at a time. All choices for the active input cell yield distinguishers that are at least 2.2\sigma above the mean of the PRP, with peaks at 4.9\sigma.

F S-box Dependencies of The Four-round Distinguisher

The results for our four-round distinguisher with Small-AES deviate significantly from the theoretical prediction (6.85 standard-deviation units higher). We tested different S-boxes:

• The three real-world S-boxes (PRESENT, PRINCE, PRIDE) show lower, but noticeable distance to the random permutation.
• Two out of three toy S-boxes, Toy-8 and Toy-10, behave close to random and do not yield a distinguisher for the employed amount of data.
• The Toy-6 S-box strongly deviates from all others by having a significantly lower mean than the random permutation (-2.86 standard-deviation units).

S-box Properties. We tested the correlation of the distance measure D_S with S-box properties. We obtained a Pearson correlation coefficient (r, p) \simeq (0.812, 1.637 \cdot 10^{-13}), i.e., a high correlation of 0.812 with the S-box variance. S-boxes with low variances are considerably closer to the expected numbers of collisions. However, the variance does not fully explain the quality of an S-box.

G Adapted Heys-Liu Probabilistic Integral Distinguisher on Four-round Small-AES

In 2014, Heys [Hey14] conducted a similar analysis on BSPN, studying a probabilistic extension of the three-round integral. They studied the probability of obtaining a zero sum in the individual bytes after three rounds.

We adapted this to Small-AES, using 100 random keys and 2^s \delta-sets for s \in \{24, 26, 28, 30\}. We see considerable differences in the distribution starting from s = 28, although still a broad overlap of both distributions. For s = 30, the different distributions become apparent. The distinguisher is a consequence of ours but significantly more sophisticated to explore.

References

• [ADK+14] Albrecht, Driessen, Kavun, Leander, Paar, Yalcin. Block Ciphers - Focus on the Linear Layer (feat. PRIDE). CRYPTO I 2014, LNCS 8616, pp. 57-76.
• [Bar19] Bardeh. A Key-Independent Distinguisher for 6-round AES in an Adaptive Setting. ePrint 2019/945. [page on this site]
• [BCC19] Boura, Canteaut, Coggia. A General Proof Framework for Recent AES Distinguishers. ToSC 2019(1):170-191.
• [BCG+12] Borghoff et al. PRINCE - A Low-Latency Block Cipher for Pervasive Computing Applications. ASIACRYPT 2012, LNCS 7658.
• [BDK+20] Bar-On, Dunkelman, Keller, Ronen, Shamir. Improved Key Recovery Attacks on Reduced-Round AES with Practical Data and Memory Complexities. J. Cryptology 33(3), 2020.
• [BKL+07] Bogdanov et al. PRESENT: An Ultra-Lightweight Block Cipher. CHES 2007, LNCS 4727.
• [BKR11] Bogdanov, Khovratovich, Rechberger. Biclique Cryptanalysis of the Full AES. ASIACRYPT 2011, LNCS 7073.
• [BLNS18] Boura, Lallemand, Naya-Plasencia, Suder. Making the Impossible Possible. J. Cryptology 31(1), 2018.
• [BODK+18] Bar-On, Dunkelman, Keller, Ronen, Shamir. Improved Key Recovery Attacks on Reduced-Round AES. CRYPTO II 2018, LNCS 10992.
• [BR19a] Bardeh, Ronjom. Practical Attacks on Reduced-Round AES. Africacrypt 2019, LNCS 11627.
• [BR19b] Bardeh, Ronjom. The Exchange Attack: How to Distinguish 6 Rounds of AES with 2^{88.2} chosen plaintexts. ePrint 2019/652. [page on this site]
• [BR19c] Bardeh, Ronjom. The Exchange Attack. ASIACRYPT 2019, LNCS 11923.
• [CCM+18] Cui, Chen, Mesnager, Sun, Wang. Statistical integral distinguisher with multi-structure and its application on AES-like ciphers. Cryptography and Communications 10(5), 2018.
• [CKK+01] Cheon, Kim, Kim, Lee, Kang. Improved Impossible Differential Cryptanalysis of Rijndael and Crypton. ICISC 2001, LNCS 2288.
• [CMR05] Cid, Murphy, Robshaw. Small Scale Variants of the AES. FSE 2005, LNCS 3557.
• [CMSZ15] Chen, Miyaji, Su, Zhao. A New Statistical Approach for Integral Attack. NSS 2015, LNCS 9408.
• [DFJ13] Derbez, Fouque, Jean. Improved Key Recovery Attacks on Reduced-Round AES in the Single-Key Setting. EUROCRYPT 2013, LNCS 7881.
• [DKR97] Daemen, Knudsen, Rijmen. The Block Cipher Square. FSE 1997, LNCS 1267.
• [DKRS20] Dunkelman, Keller, Ronen, Shamir. The Retracing Boomerang Attack. EUROCRYPT I 2020, LNCS 12105.
• [DR02] Daemen, Rijmen. The Design of Rijndael: AES - The Advanced Encryption Standard. Springer, 2002.
• [DS08] Demirci, Selcuk. A Meet-in-the-Middle Attack on 8-Round AES. FSE 2008, LNCS 5086.
• [FKL+00] Ferguson, Kelsey, Lucks, Schneier, Stay, Wagner, Whiting. Improved Cryptanalysis of Rijndael. FSE 2000, LNCS 1978.
• [GM00] Gilbert, Minier. A Collision Attack on 7 Rounds of Rijndael. AES Candidate Conference, 2000.
• [GR18] Grassi, Rechberger. New Rigorous Analysis of Truncated Differentials for 5-round AES. ePrint 2018/182. [page on this site]
• [GR19] Grassi, Rechberger. Rigorous Analysis of Truncated Differentials for 5-round AES. ePrint 2018/182 (updated 2019).
• [Gra17] Grassi. Mixture Differential Cryptanalysis. ePrint 2017/832. [page on this site]
• [Gra18a] Grassi. MixColumns Properties and Attacks on (Round-Reduced) AES with a Single Secret S-Box. CT-RSA 2018, LNCS 10808.
• [Gra18b] Grassi. Mixture Differential Cryptanalysis. ToSC 2018(2):133-160.
• [Gra19] Grassi. Probabilistic Mixture Differential Cryptanalysis on round-reduced AES. SAC 2019, LNCS 11959.
• [GRR16] Grassi, Rechberger, Ronjom. Subspace Trail Cryptanalysis and its Applications to AES. ToSC 2016(2):192-225.
• [GRR17] Grassi, Rechberger, Ronjom. A New Structural-Differential Property of 5-Round AES. EUROCRYPT II 2017, LNCS 10211.
• [HCGW18] Hu, Cui, Gao, Wang. Towards Key-Dependent Integral and Impossible Differential Distinguishers on 5-Round AES. SAC 2018, LNCS 11349.
• [Hey14] Heys. Integral cryptanalysis of the BSPN block cipher. Biennial Symposium on Communications, IEEE, 2014.
• [MDRM10] Mala, Dakhilalian, Rijmen, Modarres-Hashemi. Improved Impossible Differential Cryptanalysis of 7-Round AES-128. INDOCRYPT 2010, LNCS 6498.
• [Nat01] NIST. FIPS 197. National Institute of Standards and Technology, 2001.
• [Pat08] Patarin. Generic Attacks for the Xor of k random permutations. ePrint 2008/009.
• [Pat13] Patarin. Generic Attacks for the Xor of k Random Permutations. ACNS 2013, LNCS 7954.
• [RBH17] Ronjom, Bardeh, Helleseth. Yoyo Tricks with AES. ASIACRYPT I 2017, LNCS 10624.
• [Ron19] Ronjom. A Short Note on a Weight Probability Distribution Related to SPNs. ePrint 2019/750. [page on this site]
• [Sel08] Selcuk. On Probability of Success in Linear and Differential Cryptanalysis. J. Cryptology 21(1), 2008.
• [SLG+16a] Sun, Liu, Guo, Qu, Rijmen. New Insights on AES-Like SPN Ciphers. CRYPTO I 2016, LNCS 9814.
• [SLG+16b] Sun, Liu, Guo, Rijmen, Li. Provable Security Evaluation of Structures Against Impossible Differential and Zero Correlation Linear Cryptanalysis. EUROCRYPT I 2016, LNCS 9665.
• [SLR+15] Sun, Liu, Rijmen, Li, Cheng, Wang, AlKhzaimi, Li. Links Among Impossible Differential, Integral and Zero Correlation Linear Cryptanalysis. CRYPTO I 2015, LNCS 9215.
• [SS17] Samajder, Sarkar. Rigorous upper bounds on data complexities of block cipher cryptanalysis. J. Mathematical Cryptology 11(3), 2017.
• [TA14] Todo, Aoki. FFT Key Recovery for Integral Attack. CANS 2014, LNCS 8813.
• [Tod14] Todo. FFT-Based Key Recovery for the Integral Attack. ePrint 2014/187.
• [Tun12a] Tunstall. Improved Partial Sums-based Square Attack on AES. SECRYPT 2012.
• [Tun12b] Tunstall. Improved "Partial Sums"-based Square Attack on AES. ePrint 2012/280. [page on this site]
• [WJ18] Wang, Jin. Upper bound of the length of truncated impossible differentials for AES. Des. Codes Cryptography 86(7), 2018.
• [WJ19] Wang, Jin. More accurate results on the provable security of AES against impossible differential cryptanalysis. Designs, Codes and Cryptography, 2019.