# Truncated differential cryptanalysis: new insights and application to QARMAv1-n and QARMAv2-64

Zahra Ahmadian, Akram Khalesi, Dounia M'foukh, Hossein Moghimi, María Naya-Plasencia

► To cite this version:

Zahra Ahmadian, Akram Khalesi, Dounia M'foukh, Hossein Moghimi, María Naya-Plasencia. Truncated differential cryptanalysis: new insights and application to QARMAv1-n and QARMAv2-64. Designs, Codes and Cryptography, 2024, 92 (12), pp.4549-4591. 10.1007/s10623-024-01486-8. hal-05465577

HAL Id: hal-05465577

https://hal.science/hal-05465577v1

Submitted on 19 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
Truncated Differential Cryptanalysis:
New Insights and Application to QARMAv1-n and
QARMAv2-64

Zahra Ahmadian¹, Akram Khalesi¹, Dounia M’foukh², Hossein Moghimi¹
and María Naya-Plasencia²

¹ Department of Electrical Engineering, Shahid Beheshti University, Tehran, Iran,
[z_ahmadian@sbu.ac.ir](mailto:z_ahmadian@sbu.ac.ir), [a_khalesi@sbu.ac.ir](mailto:a_khalesi@sbu.ac.ir), [h.moghimi@mail.sbu.ac.ir](mailto:h.moghimi@mail.sbu.ac.ir)

² Inria, Paris, France,
dounia.mfoukh@inria.fr, maria.naya_plasencia@inria.fr

**Abstract.** Truncated differential cryptanalyses were introduced by Knudsen in 1994. They are a well-known family of attacks that has arguably received less attention than some other variants of differential attacks. This paper gives some new insights into the theory of truncated differential attacks, specifically the conditions of provable security of SPN ciphers with MDS diffusion matrices against this type of attack. Furthermore, our study extends to various versions within the **QARMA** family of block ciphers, unveiling the only valid instances of single-tweak attacks on 10-round **QARMAv1-64**, 10-round **QARMAv1-128**, and 10- and 11-round **QARMAv2-64**. These attacks benefit from the optimal truncated differential distinguishers as well as some evolved key-recovery techniques.

**Keywords:** Cryptanalysis · Truncated Differentials · QARMA · Key Recovery

# 1 Introduction

In the realm of modern cryptography, the design and analysis of secure block ciphers play a pivotal role in ensuring the confidentiality of sensitive data. The development of advanced encryption algorithms has been an ongoing endeavor, aiming to thwart increasingly sophisticated attacks while maintaining implementation efficiency. One of the key aspects in this evolution is the study of the variations of differential attacks, which are powerful techniques utilized by cryptanalysts to probe the vulnerabilities of cryptographic primitives. This paper focuses on the truncated differential attack, a variant of differential attack proposed in 1994 by Knudsen [1], for security evaluation of block ciphers.

Despite some instances of cryptanalysis based on truncated differential attacks as an independent attack [2, 3, 4], this attack has garnered less attention compared to other variations, such as the impossible differential attack, higher-order differential attacks, boomerang, and rectangle attacks. The primary utilization of truncated differential path search has been targeted for discovering truncated paths with minimal activation of S-boxes, to finally instantiated by a high-probability concrete differential path [5].

In a recent work [6], a novel MILP (Mixed Integer Linear Programming) based tool has been introduced for identifying the optimum truncated differential paths and applied to MIDORI, SKINNY, and CRAFT block ciphers, covering a greater number of rounds with higher probabilities compared to their concrete differential counterparts.

This work subsequently garnered some interest in truncated differential attacks. In [7], considering that [6] has utilized certain approximations, an effective algorithm for
accurately calculating the truncated differential path probability for a given truncated path was proposed. Another subsequent work, outlined in [8], aimed at calculating the probability of truncated differentials, considering the clustering effects (also referred to as the differential effect). Furthermore, certain studies employed the methodology presented in [6] to automate the discovery of other distinguishers. These encompass the triangle attack [9] and mixture differential attacks [10], as examples. The significant advantages of truncated differential attacks, compared to concrete differential attacks, are as follows.

* **Simplicity.** The truncated differential attack utilizes a word-oriented variable definition, which results in much smaller search spaces. Moreover, it does not inherently depend on the S-box details, hence its MILP model is free from the bottleneck of S-box modeling. Consequently, the truncated differential automatic search tools display enhanced running time compared to the concrete (bit-oriented) differentials.

* **Efficiency.** There are notable instances where the truncated differential distinguisher outperforms its concrete counterpart. Some examples include KLEIN [2, 3], MIDORI, SKINNY, and CRAFT [6].

* **Value-insensitivity.** The truncated differential distinguisher is inherently independent of the concrete value of the active words. This makes the key recovery part of the attack more flexible, potentially requiring less key material to be guessed, at the two edges of the distinguisher.

Reflection ciphers are a class of symmetric encryption algorithms that exhibit a unique property: the set of encryption functions is identical to the set of decryption functions, making the cipher "reflect" the input to produce the output. This design strategy aims to reduce the implementation cost of the cipher, by minimizing the overhead of decryption on top of the encryption.

PRINCE block cipher [11], an SPN cipher with FX construction, stands as one of the most renowned examples of reflection ciphers. To be precise, it possesses the α-reflection property, meaning that decryption is equivalent to the encryption with the related key $K_{dec} = K_{enc} \oplus \alpha$, where α is a constant. In [12], a new attack called the reflection attack is proposed as a dedicated approach for cryptanalysis of PRINCE-like ciphers. It exploits the existence of too many fixed points in the intermediate rounds of the cipher and its extension to the full cipher.

Following in the footsteps of PRINCE, MANTIS [13] emerges as the subsequent reflection cipher again in the FX framework. It takes inspiration from PRINCE's design while evolving into a tweakable block cipher. Notably, MANTIS integrates certain choices from MIDORI's components [14] to enhance its structure. However, a practical attack on MANTIS$_5$ has been presented in [15], attributed to the MANTIS's extremely lightweight components, including the tweak schedule, and the vulnerability resulting from the interaction between the MIDORI-inspired round function and the PRINCE-inspired inner rounds.

The newly introduced QARMAv2 family of block ciphers [16] and its predecessor QARMAv1 family (formerly known as QARMA) [17] are the most recent reflection ciphers.

Besides reflection property, QARMA boasts additional features such as being tweakable, lightweight, and low-latency. Drawing inspiration from PRINCE, MIDORI, and MANTIS, QARMA exhibits notable differences both in the structure and in the choice of components. Unlike its predecessors, QARMA adopts a three-round Even-Mansour (EM) construction [18] rather than adhering to the FX construction. This departure from the FX construction was motivated by the cryptanalysis presented in [19]. Furthermore, QARMA's decision to pivot to EM construction is motivated by the improved time, memory, and data complexities, which offer superior bounds compared to the FX construction.

Insights gleaned from the MITM and accelerated exhaustive search attacks on PRINCE [20], that exploited the unkeyed central construction of PRINCE, the designers of QARMA
included a key addition in the middle permutation of QARMA. Moreover, this middle per-
mutation is non-involuntary to avoid predictable differences at its two sides. Another
innovation within the QARMA design pertains to the introduction of a family of almost
MDS matrices defined over a ring with zero divisors. They allow to encode rotations in
their operation while maintaining the minimal latency associated with binary matrices.
The matrices used in QARMA are with the minimum and close to minimum fixed points
for 64 and 128-bit versions, respectively. This property as well as suitable whitening keys
around the middle permutation makes it secure against the reflection attacks [12].

Similar to PRINCE and MANTIS, QARMAv1 asserts a k-bit time-data trade-off security, with k as its key size. This implies that for any attack on QARMAv1 to be valid, the product of time and data complexities must be less than 2^k. However, the designers of QARMAv2 highlighted that such a trade-off threshold does not apply to QARMAv2 attacks.

It is worth noting that the QARMAv1 cipher has been the subject of various cryptanal-
ysis efforts, most of which in the related-tweak model, including MITM attack [21, 22],
statistical saturation attack [23] and impossible differential attack [24, 25]. The only single-
tweak attack [21] is a 10-round MITM attack, but it fails to meet the time-data tradeoff
threshold. To the best of our knowledge, the only third-party analysis of QARMAv2 is an
integral attack in the related-tweak model [26]. A review and discussion on the details of
QARMA attacks, is provided in Sec. 5.2 of the paper. The designers of QARMA have proposed
some security bounds against the differential attack by counting the minimum number of
active S-boxes using Mouha et al.'s MILP search method [27]. However, the resistance of
these ciphers against the truncated differential attack has not been evaluated, either by
the designer or external cryptanalysts.

**Contributions.** This paper gives new insights into the theory of the relatively less discussed truncated differential attack and adds a new dimension to the cryptanalysis of QARMA by introducing the first valid single-tweak truncated differential attacks on both variants of 10-round QARMAv1 as well as 10 and 11-round QARMAv2-64. The contributions of this paper are as follows:

* Extension of truncated differential attack theory: The paper extends the theory of truncated differential attacks by formulating the complexities of this attack, proving the forward/backward symmetry of this attack, and also providing the provable security of SPN ciphers with MDS MixColumns against this kind of attack.

* Discovering optimal truncated differential distinguishers for QARMA: The non-MDS MixColumns matrix within the QARMA variants renders them susceptible to truncated differential analysis. Focusing these ciphers, and employing the automated MILP-based method proposed in [6], the paper identifies the optimum 6 and 4-round truncated differential distinguishers for QARMAv1-64 and 128, and QARMAv2-64 variants, all of which has the same structure.

* Single-Tweak attack on 10-round QARMAv1 variants: Based on the identified distinguishers, the paper proposes the first valid attacks on both variants of 10-round QARMAv1 meeting the security claim trade-off threshold given by the designer of QARMAv1; i.e. $DT < 2^k$ with data and time complexities $D$ and $T$ and the key size $k$. The attack exploits some evolved key-recovery methods based on list merging techniques and precomputation.

* Single-Tweak key-recovery attacks on 10 and 11-round QARMAv2-64: The paper proposes the first key-recovery attacks in the single-tweak model on QARMAv2-64. The attacks exploit the redundancy of the key schedule and cover 10 and 11 rounds of the cipher. It deserves to be noted that although the time-data trade-off does not exist for QARMAv2, the attack on 10-round QARMAv2-64 meets such restriction.
## 2 Theoretical Background

In this paper, we consider a block cipher $E: \mathbb{F}_2^n \times \mathbb{F}_2^k \to \mathbb{F}_2^n$, with an $n$-bit plaintext $X$ and a $k$-bit key $K$. The input and output difference variables of $E$ are denoted by $\Delta X$ and $\Delta Y$, respectively. We assume $E$ is a Markov cipher [28], where the subkeys of iterative block cipher are assumed to be independent and uniformly distributed. This is the only assumption behind the truncated differential attack, which is a very common and widely accepted assumption in differential cryptanalysis.

**Definition 1** (Concrete Differential Probability). For block cipher $E$, the differential probability of the concrete input difference $\alpha \in F_2^n$ and output difference $\beta \in F_2^n$ is defined as:

$$ \Pr_{X,K}(\alpha \xrightarrow{E} \beta) = \Pr_{X,K}(\Delta Y = \beta | \Delta X = \alpha) = \Pr_{X,K}[E_K(X) \oplus E_K(X \oplus \alpha) = \beta] \quad (1) $$

The differential $(\alpha \xrightarrow{E} \beta)$ is called an *efficient distinguisher* if $\Pr_{X,K}(\alpha \xrightarrow{E} \beta) \gg 2^{-n}$.

**Definition 2** (Truncated Differential Probability). For block cipher $E$, the truncated differential probability with input truncated difference $\Delta_{in} \subseteq F_2^n$, and output truncated difference $\Delta_{out} \subseteq F_2^n$, is defined as:

$$ \begin{aligned} \Pr_{X,K}(\Delta_{in} \xrightarrow{E} \Delta_{out}) &= \Pr_{X,K}(\Delta Y \in \Delta_{out} | \Delta X \in \Delta_{in}) \\ &= \Pr_{X,K}[E_K(X) \oplus E_K(X \oplus \alpha) \in \Delta_{out} | \alpha \in \Delta_{in}] \end{aligned} \quad (2) $$

**Definition 3** (Efficient Truncated Differential). The truncated differential $(\Delta_{in} \to \Delta_{out})$ is called efficient if it can distinguish cipher $E$ from a Pseudo Random Permutation (PRP), which holds if:

$$ \Pr_{X,K}(\Delta_{in} \xrightarrow{E} \Delta_{out}) > \Pr_X(\Delta_{in} \xrightarrow{PRP} \Delta_{out}) = \frac{|\Delta_{out}|}{2^n}. \quad (3) $$

The concept of efficient truncated differential was introduced in [7] under the terminology of *Expected Differential Distinguishability*. This concept is defined as the average differential probability over the output truncated differences, and it must be significantly larger than $2^{-n}$ to be able to distinguish the cipher from a PRP. In the rest of the paper, all the probabilities are taken over independent and uniformly distributed random variables $X$ and $K$. To streamline the presentation, we will omit $X, K$ for simplicity.

**Proposition 1** (Symmetry of the probability of concrete differential). For block cipher $E$ with concrete input-output differential pair $(\alpha, \beta)$, it holds that:

$$ \Pr(\alpha \xrightarrow{E} \beta) = \Pr(\beta \xrightarrow{E^{-1}} \alpha) \quad (4) $$

**Proposition 2** (Asymmetry of the probability of truncated differential [29]). For block cipher $E$ with truncated input-output differential pair $(\Delta_{in}, \Delta_{out})$ it holds that:

$$ \Pr(\Delta_{out} \xrightarrow{E^{-1}} \Delta_{in}) = \Pr(\Delta_{in} \xrightarrow{E} \Delta_{out}) \frac{|\Delta_{in}|}{|\Delta_{out}|} \quad (5) $$

*Proof.* The proof is given in Appendix A.1. □

**Example 1.** Fig. 1 shows a 9-round truncated differential distinguisher for Skinny-64 with the probability of $2^{-40}$ in the forward direction [6]. The reverse truncated differential in the backward direction is depicted by red arrows, which has the probability of $2^{-56}$. Note that this trail is consistent with Lemma 2, where $|\Delta_{in}| = 2^4$ and $|\Delta_{out}| = 2^{20}$ and $P(\Delta_{out} \xrightarrow{E^{-1}} \Delta_{in}) = 2^{-40} \frac{2^4}{2^{20}} = 2^{-56}$.
<figure><img src="image_2.png" /><figcaption>Figure 1: A 9-round truncated differential path for Skinny-64. The probability of black (forward) direction is $2^{-40}$ and for red (backward) direction is $2^{-56}$</figcaption></figure>

**Proposition 3.** The truncated differential ($\Delta_{in} \xrightarrow{E} \Delta_{out}$) is efficient, iff ($\Delta_{out} \xrightarrow{E^{-1}} \Delta_{in}$) is efficient.

*Proof.* The proof is straightforward using Prop. 2. □

**Definition 4** (Optimum Truncated Differential). The truncated differential ($\Delta_{in} \xrightarrow{E} \Delta_{out}$) is called optimum if it is efficient and has the maximal $P(\Delta_{in} \xrightarrow{E} \Delta_{out})|\Delta_{in}|$.

Despite the concrete differential attack in which the data required for the distinguisher is only proportional to the inverse of the differential probability [30], this is not the case with the truncated differential distinguisher. This will be discussed more in Sec. 3.

**Proposition 4.** The differential ($\Delta_{in} \xrightarrow{E} \Delta_{out}$) is the optimum truncated differential for $E$, iff ($\Delta_{out} \xrightarrow{E^{-1}} \Delta_{in}$) is the optimum one for $E^{-1}$.

*Proof.* The proof is given in appendix A.2. □

**Proposition 5** (Link between concrete and truncated differential probabilities [7]). For block cipher $E$, with input and output truncated differences $\Delta_{in}, \Delta_{out} \subseteq F_2^n$, it holds that:

$$ \Pr(\Delta_{in} \xrightarrow{E} \Delta_{out}) = \frac{1}{|\Delta_{in}|} \sum_{\substack{\alpha \in \Delta_{in}, \\ \beta \in \Delta_{out}}} \Pr(\alpha \xrightarrow{E} \beta) \quad (6) $$

*Proof.* The proof is given in Appendix A.3. □

Prop. 5 implies that the probability of truncated differential ($\Delta_{in} \to \Delta_{out}$) is neither greater nor smaller than each of its consistent concrete differentials ($\alpha \to \beta$), $\alpha \in \Delta_{in}$, $\beta \in \Delta_{out}$. Moreover, assume ($\alpha^* \to \beta^*$) is the optimum (highest-probability) concrete differential (which practically corresponds to minimum or near to minimum active S-boxes), and ($\Delta_{in}^* \to \Delta_{out}^*$) is the optimum truncated differential. Then, according to Prop. 5, ($\alpha^* \to \beta^*$) is not necessarily an instantiation of ($\Delta_{in}^* \to \Delta_{out}^*$), i.e. it does not necessitate that ($\alpha^* \to \beta^*$) $\in (\Delta_{in}^* \to \Delta_{out}^*)$.

This means that the truncated differential can serve as an independent distinguisher, with the potential to surpass the performance of concrete differential distinguishers, in some cases.

## 3 Truncated Differential Attack

Let ($\Delta_{in} \xrightarrow{E} \Delta_{out}$) be an $r_d$-round truncated differential of probability $2^{-p}$ for block cipher $E$. As shown in Fig. 2, we extend $\Delta_{in}$ in the backward direction for $r_{in}$ rounds to get the difference $D_{in}$ and $\Delta_{out}$ in the forward direction for $r_{out}$ rounds to get $D_{out}$, both with probability 1. We denote $|D_x| = 2^{d_x}$ and $|\Delta_x| = 2^{\delta_x}$, where $x \in \{in, out\}$. According to Def. 3, ($\Delta_{in} \xrightarrow{E} \Delta_{out}$) is an efficient distinguisher if

$$ p < n - \delta_{out} \quad (7) $$
<figure><img src="image_3.png" /><figcaption>Figure 2: Truncated differential attack framework</figcaption></figure>

In the following, we formulate the parameters of the chosen plaintext attack constructed over the truncated differential distinguisher ($\Delta_{in} \xrightarrow{E} \Delta_{out}$).

**Data Complexity.** To generate the pairs required for the attack, we construct $2^s$ structures in plaintext, each of which is constant in non-active bits, and take all $2^{d_{in}}$ values in active bits of $D_{in}$. So, each structure can generate about $2^{2d_{in}-1}$ pairs with differences belonging to $D_{in}$.

**Lemma 1.** *The probability that a pair with plaintext difference $D_{in}$ come up with a difference $\Delta_{in}$ after $r_{in}$ rounds is $P_{filt} = 2^{-(d_{in}-\delta_{in})}$.*

