# Understanding Unexpected Fixed-Key Differential Behaviours: How to Avoid Major Weaknesses in Lightweight Designs

Anne Canteaut, Merlin Fruchon

► To cite this version:

Anne Canteaut, Merlin Fruchon. Understanding Unexpected Fixed-Key Differential Behaviours: How to Avoid Major Weaknesses in Lightweight Designs. ASIACRYPT 2025 - 31st International Conference on the Theory and Application of Cryptology and Information Security, Dec 2025, Melbourne, Australia. 10.1007/978-981-95-5018-0_4. hal-05466832

HAL Id: hal-05466832

https://inria.hal.science/hal-05466832v1

Submitted on 20 Jan 2026

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
Understanding Unexpected Fixed-Key
Differential Behaviours: How to Avoid Major
Weaknesses in Lightweight Designs

Anne Canteaut¹ and Merlin Fruchon²,¹

¹ Inria, Paris, France

² DGA, France

**Abstract** Many design strategies and differential attacks rely on the so-called hypothesis of stochastic equivalence, which states that the differential behaviour of a cipher for any fixed key can be approximated by its average behaviour over all keys. However, this assumption is known to be invalid in general. For instance, all two-round differential characteristics of AES are plateau, meaning that their probabilities highly depend on the key. While such discrepancies were traditionally expected to occur only for a small number of rounds, several counter-examples have been exhibited recently thanks to the quasi-differential framework. This paper aims to show why the divergence between fixed-key and average behaviour can be even more pronounced and is definitely harder to anticipate when analyzing differentials, rather than individual characteristics, which is the quantity actually relevant in differential cryptanalysis. Indeed, when a differential aggregates many characteristics that do not satisfy the hypothesis of stochastic equivalence, several scenarios may arise: the sets of weak keys may be identical across all characteristics, resulting in a strong clustering effect, or entirely disjoint, eliminating any such effect. Focusing on (truncated) differentials that include plateau characteristics, we demonstrate how this mechanism explains the unexpected differential behaviour observed in MIDORI64 and SCREAM over an arbitrary number of rounds, as recently reported by Baudrin et al. We also clarify how this situation differs from invariant subspaces, except in a few specific cases. Furthermore, we identify the properties of the Sbox that give rise to this weakness and all vulnerable Sboxes among the optimal 4-bit functions.

**Keywords.** Differential cryptanalysis · Hypothesis of stochastic equivalence · Clustering effect · Invariant subspaces · MIDORI64.

# 1 Introduction

Differential cryptanalysis, introduced in 1990 by Biham and Shamir [BS91], is one of the oldest and most prominent cryptanalytic techniques in symmetric cryptography. Various design strategies, such as the wide-trail strategy [DR01] or a careful selection of the constituent Sboxes [Nyb12], have been successfully
developed to ensure resistance against this type of attacks. Today, any new pro-
posal is expected to demonstrate robustness against differential attacks. How-
ever, evaluating the resistance to differential cryptanalysis still relies on several
hypotheses that may not hold always in practice. One such hypothesis is the
*hypothesis of stochastic equivalence*, first introduced by Lai, Massey and Mur-
phy [LMM91]. This hypothesis formalizes the idea that the behaviour of a cipher
for (almost) all *fixed values of the expanded key* can be approximated by its *av-
erage* behaviour over all possible keys. Indeed, for key-alternating ciphers, the
so-called *expected differential probability (EDP)* of a differential characteristic
corresponds to the average of its fixed-key probabilities, where the average is
taken over all possible expanded keys, i.e., over all possible sequences of inde-
pendent round-keys.

Several practical scenarios where the hypothesis of stochastic equivalence
does not hold have been known for a long time, for instance, for certain it-
erative 2-round characteristics on DES used by Biham and Shamir [Knu93].
Later, Daemen and Rijmen [DR07] identified and thoroughly studied a broad
class of characteristics, called *plateau characteristics*, for which the hypothesis
of stochastic equivalence fails. Indeed, these are characteristics whose fixed-key
probability is either a constant or zero, depending on whether the expanded
key belongs to a specific set of weak keys or not. Notably, Daemen and Rijmen
proved that, in any SPN using an Sbox with differential uniformity 4, all 2-round
differential characteristics are plateau. Extending this analysis beyond 2 rounds
was considered challenging, until Beyne and Rijmen recently introduced a novel
framework, called *quasi-differentials* [BR22]. This framework provides an exact
expression for the fixed-key probability of a differential characteristic. Although
it involves matrices of size 2<sup>2n</sup> × 2<sup>2n</sup>, where *n* is the block size, it offers an elegant
and powerful tool for enabling a far more accurate and insightful analysis of the
differential behavior of symmetric primitives.

Another major difficulty in determining the complexity of differential attacks
lies in the fact that the relevant quantity is not the probability of a specific
differential characteristic, which corresponds to a sequence (Δ₀, Δ₁, ..., Δₚ) of
intermediate differences across the successive rounds. In practice, only the input
and output differences are accessible to an attacker. Consequently, the relevant
quantity is the probability of the differential (Δ₀, Δₚ). It corresponds to the cu-
mulative probability of all differential characteristics (Δ₀, Δ₁, ..., Δₚ) that begin
with Δ₀ and end with Δₚ. In some cases, this probability is well approximated
by that of a single dominant characteristic (or a few of them). But, there also
several well-known cases where this is not the case and where the complexity
of the attack is significantly lower than expected because several characteris-
tics need to be taken into account, see e.g. [Abd13,CFG^+15,LPS21]. Crucially,
when the hypothesis of stochastic equivalence does not hold, summing the ex-
pected differential probabilities of the individual characteristics to estimate the
EDP of the overall differential is misleading. Indeed, many of the contributing
characteristics may have nonzero EDPs, but each may be valid only for different
weak-key sets. In such a case, there is no clustering effect, contrary to what might
be incorrectly inferred from the individual EDPs. However, if all contributing
characteristics happen to correspond to the same weak-key set, this could pose
a potential threat.

The aim of this paper is to analyse such behaviours, and demonstrate why
traditional analysis based on the EDP can lead to misleading results and in-
correct intuitions. Studies of recent constructions intended for low-resources de-
vices have revealed several unexpected fixed-key behaviours in ciphers designed
according to state-of-the-art design principles. These findings have led to new
types of attacks, such as invariant-subspace attacks [LAAZ11,LMR15,GJN+16]
or nonlinear-invariant attacks [TLS16,Bey18]. More intriguingly, as a corollary
of their commutative cryptanalysis, Baudrin et al. revealed the existence of trun-
cated differentials on MIDORI64 [BBI+15] that hold for an arbitrary number of
rounds with probability 2<sup>-16</sup> for a certain set of weak expanded-keys [BFL+23].
Interestingly, the corresponding set of weak expanded-keys contains, as a sub-
set, the weak keys for which invariant subspaces have been previously found
in [GJN+16] and [Bey18]. However, it also includes some new weak-keys for
which this differential behaviour was unknown and cannot be explained by tra-
ditional methods. A similar phenomenon is reported on SCREAM [GLS+14].

We believe that understanding the origin of such unexpected behaviours,
is extremely important. Indeed, the existence of an unexpected behaviour for
a cipher that follows the state-of-the-art design principles, calls into question
the security of a broader class of primitives. A common mitigation strategy is to
adopt a more complex key schedule, in the hope that it will be incompatible with
the potential weak expanded keys. However, this approach is not entirely satis-
factory: complex key schedules come with an implementation overhead, whereas
a simpler—often linear—key schedule is typically considered an efficient option,
particularly in the context of lightweight cryptography.

Our contributions. Our main contribution is to clarify the phenomenon identi-
fied by Baudrin et al. on MIDORI64 and SCREAM, and to identify its origins.
We show that this unexpected differential behaviour actually results from two
distinct phenomena, depending on the weak expanded-keys involved. For some
weak keys, specifically those previously identified by Guo et al. for MIDORI64,
this truncated differential includes a plateau characteristic which has a high
probability. However, for the vast majority of the weak expanded-keys, all con-
stituent characteristics are plateau but have a very low probability (typically
2<sup>-62</sup> or 2<sup>-63</sup>) as the number of rounds increases. We then show that the number
of such constituent plateau characteristics that are valid for at least one weak
expanded-key is quite large. More importantly, due to the specific properties of
MIDORI64’s Sbox, all these characteristics are valid for the same weak-keys. We
precisely identify the Sbox properties responsible for each phenomenon, and as
an illustration, we show how changing the Sbox significantly modifies the fixed-
key differential behaviour. As a corollary, we prove that among all optimal 4-bit
Sboxes [LP07], only those having 3 components of algebraic degree 2 may lead
to the same behavior as observed on MIDORI64 by Baudrin et al. Most notably,
some “Silver Sboxes” proposed by Guo et al. [GJN+16] as stronger alternatives
to MIDORI64's Sbox due to their resistance to invariant subspaces, exhibit the exact same vulnerability as MIDORI64 with respect to the truncated differential.

*Outline.* The next section is dedicated to plateau characteristics. It mainly recalls the results of Daemen and Rijmen [DR07]. Thanks to the quasi-differential framework [BR22], it formalizes the case of some plateau characteristics over many rounds, in a way that provides an explicit description of the weak-key subspace and of the set of valid inputs. Section 3 then focuses on the fixed-key probability of a truncated differential when it aggregates many plateau characteristics that have the previously studied form. We analyse how the number of such characteristics, that are valid for at least one weak expanded-key, grows with the number of rounds. Moreover, we determine under which condition all these characteristics are valid for the same weak keys. Section 4 illustrates these theoretical results by analysing how the fixed-key truncated differential probability in MIDORI64 varies with the properties of the Sbox. The influence of the Sbox is then further examined in Section 5, where we identify all optimal 4-bit Sboxes exhibiting this weakness, including several Silver Sboxes recommended in [GJN+16]. Section 6 shows how the results in Section 3 extend to a more general setting, with a larger set of differences, and illustrates this on SCREAM and ISCREAM. Finally, Section 7 analyses the similarities and differences between our work and different techniques, including invariant-subspace attacks [LAAZ11,LMR15,GJN+16] and commutative cryptanalysis [BFL+23].

# 2 A Deeper Look at Plateau Characteristics

## 2.1 General Setting and Notation

In the paper, we consider an SPN cipher with block size $n := sm$. Its round function is defined as $\mathcal{R} := L \circ \mathcal{S}$ where $L : \mathbb{F}_2^{sm} \to \mathbb{F}_2^{sm}$ is the linear layer and $\mathcal{S}$ corresponds to the parallel application of $m$ copies of the same $s$-bit Sbox $S : \mathbb{F}_2^s \to \mathbb{F}_2^s$. At the beginning of each round, an $n$-bit round-key is xored to the internal state of the cipher. For $r$ rounds, we denote by $K := (K_1, K_2, \dots, K_{r-1})$ the expanded key, i.e., the vector of round keys where the initial and final whitening round keys are omitted.

In the following, we study the probability of an $r$-round differential characteristic $(\Delta_0, \dots, \Delta_r)$. A valid input for this characteristic is a plaintext $x \in \mathbb{F}_2^n$ for which the following two sequences

$$ \begin{cases} x_0 := x \\ \tilde{x}_0 := x + \Delta_0 \end{cases}, \quad \begin{cases} x_{t+1} = \mathcal{R}(x_t) + K_{t+1} \\ \tilde{x}_{t+1} = \mathcal{R}(\tilde{x}_t) + K_{t+1} \end{cases} $$

satisfy $\tilde{x}_t = x_t + \Delta_t$ for all $0 \le t \le r$.

For any expanded key $K = (K_1, \dots, K_{r-1})$, we denote by $\text{DP}[K](\Delta_0, \dots, \Delta_r)$ the probability that the characteristic $(\Delta_0, \dots, \Delta_r)$ is satisfied by the $r$-round cipher with key $K$. The expected differential probability (EDP) of $(\Delta_0, \dots, \Delta_r)$
then corresponds to the average value of DP[K](Δ₀, ..., Δₚ), i.e.

$$ \mathrm{EDP}(\Delta_0, \dots, \Delta_r) = \sum_{K \in \mathbb{F}_2^{n(r-1)}} 2^{-n(r-1)} \mathrm{DP}[K](\Delta_0, \dots, \Delta_r). $$

While the expected differential probability of (Δ₀, ..., Δₚ) is entirely determined by the differential probabilities of the Sbox, its fixed-key probability highly depends on the structure of the set on inputs satisfying the Sbox transitions. The following notation will be extensively used in the rest of the paper.

**Definition 1 (Derivative).** For any $S: \mathbb{F}_2^s \to \mathbb{F}_2^s$ and any $a \in \mathbb{F}_2^s$, the derivative of $S$ at $a$ is the function from $\mathbb{F}_2^s$ to $\mathbb{F}_2^s$ defined by $D_a S: x \mapsto S(x+a)+S(x)$.

**Notation 1** For any $S: \mathbb{F}_2^s \to \mathbb{F}_2^s$, and any differential $(a, b)$, with $a, b \in \mathbb{F}_2^s$, we denote the input (resp. output) set of $(a, b)$ as follows:

$$ \mathrm{XDDT}_S(a, b) := \{x \in \mathbb{F}_2^s \mid D_a S(x) = b\} \quad \text{and} \quad \mathrm{YDDT}_S(a, b) := \{S(x) \mid x \in \mathrm{XDDT}_S(a, b)\}. $$

$$ \textit{Moreover, } \mathrm{DDT}_S(a, b) := \#\mathrm{XDDT}_S(a, b) = \#\mathrm{YDDT}_S(a, b). $$

## 2.2 Planar and Super-Planar Differentials

The case where the input and output sets of a differential are (affine) subspaces is of particular interest as first pointed out by Daemen and Rijmen [DR07].

**Definition 2 (Planar differential [DR07]).** A differential $(a, b)$ for $S: \mathbb{F}_2^s \to \mathbb{F}_2^s$ is said to be planar if both sets $\mathrm{XDDT}_S(a, b)$ and $\mathrm{YDDT}_S(a, b)$ are affine subspaces. In this case, we use the following notation:

$$ \mathrm{XDDT}_S(a, b) := x_0^{a,b} + U_S(a, b) \quad \text{and} \quad \mathrm{YDDT}_S(a, b) := y_0^{a,b} + V_S(a, b) $$

$$ \textit{where } y_0^{a,b} = S(x_0^{a,b}). $$

As noted in [DR07], any differential $(a, b)$ with $\mathrm{DDT}_S(a, b) \in \{2, 4, 2^s\}$ is planar, implying that all differentials of an Sbox with differential uniformity at most 4 are planar. We refine this notion and define the more restricted property of super-planar differential. This new property will actually enable us to determine the fixed-key probability of some characteristics over several rounds by composition.

**Definition 3 (Super-planar differential).** Let $(a, b)$ be a planar differential for $S: \mathbb{F}_2^s \to \mathbb{F}_2^s$ with $\mathrm{XDDT}_S(a, b) = x_0^{a,b} + U_S(a, b)$. Let

$$ \phi_{a,b}: U_S(a, b) \to V_S(a, b) \\ \theta \mapsto S(x_0^{a,b}) + S(x_0^{a,b} + \theta) = D_\theta S(x_0^{a,b}). $$

