# Differential Cryptanalysis of the Reduced Pointer Authentication Code Function Used in Arm's FEAT_PACQARMA3 Feature

Roberto Avanzi, Orr Dunkelman, Shibam Ghosh

► To cite this version:

Roberto Avanzi, Orr Dunkelman, Shibam Ghosh. Differential Cryptanalysis of the Reduced Pointer Authentication Code Function Used in Arm's FEAT_PACQARMA3 Feature. IACR Transactions on Symmetric Cryptology, 2025, 2025 (1), pp.380-419. 10.46586/tosc.v2025.i1.380-419. hal-05519460

HAL Id: hal-05519460

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

Submitted on 19 Feb 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
# Differential Cryptanalysis of the Reduced Pointer Authentication Code Function Used in Arm's FEAT_PACQARMA3 Feature

Roberto Avanzi<fnref n="1" />, Orr Dunkelman<fnref n="2" />,<fnref n="3" /> and Shibam Ghosh<fnref n="2" />,<fnref n="4" />

**Abstract.** The *Pointer Authentication Code* (PAC) feature in the Arm architecture is used to enforce the *Code Flow Integrity* (CFI) of running programs. It does so by generating a short MAC — called the PAC — of the return address and some additional context information upon function entry, and checking it upon exit. An attacker that wants to overwrite the stack with manipulated addresses now faces an additional hurdle, as they now have to guess, forge, or reuse PAC values. PAC is deployed on billions of devices as a first line of defense to harden system software and complex programs against software exploitation.

The original version of the feature uses a 12-round version the **QARMA-64** block cipher.
The output is then truncated to between 3 and 32 bits, in order to be inserted into
unused bits of 64-bit pointers. A later revision of the specification allows the use of
an 8-round version of **QARMA-64**. This reduction may introduce vulnerabilities such
as high-probability distinguishers, potentially enabling key recovery attacks. The
present paper explores this avenue.

A cryptanalysis of the PAC computation function entails restricting the inputs to valid virtual addresses, meaning that certain most significant bits are fixed to zero, and considering only the truncated output. Within these constraints, we present practical attacks on various PAC configurations. These attacks, while not presenting immediate threat to the PAC mechanism, show that some versions of the feature do miss the security targets made for the original function. This offers new insights into the practical security of constructing MAC from truncated block ciphers, expanding on the mostly theoretical understanding of creating PRFs from truncated PRPs.

We note that the results do not affect the security of QARMA-64 when used with the
recommended number of rounds for general purpose applications.

**Keywords:** Tweakable Block Ciphers · Lightweight Cryptography · Pseudo-Random Functions · Pseudo-Random Permutations

# 1 Introduction

The 2016 Additions to the Arm V8 architecture [Arm16] introduced the *Pointer Authentication Code* PAC feature [QPS17] to counter various exploits, including *Return-Oriented Programming* (ROP) [RBSS12].

<footnote n="1">¹ Caesarea Rothschild Institute, University of Haifa, Haifa, Israel
roberto.avanzi@gmail.com</footnote>

<footnote n="2">² Computer Science Department, University of Haifa, Haifa, Israel
orrd@cs.haifa.ac.il</footnote>

<footnote n="3">³ Faculty of Electrical Engineering and Computer Science, TU Berlin, Berlin, Germany</footnote>

<footnote n="4">⁴ Inria, Paris, France
shibam.ghosh@inria.fr</footnote>
<figure><img src="image_2.png" /><figcaption>Figure 1: PAC field in an ARM64 pointer.</figcaption></figure>

ROP involves smashing the stack with addresses of gadgets, i.e., function epilogues in the target software, together with some information that these gadgets may consume. The gadgets are typically taken from a common library like libc [Des97]. Each return instruction directly transfers control to the next gadget, thus creating a chain of gadgets, which is a form of threaded code [Bel73]. Since most non-trivial software contains a Turing-complete set of gadgets [Sha07], complex programs can be executed. Tools exist to assist the implementation of an arbitrary program as a gadget chain, such as Q [SAB11], ropc [pak13], PSHAPE [FBP$^{+16}$], and ROPER [FZHJ17, Fra18].

PAC provides instructions to insert and verify short tags in reserved bits of pointers, as shown in Figure 1. On A-profile CPUs, the size of the PAC field ranges from 3 to 31 bits, depending on factors such as Virtual Address (VA) space size and the use of some of the reserved bits for other uses. On M-profile CPUs, a 32-bit PAC is stored separately.

These cryptographically computed tags depend on a secret key and a public value representing the pointer's context. While primarily used for enforcing CFI by protecting function return address, the PAC can also protect v-tables, procedure linkage tables, Objective-C method caches, computed gotos, and other pointers [App24]. This feature is invoked continuously on billions of deployed devices to provide a first line of defense to system software and to complex programs such as browsers. Therefore, its computation must be very fast to avoid slowing down program execution. For this purpose, a new block cipher called QARMA [Ava17] was designed, suggesting that the goal was to have a critical path not exceeding 100 GE, i.e., four to five execution pipeline stages.<fnref n="1" />

The tag is computed by discarding some output bits of a lightweight Tweakable Block Cipher (TBC) [LRW02]. A TBC is a block cipher that takes an additional public input called the tweak, which is used together with the key to select the permutation computed by the cipher. For a fixed tweak, a TBC acts as a permutation, while for a fixed plaintext, the tweak-to-ciphertext mapping aims to be a Pseudo-Random Function (PRF). When at least half the output bits are discarded, the result is indistinguishable from a PRF [GG15, GGM18, GG21]. This can be seen as an instance of the Chop-MD construction [CDMP05, Sec. 3.4]. For PAC, the pointer is the plaintext input and the context is the tweak. It remains an open question to determine the conditions under which such a construction yields a PRF over the combined plaintext-tweak space.

In this paper, we refer to the process of discarding fixed output bits as “chopping” and the resulting value as “chopped” instead of “truncating” and “truncated,” in order to avoid confusion with truncation as understood in differential cryptanalysis. Additionally, we use the verb “to clamp” to describe the action of forcing certain input bits to zero.

Several lightweight cryptographic primitives already existed when the PAC feature was developed, including CLEFIA [SSA$^{+07}$], KATAN [CDK09], KLEIN [GNL11], LED [GPPR11], PRESENT [BKL$^{+07}$], PRINCE [BCG$^{+12}$], SIMON and SPECK [BSS$^{+13}$], and MIDORI [BBI$^{+15}$], to name just a few. Some of these, suitably round-reduced, do have a critical path of around 100 GE. However, none of these ciphers is tweakable, and if generic methods to construct TBCs from ordinary block ciphers [Rog04, LST12, ST13] are applied to them, the resulting latency would at least double. A different approach, the TWEAKEY framework [JNP14],

<footnote n="1">¹ With typical pipeline stage delays of 6-8 FO4 inverters plus 2-3 FO4 for latching [HBK$^{+02}$], and NAND to FO4 delay ratios at least 1.5 and rarely significantly exceeding 2.0 [GVG$^{+17}$, PP20], critical path usually ranges from 14 to 25 GE.</footnote>
<figure><img src="image_3.png" /><figcaption>Figure 2: High-level structure of MANTIS, QARMA, and QARMAv2.</figcaption></figure>

takes an existing design, mixes values derived from the tweak in each round, and suitably increases the number of the latter. The TBCs Deoxys-BC, Joltik-BC, and Kiasu-BC are examples of this design, but their latencies are still unsatisfactory, in particular because of the use of MDS diffusion matrices. Some lightweight hash functions existing at the time, such as SIPHASH [AB12], could not be used because they rely on modular additions with long critical paths. These considerations justified the design of a new primitive.

The first lightweight primitive meeting the latency requirement was MANTIS [BJK<sup>16</sup>, Section 6]. QARMA followed shortly after, improving upon MANTIS by addressing weaknesses like “copy-and-paste” characteristics due to a suboptimal diffusion layer, and a partitioning of the state into four independent 32-bit paths through the three central rounds [DEKM16].<sup>2</sup> Both ciphers, along with QARMA’s successor QARMAv2 [ABD<sup>23</sup>], adopt an approach similar to the TWEAKEY framework. They are reflection ciphers, i.e., of the form $E = F^{-1} \circ G \circ F$ where F is an encryption function, and a G is called a reflector. Even in the cases where G is an involution, E itself is not self-inverting due to key schedule changes between forward and backward operations. As shown in Figure 2, these ciphers share a common structure. The external rounds of F and $F^{-1}$ — called half rounds due to their simplified S-Box only structure — are separated out for clarity.

With PAC enabled, gadgets used in ROP attacks can verify tags but cannot generate them, unless they are entire procedures. An adversary must therefore either: (a) guess tags through trial and error; (b) reuse existing tagged pointers; (c) use code that generates valid tags (a “signing gadget”); or (d) forge tags through cryptanalysis.

Let us have a look at these four attack strategies. Option (a) is unfeasible once the gadget chains, or the tags themselves, are sufficiently long. Sometimes, short or single gadget ROP chain exploits are possible, and if the tag space is sufficiently small, the tags can be brute-forced by spawned processes. Therefore, there should be tests at compile time, or on the compiled binaries, to prevent such short chains. Tagged pointer reuse and the possibilities of signing gadgets are accepted risks [QPS17]. In this paper we are concerned with the fourth and last of the attack strategies listed above: cryptanalysis.

The original PAC architecture uses the 12-round QARMA<sub>5</sub>-64, that achieves 100 GE (as per [Ava17]) and provided generous security margins. This version of the feature is known as FEAT_PACQARMA5 in the Arm ARM (Architecture Reference Manual) for both A-profile [Arm24] and M-profile [Arm23]. However, in small cores with short pipelines, the required four to five execute pipelines stages can create pipeline bubbles and reduce performance. For this reason, a version of the feature called FEAT_PACQARMA3 was introduced, based on the eight-round QARMA<sub>3</sub>-64, with a shorter critical path of 66 GE. This can be computed in three stages, improving performance and power efficiency.

Such a heavily round-reduced version of the cipher may allow high probability distinguishers and thus expose the feature to practical cryptanalysis. Since memory read gadgets are relatively common in software environments, even in the form of complete procedures, we can assume that an adversary can read many signed pointers and mount Known Plaintext Attacks (KPAs) (strictly speaking, Known Plaintext-and-Tweak Attacks).

Furthermore, *Just-in-time* (JIT) environments, such as JavaScript engines, allow

<footnote n="2"><sup>2</sup> A 128-bit version for memory encryption is also defined, but it is out of scope for this paper.</footnote>
attackers to generate chosen signed pointers. The latter can be collected for later reuse or
for the purpose of mounting *Chosen Plaintext Attacks* (CPAs).

## 1.1 Security Claims, Security Model, and Goals

The security claims for MANTIS₅-64 and QARMA₅-64 are that the ciphers should offer "security against practical attacks [...] in the sense [...] that no related-tweak attack should be applicable with less than 2³⁰ chosen or 2⁴⁰ known text pairs." It is debatable whether the PAC function based on QARMA₃-64 should be subjected to these criteria, but, since Arm uses it for the A-profile as an alternative to QARMA₅-64, we believe that holding to the same security claim is justified.

We assume that the attacker has access to a “signing” oracle $\mathcal{E}$ that uses an unknown key $K$ for chosen inputs, such as a JIT environment combined with a memory read gadget.

Out goal is to minimize key recovery time while using at most 2³⁰ chosen plaintext-tweak pairs. Since PAC aims to deter software exploitation, we consider attacks with time complexity up to 2⁶⁴ to be breaks of the function. We also consider attacks requiring up to 2⁸⁰ operations as warnings, even though they may not be practical on commodity hardware. This 2⁸⁰ threshold has historical precedent — it was once considered a practical limit for cryptanalysis, as reflected in the use of 80-bit keys in Skipjack [NIS98] and of 160-bit SHA-1 digests [NIS95]. However, these security levels were soon deemed in sufficient for long-term use [LV01, Section 5]. Today’s Bitcoin network performs ≈ 2⁹⁵.² SHA-256 operations annually at a rate of 750 · 10⁶ TH/s [Blo24], where one “H” involves two SHA-256 calls. This demonstrates that 2⁸⁰ operations is achievable with significant parallel resources — such as the brute force key search in our most expensive attacks. Therefore, while attacks requiring between 2⁶⁴ and 2⁸⁰ operations may not lead to a quick break of the system, advancements in cryptanalytic techniques could close the gap.

## 1.2 Our Contributions

We apply differential (and multiple differential) cryptanalysis to the PAC function based on QARMA₃ used in FEAT_PACQARMA3.

Our findings reveal that the function does not meet the security bounds for the underlying cipher when pointer lengths are 48 bits or longer, with attacks using fewer than 2³⁰ chosen plaintexts and 2⁶⁴ encryptions. The 44-bit pointer version narrowly exceeds these security bounds. While the versions for shorter pointers surpass both bounds, they are susceptible to attacks using fewer than 2⁸⁰ encryptions. The 32-bit M-profile version presents the strongest resistance to our analysis despite exposing more output bits, due to its strict input constraints.

The complete results are summarized in Table 1 together with published cryptanalysis of the unrestricted QARMA-64. To understand their relevance, note first that, currently, no Arm cores implement 56-bit VA spaces. 36-bit and 40-bit VA spaces are also increasingly rare, since most modern operating systems tend to favor 48-bit VAs for commodity devices and 52-bit VAs for server applications. The most relevant cases are thus those of VA spaces of 48 and 52 bits and, to a lesser extent, 44 bits.

Our results do not directly translate to practical breaks of the PAC feature. Attackers that rely on memory read gadgets can only mount KPAs using program-generated pointers. While JIT environments theoretically enable CPAs, practical constraints significantly limit the choice of inputs. Thus, PAC remains a significant barrier for the attackers.

Comparing to the cryptanalysis published so far, it is worth noting that we improve on the 4 + 4 rounds attack in [LJ18] in terms of running time and memory usage, despite the restrictions on inputs and outputs.

In order to perform our cryptanalysis we had to overcome a few hurdles. First, the clamping of input bits and chopping of output bits in the PAC function limits the differential
<table><caption>**Table 1:** Our results, compared to published cryptanalysis of QARMA-64. Rounds are counted as *x* + *y*, where *x* and *y* are S-Box layers before and after the reflector, respectively. For the attacks on the PAC function we also mention the VA space size, which determines the number of clamped plaintext cells and of chopped ciphertext cells, and “A” and “M” refer to A-profile and M-profile architectures. Memory is given in cipher blocks.</caption><thead><tr><th>Rounds<br>attacked</th><th>VA &<br>Profile</th><th>Additions<br>of w, o(w)</th><th>Attack<br>Data</th><th>Complexity<br>Time</th><th>Memory</th><th>Technique</th><th>Reference</th></tr></thead><tbody><tr><td>4 + 6</td><td>N</td><td>2<sup>53</sup> CP</td><td>2<sup>116</sup> + 2<sup>70.1</sup></td><td>2<sup>116</sup></td><td></td><td>Meet-in-the-Middle</td><td>[ZD16]</td></tr><tr><td>3 + 8</td><td>N</td><td>2<sup>58.38</sup> CP</td><td>2<sup>64.92</sup></td><td>2<sup>63.38</sup></td><td></td><td>Imp. Diff.</td><td>[LZG+20]</td></tr><tr><td>4 + 4</td><td>Y</td><td>2<sup>16</sup> CP</td><td>2<sup>33</sup> + 2<sup>90</sup></td><td>2<sup>90</sup></td><td></td><td>Meet-in-the-Middle</td><td>[LJ18]</td></tr><tr><td rowspan="10">This paper</td><td>4 + 4</td><td>56 (A)</td><td>Y</td><td>2<sup>25</sup> CP</td><td>2<sup>60</sup></td><td>2<sup>28.98</sup></td><td>Rel-Tweak (RT) Diff.</td><td>Section 5.1</td></tr><tr><td>4 + 4</td><td>52 (A)</td><td>Y</td><td>2<sup>25.3</sup> CP</td><td>2<sup>55</sup></td><td>2<sup>28.94</sup></td><td>RT Diff.</td><td>Section 5.2</td></tr><tr><td>4 + 4</td><td>48 (A)</td><td>Y</td><td>2<sup>28</sup> CP</td><td>2<sup>60</sup></td><td>2<sup>40.83</sup></td><td>RT Mult. Diff.</td><td>Section 5.3</td></tr><tr><td>4 + 4</td><td>44 (A)</td><td>Y</td><td>2<sup>31.19</sup> CP</td><td>2<sup>68</sup></td><td>2<sup>31.67</sup></td><td>RT Diff.</td><td>Section 5.4</td></tr><tr><td>4 + 4</td><td>40 (A)</td><td>Y</td><td>2<sup>37.5</sup> CP</td><td>2<sup>76</sup></td><td>2<sup>38.82</sup></td><td>RT Diff.</td><td>Section 5.5</td></tr><tr><td>4 + 4</td><td>36 (A)</td><td>Y</td><td>2<sup>33.7</sup> CP</td><td>2<sup>76</sup></td><td>2<sup>35.02</sup></td><td>RT Diff.</td><td>Section 5.6</td></tr><tr><td>4 + 4</td><td>32 (A)</td><td>Y</td><td>2<sup>42</sup> CP</td><td>2<sup>76</sup></td><td>2<sup>44.32</sup></td><td>RT Diff.</td><td>Section 5.7</td></tr><tr><td>4 + 4</td><td>32 (M)</td><td>Y</td><td>2<sup>45</sup> CP</td><td>2<sup>76</sup></td><td>2<sup>46.32</sup></td><td>RT Diff.</td><td>Section 5.7</td></tr><tr><td>4 + 5</td><td>Y</td><td>Y</td><td>2<sup>16</sup> CP</td><td>2<sup>48</sup> + 2<sup>89</sup></td><td>2<sup>89</sup></td><td>Meet-in-the-Middle</td><td>[LJ18]</td></tr><tr><td>4 + 6</td><td>Y</td><td>Y</td><td>2<sup>61</sup> CP</td><td>2<sup>72</sup></td><td>2<sup>72.2</sup></td><td>Trunc. Imp. Diff.</td><td>[YQC18]</td></tr><tr><td>4 + 6</td><td>Y</td><td>Y</td><td>2<sup>59</sup> KP</td><td>2<sup>59</sup></td><td>2<sup>23.6</sup></td><td>RT Stat. Sat.</td><td>[LHW19]</td></tr><tr><td>4 + 6</td><td>Y</td><td>Y</td><td>2<sup>47.12</sup> CP</td><td>2<sup>75.13</sup></td><td>2<sup>72</sup></td><td>RT Trunc. Diff.</td><td>[SH23]</td></tr><tr><td>5 + 5</td><td>Y</td><td>Y</td><td>T · D (CP) = 2<sup>119.8</sup></td><td></td><td>2<sup>31</sup></td><td>Rel-Tweak Imp. Diff.</td><td>[ZD19]</td></tr><tr><td>5 + 5</td><td>Y</td><td>Y</td><td>2<sup>47.06</sup> CP</td><td>2<sup>83.53</sup></td><td>2<sup>80</sup></td><td>RT Trunc. Diff.</td><td>[SH23]</td></tr><tr><td>3 + 8</td><td>Y</td><td>Y</td><td>2<sup>61</sup> CP</td><td>2<sup>64.4</sup> + 2<sup>80</sup></td><td>2<sup>61</sup></td><td>Imp. Diff.</td><td>[ZD18]</td></tr><tr><td>4 + 7</td><td>Y</td><td>Y</td><td>2<sup>61</sup> CP</td><td>2<sup>120.4</sup></td><td>2<sup>116</sup></td><td>Trunc. Imp. Diff.</td><td>[YQC18]</td></tr><tr><td>5 + 6</td><td>Y</td><td>Y</td><td>2<sup>34.26</sup> CP</td><td>2<sup>111.16</sup></td><td>2<sup>108</sup></td><td>RT Trunc. Diff.</td><td>[SH23]</td></tr><tr><td>4 + 8</td><td>Y</td><td>Y</td><td>2<sup>48.4</sup> CP</td><td>2<sup>66.2</sup></td><td>2<sup>53.70</sup></td><td>Zero Corr./Integral</td><td>[ADG+19]</td></tr><tr><td>6 + 5</td><td>Y</td><td>Y</td><td>2<sup>54</sup> CP</td><td>2<sup>66.35</sup></td><td>2<sup>64</sup></td><td>RT Differential</td><td>[CXTQ23]</td></tr></tbody></table>