*Proof.* We can assume the differential ($\Delta_{in} \xrightarrow{E^{-1}} D_{in}$) for the first $r_{in}$ rounds of $E$ in backward direction, with probability 1. Applying Lemma 2 to this differential, yields
$$ \Pr(D_{in} \xrightarrow{E^{-1}} \Delta_{in}) = \Pr(\Delta_{in} \xrightarrow{E^{-1}} D_{in}) \frac{|\Delta_{in}|}{|D_{in}|} = 1 \cdot \frac{2^{\delta_{in}}}{2^{d_{in}}} = 2^{-(d_{in}-\delta_{in})} \quad \square $$

Therefore, the number of total pairs required for the attack must be equal to $(2^{-p} \times P_{filt})^{-1} = 2^{p+d_{in}-\delta_{in}}$. This gives the number of required structure as $2^{s+2d_{in}-1} = 2^{p+d_{in}-\delta_{in}}$ which yields $s = p - d_{in} - \delta_{in} + 1$. Finally, the data required for the attack would be as follows.

$$ \mathcal{D} = 2^{s+d_{in}} = 2^{p-\delta_{in}+1} \quad (8) $$

Note that to minimize the data complexity, it is necessary to minimize the value of $p-\delta_{in}$, which is consistent with the definition of the optimum distinguisher, given in Def. 4.

**Time Complexity.** The probability that a differential pair with difference $\Delta_{in}$ at round $r_{in}$ have a difference belonging to $D_{out}$ at the output is $P_{sieve} = 2^{-(n-d_{out})}$. So, the total number of sieved pairs supposed to be processed in the key recovery phase of the attack is $\mathcal{P} = 2^{p-n+d_{in}+d_{out}-\delta_{in}}$, and the time complexity of the attack is:

$$ \mathcal{T} = (2^{p-\delta_{in}+1} + 2^{p-\delta_{in}+1} \frac{C_S}{C_E} + 2^{p-n+d_{in}+d_{out}-\delta_{in}} \frac{C_{KR}}{C_E}) C_E \quad (9) $$

where $C_E, C_S$, and $C_{KR}$ are the time complexities of the encryption, the sieving step, and the key recovery step, respectively. Note that (9) is a generalization of the time complexity of the concrete differential attack, given in [31]. The concrete differential attack can be regarded as a special case of truncated differential attack, in which $\delta_{in} = \delta_{out} = 0$.

The concrete differential attack is a symmetric attack, which means that if there is an attack in the forward direction, there is also another one with the same main parameters, using the reverse distinguisher in the backward direction [31]. In the following theorem, we show that the same case is valid for the truncated differential attack, despite the asymmetry of the truncated differential distinguisher (Prop. 2).
**Theorem 1.** Suppose that there is a chosen plaintext truncated differential attack on block cipher E based on the distinguisher ($\Delta_{in} \xrightarrow{E} \Delta_{out}$) of probability $2^{-p}$, with data complexity $D$ and the total sieved pairs $P$. we can construct a chosen ciphertext attack, using the reversed truncated differential ($\Delta_{in} \xleftarrow{E^{-1}} \Delta_{out}$), with the same data complexity $D$ and total sieved pairs $P$.

*Proof.* The proof is given in Appendix A.4. □

# 4 Potential Targets for Truncated Differential Attack

Truncated differential attacks are particularly effective on word-oriented Substitution-Permutation Network (SPN) ciphers. While the efficiency of this attack is loosely tied to the S-box specification, it becomes significantly reliant on the differential characteristics of the MixColumns matrix. In the following, we present the general structure of a word-oriented SPN cipher, a framework that encompasses a wide range of block cipher designs including AES, MIDORI, SKINNY, QARMA, and CRAFT. Subsequently, we establish a theorem that identifies a prerequisite condition for the effectiveness of the truncated differential distinguisher.

**Definition 5** (Word-oriented SPN cipher). The block cipher E, featuring an internal state matrix of $t \times t$ of m-bit words, is called a word-oriented SPN cipher, if it undergoes the following sequence of four operations in each round, in any order of execution:

* **Subkey addition**: XORs a subkey of size $t^2$ m-bit words to the internal state.

* **S-box**: applies m-bit S-boxes to each m-bit word of the internal state, in parallel.

* **Permutation**: applies the word-wise permutation $\pi$ on $Z_{t^2}$ within the internal state, i.e. $Y[i] = \pi(X[i]) = X[\pi(i)]$ for $i \in 0, \dots, t^2 - 1$, where $X[i]$ denotes the $i^{th}$ word of the internal state. Here, each of the $t$ words within a column of $X[i]$ maps precisely to $t$ columns of $Y[i]$.

* **MixColumns**: multiplies matrix $M$ to each column of the internal state, in parallel. where, $M$ is a $t \times t$ matrix $M$ over $\mathbb{F}_{2^m}$.

While MDS (Maximum Distance Separable) matrices do provide optimal diffusion for the MixColumns operation, this constraint has been intentionally relaxed in several ciphers to gain implementation advantages. In the next theorem, we show that an MDS MixColumns matrix in the word-oriented SPN ciphers is a sufficient condition for provable security against truncated differential attacks. This claim holds under two assumptions: Markov cipher and uniformity of the output of MDS matrices. The former is a widely accepted assumption in different types of cryptanalysis of block ciphers, directly based on which the uniformity and independence of the output difference of S-boxes (which is the input of MixColumns) is concluded [32]. The latter is discussed in the following.

We define $\text{Tr}: \mathbb{F}_{2^m} \rightarrow \mathbb{F}_2$ as the m-bit truncation operation, i.e. assuming $\mathbf{x} = [x_1, \dots, x_{t-1}]^\top$, $x_i \in \mathbb{F}_{2^m}$, then $\text{Tr}(\mathbf{x}) = [r_0, \dots, r_{t-1}]^\top$, $r_i \in \mathbb{F}_2$, where $r_i = 0$ iff $x_i = 0$. Let $\text{Hw}: \mathbb{F}_2^t \rightarrow \{0, \dots, t\}$ be the Hamming weight operator, i.e. $\text{Hw}(\mathbf{a})$ is the number of non-zero elements of $\mathbf{a}$.

**Lemma 2** (Near-Uniform Distribution of MDS Matrix Output). Let $M$ be an MDS $t \times t$ matrix over $\mathbb{F}_{2^m}$. For the truncated difference vectors $\mathbf{a}, \mathbf{b} \in \mathbb{F}_2^t$, given a uniform distribution for $\mathbf{x}$, it holds that:

$$ \Pr(\mathbf{a} \xrightarrow{M} \mathbf{b}) = \Pr(\text{Tr}(M\mathbf{x}) = \mathbf{b}|\text{Tr}(\mathbf{x}) = \mathbf{a}) $$
$$ = \begin{cases} 1 & \text{Hw}(\mathbf{a}) + \text{Hw}(\mathbf{b}) = 0 \\ 0 & 1 \le \text{Hw}(\mathbf{a}) + \text{Hw}(\mathbf{b}) \le t \\ \approx 2^{-m(t-\text{Hw}(\mathbf{b}))} & \text{Hw}(\mathbf{a}) + \text{Hw}(\mathbf{b}) \ge t+1 \end{cases} \quad (10) $$

*Proof.* The proof of this lemma is given in Appendix A.5. □

For all MDS matrices $M$, the accurate value of the transition probability $\text{Pr}(\mathbf{a} \xrightarrow{M} \mathbf{b})$ is given by (42) and (43) of Appendix A.5, that can be approximated as (10). Both the accurate and approximated transition probabilities are independent of the MDS matrix description. Moreover, the transition probabilities depend only on $\text{Hw}(\mathbf{a})$ and $\text{Hw}(\mathbf{b})$, and for valid transitions (i.e. those with $\text{Hw}(\mathbf{a}) + \text{Hw}(\mathbf{b}) \in \{0, t+1, t+2, \dots, 2t\}$), it merely depends on $\text{Hw}(\mathbf{b})$. For, $t = 4, m = 4$, and $m = 8$ cases, the accurate and approximated transition probabilities of MDS matrices are reflected in Branching Property Table (BPT) in Table 5 of Appendix C. It can be seen that the approximation works well, specifically for larger values for $m$.

**Theorem 2.** *Under the assumption of Markov cipher and uniform distribution for output of MDS matrix, there is no efficient truncated differential distinguisher for 3 rounds + 1 S-box layer of a word-oriented SPN cipher with an MDS MixColumns matrix.*

*Proof.* Without loss of generality, we consider the order of operations within a round as given in Def. 5. Let $X_i$, $Y_i$, and $Z_i$ be the truncated differences of the input state, input, and output of MixColumns for round $i$, respectively. Let's denote the number of zero columns in $Z_i$ as $0 \le c_i < t$ for $i = 1, 2, 3$, which is also equivalent to the number of zero columns in $Y_i$. Moreover, as a consequence of the property of the Permutation layer outlined in Def. 5, every non-zero column in $Z_i = X_{i+1} = \pi^{-1}(Y_{i+1})$ inherits a minimum of $c_{i+1}$ zero words from zero columns in $Z_{i+1}$. Therefore, the count of zero words in $Z_i$, excluding those within zero columns, is at least $(t - c_i)c_{i+1}$. We use $P_i$ to denote the truncated differential probability for round $i$. Considering the uniform distribution of the MDS matrix output (Lemma 2), it holds that:

$$ P_i \le 2^{-m((t-c_i)c_{i+1})} \quad i = 1, 2 \quad (11) $$

Let $w_3$ denote the number of zero words of $Z_3$, not belonging to a zero column so $P_3 = 2^{-mw_3}$. Finally, the truncated differential probability of the last S-box layer is $P_s = 1$. Therefore, the probability of the truncated differential path would be upper-bounded by $P_{\text{Cipher}} = P_1P_2P_3P_s \le 2^{-m(tc_2-c_1c_2+tc_3-c_2c_3+w_3)}$. The probability of $Z_3$ being the truncated differential pattern of the output of a PRP is $P_{\text{PRP}} = 2^{-m(tc_3+w_3)}$. To prove the theorem, it suffices to show that the upper bound of $P_{\text{Cipher}}$ is less than or equal to $P_{\text{PRP}}$. Consider a nonzero column of $Z_2$ and $Y_2$, corresponding to the input and output of a MixColumns matrix of round 2. This MixColumns matrix has at least $c_1$ and $c_3$ input and output zero words, respectively. Since the MixColumns matrix is MDS, it follows that $c_1 + c_3 < t$ which ensures $2^{-m(tc_2-c_1c_2+tc_3-c_2c_3+w_3)} \le 2^{-m(tc_3+w_3)}$. Thereby $P_{\text{Cipher}} \le P_{\text{PRP}}$, which completes the proof. □

Theorem 2 implies that word-oriented SPN ciphers with non-MDS MixColumns matrices can be potentially vulnerable to truncated differential attacks. This assertion is corroborated by observations made during truncated differential cryptanalysis of MIDORI, SKINNY, and CRAFT [6], all of which use non-MDS MixColumns matrices. Within the QARMA family of block ciphers, to avoid the expensive implementation of MDS matrices, an almost-MDS matrix is selected as the MixColumns matrix. This motivated us to evaluate its security against truncated differential attack, which is outlined in the following Sections.
# 5 Introduction of QARMA Family of Block Ciphers

QARMAv1 (formerly known as QARMA) and QARMAv2 are two families of lightweight tweakable block ciphers proposed in 2017 and 2023, respectively [17, 16]. The design of QARMAv1 was influenced by PRINCE [11] and MANTIS [13], fitting to applications such as memory encryption, the generation of very short tags, and the construction of keyed hash functions. QARMAv2 which was introduced in ToSC 2023 [16], represents a redesigned version of QARMAv1 with an extended tweak and strengthened security margins.

## 5.1 Specifications of QARMA

Both families of QARMA support block sizes $n = 64$ and 128 referred to as QARMAv1-$n$ and QARMAv2-$n$. Throughout the remainder of the paper, the focus is on three versions of QARMA: QARMAv1-64, QARMAv1-128, and QARMAv2-64. When we mention QARMA without further specification, it encompasses these three aforementioned versions. We will first delineate the round functions of QARMA. Subsequently, we will outline the overall configuration of both versions of QARMA

### 5.1.1 Round Function

For QARMAv1-$n$, $n = 64$ or 128, and QARMAv2-64 the data is split into 16 $m$-bit words, where $m = 4$ for 64-bit block and 8 for 128 bit block. It is arranged in a $4 \times 4$ internal state matrix $IS$, denoted as:

$$IS = \begin{pmatrix} s_0 & s_1 & s_2 & s_3 \\ s_4 & s_5 & s_6 & s_7 \\ s_8 & s_9 & s_{10} & s_{11} \\ s_{12} & s_{13} & s_{14} & s_{15} \end{pmatrix} \qquad (12)$$

The Forward Round Function $\mathcal{R}(\cdot)$ is composed of the following layers:

1. **AddRoundTweakey.** The round key $k_i$, round tweak $t_i$, and round constant $c_i$ are added to $IS$.

2. **ShuffleCells.** The internal state $IS$ is shuffled according to the word permutation $\tau$, described below.

$$\begin{pmatrix} s_0 & s_1 & s_2 & s_3 \\ s_4 & s_5 & s_6 & s_7 \\ s_8 & s_9 & s_{10} & s_{11} \\ s_{12} & s_{13} & s_{14} & s_{15} \end{pmatrix} \xrightarrow{\tau} \begin{pmatrix} s_0 & s_{11} & s_6 & s_{13} \\ s_{10} & s_1 & s_{12} & s_7 \\ s_5 & s_{14} & s_3 & s_8 \\ s_{15} & s_4 & s_9 & s_2 \end{pmatrix} \qquad (13)$$

3. **MixColumns.** The MixColumns matrix $M_m$ is multiplied by $IS$. For QARMAv1-$n$ the MixColumns matrices are:

$$M_4 = \begin{pmatrix} 0 & \rho & \rho^2 & \rho \\ \rho & 0 & \rho & \rho^2 \\ \rho^2 & \rho & 0 & \rho \\ \rho & \rho^2 & \rho & 0 \end{pmatrix}, \quad M_8 = \begin{pmatrix} 0 & \rho & \rho^4 & \rho^5 \\ \rho^5 & 0 & \rho & \rho^4 \\ \rho^4 & \rho^5 & 0 & \rho \\ \rho & \rho^4 & \rho^5 & 0 \end{pmatrix} \qquad (14)$$

and for QARMAv2-64, the MixColumns matrix is:

$$M_4 = \begin{pmatrix} 0 & \rho & \rho^2 & \rho^3 \\ \rho^3 & 0 & \rho & \rho^2 \\ \rho^2 & \rho^3 & 0 & \rho \\ \rho & \rho^2 & \rho^3 & 0 \end{pmatrix} \qquad (15)$$
<figure><img src="image_4.png" /><figcaption>Figure 3: Overall structure of QARMAv1 and QARMAv2</figcaption></figure>

All the above matrices are defined over ring $R_m = \mathbb{F}_2[X]/(X^m + 1)$, and the multiplication by the image $\rho$ of $X$ in the ring $R_m$ is the circular left rotation of $X$. All the three versions of $M_m$ are symmetric and involutive matrices, i.e. $M_m = M_m^\top = M_m^{-1}$.

4. **SubCells.** A $m$-bit S-box is applied to all words of IS.

The Backward Round Function $\bar{R}(\cdot)$ is the inverse of the forward round function $R(\cdot)$. The Pseudo-Reflector function $P(IS; tk)$ positioned at the center of the cipher, is

$$ \mathcal{P} = \bar{\tau}(k_{ref} \oplus Q_m(\tau(IS))) \qquad (16) $$

where $Q_m = M_m$, and the bar over a transformation denotes its inverse.

### 5.1.2 Overall Structure

QARMA is an Even-Mansour cipher that uses three stages (forward, central, and backward) at the middle, and whitening keys XORed in at the beginning and end of the cipher. While QARMAv2 structure exhibits slight differences from QARMAv1, the structure of QARMAv1 has been integrated into the framework of QARMAv2 in Figure 3.

A $(2r + 2)$-round QARMA is defined as

$$ k'_{w} \oplus \bar{S}(\bar{R}^{r}(\mathcal{P}(\mathcal{R}^{r}(S(IS \oplus k_{w})))))) \qquad (17) $$

where $S$ is a single SubCells layer, and $k_w$ and $k'_w$ are input and output whitening keys.

### 5.1.3 Key Schedule

**QARMAv1.** The key size of QARMAv1-$n$ is $2n = 32m$ bits. The secret key $K$ is divided into two halves of $n$-bit length, $K = w||k$, and the first half extends to $w' = o(w) = (w^0 \gg 1) + (w^0 \gg (n-1))$. The set of keys used in the structure of QARMAv1 is defined as follows. The whitening keys are $k_w = w \oplus k \oplus T \oplus c_0$ and $k'_w = w' \oplus k \oplus \alpha \oplus T \oplus c_0$. The reflector key is $k_{ref} = k$, the round key is $k_i = k$ for forward round functions, and $k_i = k \oplus \alpha$ for backward round functions, where $\alpha$ is a constant defined in [17]. The tweak size of QARMAv1 is $n$ bits. More information about the tweak schedule of QARMAv1 can be found in [17].

**QARMAv2-64.** The key size of QARMAv2-64 is 128 bits. The secret key $K$ is divided into two halves of 64-bit length, $K = K_0||K_1$, and extends to $(L_0, L_1) = (o(K_0) \oplus \alpha, o^{-1}(K_1) \oplus \beta)$, where $\alpha$, and $\beta$ are constants defined in [16] and $o$ is the linear function defined as in QARMAv1. In the forward rounds, the round key $k_i$ alternates between $K_0$ and $K_1$, and in the backward rounds, it alternates between $L_1$ and $L_0$. Moreover, the reflector key is $k_{ref} = M \cdot W_0 \oplus W_1$ where $W_0 = o^2(K_0)$ and $W_1 = o^{-2}(K_1)$. Finally, the whitening keys are $k_w = K_0$ and $k'_w = L_0$.

QARMAv2-64 supports two tweak sizes 64 and 128 bits. The former is called the single block tweak QARMAv2-64 and the latter is called the double block tweak. More information about the tweak schedule of QARMAv2 can be found in [16]. The details of the full-round QARMAv1 and QARMAv2 are illustrated in Figures 8 and 9, respectively.
### 5.1.4 Number of Rounds