Then, $(a, b)$ is super-planar if one of the following equivalent conditions holds:
(i) The function $\phi_{a,b}$ is linear.

(ii) The set corresponding to the graph of $\phi_{a,b}$, i.e.,

$$ Z_S(a, b) := \{(\theta, \phi_{a,b}(\theta)) \mid \theta \in U_S(a, b)\} \quad (1) $$

is a linear subspace of $U_S(a, b) \times V_S(a, b)$.

(iii) For all $\theta_1, \theta_2 \in U_S(a, b)$, $D_{\theta_1} D_{\theta_2} S(x_0^{a,b}) = 0$.

The equivalence between (i) and (iii) is derived from the following more general fact: for any $\theta_1, \theta_2$ and any $x \in \mathbb{F}_2^s$, $D_{\theta_1} S(x) + D_{\theta_2} S(x) + D_{\theta_1+\theta_2} S(x) = D_{\theta_1} D_{\theta_2} S(x)$.

We note that (iii) implies that any choice for the offset $x_0^{a,b}$ leads to the same function $\phi_{a,b}$. Indeed, for any other offset $z_0^{a,b} = x_0^{a,b} + u$, with $u \in U_S(a, b)$, we have $D_\theta S(z_0^{a,b}) + D_\theta S(x_0^{a,b}) = D_u D_\theta S(x_0^{a,b}) = 0$, for all $\theta \in U_S(a, b)$.

Super-planar differentials of $S$ are therefore planar differentials such that $S$ is affine on $XDDT_S(a, b)$, because

$$ S(XDDT_S(a, b)) = S(x_0^{a,b} + U_S(a, b)) = S(x_0^{a,b}) + \phi_{a,b}(U_S(a, b)). $$

**Lemma 1.** Let $(a, b)$ be any differential for $S$ such that $DDT_S(a, b) \in \{2, 4\}$. Then, $(a, b)$ is super-planar. Most notably, if $S$ has differential uniformity at most 4, all its active differentials are super-planar.

*Proof.* We first observe that $\phi_{a,b}(0) = 0$ and $\phi_{a,b}(a) = b$.

The case $DDT_S(a, b) = 2$ is trivial since $\phi_{a,b}$ is defined over a subspace of dimension 1, and is therefore linear.

When $DDT_S(a, b) = 4$, we have $U_S(a, b) = \langle a, \theta \rangle$ for some $\theta \in U_S(a, b) \setminus \{0, a\}$, where $\langle v_1, \dots, v_k \rangle$ denotes the linear space spanned by $v_1, \dots, v_k$. Then,

$$ \begin{aligned} \phi_{a,b}(a + \theta) &= S(x_0^{a,b}) + S(x_0^{a,b} + \theta + a) \\ &= S(x_0^{a,b}) + S(x_0^{a,b} + \theta) + S(x_0^{a,b} + \theta) + S(x_0^{a,b} + \theta + a) \\ &= \phi_{a,b}(\theta) + b = \phi_{a,b}(\theta) + \phi_{a,b}(a). \end{aligned} $$

where the penultimate equality uses that $x_0^{a,b} + \theta \in XDDT_S(a, b)$. $\square$

It is important to note that any differential with probability one is planar but is not super-planar if $\deg S > 1$. Indeed, in this case, $U_S(a, b) = V_S(a, b) = \mathbb{F}_2^s$ and (iii) means that $S(0) + S(\theta_1) + S(\theta_2) + S(\theta_1 + \theta_2) = 0$ for all $\theta_1, \theta_2$, i.e. $x \mapsto S(x) + S(0)$ is linear.

Super-planar differentials may also occur for a higher value of $DDT_S(a, b)$. For instance, the Sbox of ISCREAM [GLS+14] has a super-planar differential $(a, b)$ with $DDT_S(a, b) = 8$.

Another simple but useful remark is that, when $S: \mathbb{F}_2^{sm} \to \mathbb{F}_2^{sm}$ corresponds to the Cartesian product of $m$ functions of $S_j: \mathbb{F}_2^s \to \mathbb{F}_2^s$, then the differential $(A, B)$ for $S$ is planar (resp. super-planar) if all constituent differentials are planar (resp. super-planar). Indeed, $XDDT_S(A, B) = \prod_{j=1}^m XDDT_{S_j}(A[j], B[j])$. The other subspaces $YDDT_S(A, B)$, $U_S(A, B)$, $V_S(A, B)$ and, in the super-planar case, $Z_S(A, B)$ similarly equal the products of the subspaces corresponding to the constituent Sboxes.
## 2.3 Plateau Characteristics over Several Rounds

Plateau characteristics are a major type of differential characteristics whose fixed-key probabilities are distributed in a very structured way and significantly differ from the average.

**Definition 4 (Plateau characteristic [DR07]).** A characteristic $(\Delta_0, \dots, \Delta_r)$ for an iterative function over $\mathbb{F}_2^n$ is said to be plateau if there exists an integer $h \ge 0$ such that its fixed-key probability satisfies

$$ \mathrm{DP}[K](\Delta_0, \dots, \Delta_r) \in \{0, 2^{-n+h}\}. $$

The number of expanded keys for which the characteristic is valid is then determined by the value of $h$ and the EDP of the characteristic. Daemen and Rijmen proved that any SPN with a differentially 4-uniform Sbox, including the AES, is such that all its 2-round characteristics are plateau. However, extending such characteristics to more rounds and determining their probabilities is more complicated. The notion of quasi-differential matrix, later introduced by Beyne and Rijmen [BR22], provides a very useful tool that can be applied to this context.

**Definition 5 (Quasi-differential transition matrix [BR22]).** Let $F: \mathbb{F}_2^n \to \mathbb{F}_2^n$. Its quasi-differential transition matrix is the $(2^{2n} \times 2^{2n})$-matrix defined by

$$ D^F(v, b)(u, a) := 2^{-n} \sum_{x \in \mathrm{XDDT}_F(a,b)} (-1)^{v \cdot F(x) + u \cdot x}, \quad \forall u, v, a, b \in \mathbb{F}_2^n, $$

where $x \cdot y$ denotes the scalar product between $x$ and $y$.

The entries of the quasi-differential transition matrix corresponding to a super-planar differential $(a, b)$ have a very simple expression involving the input and output sets of $(a, b)$, namely $\mathrm{XDDT}_F(a, b) = x_0^{a,b} + \mathrm{U}_F(a, b)$ and $\mathrm{YDDT}_F(a, b) = y_0^{a,b} + \mathrm{V}_F(a, b)$.

**Lemma 2.** Let $F: \mathbb{F}_2^n \to \mathbb{F}_2^n$ and $(a, b)$ be a super-planar differential for $F$, $a, b \in \mathbb{F}_2^n \setminus \{0\}$. Then, for all $u, v \in \mathbb{F}_2^n$, we have

$$ D^F(v, b)(u, a) = \begin{cases} (-1)^{u \cdot x_0^{a,b} + v \cdot y_0^{a,b}} \mathrm{DDT}_F(a, b) \times 2^{-n} & \text{if } (u, v) \in \mathrm{Z}_F(a, b)^{\perp} \\ 0 & \text{otherwise,} \end{cases} $$

where $\mathrm{Z}_F(a, b)$ is defined by (1). Moreover, if $(a, b)$ is a planar differential,

$$ -D^F(v, b)(0, a) = (-1)^{v \cdot y_0^{a,b}} \mathrm{DDT}_F(a, b) 2^{-n} \mathbf{1}_{v \in \mathrm{V}_F(a,b)^{\perp}} $$

$$ -D^F(0, b)(u, a) = (-1)^{u \cdot x_0^{a,b}} \mathrm{DDT}_F(a, b) 2^{-n} \mathbf{1}_{u \in \mathrm{U}_F(a,b)^{\perp}} $$

where $\mathbf{1}_{x \in X}$ equals 1 if $x \in X$ and 0 otherwise.
It is important to observe that the previous formula holds only for the entries of the quasi-differential matrix corresponding to an active differential, i.e., when a and b are nonzero. Indeed, the entries corresponding to a = b = 0 are given by the Walsh coefficients of the function.

While planar differentials for the Sbox lead to 2-round plateau characteristics, the result cannot be directly extended to a larger number of rounds. Daemen and Rijmen [DR07, Page 11] have pointed out that plateau characteristics can be composed in the particular case of an SPN with an Sbox with differential uniformity at most 4 when all the Sboxes are active. The following theorem refines this result, first by removing the constraint on the differential uniformity of the Sbox, which enables us to capture other situations, like in SCREAM. More importantly, we provide an explicit expression of the corresponding set of valid inputs, and of the expanded keys for which the characteristic is valid.

**Theorem 1.** Let us consider a key-alternating cipher with linear layer L and nonlinear layer $\mathcal{S} = (S, \dots, S)$. Let $(\Delta_0, \Delta_1, \dots, \Delta_r)$ be an r-round differential characteristic, $r \ge 2$, such that all constituent differentials for $S$, i.e.,

$$ (\Delta_t[j], L^{-1}(\Delta_{t+1})[j]), \forall 0 \le t \le r-1, \forall 1 \le j \le m $$

are planar, and all internal differentials, i.e. for $1 \le t \le r-2$, are super-planar. Then, $(\Delta_0, \Delta_1, \dots, \Delta_r)$ is plateau and satisfies

$$ \mathrm{DP}[K](\Delta_0, \dots, \Delta_r) = \begin{cases} 2^{-n-\dim(W)} \prod_{t=0}^{r-1} \mathrm{DDT}_{\mathcal{S}}(\Delta_t, L^{-1}(\Delta_{t+1})) & \text{if } K \in w_0 + W \\ 0 & \text{otherwise,} \end{cases} $$

with $w_0 := (x_0^{\Delta_t L^{-1}(\Delta_{t+1})} + L(y_0^{\Delta_{t-1} L^{-1}(\Delta_t)}))_{1 \le t \le r-1}$ and W is the sum of the following r linear subspaces of $\mathbb{F}_2^{sm(r-1)}$

$$ -L(\mathcal{V}_{\mathcal{S}}(\Delta_0, L^{-1}(\Delta_1))) \times \{0\}^{sm(r-2)} $$

$$ - \{0\}^{sm(r-1)} \times (I \times L)(\mathcal{Z}_{\mathcal{S}}(\Delta_t, L^{-1}(\Delta_{t+1}))) \times \{0\}^{sm(r-2-t)} \text{ for } 1 \le t \le r-2 $$

$$ - \{0\}^{sm(r-2)} \times \mathcal{U}_{\mathcal{S}}(\Delta_{r-1}, L^{-1}(\Delta_r)). $$

where $(F \times G)$ denotes the Cartesian product of two functions, i.e., the function which maps $(x, y)$ to $(F(x), G(y))$, and $\mathcal{U}_{\mathcal{S}}$, $\mathcal{V}_{\mathcal{S}}$ and $\mathcal{Z}_{\mathcal{S}}$ are defined in Def. 2 and 3.

The proof relies on the same ideas as [DR07], but it uses Lemma 2 to give an explicit expression for the weak-key space. It is detailed in [CF25].

Moreover, when the expanded key satisfies the conditions exhibited in the previous theorem, the set of the valid inputs of the characteristic can be explicitly described, as shown in the following proposition.

**Proposition 1.** Let $(\Delta_0, \Delta_1, \dots, \Delta_r)$ be an r-round differential characteristic, $r \ge 2$, satisfying the same conditions as in Theorem 1. If the expanded key is such
that the characteristic is valid, then the set of valid inputs of the characteristic equals $\mathcal{S}^{-1}(\tilde{X}_r)$ where $\tilde{X}_r$ is a coset of the linear space

$$X_r := \{x \in V_S(\Delta_0, L^{-1}(\Delta_1)) \mid L \circ \phi_{\Delta_{t-1}, L^{-1}(\Delta_t)} \circ \dots \circ L \circ \phi_{\Delta_1, L^{-1}(\Delta_2)} \circ L(x) \\ \text{belongs to } U_S(\Delta_t, L^{-1}(\Delta_{t+1})), \forall 1 \le t \le r-1\}.$$

*Proof.* We show by induction on $r \ge 2$ that the set of valid inputs of the $r$-round characteristic $(\Delta_0, \dots, \Delta_r)$ is of the form $\mathcal{S}^{-1}(\tilde{X}_r)$ where $\tilde{X}_r$ is a coset of $X_r$, and that the images of the valid inputs before the $r$-th round form a coset of

$$L \circ \phi_{\Delta_{r-2}, L^{-1}(\Delta_{r-1})} \circ \dots \circ L \circ \phi_{\Delta_1, L^{-1}(\Delta_2)} \circ L(X_r).$$

For $r = 2$: it is well-known (see e.g. [DR07, Th. 1]) that the set formed by all images of the valid inputs after the first round, $y$, corresponds to the intersection between $K_1 + L(YDDT_S(\Delta_0, L^{-1}(\Delta_1)))$ and $XDDT_S(\Delta_1, L^{-1}(\Delta_2))$. The set of all valid $y$ is therefore a coset of the linear subspace

$$L(V_S(\Delta_0, L^{-1}(\Delta_1))) \cap U_S(\Delta_1, L^{-1}(\Delta_2)),$$