characteristics we can use, requiring us to perform extended searches. To address this, we leverage the cipher's symmetry around the center by forcing center differences to zero during some clustering searches and while building a multiple differential. While this only provides bounds rather than exact values, experiments shows that the omitted characteristics have negligible impact (cf. Section 5.2 and Section 5.3.1). For some attacks, this hurdle also forces us to find more than one characteristic, often with very different properties from each other, in order to recover sufficiently many key bits.

Second, the small number of visible output bits creates high noise when trying to identify the correct key guess. We adopt a statistical approach to determine minimal data requirements to overcome this noise (cf. Section 3.5). The approach is experimentally validated as well (cf. Section 4.6).

The fixed total of 64 usable input and output bits means that having more visible output bits necessarily restrict input bits, and vice versa. Despite this inherent trade-off between input flexibility and output noise, we are able to provide some successful attacks.

Because of the restrictions on the useable characteristics and the low data bounds, in our attacks the brute force step is always the most expensive part.

The security of FEAT_PACQARMA5 and that of QARMA-64 with the recommended rounds for general use is unaffected by our results.

## 1.3 Outline

In Section 2 we recall the definitions of QARMA and of the PAC function. Section 3 describes Chosen-Input Key Recovery for the FEAT_PACQARMA3 function, and describes how we determine the success probability and the data and time complexities of a key recovery step. In Section 4 we describe how we find suitable characteristics for the attacks. In
<figure><img src="image_4.png" /><figcaption>Figure 3: The detailed common structure of MANTIS, QARMA, and QARMAv2.</figcaption></figure>

Section 5 we detail our attacks on the FEAT_PACQARMA3 function. We conclude in Section 6.

# 2 Background

## 2.1 QARMA

**Definition 2.1.** Let $E: \mathbb{F}_2^n \times \mathbb{F}_2^k \times \mathbb{F}_2^{n_t} \to \mathbb{F}_2^n$ be a function $(P, T, K) \mapsto C = E_{K,T}(P)$. The function $E$ is called a TBC if, for each fixed value of the pair $(K, T)$, it is a bijection of $\mathbb{F}_2^n$ onto itself. The $n$-bit input $P$ is called the plaintext, the $n$-bit output $C$ is called the ciphertext, the $n_t$-bit input $T$ is called the tweak, and the $k$-bit input $K$ is called the key. The key is secret, while the tweak is assumed to be public.

We recall here the definition of QARMA (v1). Its structure is represented in Figure 3, which can also be used to describe MANTIS and QARMAv2. The differences between the three ciphers, while they may appear minor, have profound implications on their security. The notations $k$, resp. $t$, $c$ denote a round key, resp. tweak and constant: The XOR of these values at the same round is the latter's round tweakey.

Each state of QARMA is represented as a $4 \times 4$ matrix of cells

$$A = \begin{pmatrix} A[0] & A[1] & A[2] & A[3] \\ A[4] & A[5] & A[6] & A[7] \\ A[8] & A[9] & A[10] & A[11] \\ A[12] & A[13] & A[14] & A[15] \end{pmatrix},$$

and $4 \times 4$ matrices operate column-wise on the state by left multiplication. With respect to cell numbering, the 64 bits of a state are indexed in big endian order and the bits in a cell are indexed in little endian order: bits [63—60] are contained in Cell 0 and bits [3—0] in Cell 15. The bits in a cell can also be referred to using the square bracket notation.

A full round has the following structure:

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

where $R = S \circ M \circ \tau$. $S$ consists of a layer of sixteen identical S-Boxes, applied to the sixteen cells in parallel. $M$ is an involutory Almost-MDS matrix. $\tau$ is the MIDORI cell permutation,
which with our cell numbering is $\tau = [0, 11, 6, 13, 10, 1, 12, 7, 5, 14, 3, 8, 15, 4, 9, 2]$, acting on a state as $\tau(A)[i] = A[\tau(i)]$ for $0 \le i \le 15$. The $4 \times 4$ matrix $M$ operates column-wise by left multiplication on each layer of the block. $S$ is the parallel application of the same S-Box to all 16 cells of the state. The half-round function, only used for the outermost rounds of the cipher, consists of just a round key addition and an S-Box layer.

The matrices are involutory circulants of the form

$$M = \text{circ}(0, \rho^a, \rho^b, \rho^c) = \begin{pmatrix} 0 & \rho^a & \rho^b & \rho^c \\ \rho^c & 0 & \rho^a & \rho^b \\ \rho^b & \rho^c & 0 & \rho^a \\ \rho^a & \rho^b & \rho^c & 0 \end{pmatrix} .$$

over a ring with zero divisors, $R_m = \mathbb{F}_2[\rho] = \mathbb{F}_2[X]/(X^m + 1)$, where $\rho$ is a circular left rotation of the bits.

We describe only QARMA's encryption, as decryption uses the same circuit with a different configuration of round keys and tweaks, which is simple to derive and found in [Ava17].

The 128-bit key is $K = w^0 \parallel k^0$ where the 64-bit values $w^0$ and $k^0$ are the whitening and core keys. Put $w^1 = o(w^0) := (w^0 \gg 1) + (w^0 \gg 63)$ and $k^1 = k^0 + \alpha$. The round keys $k_0$ and $k_{2r+1}$ are equal to $w^0 + k^0$ and $w^1 + k^1$. Then, $k_i = k^0$ for $1 \le i < r$, and $k_i = k^1$ for $r + 2 \le i \le 2r$, where $\alpha$ is a constant. The round keys at the sides of the reflector are $k_r = w^1$ and $k_{r+1} = w^0$. The central round keys are $k'_0 = 0$ and $k'_1 = k^0$. Also, $\tau' = \tau$.

For PAC, QARMA uses the S-Box $\sigma_0 := [0, 14, 2, 10, 9, 15, 8, 11, 6, 4, 3, 7, 13, 12, 1, 5]$. The matrix $M$ has parameters $a = 1, b = 2, c = 1$. The round constants are consecutive digits of the fractional part of $\pi$, with $c_0 = 0$. The tweak schedule is $t_{i+1} = \omega(h(t_i))$ for $0 \le i < r$ where $h$ is the tweak shuffle $h = [6, 5, 14, 15, 0, 1, 2, 3, 7, 12, 13, 4, 8, 9, 10, 11]$ and $\omega$ is a LFSR that maps cell $(b_3, b_2, b_1, b_0)$ to $(b_0 + b_1, b_3, b_2, b_1)$, applied to Cells 0, 1, 3, 4, 8, 11, and 13. The tweak schedule is symmetric, i.e., $t_{2r+1-i} = t_i$. For the rationale behind these choices of components, we refer readers to the original design paper [Ava17].

## 2.2 The PAC Functions

### 2.2.1 A-Profile Version

We refer here to [Arm24, Section D8.8]. The admissible VA space sizes $V$ in the Arm architecture(s) range from 32 to 56 bits in steps of 4 bits, as well as 42 bits, where the 56-th bit is always reserved. The system configuration bit tbi (“Top Byte Ignored”) indicates whether the top byte of an address is used for address match for the TTBRx_EL1 (x can be 0 or 1) region, or ignored and used for tagged addresses. If tbi is 0, the PAC is computed on $s^{64-V} \parallel ptr[V-1:0]$, where $s \in \{0,1\}$, and it is inserted in bits [63:56] and [54:V]. The effective PAC field length is thus $63 - V$ bits. The bit $s$ is called the “upper/lower” bit and it is commonly used to separate user space from system stack n memory. If tbi is 1, the PAC is computed on ptr[63:56] $\parallel s^{56-V} \parallel ptr[V-1:0]$, where $s \in \{0,1\}$, and it is inserted in bits [54:V]. The effective PAC field length is thus $55 - V$ bits.

The PAC bits are taken from the corresponding bits of the QARMA ciphertext output. For PAC calculation, pointers undergo sign-extension. We assume that the pointers in an attack are either all in user space or all in kernel space, ensuring zero difference in the sign extension bits. For the purpose of cryptanalysis, the first $z = (64 - V)/4$ cells of the plaintext input are clamped and the last $16 - z$ cells of the ciphertext are chopped.

### 2.2.2 M-Profile Version

We follow [Arm23, Section B6.1.1]. In M-Profile CPUs, pointers are 32 bits long, so the plaintext input is padded with 32 zeros, and the PAC consists of the 32 least significant bits of the cipher's output. Thus, in the cryptanalysis, the first eight cells of the plaintext are clamped and the first eight cells of the ciphertext are chopped.
<figure><img src="image_6.png" /><figcaption>**Figure 4:** Key Recovery in a Differential Attack on a Clamped and Chopped Cipher.</figcaption></figure>

### 3 Differential Key Recovery Attack on the PAC Function

Biham and Shamir's fundamental concept of a differential characteristic [BS90, BS91] is the starting point of our analysis.

**Definition 3.1.** We call $\Delta = (\Delta_{in}, \Delta_{out}) \in \mathbb{F}_2^n \times \mathbb{F}_2^n$ a differential for a block cipher with block size $n$ that covers a section $\mathcal{D}$ of the cipher consisting of $r_{mid}$ rounds where $\Delta_{in}$ is the input difference and $\Delta_{out}$ is the output difference. For a TBC, this is associated with a tweak difference $D_T$, and we write $\Delta = (\Delta_{in}, \Delta_{out}, D_T) \in \mathbb{F}_2^n \times \mathbb{F}_2^n \times \mathbb{F}_{2^t}$, where $n_t$ is the tweak's bit size. We denote the probability of a differential by $2^{-q}$ for some real value of $q$.

To apply differential cryptanalysis to an iterated block cipher, we need to identify a differential characteristic, i.e., a sequence of differences that describes how a difference propagates through the successive rounds of the cipher, and with which probability.

**Definition 3.2.** When $\Delta = (\Delta_{in}, \Delta_{out}) \in \mathbb{F}_2^n \times \mathbb{F}_2^n$ is fully specified in the sense that each intermediate state difference is described, we call it a differential characteristic. An $r$-round differential characteristic is a series of differences, denoted as $(a_0 \to a_1 \to \cdots \to a_r)$, where $a_0 = \Delta_{in}$, and $a_r = \Delta_{out}$.

**Definition 3.3.** A differential can correspond to several differential characteristics. We call a set of characteristics of the form $(a_0 \to a_1 \to \cdots \to a_r)$ with $a_0 = \Delta_{in}$ and $a_r = \Delta_{out}$, a cluster corresponding to the differential $\Delta = (\Delta_{in}, \Delta_{out})$. The probability of any differential from input difference $\Delta_{in}$ to output difference $\Delta_{out}$ can be computed by taking the sum over the probabilities of all possible characteristics of the form $(a_0 \to a_1 \to \cdots \to a_r)$ with $a_0 = \Delta_{in}$ and $a_i = \Delta_{out}$. We refer to Section 4.5 to see how clustering is performed.

To run key recovery on $\mathcal{E}$ using $\Delta$, we extend the differential by adding rounds at one or both ends until we cover the whole cipher. This is done by tracing the potential activeness of the cells, but not the actual differences, starting from $\Delta_{in}$, resp., $\Delta_{out}$, and going outwards through the added rounds until we reach $D_{in}$, resp., $D_{out}$. In Section 4 we describe how to trace this diffusion through the components of QARMA. Our goal is to recover the set of round key bits $\mathcal{K}$ affecting the differences in the rounds added in the front. We use the back of the function only as a distinguisher. Figure 4 illustrates our settings, and with reference to it, we have $\mathcal{E} = g \circ \mathcal{D} \circ f$, where $f$ consists of the initial $r_{in}$ rounds and $g$ is the final (half) round of the cipher.

Following common (abuse of) terminology, we use the terms input difference and output difference to refer to $\Delta_{in}$ and $\Delta_{out}$, respectively, even for extended characteristics, for which $D_{in}$ and $D_{out}$ are called the plaintext and ciphertext differences. The ciphertext output is then chopped to $u \le n$ bits, discarding the other $n-u$ bits (in our case $n=64$).
**Definition 3.4.** The dimensions of $D_{in}$, $D_{out}$, resp., $\Delta_{in}$, are $d_{in}$, $d_{out}$, resp., $\delta_{in}$. We further define $\hat{D}_{out}$ as the subset of $D_{out}$ that can be observed in the u visible bits, and $\hat{d}_{out}$ is its dimension, i.e. $|\hat{D}_{out}| = 2^{\hat{d}_{out}}$.

**Remark 3.1.** Note that $\Delta$ may be a truncated (or multiple) differential, where at least one of $\Delta_{in}$, $\Delta_{out}$, and $D_T$ is a set. The non-truncated case corresponds to $|\Delta_{in}| = |\Delta_{out}| = |D_T| = 1$. For simplicity, in this section we consider only a non-truncated $\Delta$. In Section 5.3.1 we straightforwardly adapt the treatment to the multiple differential case,

## 3.1 The Key Recovery Algorithm

We give first a high-level description of the various steps of the key-recovery process. The details are given in the following subsections. Pseudo-code is given in Algorithm 1.

First, we repeatedly query the encryption oracle to generate pairs of plaintext-tweak-ciphertext triplets $((P_0^i, T_0^i, C_0^i), (P_1^i, T_1^i, C_1^i))$ that, by construction, satisfy $D_{in}$ and $D_{T}$, i.e., $P_0^i + P_1^i \in D_{in}$ and $T_0^i + T_1^i \in D_{T}$. Suppose also that $N$ of these pairs satisfy $\Delta_{in}$, i.e., their differences at the start of $\mathcal{D}$ are in $\Delta_{in}$. We describe in Section 3.2 how we use structures so that we get a desired number $N$ of pairs that satisfy $\Delta_{in}$. For now we just assume that $N$ is the number of pairs that satisfy $\Delta_{in}$, and that one in $2^q$ of these $N$ pairs satisfies the output difference $\Delta_{out}$ — we call the latter right pairs. They of course satisfy the chopped ciphertext difference $\hat{D}_{out}$ as well. With a right pair, we can use the plaintext values and the difference at $\Delta_{in}$ to deduce the right key, as explained in Section 3.4. For an attack to be successful, we need at least one right pair, i.e., $N \ge 2^q$.

However, wrong (i.e., non-right) pairs may also satisfy $\hat{D}_{out}$ by random chance with probability $2^{-u+\hat{d}_{out}}$, and such pairs may suggest any key value. The right key will thus be suggested with probability $2^{-q} + 2^{-u+\hat{d}_{out}}$. (More precisely, since the proportion of wrong pairs is $1 - 2^{-q}$, the right key will be suggested by a pair with input difference $D_{in}$ with probability $2^{-q} + 2^{-u+\hat{d}_{out}}(1 - 2^{-q})$, but we are assuming $2^{-q}$ too small.) The noise from wrong pairs can make it difficult for the right to stand out, especially when $2^{-q} \ll 2^{-u+\hat{d}_{out}}$. To overcome this noise, we must choose a sufficiently large $N$. Choosing $N$ is non-trivial and is described in Section 3.5.

After data collection we perform Pair Sieving, i.e., we keep only the $L$, say, pairs that satisfy $\hat{D}_{out}$, i.e., $C_0^i + C_1^i \in \hat{D}_{out}$. While this could be performed by building a list of length $L$, we instead use a hash table keyed by the values taken by the chopped ciphertext at the inactive cells of $\hat{D}_{out}$ to enable efficient enumeration of the pairs that satisfy $\hat{D}_{out}$.

Finally, we perform the actual key recovery through the front $r_{in}$ rounds. For each sieved pair $((P_0^i, T_0^i, C_0^i), (P_1^i, T_1^i, C_1^i))$ and each key guess $\kappa \in \mathcal{K}$ we test whether $f_{\kappa}(P_0^i, T_0^i) + f_{\kappa}(P_1^i, T_1^i) \in \Delta_{in}$. When this happens, we say we have a positive match that suggests $\kappa$ as a key candidate, and we increase a counter associated with $\kappa$. The right key should appear among the most frequently suggested keys across all pairs.

Since the S-Box is bijective, given a non-zero output difference, an input pair with a non-zero difference produces on average one solution. Hence, the sum of all counters is expected to be $L$. To track key counters, we avoid full tables when most entries are zero, as these waste memory, need a lengthy initialization step, and have poor cache locality. Instead, we store non-zero counters only in self-balancing trees [Knu98, Section 6.2.3]. In our attacks, AVL trees [AVL62] give the best performance compared to Red-Black trees [Bay72], splay trees [ST85], and full tables. For cases with just a handful of non-zero counters, we could use a bubble-sorted list [Fri56] of key-counter pairs, but this does not occur in our attacks.
**Algorithm 1 BASIC KEY RECOVERY PROGRAM.**