For QARMAv1-64, $r$ is chosen as 7, i.e. the total rounds of QARMAv1-64 would be 16 rounds. However, the designer stated that the cipher is believed to be secure against practical attacks already for $r = 6$, i.e. 14 rounds, with some use cases even allowing for $r = 5$, i.e. 12 rounds. For QARMAv1-128, $r$ is chosen as 11, i.e. the total round of QARMAv1-128 would be 24 rounds. Again, it is stated that the cipher is believed to be secure against practical attacks already for $r = 8$, i.e. 18 rounds. Parameter $r$ and the number of rounds for QARMAv2-64 with a single block tweak is set as QARMAv1-64 while for QARMAv2-64 with two independent tweak blocks $r = 9$, i.e. 20 rounds.

### 5.1.5 Security Claim

**Time-Data Trade-off for QARMAv1.** The designer of QARMAv1 has claimed that: *Similary to MANTIS and PRINCE, for QARMAv1-64 and QARMAv1-128, with $r = 7$ and $r = 11$ respectively, we claim that they attain $n$ bits of tradeoff security.* This statement means that any attack on QARMAv1-$n$ with data and time complexities $\mathcal{D}$ and $\mathcal{T}$, is a valid attack as far as $\mathcal{D}\mathcal{T} < 2^{2n}$.

**QARMAv2-64.** The designers of QARMAv2 stated that QARMAv2 has shifted away from basing security levels on time-data trade-offs. With a time complexity upper bounded to $2^{128-\epsilon}$, they set data limits of $2^{56}$ blocks per key for QARMAv2-64 with a single block tweak and $r = 7$, as well as for the version with a double block tweak and $r = 9$.

## 5.2 Cryptanalysis History of QARMA

Most of the cryptanalytic work on QARMAv1-64 and QARMAv1-128 is in the related-tweak model. In [22], the idea of two related-tweaks in the MITM attacks on 8 and 9 rounds of QARMAv1-64, along with a related-tweak on 10 rounds of QARMAv1-128, has been proposed. They are based on a 5-round MITM distinguisher demanding a $\delta$-set on tweak variables. For QARMAv1-64, the $\mathcal{T}\mathcal{D}$ is $2^{106}$ and $2^{105}$, respectively, while QARMAv1-128 holds $2^{244}$. Li et al. in [23] proposed a new cryptanalytic method that can be seen as a related-tweak statistical saturation attack by making a link between related-tweak statistical saturation distinguishers and the tweak difference invariant bias. By applying this approach, a related-tweak statistical saturation attack for 10-rounds of QARMAv1-64 and an 11-round attack on QARMAv1-128 were obtained.

In [24], two related-tweak impossible differential attacks on the 11 rounds of both versions of QARMAv1, without whitening keys, a MITM attack on the 10 rounds of QARMAv1-128 with whitening keys, and 12 rounds of QARMAv1-128 with the whitening keys are proposed. In [33] and [25], two related-tweak impossible differential attacks on QARMAv1-64 and QARMAv1-128 are proposed, respectively. The former, which is a 10-round key recovery attack with time and data complexity of $2^{125.8}$ and $2^{62}$, violates the $\mathcal{T}\mathcal{D}$ threshold claimed for QARMAv1-64. The latter is an 11-round attack on QARMAv1-128 that omits the outer whitening key with time complexity and data complexity of $2^{145.98}$ and $2^{102.54}$. In [34], six related-tweak truncated differential attacks are proposed on both versions of QARMAv1. The attacks conducted on QARMAv1-64 cover 10,10 and 11 rounds respectively, whereas the attacks on QARMAv1-128 cover 11,12 and 13 rounds. Among these attacks, only two adhere to the $\mathcal{T}\mathcal{D}$ trade-off threshold, while the other four attacks are deemed invalid in this regard. In [35], a related-tweak impossible differential attack is applied to 11 rounds of QARMAv1-64 using a 7-round distinguisher. In this attack, the time complexity and data complexity are $2^{80}$ and $2^{61}$ respectively.

In [36], utilizing the concept of a zero-correlation distinguisher and its conversion into an integral distinguisher, a related-tweak attack is applied to 12 rounds of QARMAv1-64.
<table><caption>Table 1: Summary of the external cryptanalysis of QARMA</caption><thead><tr><th>Cipher</th><th>Model</th><th>Type</th><th>Whitening</th><th>Symmetry</th><th>Rounds</th><th>Time</th><th>Data</th><th>Memory</th><th>Validity</th><th>Ref.</th></tr></thead><tbody><tr><td rowspan="12">QARMAv1-64</td><td rowspan="12">RT</td><td>MITM</td><td>Yes</td><td>Yes</td><td>8</td><td>290</td><td>216</td><td>290</td><td>Yes</td><td>[22]</td></tr><tr><td>MITM</td><td>Yes</td><td>No</td><td>9</td><td>289</td><td>216</td><td>289</td><td>Yes</td><td>[22]</td></tr><tr><td>SS</td><td>Yes</td><td>Yes</td><td>10</td><td>259</td><td>259</td><td>296</td><td>Yes</td><td>[23]</td></tr><tr><td>ID</td><td>Yes</td><td>No</td><td>10</td><td>2125.8</td><td>262</td><td>237</td><td>No</td><td>[33]</td></tr><tr><td>TD</td><td>Yes</td><td>No</td><td>10</td><td>275.13</td><td>247.12</td><td>272</td><td>Yes</td><td>[34]</td></tr><tr><td>TD</td><td>Yes</td><td>Yes</td><td>10</td><td>283.53</td><td>247.06</td><td>280</td><td>No</td><td>[34]</td></tr><tr><td>TD</td><td>Yes</td><td>No</td><td>11</td><td>2111.16</td><td>234.26</td><td>2108</td><td>No</td><td>[34]</td></tr><tr><td>ID</td><td>Yes</td><td>No</td><td>11</td><td>280</td><td>261</td><td>261</td><td>No</td><td>[35]</td></tr><tr><td>ZC/IN</td><td>Yes</td><td>No</td><td>12</td><td>266.2</td><td>248.4</td><td>253.70</td><td>Yes</td><td>[36]</td></tr><tr><td>ID</td><td>Yes</td><td>No</td><td>11</td><td>269</td><td>258.38</td><td>263.38</td><td>Yes</td><td>[24]</td></tr><tr><td rowspan="4">ST</td><td>MITM</td><td>No</td><td>No</td><td>10</td><td>2116</td><td>253</td><td>2116</td><td>No</td><td>[21]</td></tr><tr><td>TID</td><td>Yes</td><td>Yes</td><td>10</td><td>272</td><td>261</td><td>278.2</td><td>No</td><td>[37]</td></tr><tr><td>TD</td><td>Yes</td><td>Yes</td><td>10</td><td>265.72</td><td>249.39</td><td>263.12</td><td>Yes</td><td>Sec. 6.2</td></tr><tr><td>TID</td><td>Yes</td><td>No</td><td>11</td><td>2120.4</td><td>261</td><td>2116</td><td>No</td><td>[37]</td></tr><tr><td rowspan="12">QARMAv1-128</td><td rowspan="12">RT</td><td>MITM</td><td>Yes</td><td>Yes</td><td>10</td><td>2164.48</td><td>288</td><td>297</td><td>Yes</td><td>[24]</td></tr><tr><td>MITM</td><td>Yes</td><td>Yes</td><td>10</td><td>2156</td><td>288</td><td>2145</td><td>Yes</td><td>[22]</td></tr><tr><td>ID</td><td>Yes</td><td>No</td><td>10</td><td>2120.94</td><td>2104.02</td><td>294.50</td><td>Yes</td><td>[25]</td></tr><tr><td>ID</td><td>No</td><td>No</td><td>11</td><td>2137</td><td>2111.38</td><td>2120.38</td><td>Yes</td><td>[24]</td></tr><tr><td>ID</td><td>No</td><td>No</td><td>11</td><td>2145.98</td><td>2102.54</td><td>2135.54</td><td>Yes</td><td>[25]</td></tr><tr><td>TDIB</td><td>Yes</td><td>No</td><td>11</td><td>2126.1</td><td>2126.1</td><td>271</td><td>Yes</td><td>[23]</td></tr><tr><td>TD</td><td>Yes</td><td>No</td><td>11</td><td>2104.60</td><td>2124.05</td><td>248</td><td>Yes</td><td>[34]</td></tr><tr><td>TD</td><td>Yes</td><td>No</td><td>12</td><td>2154.53</td><td>2108.52</td><td>2144</td><td>No</td><td>[34]</td></tr><tr><td>MITM</td><td>Yes</td><td>No</td><td>12</td><td>2156.06</td><td>288</td><td>2154</td><td>Yes</td><td>[24]</td></tr><tr><td>TD</td><td>Yes</td><td>No</td><td>13</td><td>2238.02</td><td>2106.63</td><td>2240</td><td>No</td><td>[34]</td></tr><tr><td rowspan="4">ST</td><td>MITM</td><td>No</td><td>No</td><td>10</td><td>2232</td><td>2105</td><td>2232</td><td>No</td><td>[21]</td></tr><tr><td>TID</td><td>Yes</td><td>Yes</td><td>10</td><td>2237.3</td><td>2122</td><td>2144</td><td>No</td><td>[37]</td></tr><tr><td>TD</td><td>Yes</td><td>Yes</td><td>10</td><td>2137.84</td><td>2103.95</td><td>2134.51</td><td>Yes</td><td>Sec. 6.3</td></tr><tr><td>TID</td><td>Yes</td><td>No</td><td>11</td><td>2241.8</td><td>2122</td><td>2232</td><td>No</td><td>[37]</td></tr><tr><td rowspan="4">QARMAv2-64</td><td rowspan="4">RT</td><td>IN</td><td>Yes</td><td>No</td><td>13</td><td>2110.47</td><td>246.32</td><td>246.32</td><td>Yes, (T = 1)</td><td>[26]</td></tr><tr><td>IN</td><td>Yes</td><td>No</td><td>14</td><td>2110.17</td><td>246.32</td><td>246.32</td><td>Yes, (T = 2)</td><td>[26]</td></tr><tr><td rowspan="2">ST</td><td>TD</td><td>Yes</td><td>Yes</td><td>10</td><td>270.68</td><td>247.36</td><td>268.68</td><td>Yes</td><td>Sec. 6.4</td></tr><tr><td>TD</td><td>Yes</td><td>No</td><td>11</td><td>2105.03</td><td>246.94</td><td>2103.28</td><td>Yes</td><td>Sec. 6.5</td></tr></tbody></table>

RT: Related Tweak

MITM: Meet In the Middle

SS: Statistical Saturation

RT/ST: Related Tweak/Single Tweak

ZC: Zero Correlation

ST: Single Tweak

ID: Impossible Differential

TD: Truncated Differential

TDIB: Tweak Difference Invariant Bias

IN: Integral.

The time complexity and data complexity of the attack are $2^{66.2}$ and $2^{48.4}$ respectively. There are only two works in the single-tweak, the first model is [21], which proposes 10-round MITM attacks for both versions of QARMAv1. However, it does not meet the time-data tradeoff threshold. For QARMAv1-64 the time complexity and data complexity were reported as $2^{70}$ and $2^{53}$ respectively, but its memory complexity, which is the lower bound of the time complexity, is $2^{116}$. For QARMAv1-128, the time complexity and data complexity were $2^{141}$ and $2^{105}$ while its memory complexity remains consistent at $2^{232}$. Hence, both of these attacks do not satisfy the time-data tradeoff threshold and can not be considered valid attacks on QARMAv1. The second single-tweak attack has been introduced in [37]. By using a 6-round distinguisher, it proposes four truncated impossible differential attacks on both versions of QARMAv1. Each of the four conducted attacks violates the $TD$ threshold claimed by designers.

Security of the newly introduced cipher QARMAv2 is well studied by the designers but scarcely by third parties. To the best of our knowledge, the only published result works in the related-tweak model and covers 13 and 14 rounds of QARMAv2-64, out of the recommended 16 and 20 rounds for $T = 1$ and 2, respectively [26].

A summary of all the attacks on reduced-round QARMAv1 and QARMAv2-64, along with the new attacks presented in this paper, is given in Tab. 1.

# 6 Truncated Differential attack on QARMA

In this section, we present 10-round attacks on QARMAv1-64 and QARMAv1-128, as well as 10 and 11-round attacks on QARMAv2-64. All the proposed attacks are the best valid
attacks in the single-tweak model. We first introduce the optimum 6-round truncated distinguishers for these ciphers, then based on the 4 inner rounds of which, we propose the key recovery attacks.

## 6.1 6-round Truncated Distinguisher for QARMAv1-n and QARMAv2-64

The process of determining the optimal truncated differential path involves two steps: the identification of the optimal path and computing its accurate probability. To discover the optimal truncated differential path, we employ the Mixed-Integer Linear Programming (MILP) tool proposed in [6], which fully automates the search process, in an efficient way. This approach is built upon the assumption of independent and uniformly distributed variables for the output differences of the active S-boxes, a consequence of the Markov cipher assumption [28]. Under this assumption, the only part of the cipher that needs to be modeled is the Branching Property (BPT) (defined in Def. 6 of Appendix C) associated with the MixColumns matrix $M_m$. The BPTs of QARMAv1-64, QARMAv1-128, and QARMAv2-64 can be found in Appendix C. In [6], an approximated BPT is employed for its simplicity. In this approximation, all the transition probabilities through MixColumns matrix are rounded to the nearest power of $2^{-m}$. However, when dealing with the BPT of $M_4$ and $M_8$ matrices of QARMA variants, we calculate more precise values for transition probabilities, which span a broad range of non-integer values. Thus, we employ the MILP model proposed by Abdelkhalek in [5], specifically designed for the MILP modeling of large S-boxes with non-integer transition probabilities, which is well-suited to our case.

In accordance with Def. 4, we define the objective function as the minimization of $p - \delta_{in}$. To ensure that the resulting path is an efficient one, as stipulated in Def. 3, we incorporate the constraint $p \le n - \delta_{out}$ into the model, for efficient distinguisher.

Once we have identified the optimal path under the Markov cipher assumption, we employ Prop. 5 to determine the accurate value of the distinguisher probability. There are two approaches for computing this value. The first approach, introduced in [7], is an efficient and speedy algorithm. It calculates the truncated probability for a given truncated path (referred to as an "activity pattern" in [7]) by taking into account all the concrete paths consistent with the specified path. The second approach involves utilizing a SAT- or MILP-based automatic method to find all concrete differentials ($\alpha \to \beta$), where $\alpha \in \Delta_{in}^*$ and $\beta \in \Delta_{out}^*$, with ($\Delta_{in}^*, \Delta_{out}^*$) representing the input/output difference of the optimal truncated path obtained in the previous step. While this approach may not be as swift as the method proposed in [7], it offers the advantage of considering any potential differential effects, i.e. the concrete paths that are not necessarily confined to the optimal truncated path within the internal state differences. Therefore, we opt for the second approach to refine the probability of the optimal truncated differential distinguisher. Both the MILP- and SAT-based models were employed independently, and they provided perfectly matching solutions.

**6-round distinguishers.** We searched for the longest optimum truncated differential distinguisher for the middle part of QARMAv1-64 and QARMAv1-128, as well as QARMAv2-64, independently. In all three cases, we found the same set of 16 distinguishers covering $\tilde{\mathcal{R}}^2(\mathcal{P}(\mathcal{R}^2(\cdot)))$ as the optimum distinguisher. These distinguishers, covering 6 full $\mathcal{R}$ (or $\tilde{\mathcal{R}}$) through involving seven {ShuffleCells + MixColumns} layers, are as follows:

$$ \bar{\tau}(M(a \cdot e_i)) \xrightarrow[2^{-p}]{\bar{\mathcal{R}}^2(\mathcal{P}(\mathcal{R}^2(\cdot)))} \bar{\tau}(M(b \cdot e_i)), \quad a, b \in \mathbb{F}_2^m/\{0\}, \quad i = 0, \dots, 15 \quad (18) $$

where $a \cdot e_i$ is the 4 × 4 matrix whose $i^{th}$ element is $a$, while all other elements are zero. All the 16 paths given in (18) exhibit a reflective pattern and share the following parameters:
<figure><img src="image_5.png" /><figcaption>Figure 4: An optimal 6-round truncated differential distinguisher for QARMAv1-64, QARMAv1-128, and QARMAv2-64, with probabilities $P = 2^{-49.7}$, $2^{-107.6}$, and $2^{-48.27}$, respectively. The red part is the 4-round path with the same probability.</figcaption></figure>

* For QARMAv1-64, $\delta_{in} = 4$, and $\delta_{out} = 4$, and the approximated $p$ merely based on the BPT is 51.8, which is refined to the accurate value $p = 49.7$, using SAT- and MILP-based automatic methods for computing (6), independently.

* For QARMAv1-128, $\delta_{in} = 8$, and $\delta_{out} = 8$, and the approximated $p$ merely based on the BPT is 108.77, which is refined to the accurate value $p = 107.60$ using a SAT-based automatic method.

* For QARMAv2-64, $\delta_{in} = 4$, and $\delta_{out} = 4$, and the approximated $p$ merely based on the BPT is 46.97, which is refined to the accurate value $p = 48.27$, using SAT-based automatic method.

The profile of concrete paths and their probabilities are shown in Appendix D. Moreover, this validation also shows that the accuracy of the pure-truncated search [6] is well enough in the case of QARMA. An instance of the distinguishers introduced in (18) for $i = 4$ is shown in Fig. 4, also described in (19) for QARMAv1-64.

$$ \begin{pmatrix} a\rho & 0 & 0 & 0 \\ 0 & a\rho & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & a\rho^2 \end{pmatrix} \xrightarrow[2^{-49.7}]{\bar{R}^2(P(\mathbb{R}^2(\cdot)))} \begin{pmatrix} b\rho & 0 & 0 & 0 \\ 0 & b\rho & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & b\rho^2 \end{pmatrix} \qquad (19) $$

**4-round distinguishers.** The first and last rounds of transitions in the paths given in (18) are deterministic. So, if we omit these two rounds, we come up with a series of 4-round totally reflective distinguishers with the same probability, which is as follows.

$$ a \cdot e_i \xrightarrow[2^{-p}]{\bar{R}(P(\mathbb{R}(\cdot)))} b \cdot e_i \qquad (20) $$

where $p = 49.7$, $107.60$, and $48.27$ for QARMAv1-64, QARMAv1-128, and QARMAv2-64, respectively. In Fig. 4, this distinguisher is highlighted within the 6-round distinguisher, in red. In the next subsection, we use these 4-round paths as the underlying distinguisher for the proposed key recovery attacks.

## 6.2 Single-Tweak Key Recovery Attack on 10-Round QARMAv1-64

We first present the main attack procedure on QARMAv1-64, by which its key space is reduced by a factor of about $2^{12}$. Then, we use it repeatedly to realize a full key recovery attack, satisfying the $\mathcal{T}\mathcal{D}$ trade-off threshold.
<figure><img src="image_6.png" /><figcaption>Figure 5: 10-round truncated differential attack on QARMAv1-64</figcaption></figure>
### 6.2.1 Reducing the Key Space