which is equal to $L(X_2)$. Therefore, the valid inputs of the 2-round characteristic are the values of $\mathcal{R}^{-1}(c + L(X_2)) = \mathcal{S}^{-1}(c' + X_2)$ for some offsets $c, c'$, where $\mathcal{R} = L \circ \mathcal{S}$.

**Induction step:** Consider a valid $r$-round characteristic. From the induction hypothesis, we know that the set of valid inputs of to the $(r-1)$-round characteristic $(\Delta_0, \dots, \Delta_{r-1})$ is $\mathcal{S}^{-1}(\tilde{X}_{r-1})$, where $\tilde{X}_{r-1}$ is a coset of $X_{r-1}$. Moreover, their images after the first $(r-2)$ rounds form a coset $\tilde{Y}_{r-1}$ of

$$Y_{r-1} = L \circ \phi_{\Delta_{r-3}, L^{-1}(\Delta_{r-2})} \circ \dots \circ L \circ \phi_{\Delta_1, L^{-1}(\Delta_2)} \circ L(X_{r-1}) \subset U_S(\Delta_{r-2}, L^{-1}(\Delta_{r-1})).$$

Since $(\Delta_{r-2}, L^{-1}(\Delta_{r-1}))$ is a super-planar differential for $\mathcal{S}$ and the characteristic is valid, $\tilde{Y}_{r-1}$ is non-empty and is included in $XDDT_S(\Delta_{r-2}, L^{-1}(\Delta_{r-1}))$. Therefore, we can choose $x_0^{\Delta_{r-2}, L^{-1}(\Delta_{r-1})} \in \tilde{Y}_{r-1}$ so that $\tilde{Y}_{r-1} = x_0^{\Delta_{r-2}, L^{-1}(\Delta_{r-1})} + Y_{r-1}$. Then,

$$\mathcal{S}(\tilde{Y}_{r-1}) = \mathcal{S}(x_0^{\Delta_{r-2}, L^{-1}(\Delta_{r-1})}) + \phi_{\Delta_{r-2}, L^{-1}(\Delta_{r-1})}(Y_{r-1})$$

where $\phi_{\Delta_{r-2}, L^{-1}(\Delta_{r-1})}$ is linear. It follows that the images of $\mathcal{S}^{-1}(\tilde{X}_{r-1})$ after the first $(r-1)$ rounds form a coset of $L \circ \phi_{\Delta_{r-2}, L^{-1}(\Delta_{r-1})}(Y_{r-1})$. Moreover, any element $u + y, y \in L \circ \phi_{\Delta_{r-2}, L^{-1}(\Delta_{r-1})}(Y_{r-1})$ in this coset also satisfies the last-round differential if and only if it belongs to $XDDT_S(\Delta_{r-1}, L^{-1}(\Delta_r))$, or equivalently if $L \circ \phi_{\Delta_{r-2}, L^{-1}(\Delta_{r-1})}(y) \in U_S(\Delta_{r-1}, L^{-1}(\Delta_r))$. It follows that any such element corresponds to an input in $\mathcal{S}^{-1}(\tilde{X}_r)$ where $\tilde{X}_r$ is a coset of $X_r$. $\square$

In the case where the first-round and last-round differentials for $\mathcal{S}$ are also super-planar, the valid inputs of the characteristic form an affine subspace, which
then propagates as a chain of subspaces across the r rounds, as observed in the following direct corollary. This corresponds to the notion of input-planar and output-planar characteristic in [DR07]. Obviously, the additional condition on the first-round and last-round differentials is necessary. For instance, the valid inputs of any 2-round characteristic in AES do not form an affine subspace.

**Corollary 1.** Let $(\Delta_0, \Delta_1, \dots, \Delta_r)$ be an $r$-round differential characteristic, $r \ge 2$, such that all constituent differentials for the Sbox $S$ are super-planar. If the expanded key is such that the characteristic is valid, then there is a chain of affine subspaces of the same dimension that propagates across the $r$ rounds where the linear part $V_i$ of the subspace at the input of Round $i$, $0 \le i < r$, is given by

$$ V_0 = \{x \in \mathcal{U}_S(\Delta_0, L^{-1}(\Delta_1)) \mid L \circ \phi_{\Delta_{t-1}, L^{-1}(\Delta_t)} \circ \dots \circ L \circ \phi_{\Delta_0, L^{-1}(\Delta_1)}(x) \\ \text{belongs to } \mathcal{U}_S(\Delta_t, L^{-1}(\Delta_{t+1})), \forall 1 \le t \le r-1\}, \\ \text{and } V_i = L \circ \phi_{\Delta_{i-1}, L^{-1}(\Delta_i)}(V_{i-1}) \text{ for all } 1 \le i < r. $$

Therefore, the number of valid inputs of an $r$-round plateau characteristic of the type analyzed in Prop. 1, $2^{d_r}$ ($d_r$ is the dimension of the subspaces in Coro. 1) is a decreasing sequence satisfying $d_r \ge 1$ since the characteristic is valid. The usual situation is that this sequence decreases when $r$ increases and $d_r$ becomes constant and equal to 1 after a reasonable number of rounds, and Coro. 1 becomes trivial. It is worth noting that, in some particular cases, the minimal number of valid inputs for a valid plateau characteristic may be equal to $2^{d_{min}}$ with $d_{min} > 1$, as shown in [CF25, App. C].

## 2.4 Plateau Characteristics and Invariant Subspaces

We now show that the situation, where the sequence $(d_r)_{r \ge 0}$ converges to a constant that exceeds $d_{min}$, especially occurs when the linear layer of the cipher satisfies a particular property. This property is described in the following lemma that will be extensively used in the paper, since it highly influences the behaviour of the previously analyzed differential characteristics.

**Lemma 3.** Let $L: (\mathbb{F}_{2^s})^m \to (\mathbb{F}_{2^s})^m$ be an $\mathbb{F}_{2^s}$-linear mapping defined by $M \in \mathcal{M}_m(\mathbb{F}_{2^s})$. Then, $L$ is said to satisfy Property (P) if one of the following equivalent conditions holds:

- all entries of $M$ are in $\{0, 1\}$ and all rows of $M$ have an odd Hamming weight.

- For any additive subgroup $E$ of $\mathbb{F}_{2^s}$, $L(E^m) = E^m$ and for any $x \in \mathbb{F}_{2^s}$, $L(x^{\times m}) = x^{\times m}$.

where $x^{\times m}$ denotes<fnref n="1" /> the element $(x, x, \dots, x)$ in $\mathbb{F}_{2^s}^m$.

<footnote n="1">¹ In order to avoid confusion with exponentiation $x^u$ in the field $\mathbb{F}_{2^s}$.</footnote>
**Proof.** Let $M \in \mathcal{M}_m(\mathbb{F}_{2^s})$ be a binary matrix such that all its rows have an odd Hamming weight and $x \in \mathbb{F}_{2^s}$. Then it is trivial that $M x^{\times m} = x^{\times m}$. Moreover, let $E$ be an additive subgroup of $\mathbb{F}_{2^s}$, $b \in E$, and let $e_i$ denote the $i$-th vector of the canonical basis of $(\mathbb{F}_2)^m$. Then, for all $1 \le i \le m$, $M(\text{be}_i) = b(\text{Me}_i) \in E^m$. Therefore, $L(E^m) \subset E^m$ and since $L$ is bijective, $L(E^m) = E^m$.

Conversely, suppose that for any additive subgroup $E$ of $\mathbb{F}_{2^s}$, $L(E^m) = E^m$ and for all $x \in \mathbb{F}_{2^s}$, $L(x^{\times m}) = x^{\times m}$. If there exist $1 \le i, j \le m$ such that $M_{i,j} \notin \{0, 1\}$, then $(\text{Me}_j)_i = M_{i,j} \notin \{0, 1\}$. Then, $L(\mathbb{F}_2^m) \subsetneq \mathbb{F}_2^m$, which contradicts the hypothesis on $L$. Therefore, all $M_{i,j}$ are in $\{0, 1\}$. Moreover,

$$ (M x^{\times m})_i = \left( \sum_{j=1}^{m} M_{i,j} \right) x = \begin{cases} 0 & \text{if } w_H(M[i]) \text{ is even} \\ x & \text{otherwise,} \end{cases} $$

where $M[i]$ denotes the $i$-th row of $M$. It implies that all $M[i]$ have an odd Hamming weight. $\square$

The linear layers in MIDORI [BBI$^{+}$15], SCREAM, iSCREAM [GLS$^{+}$14], PRINCE [BCG$^{+}$12] or MANTIS [BJK$^{+}$16] satisfy Property ($\mathcal{P}$). The following lemma provides the expression of the images by such linear layers of the elements in affine subspaces of the form $\{a, b\}^m$.

**Lemma 4.** Let $\{a, b\} \subset \mathbb{F}_2^s$ and $A \in \{a, b\}^m$. Let $L : (\mathbb{F}_{2^s})^m \to (\mathbb{F}_{2^s})^m$ be an $\mathbb{F}_{2^s}$-linear mapping satisfying (P). Then, $L(A) \in \{a, b\}^m$, and for all $x \in \{a, b\}$,

$$ L(\mathbf{1}_{A_j=x})_{1 \le j \le m} = (\mathbf{1}_{L(A)_j=x})_{1 \le j \le m}, $$

where $\mathbf{1}_{y=x} := 1$ if $y = x$ and 0 otherwise.

**Proof.** The fact that $\{a, b\}^m$ is invariant under $L$ comes from Lemma 3 using that $\{a, b\}^m = a^{\times m} + \langle a + b \rangle^m$. Now, let $M$ be the matrix such that $L(x) = Mx$. Let $1 \le \ell \le m$. Let us define $I_\ell := \{j \in [1, m] \mid M_{\ell, j} = 1\}$. Then, for all $x \in \{a, b\}$,

$$ [L(\mathbf{1}_{A_j=x})_{1 \le j \le m}]_{\ell} = \sum_{j \in I_{\ell}} \mathbf{1}_{A_j=x} \in \{0, 1\}. $$

By Lemma 3, $I_\ell$ is odd, implying

$$ [L(\mathbf{1}_{A_j=x})_{1 \le j \le m}]_{\ell} = 1 \iff \#\{j \in I_{\ell} \mid A_j = x\} \text{ is odd} \iff [L(A)]_{\ell} = x. $$

$\square$

The following proposition now exhibits some differential characteristics for which the number of valid inputs does not decrease with the number of rounds and is strictly larger than 2.

**Proposition 2.** Let us consider an SPN whose linear layer $L$ satisfies Property (P). Let $(a, b)$ be a super-planar differential for $S$ with DDT$(a, b) = 2^\ell$ such
that XDDT<sub>S</sub>(a, b) = XDDT<sub>S</sub>(b, a). Then, for all r ≥ 2 and all Δ<sub>0</sub> ∈ {a, b}<sup>m</sup>, there exist a differential characteristic (Δ<sub>0</sub>, Δ<sub>1</sub>, ..., Δ<sub>r</sub>) and an affine key space K ⊂ F<sub>2</sub><sup>sm(r-1)</sup> of dimension m(ℓr - dim(χ<sub>r</sub>)) such that, for any K ∈ K,

$$
\mathrm{DP}[K](\Delta_0, \dots, \Delta_r) = 2^{-m(s-\dim(\chi_r))}
$$

where $\chi_r := \{x \in V_S(a, b) \mid \forall 0 \le i \le r-2, \phi_{a,b}^i(x) \in U_S(a, b)\}$. Moreover, for any $K \in \mathcal{K}$, the set of valid inputs for $(\Delta_0, \dots, \Delta_r)$ is a coset of $(\phi_{a,b}^{-1}(\chi_r))^m$.

In particular, when $U_S(a, b) = V_S(a, b)$, we have $\mathcal{K} = (x_0^{a,b} + y_0^{a,b} + U_S(a, b))^{m(r-1)}$ and, for any weak key, the set of valid inputs equals $XDDT_S(a, b)^m$ and is an invariant subspace for the cipher.

Proof. The differences Δ<sub>t</sub>, for 1 ≤ t ≤ r, are successively determined from Δ<sub>0</sub>
as follows. For any Δ<sub>t</sub> ∈ {a, b}<sup>m</sup>, we choose Δ<sub>t+1</sub> such that, for all 1 ≤ j ≤
m, L<sup>-1</sup>(Δ<sub>t+1</sub>)[j] ∈ {a, b} and satisfies Δ<sub>t</sub>[j] = L<sup>-1</sup>(Δ<sub>t+1</sub>)[j] + a + b. Since
L<sup>-1</sup>(Δ<sub>t+1</sub>) ∈ {a, b}<sup>m</sup> and L satisfies (P), Lemma 4 implies that Δ<sub>t+1</sub> ∈ {a, b}<sup>m</sup>.
Since XDDT<sub>S</sub>(a, b) = XDDT<sub>S</sub>(b, a), (b, a) is also super-planar and we have
U<sub>S</sub>(a, b) = U<sub>S</sub>(b, a) := U<sub>S</sub>, V<sub>S</sub>(a, b) = V<sub>S</sub>(b, a) := V<sub>S</sub>, φ<sub>a,b</sub> = φ<sub>b,a</sub> := φ
and Z<sub>S</sub>(a, b) = Z<sub>S</sub>(b, a) := Z<sub>S</sub>. We can also choose the offsets such that
x<sub>0</sub><sup>a,b</sup> = x<sub>0</sub><sup>b,a</sup> := x<sub>0</sub> and thus y<sub>0</sub><sup>a,b</sup> = y<sub>0</sub><sup>b,a</sup> := y<sub>0</sub>. Therefore, we deduce from The-
orem 1 that (Δ<sub>0</sub>, ..., Δ<sub>r</sub>) is a valid characteristic for K := (K<sub>t</sub>)<sub>1≤t≤r-1</sub> if and
only if K ∈ w<sub>0</sub> + W<sub>r-1</sub> where

$$
w_0 := (x_0^{\times m} + L(y_0^{\times m}))^{\times r-1} = (x_0 + y_0)^{\times m(r-1)}
$$

$$
\begin{align*}
\text{and } W_{r-1} &:= [L(V_S^m) \times \{0\}^{sm(r-2)}] + \sum_{t=1}^{r-2} [\{0\}^{sm(t-1)} \times (I \times L)(Z_S^m) \times \{0\}^{sm(r-2-t)}] \\
&\quad + [\{0\}^{sm(r-2)} \times U_S^m] \\
&= (\Omega_{r-1})^m,
\end{align*}
$$

$$
\text{with } \Omega_{r-1} := (V_S \times \{0\}^{s(r-2)}) + \sum_{t=1}^{r-2} (\{0\}^{s(t-1)} \times Z_S \times \{0\}^{s(r-2-t)}) + (\{0\}^{s(r-2)} \times U_S).
$$

Therefore, $\mathcal{K} = (x_0 + y_0)^{\times m(r-1)} + \Omega_{r-1}^m$ and, when $(K_t)_{1\le t\le r-1} \in \mathcal{K}$, we have

$$
\mathrm{DP}[K](\Delta_0 \dots \Delta_r) = 2^{-ms-\dim W_{r-1}} \prod_{t=0}^{r-1} (\mathrm{DDT}_S(a,b))^m = 2^{m(\ell r - s - \dim \Omega_{r-1})} \quad (2)
$$

By grouping spaces together, we then deduce the form of Ω<sub>r-1</sub> depending on
the parity of r:

$$
\Omega_{2t-1} = V_S Z_S^{t-1} + Z_S^{t-1} U_S
$$

$$
\Omega_{2t} = V_S Z_S^{t-1} U_S + Z_S^t
$$
for all $t \ge 1$. It follows that

$$ \dim(\Omega_{2t-1}) = \dim(\mathbf{V}_S Z_S^{t-1}) + \dim(Z_S^{t-1}U_S) - \dim((\mathbf{V}_S Z_S^{t-1}) \cap (Z_S^{t-1}U_S)) \\ = 2t\ell - \dim((\mathbf{V}_S Z_S^{t-1}) \cap (Z_S^{t-1}U_S)). $$

Similarly, $\dim(\Omega_{2t}) = (2t+1)\ell - \dim((\mathbf{V}_S Z_S^{t-1}U_S) \cap Z_S^t)$. Let us now prove that

$$ (\mathbf{V}_S Z_S^{t-1}) \cap (Z_S^{t-1}U_S) = \{(\phi^i(x))_{0 \le i \le 2t-2} \mid x \in \chi_{2t}\} = (\mathbf{V}_S Z_S^{t-1}U_S) \cap Z_S^t. $$

We will prove the first equality for $r = 2t$ by double inclusion. By definition,

$$ Z_S = \{(x, \phi_{a,b}(x)) \mid x \in U_S\} \subset U_S \times V_S. $$

Let $x \in \chi_{2t}$. By definition, $\phi^0(x) = x \in V_S$. The previous remark leads to $(\phi^i(x))_{1 \le i \le 2t-2} \in Z_S^{t-1}$. Similarly, $(\phi^i(x))_{0 \le i \le 2t-3} \in Z_S^{t-1}$ and $\phi^{2t-2}(x) = \phi^{r-2}(x) \in U_S$ by definition of $\chi_{2t}$. Therefore,

$$ (\phi^i(x))_{0 \le i \le 2t-2} \in (\mathbf{V}_S Z_S^{t-1}) \cap (Z_S^{t-1}U_S). $$

Conversely, let $x := (x_0, \dots, x_{2t-2}) \in (\mathbf{V}_S Z_S^{t-1}) \cap (Z_S^{t-1}U_S)$. Then $x_0 \in U_S \cap V_S$. Moreover, if for some $j \in [0, 2t-3]$, $x_{j+1} \ne \phi(x_j)$, then $(x_j, x_{j+1}) \notin Z_S$. If $j$ is even, $x \notin Z_S^{t-1}U_S$, and if $j$ is odd $x \notin \mathbf{V}_S Z_S^{t-1}$. Therefore, $x = (\phi^j(x_0))_{0 \le j \le 2t-2}$ and $x_0 \in \chi_{2t}$. This achieves the proof of the first equality in the case $r$ even, the case $r$ odd is proved similarly. Formula (2) then leads to

$$ \mathrm{DP}[K](\Delta_0, \dots, \Delta_r) = 2^{\ell mr-ms-m(r\ell-\dim \chi_r)} = 2^{-m(s-\dim \chi_r)}. $$

Now, from Prop. 1, for any $K \in \mathcal{K}$, the set of valid inputs for the characteristic is equal to $\mathbf{S}^{-1}(\tilde{X}_r)$ where $\tilde{X}_r$ is a coset of $X_r := \{x \in V_S^m \mid ((L \circ \phi)^i \circ L)(x) \in U_S^m, \forall 0 \le i \le r-2\}$. Using that $L(U_S^m) = U_S^m$, we deduce that $X_r = \chi_r^m$. Since, $(a, b)$ is super-planar, we have that $\mathbf{S}^{-1}(\tilde{X}_r)$ is a coset of $(\phi^{-1}(\chi_r))^m$ which proves the result in the general case.

Now, when $U_S = V_S$, we have $\chi_r = U_S \cap V_S = U_S = V_S$ which has dimension $\ell$ and is invariant under $\phi$. Hence, the set of valid inputs is a coset of $U_S^m$ which is included in $\mathrm{XDDT}_S(a, b)^m$. Therefore, the set of valid inputs is exactly $\mathrm{XDDT}_S(a, b)^m$. Furthermore, $\Omega_{r-1} = U_S^{r-1}$ and $\mathcal{K} = (x_0+y_0)^{\times m(r-1)} + U_S^{m(r-1)}$. Then, $(L \circ \mathbf{S})(\mathrm{XDDT}_S(a, b)^m) = y_0^{\times m} + U_S^m$ and $\mathrm{Add}_{K_t}(y_0^{\times m} + U_S(a, b)^m) = x_0^{\times m} + U_S^m = \mathrm{XDDT}_S(a, b)^m$ which proves that $\mathrm{XDDT}_S(a, b)^m$ is invariant under the round-function $\mathrm{Add}_{K_t} \circ \mathcal{R}$ if $K_t \in (x_0 + y_0)^{\times m} + U_S^m$. Note that, if $K_t \notin (x_0 + y_0)^{\times m} + U_S^m$ then $\mathrm{Add}_{K_t}(y_0^{\times m} + U_S^m) = c_0 + U_S^m$ for some $c_0 \notin x_0^{\times m} + U_S^m$, and the subspace does not propagate. $\square$

The simplest case in which the previous proposition applies is when there exists a super-planar differential for $S$ with the same input and output differences, $a = b$ in Prop. 2. Then, $\mathrm{XDDT}_S(a, b) = \mathrm{XDDT}_S(b, a)$ and $0$ and $a$ are included in both $U_S(a, a)$ and $V_S(a, a)$, and therefore in $\chi_r$ because $\phi_{a,a}(a) = a$. It follows that $\dim \chi_r \ge 1$ and that the iterative characteristic $(a^{\times m}, \dots, a^{\times m})$ is plateau with $\mathrm{DP}[K](a^{\times m}, \dots, a^{\times m}) \ge 2^{-m(s-1)}$ for $K \in \mathcal{K}$.
**The case of Midori64.** The invariant subspaces in MIDORI64 exhibited by Guo et al. [GJN+16] for a certain set of weak expanded-keys actually correspond to the valid inputs of some iterative differential characteristic of the form $(a^{\times m}, \dots, a^{\times m})$ whose probability is independent of the number of rounds. Let us consider two such examples:

- For $a = 0xf$, the Sbox of MIDORI64 satisfies

$$XDDT_S(0xf, 0xf) = YDDT_S(0xf, 0xf) = 0x2 + \langle 0xa, 0xf \rangle.$$

The hypotheses of Prop. 2 are then satisfied. Moreover, for any $r$, $U_S(0xf, 0xf) = V_S(0xf, 0xf) = \chi_r = \langle 0xa, 0xf \rangle$ and has dimension 2. It follows that the expanded key $K$ is a weak key if all round keys belong to

$$(x_0^{0xf,0xf} + y_0^{0xf,0xf} + \langle 0xa, 0xf \rangle)^{16} = \langle 0xa, 0xf \rangle^{16}.$$

For these weak expanded keys, the characteristic $(0xf^{\times 16}, \dots, 0xf^{\times 16})$ has probability $2^{-2m} = 2^{-32}$.

- For $a = 0x1$, we have $XDDT_S(0x1, 0x1) = YDDT_S(0x1, 0x1) = 0x8 + \langle 0x1 \rangle$. Then, $\chi_r = \langle 0x1 \rangle$ for any $r$, and if each round key belongs to $\chi_r^m$, the characteristic $(0x1^{\times 16}, \dots, 0x1^{\times 16})$ has probability $2^{-3m} = 2^{-48}$.

As observed in [GJN+16], the space formed by the weak expanded-keys for the second characteristic is compatible with the key schedule proposed by the designers of MIDORI64 while this is not the case for the first iterative characteristic. It is worth noting that we also derive that these characteristics are plateau, which means that their probability is equal to zero when the expanded key does not belong to the weak-key space. This implies for instance that, because of MIDORI64 key schedule, the characteristic $(0xf^{\times 16}, \dots, 0xf^{\times 16})$ has probability 0 for all keys in $\mathbb{F}_2^{128}$ when we consider MIDORI64 with its key schedule.

**The case of iScream.** Another important remark is that Prop. 2 is not reduced to characteristics of the form $(\Delta, \Delta, \dots, \Delta)$. In [LMR15], the authors present different types of invariant-subspace attacks. In particular, they exhibit six affine subspaces of dimension 3 invariant under the 8-bit Sbox of iSCREAM. Four of them are actually equal to $XDDT_S(a, b)$ for some super-planar differentials $(a, b)$, and for these pairs we have $XDDT_S(a, b) = XDDT_S(b, a)$. Since the Sbox of iSCREAM is involutive, we have $U_S(b, a) = V_S(a, b)$. Moreover, the linear layer of iSCREAM satisfies Property (P). Thus, Prop. 2 applies and if the round keys all belong to the same affine subspace of dimension $\ell \times m = 48$, $XDDT_S(a, b)^{16}$ is an invariant subspace for the whole cipher, as pointed out by [LMR15]. In terms of differential characteristic, it corresponds to plateau characteristics $(\Delta_0, \dots, \Delta_r)$ with $\Delta_t \in \{a, b\}^m$ such that $\text{DP}[K](\Delta_0, \dots, \Delta_r) = 2^{-m(s-3)} = 2^{-80}$.

The existence of such differential characteristics is rather rare and can be checked by searching for affine subspaces that propagate through the cipher. Moreover, the proportion of weak expanded keys is limited since it is equal to
EDP($\Delta_0, \dots, \Delta_r$)/DP[$K$]($\Delta_0, \dots, \Delta_r$) with $K \in \mathcal{K}$. However, as usual in differential cryptanalysis, the relevant quantity is not the probability of a characteristic but the probability of a differential, which may include a very large number of valid characteristics.

### 3 Fixed-Key Truncated Differentials of Constant Probability

Following [DR07], the previous section has exhibited situations where a large family of plateau characteristics exist for an arbitrary number of rounds. By definition, none of these characteristics satisfy the hypothesis of stochastic equivalence. What happens for a given differential, composed of such plateau characteristics, is then unclear. Indeed, each of the constituent characteristics is valid for a given set of weak expanded-keys, but the weak keys may be the same for the different characteristics or not. In other words, we wonder whether there is a (possibly strong) clustering effect, or not, when the key is fixed.

In this section, we focus on truncated differentials of the form $\{\alpha, \beta\}^m$, where $(\alpha, \beta)$ is a super-planar differential for the Sbox satisfying some specific property. Indeed, the truncated differentials reported by Baudrin et al. [BFL+23] for an arbitrary number of rounds of MIDORI64 have this particular form. However, all results in this section can be generalized to truncated differentials $(a, b)$ with $a, b \in \mathcal{A}$ for a larger set of differences $\mathcal{A}$. We chose to detail this generalization in Section 6 and to keep the current section as simple as possible. Indeed, the case $\mathcal{A} = \{\alpha, \beta\}$ already captures the nature of the different (and unexpected) behaviours of fixed-key truncated differentials composed of plateau characteristics.

In this section, we will focus on the differentials satisfying the following property, which holds for several practical ciphers.

**Definition 6.** A differential $(\alpha, \beta)$ for $S: \mathbb{F}_2^s \to \mathbb{F}_2^s$ with $\alpha \neq \beta$ is said to be a square differential for $S$ if it satisfies the following conditions:

1. $(\alpha, \alpha)$, $(\alpha, \beta)$, $(\beta, \alpha)$, $(\beta, \beta)$ are super-planar differentials.

2. $U_S(\alpha, \alpha) = U_S(\alpha, \beta) := U_S(\alpha)$ and $U_S(\beta, \alpha) = U_S(\beta, \beta) := U_S(\beta)$.

3. $U_S(\alpha) + \langle x_0^{\alpha, \beta} + x_0^{\alpha, \alpha} \rangle = U_S(\beta) + \langle x_0^{\beta, \beta} + x_0^{\beta, \alpha} \rangle := E$

4. $\forall (x, y) \in \{\alpha, \beta\}^2, V_S(x, y) \subset E$

If, additionally, $\forall (x, y) \in \{\alpha, \beta\}^2, y_0^{x,y} + x_0^{y,\alpha} \in (y_0^{\alpha,\alpha} + x_0^{\alpha,\alpha}) + E$ then $(\alpha, \beta)$ is said to be a perfect square differential.

These conditions might seem very restrictive, but hold for several practical ciphers: App. B in [CF25] provides examples of square differentials for some known Sboxes. Moreover, we will see later that, in many cases, some of the requirements are consequences of some others. For example, if $S$ is an involution, all square differentials are perfect square differentials. Indeed, in that case $y_0^{x,y} \in$
$x_0^{y,x} + U_S(y)$. It follows that

$$y_0^{x,y} + x_0^{y,\alpha} \in (x_0^{y,x} + x_0^{y,\alpha}) + U_S(y) = \begin{cases} U_S(y) \subset E & \text{if } x = \alpha \\ x_0^{y,\beta} + x_0^{y,\alpha} + U_S(y) = E & \text{if } x = \beta \end{cases}$$

by definition of E.

The following three properties of square differentials will be useful for proving the main result.

**Lemma 5.** Let $(\alpha, \beta)$ a super-planar differential for $S$ such that $U_S(\alpha, \beta) = U_S(\alpha, \alpha) := U_S(\alpha)$. Then $U_S(\alpha)$ and $\langle x_0^{\alpha,\beta} + x_0^{\alpha,\alpha} \rangle$ are in direct sum, implying that $\dim E = \dim U_S(\alpha) + 1$.

*Proof.* If $x_0^{\alpha,\beta} + x_0^{\alpha,\alpha} \in U_S(\alpha)$ then $x_0^{\alpha,\alpha} \in x_0^{\alpha,\beta} + U_S(\alpha) = XDDT_S(\alpha, \beta)$. This is impossible since $XDDT_S(\alpha, \alpha)$ and $XDDT_S(\alpha, \beta)$ are disjoint. $\square$

**Lemma 6.** Let $(\alpha, \beta)$ be a square differential for $S$. Then, for all $x, y \in \{\alpha, \beta\}$,

$$Z_S(x, y) + (\{0\}^s \times E) = U_S(x, y) \times E. \qquad (3)$$

*Proof.* Any element in $Z_S(x, y) + (\{0\}^s \times E)$ can be written $(\theta, \phi_{x,y}(\theta) + e)$ for some $\theta \in U_S(x, y)$ and $e \in E$. We deduce that it belongs to $U_S \times E$ if and only if $\{\phi_{x,y}(\theta) | \theta \in U_S(x, y)\} = V_S(x, y)$ is included in $E$, which corresponds to Condition 4 in Def. 6. Moreover, the two linear spaces have the same dimension, $\dim U_S(x, y) + \dim E$, implying that there are equal if and only if $V_S(x, y) \subset E$. $\square$

**Lemma 7.** Let us consider an SPN whose linear layer $L$ satisfies Property (P). Let $(\alpha, \beta)$ be a square differential for $S$ and $(\Delta_0, \dots, \Delta_r)$ be a $r$-round characteristic with $\Delta_t \in \{\alpha, \beta\}^m$ for all $0 \le t \le r$. Then, the linear part of the subspace formed by the weak expanded keys, $W_{r-1}(\Delta_0, \dots, \Delta_r)$, is independent of $\Delta_r$.

*Proof.* The only subspace in the definition of $W_{r-1}$ in Theorem 1 that may depend on $\Delta_r$ is $U_S(\Delta_{r-1}, L^{-1}(\Delta_r))$. But Condition 2 in Definition 6 implies that $U_S(\Delta_{r-1}, L^{-1}(\Delta_r)) = U_S(\Delta_{r-1})$. $\square$

The following lemma now shows that, in the particular case of square differentials, there is a relation between the linear part of the weak-key space $W_r$ for which an $(r+1)$-round characteristic $(\Delta_0, \dots, \Delta_r, \Delta_{r+1})$ is valid, and the linear part of the weak-key space $W_{r-1}$ for $(\Delta_0, \dots, \Delta_r)$.

**Lemma 8.** Let us consider an SPN whose linear layer $L$ satisfies Property (P). Let $(\alpha, \beta)$ be a square differential for $S$ and $(\Delta_0, \dots, \Delta_{r+1})$ be a $(r+1)$-round characteristic with $\Delta_t \in \{\alpha, \beta\}^m$ for all $0 \le t \le r+1$. Then, if $r \ge 2$,

$$\left( \{0\}^{sm(r-1)} \times \prod_{j=1}^{m} \langle x_0^{\Delta_r[j],\alpha} + x_0^{\Delta_r[j],\beta} \rangle \right) + W_r = W_{r-1} \times E^m .$$
Moreover, for a two-round characteristic,

$$ \prod_{j=1}^{m} \langle x_{0}^{\Delta_{1}[j],\alpha} + x_{0}^{\Delta_{1}[j],\beta} \rangle + W_{1} = E^{m} $$

*Proof.* On the one hand, we have by Condition 3 in Def. 6

$$ U_{\mathcal{S}}(\Delta_1) + \prod_{j=1}^{m} \langle x_0^{\Delta_1[j],\alpha} + x_0^{\Delta_1[j],\beta} \rangle = E^m. $$

From Theorem 1, we know that

$$ W_1 = L(\mathcal{V}_{\mathcal{S}}(\Delta_0, L^{-1}(\Delta_1))) + U_{\mathcal{S}}(\Delta_1, L^{-1}(\Delta_2)) \subset E^m + U_{\mathcal{S}}(\Delta_1), $$

because of Condition 4. in Definition 6. It follows that

$$ \prod_{j=1}^{m} \langle x_{0}^{\Delta_{1}[j],\alpha} + x_{0}^{\Delta_{1}[j],\beta} \rangle + W_{1} \subset E^{m} $$

and we also have that

$$ E^m \subset \prod_{j=1}^{m} \langle x_0^{\Delta_1[j],\alpha} + x_0^{\Delta_1[j],\beta} \rangle + W_1 $$

since $U_{\mathcal{S}}(\Delta_1) \subset W_1$. This proves the result in the case $r=1$.

Now, for $r \ge 2$, since $L(E^m) = E^m$,

$$ \begin{aligned} \mathcal{E} &= [(I \times L)(\mathcal{Z}_{\mathcal{S}}(\Delta_{r-1}, L^{-1}(\Delta_r)))] + [\{0\}^{sm} \times E^m] \\ &= (I \times L)(\mathcal{Z}_{\mathcal{S}}(\Delta_{r-1}, L^{-1}(\Delta_r)) + \{0\}^{sm} \times E^m) \\ &= (I \times L)(U_{\mathcal{S}}(\Delta_{r-1}) \times E^m) = L(U_{\mathcal{S}}(\Delta_{r-1})) \times E^m, \end{aligned} $$

where the last equality comes from Lemma 6. Let $W'_{r-1}$ denote the sum of the first $(r-1)$ subspaces defining $W_{r-1}$ in Th. 1, i.e.,

$$ W_{r-1} = W'_{r-1} + (\{0\}^{sm(r-2)} \times U_{\mathcal{S}}(\Delta_{r-1})). $$

Then, we have

$$ \begin{aligned} \mathcal{E}' &= \left( \{0\}^{sm(r-1)} \times \prod_{j=1}^{m} \langle x_0^{\Delta_r[j],\alpha} + x_0^{\Delta_r[j],\beta} \rangle \right) + W_r \\ &= (W'_{r-1} \times \{0\}^{sm}) + \{0\}^{sm(r-2)} \times [(I \times L)(\mathcal{Z}_{\mathcal{S}}(\Delta_{r-1}, L^{-1}(\Delta_r)))] \\ &\quad + [\{0\}^{sm(r-1)} \times E^m] \\ &= (W'_{r-1} \times \{0\}^{sm}) + (U_{\mathcal{S}}(\Delta_{r-1}) \times E^m) = W_{r-1} \times E^m. \end{aligned} $$

□
The following result considers an SPN with (r + 1) rounds and a given key. It determines the number of (r + 1)-round characteristics with all differences in {$a, b$}^m that are valid for this specific key and share the same first r differences.

**Proposition 3.** Let us consider an SPN with (r + 1) rounds, r ≥ 1, whose linear layer L satisfies Property (P). Let (α, β) a square differential for S with DDT_S(α, β) = 2^l. Let K = (K_1, ..., K_r) be an expanded key and (Δ_0, ..., Δ_r) with all Δ_t ∈ {α, β}^m be an r-round characteristic which is valid for the first (r - 1) round keys. Then,

$$ \Gamma_r := \{ \Delta_{r+1} \in \{\alpha, \beta\}^m \mid (\Delta_0, \dots, \Delta_r, \Delta_{r+1}) \text{ is a valid characteristic for } K \} $$

is an affine subspace. It is non-empty if and only if

$$ L^{-1}(K_r)[j] \in (y_0^{\Delta_{r-1}[j], L^{-1}(\Delta_r)[j]} + x_0^{L^{-1}(\Delta_r)[j], \alpha}) + E, \forall 1 \le j \le m. $$

In that case, it has dimension

$$ \dim \Gamma_r = \begin{cases} \dim(W_r) - \dim(W_{r-1}) - \ell m & \text{if } r \ge 2 \\ \dim(W_1) - \ell m & \text{if } r = 1 \end{cases} \quad (4) $$

*Proof.* By Th. 1, (Δ₀, ..., Δₖ, Δₖ₊₁), is valid for K if and only if

$$ (0, \dots, 0, x_0^{\Delta_r, L^{-1}(\Delta_{r+1})}) \in K + \tilde{w}_0 + W_r $$

$$ \text{where } \tilde{w}_0[t] := \begin{cases} x_0^{\Delta_t, L^{-1}(\Delta_{t+1})} + L(y_0^{\Delta_{t-1}, L^{-1}(\Delta_t)}) & \text{if } 1 \le t \le r-1 \\ L(y_0^{\Delta_{r-1}, L^{-1}(\Delta_r)}) & \text{if } t=r. \end{cases} $$

Moreover, $K + \tilde{w}_0 + W_r$ does not depend on $\Delta_{r+1}$ by Lemma 7. Let

$$ \psi_{\Delta_r} : \{\alpha, \beta\}^m \to \mathbb{F}_2^{sm} \\ B \mapsto x_0^{\Delta_r, B}. $$

Then, the values of $\Delta_{r+1}$ in $\Gamma_r$ correspond to the intersection between $(\{0\}^{sm(r-1)} \times \text{Im}(\psi_{\Delta_r}))$ and $K + \tilde{w}_0 + W_r$. This intersection does not depend on the choice of the offset $x_0^{\Delta_r, B}$ since any other offset $z_0^{\Delta_r, B}$ belongs to $x_0^{\Delta_r, B} + U_S(\Delta_r)$ and then $(0, \dots, 0, z_0^{\Delta_r, B}) + (0, \dots, 0, x_0^{\Delta_r, B})$ lies in $W_r$.

We have

$$ \text{Im}(\psi_{\Delta_r}) = \prod_{j=1}^{m} \{x_0^{\Delta_r[j], \alpha}, x_0^{\Delta_r[j], \beta}\}, $$

which is an affine subspace whose linear part is $\prod_{j=1}^{m} \langle x_0^{\Delta_r[j], \alpha} + x_0^{\Delta_r[j], \beta} \rangle$. Therefore, $\psi_{\Delta_r}$ is an isomorphism from $\alpha^{\times m} + \langle \alpha + \beta \rangle^m$ to $\text{Im}(\psi_{\Delta_r})$. Then:

$$ \Gamma_r = L \circ \psi_{\Delta_r}^{-1} \{ \pi_r \left( \left( \{0\}^{sm(r-1)} \times \text{Im}(\psi_{\Delta_r}) \right) \cap (K + \tilde{w}_0 + W_r) \right) \} \quad (5) $$
where $\pi_r$ denotes the last coordinate of an element in $(\mathbb{F}_2^{sm})^r$. Since $\psi_{\Delta_r}$ is an isomorphism, $\Gamma_r$ is an affine subspace and $\Gamma_r$ is non-empty if and only if

$$ (\{0\}^{sm(r-1)} \times \mathrm{Im}(\psi_{\Delta_r})) \cap (K + \widetilde{w}_0 + W_r) \neq \emptyset, $$

or equivalently,

$$ K + \widetilde{w}_0 \in (\{0\}^{sm(r-1)} \times \mathrm{Im}(\psi_{\Delta_r})) + W_r $$

Choosing $Q := (0, \dots, 0, x_0^{\Delta_r, \alpha^{\times m}})$ as an offset of $(\{0\}^{sm(r-1)} \times \mathrm{Im}(\psi_{\Delta_r}))$, the above condition is equivalent to

$$ K + \widetilde{w}_0 + Q \in \left( \{0\}^{sm(r-1)} \times \prod_{j=1}^{m} \langle x_0^{\Delta_r[j], \alpha} + x_0^{\Delta_r[j], \beta} \rangle \right) + W_r = W_{r-1} \times E^m $$

by Lemma 8. By assumption, $(\Delta_0, \dots, \Delta_r)$ is a valid characteristic for $(K_1, \dots, K_{r-1})$, which means that the first $(r-1)$ coordinates of $(K+\widetilde{w}_0+Q)$ satisfy the previous condition. It follows that the condition is equivalent to

$$ K_r \in L(y_0^{\Delta_{r-1}, L^{-1}(\Delta_r)}) + x_0^{\Delta_r, \alpha^{\times m}} + E^m. $$

Applying $L^{-1}$, it is also equivalent to

$$ L^{-1}(K_r) \in y_0^{\Delta_{r-1}, L^{-1}(\Delta_r)} + L^{-1}(x_0^{\Delta_r, \alpha^{\times m}}) + E^m. $$

By Lemma 4, $L^{-1}(x_0^{\Delta_r, \alpha^{\times m}}) = x_0^{L^{-1}(\Delta_r), \alpha^{\times m}}$. Looking at each coordinate, the condition then corresponds to

$$ L^{-1}(K_r)[j] \in (y_0^{\Delta_{r-1}[j], L^{-1}(\Delta_r)[j]} + x_0^{L^{-1}(\Delta_r)[j], \alpha}) + E, \forall 1 \le j \le m. $$

When this condition holds, using again Lemma 8, we have when $r \ge 2$

$$
\begin{align*}
\dim(\Gamma_r) &= \dim \left( \left( \{0\}^{sm(r-1)} \times \prod_{j=1}^{m} \langle x_0^{\Delta_r[j], \alpha} + x_0^{\Delta_r[j], \beta} \rangle \right) \cap W_r \right) \\
&= m + \dim(W_r) - \dim \left( \left( \{0\}^{sm(r-1)} \times \prod_{j=1}^{m} \langle x_0^{\Delta_r[j], \alpha} + x_0^{\Delta_r[j], \beta} \rangle \right) + W_r \right) \\
&= m + \dim(W_r) - \dim(W_{r-1}) - m \dim(E) \\
&= m(1 - \dim(E)) + \dim(W_r) - \dim(W_{r-1}) = -m\ell + \dim(W_r) - \dim(W_{r-1})
\end{align*}
$$

where the last equality is derived from Lemma 5. For $r = 1$, we use the expression of $W_1$ given in Lemma 8 and get

$$
\begin{align*}
\dim(\Gamma_1) &= m + \dim(W_1) - \dim \left( \prod_{j=1}^{m} \langle x_0^{\Delta_1[j], \alpha} + x_0^{\Delta_1[j], \beta} \rangle + W_1 \right) \\
&= m + \dim(W_1) - m \dim(E) = -m\ell + \dim(W_1).
\end{align*}
$$

□
Therefore, the previous proposition shows that, starting from a given r-round characteristic $(\Delta_0, \dots, \Delta_r)$ with all $\Delta_t \in \{\alpha, \beta\}^m$, only two situations can occur, depending on whether the last round-key $K_r$ satisfies a condition involving $\Delta_{r-1}$ and $\Delta_r$. Either this characteristic cannot be extended to a longer characteristic with differences in $\{\alpha, \beta\}^m$, or it can be extended to many such $(r+1)$-round characteristics and in that case the set of possible extensions forms an affine subspace of $\{a, b\}^m$.

Now, we show that, in the particular case of a perfect square differential, the condition on $K_r$ required for extending $(\Delta_0, \dots, \Delta_r)$ one round further does not depend on the characteristic. Therefore, for a given expanded key, either there exists no valid r-round characteristic with differences in $\{\alpha, \beta\}^m$, or there exist many of them since any valid characteristic $(\Delta_0, \dots, \Delta_r)$ can be extended.

**Corollary 2.** Let us consider an SPN whose linear layer $L$ satisfies Property $(\mathcal{P})$. Let $(\alpha, \beta)$ a perfect square differential for $S$ with $\mathrm{DDT}_S(\alpha, \beta) = 2^\ell$. Then, for any expanded key $K$ in $(x_0^{\alpha, \alpha} + y_0^{\alpha, \alpha} + E)^{mr}$ and for any $\Delta_0 \in \{\alpha, \beta\}^m$,

$$ \sum_{\Delta_1, \dots, \Delta_r \in \{\alpha, \beta\}^m} \mathrm{DP}[K](\Delta_0, \dots, \Delta_r) = 2^{-m(s-\ell-1)}. $$

*Proof.* Let $N_r$, for $r \ge 1$, be the number of inputs satisfying an r-round characteristic with differences in $\{\alpha, \beta\}^m$ and starting from $\Delta_0$. We will prove that $N_r = 2^{m(\ell+1)}$ for all $r \ge 1$. First, for $r = 1$, we have

$$ N_1 = \sum_{\Delta_1 \in \{\alpha, \beta\}^m} \prod_{j=1}^{m} \mathrm{DDT}_{\mathcal{S}}(\Delta_0[j], L^{-1}(\Delta_1[j])) = \sum_{\Delta_1 \in \{\alpha, \beta\}^m} 2^{\ell m} = 2^{m(\ell+1)}. $$

Let us now define

$$ \mathcal{C}_r(K) := \{\Delta_1, \dots, \Delta_r \in \{\alpha, \beta\}^m \mid (\Delta_0, \Delta_1, \dots, \Delta_r) \text{ is valid for } K\}. $$

Using the same notation as in the previous proof, we have

$$ \mathcal{C}_{r+1}(K_1, \dots, K_r) = \mathcal{C}_r(K_1, \dots, K_{r-1}) \times \Gamma_r. $$

Since $K_r \in (x_0^{\alpha, \alpha} + y_0^{\alpha, \alpha} + E)^m$ and $L$ satisfies $(\mathcal{P})$, we have $L^{-1}(K_r) \in (x_0^{\alpha, \alpha} + y_0^{\alpha, \alpha} + E)^m$. Therefore, for all $1 \le j \le m$,

$$ L^{-1}(K_r)[j] \in y_0^{\Delta_{r-1}[j], L^{-1}(\Delta_r)[j]} + x_0^{L^{-1}(\Delta_r)[j], \alpha} + E $$

because $(\alpha, \beta)$ is a perfect square differential for $S$. Hence, by Prop. 3, $\Gamma_r \ne \emptyset$ and its dimension is given by (4). Let us denote $K' := (K_1, \dots, K_{r-1})$. Then,
using Lemma 7, we deduce that,

$$
\begin{align*}
N_{r+1} &= \sum_{\Delta_1, \dots, \Delta_{r+1} \in C_{r+1}(K', K_r)} 2^{-\dim(W_r)} \prod_{t=0}^{r} \mathrm{DDT}_{\mathcal{S}}(\Delta_t, L^{-1}(\Delta_{t+1})) \\
&= 2^{\ell m(r+1)} \sum_{\Delta_1, \dots, \Delta_{r+1} \in C_{r+1}(K', K_r)} 2^{-\dim(W_r)} \\
&= 2^{\ell m(r+1)} \sum_{\Delta_1, \dots, \Delta_r \in C_r(K')} 2^{-\dim(W_r) + \dim(\Gamma_r)} \\
&= 2^{\ell m(r+1)} \sum_{\Delta_1, \dots, \Delta_r \in C_r(K')} 2^{-\dim(W_{r-1}) - \ell m} \\
&= N_r.
\end{align*}
$$

Remark 1. While all results presented in this section assume that the linear layer of the cipher satisfies (P), requiring $L(E^m) = E^m$ and $L(\{\alpha, \beta\}^m) = \{\alpha, \beta\}^m$ would have been sufficient. However, we believe that it is unlikely to occur if $L$ does not satisfy (P).

4 Examples of Different Fixed-Key Behaviours

As an illustration of the previous results, we study the fixed-key probabilities of
truncated differentials obtained by aggregating all characteristics with differences
in a given set {α, β}^m. We start from MIDORI64 whose linear layer satisfies
Property (P) and then see how the properties of the underlying differential
(α, β) for S affect the general fixed-key behaviour of the truncated probability.

4.1 Case of a Perfect Square Differential: Midori64

We consider the same differential as in [BFL+23]: α = 0xa and β = 0xf. Then,

DDT<sub>S</sub>(0xa, 0xa) = DDT<sub>S</sub>(0xa, 0xf) = DDT<sub>S</sub>(0xf, 0xa) = DDT<sub>S</sub>(0xf, 0xf) = 4.

Moreover, (0xa, 0xf) is a square differential in the sense of Def. 6 since

$$
\begin{align*}
\mathrm{XDDT}_S(0\mathrm{xa}, 0\mathrm{xa}) &= 0\mathrm{x}3 + \langle 0\mathrm{x}7, 0\mathrm{xa} \rangle \quad \text{and} \quad \mathrm{YDDT}_S(0\mathrm{xa}, 0\mathrm{xa}) = 0\mathrm{x}3 + \langle 0\mathrm{x}7, 0\mathrm{xa} \rangle \\
\mathrm{XDDT}_S(0\mathrm{xa}, 0\mathrm{xf}) &= 0\mathrm{xc} + \langle 0\mathrm{x}7, 0\mathrm{xa} \rangle \quad \text{and} \quad \mathrm{YDDT}_S(0\mathrm{xa}, 0\mathrm{xf}) = \langle 0\mathrm{xa}, 0\mathrm{xf} \rangle \\
\mathrm{XDDT}_S(0\mathrm{xf}, 0\mathrm{xa}) &= \langle 0\mathrm{xa}, 0\mathrm{xf} \rangle \quad \text{and} \quad \mathrm{YDDT}_S(0\mathrm{xf}, 0\mathrm{xa}) = 0\mathrm{xc} + \langle 0\mathrm{x}7, 0\mathrm{xa} \rangle \\
\mathrm{XDDT}_S(0\mathrm{xf}, 0\mathrm{xf}) &= 0\mathrm{x}2 + \langle 0\mathrm{xa}, 0\mathrm{xf} \rangle \quad \text{and} \quad \mathrm{YDDT}_S(0\mathrm{xf}, 0\mathrm{xf}) = 0\mathrm{xd} + \langle 0\mathrm{xa}, 0\mathrm{xf} \rangle,
\end{align*}
$$

where the offset $y_0$ of $\mathrm{YDDT}_S$ corresponds to the image by $S$ of the offset of $\mathrm{XDDT}_S$. We can then easily check that all conditions in Def. 6 hold. Most notably,

$$
U_S(0xa) + \langle x_0^{0xa,0xf} + x_0^{0xa,0xa} \rangle = U_S(0xf) + \langle x_0^{0xf,0xf} + x_0^{0xf,0xa} \rangle = \langle 0x7, 0xa, 0xf \rangle := E.
$$

Then, according to Prop. 3, any valid *r*-round characteristic with differences in
{0xa, 0xf}^m can be extended for some weak round-keys K_r.
Now, we check that (0xa, 0xf) is also a perfect square differential. Indeed, we compute the four values $y_0^{\delta_0, \delta_1} + x_0^{\delta_1, 0xa}$ for $\delta_0, \delta_1 \in \{0xa, 0xf\}$ in the table below and check that these values belong to E. Note that the values in the table depend on the choice of $x_0^{\delta_0, \delta_1}$ for each $(\delta_0, \delta_1)$. However, their coset in E is always independent of that choice because $U_S(\alpha)$ and $U_S(\beta)$ are included in E.

<table><thead><tr><th>δ<sub>0</sub></th><th>α</th><th>β</th></tr></thead><tbody><tr><td>α</td><td>0x0</td><td>0xa</td></tr><tr><td>β</td><td>0xf</td><td>0xd</td></tr></tbody></table>

Because $(\alpha, \beta)$ is perfect, Coro. 2 applies and shows that the weak round-keys $K_r$ for which a valid r-round characteristic $(\Delta_0, \dots, \Delta_r)$ can be extended are the same for all $(\Delta_0, \dots, \Delta_r)$. This situation is depicted on Fig. 1 in the case of a reduced version of MIDORI64 with block size 16, named Column-MIDORI, which corresponds to MIDORI64 restricted to a single column. Fig. 1 represents, for a given randomly chosen weak expanded key, all 11-round valid characteristics $(\Delta_0, \Delta_1, \dots, \Delta_{11})$ with all $\Delta_t \in \{0xa, 0xf\}^4$ starting from given $\Delta_0, \Delta_1$ chosen at random in $\{0xa, 0xf\}^4$. The nodes at the t-th level in the tree, $0 \le t \le 11$, starting from the top, represent the different t-round valid characteristics with differences in $\{0xa, 0xf\}^4$. In other words, the $(t+1)$-th level is deduced from the t-th level by computing $\Gamma_t$ as in Prop. 3.

<figure><img src="image_2.png" /><figcaption>Figure1: Representation of the valid characteristics $(\Delta_0, \dots, \Delta_{11})$ with all $\Delta_t \in \{0xa, 0xf\}^4$ starting from given $\Delta_0, \Delta_1 \in \{\alpha, \beta\}^4$ for 11 rounds of Column-MIDORI, and for a random weak expanded key.</figcaption></figure>

In the generic case there are two growth regimes. On the first 5 or 6 rounds, the tree width grows a lot. But starting from Round 7, the width stays constant because each valid characteristic has at least 2 valid inputs. In the case of MIDORI64, Prop. 11 in [CF25, App. C] applies and shows that this minimum number is 4, instead of 2 in the general case.

In other words, there are exactly $2^8$ valid inputs for the single-round characteristic $(\Delta_0, \Delta_1)$. But then, these inputs are split up into the sets of valid inputs
of different 2-round characteristics ($Δ_0, Δ_1, Δ_2$). And when the set of valid inputs of a characteristic has size 4, it cannot be divided anymore. Then, in this example, for 9 rounds and more, we obtain a total of 64 characteristics, each having exactly 4 valid inputs.

There are some particular cases where the truncated differential derived from all characteristics with differences in {$0xa, 0xf$}^16 has the same probability, but corresponds to a very different configuration. Indeed, if all round keys belong to the subspace of weak round-keys equal to $⟨0xa, 0xf⟩^{16}$, then the tree of all valid characteristics starting from $Δ_0 = Δ_1 = 0xf^{×16}$ is a filiform tree. It consists of the single iterative characteristic $(0xf^{×16}, 0xf^{×16}, 0xf^{×16}, ...)$, meaning that all the $2^{32}$ elements of $XDDT(Δ_0, L^{-1}(Δ_1))$ satisfy the same entire characteristic. This situation corresponds to Prop. 2 and to the invariant subspaces exhibited in [GJN+16] as explained at the end of Section 2.4.

**With Sbox S₁.** Now, we consider a variant of MIDORI64 in which we use the Sbox $S_1$ defined in App. A. For this Sbox, $(0x4, 0xf)$ is a perfect square differential, hence the general behaviour is the same as in the case of MIDORI64, even if the Sbox is not involutive. Indeed, for any $Δ_0 ∈ \{0x4, 0xf\}^m$, the truncated differential beginning with $Δ_0$ has probability equal to $2^{-16}$ when only characteristics with intermediate differences in {$0x4, 0xf$}^m are considered. But, this cipher differs from the previous one for two reasons:

- The minimal number of valid inputs of a differential characteristic whose differences lie in {$0x4, 0xf$}^m is 2, while it was 4 in MIDORI64. This is because Prop. 11 in [CF25, App. C] does not apply.

- There is no characteristic having a high probability. Indeed, the highest probability of a characteristic whose differences lie in {$0x4, 0xf$}^m is $2^{-3m}$ whereas it was $2^{-2m}$ in MIDORI64. Invariant subspaces of dimension 32 as the ones found in [GJN+16] do not exist. This comes from the fact that for $x ∈ \{0x4, 0xf\}$, $dim(U_{S_1}(x, x) ∩ V_{S_1}(x, x)) = 1$.

As for MIDORI64, Fig. 2 represents, for a given randomly chosen weak expanded key, all 11-round valid characteristics ($Δ_0, Δ_1, ..., Δ_{11}$) with all $Δ_t ∈ \{0x4, 0xf\}^4$ starting from given $Δ_0, Δ_1$ chosen at random in {$0x4, 0xf$}^4. As in Fig. 1, we observe two growth regimes. But, there are more characteristics than in the original Column-MIDORI: since the minimum number of inputs for a given characteristic is divided by 2, the number of valid characteristics after 11 rounds is twice bigger.

## 4.2 Case of a Square but Not Perfect Differential

**With Rectangle Sbox.** We now replace MIDORI64 Sbox by the Sbox used in RECTANGLE [ZBL+14,ZBL+15] specified in Appendix A. It can be checked that $(α, β)$ with $α := 0x5$ and $β := 0x9$ is a square differential for S with

$$DDT_S(0x5, 0x5) = DDT_S(0x5, 0x9) = DDT_S(0x9, 0x5) = DDT_S(0x9, 0x9) = 2.$$
<figure><img src="image_3.png" /><figcaption>Figure 2: Representation of the valid characteristics $(\Delta_0, \dots, \Delta_{11})$ with all $\Delta_t \in \{0x4, 0xf\}^4$ starting from given $\Delta_0, \Delta_1 \in \{\alpha, \beta\}^4$ for 11 rounds of Column-MIDORI with Sbox $S_1$, and for a random weak expanded-key.</figcaption></figure>

Indeed, we have

$$
\begin{align*}
\text{XDDT}_S(0x5, 0x5) &= 0x2 + \langle 0x5 \rangle \quad \text{and} \quad \text{YDDT}_S(0x5, 0x5) = 0xc + \langle 0x5 \rangle, \\
\text{XDDT}_S(0x5, 0x9) &= 0xe + \langle 0x5 \rangle \quad \text{and} \quad \text{YDDT}_S(0x5, 0x9) = 0x4 + \langle 0x9 \rangle, \\
\text{XDDT}_S(0x9, 0x5) &= 0x6 + \langle 0x9 \rangle \quad \text{and} \quad \text{YDDT}_S(0x9, 0x5) = 0x7 + \langle 0x5 \rangle, \\
\text{XDDT}_S(0x9, 0x9) &= 0x3 + \langle 0x9 \rangle \quad \text{and} \quad \text{YDDT}_S(0x9, 0x9) = 0xa + \langle 0x9 \rangle.
\end{align*}
$$

Moreover, $E = \langle 0x5, 0x9 \rangle$.

This differential is not a perfect square differential, as shown in the following table providing the values of $y_0^{\delta_0, \delta_1} + x_0^{\delta_1, 0x5}$ for all $\delta_0, \delta_1 \in \{0x5, 0x9\}$. Elements in red lie in $E$, those in blue lie in $0x2 + E$. Hence, the set of weak round-keys is defined by the disjoint union of these two cosets of $E: K = (E \cup (0x2 + E))^m$.

<table><thead><tr><th>δ<sub>1</sub></th><th>α</th><th>β</th></tr></thead><tbody><tr><td>α</td><td>0xe</td><td>0x2</td></tr><tr><td>β</td><td>0x5</td><td>0xc</td></tr></tbody></table>

From Prop. 3, we know that a valid $(r-1)$-round characteristic $(\Delta_0, \dots, \Delta_{r-1})$ can be extended to some $r$-round characteristic if and only if, for each $1 \le j \le m$, one of the following two conditions holds

$$
\begin{array}{l}
L^{-1}(K_{r-1})[j] \in E \text{ and } \Delta_{r-2}[j] = 0x9 \\
\text{or } L^{-1}(K_{r-1})[j] \in (0x2 + E) \text{ and } \Delta_{r-2}[j] = 0x5.
\end{array}
$$

It follows that, for any given $(K_1, \dots, K_{r-1})$ in the set of weak expanded keys, there is a single $(r-2)$-round characteristic $(\Delta_0, \dots, \Delta_{r-2})$ such that $(\Delta_0, \dots, \Delta_{r-2}, \Delta_{r-1}, \Delta_r)$ is valid for some $\Delta_{r-1}, \Delta_r \in \{0x5, 0x9\}^m$. In other words, all valid $r$-round characteristics with differences in $\{0x5, 0x9\}^m$ share the same $(\Delta_0, \dots, \Delta_{r-2})$.

As before, we consider a randomly chosen weak expanded key. We choose for $\Delta_0$ and $\Delta_1$ the values determined by $K_1$ and $K_2$. Then, at Round 3, there are several valid characteristics $(\Delta_0, \Delta_1, \Delta_2, \Delta_3)$. For the majority of the weak expanded keys, these characteristics cannot be extended since none of the valid values of $\Delta_2$ is compatible with the condition for $\Gamma_3 \neq \emptyset$, namely

$$
\begin{array}{l}
L^{-1}(K_3)[j] \in E \text{ and } \Delta_2[j] = 0x9 \\
\text{or } L^{-1}(K_3)[j] \in (0x2 + E) \text{ and } \Delta_2[j] = 0x5.
\end{array}
$$
<figure><img src="image_4.png" /><figcaption>Figure 3: Representation of the valid characteristics ($\Delta_0, \dots, \Delta_{11}$) with all $\Delta_t \in \{0x5, 0x9\}^4$ starting from the unique possible $\Delta_0, \Delta_1 \in \{\alpha, \beta\}^4$ for 11 rounds of Column-MIDORI with RECTANGLE Sbox.</figcaption></figure>

This generic situation is depicted by Fig. 3a.

But, for a few weak expanded keys, there exist differential characteristics ($\Delta_0, \Delta_1, \Delta_2, \Delta_3$) that can be extended. This situation is described by Fig. 3b. Here, we start from a set of $2^4$ valid inputs for ($\Delta_0, \Delta_1$). This set is then divided into the input sets of 8 different 3-round characteristics, each of size 2. Obviously, these sets cannot be divided further, but only some of the characteristics can be extended. This implies that, after 5 rounds and more, there is a single valid characteristic with differences in $\{0x5, 0x9\}^4$ and this characteristic has only two valid inputs.

# 5 Identifying the Weak Sboxes

We have seen that the existence of weak keys, for which differential characteristics aggregate and lead to a high truncated differential probability, as in the case of MIDORI64, comes from the structure of the linear layer and from the existence of perfect square differentials for the Sbox. At first glance and as discussed in [GJN$^+$16], it seems that the fact that MIDORI64's Sbox is involutive is the main cause of such differentials. However, in Section 4.1, we studied an optimal 4-bit Sbox that is not involutive and nevertheless has the same weakness.

In order to identify the Sboxes that have perfect square differentials, it is much more convenient to study this property up to some equivalence relation, since optimal Sboxes are classified up to equivalence, e.g. [LP07,DC07] for 4-bit Sboxes. Moreover, it is well-known that the differential properties of an Sbox can be derived from those of any Sbox in its equivalence class. In the following, we mainly focus on *affine equivalence* which is used for 4-bit Sboxes in [LP07].

**Definition 7 (Affine equivalence).** Two Sboxes from $\mathbb{F}_2^s$ to $\mathbb{F}_2^s$ are said to be affine equivalent if there exist two affine bijections on $\mathbb{F}_2^s$, $A_1$ and $A_2$, such that $S_2 = A_2 \circ S_1 \circ A_1$.

It is well-known that the differential properties of Sboxes within the same affine-equivalence class are related, as pointed out by the following lemma whose proof is detailed in [CF25].
**Lemma 9.** Let $S_1, S_2$ two s-bit Sboxes such that $S_2 = A_2 \circ S_1 \circ A_1$. Then,

$$XDDT_{S_2}(a, b) = A_1^{-1}(XDDT_{S_1}(L_1(a), L_2^{-1}(b))) \\ \text{and } YDDT_{S_2}(a, b) = A_2(YDDT_{S_1}(L_1(a), L_2^{-1}(b))),$$

where $L_1$ and $L_2$ are the linear parts of $A_1$ and $A_2$. Moreover, $(L_1(a), L_2^{-1}(b))$ is a super-planar differential for $S_1$ if and only if $(a, b)$ is super-planar for $S_2$.

A square differential for a given Sbox then corresponds, for an affine-equivalent Sbox, to four related differentials that have the following structure.

**Definition 8.** A 4-tuple $(a_1, a_2, b_1, b_2)$ is called a rectangle of differentials of weight $\ell$ for $S$ if the following conditions hold:

1. $(a_1, b_1), (a_1, b_2), (a_2, b_1), (a_2, b_2)$ are super-planar differentials for $S$ with $DDT_S(a_i, b_j) = 2^\ell$, for all $1 \le i, j \le 2$.

2. $U_S(a_1, b_1) = U_S(a_1, b_2) := U_S(a_1)$ and $U_S(a_2, b_1) = U_S(a_2, b_2) := U_S(a_2)$.

3. $U_S(a_1) + \langle x_0^{a_1, b_1} + x_0^{a_1, b_2} \rangle = U_S(a_2) + \langle x_0^{a_2, b_1} + x_0^{a_2, b_2} \rangle$

4. $\dim(V_S(a_1, b_1) + V_S(a_1, b_2) + V_S(a_2, b_1) + V_S(a_2, b_2)) \le \ell + 1$.

The next proposition shows that square differentials for a given Sbox can be derived from a rectangle of differentials for an affine-equivalent Sbox. It can be used either for checking whether an Sbox admits square differentials from a representative in its equivalence class, or for constructing an Sbox having square differentials from an Sbox with a rectangle of differentials. See [CF25] for the proof.

**Proposition 4.** Let $S_1, S_2$ two s-bit Sboxes such that $S_2 = A_2 \circ S_1 \circ A_1$. Then $(a_1, a_2, b_1, b_2)$ is a rectangle of differentials of weight $\ell$ for $S_1$ if and only if

$$(L_1^{-1}(a_1), L_1^{-1}(a_2), L_2(b_1), L_2(b_2))$$

is a rectangle of differentials of weight $\ell$ for $S_2$.

Most notably, $(L_1^{-1}(a_1), L_1^{-1}(a_2))$ is a square differential for $S_2$ if and only if $(L_1 \circ L_2)(\{b_1, b_2\}) = \{a_1, a_2\}$, and for all $1 \le i, j \le 2$,

$$(L_1 \circ L_2)(V_{S_1}(a_i, b_j)) \subset U_{S_1}(a_1) + \langle x_0^{a_1, b_1} + x_0^{a_1, b_2} \rangle.$$

**Focus on Optimal 4-bit Sboxes.** It is well-known that the best differential uniformity and linearity for 4-bit Sboxes are equal to 4 and 8, respectively. The Sboxes reaching these two values are said to be optimal, and correspond to 16 affine-equivalence classes [LP07]. These classes may differ regarding several properties. Most notably, the subspace of their quadratic components, i.e., $\{\lambda \in F_2^4 | x \mapsto \lambda \cdot S(x) \text{ has degree at most 2}\}$ may have dimension 0, 1 or 2 depending on the class considered. Then, the existence of rectangles of differentials is related to this dimension as follows.

**Proposition 5.** Let $S$ be a 4-bit optimal Sbox. Then, the following assertions are equivalent:
- S has 3 quadratic components;

- S admits one rectangle of differentials of weight 2;

- S admits three distinct rectangles of differentials of weight 2.

This fact can be observed by studying the 16 affine-equivalence representatives exhibited in [LP07].

Moreover, since any square differential for S with $DDT_S(\alpha, \beta) = 4$ can be derived from a rectangle of differentials for a representative in the affine-equivalence class, it can be checked that any such square differential is a perfect square differential, and leads to the same weakness as MIDORI64 Sbox.

**Proposition 6.** Let S be an optimal 4-bit Sbox and $(\alpha, \beta)$ be a square differential of weight 2 for S. Then $(\alpha, \beta)$ is a perfect square differential.

As an example, the security criteria defined in [GJN$^{+}$16, Section 5.6] for the best possible resistance to invariant-subspace attacks has led to the conclusion that the Sbox should be selected within five affine-equivalence classes. However, among those five classes, two correspond to classes satisfying the property defined in Prop. 5. Therefore, some optimal Sboxes in these two equivalent classes admit perfect square differentials, and using these Sboxes instead of MIDORI64's Sbox, would not avoid the weakness exhibited in Coro. 2. For instance, using Prop. 4, we were able to build an Sbox $S_2$ that admits $(0 \times 2, 0 \times 3)$ as a perfect square differential and is affine equivalent to $S_{silver}$, the fifth silver Sbox given in [GJN$^{+}$16]. These Sboxes are defined in Appendix A.

# 6 Generalization to a Larger Set of Differentials

**Definition 9 (Good set of differences).** A subset $\mathcal{A}$ of elements in $\mathbb{F}_2^s$ is said to be a good set of differences of weight $\ell$ for $S: \mathbb{F}_2^s \to \mathbb{F}_2^s$ if all differentials $(a, b) \in \mathcal{A} \times \mathcal{A}$ are super-planar differentials with $DDT_S(a, b) = 2^\ell$ and if there exists a vector space $E$, called the associated subspace, such that

1. For all $(a, b) \in \mathcal{A} \times \mathcal{A}$, $V_S(a, b) \subset E$.

2. For all $a \in \mathcal{A}$, $\biguplus_{b \in \mathcal{A}} XDDT_S(a, b) = x_0^{a,a} + E$.

This definition generalizes the notion of square differentials: a square differential, as defined in Def. 6, is a particular case of a good set of differences of size 2. The following proposition in an analogue of Prop. 3, on the number of $(r+1)$-round characteristics with all differences in $\mathcal{A}^m$ that are valid for this specific key and share the same first $r$ differences. The proof can be found in [CF25].

**Proposition 7.** Let us consider an SPN with $(r+1)$ rounds, $r \ge 1$, with Sbox $S$ and linear layer $L$. Let $\mathcal{A}$ be a set of good differences of weight $\ell$ for $S$ with associated subspace $E$, such that $L(\mathcal{A}^m) = \mathcal{A}^m$ and $L(E^m) = E^m$. Let $K := (K_1, \dots, K_r)$ be an expanded key and $(\Delta_0, \dots, \Delta_r)$ with all $\Delta_t \in \mathcal{A}^m$ be an $r$-round characteristic which is valid for the first $(r-1)$ round keys. Then

$$ \Gamma_r := \{ \Delta_{r+1} \in \mathcal{A}^m \mid (\Delta_0, \dots, \Delta_r, \Delta_{r+1}) \text{ is a valid characteristic for } K \} $$
is non-empty if and only if

$$K_r \in L(y_0^{\Delta_{r-1}, L^{-1}(\Delta_r)}) + x_0^{\Delta_r, \Delta_r} + E^m.$$

In that case, the subspaces $W_{r-1}(\Delta_0, \dots, \Delta_r)$ and $W_r(\Delta_0, \dots, \Delta_{r+1})$ formed by the weak expanded keys for the r-round (resp. $(r+1)$-round) characteristic satisfy:

$$\sum_{\Delta_{r+1} \in \Gamma_r} 2^{\ell m(r+1) - \dim(W_r(\Delta_0, \dots, \Delta_{r+1}))} = 2^{\ell m r - \dim(W_{r-1}(\Delta_0, \dots, \Delta_r))}.$$

As a consequence, the following generalization of Coro. 2 states that if the set of good differentials satisfies an additional condition, which generalizes the notion of perfect square differentials, the condition on $K_r$ required for extending $(\Delta_0, \dots, \Delta_r)$ one round further is the same for all characteristics.

**Corollary 3.** Let us consider an SPN with Sbox S and linear layer L. Let $\mathcal{A}$ be a set of good differences of weight $\ell$ for S with associated subspace E, such that $L(\mathcal{A}^m) = \mathcal{A}^m$ and $L(E^m) = E^m$. Assume that for any $\Delta, \Delta' \in \mathcal{A}^m$,

$$L(y_0^{\Delta, L^{-1}(\Delta')} + x_0^{\Delta', \Delta'} \in \theta + E^m)$$

for some offset $\theta \in \mathbb{F}_2^{sm}$. Then, for any expanded key $K$ in $(\theta + E^m)^r$ and for any $\Delta_0 \in \mathcal{A}^m$, we have

$$\sum_{\Delta_1, \dots, \Delta_r \in \mathcal{A}^m} \mathrm{DP}[K](\Delta_0, \dots, \Delta_r) = (2^{-(s-\ell)} \#\mathcal{A})^m.$$

**Truncated Differentials for Scream and iScream.** Using commutative cryptanalysis, Baudrin et al. [BFL+23] observed that SCREAM exhibits a behaviour similar to MIDORI64, namely the existence of fixed-key truncated differentials whose probabilities are independent of the number of rounds. This phenomenon is captured by the previous result for a suitable set of differences forming an affine subspace of dimension 3. A comparable differential behaviour can also be identified in iSCREAM, although the techniques of [BFL+23] no longer apply. Let $S_3$ (resp. $S_4$) denote the S-box of SCREAM (resp. iSCREAM), and $L_3$ (resp. $L_4$) its linear layer. Both $L_3$ and $L_4$ satisfy Property (P). However, the approach of [BFL+23] does not apply to iSCREAM, since there exist no non-trivial affine bijections $B, C : \mathbb{F}_2^n \to \mathbb{F}_2^n$ such that $B \circ S_4 = S_4 \circ C$. This can be checked, as suggested by the authors, using the function self_affine-equivalent mappings from the sboxU library.<fnref n="2" /> Now, let $\mathcal{A}_3 := 0x21 + \langle 0x10, 0x40, 0x80 \rangle$ and $\mathcal{A}_4 := 0x94 + \langle 0x01, 0x02, 0x08 \rangle$. Then it can be easily checked that $\mathcal{A}_3$ (resp. $\mathcal{A}_4$) is a good set of differences for $S_3$ (resp. $S_4$) with associated subspace $E_3 := \langle 0x01, 0x10, 0x20, 0x40, 0x80 \rangle$ (resp. $E_4 := \langle 0x90, 0x08, 0x04, 0x02, 0x01 \rangle$).

<footnote n="2">² https://github.com/lpp-crypto/sboxU</footnote>
Moreover, it can be shown that SCREAM satisfies the condition exhibited in Coro. 3 implying that the weak-key sets are the same for all differentials in $A_3 \times A_3$, which leads to a truncated differential of probability $2^{-48}$. However, this additional condition does not hold in the case of iSCREAM. In that case, the differential characteristics involved in the cluster are valid for different weak-keys, implying that there is no fixed-key clustering. Therefore, our analysis provides an explanation for the origin of these two differential behaviours, despite their apparent similarity at first glance.

# 7 Similarities and Differences with Other Concepts

Since MIDORI64 already suffers from many different types of attacks, including invariants [GJN+16,TLS16,Bey18] and commutative cryptanalysis [BFL+23], it is worth understanding whether the phenomenon we have analysed is related to these other notions. A discussion on the differences between super-planar plateau characteristics and invariant subspaces can be found in [CF25]. Here, we focus on the clustering of plateau characteristics having the same weak keys.

## 7.1 Clusters of Plateau Characteristics, Invariant Subspaces and Truncated Differentials

The differential behaviour we have identified shares with invariant subspaces and commutative cryptanalysis the property that it defines a fixed-key truncated differential for $r$ rounds, of the form

$$ \sum_{\Delta_r \in \mathcal{D}} \mathrm{DP}[K](\Delta_0, \Delta_r) \geq 2^{-ms+k} \quad (6) $$

for a subspace $W^r$ of weak keys, where $ms$ is the block size of the cipher.

In the case of an invariant subspace, e.g. if $\mathcal{R}(a + V) = b + V$, then the truncated differential we derive includes all output differences in $\mathcal{D} = V$ and $k = \dim W = \dim V$. If $V$ is defined as an invariant under several rounds, but is not invariant under the round function, $\mathcal{D}$ and $k$ in (6) remain the same, but the weak-key set is not of the form $W^r$ anymore (see [Bey18]).

When considering a square differential $(\alpha, \beta)$ for the Sbox as in Section 3, the output difference in (6) varies in $\mathcal{D} = \{\alpha, \beta\}^m$ and $k = \dim W = m(\ell+1)$ where $\mathrm{DDT}_S(\alpha, \beta) = 2^\ell$. In the more general situation of a good set of differences, we still have that $k = \dim W = m\ell + \log_2(\#\mathcal{D})$. Therefore, $k$ is always strictly greater than the dimension of $\mathcal{D}$, while both values are equal when the truncated differential is derived from an invariant subspace. This shows that these two phenomena are distinct.

An argument pointing out the difference between our work and nonlinear invariants is that MIDORI64 with Sbox $S_2$, defined in App. A, has the same behaviour as the genuine MIDORI64 as shown at the end of Section 5. However, neither $S_2$ nor its powers $S_2^i$ for $i \le 4$, admit a quadratic invariant. Therefore,
the truncated differential we present does not stem from a quadratic invariant of the round function nor from a two-round invariant, as those identified in [Bey18]. Moreover, the weak-key set identified by Coro. 2 differs from those found in [Bey18], and is strictly larger than those in [TLS16].

Obviously, as already noted in [LTW18] in the case of subspace trails, the notion of truncated differentials is more general than the differential behaviour we analyse (and than the notion of invariant subspaces).

## 7.2 Clusters of Plateau Characteristics and Commutative Cryptanalysis

We now show that our results capture the truncated differentials derived from commutative cryptanalysis [BFL$^{+23}$] as soon as the corresponding differentials for the Sbox are super-planar. As in [BFL$^{+23}$], we only focus on commutants that are built from a small affine bijection $\mathcal{A}$ that commutes with the Sbox.<fnref n="3" /> As detailed in [CF25], we can prove the following.

**Corollary 4.** If all pairs $(\alpha, \beta)$ of elements of $\mathcal{A}$ are super-planar differentials for $S$ with $\text{DDT}_S(\alpha, \beta) = 2^\ell$, then $\mathcal{A}$ is a good set of differentials as defined in Def 9. In the particular case where $\dim \mathcal{A} = 1$, $\mathcal{A}$ is a square differential.

**Commutation with the linear layer.** We now show that if the linear layer $L$ commutes with $A^m$, then it satisfies the hypotheses of Coro. 3. Indeed, the only requirement is that $E^m$ and $A^m$ are invariant under $L$ (this also holds for the particular case of Coro. 2, as observed in Rmk. 1). These two conditions can be deduced from the following observation, stated in [Bau24, Lemma 5.12]: $A^{\times m} \circ L = L \circ A^{\times m}$ iff $L_A^{\times m} \circ L = L \circ L_A^{\times m}$ and $L(c_A^{\times m}) = c_A^{\times m}$.

Therefore, it follows that the fixed-key truncated differentials derived from commutative trails built from a matrix $\mathcal{A}$ commuting with the Sbox and such that $A^m$ commutes with the linear layer, all correspond to a cluster of plateau characteristics and are captured by our work. The only additional condition we need is that the involved differentials are super-planar.

**Remark 2.** Compared to [BFL$^{+23}$], we require that all pairs in $\mathcal{A}$ are super-planar differentials. This condition always holds when the Sbox has differential uniformity at most 4 and when $0 \notin \mathcal{A}$. This last requirement equivalently means that $c_A \neq 0$. But when $c_A = 0$, $A = L_A$ is linear and $E$ is an invariant subspace of the cipher. This is the case of the commutative trail for MIDORI128 (without key-schedule) exhibited in [BFL$^{+23}$]. This subspace is invariant under the linear and the Sbox layers.

Most importantly, our work captures more ciphers than the ones covered by the commutative trails described in [BFL$^{+23}$]. For instance, as detailed in Section 6, it enables us to show that SCREAM and ISCREAM both present similar clusters of plateau characteristics, but that the associated weak-keys are the same of all characteristics in SCREAM, and are different in ISCREAM.

<footnote n="3">³ The linear commutants that are independent of the Sbox, as in [LMR15,CFG$^{+17}$], are of a different nature.</footnote>
# 8 Conclusions and Future Work

Our work emphasizes that when the hypothesis of stochastic equivalence does not hold, estimating the expected differential probability of an overall differential by summing the EDPs of its individual characteristics can be misleading. By focusing on (truncated) differentials composed of plateau characteristics, we are able to characterize and explain the distinct fixed-key behaviours of MIDORI64, SCREAM and iSCREAM with respect to certain truncated differentials. Identifying this mechanism is particularly relevant, as the associated weak expanded-keys of MIDORI64 are not detected by other known attacks, such as invariant-subspace attacks. Gaining insight into this a priori unpredictable differential behaviour is therefore crucial. Ignoring it could raise concerns about the security of other lightweight ciphers that relies solely on conventional EDP-based reasoning.

Our analysis has two major limitations: it is restricted to ciphers whose linear layers let some particular subspaces invariant. This holds in particular for the linear layers with a binary matrix satisfying the so-called Property (P), as those of MIDORI, SCREAM, iSCREAM, PRINCE or MANTIS. It is also limited to differential characteristics where all internal differentials for the Sbox are super-planar, otherwise these characteristics won't be plateau. In practice, when the Sbox has differential uniformity at most 4, this condition equivalently means that all internal Sboxes are active. Generalizing this to non-plateau characteristics would require determining the fixed-key probabilities of characteristics that do not present such a strong structure. The quasi-differential framework offers a promising avenue in this context, but deriving meaningful expressions for a large set of characteristics remains challenging, especially because it not only involves the differential properties of the Sboxes, but also their Walsh spectra. The omission of the concrete key schedule in our analysis should not be viewed as a limitation. Quite the opposite, it enables a two-step design approach: first, identifying potential weaknesses in the expanded-key model, and then developing a key schedule that mitigates them. Guaranteeing the absence of weak expanded keys is an attractive design principle, as it provides greater flexibility in the choice of key-schedule algorithms.

# A Specifications of the Sboxes Analysed in the Paper

<table><caption>Table1: Specifications of the 4-bit Sboxes used in the paper, in hexadecimal notation.</caption><thead><tr><th></th><th>0</th><th>1</th><th>2</th><th>3</th><th>4</th><th>5</th><th>6</th><th>7</th><th>8</th><th>9</th><th>a</th><th>b</th><th>c</th><th>d</th><th>e</th><th>f</th></tr></thead><tbody><tr><td>MIDORI64</td><td>c</td><td>a</td><td>d</td><td>3</td><td>e</td><td>b</td><td>f</td><td>7</td><td>8</td><td>9</td><td>1</td><td>5</td><td>0</td><td>2</td><td>4</td><td>6</td></tr><tr><td>RECTANGLE</td><td>6</td><td>5</td><td>c</td><td>a</td><td>1</td><td>e</td><td>7</td><td>9</td><td>b</td><td>0</td><td>3</td><td>d</td><td>8</td><td>f</td><td>4</td><td>2</td></tr><tr><td>Luffa v1</td><td>7</td><td>d</td><td>b</td><td>a</td><td>c</td><td>4</td><td>8</td><td>3</td><td>5</td><td>f</td><td>6</td><td>0</td><td>9</td><td>1</td><td>2</td><td>c</td></tr><tr><td>S<sub>1</sub></td><td>4</td><td>8</td><td>1</td><td>7</td><td>9</td><td>0</td><td>e</td><td>3</td><td>6</td><td>5</td><td>f</td><td>d</td><td>2</td><td>a</td><td>c</td><td>b</td></tr><tr><td>S<sub>2</sub></td><td>b</td><td>9</td><td>a</td><td>8</td><td>7</td><td>c</td><td>4</td><td>e</td><td>5</td><td>0</td><td>6</td><td>2</td><td>d</td><td>1</td><td>3</td><td>f</td></tr><tr><td>S<sub>silver</sub></td><td>0</td><td>1</td><td>2</td><td>d</td><td>4</td><td>7</td><td>f</td><td>6</td><td>8</td><td>b</td><td>e</td><td>3</td><td>a</td><td>c</td><td>5</td><td>9</td></tr></tbody></table>
*Acknowledgements.* This work was supported by PEPR Cybersécurité, project Cryptanalyse (22-PECY-0010) and by the French DGA. The authors warmly thank Jules Baudrin and Léo Perrin for stimulating discussions, and the anonymous reviewers for their insightful comments, which contributed to improving the quality of this work.

## References

Abd13. Mohamed Ahmed Abdelraheem. Estimating the probabilities of low-weight differential and linear approximations on PRESENT-like ciphers. In Taekyong Kwon, Mun-Kyu Lee, and Daesung Kwon, editors, *ICISC 12*, volume 7839 of LNCS, pages 368–382. Springer, Berlin, Heidelberg, November 2013.

Bau24. Jules Baudrin. *Algebraic properties of symmetric ciphers and of their non-linear components*. PhD thesis, Sorbonne Université, 2024. https://theses.fr/api/v1/document/2024SORUS547.

BBI<sup>+15</sup>. Subhadeep Banik, Andrey Bogdanov, Takanori Isobe, Kyoji Shibutani, Harunaga Hiwatari, Toru Akishita, and Francesco Regazzoni. Midori: A block cipher for low energy. In Tetsu Iwata and Jung Hee Cheon, editors, *ASIACRYPT 2015, Part II*, volume 9453 of LNCS, pages 411–436. Springer, Berlin, Heidelberg, November / December 2015.

BCG<sup>+12</sup>. Julia Borghoff, Anne Canteaut, Tim Güneysu, Elif Bilge Kavun, Miroslav Knežević, Lars R. Knudsen, Gregor Leander, Ventzislav Nikov, Christof Paar, Christian Rechberger, Peter Rombouts, Søren S. Thomsen, and Tolga Yalçin. PRINCE - A low-latency block cipher for pervasive computing applications - extended abstract. In Xiaoyun Wang and Kazue Sako, editors, *ASIACRYPT 2012*, volume 7658 of LNCS, pages 208–225. Springer, Berlin, Heidelberg, December 2012.

Bey18. Tim Beyne. Block cipher invariants as eigenvectors of correlation matrices. In Thomas Peyrin and Steven Galbraith, editors, *ASIACRYPT 2018, Part I*, volume 11272 of LNCS, pages 3–31. Springer, Cham, December 2018.

BFL<sup>+23</sup>. Jules Baudrin, Patrick Felke, Gregor Leander, Patrick Neumann, Léo Perrin, and Lukas Stennes. Commutative cryptanalysis made practical. *IACR Trans. Symm. Cryptol.*, 2023(4):299–329, 2023.

BJK<sup>+16</sup>. Christof Beierle, Jérémy Jean, Stefan Kölbl, Gregor Leander, Amir Moradi, Thomas Peyrin, Yu Sasaki, Pascal Sasdrich, and Siang Meng Sim. The SKINNY family of block ciphers and its low-latency variant MANTIS. In Matthew Robshaw and Jonathan Katz, editors, *CRYPTO 2016, Part II*, volume 9815 of LNCS, pages 123–153. Springer, Berlin, Heidelberg, August 2016.

BR22. Tim Beyne and Vincent Rijmen. Differential cryptanalysis in the fixed-key model. In Yevgeniy Dodis and Thomas Shrimpton, editors, *CRYPTO 2022, Part III*, volume 13509 of LNCS, pages 687–716. Springer, Cham, August 2022.

BS91. Eli Biham and Adi Shamir. Differential cryptanalysis of DES-like cryptosystems. In Alfred J. Menezes and Scott A. Vanstone, editors, *CRYPTO'90*, volume 537 of LNCS, pages 2–21. Springer, Berlin, Heidelberg, August 1991.

CF25. Anne Canteaut and Merlin Fruchon. Understanding unexpected fixed-key differential behaviours: How to avoid major weaknesses in lightweight designs (extended version). Cryptology ePrint Archive, Report 2025/1553, 2025.
CFG<sup>+</sup>15. Anne Canteaut, Thomas Fuhr, Henri Gilbert, María Naya-Plasencia, and Jean-René Reinhard. Multiple differential cryptanalysis of round-reduced PRINCE. In Carlos Cid and Christian Rechberger, editors, *FSE 2014*, volume 8540 of LNCS, pages 591–610. Springer, Berlin, Heidelberg, March 2015.

CFG<sup>+</sup>17. Colin Chaigneau, Thomas Fuhr, Henri Gilbert, Jérémy Jean, and Jean-René Reinhard. Cryptanalysis of NORX v2.0. *IACR Trans. Symm. Cryptol.*, 2017(1):156–174, 2017.

DC07. Christophe De Cannière. *Analysis and Design of Symmetric Encryption Algorithms*. PhD thesis, Katholieke Universiteit Leuven, 2007.

DR01. Joan Daemen and Vincent Rijmen. The wide trail design strategy. In Bahram Honary, editor, *8th IMA International Conference on Cryptography and Coding*, volume 2260 of LNCS, pages 222–238. Springer, Berlin, Heidelberg, December 2001.

DR07. Joan Daemen and Vincent Rijmen. Plateau characteristics. *IET information security*, 1(1):11–17, 2007.

GJN<sup>+</sup>16. Jian Guo, Jérémy Jean, Ivica Nikolic, Kexin Qiao, Yu Sasaki, and Siang Meng Sim. Invariant subspace attack against Midori64 and the resistance criteria for S-box designs. *IACR Trans. Symm. Cryptol.*, 2016(1):33–56, 2016.

GLS<sup>+</sup>14. Vincent Grosso, Gaëtan Leurent, François-Xavier Standaert, Kerem Varici, François Durvaux, Lubos Gaspar, and Stéphanie Kerckhof. SCREAM & iSCREAM: Side-channel resistant authenticated encryption with masking. Submission to the Caesar competition https://competitions.cr.yp.to/round1/screamv1.pdf, 2014.

Knu93. Lars R. Knudsen. Iterative characteristics of DES and s<sup>2</sup>-DES. In Ernest F. Brickell, editor, *CRYPTO'92*, volume 740 of LNCS, pages 497–511. Springer, Berlin, Heidelberg, August 1993.

LAAZ11. Gregor Leander, Mohamed Ahmed Abdelraheem, Hoda AlKhzaimi, and Erik Zenner. A cryptanalysis of PRINTcipher: The invariant subspace attack. In Phillip Rogaway, editor, *CRYPTO 2011*, volume 6841 of LNCS, pages 206–221. Springer, Berlin, Heidelberg, August 2011.

LMM91. Xuejia Lai, James L. Massey, and Sean Murphy. Markov ciphers and differential cryptanalysis. In Donald W. Davies, editor, *EUROCRYPT'91*, volume 547 of LNCS, pages 17–38. Springer, Berlin, Heidelberg, April 1991.

LMR15. Gregor Leander, Brice Minaud, and Sondre Rønjom. A generic approach to invariant subspace attacks: Cryptanalysis of Robin, iSCREAM and Zorro. In Elisabeth Oswald and Marc Fischlin, editors, *EUROCRYPT 2015, Part I*, volume 9056 of LNCS, pages 254–283. Springer, Berlin, Heidelberg, April 2015.

LP07. Gregor Leander and Axel Poschmann. On the classification of 4 bit S-boxes. In Claude Carlet and Berk Sunar, editors, *WAIFI 2007*, pages 159–176, Berlin, Heidelberg, 2007. Springer.

LPS21. Gaëtan Leurent, Clara Pernot, and André Schrottenloher. Clustering effect in Simon and Simeck. In Mehdi Tibouchi and Huaxiong Wang, editors, *ASIACRYPT 2021, Part I*, volume 13090 of LNCS, pages 272–302. Springer, Cham, December 2021.

LTW18. Gregor Leander, Cihangir Tezcan, and Friedrich Wiemer. Searching for subspace trails and truncated differentials. *IACR Trans. Symm. Cryptol.*, 2018(1):74–100, 2018.
Nyb12. Kaisa Nyberg. "Provable" security against differential and linear cryptanalysis (invited talk). In Anne Canteaut, editor, *FSE 2012*, volume 7549 of *LNCS*, pages 1-8. Springer, Berlin, Heidelberg, March 2012.

TLS16. Yosuke Todo, Gregor Leander, and Yu Sasaki. Nonlinear invariant attack - practical attack on full SCREAM, iSCREAM, and Midori64. In Jung Hee Cheon and Tsuyoshi Takagi, editors, *ASIACRYPT 2016, Part II*, volume 10032 of *LNCS*, pages 3-33. Springer, Berlin, Heidelberg, December 2016.

ZBL+14. Wentao Zhang, Zhenzhen Bao, Dongdai Lin, Vincent Rijmen, Bohan Yang, and Ingrid Verbauwhede. RECTANGLE: A bit-slice lightweight block cipher suitable for multiple platforms. Cryptology ePrint Archive, Report 2014/084, 2014.

ZBL+15. Wentao Zhang, Zhenzhen Bao, Dongdai Lin, Vincent Rijmen, Bohan Yang, and Ingrid Verbauwhede. RECTANGLE: a bit-slice lightweight block cipher suitable for multiple platforms. *Sci. China Inf. Sci.*, 58(12):1-15, 2015.