**Input:** A tweakable encryption oracle $\mathcal{E}$, a characteristic $D_{in} \times D_T \mapsto \Delta_{in} \mapsto \Delta_{out} \mapsto D_{out}$ and a set of round key bits $\mathcal{K}$ intersecting the active cells in the additional front rounds.

**Output:** A dictionary associating counters with the elements in $\mathcal{K}$.

▷ *Data Collection and Pair Sieving Stage*

1: $C = \emptyset$

2: **for** $s$ distinct structures $S$ **do**

3: Prepare $\mathcal{L}_0 = \{(P, T_0, \varepsilon_{T_0, \mathcal{K}}(P)) \mid (P, T_0) \in S_0\}$

4: Prepare $\mathcal{L}_1 = \{(P, T_1, \varepsilon_{T_1, \mathcal{K}}(P)) \mid (P, T_1) \in S_1\}$

5: **for** $((P_0, T_0, C_0), (P_1, T_1, C_1)) \in \mathcal{L}_0 \times \mathcal{L}_1$ **do**

6: **if** $C_0 + C_1 \in D_{out}$ **then**

7: $C = C \cup ((P_0, T_0, C_0), (P_1, T_1, C_1))$

▷ *Data Analysis Stage (Guess-and-Filter)*

8: Prepare a dictionary $\chi$ to associate counters with the elements $k \in \langle \mathcal{K} \rangle$

9: **for** $((P_0, T_0, C_0), (P_1, T_1, C_1)) \in C$ **do**

10: **for** $k \in \langle \mathcal{K} \rangle$ **do**

11: **if** $f_k(P_0^i, T_0^i) + f_k(P_1^i, T_1^i) \in \Delta_{in}$ **then**

12: $\chi(k) = \chi(k) + 1$

13: **return** $\chi$

## 3.2 Structures and Complexity

To efficiently generate plaintext pairs, we use *structures*, a technique dating back to [BS92].
We present our adaptation of the concept tailored to our specific case.

**Definition 3.5.** A structure $\mathcal{S}$ consists of two affine subspaces $S_0, S_1 \subseteq \mathbb{F}_2^n \times \mathbb{F}_2^{n_t}$, which we call half-structures, each half-structure being constant on $\mathbb{F}_2^{n_t}$. Here $S_1 = (\mathbf{x}_0, \mathbf{t}_0) + S_0$ where $\mathbf{x}_0$ and $\mathbf{t}_0$ are the fixed differences in the input pairs restricted to the plaintext and to the tweak, respectively.

**Remark 3.2.** When there are no bits with a fixed non-zero difference at the input and no tweak difference, then $S_1 = S_0$. As in this paper we use a non-zero tweak difference in the attacks, the remainder of this paper assumes two subspaces, i.e., $S_1 \neq S_0$.

All the elements of $D_{in} \times D_T$ are of the form $((P_0, T_0), (P_1, T_1))$ with $(P_i, T_i) \in S_i$. Since the $S_i$ have dimension $d_{in}$, each structure generates $2^{2d_{in}}$ pairs, out of which $2^{d_{in}}$ satisfy $\Delta_{in}$. With $2^s$ structures we generate $2^{s+d_{in}}$ such pairs. To generate $N$ pairs, we distinguish two cases, depending on the relative magnitude of $2^{d_{in}}$ and $N$.

If $2^{d_{in}} \le N$, then we have $s = \log_2 N - d_{in}$ and we need to query the encryption oracle $2 \cdot 2^{s+d_{in}} = 2^{\log_2 N+1} = 2N$ times.

If $2^{d_{in}} > N$, a complete structure generates more data than needed. Instead, we use a *partial structure*, where each half-structure $S_i$ is a randomly chosen subset of $\mathbb{F}_2^n \times \mathbb{F}_2^{n_t}$, and is constant on $\mathbb{F}_2^{n_t}$. If we pick $2^x$ values out of $2^{d_{in}}$ from each of $S_0$ and $S_1$, the expected number of pairs that satisfy $\Delta_{in}$ is approximately $2^{2x-d_{in}}$. We want $2^{2x-d_{in}} = N$, that is $x = (\log_2 N + d_{in})/2$, hence we need to query the encryption oracle $2\sqrt{N} \cdot 2^{d_{in}}$ times.

In some cases (namely, where we use conditional characteristics) we have to use multiple partial structures, which requires minimal adjustments to data and time complexity (cf. Section 4.6 for the background, Section 5.3.1, and Section 5.4 for concrete applications).

For each pair that satisfies $\hat{D}_{out}$, we perform a *guess-and-filter* step, whose cost we denote by $T_{GF}$. We determine the cost of such steps in Section 3.4. The number of non-zero counters is expected to be relatively small, hence the time for updating them is usually negligible, but its worst case is $\min(2^{|\mathcal{K}|}, L)$.
## 3.3 Memory Usage

Each data triplet $(P^i, T^i, C^i)$ needs only two 64-bit blocks worth of storage, since the tweaks are constant per half-structure. By offloading structure data to external storage, we need to keep in RAM only at most one structure worth of collected data.

For the hash table we need at most one block (which can hold either a plaintext or a pointer depending on the implementation) per entry in the structure currently in memory, as well as one block per each of the $2^{u-\hat{d}_{out}}$ possible hashing keys.

Regarding the dictionary structure, let us consider an AVL tree. An internal node contains two pointers, a key, and a counter, which in our attacks always fit in 3 blocks. A leaf counter does not contain the pointers, hence it fits in one block. Since at least $1/\varphi$ of the nodes are leaves (where $\varphi = (1 + \sqrt{5})/2$), we have that the average size of a node does not exceed $3 \cdot (1 - 1/\varphi) + 1/\varphi \approx 1.764$ blocks. We allocate the blocks in chunks, to minimize the overhead and performance impact from the system memory allocator. The number of nodes is $\ell = \min(2^{|\mathcal{K}|}, L)$. Since the size of the AVL tree can be estimated in advance, we revert to a table of counters in case the latter is expected to be smaller.

Computing the memory storage is a routine application of the three estimates above to the data provided with the attacks. If an attack uses more characteristics, we reuse the memory and thus consider only the maximum memory usage across all characteristics. Full results are tabulated in Table 1 to provide a comparison with previous work.

## 3.4 Implementing Guess-and-Filter

### 3.4.1 Guess-and-Filter in a 0.5R Attack

Let us start with the case where a half-round is added in front of the characteristic. This is called a 0.5R (for half round) attack. We denote the set of the indices of the active cells at the beginning of $\mathcal{D}$ by $\mathfrak{S} \subseteq [0..15]$. Note that $\mathfrak{S}$ coincides with the set of active cells in $D_{in}$, except possibly for those affected by the tweak addition. Let $A[i]$ denote the $i$-th cell of a state $A$. Given a sieved pair $((P_0, T_0, C_0), (P_1, T_1, C_1))$, we aim to obtain key suggestions $(k + w)[i]$ for $i \in \mathfrak{S}$. As $\Delta_{in}$ is the output difference of the first S-box layer, we recover $i$-th cell of $k + w$ by solving the following equations

$$ \Delta_{in}[i] = S(P_0[i] + T_0[i] + (k+w)[i]) + S(P_1[i] + T_1[i] + (k+w)[i]) \quad \text{for } i \in \mathfrak{S}, \quad (1) $$

where $S$ is the S-box. We can rewrite Equation (1) as

$$ \Delta_{in}[i] = S(x[i]) + S(x[i] + P_0[i] + P_1[i] + T_0[i] + T_1[i]) \quad \text{for } i \in \mathfrak{S}, \quad (2) $$

where $x[i] = P_0[i] + T_0[i] + (k+w)[i]$. Solving such equations is easy since the differences $P_0[i] + P_1[i] + T_0[i] + T_1[i]$ and $\Delta_{in}[i]$ are known. Following [BS90, BS91], we store not only the number of solutions in the *Difference Distribution Table* (DDT) but also the solutions themselves. By solving each of these equations we obtain suggestions for each $(k+w)[i]$, and we denote the set of suggested keys by $\mathcal{K}_i$ for each $i \in \mathfrak{S}$. After that, we combine the sets $\mathcal{K}_i$ suggestions for each $i \in \mathfrak{S}$.

For each sieved pair, the cost of key recovery through a half-round at the front depends on the size of $\mathfrak{S}$. Note that while $P_0[i] + P_1[i] + T_0[i] + T_1[i]$ and $\Delta_{in}[i]$ are fixed, for any active S-box there are at most 4 solutions to Equation (2) due to the *differential uniformity* of the used S-box being 4. Out of the 255 entries (excluding the entry corresponding to $0 \mapsto 0$) in the DDT, 102 are non-zero: 84 entries have the value 2 and 18 the value 4. On average, for a random non-zero input/output pair, we expect a solution, but if there are solutions, there are either 2 or 4. In most of the characteristics used in this paper, the size of $\mathfrak{S}$ is at most 7. Hence, when a solution exists, there are about $2^7$ solutions, the same number as the amount of S-Boxes in $\mathbf{QARMA}_3$. Thus, we bound the cost of $T_{GF}$ in a 0.5R attack from above with the cost of a single $\mathbf{QARMA}_3$ encryption, which we denote by $T_{\delta}$.
<figure><img src="image_7.png" /><figcaption>Figure 5: The four cell quartets of a state mapped by $\tau$ to columns.</figcaption></figure>

<figure><img src="image_8.png" /><figcaption>Figure 6: Attacking 1.5 rounds, naïvely.</figcaption></figure>

### 3.4.2 Guess-and-Filter in a 1.5R Attack

Adding 1.5 rounds to the differential characteristic is also called a 1.5R attack. As before, we consider the case where the rounds are added to the front. The naïve way of performing a 1.5R attack is to try all the involved key bits in $k+w$ and $k$.

Due to the matrix operation in the full round, we must examine $\Delta_{in}$ column-wise. Consider the four cells of $D_{in}$ that map to an active column $c$ of $\Delta_{in}$ after 1.5 rounds: The four cell quartets of $D_{in}$ mapped to the four columns of $\Delta_{in}$ by $\tau$ are given in Figure 5. For conciseness, we consider only the first quartet, corresponding to the first column, the other cases being corresponding to permutations.

If only one cell of $c$ is active, then exactly three of the four cells in $D_{in}$ are active unless the fourth is activated by a tweak addition or one is cancelled by the tweak difference. Given a sieved pair $((P_0, T_0, C_0), (P_1, T_1, C_1))$, up to a permutation of the indices, the situation is equivalent to the one depicted in Figure 6, where 0 indicates a zero difference. Let $\mathcal{G}$ denote the set of the three cells activated by $c$ in $D_{in}$, in our example $\mathcal{G} = \{5, 10, 15\}$. Note that here we attempt to recover the key bits of $(k+w)$ and $k$ that are involved while we extend $\Delta_{in}$ backward to $D_{in}$. However, in the case of the key bits in $k$, it is more helpful to recover the equivalent key $k'$ where $k' = M(\tau(k))$ is added before the second S-box operation as shown in Figure 7. This results in the following relations

