Abstract
Schwaemm is a member of the Sparkle-suite, a family of lightweight symmetric cryptographic algorithms that advanced to finalist status in the NIST lightweight cryptography standardization process. In 2023, using differential-linear cryptanalysis, Xiong and Liu presented a practical 4-round distinguisher and a theoretical 4.5-round key-recovery attack on a variant of Schwaemm128-128 that did not adhere to the original round constants. Recently, Niu et al. introduced a dedicated time-memory trade-off framework to achieve key-recovery attacks on 4.5-round Schwaemm using 2.5-round differential-linear distinguishers. This paper revisits the differential-linear cryptanalysis of round-reduced Schwaemm, focusing on the original, round-constant-respecting versions. We identify effective 4-round differential-linear trails and establish practical 4-round distinguishers with complexity below \(2^{13.1}\). Experimental results demonstrate 100% distinguishing success for Schwaemm128-128, Schwaemm256-128, and Schwaemm192-192, and 12.10% for Schwaemm256-256. Building upon these distinguishers, we propose a stream-based Time-Memory Trade-Off method and multi-trail (full) key recovery to mount 4.5-round attacks on the initialization phase of all Schwaemm versions. Our full key-recovery attacks achieve the best-known data complexities (bounded between \(2^{9.58}\) and \(2^{15.73}\)) and memory footprints (constrained between \(2^{27}\) and \(2^{55}\)), significantly outperforming prior works. Furthermore, by extracting bit-level algebraic equations, we demonstrate that partial key information can be directly recovered with extremely low time complexities. For the respective versions, we establish a total of 36, 29, 29, and 9 equations, with time complexities of only \(2^{15.73}\), \(2^{14.94}\), \(2^{14.94}\), and \(2^{9.58}\). Among these, 9, 7, 7, and 3 are strictly linear equations, allowing for the direct recovery of an equal number of key bits, which drastically prunes the search space and reduces the time complexity of the full key-recovery process. Also, we emphasize that these attacks in this paper do not compromise the security of full Schwaemm.
Introduction
Among the lightweight ciphers, there is a class of algorithms that are called ARX-based ciphers, or ARX ciphers for short, because they only use three basic operations: Addition, Rotation, and XOR. In a broad sense, ARX ciphers also include algorithms that use bit operations such as logical operations, logical shifts, and boolean functions. Benefiting from the simple operations in the designs, ARX ciphers usually enjoy high efficiency at a relatively low implementation cost. Therefore, many block ciphers have been proposed following the ARX design strategy, such as FEAL (Shimizu and Miyaguchi 1987), TEA (Wheeler and Needham 1994), XTEA (Needham and Wheeler 1997), RC5 (Rivest 1994), HIGHT (Hong et al. 2006), LEA (Hong et al. 2013), SPECK (Beaulieu et al. 2013), and SPARX (Dinu et al. 2016). In addition, there are hash functions, stream ciphers and message authentication codes based on ARX structures, such as MD (Rivest 1992) and SHA (Dworkin 2015) series of hash functions, Skein (Ferguson et al. 2010), BLAKE (Aumasson et al. 2008), Keccak (Bertoni et al. 2013), ChaCha (Bernstein et al. 2008), Salsa20 (Bernstein 2008) and Chaskey (Mouha et al. 2014).
The lightweight cryptographic algorithm Sparkle (Beierle et al. 2019) designed by Beierle et al. was selected as one of the ten finalists of the NIST lightweight cryptography standardization process. In the suite of Sparkle, an Authenticated Encryption with Associated Data (AEAD) Schwaemm, a hash function Esch and an Extendable-output function XOEsch are provided. The underlying permutation for the three aforementioned algorithms is built upon an ARX S-box called Alzette.
Related Works. The current analysis of the Sparkle family can be delineated into three main aspects.
The first is the analysis of the S-box Alzette. In 2020, the designers (Beierle et al. 2020) gave a comprehensive analysis of Alzette. By using the tools published in Huang and Wang (2019) and Huang (2020), Huang et al. (2022) improved the bounds on the differential and linear trail of Alzette. They also analyzed the probabilities of rotational-XOR differential probabilities of all instances of Alzette used in Sparkle. Those probabilities (over one iteration of Alzette) were reported to be in the range \([2^{-52.66}, 2^{-37.66}]\) depending on the constant \(c_i\). In Liu et al. (2021), Liu et al. introduced a generalization of differential-linear cryptanalysis, so-called rotational differential-linear attacks. The general idea of those attacks is to replace the differential part of a differential-linear distinguisher by a rotational-XOR difference. They analyzed (rotational) differential-linear distinguishers of Alzette with the constant \(c_0\). More precisely, Liu et al. found a differential-linear distinguisher over one iteration of Alzette with correlation \(2^{-0.27}\) (experimental correlation is \(2^{-0.1}\)), and a rotational differential-linear distinguisher over one iteration of Alzette with correlation \(2^{-11.37}\) (experimental correlation is \(2^{-7.35}\)). In 2024, Han et al. (2024) used the SAT-based method again to improve the bounds on differential and linear trails of Alzette.
The second is the analysis of the Sparkle permutation. In 2022, Schrottenloher and Stevens (2022) studied the simplified MILP modeling of the Meet-in-the-Middle (MITM) attacks, which can greatly reduce the input of the general solver. Combined with theoretical analysis, they proved the existence and complexity of the attack. Applying the new method to Sparkle permutation, a 4-round MITM distinguisher for Sparkle256/384/512 was found using the MILP solver. Further, they used the guess and determine (GAD) strategy combined with the SAT solver to simplify and improve the 4-round MITM distinguisher. Finally, they found 4-round distinguishers of Sparkle256/384 and 5-round distinguishers of Sparkle512. However, the analysis results of Schrottenloher et al. are Sparkle permutation, not applicable to authenticated encryption algorithm Schwaemm.
The third focuses on the analysis of the authentication encryption algorithm Schwaemm. Schwaemm includes four versions, namely Schwaemm128-128, Schwaemm256-128, Schwaemm192-192, and Schwaemm256-256. The designers Beierle et al. (2019) gave 3.5 rounds of data trade-off attack on all versions of Schwaemm, 3.5 rounds of guess and determine attacks on Schwaemm256-256, 4.5-round birthday differential attack on all versions of Schwaemm and 4.5-round birthday differential attack on Schwaemm256-256 under the whitening key. In 2023, Xiong and Liu (2023) presented a practical distinguishing attack as well as a theoretical key-recovery attack on 4.5-round Schwaemm128-128 with the constants of Alzette at the second round being all c[0]Footnote 1, by using differential-linear cryptanalysis. More recently, in 2024, Niu et al. (2024) presented a framework for speeding up key-recovery attacks on Schwaemm based on 2.5-round differential-linear distinguishers. When there are a large number of highly biased differential-linear approximations, they introduced a dedicated time-memory trade-off technique relying on a large hash table for testing the equations induced by the differential-linear approximations, based on which they presented the first valid key-recovery attacks on the AEAD Schwaemm. For 3.5 and 4.5 steps of Schwaemm, their attacks are about \(2^{63}\) or \(2^{126}\) times faster than the brute-force search.
Contributions. This paper revisits the Schwaemm against differential-linear cryptanalysis. In Xiong and Liu (2023), Xiong and Liu gave a 4-round differential-linear distinguisher/key recovery attack solely on Schwaemm128-128. While their approach is effective, their algorithm for calculating corresponding values in differential trail suffers from high memory complexity. To address this, we first introduce a new and optimized algorithm that significantly reduces this complexity by partitioning tables of storing values, with full details provided in Section “Searching Differential-Linear Trails of Schwaemm”.
Furthermore, whereas the analysis in Xiong and Liu (2023) was confined to a basic key-recovery attack on a modified variant of the single Schwaemm128-128 version, we present a 4.5-round multi-trail key-recovery attack applicable to the initialization phase of all Schwaemm versions. Importantly, we introduce a new theoretical methodology for the key-recovery phase. This method establishes mathematical equations on the key by analyzing the bit-level differential propagation of the modular addition within the Alzette permutation, the linear ones of which allow for the direct recovery of key bits.
For the 4-round of Schwaemm128-128, Schwaemm256-128, Schwaemm192-192 and Schwaemm256-256, the success probabilities of distinguishing attacks are 100%, 100%, 100% and 12.10%. The complexities are \(2^{10.63}\), \(2^{13.06}\), \(2^{13.06}\), and \(2^{9.81}\), respectively. That is, all the distinguishers have complexities less than \(2^{13.1}\). As far as we know, this is the first time that 4-round distinguishers are presented for Schwaemm.
Based on our multi-trail TMTO framework, we evaluate the full key-recovery attacks on 4.5 rounds of all Schwaemm versions. Our attacks exhibit significant advantages in both data and memory requirements. Specifically, the data complexities are remarkably bounded between \(2^{9.58}\) and \(2^{15.73}\), and the memory footprints are strictly constrained between \(2^{27}\) and \(2^{55}\). Compared to prior works that typically demand \(2^{64}\) to \(2^{128}\) data and memory, our attacks achieve the best-known data and memory complexities to date.
Furthermore, we demonstrate that partial key information can be directly recovered with extremely low time complexities by extracting bit-level algebraic equations. For the four versions, we establish a total of 36, 29, 29, and 9 equations with time complexities of only \(2^{15.73}\), \(2^{14.94}\), \(2^{14.94}\), and \(2^{9.58}\), respectively. Among these, we successfully identified 9, 7, 7, and 3 strictly linear equations, which allow for the direct deduction of an equal number of actual key bits without any exhaustive guessing, thereby significantly reducing the overall time complexity required to recover the full key.
For the details of our attacks with the most key equations, please refer to Tables 1 and 2. Note that our new results are highlighted in bold in these tables. For other attack results (Tables 3, 4), please refer to Tables 5, 6 and 7.
Organization. The rest of this paper is organized as follows. In Section “Preliminaries”, we introduce the specifications of Sparkle and the authenticated cipher family Schwaemm, and recall the theoretical framework of Carry-bit-dependent difference distribution tables (CDDT), the improved Matsui’s algorithm, and differential-linear cryptanalysis. In Section “Searching Differential-Linear Trails of Schwaemm”, we present the improved method for searching 4-round differential-linear trails of Schwaemm. The details of the differential-linear cryptanalysis on Schwaemm are presented in Section “DL Cryptanalysis of Schwaemm”. Finally, we conclude this paper in Section “Conclusion”.
Preliminaries
In this section, we first introduce the specifications of Sparkle and the authenticated cipher family Schwaemm. Then, we recall the theoretical framework of Carry-bit-dependent difference distribution tables (CDDT), the improved Matsui’s algorithm (Matsui 1994), and differential-linear cryptanalysis.
Symbol description
Here we summarize the notations used by our attacks in Table 3.
Description of Sparkle
The Sparkle family of lightweight cryptographic algorithms includes the authenticated encryption algorithm Schwaemm, the hash function Esch and the scalable output function XOEsch (Beierle et al. 2019). All three algorithms use the Sparkle permutations.
The Sparkle Permutations. Sparkle permutation consists of multiple rounds, each round consists of multiple sets of Alzette with 64-bit input in parallel and a linear transformation.
-
The ARX-box Alzette (denoted by A) \(A:\left( \mathbb {F}_2^{32} \times \mathbb {F}_2^{32}\right) \times \mathbb {F}_2^{32}\rightarrow \left( \mathbb {F}_2^{32} \times \mathbb {F}_2^{32}\right)\), \(((x, y), c) \mapsto (u, v).\) We define \(A_c\) to be the permutation \((x, y) \mapsto A(x, y, c)\) from \(\mathbb {F}_2^{32} \times \mathbb {F}_2^{32}\) to \(\mathbb {F}_2^{32} \times \mathbb {F}_2^{32}\).
-
The linear diffusion layer \(\mathcal {L}_{n_b}: {(\mathbb {F}_2^{64})}^{n_b} \rightarrow {(\mathbb {F}_2^{64})}^{n_b}\), where \(n_b\) denotes the number of 64-bit branches, i.e., the block size divided by 64. It is necessary that \(n_b\) is even. Specifically, \(\mathcal {L}_{n_b}\) represents a Feistel round that utilizes a linear Feistel function \(\mathcal {M}_{h_b}\), which permutes \((\mathbb {F}_2^{64})^{h_b}\), where \(h_b = \frac{n_b}{2}\).
The Authenticated Cipher Family Schwaemm. Lightweight authenticated encryption Schwaemm includes four versions, i.e., Schwaemm128-128, Schwaemm256-128, Schwaemm192-192 and Schwaemm256-256. During the encryption process, for a given key K and nonce N, it allows to process associated data A and message M of arbitrary length and output a ciphertext C with \(|C| = |M|\) and an authentication tag T. For a given (K, N, A, C, T), the decryption procedure returns the decryption M of C if the tag T is valid, otherwise it returns the error symbol \(\bot\). The primary member of the family is Schwaemm256-128. For more details, we refer to Beierle et al. (2019).
Carry-bit-dependent difference distribution tables
The core challenge in analyzing ARX ciphers lies in the modular addition operation, for which computing a full Difference Distribution Table (DDT) is infeasible due to the typical 32-bit word size. To address this, Liu et al. introduced the concept of the CDDT (Liu et al. 2021). The fundamental insight is that an n-bit modulo addition can be divided into a sequence of smaller modulo additions on small bit words (e.g., 8 or 4-bit words), which are correlated by carry bits. The CDDT is essentially the DDT of these small, correlated partial sums. By utilizing the CDDT, the differential probability of the large n-bit addition is computed by looking up and multiplying the probabilities from these smaller, dependent tables. This methodology allows the differential search problem in ARX ciphers to be treated similarly to S-box based ciphers. In the following, we summarize the notations and theoretical framework of CDDT as proposed by Liu et al. (2021), which serves as the foundation for our search.
An n-bit vector \(x = (x_{n-1}, \dots , x_1, x_0) \in \mathbb {F}_2^n\) means a binary representation of an integer \(\sum \limits _{i=0}^{n-1} x_i 2^i\) in \(\mathbb {Z}_{2^n}\). Let \(x, y \in \mathbb {F}_2^n\). Then
where \(carry(x,y) = (c_{n-1}, \dots , c_1, c_0) \in \mathbb {F}_2^n\) denotes the carry bit vector of \(x \boxplus y\). It is defined as follows:
Next, Liu et al. gave another representation of vectors in \(\mathbb {F}_2^n\), which is helpful for characterizing the differential probability of addition modulo \(2^n\) from a new viewpoint.
Suppose \(n = mt\). For an n-bit vector \(x \in \mathbb {F}_2^n\), \(X_k = x[(k + 1)t - 1: kt]\). Then it holds
For two t-bit vectors \(X, Y \in \mathbb {F}_2^t\) and a bit \(e \in \mathbb {F}_2\), \(X \boxplus Y \boxplus e\) denotes
which is equal to \(X \oplus Y \oplus carry^*(X, Y)\), and \(carry^*(X, Y) = (c^*_{t-1}, \dots , c^*_0)\) is computed as follows
Therefore, it is easy to check that addition modulo \(2^n\) can be written as follows:
where \(C_{k}=carry(x,y)[(k+1)t-1:kt]\), and \(c_{kt}\) is the kt-th bit of carry(x, y), which is the carry bit vector of \(x \boxplus y\).
Note that \(c_0=0\) and for \(k \ge 0\), \(c_{(k+1)t}\)can be computed from \(X_{k} \boxplus Y_{k} \boxplus c_{k t}\) by formula 2. Then the computation of \(mt-\)bit vectors addition modulo \(2^{mt}\) can be divided into m portions of \(t-\)bit vectors addition modulo \(2^t\), and the \((k+1)-\)th portion is correlated to the \(k-\)th portion by the carry bit \(C_{(k+1)t}\). Then we can build difference distribution tables of addition modulo \(2^t\) with different correlated values, and these difference distribution tables are called carry-bit-dependent difference distribution tables (CDDTs).
The improved Matsui’s algorithm
Besides using the CDDT, the main difference between the optimized algorithm by Liu et al. (2021) and Matsui’s algorithm (Matsui 1994) is to search the differential trails according to the differential probability from large to small. In the original Matsui’s algorithm, one computes the n-round maximum differential probability \(B_n\) based on the maximum probabilities for fewer rounds (i.e., \(B_{n-1}\)) and an initial estimate \(\overline{B_n}\) for the n-round probability. Let \(\overline{B_n} = B_n\), each time the differential trail with a specified probability is searched. If the differential trails of this probability cannot be found, then reduce the differential probability and search again. Once the algorithm terminates, the obtained differential trails must be the optimal differential trails.
In addition, in order to speed up the search, two improvements have been taken by Liu et al. in 2021. Firstly, before searching the differential trail, the CDDTs are sorted according to their differential probability from large to small. The improved Matsui’s algorithm proposed in Liu et al. (2021) ensures that the algorithm always evaluates the output difference with the highest probabilities first. Consequently, once a difference is found whose probability fails to meet the search condition, the algorithm can immediately break the unnecessary branches. This significantly reduces the search space and thus speeds up the search for the differential trail. Secondly, Liu et al. found that the size of CDDT is inversely proportional to the execution time of the search algorithm and directly proportional to the required storage space. If a large CDDT is used, the memory complexity of calculating the optimal differential trail will be large. On the contrary, if a small CDDT is used, the time complexity of calculating the optimal differential trail will be large. They used an 8-bit CDDT to achieve a balance between time complexity and memory complexity in Liu et al. (2021).
In this paper, we employ a time-space trade-off method to establish an 8-bit CDDT for searching valid differential trails in Schwaemm. While we reference the work of Liu et al. (2021), we do not directly use their improved Matsui’s algorithm due to specific limitations when applied to the Alzette in Schwaemm. Specifically, this algorithm was designed to find the optimal differential trails; however, for Alzette, the number of optimal differential trails is notably large. Moreover, optimal differential trails may not yield optimal differentials due to cluster effects and the frequent situations where some trails prove invalid due to the absence of actual conforming pairs. Consequently, we broadened our search to include differential trails within a specific probability range rather than focusing solely on optimal ones. Furthermore, we use the CDDT method proposed by Liu et al. to determine the probability of specific differential trails given known input and output differences of Alzette. Once a differential trail is identified, we employ a time-space trade-off method to derive concrete pairs that conform to this trail, thus guaranteeing its validity.
Differential-linear cryptanalysis
In the following, we recall the common framework of differential-linear approximation and the success probability of a key-recovery attack in the differential-linear context.
The cryptographic algorithm E consists of subsystems \(E_0\) and \(E_1\). Assuming that \(\Delta _{in}\) and \(\Delta _{out}\) are the input differential and output differential corresponding to the \(E_0\) stage respectively. The probability of the differential \(\Delta _{in} \rightarrow \Delta _{out}\) is p, that is, \(\operatorname {Pr} [E_0 (P) \oplus E_0(P \oplus \Delta _{in}) = \Delta _{out} ] = p\). \(\gamma _{in}\) and \(\gamma _{out}\) are the input mask and output mask corresponding to the linear trails of the \(E_1\) stage respectively. The probability of linear approximation \(\gamma _{in} \rightarrow \gamma _{out}\) is \(1/2 + q\) (or with bias q), that is, \(\operatorname {Pr} [\gamma _{in} \cdot W = \gamma _{out} \cdot E_1 (W)] = 1/2 + q\), where “\(\cdot\)” denotes the inner product between two vectors. Assume that the subsystems \(E_0\) and \(E_1\) are independent of each other, the probability of the differential-linear distinguisher can be estimated as \(\operatorname {Pr} [\gamma _{out} \cdot E(P) = \gamma _{out} \cdot E(P \oplus \Delta _{in})] = p(1/2 + 2q^2)+(1 - p) \cdot 1/2 = 1/2 + 2pq^2\). The data complexity of the differential-linear distinguisher is \(O(p^{-2}q^{-4})\).
Searching differential-linear trails of Schwaemm
In the subsequent discussion, we detail the approach for Schwaemm128-128, which utilizes the Sparkle256 permutation. This methodology is also applicable to other versions of Schwaemm.
Our study focuses on the initialization phase of Schwaemm. The subsequent analysis focuses on the DL trail applicable during this phase of Schwaemm128-128, which utilizes the four-branch permutation Sparkle256. The inputs include public nonce and secret key. The nonce occupies the 0th and 1st branches, while the key occupies the 2nd and 3rd branches. For a successful attack under a single key setting, the 0-round input differences \(\Delta _2^0\) and \(\Delta _3^0\) of the DL trail must both be zero. During the attack, the attacker has access to only the 0th and 1st branches of the output from the Sparkle256 permutation. The 2nd and 3rd branches remain concealed, necessitating that the output linear masks be non-zero only in the 0th and 1st branches, and zero in the inaccessible branches. This establishes the preconditions for a valid DL trail used in the initialization phase of Schwaemm128-128. Upon satisfying these preconditions, a DL trail can be identified.
Figure 1 exemplifies this by illustrating a 4-round DL trail. This trail consists of a 2-round concrete differential trail over the subsystem \(E_0\), a 1.5-round truncated differential trail over \(E_1\), and a 0.5-round linear trail over \(E_2\).
Probability of DL trail and distinguisher. Suppose that the probability of the 2-round differential trail over the subsystem \(E_0\) is \(p_0\), the probability of the 1.5-round truncated differential trail over \(E_1\) is \(p_1\), and the probability of the 0.5-round linear trail over \(E_2\) is \(p_2=\frac{1}{2}(1+q)\). According to the 4-round DL trail given in Fig. 1, the theoretical probability of this trail, denoted as \(p_{\text {trail}}\), is \(p_{\text {trail}} = \frac{1}{2}(1+p_0 \cdot p_1 \cdot q^2)\). In our attack, since \(p_0 = \operatorname {Pr} \left[ \Delta _0^1 \rightarrow \nabla _0^1 \right]\), \(p_1 = 1\), and \(p_2 =1\), this simplifies to \(p_{\text {trail}} = \frac{1}{2}(1+\operatorname {Pr} \left[ \Delta _0^1 \rightarrow \nabla _0^1 \right] )\) for the initialization phase of Schwaemm.
In short, the (4-round) DL trail is used to construct a practical distinguisher which operates by checking whether a 64-bit linear equation holds. The success probability of this distinguisher, denoted as \(p_{\text {dist}}\), is given by \(p_{\text {dist}} = p_0+(1-p_0) \cdot 2^{-64}\). For a sufficiently large \(p_0\) (i.e., \(p_0 \gg 2^{-64}\)), this probability can be approximated as \(p_{\text {dist}} \approx p_0 = \operatorname {Pr} \left[ \Delta _0^1 \rightarrow \nabla _0^1 \right]\).
Procedure of searching 4-round DL trail.
The method of searching the 4-round DL trail is described as follows, as illustrated in Fig. 1.
-
1.
Fix the target differential probability, see Section “Calculating differential trails”. (the green region in Fig. 1) Choose a target probability (\(p \le 2^{-6}\) because the highest differential-trail probability for Alzette is \(2^{-6}\)) for the trail \(\Delta _0^1 \rightarrow \nabla _0^1\). Using the improved Matsui’s algorithm of Liu et al. (2021), search for trails \(\Delta _0^1 \rightarrow \nabla _0^1\) that meet the target probability p.
-
2.
Propagate through the linear layer \(\mathcal {M}_2\) , see Section “Calculating differential trails”. (the purple region in Fig. 1) From the output difference \((\Delta _0^1, 0)\) of the first linear layer, compute the corresponding input differences \((\Delta _3^1, \Delta _2^1)\). Similarly, from the input difference \((0, \nabla _0^1)\) of the second linear layer, compute the output differences \((\nabla _3^1, \nabla _2^1)\).
-
3.
Determine middle trails, see Section “Calculating middle trail”. (the blue region in Fig. 1) Given \((\Delta _3^1, \Delta _2^1)\) and \((\nabla _3^1, \nabla _2^1)\) from Step 2, apply the middle-trail calculation algorithm (Algorithm 1) to decide whether the Alzette trails \(\Delta _2^1 \rightarrow \nabla _2^{1}\) and \(\Delta _3^1 \rightarrow \nabla _3^{1}\) exist and to evaluate their probabilities.
-
4.
Enumerate conforming pairs with the value-calculation algorithm, see Section “Calculating the values satisfying middle trail”. (the red region in Fig. 1) Once the middle differential trails \(\Delta _2^1 \rightarrow \nabla _2^{1}\) and \(\Delta _3^1 \rightarrow \nabla _3^{1}\) are fixed, apply the value-calculation algorithm (Algorithm 3) to enumerate the state pairs that satisfy each trail. Combining the resulting sets yields many pairs realizing the joint differential propagation \((\Delta _2^1, \Delta _3^1) \rightarrow (\nabla _2^{1}, \nabla _3^{1})\). From these, derive nonce pairs that satisfy the overall 4-round DL with input differences \((\Delta _0^0, \Delta _1^0, 0, 0)\) and, at the input of \(E_1\), intermediate differences \((0, 0, \nabla _0^{1}, 0)\).
Here, we emphasize that our method is applicable to all versions of Schwaemm, that is, Schwaemm128-128, Schwaemm256-128, Schwaemm192-192, and Schwaemm256-256.
Calculating differential trails
We employ the improved Matsui’s algorithm of Liu et al. (2021) to search for trails \(\Delta _0^1 \rightarrow \nabla _0^1\) under a target probability p. Once such a trail is fixed, we propagate differences through the linear layer \(\mathcal {M}_2\): from the output difference \((\Delta _0^1, 0)\) we recover the corresponding input differences \((\Delta ^{1}_{3}, \Delta ^{1}_{2})\) by applying \(\mathcal {M}_2^{-1}\); symmetrically, from the input difference \((0, \nabla _0^1)\) we obtain the output differences \((\nabla _3^1, \nabla _2^1)\). This procedure corresponds to the green and purple regions in Fig. 1.
Because the highest differential-trail probability for Alzette is \(2^{-6}\), we take \(p\le 2^{-6}\). Reducing p substantially increases the number of trails (and the time needed to enumerate them), so we restrict our search to \(2^{-13}\le p\le 2^{-6}\). For each p in this range, Table 8 reports the number of trails \(\Delta _0^{1} \rightarrow \nabla _0^{1}\), alongside the corresponding counts of middle differential trails \((\Delta _2^{1},\nabla _2^{1})\) and \((\Delta _3^{1},\nabla _3^{1})\). Furthermore, Table 9 and Table 10 give the number of middle differential trails of Alzette for the remaining versions of Schwaemm.
Calculating middle trail
In Section “Calculating differential trails”, we use the improved Matsui’s algorithm to obtain candidates for the trails \(\Delta ^{1}_{0}\!\rightarrow \!\nabla ^{1}_{0}\). Propagating these differences through the linear layer \(\mathcal {M}_{2}\) yields \((\Delta ^{1}_{2},\Delta ^{1}_{3})\) and \((\nabla ^{1}_{2},\nabla ^{1}_{3})\). We now determine the middle trails consisting \(\Delta ^{1}_{2}\!\rightarrow \!\nabla ^{1}_{2}\) and \(\Delta ^{1}_{3}\!\rightarrow \!\nabla ^{1}_{3}\) admitted by Alzette and evaluate their probabilities. To this end, we apply the middle-trail calculation algorithm, a segment-matching procedure based on forward and reverse CDDTs; it returns both the concrete trails and their theoretical probabilities. This entire matching procedure corresponds to the blue region in Fig. 1.
Middle trail calculation algorithm
We solve the middle-trail calculation problem by matching 16-bit slices computed forward and backward, augmented with carry/borrow metadata. Throughout, \(\textrm{CDDT}_{c}\) denotes the forward table and \(\textrm{CDDT}'_{c}\) the reverse table of Alzette with round constant c. Let \((\Delta x^{(0)},\Delta y^{(0)})\) and \((\Delta x^{(4)},\Delta y^{(4)})\) be the known input and output differences. The procedure proceeds as follows.
This procedure functions as a multi-stage meet-in-the-middle (MITM) search that decomposes the 64-bit state matching problem into four successive 16-bit slice comparisons. The process begins with a Forward Phase (Rounds \(0 \rightarrow 2\)) which pre-computes intermediate differences \((\Delta x^{(1)}, \Delta y^{(1)})\) and the first 16-bit difference slice (\(\textrm{col}_0\)) along with its outgoing carry (\(c^{(0)}\)) and stores them in a hash table \(T_0\). This is followed by a Backward Phase (Rounds \(3 \rightarrow 2\)) which iteratively computes difference slices (\(\textrm{col}'_k\)) and their required incoming borrow bits (\(b^{(k)}\)).
The core of the attack is the slice-by-slice joining: Starting with Stage 0, the backward-computed slice \(\textrm{col}'_0\) is matched against the indices stored in \(T_0\). For subsequent stages (Stage 1 to Stage 3), local hash tables (\(T_1, T_2, T_3\)) are built using the backward calculation. The forward path is then checked against these local tables. This ensures that only candidates whose forward and backward components are linked by consistent carry/borrow metadata across consecutive 16-bit slices survive to the next stage. A match in the final stage (Stage 3) completes the full middle difference \((\Delta x^{(2)},\Delta y^{(2)})\), allowing the 4-round trail and its total theoretical probability to be reconstructed.
The entire procedure, including the definition of the four matching stages (Stage 0 to Stage 3), is detailed in Algorithm 1. The specific differential operators used for slicing and incorporating carry/borrow bits are listed in Table 4.
Complexity Analysis. The computational cost of the middle-trail calculation comprises a one-time offline precomputation and an online candidate matching phase.
First, constructing the CDDT involves enumerating 8-bit modular addition transitions (\(2^8 \times 2^8 \times 2^8 = 2^{24}\) operations per slice). For a 32-bit state processed via four sequential slices, this fixed offline cost is approximately \(2^{26}\) operations.
Second, let N denote the number of input 32-bit candidate differences. By utilizing the CDDT as an \(\mathcal {O}(1)\) array-indexed filter, the matching phase processes these candidates with a strictly linear time complexity of \(\mathcal {O}(N)\).
In summary, the time and memory complexities are bounded by \(\mathcal {O}(2^{26} + N)\). Since \(N \ll 2^{26}\), the total complexity is effectively \(\mathcal {O}(2^{26})\).
Experimental results
For each \((\Delta ^{1}_{2},\nabla ^{1}_{2})\) and \((\Delta ^{1}_{3},\nabla ^{1}_{3})\), we run the middle-trail calculation algorithm (Algorithm 1) and record the number of admissible middle trails. The resulting counts are reported in Tables 8, 9, and 10 of Appendix A. This procedure applies generally to the initialization phase of all four Schwaemm variants – Schwaemm128-128, Schwaemm256-128, Schwaemm192-192, and Schwaemm256-256.
Calculating the values satisfying middle trail
In Section “Calculating middle trail”, we determined the middle trails \(\Delta ^{1}_{2}\!\rightarrow \!\nabla ^{1}_{2}\) and \(\Delta ^{1}_{3}\!\rightarrow \!\nabla ^{1}_{3}\) and their theoretical probabilities. We now compute concrete state pairs that satisfy these trails. The value-computation approach of Xiong and Liu (2023) requires prohibitive memory. To solve this problem, we modify and present a finer time-space trade-off: we evaluate two successive rounds at a time, materialize several small lookup tables keyed by selected bit slices together with the carry/borrow bits of the modular additions, and then join/verify candidates against the remaining two rounds.
Concretely, we enumerate values that satisfy two consecutive rounds, store them in compact tables, and subsequently traverse these tables to check whether the surviving candidates satisfy the other two rounds as well. When building the tables, we link them via carry/borrow metadata across consecutive rounds. We consider three two-round windows: rounds (0-1), (1-2), and (2-3). As a running example, we detail the (1-2) case: given a trail \((\Delta x^{(0)},\Delta y^{(0)}) \rightarrow (\Delta x^{(4)},\Delta y^{(4)})\), we enumerate all \((x^{(2)},y^{(2)})\) consistent with both \((\Delta x^{(2)},\Delta y^{(2)}) \rightarrow (\Delta x^{(1)},\Delta y^{(1)})\) and \((\Delta x^{(2)},\Delta y^{(2)}) \rightarrow (\Delta x^{(3)},\Delta y^{(3)})\); candidates that also validate across rounds 0 and 3 yield the desired \((x^{(0)},y^{(0)})\) pairs for the full trail. This procedure corresponds to the red region in Fig. 1. For a detailed illustration of this value calculation process, refer to Fig. 2, which will be discussed further below.
Value calculation algorithm
For the case of the 1st and 2nd rounds of Alzette, the method is to adopt a time-space trade-off method. By establishing multiple tables that occupy smaller memory, and traversing these tables in sequence, we can obtain the value \((x^{(2)}, y^{(2)})\) to satisfy \(({\Delta x}^{(2)}, {\Delta y}^{(2)}) \rightarrow ({\Delta x}^{(1)}, {\Delta y}^{(1)})\) and \(({\Delta x}^{(2) }, {\Delta y}^{(2)}) \rightarrow ({\Delta x}^{(3)}, {\Delta y}^{(3)})\).
Figure 2 illustrates our method for obtaining \((x^{(2)}, y^{(2)})\) from \(({\Delta x}^{(2)}, {\Delta y}^{(2)}) \rightarrow ({\Delta x}^{(1)}, {\Delta y}^{(1)})\) and \(({\Delta x}^{(2)}, {\Delta y}^{(2)}) \rightarrow ({\Delta x}^{(3)}, {\Delta y}^{(3)})\). In the case that \(({\Delta x}^{(0)}, {\Delta y}^{(0)}) \rightarrow ({\Delta x}^{(4)}, {\Delta y}^{(4)})\) and \(({\Delta x}^{(2)}, {\Delta y}^{(2)})\) is known, if we traverse \((x^{(2)}, y^{(2)})\), we can get all \(({\Delta x}^{(1)}, {\Delta y}^{(1)})\) and \(({\Delta x}^{(3)}, {\Delta y}^{(3)})\) via CDDT. Since the difference \(({\Delta x}^{(1)}, {\Delta y}^{(1)})\) is known, we can filter out all \((x^{(2)}, y^{(2)})\) that do not satisfy the forward propagation \(({\Delta x}^{(2)}, {\Delta y}^{(2)}) \rightarrow ({\Delta x}^{(1)}, {\Delta y}^{(1)})\) and the backward propagation \(({\Delta x}^{(2)}, {\Delta y}^{(2)}) \rightarrow ({\Delta x}^{(3)}, {\Delta y}^{(3)})\).
Since it is impossible to traverse the 64-bit \((x^{(2)}, y^{(2)})\), it needs to be traversed in parts. From \((x^{(2)}, y^{(2)})\), we can calculate \((x^{(1)}, y^{(1)})\) and \((x^{(3)}, y^{(3)})\), so we use \((x^{(2)}, y^{(2)})\) to represent \((x^{(1)}, y^{(1)})\) and \((x^{(3)}, y^{(3)})\). We create the internal relationship between \((x^{(1)}, y^{(1)})\) and \((x^{(3)}, y^{(3)})\) under \((x^{(2)}, y^{(2)})\). Furthermore, modular addition and modular subtraction are nonlinear components in Alzette, so only \(x^{(1)}\) and \(x^{(3)}\) need to be considered, that is, using \((x^{(2)}, y^{(2)})\) represents \(x^{(1)}\) and \(x^{(3)}\). By derivation, we have
Based on the above two formulas, we determine the table partitioning for the 1st and 2nd rounds of Alzette, as illustrated in Fig. 3. In this representation, \((x^{(2)}, y^{(2)})\) is utilized to represent the states \(x^{(1)}\) and \(x^{(3)}\). As shown in Fig. 3, the top three lines correspond to the bit-slices \(y^{(2)}[16,\dots ,0] \parallel y^{(2)}[31,\dots ,17]\), \(x^{(2)}[1,0] \parallel x^{(2)}[31,\dots ,2]\), and \(x^{(2)}[31,\dots ,0]\) from top to bottom, respectively. The subsequent two lines represent \(y^{(2)}[31,\dots ,0]\) and \(x^{(2)}[31,\dots ,0]\).
To construct the search tables efficiently, the CDDT is employed as a foundational validity filter. Specifically, for each localized bit-slice, we query the CDDT to identify valid bit-combinations of \((x^{(2)}, y^{(2)})\); only those combinations consistent with the fixed differential carry-propagation (i.e., possessing a non-zero probability in the CDDT) are recorded. These pre-filtered lookup tables (A through H) are established in sequence according to the bit-dependency of the carry and borrow streams. These tables correspond directly to the differently colored functional blocks depicted in Fig. 3, where each color represents a specific bit-slice constraint and its associated carry propagation. Subsequently, these tables are traversed using a multi-stage piecewise matching strategy to obtain all potential values of \((x^{(2)}, y^{(2)})\) that satisfy the differential transitions \(({\Delta x}^{(2)}, {\Delta y}^{(2 )}) \rightarrow ({\Delta x}^{(1)}, {\Delta y}^{(1)})\) and \(({\Delta x}^{(2)}, {\Delta y}^{(2 )}) \rightarrow ({\Delta x}^{(3)}, {\Delta y}^{(3)})\). Finally, the retrieved candidates for \((x^{(2)}, y^{(2)})\) are verified against the remaining two rounds of the Alzette structure to ensure full-path consistency.
We give a detailed description of the optimized value calculation algorithm for the 1st and 2nd round of Alzette, which is used the most. As for the table partitioning of the 0th and 1st, and 2nd and 3rd rounds of Alzette, see also Figs. 7 and 8 in Appendix C, respectively.
Overall, the value calculation is executed in two primary phases: Phase 1: Table Creation and Phase 2: Sequential Traversal and Verification, which relies on a time-space trade-off method. This methodology avoids exhaustive search by breaking the problem into a series of computationally cheaper lookups and sequential verification steps.
Phase 1: Table Creation. The first phase creates eight lookup tables (A through H) by exhaustively traversing the bit-slices defined for the middle state \((x^{(2)}, y^{(2)})\). Each table stores combinations of state slices and their corresponding carry/borrow bits that satisfy the local differential propagation across the 1st and 2nd rounds of Alzette. The detailed procedure is provided in Algorithm 2.
Phase 2: Sequential Traversal and Verification. The second phase sequentially traverses the generated tables (A through H), using nested loops and shared carry/borrow bits (\(c_i\) and \(b_i\)) as linking keys to progressively reconstruct the full 64-bit middle state \((x^{(2)}, y^{(2)})\). The detailed procedure is provided in Algorithm 3. The final step of Algorithm 3 returns a state satisfying the 4-round differential trail.
Complexity Analysis. The complexity is analyzed in two distinct functional phases.
Phase 1 (Table Filtering): This phase constructs the lookup tables (A through H). For each state slice, the algorithm identifies valid bit-combinations (x, y) that are consistent with the fixed differential trail. The CDDT serves as the benchmark: if the CDDT returns a forbidden value for a specific differential transition, all corresponding bit-values are excluded. The complexity of this phase is dominated by the search space required to identify these valid bit-entries, peaking at \(\mathcal {O}(2^{20})\) for Table A.
Phase 2 (Value Reconstruction): This phase performs the actual traversal of the pre-filtered tables. Although implemented as nested loops (Algorithm 3), this is a highly efficient matching process rather than a brute-force search. The time complexity of this phase is linear relative to the number of recovered values, which is negligible compared to Phase 1.
Summary: The overall bottleneck is the pre-filtering of bit-values in Phase 1, resulting in an effective complexity of \(\mathcal {O}(2^{20})\).
Experimental results
Assume that among the 4-round differential trails of Alzette, the probability of the differential trails in ith round is p[i], that is, \(p \left[ i \right] = \operatorname {Pr} \left[ ({\Delta x}^{(i)}, {\Delta y}^{(i)}) \rightarrow ({\Delta x}^{(i + 1)}, {\Delta y}^{(i + 1)}) \right]\). Using the optimized algorithms of the table partitioning given above, we can get the value of all differential trails \(\Delta _2^1 \rightarrow \nabla _2^1\) and \(\Delta _3^1 \rightarrow \nabla _3^1\) in Tables 8, 9 and 10 of Appendix A. In the process of using the three optimized algorithms, we need to follow the following rules. If \(p[0]+p[1] \le p[1]+p[2]\) and \(p[0]+p[1] \le p[2]+p[3]\), we use the optimized algorithms of the 0th and 1st round of Alzette. If \(p[1]+p[2] \le p[0]+p[1]\) and \(p[1]+p[2] \le p[2]+p[3]\), we use the optimized algorithms of the 1st and 2nd round of Alzette. If \(p[2]+p[3] \le p[0]+p[1]\) and \(p[2]+p[3] \le p[1]+p [2]\), we use the optimized algorithms of the 2nd and 3rd round of Alzette. We obtain the experimental results shown in Tables 11, 12 and 13 of Appendix A.
The linear trail and bias calculation
We now turn our attention to the linear part of the DL trail. If we move the 0th branch to the 1st branch of Sparkle256 in 0th round, we will get another 4-round DL trail with the same probability. We denote the 4-round DL trail of \(\Delta _0^1 \rightarrow \nabla _0^1\) in the 0th branch of Sparkle256 as trail 1 and the 4-round DL trail of \(\Delta _0^1 \rightarrow \nabla _0^1\) in the 1st branch of Sparkle256 as trail 2. Next, we focus only on deriving the relationship for trail 1. The analysis applies similarly to trail 2.
Derive the relationship between \(\gamma _0^4\) and \(\gamma _1^4\). Assume that the input value of the linear transformation \(\mathcal {M}_2\) is \(\vec {x}=\left( x_{127}, \ldots , x_0\right) ^T\), the output value is \(\vec {y}=\left( y_{127}, \ldots , y_0\right) ^T\), the input mask is \(\vec {\gamma }=\left( \gamma _{127}, \ldots , \gamma _0\right)\) and the output mask is \(\vec {\Gamma }=\left( \Gamma _{127}, \ldots , \Gamma _0\right)\). We get \(\vec {y}=\mathcal {M}_2 \cdot \vec {x}\) and \(\vec {\Gamma }=\vec {\gamma } \cdot \mathcal {M}_2^{-1}\). In trail 1, we get \(\left( \Gamma _3^3, \Gamma _2^3 \right) = \left( 0, \Gamma _0^3\right) \cdot \mathcal {M}_2^{-1}\) via \(\vec {\Gamma } = \left( \Gamma _3^3, \Gamma _2^3 \right)\), \(\vec {\gamma } = \left( 0, \Gamma _0^3 \right)\). Because \(\Gamma _3^3 = \gamma _0^4\), \(\Gamma _2^3 = \gamma _1^4\) and \(\mathcal {M}_2^{-1} = \mathcal {M}_2\) where \(\mathcal {M}_2\) is a symmetric matrix, \(\left( \gamma _0^4, \gamma _1^4 \right) = \left( 0, \Gamma _0^3 \right) \cdot \mathcal {M}_2^{-1} = \left( 0, \Gamma _0^3 \right) \cdot \mathcal {M}_2\). Partition the matrix \(\mathcal {M}_2\) into blocks, let \(A=\left[ \begin{array}{llll}O & O & O & I \\ O & O & I & I \\ O & I & O & O \\ I & I & O & O\end{array}\right]\), \(B=\left[ \begin{array}{cccc}I & O & O & I \\ O & I & I & I \\ O & I & I & O \\ I & I & O & I\end{array}\right]\). We get \(\left( \gamma _0^4, \gamma _1^4 \right) = \left( 0, \Gamma _0^3 \right) \cdot \left[ \begin{array}{ll}B & A \\ A & B\end{array}\right] = \left( \Gamma _0^3 \cdot A, \Gamma _0^3 \cdot B \right)\), so \(\gamma _0^4 = \Gamma _0^3 \cdot A\) and \(\gamma _1^4 = \Gamma _0^3 \cdot B\). The relationship between \(\gamma _0^4\) and \(\gamma _1^4\) is
The bias of the DL distinguisher. Because \(\vec {\gamma } \cdot \vec {x} = \vec {\Gamma } \cdot \vec {y}\), \(\left( 0, \Gamma _0^3 \right) \cdot \vec {x} = \left( \gamma _0^4, \gamma _1^4\right) \cdot \vec {y}\). Let \(\vec {x} = \left( \overrightarrow{x^{\prime \prime }}, \overrightarrow{x^{\prime }} \right)\), \(\vec {y} = \left( \overrightarrow{y^{\prime \prime }}, \overrightarrow{y^{\prime }} \right)\), where \(\overrightarrow{x^{\prime \prime }} = \left( x_{127}, \ldots , x_{64}\right) ^T\), \(\overrightarrow{x^{\prime }} = \left( x_{63}, \ldots , x_0 \right) ^T\), \(\overrightarrow{y^{\prime \prime }} = \left( y_{127}, \ldots , y_{64} \right) ^T\), \(\overrightarrow{y^{\prime }} = \left( y_{63}, \ldots , y_0\right) ^T\). We get \(\left( 0, \Gamma _0^3 \right) \cdot \left( \overrightarrow{x^{\prime \prime }}, \overrightarrow{x^{\prime }} \right) = \left( \gamma _0^4, \gamma _1^4 \right) \cdot \left( \overrightarrow{y^{\prime \prime }}, \overrightarrow{y^{\prime }} \right)\), that is \(\Gamma _0^3 \cdot \overrightarrow{x^{\prime }} = \gamma _0^4 \cdot \overrightarrow{y^{\prime \prime }} \oplus \gamma _1^4 \cdot \overrightarrow{y^{\prime }} = \gamma _0^4 \cdot \overrightarrow{y^{\prime \prime }} \oplus \left( \gamma _0^4 \cdot A^{-1} \cdot B \right) \cdot \overrightarrow{y^{\prime }}\). In trail 1, we get \(\nabla _0^3 = 0\), that is \(\overrightarrow{x^{\prime }} = 0\), so
In the 4-round difference-linear distinguisher, we have \(\gamma = \left( \gamma _0^4, \gamma _1^4 \right)\), \(E(x) \oplus E(x \oplus \delta ) = \left( \Delta _0^4, \Delta _1^4 \right)\) and Formula 6, so
DL cryptanalysis of Schwaemm
In Section 3, we gave a 4-round DL trail of Schwaemm128-128. We first show how to use the 4-round DL trail to perform a distinguishing attack in Section 4.1. Then, by the property that the 0.5-round nonlinear layer Alzette can be inverted, we present a procedure of key-recovery attack on the 4.5-round initialization phase of Schwaemm, see Section 4.2.
Distinguishing attacks on Schwaemm
Suppose the number of nonce is N in a given 4-round DL trail of Schwaemm. As detailed in Algorithm 4, for an Oracle instantiated with a target cipher or a random function, if at least one output pair satisfies Formula 6, the distinguisher outputs Schwaemm; otherwise, it outputs Random function.
We evaluate the validity of this distinguisher from two aspects: On the one hand, if the Oracle is instantiated with 4-round Schwaemm with a secret key, the distinguisher expects to capture the biased linear correlation. Given the strictly limited data volume N, the empirical success probability of finding at least one conforming pair is evaluated experimentally. On the other hand, if the Oracle is a random function, the output differences are uniformly distributed. The probability that a single random output pair accidentally satisfies Formula 6 is \(2^{-64}\). Consequently, across N independent nonce pairs, the probability that the random function satisfies Formula 6 is approximately \(1 - (1 - 2^{-64})^N \approx N \cdot 2^{-64}\). Since our required data complexity \(N \ll 2^{64}\), this false positive probability is strictly negligible.
We use the trail numbered \(\{t\_\alpha \_1\}\) to perform the distinguishing attack on Schwaemm128-128. When \(P \left[ \Delta _0^1 \rightarrow \nabla _0^1 \right] = 2^{-8}\), we get the number of nonce \(\# \left[ (\Delta _0^0, \Delta _1^0) \right] = 2^{10.63}\) and the success probability of distinguishing attack is 100%. We use the trail numbered \(\{s\_\beta \_4\}\) to perform the distinguishing attack on Schwaemm256-128. When \(P \left[ \Delta _0^1 \rightarrow \nabla _0^1 \right] = 2^{-10}\), we get the number of nonce \(\# \left[ (\Delta _0^0, \Delta _1^0) \right] = 2^{13.06}\) and the success probability of distinguishing attack is 100%. We use the trail numbered \(\{s\_\beta \_4\}\) to perform the distinguishing attack on Schwaemm192-192. When \(P \left[ \Delta _0^1 \rightarrow \nabla _0^1 \right] = 2^{-10}\), we get the number of nonce \(\# \left[ (\Delta _0^0, \Delta _1^0) \right] = 2^{13.06}\) and the success probability of distinguishing attack is 100%. We use the trail combination \(\{w\_\beta \_0 \cup w\_\beta \_1\}\) to perform the distinguishing attack on Schwaemm256-256. When \(P \left[ \Delta _0^1 \rightarrow \nabla _0^1 \right] = 2^{-9}\), we get the number of nonce \(\# \left[ (\Delta _0^0, \Delta _1^0) \right] = 2^{9.58} + 2^{8} = 2^{9.81}\) and the success probability of distinguishing attack is 12.10%. The success probability for the attack on Schwaemm256-256 is lower than those for the other variants since there are few high-probability trails found in our experiments. This is due to the complex permutation Sparkle512 used in Schwaemm256-256, leading to difficulty in finding available nonce pairs.
The results for these attacks are summarized in Table 5.
Key-recovery attacks on Schwaemm
Since the final 0.5-round of Alzette can be cleanly inverted, our 4-round DL distinguishers naturally extend to 4.5-round key-recovery attacks on Schwaemm. In Section “Key-recovery attacks with multiple DL trails”, we introduce a multi-trail combination strategy to enhance filtering power. Based on this, Section “Algorithmic procedure and complexity analysis” presents the algorithmic procedure using a memory-efficient TMTO technique, detailing the full key-recovery results for all variants. Finally, Section “Key-recovery attacks with equations” demonstrates how to extract bit-level linear equations from the modular addition. By directly recovering partial key bits, this approach further bypasses the filtering bottleneck, leading to a significantly lower time complexity for the full key recovery.
Key-recovery attacks with multiple DL trails
In our key-recovery attacks on Schwaemm, we explore and implement a strategy that combines multiple effective DL trails. This approach aims not only to enhance the key recovery success rate and potentially reduce the required time complexity, but also to increase the number of directly recoverable key bits.
Attack Theory and Methodology. The core idea is that the correct key should consistently exhibit the expected zero-correlation property under multiple independent or partially independent DL trails. In ARX-based structures, the differential probability is directly linked to the state constraints. For a 64-bit equivalent subkey targeted by an active differential branch, a single DL trail with a differential probability of \(2^{-p}\) inherently imposes p independent bit-level equations on the internal state. Consequently, satisfying this specific trail theoretically reduces the candidate key space to \(2^{64-p}\). When multiple DL trails are utilized, their combination strategy fundamentally influences the efficiency and the filtering capability of the final key recovery:
-
“AND\(\cap\)”-combination Strategy: If multiple trails are statistically independent, and a key is required to simultaneously satisfy the zero-correlation conditions of all these trails, their combined filtering probability becomes the product of the individual probabilities. For instance, if two independent trails have filtering probabilities of \(2^{-p}\) and \(2^{-q}\), the combined probability drops to \(2^{-(p+q)}\). Consequently, the candidate key space is drastically narrowed down to \(2^{64-(p+q)}\). Moreover, the linear equations derived from this combined approach are the union of those from the individual trails, enabling the direct recovery of a significantly larger number of key bits.
-
“OR\(\cup\)”-combination Strategy: If we only require a key to satisfy the condition of any one of the multiple trails, the filtering power is inherently reduced. The remaining candidate key space becomes the union of the surviving keys from each trail, bounded by \(\mathcal {O}(2^{64-\min (p,q)})\). In this scenario, the attack branches, and the number of recovered equations in each branch is dynamically determined by the specific trail that is satisfied. However, this strategy is highly robust: it guarantees a much higher overall attack success rate, as the key recovery succeeds as long as at least one trail is valid.
In our implementation, the attack procedure integrates a hybrid of both strategies. To minimize the time complexity of the exhaustive search phase, we prioritize the “AND”-combination strategy, which maximizes the number of directly recoverable key bits and heavily prunes the search space. Conversely, to ensure a high empirical success rate, we incorporate the “OR”-combination as a fallback mechanism. The specific choice dynamically depends on the independence relationships among the trails and the individual distinguishing success rates. This flexible framework allows our attack to optimally balance time complexity and success rate based on practical constraints.
Algorithmic procedure and complexity analysis
Building upon the theoretical foundations of multi-trail combinations, we now detail the algorithmic procedure of the general key-recovery attack. The core strategy employs a divide-and-conquer approach, independently filtering the subkeys of different branches before combining them for a final verification. To elegantly manage the memory footprint, we adopt a stream-based Time-Memory Trade-Off (TMTO) technique during the combination phase.
In general, the master key of the Schwaemm family is divided into n 64-bit branches. Here, we take Schwaemm128-128 (\(n=2\)) as a concrete example to illustrate the procedure. Its 128-bit master key is divided into two branches, denoted as Branch \(\alpha\) and Branch \(\beta\). Assuming the required nonce pairs have been collected, the core attack proceeds in the following three steps:
-
1.
Data Collection and Filtering Branch \(\alpha\): First, we utilize the 4-round DL distinguisher (Algorithm 4) under the target secret key to query the Oracle and pre-filter the chosen nonces, extracting the “right pairs” that successfully exhibit the expected distinguishing properties. These pairs are immediately inverted by 0.5 rounds to recover the internal states required for the subsequent evaluation. Next, we evaluate all \(2^{64}\) candidate 64-bit subkeys for Branch \(\alpha\). A candidate is deemed valid only if it satisfies the local differential requirements of the corresponding DL trails. To explicitly optimize memory, the surviving subkey space \(\mathcal {K}_\alpha\) is stored in a hash table.
-
2.
Data Collection and Filtering Branch \(\beta\): Similarly, we first extract and invert the right pairs for Branch \(\beta\) by querying the Oracle with its respective 4-round DL distinguishers. We then independently evaluate the candidate subkeys for Branch \(\beta\) offline. However, instead of explicitly storing the surviving candidates \(\mathcal {K}_\beta\), we process them dynamically as a continuous data stream.
-
3.
Recombination and Verification: The moment a candidate subkey \(\nu _\beta\) survives the local filtering in Step 2, we immediately combine it with every \(\nu _\alpha \in \mathcal {K}_\alpha\) currently stored in the hash table to derive the 128-bit master key MK. This candidate MK is then subjected to the 4.5-round Schwaemm encryption using the known reference tuple to verify its absolute correctness and uniquely identify the true master key.
The formal algorithm for this memory-efficient procedure is presented in Algorithm 5.
Complexity Analysis. The efficiency of Algorithm 5 is evaluated across three dimensions:
-
Data Complexity: The data complexity is bounded by \(\mathcal {O}(N)\), where N is the total number of chosen nonce pairs required to evaluate the DL distinguishers for both \(\mathcal {T}_\alpha\) and \(\mathcal {T}_\beta\) with a reliable success probability.
-
Time and Memory Complexity: A naive exhaustive search over the entire 128-bit key space would require a prohibitive \(\mathcal {O}(2^{128})\) time complexity. Our strategy dramatically reduces this by independently filtering the branches. The filtering phase strictly takes \(2 \times 2^{64} = 2^{65}\) operations, followed by a cross-verification phase demanding \(|\mathcal {K}_\alpha | \times |\mathcal {K}_\beta |\) trial encryptions. Thus, the overall time complexity plummets to \(\mathcal {O}(2^{65} + |\mathcal {K}_\alpha | \times |\mathcal {K}_\beta |)\). Simultaneously, rather than naively storing all surviving candidates (which requires \(\mathcal {O}(|\mathcal {K}_\alpha | + |\mathcal {K}_\beta |)\) memory), our asymmetric stream-based TMTO strategy processes one branch dynamically as a data stream. This strictly optimizes the memory complexity to \(\mathcal {O}(\min (|\mathcal {K}_\alpha |, |\mathcal {K}_\beta |))\), completely eliminating the storage overhead of the larger branch while retaining the accelerated time complexity.
Extension to Multi-Branch Variants (\(n \ge 3\)). For Schwaemm variants with more branches, such as Schwaemm192-192 (\(n=3\)), this stream-based TMTO strategy naturally generalizes. Assuming the master key is divided into n branches, we independently filter all branches to obtain their respective surviving spaces \(\mathcal {K}_i\). To minimize the memory footprint, we identify the branch with the largest surviving space to act as the dynamic data stream, while pre-computing and explicitly storing the remaining \(n-1\) smaller surviving spaces in tables. Consequently, while the time complexity of the cross-verification phase inevitably scales multiplicatively (reaching \(\prod _{i=1}^n |\mathcal {K}_i|\)), the memory complexity scales only additively, strictly bounded by the sum of the surviving spaces of the remaining \(n-1\) smaller branches. This additive memory growth effectively circumvents the exponential memory explosion typical of multi-branch exhaustive combinations.
Full Key Recovery Results. We apply this procedure to all Schwaemm versions. For Schwaemm128-128, we present two configurations representing different time-success trade-offs.
In the first configuration, aiming for minimal time complexity, we first evaluate the trail set \(\{t\_\beta \_1 \cap t\_\beta \_2 \cap t\_\beta \_12 \cap t\_\beta \_16\}\) for Branch \(\beta\). Its surviving space is reduced to \(2^{27}\), which we explicitly store in the memory hash table. For Branch \(\alpha\), combining \(\{t\_\alpha \_0 \cap t\_\alpha \_7 \cap t\_\alpha \_8\}\) yields a surviving space of \(2^{37}\). By dynamically streaming the \(2^{37}\) candidates of Branch \(\alpha\) against the stored Branch \(\beta\), the cross-verification phase traverses \(2^{37} \times 2^{27} = 2^{64}\) combinations. Including the initial filtering stage, the total time complexity is approximately \(2^{64}+2^{64}+2^{64}=2^{65.58}\) with a memory footprint strictly bounded by \(2^{27}\) and an overall key recovery success probability of \(2^{-17.93}\).
Alternatively, to achieve a much higher success rate, we introduce a second configuration. We first evaluate the trail set \(\{t\_\beta \_16 \cap (t\_\beta \_0 \cup t\_\beta \_1 \cup t\_\beta \_3 \cup t\_\beta \_5 \cup t\_\beta \_8 \cup t\_\beta \_12)\}\) for Branch \(\beta\). Its surviving space is reduced to \(2^{43}\), which we explicitly store in the memory hash table. For Branch \(\alpha\), evaluating \(\{t\_\alpha \_1 \cap (t\_\alpha \_0 \cup t\_\alpha \_2 \cup t\_\alpha \_3)\}\) yields a surviving space of \(2^{49}\). By dynamically streaming the \(2^{49}\) candidates of Branch \(\alpha\) against the stored Branch \(\beta\), the cross-verification traverses \(2^{49} \times 2^{43} = 2^{92}\) combinations. This configuration achieves an impressive 54% overall success probability with a time complexity of \(2^{92}\), a data complexity of \(2^{15.73}\), and a memory footprint strictly bounded by \(2^{43}\).
Similar results for other variants, including multi-branch scenarios such as Schwaemm192-192 (\(n=3\)) and Schwaemm256-256 (\(n=4\)), are summarized in Table 6.
Key-recovery attacks with equations
Attack Theory and Methodology. While Section “Algorithmic procedure and complexity analysis” detailed the full key recovery utilizing the TMTO framework, we further demonstrate in this section that partial key information can be directly recovered by extracting bit-level algebraic equations. It is crucial to note that the equations established here are inherently formulated with respect to an equivalent key—defined as the internal state immediately following the initial, invertible Alzette permutation applied to the original master key. Since this permutation is strictly bijective, imposing linear constraints on this equivalent key is cryptographically isomorphic to constraining the original key. The direct recovery of these equivalent key bits yields a critical practical advantage: it substantially prunes the initial subkey space before the TMTO cross-verification. This directly and significantly accelerates the exhaustive evaluation phases—specifically, the computationally heavy loops over the candidate subkeys (i.e., Line 11 and Line 30) in Algorithm 5.
The successful extraction of these bit-level algebraic equations relies on identifying a right nonce pair that successfully traverses the specific differential path \(\Delta _0^1 \rightarrow \nabla _0^1\). By leveraging such a pair, we can characterize the propagation characteristics of this differential path by analyzing its internal mathematical properties, specifically through the establishment of corresponding mathematical equations.
According to the first round of Schwaemm128-128 illustrated in Fig. 4, we know that \(\omega \oplus \nu = x_0 || y_0\). Here, \(\omega\) and \(\nu\) are 64-bit values, while \(x_0\) and \(y_0\) are the 32-bit values being concatenated. Crucially, this value \(x_0 || y_0\) serves as the input to the differential path \(\Delta _0^1 \rightarrow \nabla _0^1\). This implies that by studying the internal properties of the Alzette permutation, we can establish mathematical equations concerning \(x_0\) and \(y_0\). Since \(\omega\) is a known value derived from the nonce and the diffusion layer, any such equation on \(x_0\) and \(y_0\) is directly equivalent to a relation that must be satisfied by the bits of \(\nu\). As \(\nu\) is the output of the secret key after a single, invertible Alzette permutation, we can treat it as an equivalent key. Consequently, the derived relations become equations for this equivalent key. The linear ones among these equations provide direct linear constraints on the original key bits, thus allowing for the recovery of a number of key bits equal to the number of independent linear equations found.
We now analyze the mathematical properties of the Alzette permutation, focusing on its most critical component: the modular addition operation. For the modular addition \(x \boxplus y\), the differential propagation at the i-th bit (starting from 0) can be expressed as a series of bit-level equations. Crucially, the non-linear part involves the carry bits. We define \(\text {carry}(x,y)[i]\) as the i-th bit of the carry vector for \(x \boxplus y\). By definition, we have \(x[i] \boxplus y[i] = x[i] \oplus y[i] \oplus \text {carry}(x,y)[i]\). The carry bit can be expressed as:
while \(\text {carry}(x,y)[0]\) is 0. Based on this bit-level analysis, given a specific differential path such as \(\Delta _0^1 \rightarrow \nabla _0^1\), we can formulate a complete set of corresponding equations.
With the bit-level relations of modular addition established, we can now determine the conditions for any specific differential propagation (Bao et al. 2023). For cases involving complex interactions across adjacent bits, such as a differential where an input difference in x at bit \(a+2\) and in y at bit \(a+1\) results in an output difference in z at bits a and \(a+1\), manual derivation can be cumbersome. Therefore, we employ an exhaustive search algorithm to automatically deduce the local differential propagation equations. To make this search tractable, the algorithm first isolates a small window of W consecutive bits, starting from a reference bit position a, chosen to cover the active differential. Within this window, it exhaustively searches all possible input combinations to identify the subset that satisfies the given differential transition. The resulting set of valid solutions is then analyzed to find any consistent linear relationships. Specifically, for each bit offset k (\(0 \le k < W\)) within the window, which corresponds to the actual bit position \(a+k\), the algorithm checks if the linear expressions \(x[a+k] \oplus y[a+k]\), \(x[a+k] \oplus c[a+k]\), and \(y[a+k] \oplus c[a+k]\) (where c represents the internal carry vector) evaluate to a constant value across all valid solutions. For details, see Algorithm 6. The diagrams illustrating the first round of the other Schwaemm versions (Schwaemm256-128/Schwaemm192-192 and Schwaemm256-256) are provided in Figs. 5 and 6, respectively.
Case Study: Path \(t\_\alpha \_0\). Let us consider Path \(t\_\alpha \_0\) as an example to elaborate on key-recovery attacks with linear equations (see also the first row of Table 11 in Appendix B). For clarity, this path identifier is an internal label, where the \(\alpha\) signifies that this specific trail is located in the 0th branch of Sparkle256.
Specifically, the given differential characteristic is \(\Delta _0^1 \rightarrow \nabla _0^1 = (\texttt{0x60008140}, \texttt{0x000040A0}) \rightarrow (\texttt{0x80000100}, \texttt{0x01008001})\), which can be summarized by its active input and output bit positions as \(([6,8,15,29,30],[5,7,14]) \rightarrow ([8,31],[0,15,24])\). Given these, the detailed 4-round propagation trail within Alzette is as follows: \(([6,8,15,29,30],[5,7,14]) \rightarrow ([29,31],[14]) \rightarrow ([31],[]) \rightarrow ([31],[0]) \rightarrow ([8,31],[0,15,24])\).
We establish its bit-level differential propagation equations within Alzette. As illustrated in Fig. 4, the differential propagation path from \(\Delta _0^1 = (\Delta x^{(0)},\Delta y^{(0)})\) to \(\nabla _0^1 = (\Delta x^{(4)},\Delta y^{(4)})\) is as described above. Here, we define \(x_j'\) and \(y_j'\) as intermediate variables after XORing with round constants and cyclic shifts, e.g., \(x_0'=x_0 \oplus c\) and \(y_0'=y_0 \ggg j\).
By feeding the specific input and output difference masks of this trail into our automated local exhaustive search (Algorithm 6), we systematically deduce the constraints for each modular addition. Consequently, the algorithm outputs the following seven bit-level equations that the equivalent secret key must satisfy:
Among these equations, the first five characterize the differential propagation properties of the first modular addition operation, the sixth characterizes the second modular addition, and the seventh characterizes the fourth modular addition. Crucially, the first four equations (the first two rows of Eq. 9) are strictly linear—comprising pure XOR sums without non-linear carry bit variables. Because \(\omega\) is known, these four linear relations translate directly into four deterministic linear constraints on the key bits, allowing for the immediate recovery of 4 bits of the secret key.
Linear Equation Recovery Results. Based on the deduced conditions, the key-recovery process involves two stages: finding a nonce pair that allows the traversal through a specific differential trail by the 4-round distinguisher and setting up the equations according to the found nonces. To build more equations, we exploit multiple trails. Here we take Schwaemm128-128 as an example to illustrate the attack procedure:
-
1.
Using the trail \(t\_\alpha \_1\) (see also Table 11 ), we obtain 8 equations (2 of which are linear) with success rate \(100\%\) by iteratively using Algorithm 6 in the current trail.
-
2.
-
(a)
Similarly, using the trail \(t\_\alpha \_0\), we obtain 7 equations (4 of which are linear) with success rate \(60.16\%\);
-
(b)
If the distinguisher fails in step 2, using \(t\_\alpha \_2\), obtain 8 equations (3 of which are linear);
-
(c)
If the above two distinguishers fail, using \(t\_\alpha \_3\), obtain 8 equations (3 of which are linear).
-
(a)
-
3.
For another branch, using the trail \(t\_\beta \_16\), we obtain 13 equations (2 of which are linear) with success rate \(99.46\%\).
-
4.
Similar to step 2, by using the trails \(t\_\beta \_0\), \(t\_\beta \_1\), \(t\_\beta \_3\), \(t\_\beta \_5\), \(t\_\beta \_8\), or \(t\_\beta \_12\), we obtain at least 8 equations (2 or 3 of which are linear).
Analysis. In total, we identify 36 equations on the key (including 9 linear equations), achieving a success rate of 54% (as listed in the second row of Table 7). The time and data complexities for this attack are determined by the total number of nonce pairs required across all utilized trails, resulting in a complexity of \(2^{15.73}\). The detailed results for all four versions of Schwaemm are summarized in Table 7.
Furthermore, for full key recovery, while the 9 linear equations directly determine 9 key bits, the remaining 27 non-linear equations provide 27 bits of filtering constraints. By exhaustively searching the remaining key space (\(128 - 36 = 92\) bits) to uniquely solve the system, the total time complexity for full key recovery is strictly bounded by \(2^{15.73} + 2^{92} \approx 2^{92}\). This is significantly lower than the \(2^{128}\) brute-force bound, demonstrating the high efficiency of the proposed attack. The comprehensive results for all four Schwaemm versions are summarized in Table 2.
Practical Verification and Theoretical Scaling. Furthermore, to experimentally validate the theoretical effectiveness of this equation-based framework, we consider a scenario where the key space is artificially constrained. From a generalized symbolic perspective, suppose the candidate subkey spaces for the two branches are reduced from \(2^{64}\) to \(2^{m_1}\) and \(2^{m_2}\), respectively, by pre-fixing a certain number of key bits. Under this setting, the independent filtering phase requires \(\mathcal {O}(2^{m_1} + 2^{m_2})\) operations. More importantly, the recovered \(N_{\textrm{eq}}\) equations directly reduce the exhaustive search space from \(2^{m_1 + m_2}\) down to \(\mathcal {O}(2^{m_1 + m_2 - N_{\textrm{eq}}})\). This algebraic pruning significantly reduces the overall theoretical complexity compared to the pure TMTO approach discussed in Section “Algorithmic procedure and complexity analysis”.
To instantiate this framework, we first demonstrate the practical recovery of an 80-bit target key. By uniformly fixing 24 bits in both branches of Schwaemm128-128, we set \(m_1 = m_2 = 40\). Utilizing the configuration from the second row of Table 7 (\(N_{\textrm{eq}} = 36\)), the recovered equations prune the cross-verification complexity from \(2^{80}\) down to \(2^{80-36} = 2^{44}\). As a result, the targeted 80-bit key was successfully recovered with a total time complexity of \(2^{40} + 2^{40} + 2^{44} \approx 2^{44.17}\), which is well within realistic computational limits.
Beyond experimental verification, we highlight the theoretical advantage of increased linear constraints in full 128-bit key recovery. As initially analyzed for the basic TMTO attack in Section “Algorithmic procedure and complexity analysis” (and summarized in the first row of Table 6), the baseline approach consumes \(2^{64} + 2^{64} + 2^{64} \approx 2^{65.58}\) operations. However, taking the exact equation count from the optimal configuration in the first row of Table 7 (\(N_{\textrm{eq}} = 64\), including \(N_{\textrm{lin}} = 16\) linear equations), the linear constraints effectively reduce the initial filtering space to \(2^{64-8} = 2^{56}\) per branch. Consequently, the total complexity plummets to \(2^{56} + 2^{56} + 2^{128-64} = 2^{57} + 2^{64} \approx 2^{64}\). This represents a substantial acceleration over the baseline \(2^{65.58}\) bound. By eliminating the filtering bottleneck through algebraic constraints, the total effort is reduced almost entirely to the cost of the final verification phase. This concretely demonstrates that gathering more linear equations is the most effective path to bypassing the inherent complexity limits of multi-branch differential-linear attacks.
Conclusion
In this paper, we evaluated the security of the Schwaemm family—specifically the 128-128, 256-128, 192-192, and 256-256 variants—against differential-linear (DL) cryptanalysis. We developed an optimized calculation algorithm to determine the precise values of differential trails with significantly improved efficiency. This methodology was successfully applied to identify DL approximations for the initialization phase across all Schwaemm versions, resulting in the discovery of practical 4-round DL distinguishers for every variant. Based on these distinguishers, we presented 4.5-round key-recovery attacks. Our contribution is two-fold: first, we proposed a stream-based Time-Memory Trade-Off (TMTO) multi-trail framework to achieve full key recovery with optimized memory and data complexities; second, we leveraged multiple DL trails to establish bit-level linear equations, enabling the direct recovery of partial key bits and significantly reducing the overall time complexity of the full key recovery process.
For future work, we intend to further refine our DL cryptanalysis methodology. First, the efficiency of our 2-round differential trail search can be enhanced through optimized table partitioning and parallel computing. Second, although our current approach identified numerous 4-round DL distinguishers for all Schwaemm variants, they have not yet been fully exploited in our key-recovery attacks. In the future, we aim to integrate these additional distinguishers to further increase the bit advantage. Finally, we plan to extend our analysis to the Esch hash function and the scalable output function XOEsch within the Sparkle family, as well as other lightweight primitives.
Data availability
Not applicable.
Notes
Two different constants c[0] and c[1] are actually used in original Schwaemm128-128.
References
Aumasson JP, Henzen L, Meier W, et al (2008) Sha-3 proposal blake. Submission to NIST 92. https://perso.uclouvain.be/fstandae/source_codes/hash_atmel/specs/blake.pdf
Bao Z, Lu J, Yao Y, et al (2023) More insight on deep learning-aided cryptanalysis. In: Guo J, Steinfeld R (eds) Advances in cryptology - ASIACRYPT 2023 - 29th international conference on the theory and application of cryptology and information security, Guangzhou, China, December 4-8, 2023, Proceedings, part III, lecture notes in computer science, vol 14440. Springer, pp 436–467, https://doi.org/10.1007/978-981-99-8727-6_15
Beaulieu R, Shors D, Smith J, et al (2013) The SIMON and SPECK families of lightweight block ciphers. IACR Cryptol ePrint Arch p 404. http://eprint.iacr.org/2013/404
Beierle C, Biryukov A, dos Santos LC, et al (2019) Schwaemm and esch: lightweight authenticated encryption and hashing using the sparkle permutation family. Submission to the NIST Lightweight Cryptography 2. https://csrc.nist.gov/CSRC/media/Projects/lightweight-cryptography/documents/finalist-round/updated-spec-doc/sparkle-spec-final.pdf
Beierle C, Biryukov A, dos Santos LC, et al (2020) Alzette: A 64-bit arx-box - (feat. CRAX and TRAX). In: Micciancio D, Ristenpart T (eds) Advances in cryptology - CRYPTO 2020 - 40th annual international cryptology conference, CRYPTO 2020, Santa Barbara, CA, USA, August 17-21, 2020, Proceedings, part III, lecture notes in computer science, vol 12172. Springer, pp 419–448, https://doi.org/10.1007/978-3-030-56877-1_15
Bernstein DJ, et al (2008) ChaCha, a variant of Salsa20. In: Workshop record of SASC, Citeseer, pp 3–5, https://citeseerx.ist.psu.edu/document?repid=rep1&type=pdf&doi=3599e1409c41e31b1f0be7f7c74c179b89f8443b
Bernstein DJ (2008) The salsa20 family of stream ciphers. In: Robshaw MJB, Billet O (eds) New stream cipher designs - the eSTREAM finalists, lecture notes in computer science, vol 4986. Springer, p 84–97, https://doi.org/10.1007/978-3-540-68351-3_8
Bertoni G, Daemen J, Peeters M, et al (2013) Keccak. In: Johansson T, Nguyen PQ (eds) Advances in cryptology - EUROCRYPT 2013, 32nd annual international conference on the theory and applications of cryptographic techniques, Athens, Greece, May 26-30, 2013. Proceedings, lecture notes in computer science, vol 7881. Springer, pp 313–314, https://doi.org/10.1007/978-3-642-38348-9_19
Dinu D, Perrin L, Udovenko A, et al (2016) Design strategies for ARX with provable bounds: Sparx and LAX. In: Cheon JH, Takagi T (eds) Advances in cryptology - ASIACRYPT 2016 - 22nd international conference on the theory and application of cryptology and information security, Hanoi, Vietnam, December 4-8, 2016, Proceedings, Part I, pp 484–513, https://doi.org/10.1007/978-3-662-53887-6_18
Dworkin MJ (2015) SHA-3 standard: Permutation-based hash and extendable-output functions https://www.nist.gov/publications/sha-3-standard-permutation-based-hash-and-extendable-output-functions?pub_id=919061
Ferguson N, Lucks S, Schneier B, et al (2010) The skein hash function family. Submission to NIST (round 3) 7(7.5):3. https://www.schneier.com/wp-content/uploads/2008/10/skein.pdf
Han Y, Wang C, Niu Z et al (2024) Sat-based automatic searching for differential and linear trails: applying to CRAX. Chin J Electron 33(1):72–79. https://doi.org/10.23919/cje.2022.00.313
Hong D, Lee J, Kim D, et al (2013) LEA: a 128-bit block cipher for fast encryption on common processors. In: Kim Y, Lee H, Perrig A (eds) Information security applications - 14th international workshop, WISA 2013, Jeju Island, Korea, August 19-21, 2013, Revised selected papers, lecture notes in computer science, vol 8267. Springer, pp 3–27, https://doi.org/10.1007/978-3-319-05149-9_1
Hong D, Sung J, Hong S, et al (2006) HIGHT: a new block cipher suitable for low-resource device. In: Goubin L, Matsui M (eds) Cryptographic hardware and embedded systems - CHES 2006, 8th international workshop, Yokohama, Japan, October 10-13, 2006, Proceedings, lecture notes in computer science, vol 4249. Springer, pp 46–59, https://doi.org/10.1007/11894063_4
Huang M, Wang L (2020) Automatic search for the linear (hull) characteristics of ARX ciphers: applied to speck, sparx, chaskey, and CHAM-64. Secur Commun Netw 4898612(1–4898612):14. https://doi.org/10.1155/2020/4898612
Huang M, Xu Z, Wang L (2022) On the probability and automatic search of rotational-XOR cryptanalysis on ARX ciphers. Comput J 65(12):3062–3080. https://doi.org/10.1093/comjnl/bxab126
Huang M, Wang L (2019) Automatic tool for searching for differential characteristics in ARX ciphers and applications. In: Hao F, Ruj S, Gupta SS (eds) Progress in cryptology - INDOCRYPT 2019 - 20th International conference on cryptology in India, Hyderabad, India, December 15-18, 2019, Proceedings, lecture notes in computer science, vol 11898. Springer, pp 115–138, https://doi.org/10.1007/978-3-030-35423-7_6
Liu Z, Li Y, Jiao L et al (2021) A new method for searching optimal differential and linear trails in ARX ciphers. IEEE Trans Inf Theory 67(2):1054–1068. https://doi.org/10.1109/TIT.2020.3040543
Liu Y, Sun S, Li C (2021) Rotational cryptanalysis from a differential-linear perspective - practical distinguishers for round-reduced friet, xoodoo, and alzette. In: Canteaut A, Standaert F (eds) Advances in cryptology - EUROCRYPT 2021 - 40th annual international conference on the theory and applications of cryptographic techniques, Zagreb, Croatia, October 17-21, 2021, Proceedings, part I, lecture notes in computer science, vol 12696. Springer, pp 741–770, https://doi.org/10.1007/978-3-030-77870-5_26
Matsui M (1994) On correlation between the order of s-boxes and the strength of DES. In: Santis AD (ed) Advances in cryptology - EUROCRYPT ’94, workshop on the theory and application of cryptographic techniques, Perugia, Italy, May 9-12, 1994, Proceedings, Lecture Notes in Computer Science, vol 950. Springer, pp 366–375, https://doi.org/10.1007/BFb0053451
Mouha N, Mennink B, Herrewege AV, et al (2014) Chaskey: an efficient MAC algorithm for 32-bit microcontrollers. In: Joux A, Youssef AM (eds) Selected areas in cryptography - SAC 2014 - 21st international conference, Montreal, QC, Canada, August 14-15, 2014, Revised Selected Papers, Lecture notes in computer science, vol 8781. Springer, pp 306–323, https://doi.org/10.1007/978-3-319-13051-4_19
Needham RM, Wheeler DJ (1997) Tea extensions. Report (Cambridge University, Cambridge, UK, 1997) http://www.club.cc.cmu.edu/~ajo/docs/xtea.pdf
Niu Z, Hu K, Sun S, et al (2024) Speeding up preimage and key-recovery attacks with highly biased differential-linear approximations. In: Reyzin L, Stebila D (eds) Advances in cryptology - CRYPTO 2024 - 44th annual international cryptology conference, Santa Barbara, CA, USA, August 18-22, 2024, Proceedings, part IV, lecture notes in computer science, vol 14923. Springer, pp 73–104, https://doi.org/10.1007/978-3-031-68385-5_3
Rivest RL (1992) The MD5 message-digest algorithm. RFC 1321:1–21. https://doi.org/10.17487/RFC1321
Rivest RL (1994) The RC5 encryption algorithm. In: Preneel B (ed) Fast software encryption: second international workshop. Leuven, Belgium, 14-16 December 1994, Proceedings, lecture notes in computer science, vol 1008. Springer, pp 86–96, https://doi.org/10.1007/3-540-60590-8_7
Schrottenloher A, Stevens M (2022) Simplified MITM modeling for permutations: New (quantum) attacks. In: Dodis Y, Shrimpton T (eds) Advances in cryptology - CRYPTO 2022 - 42nd annual international cryptology conference, CRYPTO 2022, Santa Barbara, CA, USA, August 15-18, 2022, Proceedings, part III, lecture notes in computer science, vol 13509. Springer, pp 717–747, https://doi.org/10.1007/978-3-031-15982-4_24
Shimizu A, Miyaguchi S (1987) Fast data encipherment algorithm FEAL. In: Chaum D, Price WL (eds) Advances in cryptology - EUROCRYPT ’87, Workshop on the theory and application of of cryptographic techniques, Amsterdam, The Netherlands, April 13-15, 1987, Proceedings, Lecture Notes in Computer Science, vol 304. Springer, pp 267–278, https://doi.org/10.1007/3-540-39118-5_24
Wheeler DJ, Needham RM (1994) Tea, a tiny encryption algorithm. In: Preneel B (ed) Fast software encryption: second international workshop. Leuven, Belgium, 14-16 December 1994, Proceedings, lecture notes in computer science, vol 1008. Springer, pp 363–366, https://doi.org/10.1007/3-540-60590-8_29
Xiong Z, Liu M (2023) A differential-linear attack of lightweight cipher schwaemm. J Cyber Secur https://jcs.iie.ac.cn/xxaqxb/ch/reader/view_abstract.aspx?flag=2&file_no=202212070000004 (In Chinese)
Acknowledgements
We are grateful to Zhongyi Zhang for helpful discussions and valuable suggestions. We also thank the associate editor and the anonymous reviewers for their constructive comments, which greatly helped improve the quality of this manuscript.
Funding
This work is supported by the National Key R&D Program of China (No. 2024YFA1013000), the Strategic Priority Research Program of the Chinese Academy of Sciences under Grant XDB0690200, and the National Natural Science Foundation of China (Grant No. 12231015).
Author information
Authors and Affiliations
Contributions
Jiajun Zhou and Zhicheng Xiong contributed to the conceptualization and methodology of the study and wrote the original draft. Zhenzhen Bao, Jian Guo, and Qingju Wang participated in the discussions and contributed to the review and revision of the manuscript. Shichang Wang and Meicheng Liu supervised the study and reviewed and edited the manuscript. All authors read and approved the final manuscript.
Corresponding authors
Ethics declarations
Conflict of interest
The authors declare that they have no conflict of interest.
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Appendices
Appendix
A The number of differential trails
Here we give the number of middle differential trails of Alzette using the middle differential trail calculation algorithm in Tables 8, 9 and 10 respectively.
B Experimental results of the pair of values satisfying the differential trail of Schwaemm
Here we give the pair of values satisfying the differential trail of Schwaemm using the differential trails value calculation algorithm in Table 11, Table 12 and Table 13 respectively. In the tables, the numbers in parentheses indicate the minimum number of pairs required for a successful attack, while the numbers outside the parentheses represent the total number of pairs.
The suffixes used to denote the active branches—namely \(\alpha\), \(\beta\), \(\gamma\), and \(\delta\)—are illustrated in the first-round structure diagrams for each respective variant (Figs. 4, 5, and 6). For Schwaemm128-128, \(\alpha\) and \(\beta\) signifies that this specific trail is the 4-round differential-linear trail of \(\Delta _0^1 \rightarrow \nabla _0^1\) located in the 0th branch and 1st branch of Sparkle256, respectively. For Schwaemm256-128 and Schwaemm192-192, \(\alpha\), \(\beta\) and \(\gamma\) signifies that this specific trail is the 4-round differential-linear trail of \(\Delta _0^1 \rightarrow \nabla _0^1\) located in the 0th branch, 1st branch and 2nd branch of Sparkle384, respectively. For Schwaemm256-256, the suffix \(\beta\) signifies that this specific trail is the 4-round differential-linear trail of \(\Delta _0^1 \rightarrow \nabla _0^1\) located in the 2nd branch of Sparkle512.
The table of value calculation algorithm
Here we give the table partitioning of the 0th and 1st, and 2nd and 3rd rounds in value calculation algorithm (Figs. 7, 8).
Rights and permissions
Open Access This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article’s Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article’s Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/
About this article
Cite this article
Zhou, J., Xiong, Z., Bao, Z. et al. Revisiting differential-linear cryptanalysis of lightweight cipher Schwaemm. Cybersecurity 9, 207 (2026). https://doi.org/10.1186/s42400-026-00636-w
Received:
Accepted:
Published:
Version of record:
DOI: https://doi.org/10.1186/s42400-026-00636-w