We use an equivalent representation of QARMAv1-64, in which the AddRoundTweakey layer of all rounds, are replaced by an equivalent key $u = M(\tau(k))$ XORed in after (before) the MixColumn layer in the forward (backward) round functions.

We use the 4-round distinguisher given in (20) of probability $2^{-49.7}$ for $i = 4$, which is shown in Fig. 4, omitting the first and last rounds of the 6-round path. We extend this distinguisher for three rounds in each direction, resulting in a 10-round attack. This attack is shown in Fig. 5. For simplicity in this figure, we have omitted the tweaks, the constants $c_i$ and also $\alpha$.

The propagation of active nibbles in the upper and lower parts is exactly the same. This causes all subkeys $k$ or $u$ involved in the attack to be the same in the upper and lower parts. The resulting differences in plaintext and ciphertext are active over the same nibbles, and finally $d_{in} = d_{out} = 36$.

**Precomputation Phase.** We will use the linear relations in the subkey bits to compute a precomputation table to reduce the time complexity of the attack by reducing the number of subkey bits guessed during the attack steps.

Thanks to the key schedule and the linear description of subkey bits involved in the attack given in Appendix E, we have the following linear relations between the subkey bits of $(w \oplus k), u$ and $(w' \oplus k)$:

$$ 
\begin{align*}
(w' \oplus k)[4]_3 + (w' \oplus k)[11]_2 + (w' \oplus k)[14]_2 &= (w \oplus k)[4]_2 + (w \oplus k)[11]_1 + (w \oplus k)[14]_1 + u[5]_{1,4}, \\
(w' \oplus k)[4]_4 + (w' \oplus k)[11]_3 + (w' \oplus k)[14]_3 &= (w \oplus k)[4]_3 + (w \oplus k)[11]_2 + (w \oplus k)[14]_2 + u[5]_{1,2}, \\
(w' \oplus k)[4]_{2,3,4} + (w' \oplus k)[11]_4 + (w' \oplus k)[14]_4 &= (w \oplus k)[4]_{1,2,3} + (w \oplus k)[11]_3 + (w \oplus k)[14]_3 + u[5]_{2,3}.
\end{align*}
$$

Thus if we guess the $2^{12}$ possible values of $(w \oplus k)[4,11,14]$, the $2^4$ possible values of $u[5]$, the $2^4$ possible values of $(w' \oplus k)[4]$, and the $2^{24}$ possible values of $(C, C')[4,11,14]$, we would be able to compute $(w' \oplus k)[11]$ and $(w' \oplus k)[14]$, according to Step 1 of the attack below. Then, the three linear relations between the subkey bits apply a 3-bit filter on $(w' \oplus k)[4]$ and only two possible values of $(w' \oplus k)[4]$ remain for each triplet of $((w \oplus k)[4,11,14], u[5], (C, C')[4,11,14])$. We can now compute a precomputation table of the values of $(w' \oplus k)[4]$ for each possible $((w \oplus k)[4,11,14], u[5], (C, C')[4,11,14])$. Thus we have a size $2^{41}$ precomputation table of the 2 possible values of $(w' \oplus k)[4]$ for each of the $2^{40}$ possible values of $((w \oplus k)[4,11,14], u[5], (C, C')[4,11,14])$.

Similarly, we can compute the same precomputation table for the values of $(w' \oplus k)[5]$ and $(w' \oplus k)[7]$.

**Generating Pairs.** We follow the process discussed in Sec. 3 to accurately determine the data required for the attack. Each structure contains $2^{36}$ plaintexts, which are constant in the 7 non-active nibbles {0,1,2,3,6,9,12}, and take all possible values in the other nibbles. Since none of the differential pairs should share similar values in the active nibbles, the total number of pairs in each structure is $\frac{1}{2}(2^4(2^4 - 1))^9 = 2^{70.16}$. According to the branching property table of $M_4$, which can be found in Appendix C, the filtering probability is $P_{Filt} = (2^{-7.81})^4 = 2^{-31.25}$, because of the three column transitions in the first MixColumns, and the one in the second. It must be held that $2^{s+70.16} = 2^{49.7+31.25}$ which gives $s = 10.8$. Therefore, the data required for the attack is $2^{s+36} = 2^{46.8}$. Finally, the probability of sieving the ciphertext pairs is $P_{sieve} = (2^{-4})^7 \times (\frac{15}{16})^9 = 2^{-28.84}$, and the total number of pairs after sieving is $2^{s+70.16-28.84} = 2^{52.12}$.

**Attack Steps.** For each of the $2^{52.12}$ candidate pairs, in order to verify which keys would allow to follow the differential path, the following steps are performed:
1. We first guess the nibble $(w \oplus k)[4]$ which implies the pair of values in $X_1[4]$. The MixColumns transition to column two in $Y_1$ implies that $\Delta X_1[11] = \Delta X_1[14] = \rho^{-1}\Delta X_1[4]$. On the other hand, we know the differences in nibbles $X_0[11]$ and $X_0[14]$ in the input of the S-box as they are given by the plaintext.

There is a $2^{-p_n}$ probability of having a possible transition through the DDT and for each transition $2^{p_n}$ values make it possible. Thus, on average we associate one value of the nibbles $(w \oplus k)[11, 14]$, per pair and per guess of $(w \oplus k)[4]$. The time complexity of this step is $2^{52.12} \times 2^4 = 2^{56.12}$.

2. We guess the nibble $u[5]$ to be able to use the precomputation table. Since we have $P$ and $P'$, we already have the needed bits of the ciphertexts, i.e. $(C, C')[4, 11, 14]$. Thus we can read on the precomputation table the 2 possible values of $(w' \oplus k)[4]$ and compute as in step 1, the value of $(w' \oplus k)[11]$ and $(w' \oplus k)[14]$. The time complexity after this step is $2^{56.12} \times 2^4 \times 2 = 2^{61.12}$.

3. Since we guessed $u[5]$, we can compute the pairs of values in $Y_8[5]$, and consequently $X_8[5]$. Due to the linear relation imposed by the MixColumns matrix, it holds that $\Delta Z_7[4] = \rho^{-1}\Delta X_8[5]$. Thanks to the reflective structure of the cipher, the same conditions apply to the upper part and we can compute $\Delta Z_2[4] = \rho^{-1}\Delta X_2[5]$.

4. We repeat Steps 1,2 and 3 with $((w' \oplus k)[5], u[0])$ and $((w' \oplus k)[7], u[15])$. The time complexity is now $3 \times 2^{61.12} = 2^{62.72}$.

5. We now have to match the three different candidates subkey bits we computed. For this, we will merge the list of the $2^9$ differences $(\Delta_1 Z_2[4], \Delta_1 Z_7[4])$ computed in Step 3 using $u[5]$, the list of the $2^9$ differences $(\Delta_2 Z_2[4], \Delta_2 Z_7[4])$ computed in Step 3 using $u[0]$ and the list of the $2^9$ differences $(\Delta_3 Z_2[4], \Delta_3 Z_7[4])$ computed in Step 3 using $u[15]$.

There is $2^8$ possible values for the differences $(\Delta_i Z_2[4], \Delta_i Z_7[4])$, $i = 1, 2, 3$, therefore for each of the $2^9$ possible values of $((w \oplus k)[4, 11, 14], u[5], (w' \oplus k)[4])$, there is $\frac{2^9}{2^8} = 2$ values of $((w \oplus k)[5, 10, 15], u[0], (w' \oplus k)[5, 10, 15])$ which will match. Similarly, for each of the two values of $((w \oplus k)[5, 10, 15], u[0], (w' \oplus k)[5, 10, 15])$, there will be two matches in the list of differences $(\Delta_3 Z_2[4], \Delta_3 Z_7[4])$ thus there will be 2 values of $((w \oplus k)[7, 8, 13], u[15], (w' \oplus k)[7, 8, 13])$ for each of the 2 values of $((w \oplus k)[5, 10, 15], u[0], (w' \oplus k)[5, 10, 15])$.

Thus for each of the $2^9$ guesses of $((w \oplus k)[4, 11, 14], u[5], (w' \oplus k)[4, 11, 14])$ we match two sets of subkey bits candidates $((w \oplus k)[5, 10, 15], u[0], (w' \oplus k)[5, 10, 15])$ and for each of those two sets we match two sets of subkey bits candidates of $((w \oplus k)[7, 8, 13], u[15], (w' \oplus k)[7, 8, 13])$. So overall, we get $2^{52.12} \times 2^9 \times 2 \times 2 = 2^{63.12}$ candidate triplets $(P, P', \text{information bits of key})$.

The information bits of subkeys involved in the attack have linear representations in key bits $w$ and $k$, which are shown in Tab. 7 of Appendix E. The resulting linear system of equations has 84 equations (each corresponds to a guessed/implied subkey bit in the attack) in 77 variables ($w$ and $k$ bits), and its rank is 75. This means that the remaining triplets give $2^{63.12}$ possible values for 75 key bits, hence reducing the space for about 11.88 bits.

### 6.2.2 Recovering the Whole Key

If we repeat the attack steps once again with a new set of data, the data and time complexity will increase by a factor of 2, each. But, the key space is reduced by a factor of $2^{11.88}$. So, the remaining candidate keys will become $2^{63.12-11.88} = 2^{51.24}$.
In general, the time complexity of repeating the attack for $N$ times is $2^{63.12} \times N$, and the complexity of the exhaustive search of the remaining key bits is $2^{128-11.88N}$, so the time complexity would be $2^{128-11.88N} + 2^{63.12} \times N$, which is minimized at $N = 6$. All in all, the time, data, and memory complexities of the attack are:

$$ 
\begin{aligned}
\mathcal{D} &= 6 \times 2^{46.8} = 2^{49.39} \\
\mathcal{T} &= 2^{63.12} \times 6 + 2^{128-11.88 \times 6} = 2^{65.72}
\end{aligned}
\qquad (21) $$

$$ 
\begin{aligned}
\mathcal{M} &= 2^{63.12} \\
\mathcal{T}\mathcal{D} &= 2^{115.11} < 2^{128}.
\end{aligned}
\qquad (22) $$

## 6.3 Single-Tweak Key Recovery Attack on 10-Round QARMAv1-128

The attack on QARMAv1-128 shares many similarities with QARMAv1-64 and uses the same 4-round pattern for truncated distinguisher with probability $2^{-107.60}$. Therefore, in this section, we will focus on highlighting the distinctions between them to avoid repeating the details already discussed.

**Precomputation Phase.** For QARMAv1-128, we also have linear relations in the subkey bits which are used in the precomputation phase of the attack. Based on the linear description of subkey bits involved in the attack given in Appendix E, we have the following linear relations between the subkey bits of $(w \oplus k)$, $u$ and $(w' \oplus k)$:

$$ 
\begin{aligned}
(w' \oplus k)[4]_2 + (w' \oplus k)[11]_3 + (w' \oplus k)[14]_7 &= (w \oplus k)[4]_1 + (w \oplus k)[11]_2 + (w \oplus k)[14]_6 + u[5]_{5,6} \\
(w' \oplus k)[4]_3 + (w' \oplus k)[11]_4 + (w' \oplus k)[14]_8 &= (w \oplus k)[4]_2 + (w \oplus k)[11]_3 + (w \oplus k)[14]_7 + u[5]_{6,7} \\
(w' \oplus k)[4]_4 + (w' \oplus k)[11]_5 + (w' \oplus k)[14]_{2...8} &= (w \oplus k)[4]_3 + (w \oplus k)[11]_4 + (w \oplus k)[14]_{1...7} + u[5]_{7,8} \\
(w' \oplus k)[4]_5 + (w' \oplus k)[11]_6 + (w' \oplus k)[14]_2 &= (w \oplus k)[4]_4 + (w \oplus k)[11]_5 + (w \oplus k)[14]_1 + u[5]_{1,8} \\
(w' \oplus k)[4]_6 + (w' \oplus k)[11]_7 + (w' \oplus k)[14]_3 &= (w \oplus k)[4]_5 + (w \oplus k)[11]_6 + (w \oplus k)[14]_2 + u[5]_{1,2} \\
(w' \oplus k)[4]_7 + (w' \oplus k)[11]_8 + (w' \oplus k)[14]_4 &= (w \oplus k)[4]_6 + (w \oplus k)[11]_7 + (w \oplus k)[14]_3 + u[5]_{2,3} \\
(w' \oplus k)[4]_8 + (w' \oplus k)[11]_{2...8} + (w' \oplus k)[14]_5 &= (w \oplus k)[4]_7 + (w \oplus k)[11]_{1...7} + (w \oplus k)[14]_4 + u[5]_{3,4}
\end{aligned}
$$

Thus if we guess the $2^{24}$ possible values of $(w \oplus k)[4, 11, 14]$, the $2^8$ possible values of $u[5]$, the $2^8$ possible values of $(w' \oplus k)[4]$, and the $2^{48}$ possible values of $(C, C')[4, 11, 14]$, we would be able to compute $(w' \oplus k)[11]$ and $(w' \oplus k)[14]$, as in Step 1 of the attack. Then, the seven linear relations between the subkey bits apply a 7-bit filter on $(w' \oplus k)[4]$ and only two possible values of $(w' \oplus k)[4]$ remain for each triplet of $((w \oplus k)[4, 11, 14], u[5], (C, C')[4, 11, 14])$. We can now compute a precomputation table of the values of $(w' \oplus k)[4]$ for each possible $((w \oplus k)[4, 11, 14], u[5], (C, C')[4, 11, 14])$. Thus we have a size $2^{81}$ precomputation table of the 2 possible values of $(w' \oplus k)[4]$ for each of the $2^{80}$ possible values of $((w \oplus k)[4, 11, 14], u[5], (C, C')[4, 11, 14])$.

Similarly, we can compute the same precomputation table for the values of $(w' \oplus k)[5]$ and $(w' \oplus k)[7]$.

**Generating Pairs.** Each structure contains $2^{9m} = 2^{72}$ plaintexts, which are constant in 7 non-active words, taking all possible values in the other words. The total number of pairs in each structure is $\frac{1}{2}(2^m(2^m - 1))^9 = 2^{142.94}$. The filtering probability is $P_{Filt} = (2^{-15.99})^4 = 2^{-63.96}$. It must be held that $2^{s+142.94} = 2^{107.60+63.96}$ which gives $s = 28.62$. Therefore, the data required for the attack is $2^{s+72} = 2^{100.62}$. Finally, the probability of sieving the ciphertext pairs is $P_{sieve} = (2^{-8})^7 \times (\frac{255}{256})^9 = 2^{-56.05}$, and the total number of pairs after sieving is $2^{s+142.94-56.05} = 2^{115.51}$.
**Attack Steps.** Since the attack steps is very similar to QARMAv1-64's, which are performed for each of the $2^{101.68}$ pairs of data. In the following, we just report the time complexity of each step.

1. The time complexity of this step is $2^{115.51} \times 2^8 = 2^{123.51}$.

2. The time complexity after this step is $2^{123.51} \times 2^8 \times 2 = 2^{132.51}$.

3. In this step, it should hold that $\Delta Z_7[4] = \rho^{-5}\Delta X_8[5]$ and $\Delta Z_2[4] = \rho^{-5}\Delta X_2[5]$.

4. After repeating Steps 1,2 and 3 with $((w' \oplus k)[5], u[0])$ and $((w' \oplus k)[7], u[15])$, the time complexity is now $3 \times 2^{132.51} = 2^{134.10}$.

5. The three different candidate subkey bits should be matched by merging the list of the $2^{17}$ differences $(\Delta_i Z_2[4], \Delta_i Z_7[4])$, $1 \le i \le 3$, computed in Step 3 using $u[5]$, $u[0]$, and $u[15]$.

Thus for each of the $2^{17}$ guesses of $((w \oplus k)[4, 11, 14], u[5], (w' \oplus k)[4, 11, 14])$ we match two sets of subkey bits candidates $((w \oplus k)[5, 10, 15], u[0], (w' \oplus k)[5, 10, 15])$ and for each of those two sets we match two sets of subkey bits candidates of $((w \oplus k)[7, 8, 13], u[15], (w' \oplus k)[7, 8, 13])$. So overall, we get $2^{115.51} \times 2^{17} \times 2 \times 2 = 2^{134.51}$ candidate triplets $(P, P', \text{information bits of key})$.

The linear representations of the information bits of subkeys involved in the attack in key bits $w$ and $k$ are shown in Tab. 8 of Appendix E. The resulting linear system of equations has 168 equations in 149 variables, with rank 147. This means that the remaining triplets give $2^{134.51}$ possible values for 147 key bits, hence reducing the space for about 12.49 bits.

### 6.3.1 Recovering the Whole Key

The time complexity of repeating the attack $N$ times is $2^{134.51} \times N$, and the complexity of the exhaustive search of the remaining key bits is $2^{256-12.49N}$, so the time complexity would be $2^{256-12.49N} + 2^{134.51} \times N$, which is minimized at $N = 10$. All in all, the time, data, and memory complexities of the attack are:

$$ 
\begin{aligned}
\mathcal{D} &= 10 \times 2^{100.62} = 2^{103.95} \\
\mathcal{T} &= 2^{256-12.49 \times 10} + 2^{134.51} \times 10 = 2^{137.84} \\
\mathcal{M} &= 2^{134.51} \\
\mathcal{T}\mathcal{D} &= 2^{241.79} < 2^{256}. \qquad (23)
\end{aligned}
$$

## 6.4 Single-Tweak Key Recovery Attack on 10-Round QARMAv2-64

In this section, we present a 10-round attack on QARMAv2-64, illustrated in Fig. 6. Despite sharing the same pattern of active nibbles throughout the cipher with QARMAv1-64, the attack on QARMAv2 follows a modified strategy due to variations in key schedules. We again use the equivalent representation of QARMAv2-64, in which the AddRoundTweak layer of all rounds, are replaced by an equivalent key $K'_i = M(\tau(K_i))$ ($L'_i = M(\tau(L_i))$), $i = 0, 1$, XORed in after (before) the MixColumn layer in the forward (backward) round functions.

The attack overview is outlined as follows: initially, we select a set of (pairs of) plaintexts based on the differential input to the cipher and filter them according to the resulting differential output. Subsequently, we compute the differential input and output of the distinguisher for each pair, denoted as $(\Delta Z_2[4], \Delta Z_7[4])$ along three distinct paths, each dependent on a set of subkeys. The values of the relevant subkeys, along with their corresponding $(\Delta Z_2[4], \Delta Z_7[4])$ pairs, are organized into three separate lists, namely $\mathcal{L}_1, \mathcal{L}_2,$
<figure><img src="image_7.png" /><figcaption>Figure 6: 10-round truncated differential attack on QARMAv2-64</figcaption></figure>

and $\mathcal{L}_3$. Finally, these lists are consolidated, and candidate subkeys are filtered based on the redundancy of the subkeys involved. In the initial path, the computation of differences $(\Delta Z_2[4], \Delta Z_7[4])$ depends on the subkeys $(K_0[7,8,13], L_1[7,8,13], K'_1[15], L'_0[15])$. So, we construct list $\mathcal{L}_1$ as follows:

$$ \mathcal{L}_1 : (K_0[7,8,13], L_1[7,8,13], K'_1[15], L'_0[15], \Delta Z_2[4], \Delta Z_7[4]) \quad (24) $$

Similarly, the other two lists $\mathcal{L}_2$ and $\mathcal{L}_3$, are constructed, as follows:

$$ \mathcal{L}_2 : (K_0[4,11,14], L_1[4,11,14], K'_1[5], L'_0[5], \Delta Z_2[4], \Delta Z_7[4]) \quad (25) $$

$$ \mathcal{L}_3 : (K_0[5,10,15], L_1[5,10,15], K'_1[0], L'_0[0], \Delta Z_2[4], \Delta Z_7[4]) \quad (26) $$

Note that the attack benefits from both inter-list dependencies (relationships between subkeys of different lists) and intra-list dependencies (relationships within the subkeys of the same list).
**Subkey Relations.** Using relations $K'_1 = \mathbb{M}(\tau(K_1))$ and $L'_0 = \mathbb{M}(\tau(L_0))$, the exploited subkey relations would be outlined as (27) to (32)

$$ K'_1[0] = \rho K_1[10] + \rho^2 K_1[5] + \rho^3 K_1[15] \rightarrow \left\{ \begin{array}{l} K'_1[0]_0 = L_1[10]_0 + L_1[5]_1 + L_1[15]_2 + L_1[0]_0 \\ K'_1[0]_1 = L_1[10]_1 + L_1[5]_2 + L_1[14]_3 \\ K'_1[0]_2 = L_1[10]_2 + L_1[4]_3 + L_1[15]_0 \\ K'_1[0]_3 = L_1[9]_3 + L_1[5]_0 + L_1[15]_1 \end{array} \right. \quad (27) $$

$$ K'_1[5] = \rho^3 K_1[11] + \rho K_1[14] + \rho^2 K_1[4] \rightarrow \left\{ \begin{array}{l} K'_1[5]_0 = L_1[11]_2 + L_1[14]_0 + L_1[4]_1 \\ K'_1[5]_1 = L_1[10]_3 + L_1[14]_1 + L_1[4]_2 \\ K'_1[5]_2 = L_1[11]_0 + L_1[14]_2 + L_1[3]_3 \\ K'_1[5]_3 = L_1[11]_1 + L_1[13]_3 + L_1[4]_0 \end{array} \right. \quad (28) $$

$$ K'_1[15] = \rho K_1[13] + \rho^2 K_1[7] + \rho^3 K_1[8] \rightarrow \left\{ \begin{array}{l} K'_1[15]_0 = L_1[13]_0 + L_1[7]_1 + L_1[8]_2 \\ K'_1[15]_1 = L_1[13]_1 + L_1[7]_2 + L_1[7]_3 \\ K'_1[15]_2 = L_1[13]_2 + L_1[6]_3 + L_1[8]_0 \\ K'_1[15]_3 = L_1[12]_3 + L_1[7]_0 + L_1[8]_1 \end{array} \right. \quad (29) $$

$$ L'_0[0] = \rho L_0[10] + \rho^2 L_0[5] + \rho^3 L_0[15] \rightarrow \left\{ \begin{array}{l} L'_0[0]_0 = K_0[10]_0 + K_0[5]_1 + K_0[15]_2 + K_0[0]_0 \\ L'_0[0]_1 = K_0[10]_1 + K_0[5]_2 + K_0[14]_3 \\ L'_0[0]_2 = K_0[10]_2 + K_0[4]_3 + K_0[15]_0 \\ L'_0[0]_3 = K_0[9]_3 + K_0[5]_0 + K_0[15]_1 \end{array} \right. \quad (30) $$

$$ L'_0[5] = \rho^3 L_0[11] + \rho L_0[14] + \rho^2 L_0[4] \rightarrow \left\{ \begin{array}{l} L'_0[5]_0 = K_0[11]_2 + K_0[14]_0 + K_0[4]_1 \\ L'_0[5]_1 = K_0[10]_3 + K_0[14]_1 + K_0[4]_2 \\ L'_0[5]_2 = K_0[11]_0 + K_0[14]_2 + K_0[3]_3 \\ L'_0[5]_3 = K_0[11]_1 + K_0[13]_3 + K_0[4]_0 \end{array} \right. \quad (31) $$

$$ L'_0[15] = \rho L_0[13] + \rho^2 L_0[7] + \rho^3 L_0[8] \rightarrow \left\{ \begin{array}{l} L'_0[15]_0 = K_0[13]_0 + K_0[7]_1 + K_0[8]_2 \\ L'_0[15]_1 = K_0[13]_1 + K_0[7]_2 + K_0[7]_3 \\ L'_0[15]_2 = K_0[13]_2 + K_0[6]_3 + K_0[8]_0 \\ L'_0[15]_3 = K_0[12]_3 + K_0[7]_0 + K_0[8]_1 \end{array} \right. \quad (32) $$

**Generating Pairs.** We choose $2^s$ structures of $2^{36}$ plaintexts, which are constant in the seven non-active nibbles {0,1,2,3,6,9,12}, and take all possible values in the other nibbles. Since none of the differential pairs should share similar values in the active nibbles, the total number of pairs in each structure is $\frac{1}{2}(2^4(2^4 - 1))^9 = 2^{70.16}$. Hence, we have $2^{s+70.16}$ pairs of plaintexts in total. According to the BPT of the diffusion matrix, which can be found in Appendix C, the filtering probability is $P_{Filt} = (2^{-7.81})^4 = 2^{-31.25}$, because of the three column transitions in the first MixColumns, and the one in the second. So, it must be held that $2^{s+70.16} = 2^{48.27+31.25}$ which gives $s = 9.36$. Therefore, the data required for the attack is $2^{s+36} = 2^{45.36}$. Finally, the probability of sieving the ciphertext pairs is $P_{sieve} = (2^{-4})^7 \times (\frac{15}{16})^9 = 2^{-28.84}$ due to the 7 non-active and the 9 active nibbles, and the total number of pairs after sieving is $2^{s+70.16-28.84} = 2^{50.68}$.

**Attack Steps.** For each of the $2^{50.68}$ candidate pairs the following steps are performed:

1. Similar to the first step in key recovery attack on QARMAv1-64, we guess $K_0[7]$ and $L_1[7]$ and compute $(K_0[8,13], (Y_1, Y'_1)[15])$ and $(L_1[8,13], (Y_8, Y'_8)[15])$, respectively. Then,

(a) We guess $L_1[6]_3, L_1[12]_3$. Utilizing the other guessed bits from $L_1$ in (29), we calculate $K'_1[15]$. Subsequently, $\Delta Z_2[4]$ can be computed.
(b) Similarly, we make guesses for $K_0[6]_3$ and $K_0[12]_3$. Using the known value of $L'_0[15]$ as specified in (32), we compute $\Delta Z_7[4]$.

All guessed values for subkeys, along with the resulting values for $(\Delta Z_2[4], \Delta Z_7[4])$ for each subkey guess, are incorporated into the list $\mathcal{L}_1$ as defined in (24). The time complexity of this step is $2^8(2^2 + 2^3) = 2^{11}$, and the size of $\mathcal{L}_1$ is $2^{12}$.

2. Likewise Step 1, we guess $K_0[4]$ and $L_1[4]$ and compute $(K_0[11, 14], (Y_1, Y'_1)[5])$ and $(L_1[11, 14], (Y_8, Y'_8)[5])$, respectively. Then,

(a) We guess $L_1[3]_3$, $L_1[10]_3$, and $L_1[13]_3$, and compute $K'_1[5]$ by (28). Then, $\Delta Z_2[4]$ can be obtained.

(b) We also guess $K_0[3]_3$, $K_0[10]_3$, and $K_0[13]_3$, and compute $L'_0[5]$ by (31). Then, $\Delta Z_7[4]$ can be obtained.

Similar to Step 1, we construct list $\mathcal{L}_2$, as defined in (25). The time complexity of this step is $2^8(2^3 + 2^3) = 2^{12}$ and the size of $\mathcal{L}_2$ is $2^{14}$.

3. Likewise Step 1, we guess $K_0[5]$ and $L_1[5]$ and compute $(K_0[10, 15], (Y_1, Y'_1)[0])$ and $(L_1[10, 15], (Y_8, Y'_8)[0])$, respectively. Then,

(a) We guess $L_1[0]_0$, $L_1[9]_3$, and $L_1[14]_3$, and compute $K'_1[0]$ by (27). Then, $\Delta Z_2[4]$ can be obtained.

(b) We also guess $K_0[0]_0$, $K_0[9]_3$, and $K_0[14]_3$, and compute $L'_0[0]$ by (30). Then, $\Delta Z_7[4]$ can be obtained.

Similar to Step 1, we construct list $\mathcal{L}_3$, as defined in (26). The time complexity of this step is $2^8(2^3 + 2^3) = 2^{12}$ and the size of $\mathcal{L}_3$ is $2^{14}$.

4. In the last step, we merge lists $\mathcal{L}_1$, $\mathcal{L}_2$ and $\mathcal{L}_3$. For this purpose,

(a) For each $2^{12}$ tuple in $\mathcal{L}_1$, we get $(\Delta Z_2[4], \Delta Z_7[4])$.

(b) For each $(\Delta Z_2[4], \Delta Z_7[4])$ from Step 4.a, we get $2^6$ values for subkeys involved in $\mathcal{L}_2$. Since $L_1[13]_3$ and $K_0[13]_3$ are present in both $\mathcal{L}_1$ and $\mathcal{L}_2$, the overall subkey candidates undergo a filtering process by a factor of $2^{-2}$. Consequently, we have $2^{12} \times 2^6 \times 2^{-2} = 2^{16}$ candidates at the end of this step.

(c) For each $2^{16}$ candidates from Step 4.c, we get $2^6$ values for the subkeys involved in $\mathcal{L}_3$. Since $L_1[10]_3$, $L_1[14]_3$ and $K_0[10]_3$, $K_0[14]_3$ are present in both $\mathcal{L}_2$ and $\mathcal{L}_3$, the number of subkey candidates would be $2^{16} \times 2^6 \times 2^{-4} = 2^{18}$.

Finally, we repeat these steps for each of the $2^{50.68}$ pairs. Consequently, we accumulate $2^{50.68} \times 2^{18} = 2^{68.68}$ candidates for the 88 involved subkey bits. This results in a reduction of the key space by a factor of $2^{19.32}$. The time complexity of these steps is as follows:

$$2^{50.68}(2^{11} + 2^{12} + 2^{12} + 2^{18}) \approx 2^{68.68}$$

### 6.4.1 Recovering the Whole Key

We repeat the attack steps $N$ times. So, the total time complexity would be $N \times 2^{68.68} + 2^{128-19.32N}$, which is minimized at $N = 4$. Therefore, the data, time, and memory complexities of the attack are:

$$ \begin{aligned} \mathcal{D} &= 4 \times 2^{45.36} = 2^{47.36} \\ \mathcal{T} &= 4 \times 2^{68.68} + 2^{128-19.32 \times 4} = 2^{70.68} \\ \mathcal{M} &= 2^{68.68} \end{aligned} \qquad (33) $$
<figure><img src="image_8.png" /><figcaption>Figure 7: 11-round truncated differential attack on QARMAv2-64</figcaption></figure>

## 6.5 Single-Tweak Key Recovery Attack on 11-Round QARMAv2-64

As stated in Sec. 5.1.5, QARMAv2-64 no longer relies on time-data trade-offs as the foundation for determining security levels. This enables us to extend the 10-round attack to one round more, as detailed in the following.

**Generating Pairs.** As in 10-round attack in Sec. 6.4, we choose $2^s$ structures of $2^{36}$ plaintexts, which are constant in the 7 non-active nibbles {0,1,2,3,6,9,12}, and take all possible values in the other nibbles, according to Fig. 7. The total number of pairs in each structure is $\frac{1}{2}(2^4(2^4 - 1))^9 = 2^{70.16}$ and we have $2^{s+70.16}$ pairs of plaintexts in total. Similarly, the filtering probability is $P_{Filt} = (2^{-7.81})^4 = 2^{-31.25}$ according to the BPT of the diffusion matrix. So, it must be held that $2^{s+70.16} = 2^{48.27+31.25}$ which gives $s = 9.36$. Therefore, the data required for the attack is $2^{s+36} = 2^{45.36}$. Finally, there is no sieving due to the fully active state in the cipher output and the attack will proceed with $2^{s+70.16} = 2^{79.52}$ pairs.

**Attack Steps.** For each of the $2^{79.52}$ candidate pairs the following steps are performed:
1. We guess $2^8$ possible values for $L_0[0,5]$ and compute $(X_{10}, X'_{10})[0,5]$ as well as $\Delta X_{10}[0,5]$. Since the differences in two nibbles in the last MixColumn input as well as differences in two nibbles in its output are known, the other four nibbles differences can be computed. In this way, $\Delta C[0,5,10,15]$ and $\Delta X_{10}[0,5,10,15]$ are known.

So, for each guess of $L_0[0,5]$ per pair, we have one value for $L_0[10,15]$, in average. The time complexity of this step is $2^{79.52} \times 2^8 = 2^{87.52}$ and we have $2^{79.52+8} = 2^{87.52}$ candidates at the end of this step.

2. Based on the key schedule, $K_0[5]_{0,1,2}$, $K_0[10]_{0,1,2}$, $K_0[15]_{0,1}$ can be computed from $L_0[0,5,10,15]$, already determined in the previous step. So, we just need to guess $K_0[5]_3$, $K_0[10]_3$, $K_0[15]_{2,3}$ to compute $\Delta Y_1[0,4,8,12]$. According to the BPT of the diffusion matrix, the probability of $\Delta Y_1[0] \neq 0$ and $\Delta Y_1[4] = \Delta Y_1[8] = \Delta Y_1[12] = 0$ for the chosen pairs is equal to $2^{-7.81}$. Hence, we come up with $2^{87.52+4-7.81} = 2^{83.71}$ candidates at the end of this step with time complexity $2^{87.52+4} = 2^{91.52}$.

3. Similar to step 1, we guess $2^8$ possible values for $L_0[1,4]$ and compute values of $L_0[11,14]$. So, we have $2^{83.71+8} = 2^{91.71}$ candidates at the end of this step with time complexity $2^{83.71+8} = 2^{91.71}$.

4. Based on the key schedule, $K_0[4]$, $K_0[11]_{0,1,2}$, and $K_0[14]$ can be computed from $L_0[4,5,11,14,15]$, already guessed in Steps 1 and 3. So, we just need to guess $K_0[11]_3$ to compute $\Delta Y_1[1,5,9,13]$. Likewise Step 2, the probability of $\Delta Y_1[5] \neq 0$ and $\Delta Y_1[1] = \Delta Y_1[9] = \Delta Y_1[13] = 0$ for the chosen pairs equals $2^{-7.81}$, according to the BPT of the diffusion matrix. Therefore, we have $2^{91.71+1-7.81} = 2^{84.9}$ candidates with time complexity $2^{92.71}$ at the end of this step.

5. Since there are three nibbles with non-zero difference in the output of the third column of the last MixColumn as well as its input, we need to guess three nibbles of the subkeys $L_0[2,7,8,13]$ to compute the fourth nibble. Hence, we have $2^{84.9+12} = 2^{96.9}$ candidates with time complexity $2^{96.9}$ at the end of this step.

6. From the already guessed subkeys $L_0[7,8,13,14]$, we can compute the whole bits of subkeys $K_0[7,8,13]$ except $K_0[8]_3$, which should be guessed. Then, $\Delta Y_1[3,7,11,15]$ can be computed. Given the probability of $2^{-7.81}$ for $\Delta Y_1[15] \neq 0$ and $\Delta Y_1[3] = \Delta Y_1[7] = \Delta Y_1[11] = 0$ for the chosen pairs, we end up with $2^{96.9+1-7.81} = 2^{90.09}$ candidates. The time complexity at the end of this step is $2^{97.9}$.

7. Similar to Step 1, we guess $2^8$ possible values for $L_0[3,6]$ and compute values of $L_0[9,12]$. However, there is a filter with probability $2^{-3}$ since $L_0[6]_0$, $L_0[9]_0$ and $L_0[12]_0$ should comply with the already known values $K_0[5]_3$, $K_0[8]_3$ and $K_0[11]_3$, respectively. So, we have $2^{90.09+8-3} = 2^{95.09}$ candidates at the end of this step with time complexity $2^{98.09}$.

8. We refer to a precomputation table, indexed by $((X_9, X'_9)[4,5,7,8,10,11,13,14,15], L'_0[0,5,15])$. In each entry of this table, the possible values for the combinations of $L'_1[4,11,14]$, $L'_1[5,10,15]$ and $L'_1[7,8,13]$ are stored in a way that the differential pattern of the distinguisher's output is satisfied. For the number of candidates in each entry, since there are $2^4$ possible values for each set of $L'_1[4,11,14]$, $L'_1[5,10,15]$ and $L'_1[7,8,13]$, independently (i.e. $2^{12}$ candidates for their combinations in total), and the probability $2^{-7.81}$ for getting the differential output of the distinguisher for the filtered pairs, there are $2^{12-7.81} = 2^{4.19}$ possible values for $L'_1[4,5,7,8,10,11,13,14,15]$ in each entry. The required memory to store such a table is $2^{84+4.19} = 2^{88.19}$. Hence, we have $2^{95.09+4.19} = 2^{99.28}$ candidates at the end of this step with time complexity $2^{95.09}$.
9. Finally, we guess $2^4$ possible values for $K'_1[0]$ and compute $K'_1[5,15]$ in order to have $\Delta Z_2[4] \neq 0$ and $\Delta Z_2[0] = \Delta Z_2[8] = \Delta Z_2[12] = 0$. Therefore, we have $2^{99.28+4} = 2^{103.28}$ candidates at the end of this step with time complexity $2^{103.28}$ which is the dominant time complexity of the attack.

Since we achieve $2^{103.28}$ candidates for 112 involved key bits, the key space is reduced by a factor of $2^{8.72}$ with time complexity $2^{103.28}$.

### 6.5.1 Recovering the Whole Key

We repeat the attack steps $N$ times. So, the total time complexity would be $N \times 2^{103.28} + 2^{128-8.72N}$, which is minimized at $N = 3$. Therefore, the data, time, and memory complexities of the attack are:

$$ 
\begin{align} 
\mathcal{D} &= 3 \times 2^{45.36} = 2^{46.94} \nonumber \\ 
\mathcal{T} &= 3 \times 2^{103.28} + 2^{128-8.72 \times 3} = 2^{104.86} + 2^{101.84} = 2^{105.03} \tag{34} \\ 
\mathcal{M} &= 2^{103.28} \nonumber 
\end{align} 
$$

## 7 Conclusion

We have generalized and provided some new insights on truncated differential attacks, contributing to potential future research directions. We showcased a successful application of this attack to specific variants within the QARMA family of ciphers. It led to the only valid known attack in the single-tweak model on QARMAv1-64, QARMAv1-128, and QARMAv2-64 variants. Our proposed attacks reached up to 10 rounds of QARMAv1-64 and QARMAv1-128, maintaining adherence to the time-data trade-off security claimed by the designers, and 11-round of QARMAv2-64, satisfying the data limit provided by its designers. Although the designers have not made any claims for the single-tweak model, our findings indicate that QARMAv2-64, despite the version update, does not offer a higher level of security compared to QARMAv1-64 in this model.

To execute these attacks, we employed optimal truncated differential distinguishers identified through an automatic MILP- and SAT-based search. We introduced an enhanced variant-specific key-recovery procedure. Tailored to the target variant under analysis, our approach utilizes a combination of list merging techniques and precomputation, resulting in a significant reduction in time complexity.

## Acknowledgment

The research conducted by Maria Naya-Plasencia and Dounia Mfoukh in this project has received funding from the European Research Council (ERC) under the European Unions Horizon 2020 research and innovation programme (grant agreement no. 714294 - acronym QUASYModo). The authors would like to thank Mohammadjavad Chaveleh for his assistance in the SAT modeling of the attack.

## References

[1] L. R. Knudsen, “Truncated and higher order differentials,” in *Fast Software Encryption: Second International Workshop Leuven, Belgium, December 14–16, 1994 Proceedings 2*, pp. 196–211, Springer, 1995.

[2] V. Lallemand and M. Naya-Plasencia, “Cryptanalysis of KLEIN,” in *International Workshop on Fast Software Encryption*, pp. 451–470, Springer, 2014.
[3] S. Rasoolzadeh, Z. Ahmadian, M. Salmasizadeh, and M. R. Aref, "An improved truncated differential cryptanalysis of KLEIN," *Tatra Mountains Mathematical Publications*, vol. 67, no. 1, pp. 135-147, 2016.

[4] L. Li, K. Jia, X. Wang, and X. Dong, "Meet-in-the-middle technique for truncated differential and its applications to CLEFIA and camellia," in *International Workshop on Fast Software Encryption*, pp. 48-70, Springer, 2015.

[5] A. Abdelkhalek, Y. Sasaki, Y. Todo, M. Tolba, and A. M. Youssef, "Milp modeling for (large) s-boxes to optimize probability of differential characteristics," *IACR Transactions on Symmetric Cryptology*, pp. 99-129, 2017.

[6] A. Ebrahimi Moghaddam and Z. Ahmadian, "New automatic search method for truncated-differential characteristics application to Midori, SKINNY and CRAFT," *The Computer Journal*, vol. 63, no. 12, pp. 1813-1825, 2020.

[7] M. Eichlseder, G. Leander, and S. Rasoolzadeh, "Computing expected differential probability of (truncated) differentials and expected linear potential of (multidimensional) linear hulls in spn block ciphers," in *Progress in Cryptology-INDOCRYPT 2020: 21st International Conference on Cryptology in India, Bangalore, India, December 13-16, 2020, Proceedings 21*, pp. 345-369, Springer, 2020.

[8] H. Guo, Z. Zhang, Q. Yang, L. Hu, and Y. Luo, "A new method to find all the high-probability word-oriented truncated differentials: Application to Midori, SKINNY and CRAFT," *The Computer Journal*, vol. 66, no. 5, pp. 1069-1082, 2023.

[9] X. Xie and T. Tian, "The triangle differential cryptanalysis," in *Australasian Conference on Information Security and Privacy*, pp. 72-88, Springer, 2023.

[10] X. Xie and T. Tian, "Structural evaluation of AES-like ciphers against mixture differential cryptanalysis," *Designs, Codes and Cryptography*, pp. 1-19, 2023.

[11] J. Borghoff, A. Canteaut, T. Güneysu, E. B. Kavun, M. Knezevic, L. R. Knudsen, G. Leander, V. Nikov, C. Paar, C. Rechberger, et al., "PRINCE-a low-latency block cipher for pervasive computing applications," in *Advances in Cryptology-ASIACRYPT 2012: 18th International Conference on the Theory and Application of Cryptology and Information Security*, pp. 208-225, Springer, 2012.

[12] H. Soleimany, C. Blondeau, X. Yu, W. Wu, K. Nyberg, H. Zhang, L. Zhang, and Y. Wang, "Reflection cryptanalysis of PRINCE-like ciphers," *Journal of Cryptology*, vol. 28, pp. 718-744, 2015.

[13] C. Beierle, J. Jean, S. Kölbl, G. Leander, A. Moradi, T. Peyrin, Y. Sasaki, P. Sasdrich, and S. M. Sim, "The SKINNY family of block ciphers and its low-latency variant MANTIS," in *Advances in Cryptology-CRYPTO 2016: 36th Annual International Cryptology Conference*, pp. 123-153, Springer, 2016.

[14] S. Banik, A. Bogdanov, T. Isobe, K. Shibutani, H. Hiwatari, T. Akishita, and F. Regazzoni, "Midori: A block cipher for low energy," in *Advances in Cryptology-ASIACRYPT 2015: 21st International Conference on the Theory and Application of Cryptology and Information Security, Auckland, New Zealand, November 29-December 3, 2015, Proceedings, Part II 21*, pp. 411-436, Springer, 2015.

[15] C. Dobraunig, M. Eichlseder, D. Kales, and F. Mendel, "Practical key-recovery attack on MANTIS5," *IACR Transactions on Symmetric Cryptology*, pp. 248-260, 2016.
[16] R. Avanzi, S. Banik, O. Dunkelman, M. Eichlseder, S. Ghosh, M. Nageler, and F. Regazzoni, “The QARMAv2 family of tweakable block ciphers,” *IACR Transactions on Symmetric Cryptology*, vol. 2023, no. 3, pp. 25–73, 2023.

[17] R. Avanzi, “The QARMA block cipher family. almost mds matrices over rings with zero divisors, nearly symmetric even-mansour constructions with non-involutory central rounds, and search heuristics for low-latency s-boxes,” *IACR Transactions on Symmetric Cryptology*, pp. 4–44, 2017.

[18] S. Even and Y. Mansour, “A construction of a cipher from a single pseudorandom permutation,” *Journal of cryptology*, vol. 10, pp. 151–161, 1997.

[19] I. Dinur, “Cryptanalytic time-memory-data tradeoffs for fx-constructions with applications to PRINCE and PRIDE,” in *Annual International Conference on the Theory and Applications of Cryptographic Techniques*, pp. 231–253, Springer, 2015.

[20] S. Rasoolzadeh and H. Raddum, “Cryptanalysis of PRINCE with minimal data,” in *Progress in Cryptology–AFRICACRYPT 2016: 8th International Conference on Cryptology in Africa, Fes, Morocco, April 13-15, 2016, Proceedings* 8, pp. 109–126, Springer, 2016.

[21] R. Zong and X. Dong, “Meet-in-the-middle attack on QARMA block cipher,” *Cryptology ePrint Archive*, 2016.

[22] R. Li and C. Jin, “Meet-in-the-middle attacks on reduced-round QARMA-64/128,” *The Computer Journal*, vol. 61, no. 8, pp. 1158–1165, 2018.

[23] M. Li, K. Hu, and M. Wang, “Related-tweak statistical saturation cryptanalysis and its application on QARMA,” *Cryptology ePrint Archive*, 2019.

[24] Y. Liu, T. Zang, D. Gu, F. Zhao, W. Li, and Z. Liu, “Improved cryptanalysis of reduced-version QARMA-64/128,” *IEEE Access*, vol. 8, pp. 8361–8370, 2020.

[25] J. Du, W. Wang, M. Li, and M. Wang, “Related-tweakey impossible differential attack on QARMA-128,” *Science China Information Sciences*, vol. 65, no. 2, p. 129102, 2022.

[26] H. Hadipour and Y. Todo, “Cryptanalysis of qarmav2.” *Cryptology ePrint Archive*, Paper 2023/1833, 2023. https://eprint.iacr.org/2023/1833.

[27] N. Mouha, Q. Wang, D. Gu, and B. Preneel, “Differential and linear cryptanalysis using mixed-integer linear programming,” in *Information Security and Cryptology: 7th International Conference, Inscrypt 2011, Beijing, China, November 30–December 3, 2011. Revised Selected Papers* 7, pp. 57–76, Springer, 2012.

[28] X. Lai, J. L. Massey, and S. Murphy, “Markov ciphers and differential cryptanalysis,” in *Advances in CryptologyEUROCRYPT91: Workshop on the Theory and Application of Cryptographic Techniques Brighton, UK, April 8–11, 1991 Proceedings* 10, pp. 17–38, Springer, 1991.

[29] C. Blondeau, G. Leander, and K. Nyberg, “Differential-linear cryptanalysis revisited,” *Journal of Cryptology*, vol. 30, pp. 859–888, 2017.

[30] E. Biham and A. Shamir, “Differential cryptanalysis of DES-like cryptosystems,” *Journal of CRYPTOLOGY*, vol. 4, pp. 3–72, 1991.

[31] C. Boura, N. David, R. Heim Boissier, and M. Naya-Plasencia, “Better steady than speedy: full break of SPEEDY-7-192,” in *Annual International Conference on the Theory and Applications of Cryptographic Techniques*, pp. 36–66, Springer, 2023.
[32] M. Eichlseder and D. Kales, “Clustering related-tweak characteristics: application to MANTIS-6,” *IACR Transactions on Symmetric Cryptology*, pp. 111–132, 2018.

[33] R. Zong and X. Dong, “Milp-aided related-tweak/key impossible differential attack and its applications to qarma, joltik-bc,” *IEEE Access*, vol. 7, pp. 153683–153693, 2019.

[34] K. Sakamoto, R. Ito, and T. Isobe, “Parallel sat framework to find clustering of differential characteristics and its applications,” *Cryptology ePrint Archive*, 2023.

[35] R. Zong and X. Dong, “Milp-aided related-tweak/key impossible differential attack and its applications to qarma, joltik-bc,” *IEEE Access*, vol. 7, pp. 153683–153693, 2019.

[36] R. Ankele, C. Dobraunig, J. Guo, E. Lambooij, G. Leander, and Y. Todo, “Zero-correlation attacks on tweakable block ciphers with linear tweakey expansion,” 2019.

[37] D. Yang, W.-F. Qi, and H.-J. Chen, “Impossible differential attack on QARMA family of block ciphers,” *Cryptology ePrint Archive*, 2018.

[38] S. Banerjee and A. Roy, *Linear algebra and matrix analysis for statistics*. Crc Press, 2014.

# A Proofs of Theorems

## A.1 Proof of Proposition 2

By using Bayes theorem,

$$ 
\begin{aligned}
\Pr(\Delta_{out} \xrightarrow{E^{-1}} \Delta_{in}) &= \Pr(\Delta X \in \Delta_{in} | \Delta Y \in \Delta_{out}) \\
&= \Pr(\Delta Y \in \Delta_{out} | \Delta X \in \Delta_{in}) \frac{\Pr(\Delta X \in \Delta_{in})}{\Pr(\Delta Y \in \Delta_{out})} \\
&= \Pr(\Delta_{in} \xrightarrow{E} \Delta_{out}) \frac{|\Delta_{in}|}{|\Delta_{out}|}
\end{aligned} 
\quad (35) $$

where the last equality holds by assuming uniform distributions for $\Delta X$ and $\Delta Y$.

## A.2 Proof of Proposition 4

This proposition is proved by contradiction. Suppose that $(\Delta_{out} \xrightarrow{E^{-1}} \Delta_{in})$ is not optimum. So, there is another efficient differential $(\mathcal{U} \xrightarrow{E^{-1}} \mathcal{V})$ such that $P(\mathcal{U} \xrightarrow{E^{-1}} \mathcal{V})|\mathcal{U}| > P(\Delta_{out} \xrightarrow{E^{-1}} \Delta_{in})|\Delta_{out}|$. By Lemma 2, it holds that:

$$ 
\begin{aligned}
P(\mathcal{U} \xrightarrow{E^{-1}} \mathcal{V})|\mathcal{U}| &> P(\Delta_{out} \xrightarrow{E^{-1}} \Delta_{in})|\Delta_{out}| \\
P(\mathcal{V} \xrightarrow{E} \mathcal{U})|\mathcal{V}| &> P(\Delta_{in} \xrightarrow{E} \Delta_{out})|\Delta_{in}|
\end{aligned} 
\quad (36) $$

Eq. (36) means that $(\Delta_{in} \xrightarrow{E} \Delta_{out})$ is not the optimum truncated differential distinguisher for $E$, which is a contradiction. The proof of the reverse direction is analogous to this direction.
## A.3 Proof of Proposition 5

Using the law of total probability and the rule of union of disjoint events, we can write:

$$
\begin{align*}
\mathrm{Pr}(\Delta_{in} \rightarrow \Delta_{out}) &= \mathrm{Pr}(\Delta Y \in \Delta_{out} | \Delta X \in \Delta_{in}) \\
&= \sum_{\alpha \in \Delta_{in}} \mathrm{Pr}(\Delta Y \in \Delta_{out} | \Delta X \in \Delta_{in}, \Delta X = \alpha) \mathrm{Pr}(\Delta X = \alpha | \Delta X \in \Delta_{in}) \\
&= \frac{1}{|\Delta_{in}|} \sum_{\alpha \in \Delta_{in}} \mathrm{Pr}(\Delta Y \in \Delta_{out} | \Delta X = \alpha) \\
&= \frac{1}{|\Delta_{in}|} \sum_{\beta \in \Delta_{out}} \sum_{\alpha \in \Delta_{in}} \mathrm{Pr}(\Delta Y = \beta | \Delta X = \alpha) \\
&= \frac{1}{|\Delta_{in}|} \sum_{\substack{\alpha \in \Delta_{in}, \\ \beta \in \Delta_{out}}} \mathrm{Pr}(\alpha \rightarrow \beta)
\end{align*}
$$

## A.4 Proof of Theorem 1

Suppose that $P(\Delta_{out} \xrightarrow{E^{-1}} \Delta_{in}) = 2^{-p'}$. So, according to Lemma 2,

$$p' = p - \delta_{in} + \delta_{out} \qquad (37)$$

This distinguisher is efficient if $p' < n - \delta_{in}$ which, given (37), is equivalent to the efficiency of the forward distinguisher (7). Suppose that we construct $2^{s'}$ structures in the output of the cipher, each of which contains $2^{d_{out}}$ ciphertexts, that gives $2^{2d_{out}-1}$ pairs of ciphertexts. So, the total number of pairs would be $2^{s'+2d_{out}-1}$. The filtering probability from $D_{out}$ to $\Delta_{out}$ is $P'_{filt} = 2^{-(d_{out}-\delta_{out})}$. So, the total pairs required for the attack is $2^{p'+d_{out}-\delta_{out}}$ which must be equal to $2^{s'+2d_{out}-1}$. In this way, the total number of structures would be obtained as $2^{s'} = 2^{p'-d_{out}-\delta_{out}+1}$. Therefore, the data complexity of the attack is

$$D' = 2^{s'+d_{out}} = 2^{p'-\delta_{out}+1} = 2^{p-\delta_{in}+1} = D \qquad (38)$$

Finally, the sieving probability is $P'_{sieve} = 2^{-(n-d_{in})}$, and Total pairs after sieving is

$$P' = 2^{p'-n+d_{in}+d_{out}-\delta_{out}} = 2^{p-n+d_{in}+d_{out}-\delta_{in}} = P \qquad (39)$$

The time complexity of the attack mainly depends on $D'$ and $P'$.

## A.5 Proof of Lemma 2

Let $N(\mathbf{a}, \mathbf{b}) = |\{(\mathbf{x}, \mathbf{y}) \in \mathbb{F}_{2^m}^t \times \mathbb{F}_{2^m}^t | \mathbf{y} = M\mathbf{x}, \mathrm{Tr}(\mathbf{x}) = \mathbf{a}, \mathrm{Tr}(\mathbf{y}) = \mathbf{b}\}|$. Since $M$ is an MDS matrix, $N(\mathbf{a}, \mathbf{b}) = 0$ for $1 \le \mathrm{Hw}(\mathbf{a}) + \mathrm{Hw}(\mathbf{b}) \le t$ and $N(\mathbf{a}, \mathbf{b}) = 1$ for $\mathbf{a} = \mathbf{b} = 0$. Therefore, we have

$$\mathrm{Pr}(\mathbf{a} \rightarrow \mathbf{b}) = \begin{cases} 1 & \mathrm{Hw}(\mathbf{a}) + \mathrm{Hw}(\mathbf{b}) = 0 \\ 0 & 1 \le \mathrm{Hw}(\mathbf{a}) + \mathrm{Hw}(\mathbf{b}) \le t. \\ \frac{N(\mathbf{a}, \mathbf{b})}{(2^m - 1)^{\mathrm{Hw}(\mathbf{a})}} & \mathrm{Hw}(\mathbf{a}) + \mathrm{Hw}(\mathbf{b}) \ge t + 1 \end{cases} \qquad (40)$$

We first provide a recursive form for $N(\mathbf{a}, \mathbf{b})$, then show how (40) approximately equals (10). Let $Q(\mathbf{a}, \mathbf{b}) = |\{(\mathbf{x}, \mathbf{y}) \in \mathbb{F}_{2^m}^t \times \mathbb{F}_{2^m}^t | \mathbf{y} = M\mathbf{x}, \mathrm{Tr}(\mathbf{x}) \le \mathbf{a}, \mathrm{Tr}(\mathbf{y}) \le \mathbf{b}, \mathbf{x} \ne \mathbf{0}\}|$, where $\mathrm{Tr}(\mathbf{x}) \le \mathbf{a}$ means that $\mathrm{Tr}(\mathbf{x})$ is component-wise less than or equal to $\mathbf{a}$. According to the definitions of $N$ and $Q$, it holds that:

$$N(\mathbf{a}, \mathbf{b}) = Q(\mathbf{a}, \mathbf{b}) - \sum_{\substack{0 < \mathbf{a}' < \mathbf{a}, \\ 0 < \mathbf{b}' < \mathbf{b}}} N(\mathbf{a}', \mathbf{b}') \qquad (41)$$
It is more convenient to first compute $Q(\mathbf{a}, \mathbf{b})$, then $N(\mathbf{a}, \mathbf{b})$ according to (41). Let $\mathrm{Hw}(\mathbf{a}) = i$ and $\mathrm{Hw}(\mathbf{b}) = j$. Let $\mathcal{I}$ and $\mathcal{J}$ represent the index sets of zero components in $\mathbf{a}$ and $\mathbf{b}$, respectively. So, $|\mathcal{I}| = t - i$ and $|\mathcal{J}| = t - j$, and $\mathrm{Tr}(\mathbf{x}) \le \mathbf{a}$ implies $x_r = 0$ if $r \in \mathcal{I}$, and $\mathrm{Tr}(\mathbf{y}) \le \mathbf{b}$ implies $y_r = 0$ if $r \in \mathcal{J}$. All these constraints simplifies $Q(\mathbf{a}, \mathbf{b})$ into $Q(\mathbf{a}, \mathbf{b}) = |\{\mathbf{x}' \in \mathbb{F}_2^i | M'\mathbf{x}' = \mathbf{0}, \mathbf{x}' \ne \mathbf{0}\}|$, where $M' = M[\mathcal{J}, \mathcal{I}^c]$, i.e. $M'$ is a submatrix of $M$ with dimensions $t - j \times i$, obtained by retaining rows in $\mathcal{J}$, and removing columns in $\mathcal{I}$.

So, $Q(\mathbf{a}, \mathbf{b})$ would be the number of non-zero solutions for the homogeneous system of linear equations $M'\mathbf{x}' = \mathbf{0}$ over $\mathbb{F}_{2^m}$. Since $M$ is an MDS matrix, any submatrix of that, including $M'$ is non-singular. Therefore, according to Rouché–Capelli Theorem [38], it has a number of $2^{m(i-(t-j))} = 2^{m(i+j-t)}$ solutions, excluding $\mathbf{x}' = \mathbf{0}$, it would be

$$Q(\mathbf{a}, \mathbf{b}) = 2^{m(i+j-t)} - 1 \qquad (42)$$

According to (42), $Q(\mathbf{a}, \mathbf{b})$ only depends on $i$ and $j$, so for simplicity we can change the arguments $(\mathbf{a}, \mathbf{b})$ of $N$ and $Q$ into $(i, j)$, and (41) will be updated to

$$N(i, j) = 2^{m(i+j-t)} - 1 - \sum_{t+1 \le i' + j' < i+j} \binom{i}{i'} \binom{j}{j'} N(i', j') \qquad (43)$$

While (43) does not provide a direct formula for $N(i, j)$, it meets our needs adequately. Note that the terms within the summation, $N(i', j')$, are of order at most $2^{m(i+j-t-1)}$, much smaller than the first term $2^{m(i+j-t)}$, specifically for large $m$. Hence, we can approximate $N(i, j)$ by its dominant term, which is $2^{m(i+j-t)}$, by replacing $N(i, j) \approx 2^{m(i+j-t)}$ into (40), it holds that

$$\mathrm{Pr}(\mathbf{a} \to \mathbf{b}) \approx \frac{2^{m(i+j-t)}}{(2^m - 1)^i} \approx 2^{-m(t-j)}, \qquad (44)$$

which completes the proof.

## B Overview of full-round QARMA

An overview of the full-round QARMA family of block ciphers is given in Figures 8 and 9.

<figure><img src="image_9.png" /><figcaption>Figure 8: QARMAv1 full round [17]</figcaption></figure>
<figure><img src="image_10.png" /><figcaption>Figure 9: QARMAv2 full round [16]</figcaption></figure>

## C Branching Property Tables

**Definition 6** (Branching Property Table (BPT)). For matrix $M_{t \times t}$ over $\mathbb{F}_{2^m}$, the Branching Property Table is defined as a $2^t \times 2^t$ table whose entry $(\mathbf{a}, \mathbf{b})$ reflects the base-2 logarithm of $P(\mathbf{a} \xrightarrow{M} \mathbf{b})$:

$$ BPT(\mathbf{a}, \mathbf{b}) = \log_2(\Pr_{\mathbf{x}}\{\mathrm{Tr}(M \cdot \mathbf{x}) = \mathbf{b} | \mathrm{Tr}(\mathbf{x}) = \mathbf{a}\}) \quad (45) $$

where $\mathbf{a} = [a_3, a_2, a_1, a_0]^\top$, $\mathbf{b} = [b_3, b_2, b_1, b_0]^\top \in \mathbb{F}_t^2$, and $\mathrm{Tr}(\cdot)$ is the $m$-bit truncation operator. The impossible transitions are shown by a "-".

Tables 2 and 4 show the Branching Property Table (BPT) for QARMA-64/128 MixColumns Matrix $M(=Q)$. Table 5 includes the accurate and approximated BPT for all $t \times t$ MDS matrices for $t = 4$ and $m = 4, 8$. Since, for accurate MDS matrices the transition probabilities depend only on $Hw(\mathbf{a})$ and $Hw(\mathbf{b})$, the BPT reduces to a $(t+1) \times (t+1)$ table.

<table><caption>Table 2: BPT for QARMAv1-64 MixColumns Matrix $M_4$</caption><thead><tr><th>a / b</th><th>0x0</th><th>0x1</th><th>0x2</th><th>0x3</th><th>0x4</th><th>0x5</th><th>0x6</th><th>0x7</th><th>0x8</th><th>0x9</th><th>0xa</th><th>0xb</th><th>0xc</th><th>0xd</th><th>0xe</th><th>0xf</th></tr></thead><tbody><tr><td>0x0</td><td>0</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td></tr><tr><td>0x1</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>0</td><td>-</td></tr><tr><td>0x2</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>0</td><td>-</td><td>-</td></tr><tr><td>0x3</td><td>-</td><td>-</td><td>-</td><td>-6.229</td><td>-</td><td>-</td><td>-</td><td>-4.229</td><td>-</td><td>-</td><td>-4.229</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-0.184</td></tr><tr><td>0x4</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>0</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td></tr><tr><td>0x5</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-3.907</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-0.099</td></tr><tr><td>0x6</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-6.229</td><td>-4.229</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-4.229</td><td>-0.184</td></tr><tr><td>0x7</td><td>-</td><td>-</td><td>-</td><td>-8.135</td><td>-</td><td>-</td><td>-8.135</td><td>-4.181</td><td>-7.814</td><td>-</td><td>-</td><td>-4.091</td><td>-</td><td>-4.096</td><td>-4.091</td><td>-0.408</td></tr><tr><td>0x8</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>0</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td></tr><tr><td>0x9</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-6.229</td><td>-</td><td>-4.229</td><td>-</td><td>-4.229</td><td>-</td><td>-0.184</td></tr><tr><td>0xa</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-3.907</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-0.099</td></tr><tr><td>0xb</td><td>-</td><td>-</td><td>-</td><td>-8.135</td><td>-7.814</td><td>-</td><td>-</td><td>-4.091</td><td>-</td><td>-8.135</td><td>-</td><td>-4.181</td><td>-</td><td>-4.091</td><td>-4.006</td><td>-0.408</td></tr><tr><td>0xc</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-6.229</td><td>-4.229</td><td>-4.229</td><td>-0.184</td></tr><tr><td>0xd</td><td>-</td><td>-</td><td>-7.814</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-4.006</td><td>-</td><td>-8.135</td><td>-</td><td>-4.091</td><td>-8.135</td><td>-4.181</td><td>-4.091</td><td>-0.408</td></tr><tr><td>0xe</td><td>-</td><td>-7.814</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-8.135</td><td>-4.091</td><td>-</td><td>-</td><td>-</td><td>-4.006</td><td>-8.135</td><td>-4.091</td><td>-4.181</td><td>-0.408</td></tr><tr><td>0xf</td><td>-</td><td>-</td><td>-7.998</td><td>-</td><td>-</td><td>-7.913</td><td>-7.998</td><td>-4.314</td><td>-</td><td>-</td><td>-7.998</td><td>-7.913</td><td>-4.314</td><td>-7.998</td><td>-4.314</td><td>-0.368</td></tr></tbody></table>
<table><caption>Table 3: BPT for QARMAv1-128 MixColumns Matrix $M_8$</caption><thead><tr><th>a / b</th><th>0x0</th><th>0x1</th><th>0x2</th><th>0x3</th><th>0x4</th><th>0x5</th><th>0x6</th><th>0x7</th><th>0x8</th><th>0x9</th><th>0xa</th><th>0xb</th><th>0xc</th><th>0xd</th><th>0xe</th><th>0xf</th></tr></thead><tbody><tr><td>0x0</td><td>0</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td></tr><tr><td>0x1</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>0</td><td>-</td></tr><tr><td>0x2</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>0</td><td>-</td></tr><tr><td>0x3</td><td>-</td><td>-</td><td>-</td><td>-14.404</td><td>-</td><td>-</td><td>-</td><td>-8.011</td><td>-</td><td>-</td><td>-</td><td>-8.011</td><td>-</td><td>-</td><td>-</td><td>-0.011</td></tr><tr><td>0x4</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>0</td><td>-</td><td>-</td><td>-</td><td>-</td></tr><tr><td>0x5</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-7.994</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-0.005</td></tr><tr><td>0x6</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-14.404</td><td>-8.011</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-8.011</td><td>-0.011</td></tr><tr><td>0x7</td><td>-</td><td>-</td><td>-</td><td>-16.007</td><td>-</td><td>-</td><td>-16.007</td><td>-8.011</td><td>-15.99</td><td>-</td><td>-</td><td>-8.06</td><td>-</td><td>-8</td><td>-8.006</td><td>-0.022</td></tr><tr><td>0x8</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>0</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td></tr><tr><td>0x9</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-14.404</td><td>-</td><td>-8.011</td><td>-</td><td>-8.011</td><td>-</td><td>-</td><td>-0.011</td></tr><tr><td>0xa</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-7.99</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-0.005</td></tr><tr><td>0xb</td><td>-</td><td>-</td><td>-</td><td>-16.007</td><td>-15.99</td><td>-</td><td>-</td><td>-8.006</td><td>-</td><td>-16.007</td><td>-</td><td>-8.011</td><td>-</td><td>-8.006</td><td>-8</td><td>-0.022</td></tr><tr><td>0xc</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-14.404</td><td>-8.011</td><td>-8.011</td><td>-0.011</td></tr><tr><td>0xd</td><td>-</td><td>-15.99</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-8</td><td>-</td><td>-16.007</td><td>-</td><td>-8.006</td><td>-16.007</td><td>-8.011</td><td>-8.006</td><td>-0.022</td></tr><tr><td>0xe</td><td>-15.99</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-16.007</td><td>-8.006</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-8</td><td>-16.007</td><td>-8.006</td><td>-8.011</td><td>-0.022</td></tr><tr><td>0xf</td><td>-</td><td>-</td><td>-16</td><td>-</td><td>-15.995</td><td>-16</td><td>-8.017</td><td>-</td><td>-16</td><td>-15.995</td><td>-8.017</td><td>-</td><td>-16</td><td>-8.017</td><td>-8.017</td><td>-0.022</td></tr></tbody></table>
<table><caption>Table 4: BPT for QARMAv2-64 MixColumns Matrix $M_4$</caption><thead><tr><th>a / b</th><th>0x0</th><th>0x1</th><th>0x2</th><th>0x3</th><th>0x4</th><th>0x5</th><th>0x6</th><th>0x7</th><th>0x8</th><th>0x9</th><th>0xa</th><th>0xb</th><th>0xc</th><th>0xd</th><th>0xe</th><th>0xf</th></tr></thead><tbody><tr><td>0x0</td><td>0</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td></tr><tr><td>0x1</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>0</td><td>-</td></tr><tr><td>0x2</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>0</td><td>-</td><td>-</td></tr><tr><td>0x3</td><td>-</td><td>-</td><td>-</td><td>-3.906</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-0.099</td></tr><tr><td>0x4</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>0</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td></tr><tr><td>0x5</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-3.906</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-0.099</td></tr><tr><td>0x6</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-3.906</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-0.099</td></tr><tr><td>0x7</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-4.006</td><td>-7.813</td><td>-</td><td>-</td><td>-4.006</td><td>-</td><td>-4.006</td><td>-4.006</td><td>-0.421</td></tr><tr><td>0x8</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>0</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td></tr><tr><td>0x9</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-3.906</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-0.099</td></tr><tr><td>0xa</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-3.906</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-0.099</td></tr><tr><td>0xb</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-7.813</td><td>-</td><td>-</td><td>-4.006</td><td>-</td><td>-</td><td>-</td><td>-4.006</td><td>-</td><td>-4.006</td><td>-4.006</td><td>-0.421</td></tr><tr><td>0xc</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-3.906</td><td>-</td><td>-</td><td>-0.099</td></tr><tr><td>0xd</td><td>-</td><td>-</td><td>-7.813</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-4.006</td><td>-</td><td>-</td><td>-</td><td>-4.006</td><td>-</td><td>-4.006</td><td>-4.006</td><td>-0.421</td></tr><tr><td>0xe</td><td>-</td><td>-7.813</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-4.006</td><td>-</td><td>-</td><td>-</td><td>-4.006</td><td>-</td><td>-4.006</td><td>-4.006</td><td>-0.421</td></tr><tr><td>0xf</td><td>-</td><td>-</td><td>-</td><td>-7.913</td><td>-</td><td>-7.913</td><td>-7.913</td><td>-4.328</td><td>-</td><td>-7.913</td><td>-7.913</td><td>-4.328</td><td>-7.913</td><td>-4.328</td><td>-4.328</td><td>-0.365</td></tr></tbody></table>

<table><caption>Table 5: Accurate (left) and approximated (right) BPTs for all the 4 × 4 MDS Matrix for $m = 4$ and $m = 8$, $i = \text{Hw}(a)$ and $j = \text{Hw}(b)$.</caption><thead><tr><th colspan="5">m = 4, accurate</th><th colspan="5">m = 4, approximated</th></tr><tr><th>i/j</th><th>0</th><th>1</th><th>2</th><th>3</th><th>4</th><th>i/j</th><th>0</th><th>1</th><th>2</th><th>3</th><th>4</th></tr></thead><tbody><tr><td>0</td><td>0</td><td>-</td><td>-</td><td>-</td><td>-</td><td>0</td><td>0</td><td>-</td><td>-</td><td>-</td><td>-</td></tr><tr><td>1</td><td>-</td><td>-</td><td>-</td><td>-</td><td>0</td><td>1</td><td>-</td><td>-</td><td>-</td><td>-</td><td>0</td></tr><tr><td>2</td><td>-</td><td>-</td><td>-</td><td>-3.907</td><td>-0.447</td><td>2</td><td>-</td><td>-</td><td>-</td><td>-4</td><td>0</td></tr><tr><td>3</td><td>-</td><td>-</td><td>-7.814</td><td>-4.354</td><td>-0.363</td><td>3</td><td>-</td><td>-</td><td>-8</td><td>-4</td><td>0</td></tr><tr><td>4</td><td>-11.721</td><td>-8.261</td><td>-4.269</td><td>-0.374</td><td>-</td><td>4</td><td>-</td><td>-12</td><td>-8</td><td>-4</td><td>0</td></tr></tbody></table>
<table><thead><tr><th colspan="5">m = 8, accurate</th><th colspan="5">m = 8, approximated</th></tr><tr><th>i/j</th><th>0</th><th>1</th><th>2</th><th>3</th><th>4</th><th>i/j</th><th>0</th><th>1</th><th>2</th><th>3</th><th>4</th></tr></thead><tbody><tr><td>0</td><td>0</td><td>-</td><td>-</td><td>-</td><td>-</td><td>0</td><td>0</td><td>-</td><td>-</td><td>-</td><td>-</td></tr><tr><td>1</td><td>-</td><td>-</td><td>-</td><td>-</td><td>0</td><td>1</td><td>-</td><td>-</td><td>-</td><td>-</td><td>0</td></tr><tr><td>2</td><td>-</td><td>-</td><td>-</td><td>-7.994</td><td>-0.023</td><td>2</td><td>-</td><td>-</td><td>-</td><td>-8</td><td>0</td></tr><tr><td>3</td><td>-</td><td>-</td><td>-15.989</td><td>-8.017</td><td>-0.023</td><td>3</td><td>-</td><td>-</td><td>-16</td><td>-8</td><td>0</td></tr><tr><td>4</td><td>-23.98</td><td>-16.01</td><td>-8.017</td><td>-0.023</td><td>-</td><td>4</td><td>-</td><td>-24</td><td>-16</td><td>-8</td><td>0</td></tr></tbody></table>
## D Profile of Number of Concrete Paths in Terms of Probability

<table><caption>Table 6: Number of concrete differential paths $N(\tilde{p})$ of probability $\tilde{p}$ consistent with the 6-round truncated path given in (18), for QARMAv1-64 (left), QARMAv1-128 (right), and QARMAv2-64 (bottom).</caption><thead><tr><th>p̃</th><th>N(p̃)</th><th>1/|Δ<sub>in</sub>| log<sub>2</sub>(∑<sub>i≤p̃</sub> 2<sup>-i</sup>N(i))</th><th>p̃</th><th>N(p̃)</th><th>1/|Δ<sub>in</sub>| log<sub>2</sub>(∑<sub>i≤p̃</sub> 2<sup>-i</sup>N(i))</th></tr></thead><tbody><tr><td>55</td><td>2</td><td>-57.9068</td><td>109</td><td>2</td><td>-115.9943</td></tr><tr><td>56</td><td>20</td><td>-55.3218</td><td>110</td><td>5</td><td>-114.8243</td></tr><tr><td>57</td><td>44</td><td>-54.3832</td><td>111</td><td>9</td><td>-114.2394</td></tr><tr><td>58</td><td>189</td><td>-53.3637</td><td>112</td><td>38</td><td>-113.4707</td></tr><tr><td>59</td><td>512</td><td>-52.6098</td><td>113</td><td>155</td><td>-112.5891</td></tr><tr><td>60</td><td>1624</td><td>-51.8913</td><td>114</td><td>688</td><td>-11.5785</td></tr><tr><td>61</td><td>3784</td><td>-51.3483</td><td>115</td><td>2479</td><td>-110.5740</td></tr><tr><td>62</td><td>9943</td><td>-50.8505</td><td>116</td><td>10174</td><td>-109.6268</td></tr><tr><td>63</td><td>21134</td><td>-50.4608</td><td>117</td><td>38190</td><td>-108.6982</td></tr><tr><td>64</td><td>40528</td><td>-50.1657</td><td>118</td><td>133167</td><td>-108.0414</td></tr><tr><td>65</td><td>66060</td><td>-49.9631</td><td>119</td><td>75479</td><td>-107.8413</td></tr><tr><td>66</td><td>96836</td><td>-49.8308</td><td>120</td><td>91853</td><td>-107.7319</td></tr><tr><td>67</td><td>119046</td><td>-49.7551</td><td>121</td><td>123217</td><td>-107.6629</td></tr><tr><td>68</td><td>123644</td><td>-49.7173</td><td>122</td><td>122651</td><td>-107.6298</td></tr><tr><td>69</td><td>99734</td><td>-49.7063</td><td>123</td><td>120829</td><td>-107.6137</td></tr><tr><td>70</td><td>64261</td><td>-49.6967</td><td>124</td><td>118665</td><td>-107.6103</td></tr><tr><td>71</td><td>29406</td><td>-49.6965</td><td>125</td><td>112937</td><td>-107.6022</td></tr><tr><td>72</td><td>10514</td><td>-49.6963</td><td>126</td><td>114523</td><td>-107.6003</td></tr><tr><td></td><td></td><td></td><td>127, ..., 144</td><td>2268082</td><td>-107.5984</td></tr></tbody></table><table><thead><tr><th>p̃</th><th>N(p̃)</th><th>1/|Δ<sub>in</sub>| log<sub>2</sub>(∑<sub>i≤p̃</sub> 2<sup>-i</sup>N(i))</th></tr></thead><tbody><tr><td>57</td><td>1</td><td>-60.9070</td></tr><tr><td>58</td><td>11</td><td>-58.2065</td></tr><tr><td>59</td><td>82</td><td>-56.1521</td></tr><tr><td>60</td><td>546</td><td>-54.3333</td></tr><tr><td>61</td><td>3606</td><td>-52.5822</td></tr><tr><td>62</td><td>18630</td><td>-51.0887</td></tr><tr><td>63</td><td>77596</td><td>-49.8603</td></tr><tr><td>64</td><td>267390</td><td>-48.8693</td></tr><tr><td>65</td><td>272415</td><td>-48.5438</td></tr><tr><td>66</td><td>286225</td><td>-48.3983</td></tr><tr><td>67</td><td>295291</td><td>-48.3286</td></tr><tr><td>68</td><td>299727</td><td>-48.2945</td></tr><tr><td>69</td><td>307232</td><td>-48.2773</td></tr><tr><td>70</td><td>316206</td><td>-48.2686</td></tr><tr><td>71</td><td>325986</td><td>-48.2641</td></tr><tr><td>72</td><td>395470</td><td>-48.2614</td></tr></tbody></table>

## E Linear description of Subkey bits

The information bits guessed/implied during the attack have linear representations in key bits $w$ and $k$ which are shown in Tab. 7 and Tab. 8. In this paper the bit indices are arranged according to the following patterns. For QARMA-64

$$ \begin{pmatrix} x_0 \dots x_3 & x_4 \dots x_7 & x_8 \dots x_{11} & x_{12} \dots x_{15} \\ x_{16} \dots x_{19} & x_{20} \dots x_{23} & x_{24} \dots x_{27} & x_{28} \dots x_{31} \\ x_{32} \dots x_{35} & x_{36} \dots x_{39} & x_{40} \dots x_{43} & x_{44} \dots x_{47} \\ x_{48} \dots x_{51} & x_{52} \dots x_{55} & x_{56} \dots x_{59} & x_{60} \dots x_{63} \end{pmatrix}, \quad (46) $$
and for QARMA-128

$$ \begin{pmatrix} x_0 \dots x_7 & x_8 \dots x_{15} & x_{16} \dots x_{23} & x_{24} \dots x_{31} \\ x_{32} \dots x_{39} & x_{40} \dots x_{47} & x_{48} \dots x_{55} & x_{56} \dots x_{63} \\ x_{64} \dots x_{71} & x_{72} \dots x_{79} & x_{80} \dots x_{87} & x_{88} \dots x_{95} \\ x_{96} \dots x_{103} & x_{104} \dots x_{11} & x_{112} \dots x_{119} & x_{120} \dots x_{127} \end{pmatrix}. \quad (47) $$
<table><caption>Table 7: QARMA-64 subkey linear description in *w* and *k*</caption><thead><tr><th>guessed/ computed subkeys</th><th>w</th><th>k</th><th>linear description</th><th>guessed/ computed subkeys</th><th>w</th><th>k</th><th>linear description</th><th>guessed/ computed subkeys</th><th>w</th><th>k</th></tr><tr><th>subkey</th><th>bit</th><th></th><th></th><th>subkey</th><th>bit</th><th></th><th></th><th>subkey</th><th>bit</th><th></th></tr></thead><tbody><tr><td></td><td>16</td><td>16</td><td></td><td>16</td><td>15</td><td>16</td><td></td><td>0</td><td>-</td><td>22,41,61</td></tr><tr><td></td><td>17</td><td>17</td><td></td><td>17</td><td>16</td><td>17</td><td></td><td></td><td></td><td></td></tr><tr><td></td><td>18</td><td>18</td><td></td><td>18</td><td>17</td><td>18</td><td></td><td></td><td></td><td></td></tr><tr><td></td><td>19</td><td>19</td><td></td><td>19</td><td>18</td><td>19</td><td></td><td>1</td><td>-</td><td>23,42,62</td></tr><tr><td></td><td>20</td><td>20</td><td></td><td>20</td><td>19</td><td>20</td><td></td><td></td><td></td><td></td></tr><tr><td></td><td>21</td><td>21</td><td></td><td>21</td><td>20</td><td>21</td><td></td><td></td><td></td><td></td></tr><tr><td></td><td>22</td><td>22</td><td></td><td>22</td><td>21</td><td>22</td><td></td><td></td><td></td><td></td></tr><tr><td></td><td>23</td><td>23</td><td></td><td>23</td><td>22</td><td>23</td><td></td><td>2</td><td>-</td><td>20,43,63</td></tr><tr><td></td><td>28</td><td>28</td><td></td><td>28</td><td>27</td><td>28</td><td></td><td></td><td></td><td></td></tr><tr><td></td><td>29</td><td>29</td><td></td><td>29</td><td>28</td><td>29</td><td></td><td>3</td><td>-</td><td>21,40,60</td></tr><tr><td></td><td>30</td><td>30</td><td></td><td>30</td><td>29</td><td>30</td><td></td><td></td><td></td><td></td></tr><tr><td></td><td>31</td><td>31</td><td></td><td>31</td><td>30</td><td>31</td><td></td><td></td><td></td><td></td></tr><tr><td></td><td>32</td><td>32</td><td></td><td>32</td><td>31</td><td>32</td><td></td><td>20</td><td>-</td><td>18,45,57</td></tr><tr><td></td><td>33</td><td>33</td><td></td><td>33</td><td>32</td><td>33</td><td></td><td></td><td></td><td></td></tr><tr><td></td><td>34</td><td>34</td><td></td><td>34</td><td>33</td><td>34</td><td></td><td></td><td></td><td></td></tr><tr><td></td><td>35</td><td>35</td><td></td><td>35</td><td>34</td><td>35</td><td></td><td></td><td></td><td></td></tr><tr><td></td><td>40</td><td>40</td><td></td><td>40</td><td>39</td><td>40</td><td></td><td>21</td><td>-</td><td>19,46,58</td></tr><tr><td>(w + k)</td><td>41</td><td>41</td><td></td><td>(w' + k)</td><td>41</td><td>41</td><td></td><td></td><td></td><td></td></tr><tr><td></td><td>42</td><td>42</td><td></td><td></td><td>42</td><td>41</td><td></td><td></td><td></td><td></td></tr><tr><td></td><td>43</td><td>43</td><td></td><td></td><td>43</td><td>42</td><td></td><td></td><td></td><td></td></tr><tr><td></td><td>44</td><td>44</td><td></td><td></td><td>44</td><td>43</td><td></td><td></td><td></td><td></td></tr><tr><td></td><td>45</td><td>45</td><td></td><td></td><td>45</td><td>44</td><td></td><td></td><td></td><td></td></tr><tr><td></td><td>46</td><td>46</td><td></td><td></td><td>46</td><td>45</td><td></td><td></td><td></td><td></td></tr><tr><td></td><td>47</td><td>47</td><td></td><td></td><td>47</td><td>46</td><td></td><td></td><td></td><td></td></tr><tr><td></td><td>52</td><td>52</td><td></td><td></td><td>52</td><td>51</td><td></td><td></td><td></td><td></td></tr><tr><td></td><td>53</td><td>53</td><td></td><td></td><td>53</td><td>52</td><td></td><td></td><td></td><td></td></tr><tr><td></td><td>54</td><td>54</td><td></td><td></td><td>54</td><td>53</td><td></td><td></td><td></td><td></td></tr><tr><td></td><td>55</td><td>55</td><td></td><td></td><td>55</td><td>54</td><td></td><td></td><td></td><td></td></tr><tr><td></td><td>56</td><td>56</td><td></td><td></td><td>56</td><td>55</td><td></td><td></td><td></td><td></td></tr><tr><td></td><td>57</td><td>57</td><td></td><td></td><td>57</td><td>56</td><td></td><td></td><td></td><td></td></tr><tr><td></td><td>58</td><td>58</td><td></td><td></td><td>58</td><td>57</td><td></td><td></td><td></td><td></td></tr><tr><td></td><td>59</td><td>59</td><td></td><td></td><td>59</td><td>58</td><td></td><td></td><td></td><td></td></tr><tr><td></td><td>60</td><td>60</td><td></td><td></td><td>60</td><td>59</td><td></td><td></td><td></td><td></td></tr><tr><td></td><td>61</td><td>61</td><td></td><td></td><td>61</td><td>60</td><td></td><td></td><td></td><td></td></tr><tr><td></td><td>62</td><td>62</td><td></td><td></td><td>62</td><td>61</td><td></td><td></td><td></td><td></td></tr><tr><td></td><td>63</td><td>63</td><td></td><td></td><td>63</td><td>62</td><td></td><td></td><td></td><td></td></tr></tbody></table>
<table><caption>Table 8: QARMA-128 subkey linear description in *w* and *k*</caption><thead><tr><th rowspan="2">guessed/ computed subkeys</th><th rowspan="2">bit</th><th colspan="2">linear description</th><th colspan="2">guessed/ computed subkeys</th><th colspan="2">linear description</th><th colspan="2">guessed/ computed subkeys</th><th colspan="2">linear description</th><th colspan="2">guessed/ computed subkeys</th><th colspan="2">linear description</th></tr><tr><th>w</th><th>k</th><th>w</th><th>k</th><th>w</th><th>k</th><th>w</th><th>k</th><th>w</th><th>k</th><th>w</th><th>k</th><th>w</th><th>k</th></tr></thead><tbody><tr><td rowspan="19">(w + k)</td><td>32</td><td>32</td><td>32</td><td>84</td><td>84</td><td>32</td><td>31</td><td>84</td><td>83</td><td>84</td><td>0</td><td>44,81,125</td><td>0</td><td>44,81,125</td></tr><tr><td>33</td><td>33</td><td>33</td><td>85</td><td>85</td><td>33</td><td>32</td><td>85</td><td>84</td><td>85</td><td>1</td><td>45,82,126</td><td>1</td><td>45,82,126</td></tr><tr><td>34</td><td>34</td><td>34</td><td>86</td><td>86</td><td>34</td><td>33</td><td>86</td><td>85</td><td>86</td><td>2</td><td>46,83,127</td><td>2</td><td>46,83,127</td></tr><tr><td>35</td><td>35</td><td>35</td><td>87</td><td>87</td><td>35</td><td>34</td><td>87</td><td>86</td><td>87</td><td>3</td><td>47,84,120</td><td>3</td><td>47,84,120</td></tr><tr><td>36</td><td>36</td><td>36</td><td>88</td><td>88</td><td>36</td><td>35</td><td>88</td><td>87</td><td>88</td><td>4</td><td>40,85,121</td><td>4</td><td>40,85,121</td></tr><tr><td>37</td><td>37</td><td>37</td><td>89</td><td>89</td><td>37</td><td>36</td><td>89</td><td>88</td><td>89</td><td>5</td><td>41,86,122</td><td>5</td><td>41,86,122</td></tr><tr><td>38</td><td>38</td><td>38</td><td>90</td><td>90</td><td>38</td><td>37</td><td>90</td><td>89</td><td>90</td><td>6</td><td>42,87,123</td><td>6</td><td>42,87,123</td></tr><tr><td>39</td><td>39</td><td>39</td><td>91</td><td>91</td><td>39</td><td>38</td><td>91</td><td>90</td><td>91</td><td>7</td><td>43,80,124</td><td>7</td><td>43,80,124</td></tr><tr><td>40</td><td>40</td><td>40</td><td>92</td><td>92</td><td>40</td><td>39</td><td>92</td><td>91</td><td>92</td><td>40</td><td>36,93,113</td><td>40</td><td>36,93,113</td></tr><tr><td>41</td><td>41</td><td>41</td><td>93</td><td>93</td><td>41</td><td>40</td><td>93</td><td>92</td><td>93</td><td>41</td><td>37,94,114</td><td>41</td><td>37,94,114</td></tr><tr><td>42</td><td>42</td><td>42</td><td>94</td><td>94</td><td>42</td><td>41</td><td>94</td><td>93</td><td>94</td><td>42</td><td>38,95,115</td><td>42</td><td>38,95,115</td></tr><tr><td>43</td><td>43</td><td>43</td><td>95</td><td>95</td><td>43</td><td>42</td><td>95</td><td>94</td><td>95</td><td>43</td><td>39,88,116</td><td>43</td><td>39,88,116</td></tr><tr><td>44</td><td>44</td><td>44</td><td>104</td><td>104</td><td>44</td><td>43</td><td>104</td><td>103</td><td>104</td><td>44</td><td>32,89,117</td><td>44</td><td>32,89,117</td></tr><tr><td>45</td><td>45</td><td>45</td><td>105</td><td>105</td><td>45</td><td>44</td><td>105</td><td>104</td><td>105</td><td>45</td><td>37,90,118</td><td>45</td><td>37,90,118</td></tr><tr><td>46</td><td>46</td><td>46</td><td>106</td><td>106</td><td>46</td><td>45</td><td>106</td><td>105</td><td>106</td><td>46</td><td>34,91,119</td><td>46</td><td>34,91,119</td></tr><tr><td>47</td><td>47</td><td>47</td><td>107</td><td>107</td><td>47</td><td>46</td><td>107</td><td>106</td><td>107</td><td>47</td><td>35,92,112</td><td>47</td><td>35,92,112</td></tr><tr><td>56</td><td>56</td><td>56</td><td>108</td><td>108</td><td>56</td><td>47</td><td>108</td><td>107</td><td>108</td><td>47</td><td>36,92,113</td><td>47</td><td>36,92,113</td></tr><tr><td>57</td><td>57</td><td>57</td><td>109</td><td>109</td><td>57</td><td>56</td><td>109</td><td>108</td><td>109</td><td>47</td><td>36,94,114</td><td>47</td><td>36,94,114</td></tr><tr><td>58</td><td>58</td><td>58</td><td>110</td><td>110</td><td>58</td><td>57</td><td>110</td><td>109</td><td>110</td><td>47</td><td>36,96,115</td><td>47</td><td>36,96,115</td></tr><tr><td>59</td><td>59</td><td>59</td><td>111</td><td>111</td><td>59</td><td>58</td><td>111</td><td>110</td><td>111</td><td>47</td><td>37,96,116</td><td>47</td><td>37,96,116</td></tr><tr><td>60</td><td>60</td><td>60</td><td>112</td><td>112</td><td>60</td><td>59</td><td>112</td><td>111</td><td>112</td><td>47</td><td>38,96,117</td><td>47</td><td>38,96,117</td></tr><tr><td>61</td><td>61</td><td>61</td><td>113</td><td>113</td><td>61</td><td>60</td><td>113</td><td>112</td><td>113</td><td>47</td><td>39,96,118</td><td>47</td><td>39,96,118</td></tr><tr><td>62</td><td>62</td><td>62</td><td>114</td><td>114</td><td>62</td><td>61</td><td>114</td><td>113</td><td>114</td><td>47</td><td>39,96,119</td><td>47</td><td>39,96,119</td></tr><tr><td>63</td><td>63</td><td>63</td><td>115</td><td>115</td><td>63</td><td>62</td><td>115</td><td>114</td><td>115</td><td>47</td><td>39,96,120</td><td>47</td><td>39,96,120</td></tr><tr><td>64</td><td>64</td><td>64</td><td>116</td><td>116</td><td>64</td><td>63</td><td>116</td><td>115</td><td>116</td><td>47</td><td>39,96,121</td><td>47</td><td>39,96,121</td></tr><tr><td>65</td><td>65</td><td>65</td><td>117</td><td>117</td><td>65</td><td>64</td><td>117</td><td>116</td><td>117</td><td>47</td><td>39,96,122</td><td>47</td><td>39,96,122</td></tr><tr><td>66</td><td>66</td><td>66</td><td>118</td><td>118</td><td>66</td><td>65</td><td>118</td><td>117</td><td>118</td><td>47</td><td>39,96,123</td><td>47</td><td>39,96,123</td></tr><tr><td>67</td><td>67</td><td>67</td><td>119</td><td>119</td><td>67</td><td>66</td><td>119</td><td>118</td><td>119</td><td>47</td><td>39,96,124</td><td>47</td><td>39,96,124</td></tr><tr><td>68</td><td>68</td><td>68</td><td>120</td><td>120</td><td>68</td><td>67</td><td>120</td><td>119</td><td>120</td><td>47</td><td>39,96,125</td><td>47</td><td>39,96,125</td></tr><tr><td>69</td><td>69</td><td>69</td><td>121</td><td>121</td><td>69</td><td>68</td><td>121</td><td>120</td><td>121</td><td>47</td><td>39,96,126</td><td>47</td><td>39,96,126</td></tr><tr><td>70</td><td>70</td><td>70</td><td>122</td><td>122</td><td>70</td><td>69</td><td>122</td><td>121</td><td>122</td><td>47</td><td>39,96,127</td><td>47</td><td>39,96,127</td></tr><tr><td>71</td><td>71</td><td>71</td><td>123</td><td>123</td><td>71</td><td>70</td><td>123</td><td>122</td><td>123</td><td>47</td><td>39,96,128</td><td>47</td><td>39,96,128</td></tr><tr><td>80</td><td>80</td><td>80</td><td>124</td><td>124</td><td>80</td><td>71</td><td>124</td><td>123</td><td>124</td><td>47</td><td>39,96,129</td><td>47</td><td>39,96,129</td></tr><tr><td>81</td><td>81</td><td>81</td><td>125</td><td>125</td><td>81</td><td>80</td><td>125</td><td>124</td><td>125</td><td>47</td><td>39,96,130</td><td>47</td><td>39,96,130</td></tr><tr><td>82</td><td>82</td><td>82</td><td>126</td><td>126</td><td>82</td><td>81</td><td>126</td><td>125</td><td>126</td><td>47</td><td>39,96,131</td><td>47</td><td>39,96,131</td></tr><tr><td>83</td><td>83</td><td>83</td><td>127</td><td>127</td><td>83</td><td>82</td><td>127</td><td>126</td><td>127</td><td>47</td><td>39,96,132</td><td>47</td><td>39,96,132</td></tr></tbody></table>