$$ 
\left\{ 
\begin{array}{l}
Q_i[j] = S(P_i[j] + T_i[j] + (k+w)[j] + c_0[j]) \quad \text{for } i \in \{0, 1\} \text{ and } j \in \{5, 10, 15\} \\
W_i[j] = Q_i[j] + \omega(h(T_i))[j] + c_1[j] \\
X_i[0] = W_i[0] \ , \ X_i[4] = W_i[10] \ , \ X_i[8] = W_i[5] \ , \ X_i[12] = W_i[15] \\
Y_i[0] = \rho(X_i[4]) + \rho^2(X_i[8]) + \rho(X_i[12]) \qquad (3a) \\
Y_i[4] = \rho(X_i[0]) + \rho(X_i[8]) + \rho^2(X_i[12]) \Rightarrow \Delta_Y[4] = \rho(\Delta_X[8]) + \rho^2(\Delta_X[12]) \\
Y_i[8] = \rho^2(X_i[0]) + \rho(X_i[4]) + \rho(X_i[12]) \Rightarrow \Delta_Y[8] = \rho(\Delta_X[4]) + \rho(\Delta_X[12]) \\
Y_i[12] = \rho(X_i[0]) + \rho^2(X_i[4]) + \rho(X_i[8]) \Rightarrow \Delta_Y[12] = \rho^2(\Delta_X[4]) + \rho(\Delta_X[8]) \\
\Delta_Z[0] = S(Y_0[0] + k'[0]) + S(Y_1[0] + k'[0]) \ , \qquad (3b)
\end{array}
\right.
$$

where $\Delta_v$ denotes $v_0 + v_1$ for any variable pair $v = (v_0, v_1)$. These relations imply that in order to recover, say $k'[0]$, we also need to either know or to guess $(k+w)[\mathcal{G}]$.

We now describe the peeling strategy (see the 3R attack in [BS91, Section 5]) to recover one or more cells of $k'$ — for simplicity let us stick to $k'[0]$. Assuming that we already mounted a 0.5R attack with the same $D_{in}$ and $\hat{D}_{out}$, we can reuse the same data set. We repeat the pair sieving iterator of the 0.5R attack, but this time instead of testing for round key candidates, we simply check whether the current pair suggests the already recovered right key bits of $(k+w)$. For these pairs and each possible guess of the as-of-yet unknown bits of $(k+w)[\mathcal{G}]$ that contribute to $k'[0]$, we determine candidates for $k'[0]$. The
<figure><img src="image_9.png" /><figcaption>**Figure 7:** Attacking 1.5 rounds, using an equivalent key on the second round, landing on a column with one active cell.</figcaption></figure>

<figure><img src="image_10.png" /><figcaption>**Figure 8:** Attacking 1.5 rounds, using an equivalent key on the second round, landing on a column with two active cells.</figcaption></figure>

counters correspond to the guessed bits $(k + w)[\mathcal{G}] \cup k'[0]$. To recover $k'$ in our example, we compute the values $Y_0[0]$ and $Y_1[0]$ from Equation (3a). Note that we either know $P_0, P_1, T_0, T_1$ as well as the cells of $k + w$ that are required to compute $Y_i[0]$, or we need to fix a guess for the unknown cells of $k + w$ that contribute to $k'[0]$. Finally, we consider the following equation which is equivalent to Equation (3b), and we solve it for $k'[0]$

$$ \Delta_Z[0] = S(x[0]) + S(Y_1[0] + Y_0[0] + x[0] + k'[0]) $$

where $x[0] = k'[0] + Y_1[0] + Y_0[0]$. Since the rounds of filtering are relatively rare, and the number of key bits to recover in a peeling step — including both bits to be guessed and those to be filtered — is often smaller than in the initial 0.5R attack step, making the cost of a peeling step is bounded by that of a 0.5R attack. This is the case in all our attacks.

The case where in the column c two cells (Figure 8) or more are active is similar. As the number of active cells in c increases, the number of cells with zero differences in $\Delta_Y$ decreases, and at the same time we can recover more bits of $k'$. There is thus a trade-off between the number of key bits recovered and the time complexity. In this paper, we use characteristics with at most two active cells in c.

**Remark 3.3.** Peeling can be done directly after a 0.5R attack even if did not start with a differential for a 1.5R attack. With reference to Figure 4, we perform key recovery also inside $\mathcal{D}$. The transition through the second round is not always unique, and sometimes there are multiple transitions with the same probability. However, if we fix the second round transition as in the original characteristic of the 0.5R attack, the probability of the differential obtained by removing the first round of $\mathcal{D}$ is still higher than that of $\mathcal{D}$. In particular, it allows us to recover correct key bits without the need for additional data.

## 3.5 The Poisson Distribution Argument

The relation between data complexity, time complexity and success probability is quite complex. However, ignoring the latter easily leads to oversimplifications and too optimistic complexity estimates. This subsection describes the approach we follow in this paper to determine all three quantities together: the *Poisson distribution argument*.

For each integer $a$, let $\omega(a)$ be the probability that the counter of a fixed wrong key is equal to $a$. The probability that the counter of one, fixed wrong key is smaller than
<figure><img src="image_11.png" /><figcaption>**Figure 9:** Modeling success probability. Let $\psi$ be the probability that the counter for a fixed wrong key is smaller than $E(R)$. If $\psi$ is not close to 1 (left), then its successive powers will quickly converge to zero. To ensure that the counters of many wrong keys are all smaller than $E(R)$ with a significant probability, $\psi$ must be very close to 1 (right), i.e., the probability that the counter of a fixed wrong key is at least $E(R)$ must be negligible.</figcaption></figure>

the expected value of the counter of the correct key $E(R)$ is the sum of the probabilities $\omega(a)$ for all $a < E(R)$. This sum is depicted as the shaded areas in Figure 9, while the dotted areas represent the failure probability. Since this must happen for all wrong keys, under the *Wrong Key Randomization Hypothesis* (WKRH) [HKM95], if the number of all possible keys is $\nu$, the success probability is

$$ \left( \sum_{a \le E(R)} \omega(a) \right)^{\nu-1}, \qquad (4) $$

i.e., the $(\nu-1)$-th power of the cumulative distribution function for the Poisson distribution at $E(R)$. To ensure a good success probability, the distributions for the counters of the correct key and of a wrong key must be clearly separated. To achieve this, we require that the difference between the expected counter values for the correct key and a wrong key be $\gamma$ times the standard deviation of the counter of a wrong key. We then pick the smallest value of $\gamma$ such that Equation (4) yields a 90% success probability under ideal distribution assumptions. When more than one characteristic is used in an attack, the product of their corresponding success probabilities should be at least 90%, so we have to aim at higher probabilities for the individual characteristics.

It is known that the WKRH is not always completely accurate [BT13], particularly for lightweight ciphers [ABR20]. Hence, after determining a value for $N$ we experimentally verify the effectiveness of the characteristics — if computationally feasible (cf. Table 2).

We now describe the actual Poisson distribution argument. If we are recovering $d$ round key bits from the front, we have $\nu = 2^d$ round key choices and, thus, counters.

Let $N$ be the to-be-determined required number of pairs that satisfy the input difference $\Delta_{in}$. We want to obtain a bound for $N$ in terms of the statistical properties of the characteristic we are analysing. The counters of the wrong keys behave according to Poisson $(N \cdot 2^{-u+\hat{d}_{out}})$, since a random pair, even if not right, still passes the sieving test with probability $2^{-u+\hat{d}_{out}}$. The counter of the correct key behaves like Poisson $(N \cdot (2^{-q} + 2^{-u+\hat{d}_{out}}))$ where $N \cdot 2^{-q}$ is the contribution from the right pairs. To ensure a significant separation between the distributions of the counter for the correct key and of the counters of the wrong keys, we require the difference between the means, $N \cdot 2^{-q}$, to be $\gamma$ times the standard deviation $\sigma = \sqrt{N \cdot 2^{-u+\hat{d}_{out}} \cdot (1 - 2^{-u+\hat{d}_{out}})}$ of the counter associated with a wrong key for some positive real number $\gamma$. Solving the inequality
$N \cdot 2^{-q} \geq \gamma \cdot \sigma$ for $N$, we obtain that $N$ must be at least

$$N(\gamma) = \gamma^2 \cdot 2^{2q} \cdot 2^{-u+\hat{d}_{out}} \cdot (1 - 2^{-u+\hat{d}_{out}}) .$$

Then, we apply Equation (4) to the distribution Poisson $(N(\gamma) \cdot 2^{-u+\hat{d}_{out}})$ and the expected value of the counter of the correct key, $E(R) = N(\gamma) \cdot (2^{-q} + 2^{-u+\hat{d}_{out}})$, with $\nu = 2^d$ to determine the success probability for the given $\gamma$.

If $\log_2 N \geq d_{in}$ we use multiple structures, otherwise we use partial structures. Out of the structures of Section 3.2 one can construct $2^{d_{in}} \cdot N$ pairs and therefore there are

$$L \approx 2^{d_{in}} \cdot N \cdot (2^{-u+\hat{d}_{out}} + 2^{-(q+d_{in})}) = N \cdot (2^{d_{in}-u+\hat{d}_{out}} + 2^{-q}) . \quad (5)$$

sieved pairs. Note that if we fix some of the variable bits, the effective value of $d_{in}$ needs to be reduced accordingly. The time and data complexities of Algorithm 1 are thus

$$ \mathbb{D} = 2^{m+1} \quad \text{and} \quad \mathbb{T} = 2^{m+1} \cdot (T_{\mathbb{O}} + T_{MW} + T_{MR}) + L \cdot T_{GF} \\ \text{where } m = \begin{cases} \log_2 N & \text{if } \log_2 N \geq d_{in} \text{ and} \\ \frac{\log_2 N + d_{in}}{2} & \text{if } \log_2 N < d_{in} \end{cases} \quad (6) $$

Here, $T_{MW}$, resp., $T_{MR}$ is the time required for a memory write, resp., read. $T_{\mathbb{O}}$ is the time required to query the SW oracle to obtain a chosen input encryption. The additional cost of $T_{\mathbb{O}}$ over that of an encryption, $T_{\xi}$, is impossible to estimate in general, as it depends on the details of the SW attack. For simplicity, we shall assume that $T_{\mathbb{O}} \approx T_{\xi}$.

# 4 Finding Good Key Recovery Characteristics

In this section, we describe how we search for key recovery friendly differential characteristics for QARMA. This is a cipher-specific and challenging problem. For a different scenario, namely the search for key recovery friendly characteristics for GIFT, see [ZDC+21].

## 4.1 Choice of the Cost Function

It is well established that the time complexity of key recovery inversely correlates with the probability $2^{-p}$ of the characteristic, making it desirable to minimize $p$. However, a characteristic with minimal $p$ but involving too many key bits may lead to a poor attack complexity [BS93]. Indeed, when the guess-and-filter phase dominates the cost of key recovery, time complexity is roughly proportional to $L$ encryptions. From Equation (5) we have $L \approx (\gamma \cdot 2^{q-u+\hat{d}_{out}})^2 \cdot 2^{d_{in}}$, with a dependency on $d_{in}$, specifically a factor of $2^{d_{in}}$. To heuristically account for this effect, we also consider characteristics minimizing $p + d_{in}$.

To better illustrate our approach, we discuss two characteristics. Each characteristic is constructed from a differential with two forward and three backward rounds, extended by 1.5 rounds at the front and 0.5 at the back. Only the two most significant nibbles of the output are visible and can thus be used as a distinguisher. The first characteristic has
been found by maximizing its probability, which is $2^{-p} = 2^{-9}$.

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

Here, and in the following, we denote the undetermined differences by *, the clamped plaintext cells by a boldface zero, and the visible ciphertext cells are grouped by a “lasso.” A single large, boldface zero in a smaller square denotes an all-zero state in the center. The states with an additional border are $D_{in}$, $\Delta_{in}$, $\Delta_{out}$ and $D_{out}$.

A random pair passes the sieving step with probability $2^{-8}$. By the Poisson distribution argument (Section 3.5) we need $2^{16}$ pairs satisfying $\Delta_{in}$, with $\gamma = 8$, to get a success probability of 95%. A partial structure with $2^{28}$ values per each half-structure (out of $2^{40}$) produces the required $2^{16}$ pairs, with a data complexity of $2^{29}$. After pair sieving, an average of $2^{48}$ sieved pairs remain. The time complexity is approximately $2^{49} T_{\delta}$.

The second characteristic has been found by minimizing $p + d_{in}$. It has probability $2^{-14}$, $d_{in} = 20$ and thus $p + d_{in} = 34$.

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

The Poisson distribution argument shows we need $2^{25}$ pairs satisfying $\Delta_{in}$, with $\gamma = 5.35$, to attain a success probability of 95%. We use $2^5$ complete structures, each producing $2^{20}$ pairs satisfying $\Delta_{in}$, for a data complexity of $2^{26}$. The time complexity is $2^{37} T_{\delta}$. Therefore, the second characteristic leads to a faster key recovery that also needs less data.

We now re-evaluate the two examples using the probability of the differential. For the first example, the probability of the differential $2^{-q} \approx 2^{-2}$ is significantly higher than the probability of the characteristic.<fnref n="3" /> Thus, there is an attack with a data complexity of $2^{27.5}$, a time complexity of $2^{46} T_{\delta}$, and a success probability of 95%. For the second example, $q \le 5$, for a data complexity of $2^{17}$, a time complexity of $2^{25} T_{\delta}$, and a success probability of 95%. Notably, the second characteristic remains the more effective one. While this is usually to be expected, it is not necessarily always the case. Nonetheless, these examples indicate that minimizing $p + d_{in}$ is a source of useful characteristics.

Though the expression $L \approx (\gamma \cdot 2^{q-u} + \hat{d}_{out})^2 \cdot 2^{d_{in}}$ suggests the use of the cost function $p + \hat{d}_{out} + d_{in}/2$ (note that $d_{in}$ is always a multiple of 4), the latter did not lead to improved attacks, while considerably increasing search time.

<footnote n="3">³ This bound, as well as the bounds for the other examples in this subsection, can be obtained by clustering (cf. Section 4.5) or by an argument similar to the one we use for Char. (13).</footnote>
Expanding on the examples above, minimizing $p + \hat{d}_{out} + d_{in}/2$ we find a characteristic with probability $2^{-10}$, $d_{in} = 28$ and $\hat{d}_{out} = 0$, for $p + \hat{d}_{out} + d_{in}/2 = 24$.

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

We need $2^{17.60}$ pairs satisfying $\Delta_{in}$, with $\gamma = 7$, to attain a success probability of 95%. A partial structure with $2^{22.80}$ values in each half-structure produces the required $2^{17.60}$ pairs. With respect to the second characteristic we need less data — $2^{23.80}$ blocks instead of $2^{26}$ — but the running time is slightly higher — $2^{37.61} T_{\delta}$ as opposed to $2^{37} T_{\delta}$.

Using the probability of the differential $2^{-3}$, i.e., $q = 3$, results in an attack with a data requirement of $2^{21.25}$ blocks and a time complexity of $2^{32.50}$, $T_{\delta}$. This is notably less effective than the second characteristic. This observation holds generally and can be attributed to the presence of the term $\hat{d}_{out}$ in the cost function. Reducing $\hat{d}_{out}$ imposes a fixed difference on more output cells, limiting their ability to take any value; as a result, it restricts the number of characteristics within a cluster.

We observe that constraining $\hat{d}_{out}$ leads to an increase in data requirements while the time complexity reduction does not significantly improve the time complexity of complete attacks, since they are primarily determined by the final brute-force steps.

Therefore, a more favorable cost function could be $p + d_{in}/2$. It quickly provides the second example, and also Char. (16) was found by minimizing this function.

## 4.2 Modelling the Search

In order to find good characteristics for key recovery, we model QARMA as a program for STP, the *Simple Theorem Prover* [GD07]. We extend Stefan Kölbl's *cryptosmt* [Köl14], which produces a *Satisfiability Modulo Theories* (SMT) program written in *Cooperating Validity Checker* (CVC) format (a language whose roots can be traced back to [SBD02]). STP uses then *cryptominisat* [SNC09] as the SAT solver. The steps are:

1. We program a bit-wise model of the $r_{mid}$ middle rounds (always including also the central construction). This allows tighter bounds than the cell-wise MILP (Mixed-Integer Linear Programming) models used in the development of QARMA.

2. To determine $D_{in}$ and $\hat{D}_{out}$, and thus $d_{in}$ and $\hat{d}_{out}$, we add cell-wise models to trace the involved key cells through the first $r_{in}$ rounds and the last round.

3. We add constraints on $D_{in}$, $\Delta_{in}$, $\Delta_{out}$, $D_{out}$ and, if necessary, also relations involving arbitrary cell differences to the model. Such constraints are used to restrict a search, or to split a single search into more searches that can run in parallel.

4. Finally, we add one of the cost functions discussed in Section 4.1 to the model.

STP can find all characteristics with a given cost. We also use it to enumerate representatives of all subsets of a cluster defined by a common difference at a given state (e.g., the state after the first S-Box layer that follows $\Delta_{in}$). The code is publicly available on GitHub<fnref n="4" />.

<footnote n="4">⁴https://github.com/ShibamCrS/DifferentialAttackPACQARMA3.git</footnote>
## 4.3 Impact of Input Clamping

The input to PAC functions is clamped. Without clamping, for each characteristic, usually additional ones exist with similar probabilities and related by various symmetries. Such symmetries can often be expressed as permutations of the cells, which can be iterated. In papers on unconstrained ciphers, authors often just need to mention that more key cells can be recovered at the same complexity by finding additional similar characteristics. However, input clamping eliminates most of these symmetries, necessitating an explicit search for additional characteristics.

## 4.4 Impact of Output Chopping

It is tempting to invoke some form of signal-to-noise-ratio argument to conclude that differential attacks are impossible when the probability of the differential is smaller than $2^{-u}$, where $u$ is the number of output bits. However, our analysis provides counterexamples, proving such an argument incorrect. Similar findings have been reported in the differential attacks on Feistel structures [Pat08] used to attack format preserving encryption schemes [HTT18, HMT19] and in linear cryptanalysis [ABD17].

## 4.5 Clustering

After a potentially good differential characteristic has been found, we can estimate its actual probability by identifying clusters for the given $\Delta_{in}$ and $\Delta_{out}$.

In our SMT model we fix the input difference $\Delta_{in}$ and only the zero positions of the output difference $\Delta_{out}$. This reflects the fact that pair sieving is based on the activeness of the output cells, not on their values, and suffices for key recovery only in the front rounds. The values of $D_T$ are fixed. The number of solutions is determined using cryptominisat.

Suppose we have a characteristic $\Delta_{in} \mapsto \Delta_{out}$ with probability $2^{-p}$. We count the characteristics $\Delta_{in} \mapsto \Delta_{out}$ with probability $2^{-p}, 2^{-(p+1)},$... until a certain fixed limit is reached. The sum of the probabilities of all the found characteristics, denoted by $2^{-q}$, is an estimate of the probability of the differential $\Delta_{in} \mapsto \Delta_{out}$. In Tables 2 and 3 we collect data on the effect of clustering analysis on the differentials used in our attacks.

## 4.6 Experimental Verification of Clustering Probabilities, and Conditional Characteristics

We experimentally verified the probabilities $2^{-q}$ computed by clustering by averaging results from 100 trials using random plaintexts, tweaks, and keys, obtaining a value $2^{-\bar{q}}$. A highly optimized implementation of QARMA is used in these experiments. The code for experimental verification is available on GitHub$^5$.

We now explain our experiments. If we use $N$ pairs, we observe random noise of magnitude $\eta = N \cdot 2^{-u+\hat{d}_{out}}$. The goal is to distinguish between two distributions, one with probability $\mu_1 = 2^{-q} + 2^{-u+\hat{d}_{out}}$ and another with probability $\mu_2 = 2^{-u+\hat{d}_{out}}$ and want to estimate $q$. Let $\bar{h}_i$ be the number of pairs that satisfy the truncated output difference $\hat{D}_{out}$ in the $i$-th experiment. The statistics of $\bar{h}_i - \eta$ give us an estimate of $q$ as $\bar{q} = -\log_2(\text{Mean}(\bar{h}_i - \eta)/N)$. These values are given in Table 2 for each characteristic.

We consider that a differential has sufficient signal if $\bar{h}_i - \eta$ is at least $\gamma/2$ units of the standard deviation of random noise. Thus, if $\bar{h}_i - \eta > (N \cdot 2^{-q})/2$, we consider the experiment to have been successful. We record the number of successful experiments in Table 2 together with $\bar{q}$ and the value of $q$ obtained from clustering analysis.

<footnote>$^5$https://github.com/ShibamCrS/DifferentialAttackPACQARMA3.git</footnote>
<caption>**Table 2:** Statistical properties of the characteristic used in our attacks.</caption>

The number of pairs *N* used in each experiment is the same as in the corresponding attack in Section 5. * marks the experiments restricted to tweaks fulfilling Relations (7) (resp. (8)) for Char. (13) (resp., Char. (15)). The experimentally obtained value of *q*, namely $\bar{q}$, is compared to the value obtained by clustering.

<table><thead><tr><th rowspan="2">z</th><th rowspan="2">Char.</th><th rowspan="2">q̃<sub>out</sub><br>z</th><th colspan="3">Estimated</th><th colspan="3">Computed</th><th rowspan="2">Successes<br>out of<br>100 trials</th></tr><tr><th>N</th><th>q</th><th>Chars. in<br>Cluster</th><th>η<br>S.D.</th><th>Mean ± S.D</th><th>Min</th><th>Max</th></tr></thead><tbody><tr><td rowspan="3">2</td><td>(9)</td><td>8</td><td>2<sup>14</sup></td><td>7.98</td><td>1543</td><td>7.98</td><td>64.11 ± 11.69</td><td>40</td><td>107</td><td>8.00</td><td>100</td></tr><tr><td>(10)</td><td>8</td><td>2<sup>18</sup></td><td>10.01</td><td>474186</td><td>31.94</td><td>256.19 ± 32.40</td><td>186</td><td>346</td><td>10.00</td><td>100</td></tr><tr><td>(11)</td><td>8</td><td>2<sup>20</sup></td><td>12.00</td><td>385024</td><td>63.87</td><td>257.50 ± 58.90</td><td>140</td><td>406</td><td>11.99</td><td>100</td></tr><tr><td rowspan="3">3</td><td>(11')</td><td>12</td><td>2<sup>18</sup></td><td>12.01</td><td>384880</td><td>7.99</td><td>63.80 ± 11.50</td><td>34</td><td>96</td><td>12.00</td><td>100</td></tr><tr><td>(13)</td><td>8</td><td>2<sup>22</sup></td><td>12.00</td><td>> 100 K</td><td>127.75</td><td>1022.33 ± 1832.27</td><td>-396</td><td>4739</td><td>12.00</td><td>27</td></tr><tr><td>(13)*</td><td>8</td><td>2<sup>18</sup></td><td>10.00</td><td>—</td><td>31.93</td><td>258.32 ± 39.27</td><td>164</td><td>366</td><td>9.98</td><td>100</td></tr><tr><td rowspan="2">4</td><td>(13')</td><td>8</td><td>2<sup>22</sup></td><td>12.00</td><td>> 100 K</td><td>127.75</td><td>1022.33 ± 1832.27</td><td>-396</td><td>4739</td><td>12.00</td><td>27</td></tr><tr><td>(13')*</td><td>8</td><td>2<sup>18</sup></td><td>10.00</td><td>—</td><td>31.93</td><td>258.32 ± 39.27</td><td>164</td><td>366</td><td>9.98</td><td>100</td></tr><tr><td rowspan="4">5</td><td>(15)</td><td>12</td><td>2<sup>29</sup></td><td>18.00</td><td>1512</td><td>361.99</td><td>2128.71 ± 2075.29</td><td>-614</td><td>5345</td><td>17.94</td><td>53</td></tr><tr><td>(15)*</td><td>12</td><td>2<sup>27</sup></td><td>17.00</td><td>—</td><td>181.00</td><td>1026.25 ± 174.94</td><td>568</td><td>1527</td><td>17.00</td><td>100</td></tr><tr><td>(16)</td><td>16</td><td>2<sup>30</sup></td><td>21.00</td><td>22440</td><td>128.00</td><td>505.58 ± 141.39</td><td>126</td><td>790</td><td>21.02</td><td>94</td></tr><tr><td>(16)</td><td>16</td><td>2<sup>31</sup></td><td>21.00</td><td>22440</td><td>181.02</td><td>1028.42 ± 176.56</td><td>659</td><td>1472</td><td>20.99</td><td>100</td></tr><tr><td>6</td><td>(18)</td><td>4</td><td>2<sup>33</sup></td><td>18.00</td><td>> 350 K</td><td>5781.29</td><td>33324.88 ± 6337.25</td><td>20921</td><td>47369</td><td>17.97</td><td>100</td></tr><tr><td>7</td><td>(18')</td><td>8</td><td>2<sup>33</sup></td><td>18.00</td><td>> 350 K</td><td>5781.29</td><td>31647.44 ± 5694.98</td><td>19383</td><td>43991</td><td>18.05</td><td>100</td></tr></tbody></table>

Looking at Table 2 we see that two characteristics — (13) (also (13')) and (15) — have significantly lower success rates. We observe that, for these two characteristics, the probability is highly dependent on the tweak and key values — being higher than average for some combinations and zero for others. This also explains the high standard deviation in $\bar{h}_i - \eta$. Such characteristics are called conditional characteristic [BB93],

To understand this behavior, we investigate the dependency on the tweak and the key for both characteristics. For Char. (13), the dependency occurs in the third round. This part of the characteristic is depicted in Figure 10, where $T'_i$ for $i = 0, 1$ is the value of the tweak in the third round in the first and the second element of a differential pair. The sets $\mathcal{A}$ and $\mathcal{B}$ of the valid S-box transitions in $\Delta_P \to \Delta_Q$ and $\Delta_Y \to \Delta_Z$, respectively, are:

$$ \mathcal{A} = \{x : S(x + 4) + S(x) = 1\} = \{1, 3, 5, 7\} $$

$$ \mathcal{B} = \{x : S(x + 4) + S(x) = 2\} = \{10, 11, 14, 15\}. $$

Now we have the following relations

$$
\left\{
\begin{aligned}
X_i[0] &= S(P_i[0]) + (T'_i + k + c_2)[0] , & X_i[4] &= S(P_i[10]) + (T'_i + k + c_2)[10] , \\
X_i[8] &= S(P_i[5]) + (T'_i + k + c_2)[5] , & X_i[12] &= S(P_i[15]) + (T'_i + k + c_2)[15] , \\
Y_i[0] &= \rho(X_i[4]) + \rho^2(X_i[8]) + \rho(X_i[12]) \\
&= \rho^2((T'_i + k + c_2)[5]) + \rho((T'_i + k + c_2)[10]) + \rho((T'_i + k + c_2)[15]) + \\
&\qquad + \rho^2(S(P_i[5])) + \rho(S(P_i[10])) + \rho(S(P_i[15])) , \\
Y_i[8] &= \rho^2(X_i[0]) + \rho(X_i[4]) + \rho(X_i[12]) \\
&= \rho^2((T'_i + k + c_2)[0]) + \rho((T'_i + k + c_2)[10]) + \rho((T'_i + k + c_2)[15]) + \\
&\qquad + \rho^2(S(P_i[0])) + \rho(S(P_i[10])) + \rho(S(P_i[15])) .
\end{aligned}
\right.
$$

To get a valid transition through the part of the characteristic depicted in Figure 10,
<figure><img src="image_15.png" /><figcaption>Figure 10: Example of tweak dependency (from (13)).</figcaption></figure>

the following four conditions must be satisfied

$$P_i[0], P_i[5] \in \mathcal{A} \text{ and } Y_i[0], Y_i[8] \in \mathcal{B}.$$

This implies $\rho^2((T'_i + k + c_2)[5]) + \rho^2((T'_i + k + c_2)[0]) \in \{0, 1, 4, 5\}$, or, equivalently $(T'_i + k + c_2)[5] + (T'_i + k + c_2)[0] \in \{0, 1, 4, 5\}$. We get two linearly independent binary relations on a few bits of the tweak and the key:

$$\begin{cases} (T'_i + k + c_2)[5][1] + (T'_i + k + c_2)[0][1] = 0 \\ (T'_i + k + c_2)[5][3] + (T'_i + k + c_2)[0][3] = 0. \end{cases}$$

However, the relations given above are on the third round tweaks $T'_i$. Inverting the tweak schedule, we obtain these two relations over the input tweaks $T_i$:

$$\left\{ \begin{array}{l} B_0 := T_i[2][2] + T_i[5][2] = (k+c_2)[0][1] + (k+c_2)[5][1] \\ B_1 := T_i[2][0] + T_i[2][1] + T_i[5][0] + T_i[5][1] = (k+c_2)[0][3] + (k+c_2)[5][3]. \end{array} \right. \qquad (7)$$

Since Cells 2 and 5 of the tweak are inactive, Relations (7) do not depend on $i$. For an attack to be feasible, the l.h.s. expressions in the tweak bits in Relations (7) must take specific values $B_0$ and $B_1$, which are determined by the key. This means that only 25% of tweaks can be used to recover a given key, and a given tweak pair can aid in recovering only 25% of all keys. However, when the conditions are met, the distinguisher probability increases fourfold to approximately $2^{-10}$. Our experimental results in Table 2 confirm this.

**Remark 4.1.** (i) The structures can be easily constructed such that the pairs are evenly split into four subsets according to the four values of $(B_0, B_1)$. Since only one subsets allows to counter of the correct key to stand out, testing the subset in succession reduces the average complexity by 37.5% versus the worst case. If multiple structures are used, then a quarter each of the structures will have a different value of $(B_0, B_1)$. If a single partial structure was meant to be used had the characteristic not been conditional, then four partial structures should be used instead, each one having half-structures of half-size.

(ii) Furthermore, this construction of the structures still allows the counter of the correct key to stand out also when all pairs are considered and all their suggestions counted.

Remark 4.1.(ii) is crucial for the multiple differential attack for $z = 4$ (Section 5.3.1). In addition to Char. (13'), 43 more characteristics are used, displayed in Figures 12 and 13. Their statistical properties are collected in Appendix A. They are all conditional characteristics, with the conditions all using the same expressions $B_i$ as defined in (7), but with different parities $(B_0, B_1) = (d_0, d_1) \in \mathbb{F}_2 \times \mathbb{F}_2$, as in

$$\left\{ \begin{array}{l} B_0 := T_i[2][2] + T_i[5][2] = (k+c_2)[0][1] + (k+c_2)[5][1] + d_0 \\ B_1 := T_i[2][0] + T_i[2][1] + T_i[5][0] + T_i[5][1] = (k+c_2)[0][3] + (k+c_2)[5][3] + d_1. \end{array} \right. \qquad (7')$$

Each characteristic is effective for only one of the four possible values $(d_0, d_1)$ can take and, for a fixed key, all four possible values are taken by the characteristics. This implies that,
for the attack to succeed, the pairs must be equally distributed among the four subsets characterised by $(d_0, d_1)$.

Similarly, we establish that Char. (15) is also conditional, the dependency

$$ \sum_{j \in \{0,2,3\}} (T_i[3] + T_i[15])[j] = 1 + \sum_{j=0}^{3} ((k + c_2)[7] + (k + c_2)[8])[j] \quad (8) $$

being independent from $i$ since $\Delta_T[3] = \Delta_T[15] = 0$. When this condition is met, the probability is $2^{-17}$, otherwise it is 0. This has been experimentally verified, cf. Table 2.

Finally, we observe that some experiments for Equation (16) do not show a significantly strong signal. We could not identify any tweak or key dependency, and the absence of such a dependency is supported by the low standard deviation of $\bar{h}_i - \eta$. While some experiments had $\bar{h}_i - \eta$ lower than $(N \cdot 2^{-q})/2$ due to our choice of $N$, increasing $N$ to $2^{31}$ from $2^{30}$ yields a success rate of 100. In contrast, for Chars. (13) and (15), increasing the data amount does not improve success rates because of the tweak dependencies discussed above.

# 5 Cryptanalysis of the PAC Function in FEAT_PACQARMA3

We now describe the cryptanalysis of the PAC function for $z = 2$ through 8, with $z = v$, in full detail. Table 3 summarizes all attacks. For most characteristics we perform a 0.5R key recovery, followed by peeling to recover second round equivalent key cells $k' = M(\tau(k))$, guessing additional $k + w$ bits as needed. This is repeated for every characteristic in an attack, and any remaining bits are recovered through brute force. For $z = 2$ and 3, we also perform a 1.5R recovery, while for $z = 4$ we also mount a multiple differential attack.

## 5.1 Attack for $z = 2$ (56-bit Pointers)

Let us consider first the case of $z = 2$, i.e., the two most significant cells of the input are clamped, and only the two most significant cells of the output are revealed.

We first use Char. (9), with $p = 16$ and $d_{in} = 28$, in a 0.5R key recovery step, to recover the 28 bits $(k + w)[\{4, 6, 7, 8, 11, 13, 14\}]$. Clustering analysis (cf., Section 4.5 and experimental verification results in Table 2) show that the probability of the differential distinguisher is $2^{-7.98}$, i.e., $q = 7.98$.

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

We follow the Poisson distribution argument from Section 3.5 to determine how many pairs satisfying the input difference $\Delta_{in}$ are required in a key recovery step on Char. (9). As we can observe exactly two output cells, a random pair passes the sieving test with probability $2^{-8}$. We have $2^{28}$ possible round key. With $N$ pairs, the counters of the wrong keys follow Poisson($N \cdot 2^{-8}$) distribution. The counter for the correct key follows Poisson($N \cdot (2^{-8} + 2^{-7.98})$) distribution as $N \cdot 2^{-8}$ of the pairs pass the filter by random chance, and $N \cdot 2^{-7.98}$ are right pairs satisfying the characteristics. We find that the
<caption>**Table 3:** Summary of key recovery attacks on the PAC function for $2 \le z \le 8$.</caption>

For each characteristic, initial key cell recovery and peeling steps are separated by semi-colons. “M” denotes the only M-profile attack, which is for $z = 8$. The success probability of each complete attack is at least 90%.

<table><thead><tr><th>z</th><th>Char.</th><th>d<sub>in</sub></th><th>p</th><th>q</th><th>log<sub>2</sub>D</th><th>log<sub>2</sub>T</th><th>Recovered Round Key Cells</th></tr></thead><tbody><tr><td rowspan="5">2</td><td>(9)</td><td>28</td><td>16</td><td>7.98</td><td>22</td><td>35</td><td>(k + w)[{4, 6, 7, 8, 11, 13, 14}] &cup; (k + w)[{1, 2} &cup; k'[{5, 15}].</td></tr><tr><td>(10)</td><td>16</td><td>19</td><td>10.01</td><td>18</td><td>26</td><td>(k + w)[{3, 9, 12}]; k'[{6, 10}].</td></tr><tr><td>(11)</td><td>28</td><td>22</td><td>12.00</td><td>24.5</td><td>39</td><td>k'[2].</td></tr><tr><td>Exhaustive Search</td><td></td><td></td><td></td><td>60</td><td></td><td>(k + w)[{0, 5, 10, 15}] &cup; k'[{0, 1, 3, 4, 7, 8, 9, 11 &minus; 14}].</td></tr><tr><td>Overall Complexity<br>Without using (11)</td><td></td><td></td><td></td><td>25<br>22.2</td><td>60<br>64</td><td></td></tr><tr><td rowspan="5">3</td><td>(11')</td><td>28</td><td>22</td><td>12.01</td><td>24</td><td>35</td><td>(k + w)[{3, 4, 7, 9, 11, 12, 14}], k'[{2, 5}].</td></tr><tr><td>(13)</td><td>40</td><td>24</td><td>12.00</td><td>24.5</td><td>38</td><td>(k + w)[{5, 6, 8, 10, 13, 15}]; k'[{0, 6}]; (k + w)[2] &cup; k'[7].</td></tr><tr><td>Exhaustive Search</td><td></td><td></td><td></td><td>52</td><td></td><td>(k + w)[{0, 1}] &cup; k'[{1, 3, 4, 8 &minus; 15}].</td></tr><tr><td>Overall Complexity</td><td></td><td></td><td></td><td>25.3</td><td>52</td><td></td></tr><tr><td>(13')</td><td></td><td></td><td></td><td>12.00</td><td></td><td>(k + w)[{4, 5, 6, 8 &minus; 11, 13, 14, 15}];</td></tr><tr><td rowspan="5">4</td><td>Fig. 12</td><td>40</td><td>24</td><td>13.00</td><td>28</td><td>54.5</td><td>(k + w)[0] &cup; k'[0, 5]; (k + w)[3] &cup; k'[6]; (k + w)[2] &cup; k'[7].</td></tr><tr><td>Fig. 13</td><td></td><td></td><td>14.00</td><td></td><td></td><td>(k + w)[{1, 7, 12}] &cup; k'[{1, 2, 3, 4, 8 &minus; 15}].</td></tr><tr><td>Exhaustive Search</td><td></td><td></td><td></td><td>60</td><td></td><td></td></tr><tr><td>Overall Complexity</td><td></td><td></td><td></td><td>28</td><td>60</td><td></td></tr><tr><td>(15)</td><td>24</td><td>26</td><td>18.00</td><td>30</td><td>41</td><td>(k + w)[{5, 7, 8, 10, 13, 15}]; (k + w)[0] &cup; k'[{4, 8}]; (k + w)[2] &cup; k'[{3, 7}].</td></tr><tr><td rowspan="5">5</td><td>(16)</td><td>16</td><td>25</td><td>20.80</td><td>30.35</td><td>31</td><td>(k + w)[{9, 14}]; k'[12].</td></tr><tr><td>Exhaustive Search</td><td></td><td></td><td></td><td>68</td><td></td><td>(k + w)[{1, 3, 4, 6, 11, 12}] &cup; k'[{0, 1, 2, 5, 6, 9, 10, 11, 13, 14, 15}].</td></tr><tr><td>Overall Complexity</td><td></td><td></td><td></td><td>31.19</td><td>68</td><td></td></tr><tr><td>(18)</td><td>20</td><td>30</td><td>18.00</td><td>37.50</td><td>54</td><td>(k + w)[{10, 12, 13, 15}]; (k + w)[{0, 5}] &cup; k'[{4, 12}]; (k + w)[{2, 7, 8}] &cup; k'[{3, 7}].</td></tr><tr><td>Exhaustive Search</td><td></td><td></td><td></td><td>76</td><td></td><td>(k + w)[{1, 3, 4, 6, 9, 11, 14}] &cup; k'[{0, 1, 2, 5 &minus; 10, 13, 14, 15}].</td></tr><tr><td>(18')</td><td>20</td><td>30</td><td>18.00</td><td>33.70</td><td>46</td><td>Same as for z = 6, Char. (18).</td></tr><tr><td rowspan="5">7</td><td>Exhaustive Search</td><td></td><td></td><td></td><td>76</td><td></td><td>Same as for z = 6.</td></tr><tr><td>Overall Complexity</td><td></td><td></td><td></td><td>33.70</td><td>76</td><td></td></tr><tr><td>(19)</td><td>12</td><td>38</td><td>29.00</td><td>42</td><td>43</td><td>(k + w)[{9, 11, 13}]; (k + w)[{2, 7, 8}] &cup; k'[3]; (k + w)[{1, 4, 14}] &cup; k'[{5, 9, 13}].</td></tr><tr><td>Exhaustive Search</td><td></td><td></td><td></td><td>76</td><td></td><td>(k + w)[{0, 3, 5, 6, 10, 12, 15}] &cup; k'[{0, 1, 2, 4, 6, 7, 8, 10, 11, 12, 14, 15}].</td></tr><tr><td>Overall Complexity</td><td></td><td></td><td></td><td>42</td><td>76</td><td></td></tr><tr><td rowspan="5">M</td><td>(19)</td><td>12</td><td>38</td><td>26.00</td><td>45</td><td>46.33</td><td>Same as for z = 8 (A-profile), Char. (19).</td></tr><tr><td>Exhaustive Search</td><td></td><td></td><td></td><td>76</td><td></td><td>Same as for z = 8 (A-profile), Char. (19).</td></tr><tr><td>Overall Complexity</td><td></td><td></td><td></td><td>45</td><td>76</td><td></td></tr></tbody></table>
difference between the means must be at least $\gamma = 7$ times the standard deviation of the counter values associated with wrong keys, and that we need (at least) $N = 2^{14}$ pairs satisfying the input difference $\Delta_{in}$, to achieve a success rate of 99%. A partial structure of $2^{21}$ values out of $2^{28}$ for each of the two half-structures generates an expected $2^{14}$ such pairs, and the total data complexity is $2^{22}$ chosen plaintexts.

So far we have recovered the 28 key bits $(k+w)[\{4, 6, 7, 8, 11, 13, 14\}]$. We can recover more cells using the same sieved pairs from the previous step by peeling the first half round. To recover $k'[\{5, 15\}]$, we additionally need to guess $(k+w)[\{1, 2\}]$. Thus, we iterate again through all sieved pairs from the first step. This time, for each sieved pair that suggested the correct value of the 28 key bits, we guess $(k+w)[\{1, 2\}]$ and compute the values of $(Y_0[5], Y_1[5])$ and $(Y_0[15], Y_1[15])$ (i.e., the cell values before the second S-box layer according to the notation given in Figure 7). By enforcing the transitions $2 \mapsto 9$ and $7 \mapsto 3$, we obtain candidates for $k'[\{5, 15\}]$, and for each of them we tick the counter corresponding to $(k+w)[\{1, 2\}] \cup k'[\{5, 15\}]$.

After pair sieving, we are left with $L \approx 2^{14} \cdot (2^{28}-8 + 2^{-7.98}) = 2^{34}$ candidate pairs on average, as per Equation (5). For each such pair we perform a guess-and-filter step and of the peeling step, whose costs are bounded by the cost of a single QARMA encryption. So, the time complexity of this key recovery step is $\approx 2 \cdot 2^{34} = 2^{35} T_{\delta}$.

We then use Char. (10) below, which has $p = 19$, $d_{in} = 16$ to recover the 12 key bits $(k+w)[\{3, 9, 12\}]$. For this characteristic, clustering analysis yields $q = 10.01$.

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

Reasoning as before, we need $2^{17}$ pairs with input difference $\Delta_{in}$, and $\gamma = 5$, for a 95% success rate. We use two structures, each providing $2^{16}$ such pairs out of $2^{32}$ total pairs, for a data complexity of $2^{18}$. We then peel another round to recover $k'[\{6, 10\}]$, using the known $(k+w)[6]$ from earlier. This key recovery step has time complexity $2^{26} T_{\delta}$.

Next, we use Char. (11) below, with $p = 22$, $d_{in} = 28$ and $q = 12.01$, to recover $k'[2]$ in a 1.5R attack, with the knowledge of previously recovered key bits $(k+w)[\{3, 9, 12\}]$:

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

Since there are only 16 possible key values, we have $\nu = 4$ in (4). A Poisson distribution argument shows that $\gamma = 2.8$ is sufficient to achieve a success rate of 96%, using $2^{19}$ pairs with input difference $\Delta_{in}$. To generate these $2^{19}$ pairs we use a partial structure of $2^{23.5}$ values out of $2^{28}$ per each half-structure, resulting in a data complexity of $2^{24.5}$. The time complexity of this key recovery step is $2^{39} T_{\delta}$.
Lastly, we brute force the 60 remaining bits. The entire attack is graphically represented in Equation (12), where each cell of $(k+w)$ and $k'$ is labeled with the number of the characteristic used to recover it or with $b$ to indicate that its value is brute forced:

$$ (k+w) \leftarrow \begin{bmatrix} b & (9) & (9) & (10) \\ (9) & b & (9) & (9) \\ (9) & (10) & b & (9) \\ (10) & (9) & (9) & b \end{bmatrix} \quad \text{and} \quad k' \leftarrow \begin{bmatrix} b & b & (11) & b \\ b & (9) & (10) & b \\ b & b & (10) & b \\ b & b & b & (9) \end{bmatrix}. \quad (12) $$

The total data complexity of the attack is $\approx 2^{25}$ and the time complexity is dominated by the brute force step, i.e., $2^{60} T_{\delta}$. The success probability is $99\% \cdot 95\% \cdot 96\% = 90\%$.

**Remark 5.1.** Without using Char. (11), one can still obtain a valid attack with data complexity of $2^{22.2}$ and time complexity of $T = 2^{64}$ encryptions.

## 5.2 Attack for $z = 3$ (52-bit Pointers)

We adapt Char. (11) by clamping one additional plaintext cell and making one more ciphertext cell visible. This is possible since the first three plaintext cells of Char. (11) are zero differences. The resulting Char. (11') has parameters $p = 22$, $d_{in} = 28$ and $q = 12$.

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

We use it to recover $(k+w)[\{3, 4, 7, 9, 11, 12, 14\}]$ and $k'[\{2, 5\}]$. By means of a Poisson distribution argument, we find that $2^{18}$ pairs satisfying the input difference $\Delta_{in}$ are required with $\gamma = 8$ to obtain a success rate of 99%. These pairs can be generated using a partial structure of $2^{23}$ values out of $2^{28}$ for each half-structure, for a data complexity of $2^{24}$. The overall time complexity of this key recovery step is $2^{35} T_{\delta}$.

To recover $(k+w)[\{5, 6, 8, 10, 13, 15\}]$ we consider Char. (13) with $p = 24$.

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

We can establish that $q \le 12$ and that in fact $q$ is very close to 12 as follows: First, we note that Char. (13) has a zero difference at its center. It is easy to prove that a zero difference at the center and $\Delta_T$ being active only in Cells 14 and 15 force the first two cells of $D_{out}$ to be zero (cf. Figure 11). In other words, the transition probability from center to $\hat{D}_{out}$ is 1. The path from $\Delta_{in}$ to the center is uniquely determined and has probability $2^{-12}$. Hence, all characteristics matching the forward path up to the center have a cumulative
<figure><img src="image_21.png" /><figcaption>Figure 11: Diffusion from the center to the output in Char. (13) and similar ones.</figcaption></figure>

probability of $2^{-12}$. They belong to the cluster for Char. (13) and, while characteristics with non-zero center exist, we expect their contribution to be negligible. This is confirmed in the experiments reported in Section 4.6 (see Table 2), where we obtained $\bar{q} = -12.00$. For comparison, a clustering search only reached $q = 12.78$ in a week (during which it found 613768 characteristics), before we interrupted it.

By the Poisson distribution argument, we find that about $N = 2^{21}$ pairs satisfying $\Delta_{in}$ are needed, with $\gamma = 6$, for a success rate over 97%. However, since this characteristic has 10 active cells in $D_{in}$, using it naively results in a data complexity of at least $2^{31}$. To reduce the latter, we leverage the fact that the 16 key bits $(k+w)[\{4, 9, 11, 14\}]$ have already been recovered using Char. (11'). With a negligible computation overhead, we can determine fixed differences at these positions in $\Delta_{in}$ such that, by varying the remaining 24 bits within a single structure, we generate plaintext pairs where one in $2^{24}$ satisfies the input difference $\Delta_{in}$, instead of one in $2^{40}$. (A similar approach was used in [BDD$^+$23].)

Now, Char. (13) is conditional (cf. Section 4.6). To use it, we partition the $N = 2^{21}$ pairs satisfying $\Delta_{in}$ into four equal sets with the tweak bit expressions in Relations (7) taking a different value for each set. Instead of using a single partial structure with $2^{22.5}$ values out of $2^{24}$ for each half-structure, we build four partial structures with $2^{21.5}$ values for each half-structure, each structure generating $2^{19}$ pairs. The data complexity is $2^{24.5}$.

After the recovery of the 24 first round key bits, we perform peeling again to recover $k'[\{0, 6\}]$ using the transitions $4 \mapsto 1$ and $2 \mapsto 4$ through the S-Boxes on Cells 0 and 6. Last, we recover $k'[7]$ by guessing $(k+w)[2]$ and using the transition $1 \mapsto 4$. The overall time complexity of this key recovery step is $2^{39.5} T_{\delta}$.

We brute force the remaining 13 cells. The complexity of the brute force step, $2^{52} T_{\delta}$, dominates the time complexity. The total data complexity is $2^{25.3}$ chosen plaintexts, and the success rate is over 96%. The complete attack is represented in Equation (14):

$$ (k+w) \leftarrow \begin{bmatrix} b & b & (13) & (11') \\ (11') & (13) & (13) & (11') \\ (13) & (11') & (13) & (11') \\ (11') & (13) & (11') & (13) \end{bmatrix} \quad \text{and} \quad k' \leftarrow \begin{bmatrix} (13) & b & (11') & b \\ b & (11') & (13) & (13) \\ b & b & b & b \\ b & b & b & b \end{bmatrix}. \quad (14) $$

## 5.3 Attack for $z = 4$ (48-bit Pointers)

From this point onwards, if the recovery process is similar to previous cases, we provide only the used characteristics, key bits, and complexities.
We reuse Char. (13) with an additional clamped cell, as Char. (13') below.

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

It has $p = 24$ and $q \le 12$ (by the same argument as in the previous attack). Here, we aim to recover first the 40 key bits $(w+k)[\{4, 5, 6, 8, 9, 10, 11, 13, 14, 15\}]$, and then $(w+k)[0] \cup k'[0,5]$, $(w+k)[3] \cup k'[6]$, and $(w+k)[2] \cup k'[7]$ by peeling. We need $\gamma = 5.77$ to achieve a success rate of at least 90%, using $2^{21}$ pairs with input difference $\Delta_{in}$. Similarly to what we have done in the case $z = 3$, we generate these pairs by using four partial structures, each with $2^{29.5}$ values out of $2^{40}$ of each half-structure, for a total data complexity of $2^{32.5}$. The time complexity is $2^{54} T_{\delta}$. We brute force the remaining 60 bits.

### 5.3.1 A Multiple Differential for $z = 4$

While the attack for $z = 4$ described above works, it exceeds our target limit of $2^{30}$ for the data complexity. To improve the latter, we propose a multiple differential attack [Knu94] for $z = 4$ using Char. (13') together with similar ones. We start by searching for additional characteristics of lowest weight such that:

1. The have the same 10 cells active in $\Delta_{in}$ as (13');

2. The have the same tweak difference;

3. The differences after the first S-Box layer of all characteristics are pairwise distinct;

4. The difference after the second S-Box layer is always equal to that in (13'); and

5. The first two cells at the ciphertext output have zero differences.

The third requirement prevents counting some characteristics multiple times when clustering each characteristic, and then building the multiple differential.

We can find 12 such characteristics with $p = 25$ and $31$ with $p = 26$. The characteristics with $p = 25$, resp., $p = 26$, are given in Figure 12, resp., Figure 13. It suffices to show the beginning of their non-truncated section, as the rest is similar to Char. (13').

For all the characteristics with $p = 25$, resp., $p = 26$, the probability of the differential from the input to the center (with a zero difference) is at least $2^{-13}$, resp., $2^{-14}$. This holds because the argument used for Char. (13) regarding the backward path having probability 1 clearly applies to all 44 characteristics. Furthermore, we have experimentally verified all the characteristics using the approach described in Section 4.6. For all the characteristics with $p = 25$, resp., $p = 26$, the experimental probability of the differential is approximately $2^{-12.9}$, resp., $2^{-13.7}$, which confirms the claim.

We combine these 44 characteristics in a multiple differential attack to recover the 40 key bits $(w+k)[\{4, 5, 6, 8, 9, 10, 11, 13, 14, 15\}]$. The counter associated with a key guess is a 44-dimensional vector with the coordinates corresponding to the 44 differentials. We assume that the coordinates are independent. Here we are interested in the distribution of the sum of these 44 values in each counter. Let us consider $N$ pairs, each one satisfying one of the 44 input differences in $\Delta_{in}$. Then, for each wrong key, the distribution of the counters
<figure><img src="image_23.png" /><figcaption>Figure 12: Start of the 12 characteristics with $p = 25$.</figcaption></figure>

follows Poisson($N \cdot 44 \cdot 2^{-8}$), and for the correct key, it follows Poisson($N \cdot (2^{-8 \cdot 12} + 44 \cdot 2^{-8})$) where $2^{-8 \cdot 12} = 2^{-12} + 12 \cdot 2^{-13} + 31 \cdot 2^{-14}$. By the Poisson distribution argument, we need $\gamma = 8.12$ to achieve a success probability higher than 90%, corresponding to $N = 2^{19.5}$.

To take into account the fact that all 44 characteristics are conditional, we use four partial structures. In each structure, the tweak bits involved in Relations (7) satisfy a different value of $(B_0, B_1) \in F_2 \times \mathbb{F}_2$, and we pick $2^{26}$ values from each half-structure (out of $2^{40}$), which allows it to generate $2^{17.5}$ pairs satisfying $\Delta_{in}$. The data complexity is $2^{29}$.

After that, we perform three peeling steps to recover, in order, $(w+k)[0] \cup k'[0,5]$, $(w+k)[3] \cup k'[6]$, and $(w+k)[2] \cup k'[7]$. Here we make use of the fact that the difference after the second S-box layer is the same in all 44 characteristics. Thus, we can use the same data we have collected previously. The time complexity of this key recovery step is $4 \cdot 44 \cdot 2^{47} T_{\delta} \approx 2^{54.5} T_{\delta}$. We recover the remaining 60 bits by brute force.

## 5.4 Attack for $z = 5$ (44-bit Pointers)

First, we use Char. (15) with $p = 26$ and $d_{in} = 24$. Clustering analysis gives here $q = 18$. Using it, we recover $(k+w)[\{5, 7, 8, 10, 13, 15\}]$. We need $2^{29}$ pairs with input difference $\Delta_{in}$ and $\gamma = 5.8$ to achieve a 94% success rate. The attack requires data complexity $2^{30}$ (using 32 structures) and time complexity $2^{41} T_{\delta}$. As shown in Section 4.6, this characteristic is conditional with a single bit condition. We therefore split the 32 structures equally between tweaks where the expression in Equation (8) equals 0 and 1.

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

Then, using Char. (16), with $p = 25$, $d_{in} = 16$ and $q = 21.00$, we recover $(k+w)[\{9, 14\}]$,
<figure><img src="image_25.png" /><figcaption>Figure 13: Start of the the 31 characteristics with $p = 26$.</figcaption></figure>

and $k'[12]$. The data complexity of this key recovery step, with $\gamma = 3.4$, is $2^{30.53}$ and the
time complexity is $2^{31.11} T_\delta$ for a success rate of 91%.

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

Incidentally, Char. (16) is found quickly by minimizing the cost function $p + d_{in}/2$.

Brute forcing the remaining 68 bits dominates the time complexity. The total data complexity is $2^{31.19}$. The entire attack is summarized as follows:

$$ (k+w) \leftarrow \begin{bmatrix} (15) & b & (15) & b \\ b & (15) & b & (15) \\ (15) & (16) & (15) & b \\ b & (15) & (16) & (15) \end{bmatrix} \quad \text{and} \quad k' \leftarrow \begin{bmatrix} b & b & b & (15) \\ (15) & b & b & (15) \\ (15) & b & b & b \\ (16) & b & b & b \end{bmatrix}. \quad (17) $$

## 5.5 Attack for $z = 6$ (40-bit Pointers)

Consider Char. (18), with $p = 30$, $d_{in} = 20$ and clustering yields $q = 18$. We use it to recover $(k+w)[\{8, 10, 12, 13, 15\}]$, then $(k+w)[\{0, 5\}] \cup k'[\{4, 12\}]$, and finally $(k+w)[\{2, 7\}] \cup k'[\{3, 7\}]$ by successive peeling. The data complexity of this step is $2^{37.50}$, since $2^{36.50}$ pairs that satisfy the input difference $\Delta_{in}$ are required, with $\gamma = 5$, to achieve a success rate of 92%. The time complexity of this step is approximately $2^{54} T_\delta$.

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

We brute force the remaining 76 bits.

## 5.6 Attack for $z = 7$ (36-bit Pointers)

This attack is similar to the previous one. Clustering on Char. (18') yields $q = 18$, i.e., the same as Char. (18). This can be explained by the easily proved fact that Cell 3 of the ciphertext output has a zero difference if and only if Cell 6 has a zero difference. We recover first $(k+w)[\{8, 10, 12, 13, 15\}]$ and then, by peeling, $(k+w)[\{0, 5\}] \cup k'[\{4, 12\}]$, and $(k+w)[\{2, 7\}] \cup k'[\{3, 7\}]$. Approximately $2^{32.7}$ pairs are required that satisfy the input difference $\Delta_{in}$, considering $\gamma = 5.2$, to achieve a success rate of 90%. The data
complexity of this step is $2^{33.7}$, and its time complexity is approximately $2^{46} T_δ$.

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

We brute force the remaining 76 bits.

## 5.7 The case of $z = 8$ (32-bit Pointers)

The best attack we found uses the following characteristic, with $p = 38$:

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

This characteristic has been found by searching for characteristics with the smallest $p$, for various values of the number of active cells of $D_{in}$.

For the A-profile variant, we reach $q = 29$ by clustering, using 1512 characteristics. We reach a success rate of 90% in an attack requiring $2^{42}$ pairs satisfying $\Delta_{in}$, with $\gamma = 4.2$. The data complexity is $2^{43}$. We first recover $(k+w)[\{9, 11, 13\}]$. By peeling, we recover $k'[3]$ guessing $(k+w)[\{2, 7, 8\}]$, and recover $k'[\{5, 9, 13\}]$ guessing $(k+w)[\{1, 4, 14\}]$. The time complexity is $2^{43} T_δ$, mostly data collection (guess-and-filter costs about $2^{34} T_δ$).

For the M-profile variant, clustering returns exactly $q = 26$ with a total of 286272 characteristics. Taking $\gamma = 4$, we obtain an attack requiring $2^{44}$ pairs satisfying the input differential, for a data complexity of $2^{45}$ and a success rate of 90%. The time complexity of guess-and-filter is $2^{44} T_δ$ for each of initial key recovery, two peeling steps, i.e. $2^{45.6}$, and including data collection we reach $2^{45} + 2^{45.6} = 2^{46.33}$.

We recover the same 13 round key cells for both versions and brute force 76 bits.

Because of the data requirements, both versions can be considered secure. However, the running time is lower than $2^{80} T_δ$ and the time/data product smaller than $2^{128}$.

# 6 Conclusions

We have analysed the security of the clamped and chopped version of QARMA$_3$ used in FEAT_PACQARMA3. We found that while the versions with $z = 8$ are secure, and those with $z = 6$ and 7 provide adequate security, the cryptographic strength of variants more typical in commodity devices ($z = 3, 4$, and 5) falls short of expectations.

In all cases, computational and memory requirements are non-trivial, and ongoing attacks could be detected by system-level anti-malware monitoring. Additionally, certain practical constraints complicate real-world attacks:
1. Code pointers on architectures with fixed size, 32-bit long instructions always have their two least significant bits equal to zero.

2. The activeness patterns of plaintext and tweak are very different in our characteristics, in contrast with the fact that they usually are pointers from close memory regions.

3. Bit 56 of the output is omitted and, if the *Memory Tagging Extension* (MTE) [Arm24] is enabled, the reserved bits of the pointer are shared between MTE and PAC.

Despite these constraints, security margins remain thinner than ideal. To hedge against potential advancements in cryptanalysis, we recommend to deploy QARMA$_5$ or QARMAv2$_4$ on high-performance, out-of-order cores, restricting the use of QARMA$_3$ to small 32-bit cores.

## Acknowledgments

Part of this research was conducted while the first author was employed at Arm. The second and third authors express their gratitude to Arm for their support. The recommendations in this paper are the opinion of the authors only and do not necessarily represent the view of any former or present employer.

## References

[AB12] Jean-Philippe Aumasson and Daniel J. Bernstein. Siphash: A fast short-input PRF. In Steven D. Galbraith and Mridul Nandi, editors, *Progress in Cryptology — INDOCRYPT 2012, 13th International Conference on Cryptology in India, Kolkata, India, December 9-12, 2012. Proceedings*, volume 7668 of LNCS, pages 489–508. Springer, 2012.

[ABD17] Tomer Ashur, Daniël Bodden, and Orr Dunkelman. Linear cryptanalysis using low-bias linear approximations. *IACR Cryptol. ePrint Arch.*, page 204, 2017.

[ABD+23] Roberto Avanzi, Subhadeep Banik, Orr Dunkelman, Maria Eichlseder, Shibam Ghosh, Marcel Nageler, and Francesco Regazzoni. The QARMAv2 family of tweakable block ciphers. *IACR Transactions on Symmetric Cryptology*, 3:25–73, 9 2023.

[ABR20] Tomer Ashur, Tim Beyne, and Vincent Rijmen. Revisiting the wrong-key-randomization hypothesis. *J. Cryptol.*, 33(2):567–594, 2020.

[ADG+19] Ralph Ankele, Christoph Dobraunig, Jian Guo, Eran Lambooi, Gregor Leander, and Yosuke Todo. Zero-Correlation attacks on tweakable block ciphers with linear tweakey expansion. *IACR Trans. Symmetric Cryptol.*, 2019(1):192–235, 2019.

[App24] Apple Inc. Operating system integrity: Pointer Authentication Codes, 2024.

[Arm16] Arm. ARM Connected blog. ARMv8-A architecture — 2016 additions. https://community.arm.com/arm-community-blogs/b/architectures-and-processors-blog/posts/armv8-a-architecture-2016-additions, 10 2016.

[Arm23] Arm. Arm Architecture Reference Manual for M-profile architecture, 2023.

[Arm24] Arm. Arm Architecture Reference Manual for A-profile architecture, 2024.
[Ava17] Roberto 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 Trans. Symmetric Cryptol.*, 2017(1):4–44, 2017.

[AVL62] Georgy Maximovich Adelson-Velsky and Evgeny Mikhailovich Landis. An algorithm for the organization of information. *Soviet Mathematics Doklady*, 3:1259–1263, 1962.

[Bay72] Rudolf Bayer. Symmetric binary b-trees: Data structure and maintenance algorithms. *Acta Informatica*, 1:290–306, 1972.

[BB93] Ishai Ben-Aroya and Eli Biham. Differential cryptanalysis of lucifer. In Douglas R. Stinson, editor, *Advances in Cryptology - CRYPTO '93, 13th Annual International Cryptology Conference, Santa Barbara, California, USA, August 22-26, 1993, Proceedings*, volume 773 of *Lecture Notes in Computer Science*, pages 187–199. Springer, 1993.

[BBI<sup>+</sup>15] Subhadeep Banik, Andrey Bogdanov, Takanori Isobe, Kyoji Shibutani, Harunaga Hiwatari, Toru Akishita, and Francesco Regazzoni. Midori: A Block Cipher for Low Energy. In Tetsu Iwata and Jung Hee Cheon, editors, *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*, volume 9453 of LNCS, pages 411–436. Springer, 2015.

[BCG<sup>+</sup>12] Julia Borghoff, Anne Canteaut, Tim Güneysu, Elif Bilge Kavun, Miroslav Knezevic, Lars R. Knudsen, Gregor Leander, Ventzislav Nikov, Christof Paar, Christian Rechberger, Peter Rombouts, Søren S. Thomsen, and Tolga Yalçın. PRINCE — A low-latency block cipher for pervasive computing applications — extended abstract. In Xiaoyun Wang and Kazue Sako, editors, *Advances in Cryptology — ASIACRYPT 2012 — 18th International Conference on the Theory and Application of Cryptology and Information Security, Beijing, China, December 2-6, 2012. Proceedings*, volume 7658 of Lecture Notes in Computer Science, pages 208–225. Springer, 2012.

[BDD<sup>+</sup>23] Christina Boura, Nicolas David, Patrick Derbez, Gregor Leander, and María Naya-Plasencia. Differential meet-in-the-middle cryptanalysis. In Helena Handschuh and Anna Lysyanskaya, editors, *Advances in Cryptology - CRYPTO 2023 - 43rd Annual International Cryptology Conference, CRYPTO 2023, Santa Barbara, CA, USA, August 20-24, 2023, Proceedings, Part III*, volume 14083 of Lecture Notes in Computer Science, pages 240–272. Springer, 2023.

[Bel73] James R. Bell. Threaded code. Commun. ACM, 16(6):370–372, 6 1973.

[BJK<sup>+</sup>16] Christof Beierle, Jérémy Jean, Stefan Kölbl, Gregor Leander, Amir Moradi, Thomas Peyrin, Yu Sasaki, Pascal Sasdrich, and Siang Meng Sim. The SKINNY family of block ciphers and its low-latency variant MANTIS. In Matthew Robshaw and Jonathan Katz, editors, *Advances in Cryptology — CRYPTO 2016 — 36th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 14-18, 2016, Proceedings, Part II*, volume 9815 of LNCS, pages 123–153. Springer, 2016.

[BKL<sup>+</sup>07] Andrey Bogdanov, Lars R. Knudsen, Gregor Leander, Christof Paar, Axel Poschmann, Matthew J. B. Robshaw, Yannick Seurin, and C. Vikkelsoe.
PRESENT: An ultra-lightweight block cipher. In Pascal Paillier and In-
grid Verbauwhede, editors, *Cryptographic Hardware and Embedded Systems — CHES 2007, 9th International Workshop, Vienna, Austria, September 10-13, 2007, Proceedings*, volume 4727 of *Lecture Notes in Computer Science*, pages 450–466. Springer, 2007.

[Blo24] Blockchain.com. Total hash rate, 2024.

[BS90] Eli Biham and Adi Shamir. Differential cryptanalysis of des-like cryptosystems. In Alfred Menezes and Scott A. Vanstone, editors, *Advances in Cryptology - CRYPTO '90, 10th Annual International Cryptology Conference, Santa Barbara, California, USA, August 11-15, 1990, Proceedings*, volume 537 of *Lecture Notes in Computer Science*, pages 2–21. Springer, 1990.

[BS91] Eli Biham and Adi Shamir. Differential cryptanalysis of des-like cryptosystems. *J. Cryptol.*, 4(1):3–72, 1991.

[BS92] Eli Biham and Adi Shamir. Differential cryptanalysis of the full 16-round DES. In Ernest F. Brickell, editor, *Advances in Cryptology - CRYPTO '92, 12th Annual International Cryptology Conference, Santa Barbara, California, USA, August 16-20, 1992, Proceedings*, volume 740 of *Lecture Notes in Computer Science*, pages 487–496. Springer, 1992.

[BS93] Eli Biham and Adi Shamir. *Differential Cryptanalysis of the Data Encryption Standard*. Springer, 1993.

[BSS<sup>+</sup>13] Ray Beaulieu, Douglas Shors, Jason Smith, Stefan Treatman-Clark, Bryan Weeks, and Louis Wingers. The simon and speck families of lightweight block ciphers. *Cryptology ePrint Archive, Report 2013/404*, 2013.

[BT13] Andrey Bogdanov and Elmar Tischhauser. On the wrong key randomisation and key equivalence hypotheses in matsui's algorithm 2. In Shiho Moriai, editor, *Fast Software Encryption - 20th International Workshop, FSE 2013, Singapore, March 11-13, 2013. Revised Selected Papers*, volume 8424 of *Lecture Notes in Computer Science*, pages 19–38. Springer, 2013.

[CDK09] Christophe De Cannière, Orr Dunkelman, and Miroslav Knezevic. KATAN and KTANTAN - A Family of Small and Efficient Hardware-Oriented Block Ciphers. In Christophe Clavier and Kris Gaj, editors, *CHES 2009*, volume 5747 of *Lecture Notes in Computer Science*, pages 272–288. Springer, 2009.

[CDMP05] Jean-Sébastien Coron, Yevgeniy Dodis, Cécile Malinaud, and Prashant Puniya. Merkle-damgård revisited: How to construct a hash function. In Victor Shoup, editor, *Advances in Cryptology - CRYPTO 2005: 25th Annual International Cryptology Conference, Santa Barbara, California, USA, August 14-18, 2005, Proceedings*, volume 3621 of *Lecture Notes in Computer Science*, pages 430–448. Springer, 2005.

[CXTQ23] Yaxin Cui, Hong Xu, Lin Tan, and Wenfeng Qi. Sat-aided differential crypt-analysis of lightweight block ciphers midori, MANTIS and QARMA. In Ding Wang, Moti Yung, Zheli Liu, and Xiaofeng Chen, editors, *Information and Communications Security - 25th International Conference, ICICS 2023, Tianjin, China, November 18-20, 2023, Proceedings*, volume 14252 of *Lecture Notes in Computer Science*, pages 3–18. Springer, 2023.
[DEKM16] Christoph Dobraunig, Maria Eichlseder, Daniel Kales, and Florian Mendel. Practical key-recovery attack on MANTIS5. *IACR Trans. Symmetric Cryptol.*, 2016(2):248-260, 2016.

[Des97] Solar Designer. Bugtraq: Getting around non-executable stack (and fix), 8 1997.

[FBP$^{+}$16] Andreas Follner, Alexandre Bartel, Hui Peng, Yu-Chen Chang, Kyriakos K. Ispoglou, Mathias Payer, and Eric Bodden. PSHAPE: automatically combining gadgets for arbitrary method execution. In Gilles Barthe, Evangelos P. Markatos, and Pierangela Samarati, editors, *Security and Trust Management - 12th International Workshop, STM 2016, Heraklion, Crete, Greece, September 26-27, 2016, Proceedings*, volume 9871 of *Lecture Notes in Computer Science*, pages 212-228. Springer, 2016.

[Fra18] Olivia Lucca Fraser. Urschleim in Silicon: Return Oriented Programming Evolution with ROPER. Technical report, Dalhousie University, Halifax, Nova Scotia, 12 2018.

[Fri56] Edward Harry Friend. Sorting on electronic computer systems. *Journal of the Association for Computing Machinery*, 3(3):134-168, 7 1956.

[FZHJ17] Olivia Lucca Fraser, Nur Zincir-Heywood, Malcolm I. Heywood, and John T. Jacobs. Return-oriented programme evolution with ROPER: a proof of concept. In Peter A. N. Bosman, editor, *Genetic and Evolutionary Computation Conference, Berlin, Germany, July 15-19, 2017, Companion Material Proceedings*, pages 1447-1454. ACM, 2017.

[GD07] Vijay Ganesh and David L. Dill. A decision procedure for bit-vectors and arrays. In Werner Damm and Holger Hermanns, editors, *Computer Aided Verification, 19th International Conference, CAV 2007, Berlin, Germany, July 3-7, 2007, Proceedings*, volume 4590 of *Lecture Notes in Computer Science*, pages 519-531. Springer, 2007.

[GG15] Shoni Gilboa and Shay Gueron. Distinguishing a truncated random permutation from a random function. *IACR Cryptol. ePrint Arch.*, page 773, 2015.

[GG21] Shoni Gilboa and Shay Gueron. The advantage of truncated permutations. *Discret. Appl. Math.*, 294:214-223, 2021.

[GGM18] Shoni Gilboa, Shay Gueron, and Ben Morris. How many queries are needed to distinguish a truncated random permutation from a random function? *J. Cryptol.*, 31(1):162-171, 2018.

[GNL11] Zheng Gong, Svetla Nikova, and Yee Wei Law. KLEIN: A new family of lightweight block ciphers. In Ari Juels and Christof Paar, editors, *RFID. Security and Privacy - 7th International Workshop, RFIDSec 2011, Amherst, USA, June 26-28, 2011, Revised Selected Papers*, volume 7055 of *Lecture Notes in Computer Science*, pages 1-18. Springer, 2011.

[GPPR11] Jian Guo, Thomas Peyrin, Axel Poschmann, and Matthew J. B. Robshaw. The LED block cipher. In Bart Preneel and Tsuyoshi Takagi, editors, *Cryptographic Hardware and Embedded Systems - CHES 2011 - 13th International Workshop, Nara, Japan, September 28 - October 1, 2011. Proceedings*, volume 6917 of *Lecture Notes in Computer Science*, pages 326-341. Springer, 2011.
[GVG$^{+17}$] Xinfei Guo, Vaibhav Verma, Patricia Gonzalez-Guerrero, Sergiu Mosanu, and Mircea R. Stan. Back to the future: Digital circuit design in the finfet era. *J. Low Power Electron.*, 13(3):338–355, 2017.

[HBK$^{+02}$] M. S. Hrishikesh, Doug Burger, Stephen W. Keckler, Premkishore Shivakumar, Norman P. Jouppi, and Keith I. Farkas. The optimal logic depth per pipeline stage is 6 to 8 FO4 inverter delays. In Yale N. Patt, Dirk Grunwald, and Kevin Skadron, editors, *29th International Symposium on Computer Architecture (ISCA 2002), 25-29 May 2002, Anchorage, AK, USA*, pages 14–24. IEEE Computer Society, 2002.

[HKM95] Carlo Harpes, Gerhard Kramer, and James L. Massey. A generalization of linear cryptanalysis and the applicability of matsui's piling-up lemma. In Louis C. Guillou and Jean-Jacques Quisquater, editors, *Advances in Cryptology - EUROCRYPT '95, International Conference on the Theory and Application of Cryptographic Techniques, Saint-Malo, France, May 21-25, 1995, Proceeding*, volume 921 of *Lecture Notes in Computer Science*, pages 24–38. Springer, 1995.

[HMT19] Viet Tung Hoang, David Miller, and Ni Trieu. Attacks only get better: How to break FF3 on large domains. In Yuval Ishai and Vincent Rijmen, editors, *Advances in Cryptology - EUROCRYPT 2019 - 38th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Darmstadt, Germany, May 19-23, 2019, Proceedings, Part II*, volume 11477 of *Lecture Notes in Computer Science*, pages 85–116. Springer, 2019.

[HTT18] Viet Tung Hoang, Stefano Tessaro, and Ni Trieu. The curse of small domains: New attacks on format-preserving encryption. In Hovav Shacham and Alexandra Boldyreva, editors, *Advances in Cryptology - CRYPTO 2018 - 38th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 19-23, 2018, Proceedings, Part I*, volume 10991 of *Lecture Notes in Computer Science*, pages 221–251. Springer, 2018.

[JNP14] Jérémy Jean, Ivica Nikolic, and Thomas Peyrin. Tweaks and Keys for Block Ciphers: The TWEAKEY Framework. In Palash Sarkar and Tetsu Iwata, editors, *Advances in Cryptology — ASIACRYPT 2014 — 20th International Conference on the Theory and Application of Cryptology and Information Security, Kaoshiung, Taiwan, R.O.C.*, December 7-11, 2014, *Proceedings, Part II*, volume 8874 of LNCS, pages 274–288. Springer, 2014.

[Knu94] Lars R. Knudsen. Truncated and higher order differentials. In Bart Preneel, editor, *Fast Software Encryption: Second International Workshop. Leuven, Belgium, 14-16 December 1994, Proceedings*, volume 1008 of *Lecture Notes in Computer Science*, pages 196–211. Springer, 1994.

[Knu98] Donald Ervin Knuth. *The art of computer programming, Volume III: Sorting and Searching, 2nd Edition*. Addison-Wesley, 1998.

[Köl14] Stefan Kölbl. CryptoSMT: An easy to use tool for cryptanalysis of symmetric primitives, 2014. https://github.com/kste/cryptoSMT.

[LHW19] Muzhou Li, Kai Hu, and Meiqin Wang. Related-tweak statistical saturation cryptanalysis and its application on QARMA. *IACR Trans. Symmetric Cryptol.*, 2019(1):236–263, 2019.

[LJ18] Rongjia Li and Chenhui Jin. Meet-in-the-Middle attacks on reduced-round QARMA-64/128. *Comput. J.*, 61(8):1158–1165, 2018.
[LRW02] Moses Liskov, Ronald L. Rivest, and David Wagner. Tweakable block ciphers. In Moti Yung, editor, *Advances in Cryptology — CRYPTO 2002, 22nd Annual International Cryptology Conference, Santa Barbara, California, USA, August 18-22, 2002, Proceedings*, volume 2442 of LNCS, pages 31–46. Springer, 2002.

[LST12] Will Landecker, Thomas Shrimpton, and R. Seth Terashima. Tweakable Blockciphers with Beyond Birthday-Bound Security. In Reihaneh Safavi-Naini and Ran Canetti, editors, *Advances in Cryptology — CRYPTO 2012 — 32nd Annual Cryptology Conference, Santa Barbara, CA, USA, August 19-23, 2012. Proceedings*, volume 7417 of LNCS, pages 14–30. Springer, 2012.

[LV01] Arjen K. Lenstra and Eric R. Verheul. Selecting cryptographic key sizes. *J. Cryptol.*, 14(4):255–293, 2001.

[LZG$^{+}$20] Ya Liu, Tiande Zang, Dawu Gu, Fengyu Zhao, Wei Li, and Zhiqiang Liu. Improved cryptanalysis of reduced-version QARMA-64/128. *IEEE Access*, 8:8361–8370, 2020.

[NIS95] NIST. FIPS PUB 180-1 — Secure Hash Standard. Technical report, National Institute of Standards and Technology, Gaithersburg, MD, United States, April 1995.

[NIS98] NIST, May 1998.

[pak13] pakt. ropc — a Turing-complete ROP compiler, 2013.

[Pat08] Jacques Patarin. Generic Attacks on Feistel Schemes. *IACR Cryptol. ePrint Arch.*, page 36, 2008.

[PP20] Rajeev Kumar Pandey and Sanjeev Kumar Pandey. Analyzing the performance of 7nm finfet based logic circuit for the signal processing in neural network. In *2020 IEEE Recent Advances in Intelligent Computational Systems (RAICS)*, pages 136–140, 2020.

[QPS17] QPSI. Qualcomm Product Security. Pointer Authentication on ARMv8.3 — Design and Analysis of the New Software Security Instructions. https://www.qualcomm.com/documents/whitepaper-pointer-authentication-armv83, 1 2017.

[RBSS12] Ryan Roemer, Erik Buchanan, Hovav Shacham, and Stefan Savage. Return-oriented programming: Systems, languages, and applications. *ACM Trans. Inf. Syst. Secur.*, 15(1):2:1–2:34, 2012.

[Rog04] Phillip Rogaway. Efficient Instantiations of Tweakable Blockciphers and Refinements to Modes OCB and PMAC. In *Advances in Cryptology — ASIACRYPT 2004, 10th International Conference on the Theory and Application of Cryptology and Information Security, Jeju Island, Korea, December 5-9, 2004, Proceedings*, pages 16–31, 2004.

[SAB11] Edward J. Schwartz, Thanassis Avgerinos, and David Brumley. Q: exploit hardening made easy. In *20th USENIX Security Symposium, San Francisco, CA, USA, August 8-12, 2011, Proceedings*. USENIX Association, 2011.

[SBD02] Aaron Stump, Clark W. Barrett, and David L. Dill. CVC: A cooperating validity checker. In Ed Brinksma and Kim Guldstrand Larsen, editors, *Computer Aided Verification, 14th International Conference, CAV 2002, Copenhagen, Denmark, July 27-31, 2002, Proceedings*, volume 2404 of Lecture Notes in Computer Science, pages 500–504. Springer, 2002.
[Sha07] Hovav Shacham. The geometry of innocent flesh on the bone: return-into-libc without function calls (on the x86). In Peng Ning, Sabrina De Capitani di Vimercati, and Paul F. Syverson, editors, *Proceedings of the 2007 ACM Conference on Computer and Communications Security, CCS 2007, Alexandria, Virginia, USA, October 28-31, 2007*, pages 552–561. ACM, 2007.

[SII23] Kosei Sakamoto, Ryoma Ito, and Takanori Isobe. Parallel SAT framework to find clustering of differential characteristics and its applications. Cryptology ePrint Archive, Paper 2023/1227, 2023.

[SNC09] Mate Soos, Karsten Nohl, and Claude Castelluccia. Extending SAT solvers to cryptographic problems. In Oliver Kullmann, editor, *Theory and Applications of Satisfiability Testing - SAT 2009, 12th International Conference, SAT 2009, Swansea, UK, June 30 - July 3, 2009. Proceedings*, volume 5584 of Lecture Notes in Computer Science, pages 244–257. Springer, 2009.

[SSA$^{+}$07] Taizo Shirai, Kyoji Shibutani, Toru Akishita, Shiho Moriai, and Tetsu Iwata. The 128-Bit blockcipher CLEFIA. In Alex Biryukov, editor, *FSE 2007*, volume 4593 of LNCS, pages 181–195. Springer, 2007.

[ST85] Daniel Dominic Sleator and Robert Endre Tarjan. Self-adjusting binary search trees. *J. ACM*, 32(3):652–686, 1985.

[ST13] Thomas Shrimpton and R. Seth Terashima. A Modular Framework for Building Variable-Input-Length Tweakable Ciphers. In Kazue Sako and Palash Sarkar, editors, *Advances in Cryptology — ASIACRYPT 2013 — 19th International Conference on the Theory and Application of Cryptology and Information Security, Bengaluru, India, December 1-5, 2013, Proceedings, Part I*, volume 8269 of LNCS, pages 405–423. Springer, 2013.

[YQC18] Dong Yang, Wen-Feng Qi, and Hua-Jin Chen. Impossible differential attack on QARMA family of block ciphers. Cryptology ePrint Archive, Paper 2018/334, 2018. https://eprint.iacr.org/2018/334.

[ZD16] Rui Zong and Xiaoyang Dong. Meet-in-the-middle attack on QARMA block cipher. Cryptology ePrint Archive, Report 2016/1160, 2016. http://eprint.iacr.org/2016/1160.

[ZD18] Rui Zong and Xiaoyang Dong. MILP-aided related-tweak/key impossible differential attack and its applications to QARMA, Joltik-BC. Cryptology ePrint Archive, Paper 2018/142, 2018. https://eprint.iacr.org/2018/142.

[ZD19] Rui Zong and Xiaoyang Dong. Milp-aided related-tweak/key impossible differential attack and its applications to qarma, joltik-bc. *IEEE Access*, 7:153683–153693, 2019.

[ZDC$^{+}$21] Rui Zong, Xiaoyang Dong, Huaifeng Chen, Yiyuan Luo, Si Wang, and Zheng Li. Towards key-recovery-attack friendly distinguishers: Application to GIFT-128. *IACR Trans. Symmetric Cryptol.*, 2021(1):156–184, 2021.
A Statistical Properties of the Multiple Differential used
in the Attack on $z = 4$

In Tables 4 and 5 we show the statistical properties for the characteristics shown in Figures 12 and 13. In the first table we display the results with no constraints on the involved tweak bits, and in the second table the results with the constraints set to the indicated values of ($d_0, d_1$), i.e., the parities in Relations (7').
<caption>**Table 4:** Statistical properties of the 43 characteristics from Figures 12 and 13 without restrictions on the tweak values.</caption>

The 12 characteristics from Figure 12: N = 2<sup>24</sup> pairs were used in each experiment.

<table><thead><tr><th rowspan="2">Char.</th><th>Estimated</th><th colspan="3">Computed</th><th rowspan="2">Successes<br>out of<br>100 trials</th></tr><tr><th>η<br>S.D.</th><th>Mean ± S.D</th><th>Min</th><th>Max</th><th>q̄</th></tr></thead><tbody><tr><td>1</td><td>255.50</td><td>2085.58 ± 3615.61</td><td>-670</td><td>8751</td><td>12.97</td><td>26</td></tr><tr><td>2</td><td>255.50</td><td>2266.01 ± 3650.12</td><td>-451</td><td>8512</td><td>12.85</td><td>28</td></tr><tr><td>3</td><td>255.50</td><td>2369.74 ± 3820.03</td><td>-655</td><td>10826</td><td>12.79</td><td>33</td></tr><tr><td>4</td><td>255.50</td><td>1993.47 ± 3511.78</td><td>-700</td><td>8576</td><td>13.04</td><td>25</td></tr><tr><td>5</td><td>255.50</td><td>2165.11 ± 3724.98</td><td>-645</td><td>10359</td><td>12.92</td><td>28</td></tr><tr><td>6</td><td>255.50</td><td>2463.98 ± 3933.09</td><td>-676</td><td>10652</td><td>12.73</td><td>30</td></tr><tr><td>7</td><td>255.50</td><td>2434.28 ± 3911.55</td><td>-415</td><td>10487</td><td>12.75</td><td>29</td></tr><tr><td>8</td><td>255.50</td><td>1920.57 ± 3284.62</td><td>-503</td><td>8903</td><td>13.09</td><td>32</td></tr><tr><td>9</td><td>255.50</td><td>1994.94 ± 3398.59</td><td>-531</td><td>9023</td><td>13.04</td><td>32</td></tr><tr><td>10</td><td>255.50</td><td>2293.29 ± 3684.26</td><td>-473</td><td>8570</td><td>12.84</td><td>28</td></tr><tr><td>11</td><td>255.50</td><td>2440.46 ± 3836.79</td><td>-414</td><td>10527</td><td>12.75</td><td>32</td></tr><tr><td>12</td><td>255.50</td><td>2288.07 ± 3783.04</td><td>-673</td><td>10673</td><td>12.84</td><td>32</td></tr></tbody></table>

The 31 characteristics from Figure 13: N = 2<sup>26</sup> pairs were used in each experiment.

<table><thead><tr><th rowspan="2">Char.</th><th>Estimated</th><th colspan="3">Computed</th><th rowspan="2">Successes<br>out of<br>100 trials</th></tr><tr><th>η<br>S.D.</th><th>Mean ± S.D</th><th>Min</th><th>Max</th><th>q̄</th></tr></thead><tbody><tr><td>1</td><td>511.00</td><td>5798.21 ± 8069.88</td><td>-1299</td><td>24959</td><td>13.50</td><td>33</td></tr><tr><td>2</td><td>511.00</td><td>5640.47 ± 9929.57</td><td>-1085</td><td>33788</td><td>13.54</td><td>31</td></tr><tr><td>3</td><td>511.00</td><td>4209.51 ± 6506.38</td><td>-1296</td><td>17398</td><td>13.96</td><td>32</td></tr><tr><td>4</td><td>511.00</td><td>4094.33 ± 7048.86</td><td>-1252</td><td>17159</td><td>14.00</td><td>25</td></tr><tr><td>5</td><td>511.00</td><td>4408.30 ± 6818.51</td><td>-777</td><td>17841</td><td>13.89</td><td>31</td></tr><tr><td>6</td><td>511.00</td><td>5069.72 ± 7001.92</td><td>-935</td><td>17287</td><td>13.69</td><td>36</td></tr><tr><td>7</td><td>511.00</td><td>3903.80 ± 6924.97</td><td>-1515</td><td>17376</td><td>14.07</td><td>24</td></tr><tr><td>8</td><td>511.00</td><td>6774.15 ± 12369.40</td><td>-1581</td><td>42109</td><td>13.27</td><td>31</td></tr><tr><td>9</td><td>511.00</td><td>4927.80 ± 7474.82</td><td>-871</td><td>17614</td><td>13.73</td><td>30</td></tr><tr><td>10</td><td>511.00</td><td>6633.73 ± 10880.50</td><td>-1201</td><td>25595</td><td>13.30</td><td>27</td></tr><tr><td>11</td><td>511.00</td><td>7330.09 ± 7933.66</td><td>-1294</td><td>25146</td><td>13.16</td><td>42</td></tr><tr><td>12</td><td>511.00</td><td>5502.13 ± 8254.59</td><td>-1307</td><td>24922</td><td>13.57</td><td>33</td></tr><tr><td>13</td><td>511.00</td><td>6316.38 ± 9064.93</td><td>-1201</td><td>25065</td><td>13.38</td><td>35</td></tr><tr><td>14</td><td>511.00</td><td>4066.96 ± 6295.16</td><td>-1230</td><td>16806</td><td>14.01</td><td>34</td></tr><tr><td>15</td><td>511.00</td><td>6032.48 ± 9243.16</td><td>-1186</td><td>33229</td><td>13.44</td><td>37</td></tr><tr><td>16</td><td>511.00</td><td>4092.05 ± 7116.01</td><td>-1225</td><td>17532</td><td>14.00</td><td>25</td></tr><tr><td>17</td><td>511.00</td><td>4475.24 ± 7876.58</td><td>-1203</td><td>24894</td><td>13.87</td><td>27</td></tr><tr><td>18</td><td>511.00</td><td>4534.33 ± 6575.20</td><td>-1079</td><td>17148</td><td>13.85</td><td>35</td></tr><tr><td>19</td><td>511.00</td><td>4129.26 ± 7557.05</td><td>-1347</td><td>25604</td><td>13.99</td><td>25</td></tr><tr><td>20</td><td>511.00</td><td>4732.90 ± 7566.95</td><td>-1166</td><td>24574</td><td>13.79</td><td>32</td></tr><tr><td>21</td><td>511.00</td><td>5011.33 ± 7583.58</td><td>-1446</td><td>17219</td><td>13.71</td><td>31</td></tr><tr><td>22</td><td>511.00</td><td>4941.77 ± 6975.90</td><td>-930</td><td>16978</td><td>13.73</td><td>37</td></tr><tr><td>23</td><td>511.00</td><td>6122.91 ± 10670.29</td><td>-1168</td><td>25513</td><td>13.42</td><td>25</td></tr><tr><td>24</td><td>511.00</td><td>5618.01 ± 8562.89</td><td>-1066</td><td>33500</td><td>13.54</td><td>36</td></tr><tr><td>25</td><td>511.00</td><td>4012.03 ± 7452.16</td><td>-1749</td><td>25390</td><td>14.03</td><td>25</td></tr><tr><td>26</td><td>511.00</td><td>6583.67 ± 10868.99</td><td>-1115</td><td>26046</td><td>13.32</td><td>27</td></tr><tr><td>27</td><td>511.00</td><td>4414.86 ± 7269.64</td><td>-1220</td><td>17261</td><td>13.89</td><td>27</td></tr><tr><td>28</td><td>511.00</td><td>5322.38 ± 8400.51</td><td>-1485</td><td>25166</td><td>13.62</td><td>31</td></tr><tr><td>29</td><td>511.00</td><td>4432.92 ± 6609.33</td><td>-1053</td><td>17107</td><td>13.89</td><td>34</td></tr><tr><td>30</td><td>511.00</td><td>3959.22 ± 6344.22</td><td>-812</td><td>17069</td><td>14.05</td><td>31</td></tr><tr><td>31</td><td>511.00</td><td>6913.14 ± 7769.96</td><td>-1602</td><td>25567</td><td>13.24</td><td>54</td></tr></tbody></table>
<caption>**Table 5:** Statistical properties of the 43 characteristics from Figures 12 and 13 when the tweak Conditions (7') are met with the given values of ($d_0, d_1$).</caption>

The 12 characteristics from Figure 12: $N = 2^{20}$ pairs were used in each experiment.

<table><thead><tr><th rowspan="2">Char.</th><th rowspan="2">Estimated<br>η<br>S.D.</th><th colspan="3">Computed</th><th rowspan="2">Successes<br>out of<br>100 trials</th><th rowspan="2">(d<sub>0</sub>, d<sub>1</sub>)</th></tr><tr><th>Mean ± S.D</th><th>Min</th><th>Max</th><th>q̄</th></tr></thead><tbody><tr><td>1</td><td>63.87</td><td>515.52 ± 62.94</td><td>369</td><td>679</td><td>10.99</td><td>100 (0, 1)</td></tr><tr><td>2</td><td>63.87</td><td>509.91 ± 66.30</td><td>383</td><td>665</td><td>11.01</td><td>100 (1, 0)</td></tr><tr><td>3</td><td>63.87</td><td>543.28 ± 84.07</td><td>342</td><td>719</td><td>10.91</td><td>100 (1, 1)</td></tr><tr><td>4</td><td>63.87</td><td>512.59 ± 78.59</td><td>352</td><td>783</td><td>11.00</td><td>100 (0, 1)</td></tr><tr><td>5</td><td>63.87</td><td>539.08 ± 78.20</td><td>358</td><td>760</td><td>10.93</td><td>100 (1, 1)</td></tr><tr><td>6</td><td>63.87</td><td>540.32 ± 92.68</td><td>309</td><td>838</td><td>10.92</td><td>100 (1, 0)</td></tr><tr><td>7</td><td>63.87</td><td>548.32 ± 90.16</td><td>393</td><td>760</td><td>10.90</td><td>100 (1, 0)</td></tr><tr><td>8</td><td>63.87</td><td>508.02 ± 69.37</td><td>316</td><td>677</td><td>11.01</td><td>100 (1, 1)</td></tr><tr><td>9</td><td>63.87</td><td>509.21 ± 64.34</td><td>370</td><td>718</td><td>11.01</td><td>100 (1, 1)</td></tr><tr><td>10</td><td>63.87</td><td>507.80 ± 65.95</td><td>374</td><td>676</td><td>11.01</td><td>100 (1, 0)</td></tr><tr><td>11</td><td>63.87</td><td>538.37 ± 76.19</td><td>376</td><td>702</td><td>10.93</td><td>100 (0, 1)</td></tr><tr><td>12</td><td>63.87</td><td>551.91 ± 82.18</td><td>378</td><td>805</td><td>10.89</td><td>100 (0, 1)</td></tr></tbody></table>

The 31 characteristics from Figure 13: $N = 2^{22}$ pairs were used in each experiment.

<table><thead><tr><th rowspan="2">Char.</th><th rowspan="2">Estimated<br>η<br>S.D.</th><th colspan="3">Computed</th><th rowspan="2">Successes<br>out of<br>100 trials</th><th rowspan="2">(d<sub>0</sub>, d<sub>1</sub>)</th></tr><tr><th>Mean ± S.D</th><th>Min</th><th>Max</th><th>q̄</th></tr></thead><tbody><tr><td>1</td><td>127.75</td><td>1154.17 ± 262.88</td><td>753</td><td>1741</td><td>11.83</td><td>100 (0, 1)</td></tr><tr><td>2</td><td>127.75</td><td>1261.24 ± 442.28</td><td>745</td><td>2296</td><td>11.70</td><td>100 (0, 0)</td></tr><tr><td>3</td><td>127.75</td><td>1037.21 ± 141.04</td><td>690</td><td>1482</td><td>11.98</td><td>100 (0, 1)</td></tr><tr><td>4</td><td>127.75</td><td>1026.67 ± 139.99</td><td>715</td><td>1398</td><td>12.00</td><td>100 (0, 0)</td></tr><tr><td>5</td><td>127.75</td><td>1028.04 ± 135.39</td><td>654</td><td>1314</td><td>11.99</td><td>100 (1, 0)</td></tr><tr><td>6</td><td>127.75</td><td>1010.56 ± 138.67</td><td>610</td><td>1396</td><td>12.02</td><td>100 (1, 0)</td></tr><tr><td>7</td><td>127.75</td><td>1024.98 ± 130.43</td><td>805</td><td>1385</td><td>12.00</td><td>100 (0, 0)</td></tr><tr><td>8</td><td>127.75</td><td>1475.22 ± 613.13</td><td>754</td><td>2765</td><td>11.47</td><td>100 (0, 0)</td></tr><tr><td>9</td><td>127.75</td><td>1025.01 ± 123.17</td><td>706</td><td>1340</td><td>12.00</td><td>100 (0, 1)</td></tr><tr><td>10</td><td>127.75</td><td>1526.31 ± 143.34</td><td>1124</td><td>1845</td><td>11.42</td><td>100 (0, 1)</td></tr><tr><td>11</td><td>127.75</td><td>1148.12 ± 254.34</td><td>744</td><td>1768</td><td>11.83</td><td>100 (1, 1)</td></tr><tr><td>12</td><td>127.75</td><td>1370.89 ± 264.60</td><td>730</td><td>1812</td><td>11.58</td><td>100 (1, 1)</td></tr><tr><td>13</td><td>127.75</td><td>1138.22 ± 228.49</td><td>769</td><td>1672</td><td>11.85</td><td>100 (1, 0)</td></tr><tr><td>14</td><td>127.75</td><td>1028.94 ± 129.78</td><td>797</td><td>1443</td><td>11.99</td><td>100 (0, 0)</td></tr><tr><td>15</td><td>127.75</td><td>1307.01 ± 486.10</td><td>758</td><td>2342</td><td>11.65</td><td>100 (0, 0)</td></tr><tr><td>16</td><td>127.75</td><td>1014.07 ± 140.57</td><td>704</td><td>1394</td><td>12.01</td><td>100 (1, 0)</td></tr><tr><td>17</td><td>127.75</td><td>1122.94 ± 236.16</td><td>725</td><td>1780</td><td>11.87</td><td>100 (1, 1)</td></tr><tr><td>18</td><td>127.75</td><td>1021.63 ± 117.58</td><td>735</td><td>1402</td><td>12.00</td><td>100 (1, 0)</td></tr><tr><td>19</td><td>127.75</td><td>1138.60 ± 246.36</td><td>679</td><td>1876</td><td>11.85</td><td>100 (1, 1)</td></tr><tr><td>20</td><td>127.75</td><td>1165.59 ± 258.04</td><td>659</td><td>1891</td><td>11.81</td><td>100 (0, 1)</td></tr><tr><td>21</td><td>127.75</td><td>1018.88 ± 136.51</td><td>759</td><td>1452</td><td>12.01</td><td>100 (1, 0)</td></tr><tr><td>22</td><td>127.75</td><td>1022.58 ± 133.59</td><td>611</td><td>1387</td><td>12.00</td><td>100 (1, 0)</td></tr><tr><td>23</td><td>127.75</td><td>1140.75 ± 259.66</td><td>701</td><td>1689</td><td>11.84</td><td>100 (1, 1)</td></tr><tr><td>24</td><td>127.75</td><td>1452.98 ± 248.09</td><td>790</td><td>1824</td><td>11.50</td><td>100 (1, 1)</td></tr><tr><td>25</td><td>127.75</td><td>1197.76 ± 275.43</td><td>754</td><td>1812</td><td>11.77</td><td>100 (1, 0)</td></tr><tr><td>26</td><td>127.75</td><td>1533.00 ± 118.06</td><td>1295</td><td>1887</td><td>11.42</td><td>100 (0, 1)</td></tr><tr><td>27</td><td>127.75</td><td>1034.45 ± 114.33</td><td>708</td><td>1300</td><td>11.99</td><td>100 (0, 1)</td></tr><tr><td>28</td><td>127.75</td><td>1165.27 ± 246.96</td><td>671</td><td>1701</td><td>11.81</td><td>100 (1, 1)</td></tr><tr><td>29</td><td>127.75</td><td>1036.41 ± 121.61</td><td>721</td><td>1369</td><td>11.98</td><td>100 (0, 1)</td></tr><tr><td>30</td><td>127.75</td><td>1013.12 ± 106.29</td><td>742</td><td>1263</td><td>12.02</td><td>100 (0, 0)</td></tr><tr><td>31</td><td>127.75</td><td>1129.12 ± 240.12</td><td>699</td><td>1737</td><td>11.86</td><td>100 (1, 1)</td></tr></tbody></table>