# Cube-based cryptanalysis of Ascon and Gift

Jules ROUSSEAU

► To cite this version:

Jules ROUSSEAU. Cube-based cryptanalysis of Ascon and Gift. Université de rennes; Irisa Institut de Recherche en Informatique et Systèmes Aléatoires. 2024, pp.32. hal-04692191

HAL Id: hal-04692191

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

Submitted on 9 Sep 2024

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>

Open licence - etalab
Internship report

Cube-based cryptanalysis of Ascon and
Gift

Jules ROUSSEAU

Master CyberSchool

Parcours Mathématiques de l'Information, Cryptographie

University of Rennes

Supervisor:
André Schrottenloher

Co-Supervisor:
Patrick Derbez
# Contents

<table><tr><td>1</td><td>Introduction</td><td>4</td></tr><tr><td>1.1</td><td>Company and supervisors</td><td>4</td></tr><tr><td>1.2</td><td>Internship Objectives</td><td>4</td></tr><tr><td>2</td><td>Ascon</td><td>4</td></tr><tr><td>2.1</td><td>Lightweight cryptography</td><td>4</td></tr><tr><td>2.2</td><td>Ascon-128 specification</td><td>5</td></tr><tr><td>3</td><td>Cube attacks using the Division Property</td><td>7</td></tr><tr><td>3.1</td><td>Preliminaries and notations</td><td>7</td></tr><tr><td>3.1.1</td><td>Basic notations</td><td>7</td></tr><tr><td>3.1.2</td><td>Preliminaries</td><td>7</td></tr><tr><td>3.2</td><td>Cube attacks</td><td>9</td></tr><tr><td>3.3</td><td>Division Property</td><td>10</td></tr><tr><td>4</td><td>Cube Attacks on Ascon</td><td>11</td></tr><tr><td>4.1</td><td>Other attacks</td><td>11</td></tr><tr><td>4.1.1</td><td>Nonce-misused scenario for capacity-recovery [BCP22]</td><td>11</td></tr><tr><td>4.1.2</td><td>Conditional cube attack on round-reduced Ascon [LDW17]</td><td>13</td></tr><tr><td>4.2</td><td>Distinguishing attacks on 7-Round Ascon</td><td>13</td></tr><tr><td>4.3</td><td>My work on Ascon</td><td>14</td></tr><tr><td>4.3.1</td><td>Different MILP SBox model</td><td>15</td></tr><tr><td>4.3.2</td><td>SAT SBox models</td><td>17</td></tr><tr><td>4.3.3</td><td>Results</td><td>18</td></tr><tr><td>5</td><td>Going further with GIFT</td><td>19</td></tr><tr><td>5.1</td><td>GIFT-64 specification</td><td>19</td></tr><tr><td>5.2</td><td>Context: Bound tightness</td><td>20</td></tr><tr><td>5.3</td><td>My work on GIFT</td><td>23</td></tr><tr><td>5.3.1</td><td>SBoxes with fixed keys</td><td>23</td></tr><tr><td>5.3.2</td><td>Super SBoxes</td><td>24</td></tr><tr><td>5.3.3</td><td>Callback: Checking a trail</td><td>25</td></tr><tr><td>5.4</td><td>Results</td><td>26</td></tr><tr><td>6</td><td>Obstacles and Achievements</td><td>27</td></tr><tr><td>6.1</td><td>Challenges Encountered</td><td>27</td></tr><tr><td>6.2</td><td>Learnings and Contributions</td><td>28</td></tr><tr><td>6.3</td><td>Conclusion</td><td>29</td></tr></table>
Remerciements

Je tiens à exprimer ma sincère gratitude à André Schrottenloher, encadrant de mon
stage, pour ses conseils formateurs, son professionnalisme, ainsi que pour sa constance
et sa disponibilité dans la supervision de mon stage, et pour son engagement lors
de la relecture de ce rapport. J'aimerais également adresser mes remerciements à
Patrick Derbez, co-encadrant de mon stage, pour son expertise précieuse. Je souhaite
exprimer ma reconnaissance à mes collègues de bureau, Baptiste Germon et Gaël
Claudel, pour avoir partagé avec moi ce doux lieu de travail qu'est "La Stagerie". Un
grand merci également à tous les permanents, stagiaires, et l'assistante administrative
de l'équipe Capsule, avec qui nous avons partagé de nombreux repas, pauses café et
quelques "social events". Plus généralement, je tiens à remercier le personnel du
laboratoire de l'IRISA et de l'Inria pour leur accueil et les services fournis au sein de
l'établissement.

Je suis très reconnaissant envers Sylvain Duquesne, gérant du Master de cryptographie de Rennes ainsi que mes professeurs de Master 1 et 2. Je souhaite également adresser mes remerciements aux membres du jury pour avoir pris le temps de lire mon rapport et d'assister à ma soutenance prévue le 5 septembre 2024. Mes remerciements vont également à mes collègues de Master, dont l'entraide et l'ambiance conviviale ont rendu ces deux années d'études particulièrement enrichissantes et agréables.

Je ne saurais trop remercier ma famille : mes parents Bernard-Marie et Sonia,
mon frère jumeau Paul et ma sœur Romane, pour leur soutien inconditionnel et leur
amour tout au long de ce parcours. Je tiens également à exprimer ma gratitude à
mes amis rencontrés pendant le Master : Étienne, Gabriel D., Gabriel V., et Antonin.
Une mention spéciale à Gabriel D., avec qui j'ai partagé la passion pour l'escalade
pendant ces six mois. Un remerciement tout particulier à Théo, qui a été un équipier
formidable et un soutien inestimable au cours de ces quatre dernières années de vie
partagées. Enfin, une pensée émue pour mes deux merveilleuses tortues, qui ont été
des compagnons fidèles et réconfortants durant toute cette période de stage.
# 1 Introduction

## 1.1 Company and supervisors

I started my internship at the beginning of April for a duration of six months at IRISA Rennes, a French research and innovation laboratory in digital science and technology. I was hired by Irisa, and I was assigned to the joint IRISA-Inria<fnref n="1" /> team CAPSULE<fnref n="2" />.

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

This team has several research themes. Among them are the design and analysis of lightweight block ciphers, lattice-based cryptography, side-channel attacks, and the design and analysis of real-world cryptographic systems such as WhatsApp and Signal secure messaging. I joined the "symmetric cryptanalysis" side of the team, with my internship supervisor being André Schrottenloher, a permanent researcher at Inria specializing in cryptology, with a focus on symmetric cryptanalysis, quantum algorithms, and post-quantum cryptography. This internship was also conducted in collaboration with Patrick Derbez, an associate professor at the University of Rennes specializing in the cryptanalysis of symmetric primitives.

## 1.2 Internship Objectives

The internship I completed took place in two phases. I first focused on performing algebraic attacks<fnref n="3" /> and in particular *cube attacks* on the authenticated encryption scheme Ascon [DEMS21]. Then, I applied this type of attacks to another symmetric algorithm, GIFT, to try to improve some results found in [HLLT20]. This report will therefore consist of an introduction to Ascon and algebraic attacks, as well as a presentation of my work on GIFT.

# 2 Ascon

## 2.1 Lightweight cryptography

The first target considered during this internship was Ascon, which is a family of lightweight authenticated ciphers selected by the US National Institute of Standards and Technology (NIST) for future standardization in lightweight cryptography [oSN23].

Lightweight cryptography is a recent trend (since the 2010s) which aims at adapting cryptographic primitives to the constraints arising in specific use cases, especially small IoT (Internet of Things) devices. These may require a low memory footprint, energy consumption, or an optimized circuit implementation which traditional primitives like the AES [DR20] cannot offer. Thus, the lightweight cryptography essential

<footnote n="1">¹The National Institute for Research in Digital Science and Technology</footnote>

<footnote n="2">²Cryptographie Appliquée et Sécurité des Implémentations</footnote>

<footnote n="3">³Algebraic attacks, in general, aim to exploit the algebraic equations that describe the behavior of the cryptographic system. They can include a wide variety of techniques, including, but not limited to, interpolation attacks, solving systems of linear equations, solving polynomial systems and other mathematical methods.</footnote>
characteristics are: less complexity, robust design, high throughput, short execution time, and less RAM requirement.

Ascon is a permutation-based design, which leverages the *Sponge construction* already used in SHA-3 [BDPA13]. This foundational approach enables Ascon to be used as several cryptographic applications, serving as an authenticated cipher (Ascon-128, Ascon-128a, etc.), hash function (Ascon-Hash), or MAC. In the context of my internship I specifically focused on the Ascon-128 variant, for which I provide a brief specification below.

## 2.2 Ascon-128 specification

The Ascon-128 authenticated cipher is permutation-based, and relies primarily on the definition of a cryptographic permutation (which is commonly named Ascon as well).

**Internal State and Round.** The permutation operates on an internal state of 320 bits divided into 5 words of 64 bits each, denoted $X_i, i \in \{0, 1, 2, 3, 4\}$. The *round function* of Ascon is denoted $p$, which is a composition of different layers: $p = p_L \circ p_S \circ p_C$. They represent respectively the linear diffusion layer, the non linear substitution layer and the addition of round constants. The permutation acts on the entire state as shown in Figure 1. First, a 1-byte round constant is XORed to the 64-bit word $X_2$. Then, the non-linear substitution layer applies a 5-bit SBox, whose Boolean circuit is given by Figure 2, 64 times in parallel in a bit-sliced fashion. Finally, the linear transformation layer is shown in Figure 3 and consists of XORs of different rotated copies of each word. In this way, all 320 bits of the state are modified.

<figure><img src="image_3.png" /><figcaption>Figure 2: Ascon's 5-bit SBox</figcaption></figure>

<figure><img src="image_4.png" /><figcaption>Figure 3: Ascon's linear diffusion layer</figcaption></figure>

$$ 
\begin{align*}
x_0 &:= x_0 \oplus (x_0 \gg 19) \oplus (x_0 \gg 28) \\
x_1 &:= x_1 \oplus (x_1 \gg 61) \oplus (x_1 \gg 39) \\
x_2 &:= x_2 \oplus (x_2 \gg 1) \oplus (x_2 \gg 6) \\
x_3 &:= x_3 \oplus (x_3 \gg 10) \oplus (x_3 \gg 17) \\
x_4 &:= x_4 \oplus (x_4 \gg 7) \oplus (x_4 \gg 41)
\end{align*}
$$

The SBox can also be seen as a table (cf. Table 1) mapping a 5-bit integer to another one.
<table><caption>Table 1: SBox as a lookup table</caption><thead><tr><th>x</th><th>0</th><th>1</th><th>2</th><th>3</th><th>4</th><th>5</th><th>6</th><th>7</th><th>8</th><th>9</th><th>a</th><th>b</th><th>c</th><th>d</th><th>e</th><th>f</th></tr></thead><tbody><tr><th>S(x)</th><td>4</td><td>b</td><td>1f</td><td>14</td><td>1a</td><td>15</td><td>9</td><td>2</td><td>1b</td><td>5</td><td>8</td><td>12</td><td>1d</td><td>3</td><td>6</td><td>1c</td></tr><tr><th>x</th><td>10</td><td>11</td><td>12</td><td>13</td><td>14</td><td>15</td><td>16</td><td>17</td><td>18</td><td>19</td><td>1a</td><td>1b</td><td>1c</td><td>1d</td><td>1e</td><td>1f</td></tr><tr><th>S(x)</th><td>1e</td><td>13</td><td>7</td><td>e</td><td>0</td><td>d</td><td>11</td><td>18</td><td>10</td><td>c</td><td>1</td><td>19</td><td>16</td><td>a</td><td>f</td><td>17</td></tr></tbody></table>

**Permutation and Mode.** The round function *p* is iterated from 6 to 12 times depending on the mode considered, to obtain the Ascon permutation. Figure 4 shows how the permutation is used in the Authenticated Encryption with Associated Data encryption (AEAD) mode of Ascon-128, which is based on a modified Duplex Sponge. The internal state has been separated into an *inner part* of size *c* = 256 bits, and an *outer part* of size *r* = 64 bits. The values *c* and *r* are respectively named the *capacity* and the *rate* of the Sponge. The parameters recommended are given in Table 2.

<figure><img src="image_5.png" /><figcaption>Figure 4: AEAD encryption mode of Ascon-128 authenticated cipher [RHSS21]</figcaption></figure>

The AEAD primitive:

$$ (N, A, P) \mapsto (C, T) $$

is an encryption mode that provides both data confidentiality and authenticity.

It takes as input a plaintext *P* (which is encrypted and authenticated), an associated data *A* (which is authenticated but not encrypted), and returns a ciphertext *C* and an authentication tag *T*. In addition, the mode uses a nonce *N* (number used once) to prevent replay attacks and increase robustness: two encryption queries should always use different nonces.

To achieve this, the steps are as follows:

* Initialization of the internal state: concatenation of the initialization constants *IV*, the secret encryption key *K*, and the unique nonce *N* for each message to be encrypted. Then the internal state is permuted using *p*<sup>*a*</sup>.

* Processing of Associated Data (AD): all blocks of AD, denoted *A*<sub>1</sub>...*A*<sub>s</sub> As in Figure 4 are XORed to the internal state sequentially, alternated with the permutation *p*<sup>*b*</sup>.

* Encryption of the plaintext: each plaintext block *P*<sub>1</sub>...*P*<sub>t</sub> is XORed with the state, then the corresponding ciphertext block *C*<sub>i</sub> is extracted and the permutation is applied again.

* Calculation of the authentication tag: the tag *T* is calculated using the secret key *K*.

Note that to encrypt a single block of plaintext without AD, only the first permutation *p*<sup>*a*</sup> will be applied.
<table><caption>Table 2: Parameters for recommended authenticated encryption schemes [DEMS21]</caption><thead><tr><th rowspan="2">Key K</th><th colspan="4">Bit size of</th><th colspan="2">Rounds</th></tr><tr><th>Nonce N</th><th>Tag T</th><th>Data block</th><th>State S</th><th>p<sup>a</sup></th><th>p<sup>b</sup></th></tr></thead><tbody><tr><td>128</td><td>128</td><td>128</td><td>64</td><td>320</td><td>12</td><td>6</td></tr></tbody></table>

# 3 Cube attacks using the Division Property

The first goal of this internship was to review and improve cube attacks on Ascon. Consequently, I started by reading several articles introducing different types of cube attacks. Among them are [BCP22, LDW17].

The article I've looked at most closely and which I'm going to detail in this report is [RHSS21], by Rohit et al. In fact, this article presents several attacks, including one which allows the key to be recovered for a restricted number of rounds. Indeed, this article introduces a 7-round key-recovery attack on Ascon-128 which, to date, remains the highest number of rounds that can be broken.

However, before presenting these attacks, it is essential to introduce the main concepts of cube attacks and division properties, which underlie the rest of this report.

## 3.1 Preliminaries and notations

In this part of the report, I present some basic notations and concepts that we will use further.

### 3.1.1 Basic notations

Let $I$ be a set. The number of elements in $I$ is written as $|I|$. The complementary set of $I$ is denoted as $\bar{I}$. Let $\mathbb{F}_2 = \{0, 1\}$ be the finite field with two elements and $f: \mathbb{F}_2^n \to \mathbb{F}_2$ and $f_k: \mathbb{F}_2^n \to \mathbb{F}_2$ be a Boolean function and a keyed Boolean function respectively.

We denote the coefficient (which is defined below) of the monomial $\mathbf{x}^u$ in $f$ by $\text{Coe}_f(\mathbf{x}^u)$. Given a set $I \subseteq \{0, \dots, n-1\}$ of indexes, $\mathbf{x}[I]$ denotes the set of variables $\{x_i : i \in I\}$. Moreover, the Hamming weight of a vector $\mathbf{u}$ is denoted by $\text{wt}(\mathbf{u})$. Note that throughout this report, since we consider operations on Booleans, $+$ will often be used to denote the Boolean XOR. The actual meaning of a specific use instance should be clear from context.

### 3.1.2 Preliminaries

Usually in symmetric cryptanalysis we see the cryptographic primitive as a function that maps bits to other bits and the goal is to distinguish this function from a random function by capturing properties specific to the encryption scheme. In the specific case of algebraic attacks, we try to find information about the algebraic normal form (ANF) of a Boolean function $f: \mathbb{F}_2^n \to \mathbb{F}_2$, which may be one of the output bits of the cipher, for example. The ANF is defined as follows.

**Definition 1** (algebraic normal form). Let $f: \mathbb{F}_2^n \to \mathbb{F}_2$ be a Boolean function. Its algebraic normal form is given by:

$$f(\mathbf{x}) = \sum_{\mathbf{u} \in \mathbb{F}_2^n} a_{\mathbf{u}} \mathbf{x}^{\mathbf{u}},$$
where $\mathbf{x} = (x_0, \dots, x_{n-1})$, $a_{\mathbf{u}} = \mathrm{Coe}_f(\mathbf{x}^{\mathbf{u}}) \in \mathbb{F}_2$ is called the coefficient of the monomial $\mathbf{x}^{\mathbf{u}} = \prod_{i=0}^{n-1} x_i^{u_i}$. In fact if the coefficient of a monomial is 1 (resp. 0) then the monomial appears (resp. does not appear) in the ANF of $f$.

**Remark 1.** Note that the sum over all vectors $\mathbf{u} \in \mathbb{F}_2^n$ is in $\mathbb{F}_2$. Moreover let $\mathbf{u} = (u_0, \dots, u_{n-1})$ and $\mathbf{v} = (v_0, \dots, v_{n-1})$ be two vectors in $\mathbb{F}_2^n$, then we write $\mathbf{u} \preceq \mathbf{v}$ if $u_i \le v_i \quad \forall i \in \{0, \dots, n-1\}$.

**Remark 2.** Equation 1 shows the ANF of the Ascon 5-bit SBox seen as a Boolean function. Each output bit $y_i$ is a linear combination of monomials formed by the products of input bits $x_j$.

$$
\begin{align}
y_0 &= x_4x_1 + x_3 + x_2x_1 + x_2 + x_1x_0 + x_1 + x_0 \nonumber \\
y_1 &= x_4 + x_3x_2 + x_3x_1 + x_3 + x_2x_1 + x_2 + x_1 + x_0 \nonumber \\
y_2 &= x_4x_3 + x_4 + x_2 + x_1 + 1 \tag{1} \\
y_3 &= x_4x_0 + x_4 + x_3x_0 + x_3 + x_2 + x_1 + x_0 \nonumber \\
y_4 &= x_4x_1 + x_4 + x_3 + x_1x_0 + x_1 \nonumber
\end{align}
$$

**Example 1.** If we consider the least significant bit (LSB) on the left, then the monomial $x_1x_4$ can be written as $\mathbf{x}^{\mathbf{u}}$ with $\mathbf{u} = (01001)$. Indeed,

$$ \mathbf{x}^{\mathbf{u}} = (x_0, x_1, x_2, x_3, x_4)^{(0,1,0,0,1)} = x_0^0 x_1^1 x_2^0 x_3^0 x_4^1 = x_1 x_4 . $$

**Definition 2 (Degree of a Boolean function).** The degree of a monomial $\mathbf{x}^{\mathbf{u}}$ contained within the ANF of a Boolean function is the Hamming weight of $\mathbf{u}$. Thus, it represents the number of variables that the monomial contains. So we can define the degree of a Boolean function $f$ as:

$$ \deg(f) := \max\{wt(\mathbf{u}) : \mathbf{u} \in \mathbb{F}_2^n \text{ and } \mathrm{Coe}_f(\mathbf{x}^{\mathbf{u}}) \neq 0\} . $$

In this article and throughout the rest of this report, we will discuss keyed Boolean functions $f(\mathbf{x}, k)$ such as those used in Ascon; of ANF:

$$ f(\mathbf{x}, k) = \sum_{\mathbf{u} \in \mathbb{F}_2^n} a_{\mathbf{u}}(k)\mathbf{x}^{\mathbf{u}}, \quad k \in \mathbb{F}_2^m . $$

In this case, the degree is calculated on the $\mathbf{x}$ variables and not on the secret constants $k$.

**Lemma 1 ([Can16, Car10]).** Given an oracle access to the Boolean function $f$, $a_{\mathbf{u}}$ for a particular $\mathbf{u}$ can be computed as the sum: $\mathrm{Coe}_f(\mathbf{x}^{\mathbf{u}}) = \sum_{\mathbf{x} \preceq \mathbf{u}} f(\mathbf{x})$ with $2^{wt(\mathbf{u})}$ evaluations of $f$.

**Lemma 2 ([Can16, Car10]).** The set of all coefficients $\{a_{\mathbf{u}} = \sum_{\mathbf{x} \preceq \mathbf{u}} f(\mathbf{x}) : \mathbf{u} \in \mathbb{F}_2^n\}$ can be obtained from the truth table of $f$ with the fast Möbius transform with about $n2^n = 2^{n+\log_2 n}$ XOR operations.

To get the ANF of a function $f$, it is sufficient to know the value of all the coefficients $a_{\mathbf{u}}$ of the monomials for each $\mathbf{u}$. However, since for all $k \in \mathbb{F}_2^m$ it takes $2^{m+wt(\mathbf{u})}$ evaluations of $f$ if $wt(\mathbf{u}) \ge \log_2(m)$ to recover $a_{\mathbf{u}}(\cdot)$ for a single $\mathbf{u}$, if the degree is high, it is not possible to recover $\mathrm{Coe}_f(\mathbf{x}^{\mathbf{u}})$ and thus to reconstruct the ANF.
## 3.2 Cube attacks

Cube attacks were introduced by Dinur and Shamir [DS09]. They are a particular type of algebraic attacks which analyze a Boolean function with unknown ANF by computing a Cube-sum. Typically, they allow to obtain distinguishers (recognizing a function of a given type, for example a reduced-round Ascon permutation) or key-recovery attacks (obtaining information about the key, which is a constant on which the ANF of the function depends). We consider $f_k(\mathbf{x}) = f(\mathbf{x}, k)$ a keyed Boolean function where $\mathbf{x} \in \mathbb{F}_2^n$ is the public input, and $k \in \mathbb{F}_2^m$ is the secret input. Next, we define the notions of cube and Cube-sum.

**Definition 3 (Cube).** Let $I \subseteq \{0, \dots, n-1\}$ be a set of indices and $\bar{I}$ its complementary. We call the cube $C_I$ the set of public inputs $\mathbf{x}[I]$ that take all $2^{|I|}$ possible values while the variables $\mathbf{x}[\bar{I}]$ are fixed. We call $|I|$ the size of the cube and denote $\mathbf{x}^I$ the monomial that is the product of the cube variables $\mathbf{x}[I]$.

**Definition 4 (Cube-sum).** The Cube-sum is the sum of all the outputs of $f(\mathbf{x}, k)$ over all the values given by the cube as input. If each output is modeled by a Boolean function $f_i$, then if all the Cube-sums of the $f_i$ for a given cube are 0, we say that the Cube-sum over $f$ is "all zero".

Knowing this, let $I \subseteq \{0, \dots, n-1\}$ be a set and $\bar{I}$ its complementary. By splitting the public input variables between $I$ and $\bar{I}$, one decomposes $f_k$ as:

$$f_k(\mathbf{x}) = \mathbf{x}^I \cdot p_I(\mathbf{x}[\bar{I}], k) + q(\mathbf{x}, k), \qquad (2)$$

where $p_I$, $q$ are polynomials and $q$ misses some variables in $\mathbf{x}[I]$. Here, $\mathbf{x}^I$ is the monomial containing all the variables with indices in $I$ and $\mathbf{x}[\bar{I}]$ denotes the set of variables with indices in $\bar{I}$, so $\mathbf{x}^I p_I(\mathbf{x}[\bar{I}], k)$ is the linear combination of terms that contain the monomial $\mathbf{x}^I$. The polynomial $p_I$ is called the superpoly associated to the cube term $\mathbf{x}^I$. The main lemma we need to perform cube attacks is the following one.

**Lemma 3.** We decompose the keyed Boolean function $f_k$ as in Equation 2. If we sum $f_k$ over all possible values that $\mathbf{x}^I$ can take, it holds that

$$\bigoplus_{\mathbf{x}[I]} f_k(\mathbf{x}) = p_I(\mathbf{x}[\bar{I}], k).$$

*Proof.* Let's consider $f_k(\mathbf{x}) = p(\mathbf{x}, k)$, a Boolean function. Now, we write this polynomial as $p(\mathbf{x}, k) = \mathbf{x}^I \cdot p_I + q(\mathbf{x}, k)$. We first consider $\mathbf{x}^J$ an arbitrary term of $q(\mathbf{x}, k)$. As $\mathbf{x}^J$ misses at least one of the variables in $I$, it is added an even number of times. Indeed, it is added for the two possible values of any one of the missed variables, where all the other values of the variables are kept the same. This means this term is canceled out modulo 2 in $\sum_{\mathbf{v} \in C_I} p_{|\mathbf{v}|}$. Where $p_{|\mathbf{v}|}$ means $p$ evaluated on the values of the cube.

Then, we focus on $\mathbf{x}^I \cdot p_I$. All the $\mathbf{v} \in C_I$ zero $\mathbf{x}^I$, except when we assign the value 1 to all the variables in $I$. This implies that $p_I$, which has no variables with indexes in $I$ and is thus independent of the values we sum over, is summed only when $\mathbf{x}^I$ is set to 1, i.e., only once. Consequently, the sum of all the derived polynomials is exactly the superpoly $p_I$ of the term we sum over.

□

Moreover, if we set the variables in $\mathbf{x}[\bar{I}]$ as constants, the superpoly is just a Boolean function in $k$. Thus, the superpoly of $\mathbf{x}^I$ becomes equal to $\mathrm{Coe}_f(\mathbf{x}^I)$. So recovering the ANF of the superpoly is equivalent to recovering the coefficient $\mathrm{Coe}_f(\mathbf{x}^I)$.
We have two cases of interest: either the superpoly is zero (the monomials do not appear) and we retrieve partial information about the ANF of $f_k$, or it depends on the key, and we can thus obtain information about the involved key bits. In both cases, we need to be able to get the superpoly structure. To do this, we use the division property.

## 3.3 Division Property

The division property, introduced by Todo [Tod15], is a generalization of integral properties in distinguishers on block ciphers and permutations. There exists a large body of literature and many variants of the property; we focus here on the conventional bit-based division property.

Let $f = \{y_i, i \in \{0, \dots, m-1\}\}$ and $g = \{z_i, i \in \{0, \dots, m-1\}\}$ be the main functions where $y_i = f_i(x_0, \dots, x_{n-1})$ and $z_i = g_i(y_0, \dots, y_{n-1})$ are their $m$ coordinate functions. The Bit Based Division Property allows us to know that:

If for a subset $\chi$ (cube) of $\mathbb{F}_2^n$ each monomial $m_y$ of $y_i$ appearing in a monomial $m_z$ of the $z'_i$s verify $\bigoplus_{\mathbf{x} \in \chi} m_y(\mathbf{x}) = 0$ then it implies $\bigoplus_{\mathbf{x} \in \chi} m_z(\mathbf{x}) = 0$. We can sum up this property as

**Definition 5** (Bit-based Division Property). Let $\mathcal{X}$, $\mathcal{K}$ be sets of $\mathbb{F}_2^n$, we say that $\mathcal{X}$ has the division property if for all $\mathbf{u} \in \mathbb{F}_2^n$ we have

$$ \bigoplus_{\mathbf{x} \in \mathcal{X}} \mathbf{x}^{\mathbf{u}} = \begin{cases} \text{unknown} & \text{if there exists } k \in \mathcal{K} \text{ such that } \mathbf{u} \succeq k \\ 0 & \text{otherwise} \end{cases} $$

*Remark 3.* The conventional division property allows to compute a set of certain monomials (and their multiples) that do not occur in the ANF of a function, and in particular of the superpoly associated to a cube in this function. In fact as the superpoly is the sum on $f$ of all values over the variables of the cube, we can show that some monomials which sum to 0 are not in the ANF of the superpoly, and neither are their multiples.

In order to track the monomials that are actually present in the ANF of the superpoly at the end through the rounds of an iterated cipher, it is necessary to know if the property propagates. We then introduce the Division Trails.

**Definition 6** (Division Trails). Let $f$ be a round function of an iterated block cipher. We denote $\mathbf{u} \xrightarrow{f} \mathbf{v}$ if the vector $\mathbf{u} \in \mathbb{F}_2^n$ can propagate the property to the vector $\mathbf{v} \in \mathbb{F}_2^m$, i.e. if there exists a monomial $m$ in the ANF of $f^\mathbf{v}$ such that $m \succeq \mathbf{u}$. Where $f^\mathbf{v}$ is the product of the $f_i$s such that $v_i = 1$.

Such division trails are also called monomial trails, as $\mathbf{u} \xrightarrow{f} \mathbf{v}$ defines monomials $\mathbf{x}^\mathbf{u}$ and $\mathbf{y}^\mathbf{v}$ such that $\mathbf{x}^\mathbf{u}$ belongs to $\mathbf{y}^\mathbf{v}$, with $\mathbf{y}$ is the ANF of $f(\mathbf{x})$. In particular, if we can show that there does not exist a division trail $a_0 \xrightarrow{f} a_r = e_i$, where $e_i$ is a unit vector, then the $i^{th}$ bit of the ciphertext at the $r^{th}$ round has a Cube-sum always equal to 0.

Thus, based on the existence or absence of trails from one round to another, we can track the non-existence of certain monomials.
**Three-Subset Variants.** So far, we have seen that the bit-based division property splits the monomials of the superpoly ANF into two subsets: those for which we know for certainty that they do not appear in the ANF, and those for which we cannot be sure.

The *Three Subset Bit-Based Division Property* (3SBDP) is a variant introduced in [TM16], which allows the separation of the monomials of the ANF into three subsets: appearing, not appearing, and unknown status. Finally, the *The 3SBDP without unknown subset* aims at removing the unknown subset. It is also known as the *Perfect division property*, since it will exactly separate the monomials between those which appear and don't appear in the ANF. We will now focus on this variant.

In the case we have a trail $a \xrightarrow{f} b$, the conventional division property doesn't give much information on the actual presence of the monomial $x^a$ in the ANF of $f^b$. But in [TM16], Todo et al. found that if there is a trail $t_1$ from $a$ to $b$ then the monomial should appear in the ANF, but if in parallel there is another trail $t_2$ from $a$ to $b$, $t_2 \neq t_1$, then the monomial should appear too. But as we are summing on the cube values over $\mathbb{F}_2$, the monomial appearing two times means it is discarded in the final ANF of the superpoly. More generally, whether the monomial appears depends on the parity of the number of trails.

**Definition 7** (3SBDP without unknown subset).

$$ \bigoplus_{x \in \mathcal{X}} x^u = \begin{cases} 1 & \text{if the number of trails } \mathbb{K} \ni k \xrightarrow{f} u \text{ is odd.} \\ 0 & \text{otherwise} \end{cases} $$

In fact, this definition of the division property allows to track exactly the existence of a monomial through the successive rounds of the function.

We will use later in the report this property to construct a distinguisher and perform superpoly ANF recovery. Indeed, one can use the Division Property to track monomials, and then show an *upper bound* on the degree of monomials for some round.

**Upper bound of algebraic degree.** If we have an upper bound $d$ on the algebraic degree of the expression of an output bit, then if we take an input cube of dimension $\ge d$, the Cube-sum always equals 0. Thus, if a cube is of degree higher than the upper bound, then its superpoly is constant 0. This constitutes a *distinguisher* as this behavior does not occur with a random function. Therefore, we can distinguish a cryptographic function from a random one. We will explore this in more detail further in this report.

# 4 Cube Attacks on Ascon

In this part of the report I'm going to introduce briefly the attack I focused on and I tried to improve. But first I'm going to introduce briefly some other articles of the best known attacks on Ascon so far.

## 4.1 Other attacks

### 4.1.1 Nonce-misused scenario for capacity-recovery [BCP22]

In this article, Baudrin et al. consider the context of *nonce misuse*, in which the attacker is allowed to make several encryption queries with the same nonce, i.e.,
the same initialisation phase. The goal is then to recover the internal state after initialisation, which depends only on the nonce and the key. As the permutation used in the message encryption phase has only 6 rounds, the version that is attacked is thus a 6-round Ascon, which has relatively low algebraic degree compared to the 12-round permutation used in the initialisation. This explains why this attack is able to break Ascon (and why the nonces shouldn't be reused in the first place).

Starting from an unknown internal state, consider the encryption of any message. The approach of [BCP22] is to identify cubes where the output coefficients share a linear divisor. Indeed, if the coefficients are linear, it is possible to recover the coefficients by interpolation. In this scenario, the inner part of the state after initialization is recovered. Below are the main points of the attack.

**First Observation.** If the $i^{th}$ column of the internal state after initialization is $c_i = (v_i, a_i, b_i, c_i, d_i)$, where $v_i$ corresponds to the public variable (a bit of the message block), then after the first SBox layer, the column becomes:

$$c_i = (v_i(a_i + 1) + \dots, v_i(1) + \dots, 0, v_i(c_i + d_i + 1), v_i(a_i))$$

We will subsequently denote $e = c + d + 1$.

**Step 1.** To mount the first step of the attack on 6 rounds Ascon, only two cubes are needed, chosen according to the following propositions:

**Proposition 1.** For a specific cube $C_1$, after the 6$^{th}$ round of permutation, all coefficients $f_i$ associated with a monomial of the product of $v_j$ at the $i^{th}$ output coordinate (i.e., all the highest degree monomials after 6 rounds) are written as:

$$f_i = (a_0 + 1)f_{a,i} + e_0 f_{e,i}$$

**Proposition 2.** For another specific cube $C_2$, after the 6$^{th}$ round of permutation, all coefficients $f_i$ associated with a monomial of the product of $v_j$ at the $i^{th}$ output coordinate are written as:

$$f_i = a_0 \tilde{f}_{a,i} + e_0 \tilde{f}_{e,i}$$

Thus, in *theory*, by performing a targeted Cube-sum for the highest degree cubes, the following results are obtained: if the Cube-sum is not zero, then either $a_0 \oplus 1$ or $e_0$ is equal to 1.

In *practice* (performing tests) it is observed that when $a_0 + 1 = 1$ or $e_0 = 1$, the Cube-sum is almost never all-zero. In fact, it is observed that if the Cube-sum $C_1$ is all-zero, then $a_0 + 1 = 0 \iff a_0 = 1$ and $e_0 = 0$. Thus, one can already recover these two bits. For the Cube-sum $C_2$, it is observed that if it is all-zero, then $a_0 = 0$ and $e_0 = 0$.

**Step 2.** The remaining $a_i$ are recovered by calculating simpler cubes. Furthermore, now that all the $e_i$ and most of the $a_i$ are known, the Boolean function expression can also be calculated using the $v_i$.

**Step 3.** After a step of reducing unknowns, the inner part recovery is finalized by performing an exhaustive search on the remaining bits. The overall complexity is strictly bounded by the cost of the Cube-sum of the degree 32 monomials: $2^{40}$ in time and data.
### 4.1.2 Conditional cube attack on round-reduced Ascon [LDW17]

This article presents several attacks ranging from a cube attack on 5-round Ascon to attacking 7-round Ascon, and reduces the complexity using a 125-bit key. They use the *Cube-like Key-subset Technique*. The idea is to find sets of common divisors of linear polynomials dependent on key bits $g_j$ called partial divisors for many 65-dimension cubes. In fact, if the $g_j$s are of the form $g_j = k_j + \alpha$ with the $k_j$ being key bit variables, and for each set of $\alpha$ denoted as $\beta$, we find a Cube $C_\beta$ that maintains the property of partial divisors of $g_j$, then we can divide the 128-bit key space into $2^{|\beta|}$ different key subsets.

**Proposition 3.** Let $g$ be a partial divisor, If $g = 0$, the Cube-sums of the corresponding 65-dimension cubes are all-zero with probability 1.

**Proposition 4.** If at least one non-zero Cube-sum appears among the Cube-sums of the 65-dimension cubes, we know that $g = 1$ and it is guaranteed to be true.

Then, to recover the key the main idea is to split the full key space into 63 key subsets and one remaining set according to different key bit conditions. In each subset, some 65-dimension cubes are constructed. Then, by testing the Cube-sum of these cubes, we know which subsets the secret key falls into.

The time complexity of this key-recovery attack on 7-round Ascon is $2^{103.92}$ ($2^{77}$ is the key falls into a weak-key set of size $2^{117}$).

## 4.2 Distinguishing attacks on 7-Round Ascon

The article I focused on the most is [RHSS21] which gives a distinguishing attack on round-reduced Ascon. Indeed, it allows to calculate upper bounds on the degree of monomials using the 3SBDP without unknown subset. In fact, the attack consists in finding a degree $d$ such that all monomials appearing in the ANF of the output of $f$ at the $r^{th}$ round are of degree at most $d$. $d$ is the so-called upper bound on the degree of monomials. We find such bounds by searching for the maximal size of a cubes that leads to the non-zero Cube-sum. This is possible thanks to the MILP (Mixed Integer Linear Programming) modeling.

**Mixed-Integer Linear Programming.** A linear programming problem is the optimization of a linear function (the objective) under linear inequality constraints. The main parameters of the problem are the number of variables and the number of constraints (including, e.g., bounds on the variables).

MILP is the extension of linear programming with Boolean or integer variables. Though this optimization problem is in general intractable, off-the-shelf solvers making use of powerful heuristics can allow to solve efficiently problems of very large size. In this article, like many other works in symmetric cryptanalysis nowadays, the off-the-shelf MILP solver Gurobi is used [Gur24].

In this method the trails for the three-subset bit-based division property are obtained as solutions of a MILP problem, using a specific set of rules which encode, round by round, how the trails can propagate.

In fact, with the propagation rules as linear constraints we can specify to the solver to find the number of variables involved in a monomial for a non-zero Cube-sum. If it's zero for all cubes of a degree $d$, then the monomial and it's multiples do not appear. Thus, the solver can find an upper bound on the monomial degree at some round $r$.
**Distinguisher.** The distinguisher on 7-round Ascon the authors found is the following. The upper bound on the degree of monomials is at 59, which means that if we set as input a cube composed of more than 60 cube variables, the Cube-sum will be zero.

In fact, depending on the parameters for the search of solution we specify in the
Gurobi model, we can look for two different things:

* the (non-)existence of trails for some monomials and obtain an upper bound on the degree of the monomials, if we set the solution pool parameters to "find one solution".

* the **exact number of trails** for a monomial, if we set the solution pool parameters to "find every solution". If it appears an odd number of times then it occurs in the ANF of the Boolean function. Otherwise, it doesn't (see Definition 7).

In concrete terms, we look for a degree upper bound focusing on the initialization of Ascon, where we can control the nonce $N$. We create the model and give it constraints on certain variables, which are Boolean variables in our case, representing input and output bits. We specify the number of the public nonce variables $v_i$ that will form the cube's variables, while the others will be constant zero. The solver then looks for a cube of this size that propagates the division property for a specific output (one of the $y_j$). If a trail is found, we can access the activeness status of each input variable and know which monomial formed by the cube variables can propagate the division property.

To find such bounds, the Ascon model is reduced to a simpler form. The design of Ascon in this scenario is displayed in Figure 5. Due to the properties of the SBox, since the algebraic degree of the round function is 2, the degree in the cube variables is at most 64 after 7 rounds. We can therefore consider a cube of size 64. Specifically, we consider the 128-bit input nonce $N = N_0 || N_1$ as the 64 cube variables by assuming $N_0 = N_1$. Consequently, we only need to search for cubes of size at most 64. Thus, the assumption $N_0 = N_1$ and the fact that, after 1 round, two words are independent of the cube variables, result in a lower degree in the cube variables.

<figure><img src="image_6.png" /><figcaption>Figure 5: Ascon attack model</figcaption></figure>

The SBox and the linear layer are modeled in MILP. We can distinguish 4, 5, 6-round with $2^8, 2^{16}, 2^{31}$ data, respectively. The upper bound of degree found for the 7th round is 59 and there are $\binom{64}{60} \sim 2^{19.27}$ cubes such that the Cube-sum is constant zero.

## 4.3 My work on Ascon

The code in C++ published by Rohit et al.
to calculate the upper bound on the degree of the monomials also contains an im-
plementation of the Algorithm 1 introduced in [HLM+20], which performs a “naïve”
superpoly recovery which is a direct application of the 3SBDP without unknown sub-
set. This algorithm finds all the possible trails from the public variables at the initial
state to the r^th^ round and discards those that appear an even number of times.

<caption>**Algorithm 1** Algorithm to recover the superpoly</caption>

1: **procedure** ATTACKFRAMEWORK($\mathcal{M}$, $I$, $C_0$)
2: Let $\mathbf{x} := (x_i), i \in \{0, \dots, n-1\}$, where $x_i$ is a MILP variable of $\mathcal{M}$ corresponding to the $i$th secret variable.
3: Let $\mathbf{v} := (v_i), i \in \{0, \dots, m-1\}$, where $v_i$ is a MILP variable of $\mathcal{M}$ corresponding to the $i$th public variable.
4: $\mathcal{M}.\text{con} \leftarrow v_i = 1$ for all $i \in I$.
5: $\mathcal{M}.\text{con} \leftarrow v_i = 0$ for all $i \in C_0$.
6: Prepare a hash table $J$ whose key is an $(n+m)$-bit string and value is a counter.
7: Solve MILP model $\mathcal{M}$ and enumerate all feasible solutions.
8: **for** all feasible solutions **do**
9: &nbsp;&nbsp;&nbsp;&nbsp;Get $\mathbf{u} = (x_1, x_2, \dots, x_n, v_1, v_2, \dots, v_m)$ in every found solution.
10: &nbsp;&nbsp;&nbsp;&nbsp;Increase $J[\mathbf{u}]$ by 1.
11: **end for**
12: Prepare a polynomial $p = 0$.
13: **for** all $\mathbf{u}$ whose $J[\mathbf{u}]$ is an odd number **do**
14: &nbsp;&nbsp;&nbsp;&nbsp;$p = p + (\mathbf{x} \| \mathbf{v})^\mathbf{u}$.
15: **end for**
16: Return $p/t_I$.
17: **end procedure**

As said in the previous part, [RHSS21] gave a more efficient way to recover the
superpoly, but as both methods are not feasible in a decent time, I tried to improve
the implementation of the previous superpoly recovery attack by trying a different
modeling of the SBox of Ascon, so that if it's more efficient it could be extended to
the new approach. Indeed, a different modeling could lead to less trails and / or a
faster computation.

4.3.1 Different MILP SBox model

As noted earlier, to model the substitution layer of Ascon we need to understand the
transitions of the SBox as linear constraints. To transform the function of the SBox to
a MILP problem we can see it as a composition of XOR, AND, COPY, NEGATION
gates which propagate the division property. We give the corresponding rules for the
MILP programming in the Table 3. These linear constraints derive from the condition
that a monomial $\mathbf{x}^a$ is contained in $\mathbf{y}^b$ by the rule $\mathcal{R}$ if and only if $a_1 \mathcal{R} a_2 \preceq b$.

**Example 2.** Let’s have a look on the example of the AND propagation rule.

We are looking for trails $a \overset{\circ}{\to} b$ such that $a$ propagates the division property to $b$, where $a = (a_1, \dots, a_n)$ and $b = (b_1, \dots, b_n)$. For easier understanding, we will consider in this example the case where the AND operation is applied over the two first input variables and the output of the operation is stored in a single variable, i.e.,
$\odot: \mathbb{F}_2^2 \to \mathbb{F}_2$. Thus it is sufficient to consider $a = (a_1, a_2)$ and $b = b_1$.

To model the trail $a \xrightarrow{\odot} b$ it is necessary and sufficient that $\mathbf{x}^a$ be contained in $\mathbf{y}^b$, where $\mathbf{y} = \odot(\mathbf{x})$ and $\mathbf{x} = (x_1, x_2)$.

**Case $b=0$:**

We have $a \xrightarrow{\odot} b$ if and only if

$$ \begin{aligned} \mathbf{y}^b &= (x_1x_2)^b \\ &= 1 \end{aligned} $$

contains the monomial $\mathbf{x}^a$, which holds if and only if $a = (0,0)$.

**Case $b=1$:**

We have $a \xrightarrow{\odot} b$ if and only if

$$ \begin{aligned} \mathbf{y}^b &= (x_1x_2)^b \\ &= x_1x_2 \end{aligned} $$

contains the monomial $\mathbf{x}^a$, which holds if and only if $a = (1,1)$.

We can thus state that the trail $a \xrightarrow{\odot} b$ propagates the division property if and only if $a_1 = a_2 = b$.

One can show the linear constraints for the propagation rules in Table 3 using the same scheme of proof.

<table><caption>Table 3: Table of the propagation rules for the division property in MILP</caption><tr><td>XOR</td><td>$a \xrightarrow{\oplus} b$</td><td>$b = a_1 + \cdots + a_n$</td></tr><tr><td>AND</td><td>$a \xrightarrow{\odot} b$</td><td>$b = a_i \quad \forall i \in \{1, \ldots, n\}$</td></tr><tr><td>COPY</td><td>$a \xrightarrow{copy} b$</td><td>$a \ge b_i \quad \forall i \in \{1, \ldots, n\}$, and $b_1 + \cdots + b_n \ge a$</td></tr><tr><td>NEGATION</td><td>$a \xrightarrow{\neg} b$</td><td>$b \ge a$</td></tr></table>

First, I implemented Algorithm 1 in Python, inspired by Raghvendra Rohit's C++ code, so that I could compare my results with those of the initial implementation. This algorithm is adapted from Algorithm 2 which describes the cube attack principle. Given a model $\mathcal{M}$ of a function $f$, to recover the ANF of a coefficient of $\mathbf{x}^u$, we set the input cube variables appearing in this monomial to 1 and the others to 0 as constraints. We then solve the MILP model of $f$ and find all trails that propagate the division property for this monomial. Finally, if the number of trails is odd, the coefficient of $\mathbf{x}^u$ is 1; otherwise, it is 0.

In the Algorithm 1 the cube variables $v_i$ are set to 1 and the others to 0. Since we are looking for the ANF of the superpoly, we want to determine if there are trails from every monomial to one of the outputs. In practice, we activate only one output bit at a time to calculate the ANF of the superpoly for one output bit. For each set of $x_i$ (key variables) and $v_i$ in each solution, we store their occurrences. Finally, we obtain the ANF of the superpoly as a sum of monomials in the $v_i$s with coefficients in the $x_i$s.
*Remark 4.* For the upper bound computation we simply have to set the objective of the MILP optimization as the maximization of the number of cube variables and find one solution.

<caption>**Algorithm 2** Algorithm to recover a coefficient $a_f^u$</caption>

1: **procedure** ATTACKFRAMEWORK($\mathcal{M}$, $u$)
2: &nbsp;&nbsp;&nbsp;&nbsp;Let $x_i$ be an MILP variable of $\mathcal{M}$ corresponding to the $i$th input of $f$.
3: &nbsp;&nbsp;&nbsp;&nbsp;$\mathcal{M}.con \leftarrow x_i = 1$ for all $i$ such that $u[i] = 1$.
4: &nbsp;&nbsp;&nbsp;&nbsp;$\mathcal{M}.con \leftarrow x_i = 0$ for all $i$ such that $u[i] = 0$.
5: &nbsp;&nbsp;&nbsp;&nbsp;solve MILP model $\mathcal{M}$ and enumerate all feasible solutions.
6: &nbsp;&nbsp;&nbsp;&nbsp;**if** the number of solutions is odd **then**
7: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$a_f^u \leftarrow 1$
8: &nbsp;&nbsp;&nbsp;&nbsp;**else**
9: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$a_f^u \leftarrow 0$
10: &nbsp;&nbsp;&nbsp;&nbsp;**end if**
11: **end procedure**

**Initial Model.** The first Ascon MILP model given in the paper was modeled according to the ANF of the SBox function given in Equation 1. It means that a multiplication between two terms is equivalent to an AND rule, an addition of two terms is equivalent to a XOR, an addition of a constant 1 is equivalent to a NEGATION and each term $x_i$ is a COPY of the initial $x_i$. For efficiency, the SBox code uses four different SBoxes based on the IV constant addition cases. Indeed, adding a constant to some variables in the SBox can lead to using fewer auxiliary variables.

**Boolean Circuit Model.** The second modeling I did was the SBox according to it's boolean circuit (cf. Figure 2). Indeed, as it is rather simple it could lead to less COPY constraints that are the most time-consuming ones because they involve a lot of auxiliary variables to store the copied terms. Unfortunately, it turned out that finding the upper bound on the degree of the monomials or the ANF of the superpoly took longer. In fact, we found more solutions (i.e. trails) because the new SBox model contains fewer constraints and therefore allows more transitions to pass until the transitions that are an odd number are discarded. We conclude that this model was less efficient and tried another modeling.

### 4.3.2 SAT SBox models

To try to address this problem, I modeled the components of Ascon as a satisfiability (SAT) problem using the PySAT solver [IMM18]. The SAT problem consists of determining whether, for a given logical formula, there exists an assignment of Boolean variables that makes the formula true. Thus, a formula is satisfiable if we can find a combination of values for the variables that satisfies all the constraints imposed by the formula. Specifically, to efficiently handle the satisfiability problem, the logical constraints are converted into conjunctive normal form (CNF). A formula in CNF is a conjunction (AND) of clauses, where each clause is a disjunction (OR) of literals. A literal is a Boolean variable or its negation. For example, the constraint $(A \lor \neg B) \land (\neg A \lor C)$ is in CNF.
We had reasons to believe that a SAT-based modeling could be more efficient and faster in finding solutions. Indeed, MILP solvers are well-suited for problems involving mixed variables, continuous variables, or complex linear constraints, while SAT solvers are specialized for solving problems that are Boolean.

Thus, I converted the logical constraints of XOR, AND, COPY, and NEGATION into CNF, which I present in Table 4. It allowed me to model various SBoxes (both the one provided in the article and the one modeled according to the Boolean circuit), the linear diffusion layer, as well as the Ascon algorithm in its entirety. Finally, I performed superpoly recovery using the Glucose4 SAT solver.

<table><caption>Table 4: Table of the propagation rules for the division property in SAT</caption><tr><td>XOR</td><td>(a<sub>1</sub>, a<sub>2</sub>) ⊕→ b</td><td>((a<sub>1</sub> ∧ a<sub>2</sub>) ∨ -b) ∧ (b ∨ -a<sub>1</sub> ∨ -a<sub>2</sub>) ∧ (-a<sub>1</sub>) ∧ (-a<sub>2</sub>)</td></tr><tr><td>AND</td><td>(a<sub>1</sub>, a<sub>2</sub>) ⊙→ b</td><td>(-a<sub>1</sub> ∨ b) ∧ (-a<sub>2</sub> ∨ b) ∧ (a<sub>1</sub> ∨ -b) ∧ (a<sub>2</sub> ∨ -b)</td></tr><tr><td>COPY</td><td>a <sup>copy</sup>→ (b<sub>1</sub>, b<sub>2</sub>)</td><td>(a ∨ -b<sub>1</sub>) ∧ (a ∨ -b<sub>2</sub>) ∧ ((b<sub>1</sub> ∧ b<sub>2</sub>) ∨ -a)</td></tr><tr><td>NEGATION</td><td>a → b</td><td>-a ∨ b</td></tr></table>

### 4.3.3 Results

Unfortunately, all these new MILP and SAT models did not reduce the computation time for the number of trails. In fact, they do not decrease the total number of trails, on the contrary. Indeed, the modeling according to the ANF of the SBox is the one that allows finding a minimum number of trails, although the number of COPY operations is higher than in the other models. The main issue with this model is that the number of trails increases exponentially, and quickly gets out of hand. A comparison between the different models is given in Table 5. The main difference between the MILP and SAT model is that SAT gives only one solution, then we must specify that we don't want this solution to be found again and then solve the model again. This makes the superpoly recovery time computation explode.

Thus, We would need an entirely different modeling in MILP, with more constraints, to reduce the number of trails.

<table><caption>Table 5: Comparison of results obtained with different SBox modelings for attacks on a single output $y_0$.</caption><thead><tr><th rowspan="2"></th><th colspan="2">SBox from ANF</th><th colspan="2">SBox from Boolean circuit</th></tr><tr><th>MILP model</th><th>SAT model</th><th>MILP model</th><th>SAT model</th></tr></thead><tbody><tr><td>Degree upper bound (7 rounds)</td><td>48s</td><td>timeout</td><td>290s</td><td>timeout</td></tr><tr><td>Superpoly ANF recovery (2 rounds)</td><td>1.5s</td><td>360s</td><td>2.5s</td><td>timeout</td></tr><tr><td>Number of trails found (2 rounds)</td><td colspan="2">1469</td><td>1593</td><td>N/A</td></tr><tr><td>Number of valid trails (2 rounds)</td><td colspan="2">917</td><td colspan="2"></td></tr></tbody></table>
*Remark 5.* The number of trails found is the number of solutions given by the model before discarded the trails appearing an even number of times, resulting from the superpoly ANF recovery attack. The number of valid trails is the actual number of monomials appearing in the ANF of the superpoly after 2 rounds. We use N/A to denote not available.

# 5 Going further with GIFT

The second focus of my internship was to improve the results in the algebraic crypt-analysis of the GIFT-64 block cipher [BPP+17]. The study of GIFT-64 is similar to that of Ascon, but GIFT's unique Super SBox structure, which groups 16 SBoxes into 4 larger ones, introduces additional constraints. These constraints can potentially reduce the number of trails, offering an opportunity to achieve better results in cube attacks where Ascon falls short. In this section, I will start with a brief presentation of the GIFT specification, followed by the context in which I worked, and finally, the actual work I accomplished on this encryption algorithm

## 5.1 GIFT-64 specification

GIFT-64 is a lightweight block cipher designed for efficiency and security in constrained environments. Like Ascon-128 it was designed for IoT devices and embedded systems. The algorithm operates on a 64-bit block size and uses a 128-bit key. It consists of 28 rounds, each involving three main components: SubCells, PermBits, and AddRoundKey.

### SubCells

This step applies a 4-bit SBox to each 4-bit nibble of the state.

<table><caption>Table 6: SBox of GIFT-64 seen as a lookup table</caption><thead><tr><th>x</th><th>0</th><th>1</th><th>2</th><th>3</th><th>4</th><th>5</th><th>6</th><th>7</th><th>8</th><th>9</th><th>a</th><th>b</th><th>c</th><th>d</th><th>e</th><th>f</th></tr></thead><tbody><tr><th>GS(x)</th><td>1</td><td>a</td><td>4</td><td>c</td><td>6</td><td>f</td><td>3</td><td>9</td><td>2</td><td>d</td><td>b</td><td>7</td><td>5</td><td>0</td><td>8</td><td>e</td></tr></tbody></table>

### PermBits

In this step, the bits of the state are permuted according to a fixed permutation pattern. This step provides diffusion by spreading the influence of each bit across the entire block.

<table><caption>Table 7: Specification of GIFT-64 Bit Permutation</caption><thead><tr><th>i</th><th>0</th><th>1</th><th>2</th><th>3</th><th>4</th><th>5</th><th>6</th><th>7</th><th>8</th><th>9</th><th>10</th><th>11</th><th>12</th><th>13</th><th>14</th><th>15</th></tr></thead><tbody><tr><th>P64(i)</th><td>0</td><td>17</td><td>34</td><td>51</td><td>48</td><td>1</td><td>18</td><td>35</td><td>32</td><td>49</td><td>2</td><td>19</td><td>16</td><td>33</td><td>50</td><td>3</td></tr><tr><th>i</th><td>16</td><td>17</td><td>18</td><td>19</td><td>20</td><td>21</td><td>22</td><td>23</td><td>24</td><td>25</td><td>26</td><td>27</td><td>28</td><td>29</td><td>30</td><td>31</td></tr><tr><th>P64(i)</th><td>4</td><td>21</td><td>38</td><td>55</td><td>52</td><td>5</td><td>22</td><td>39</td><td>36</td><td>53</td><td>6</td><td>23</td><td>20</td><td>37</td><td>54</td><td>7</td></tr><tr><th>i</th><td>32</td><td>33</td><td>34</td><td>35</td><td>36</td><td>37</td><td>38</td><td>39</td><td>40</td><td>41</td><td>42</td><td>43</td><td>44</td><td>45</td><td>46</td><td>47</td></tr><tr><th>P64(i)</th><td>8</td><td>25</td><td>42</td><td>59</td><td>56</td><td>9</td><td>26</td><td>43</td><td>40</td><td>57</td><td>10</td><td>27</td><td>24</td><td>41</td><td>58</td><td>11</td></tr><tr><th>i</th><td>48</td><td>49</td><td>50</td><td>51</td><td>52</td><td>53</td><td>54</td><td>55</td><td>56</td><td>57</td><td>58</td><td>59</td><td>60</td><td>61</td><td>62</td><td>63</td></tr><tr><th>P64(i)</th><td>12</td><td>29</td><td>46</td><td>63</td><td>60</td><td>13</td><td>30</td><td>47</td><td>44</td><td>61</td><td>14</td><td>31</td><td>28</td><td>45</td><td>62</td><td>15</td></tr></tbody></table>
• AddRoundKey

The round key and round constants are XORed with the current state. The key bits are XORed with the {$4i$}^th and {$4i+1$}^th bits of each 4-bit bloc. The round constants bits are XORed on the {$4i+3$}^th bits of each bloc. The 28 round keys are derived from the 128-bit master key using a key schedule algorithm. It involves rotating and applying some simple transformations we won't detail in this report.

As shown in Figure 6, each of the 28 rounds of GIFT-64 involves the sequential ap-
plication of SubCells, PermBits, and AddRoundKey.

<figure><img src="image_7.png" /><figcaption>Figure 6: GIFT Round function [BPP<sup>+</sup>17]</figcaption></figure>

**5.2 Context: Bound tightness**

To provide some context, the article [HLLT21] presents bounds indicating the number
of rounds from which no integral distinguisher attack is possible, for various ciphers
including GIFT-64.

We have already presented how to mount a distinguishing attack on a function by
finding upper bounds on the algebraic degree. But another interesting information
on the ANF of a function *f* is the *guarantee* that a degree has been reached. Indeed,
if there is a key such that each output bit ANF has a *full degree*, i.e. their ANFs are
of degree at least the size max of the cube: 63, then we don't have any distinguisher.
Thus, we need to find a key such that the superpoly of the 63-degree monomials is
not constant-zero. The *lower bounds of algebraic degree* allows to capture this.

*Remark 6*. In [HLLT21] Hebborn et al. search the key and the superpoly at the same time but it is important to note that they found such bounds for specific **independent round keys** at each round, thus not for all keys. In the original design, the round key is only added to half of the state. They considered a slightly different variant where the round key is added to the full state, as well as assuming that each round key is independent. Thus all their results are proven on ciphers that technically differ from the actual ones, since they use independent keys rather than keys derived from the key schedule. This is a huge difference with the Ascon-128 cipher where we look for upper bounds on the ANF of the permutation and no key pattern are needed.
**Lower bound on algebraic degree.** In their article, the authors proved the lower bounds on algebraic degree found in [HLLT20] for GIFT and other ciphers. There is a lower bound $d_l$ on algebraic degree for a function $f$ at a given round $r$ if there exists at least one key and at least one output bit which is of degree $\ge d_l$. The difference with the upper bound is that an upper bound $d_u$ on the degree of $f$ implies that for all keys all output bits are of degree $\le d_u$.

Knowing whether a degree has been reached at some round gives information on the ANF but which is better to know is information on the degree of linear combination of the coordinate functions. That is why we introduce the lower bounds on *minimal degree*.

**Lower bound on minimal degree.** Firstly, the minimal degree is the minimal algebraic degree of any linear combination of all coordinate functions. If we have a lower bound $d_l$ on the minimal degree for a round given, then there exists at least one key and at least one linear combination of output bits which is of degree $\ge d_l$.

Interestingly, we can use this lower bound to show the appearance of all high-degree monomials at some round in all the output bits (and all linear combinations of outputs). This property is called the *all maximal degree monomial* property. It excludes already a large class of integral distinguishers. Nevertheless, to ensure that no integral distinguisher exists, it is not sufficient to know that all high-degree monomials appear in the combinations of the outputs.

**Strong arguments against integral distinguishers.** As outlined above, even if we know that the degree is high, it does not allow us to exclude all integral distinguishers. An integral distinguisher in general makes use of a fixed set $M \subset \mathbb{F}_2^n$ of plaintext values and a bit-mask $\beta$ such that, for any key $k$, the value of $\sum_{x \in M} \langle \beta, E_k(x) \rangle$ (sum of all the linear combinations) is independent of the key, where $E_k$ is a cipher. In [HLLT20], this was shown for a very limited choice of sets $M$.

What Hebborn et al. did in [HLLT21] is to provide strong arguments against integral distinguishers by finding conditions that show $\sum_{x \in M} \langle \beta, E_k(x) \rangle$ is key-dependent for any possible non-empty set $M$ (excluding the whole input space) and any possible non-zero mask $\beta$. In fact, they showed the most general case by considering any possible set $M$, including sets without an affine structure. They demonstrated the *integral-resistance property* for the ciphers analyzed.

**Proposition 5.** (*Integral-resistance property*) Let $E: \mathbb{F}_2^n \times \mathbb{F}_2^m \to \mathbb{F}_2^n$ be a block cipher. This cipher fulfills the integral-resistance property if for every proper subset $M \subset \mathbb{F}_2^n$ and output mask $\beta \in \mathbb{F}_2^n$, the sum

$$ \sum_{x \in M} \langle \beta, E_k(x + k_0) \rangle . $$

is key-dependent.

To obtain either the integral-resistance property or any lower bound on algebraic or minimal degree, we need to compute all the trails and use the 3SBPD to find the coefficients of the monomials. Indeed, to demonstrate the integral-resistance property for a cipher, it is necessary to compute and prove that the rank of the *integral-resistance matrix* is full. This matrix is composed of the coefficients of the monomials in the ANF of the function targeted. We will not detail this matrix in this report, as we will instead focus on obtaining lower bounds under different assumptions.
*Remark 7.* It's important to note that throughout the article, the hypothesis made is that the keys are independent. Thus, the rounds keys are chosen as key patterns such that the number of trails from the input to the output is odd and the number of bits set to 1 in the key is the highest possible. Indeed, their main observation is that having a key pattern with a high weight tends to lower the resulting number of trails, which is quite interesting since the lower this number is, the easier (and quicker) enumerating them should be.

**GIFT-64 results.** In particular, in this article Hebborn et al. showed that at some point, the GIFT-64 cipher has the *integral-resistance* property which is the resistance against integral distinguishing attacks.

In [HLLT20], the authors showed that all 63-degree monomials appear after 11 rounds for any linear combination of the output bits. This computation was expensive and their results were obtained within about 64 hours.

In [HLLT21], they reused the key patterns given by [HLLT20] for their proof of the "all maximal degree monomial" property to prove that GIFT is resistant against integral distinguishers for 12 rounds. Thus, 12 rounds and higher of GIFT-64 has no integral distinguisher since the integral-resistance property remains as the number of round increases.

Thus, the article presents bounds that are directly found through the existence or non-existence of division trails for the 3SBDP without an unknown subset. They compare these lower bounds to the best-known distinguishers in Table 8.

<table><caption>Table 8: Comparison between best known distinguishers and the integral-resistance property for different ciphers [HLLT21]</caption><thead><tr><td>Cipher</td><td>Known integral distinguisher</td><td>Integral-resistance property</td></tr></thead><tbody><tr><td>SKINNY-64</td><td>12</td><td>13</td></tr><tr><td>CRAFT</td><td>13</td><td>14</td></tr><tr><td>GIFT-64</td><td>10</td><td>12</td></tr><tr><td>PRESENT</td><td>9</td><td>13</td></tr><tr><td>SIMON32</td><td>15</td><td>16</td></tr><tr><td>SIMON48</td><td>16</td><td>17</td></tr><tr><td>SIMON64</td><td>18</td><td>19</td></tr><tr><td>SIMON96</td><td>22</td><td>23</td></tr><tr><td>SIMON128</td><td>26</td><td>27</td></tr><tr><td>Simeck32</td><td>15</td><td>16</td></tr><tr><td>Simeck48</td><td>18</td><td>19</td></tr><tr><td>Simeck64</td><td>21</td><td>22</td></tr></tbody></table>

For almost all lightweight encryption algorithms, the bound is *tight*, which means that the number of rounds for which no attack exists coincides with the number of rounds for which we have the best distinguisher. However, for GIFT and PRESENT, the bound is not tight. It is in this context that we wanted to try to find the cause of this non-tightness. Either it is possible to find a distinguisher over more rounds, or the bound on integral-resistance property can be improved.

But, before attempting to fill this gap, my work was to examine whether we can obtain lower / upper bounds on the algebraic degree of monomials for GIFT-64 under
the assumption that the main key is fixed and the round keys are derived according
to the key schedule. Furthermore, we want to adhere to the fact that the round keys
are only XORed to half of the state and not to the full state, as was done in [HLLT20]
and [HLLT21].

5.3 My work on GIFT

The context of the study of the GIFT-64 block cipher is broadly similar to that of the Ascon study. Indeed, when using a fixed main key, the derived round keys become constants that can be directly integrated into the SBoxes. In this case, GIFT becomes a permutation like Ascon, with the only difference being that GIFT's structure allows for an equivalent representation of the encryption scheme in a different way. Specifically, by simply permuting the SBoxes, it is observed that the 16 4-bit SBoxes can be grouped into 4 so-called 16-bit Super SBoxes. Figure 7, taken from [HLLT20], illustrates this representation. The advantage of this Super SBox structure is that it allows for filtering out some trails, as will be discussed later.

<figure><img src="image_8.png" /><figcaption>Figure 7: Round function of GIFT-64 using SSB friendly description [HLLT20]</figcaption></figure>

As explained in Section 5.2, all the results presented in [HLLT21] are established under the strong condition that the round keys are all independent. However, this is not the case in reality for the round keys of GIFT, which are derived from the key schedule and thus are dependent on each other. Therefore, I focused on obtaining results such as lower bounds, and thus on the existence of trails for a certain number of rounds on GIFT with dependent keys, since this is not addressed in the article. Indeed, they used independent keys with carefully chosen patterns because otherwise, the number of solutions (i.e., trails) explodes, and we need the total number of trails to know which ones cancel each other out. However, if the number of trails is too large, we never obtain the total number. We try to overcome this by modeling the rounds of GIFT as Super SBoxes.

Before doing this, I will briefly explain how I modeled the GIFT-64 cipher with
fixed keys.

5.3.1 SBoxes with fixed keys

First, for the MILP modeling of the SBoxes, the goal is to calculate the inequalities
for the division property adapted to each SBox with the added key bits. From the
cipher's scheme, we observe that the addition of the round constants and the key bits
(which are also constant here) occurs on the 1st, 2nd, and 4th bits of each Super SBox's
output. In this way, we integrate these constants into the SBoxes by precomputing
the key constants to be added at each round using the key schedule. Thus, there are $2^3 = 8$ different SBoxes to precompute depending on the cases of constant addition. To do this, in SageMath, we can define the monomials that constitute the ANF of the GIFT SBox without constants, given by Equation 3, using a polynomial ring. From this ANF, we can obtain the 7 other SBoxes by XORing the calculated round and key constants. Note that the XOR of constants is actually an addition in the polynomial ring defined over $\mathbb{F}_2$. We then calculate the propagation table associated with the SBox by checking, for every vector $\mathbf{u} \in 2^4$, whether for every vector $\mathbf{v} \in 2^4$, $\mathbf{u}^\mathbf{v}$ is contained in the ANF of $\mathbf{y}^\mathbf{v}$. In this way, we obtain a propagation table of size $2^8$. I reformatted this table to give it to my colleague Baptiste Germon, who, during his internship, (re-)implemented an algorithm to calculate a minimal set of inequalities modeling the impossible transitions through a function. Thanks to him, I was thus able to obtain the inequalities for the 8 different SBoxes for my MILP model of GIFT.

Algebraic Normal Form of the 4-bit SBox of GIFT

$$ 
\begin{aligned}
y_0 &= 1 + x_0 + x_1 + x_2 + x_3 + x_0x_1 \\
y_1 &= x_0 + x_2 + x_3 + x_0x_1 + x_0x_2 \\
y_2 &= x_1 + x_2 + x_0x_3 + x_1x_3 + x_1x_2x_3 \\
y_3 &= x_0 + x_1x_3 + x_0x_2x_3
\end{aligned} 
\qquad (3) 
$$

### 5.3.2 Super SBoxes

The Super SBox structure offered by GIFT is a particular structure that allows grouping certain SBoxes together, where the outputs are permuted and mapped to another group of SBoxes. This allows the calculation of the ANF of these Super SBoxes, which are actually just 2 rounds of the gift "permutation". Once the ANF of the Super SBox is known, it is possible to determine whether a trail will continue to propagate the division property or not. Indeed, if we consider a trail $\mathbf{u} \xrightarrow{f} \mathbf{v}$, and if $\mathbf{x}^\mathbf{u}$ is not already contained within the ANF of the Super SBox $\mathbf{y}^\mathbf{v}$, then it will not propagate the division property further. This trail is called an *inconsistent trail*.

**Inconsistent (sub-)trails.** A trail or sub-trail is said to be inconsistent if, for a fixed input, there exist other sub-trails such that the total number of sub-trails is even. In particular, in our case, let $T_1: \mathbf{x}^\mathbf{u} \to \mathbf{y}^\mathbf{v}$ be a monomial sub-trail where $\mathbf{y}^\mathbf{v}$ is the ANF of a Super SBox. If there exists a different sub-trail $T_2: \mathbf{x}^\mathbf{u} \to \mathbf{y}^\mathbf{v}$, then the sub-trails cancel each other out, and thus the main trail can already be canceled. Moreover, inconsistent sub-trails are independent of other parts of the trail and might occur in several parts of trails simultaneously. For instance, assuming that there are 10 inconsistent sub-trails, the number of the total trails is at least $2^{10}$. In other words, inconsistent sub-trails increase the number of total trails exponentially.

In this way, if we manage to eliminate inconsistent sub-trails, it eliminates many trails that could have been generated by these sub-trails later on. Therefore, we perform *cbacks* each time a trail is found for a given number of rounds. A callback is a function passed as an argument to the Gurobi solver during optimization. When an event occurs (in this case, when a solution is found), the solver pauses, and the code of the callback function is executed. During our callback, we check whether the trail is consistent or not. If the trail turns out to be inconsistent, then we model
the fact that this trail is not possible in MILP (Mixed-Integer Linear Programming) with additional constraint that we provide to the model. The model will then resume searching for solutions without considering the trails specified as inconsistent.

We aim to drastically reduce the number of trails found in order to be able to enumerate all of them and to establish lower bounds/upper bounds on the degree of the monomials for a certain number of rounds.

In practice, the rounds of GIFT are modeled as 16-bit Super SBoxes by grouping together an initial layer of 4 SBoxes, the internal permutation within this group, and then the following layer of SBoxes. We do not precompute the Super SBoxes but rather calculate them at the moment of the Callback, meaning as soon as a solution is found. Indeed, once a trail $\mathbf{u} \to \mathbf{v}$ is found, the desired Super SBox can be easily and quickly calculated to verify whether this trail is valid or not.

### 5.3.3 Callback: Checking a trail

To do this, I first modeled the ANF of the Super SBox in SageMath. I began by applying the first layer of SBoxes to the inputs, then XORed the constant bits, applied the permutation, and finally performed the second layer of SBoxes along with the addition of constant bits.

For example we obtain the ANF of the first output of the first Super SBox (shown below) with the addition of the constant bits {0x000a, 0x210b} for the first and second layers of SBoxes respectively.

$$ 
\begin{aligned}
y_0 = & 1 + x_0 + x_1 + x_2 + x_3 + x_9 + x_{10} + x_{12} + x_0x_1 + x_0x_4 + x_0x_6 + x_0x_7 + \\ 
& x_1x_4 + x_1x_6 + x_1x_7 + x_2x_4 + x_2x_6 + x_2x_7 + x_3x_4 + x_3x_6 + x_3x_7 + x_8x_{11} + \\ 
& x_9x_{11} + x_9x_{10}x_{11} + x_{12}x_{14}x_{15} + x_{13}x_{15} + x_0x_1x_4 + x_0x_1x_6 + x_0x_1x_7 + \\ 
& x_0x_1x_4x_5 + x_0x_1x_4x_6 + x_0x_4x_5 + x_0x_4x_6 + x_1x_4x_5 + x_1x_4x_6 + x_2x_4x_5 + \\ 
& x_2x_4x_6 + x_3x_4x_5 + x_3x_4x_6
\end{aligned}
$$

While SageMath is useful for representing monomials in polynomial rings and facilitates operations like constants addition and SBox applications, I used Gurobi in C++ for efficiency purposes. Therefore, to compute the ANF of the Super SBoxes as efficiently as possible, I utilized a tool that converts a truth table of a function into its ANF. This tool is the Möbius transform. The calculation is quick because it suffices to compute the truth table of $\mathbf{y}^v$, apply the Möbius transform to obtain the ANF of $\mathbf{y}^v$ and check that $\mathbf{x}^u$ is indeed contained within $\mathbf{y}^v$, meaning if $\mathbf{u} \preceq \mathbf{v}$ holds. Therefore, it is sufficient to compute the product of the $y_i$ such that $v_i = 1$. This process is summarized in Algorithm 3 below.

**Algorithm 3** Trails checking

1: **Input:** Truth table of Super SBox

2: **Output:** Verification of $\mathbf{u} \xrightarrow{f_{SSB}} \mathbf{v}$

3: Calculate the table of $\mathbf{y}^v$

▷ This is the table of a Boolean function obtained by taking the AND of multiple bits of the Super SBox output.

4: Calculate the ANF of $\mathbf{y}^v$ by applying the Möbius Transform to its table

5: Check if $\mathbf{x}^u$ is in the ANF
**Möbius transform.** The Möbius transform is a method used to convert a Boolean function from its truth table into its Algebraic Normal Form. It works by transforming the vector of function values into a vector representing the coefficients of the monomials in the ANF. Specifically, this transformation relies on inclusion-exclusion operations, where each function value is adjusted based on the contributions of variables and their combinations.

The algorithm implementing efficiently the Möbius Transform is the Fast Möbius Transform which takes the truth table of $y^v$ as input which is composed of $2^{16}$ integers encoded on 16 bits. At the output, the table becomes the truth table of the ANF so that the 5 most significant bits of $u$ encode the vector of the table to be looked at and the 11 least significant bits encode the position of the bit in the vector to be looked at. Thus, if the bit involved at this position is 0, then the trail $u \to v$ is invalid. On the other hand, if it is 1, the trail is valid since the monomial $x^u$ belongs to the ANF of $y^v$.

Without the Fast Möbius Transform we would have to compute the ANF of an output bit according to the propagation table of the division property, which would be $2^{32}$ operations. In theory, for this same task we only need $16 \times 2^{16}$ operations, using the Fast Möbius Transform. In practice the computation time is negligible.

## 5.4 Results

Using our code modeling the GIFT-64 permutation with fixed keys, we succeeded in verifying that we indeed find the longest integral distinguishers introduced in the GIFT specification [BPP+17]. The distinguisher in question is as follows: they chose only one bit in the plaintext as constant, and the others are active, to construct cubes of size 63. Then, the number of rounds for which they can find integral distinguishers is 9 rounds for GIFT-64. We are able to reproduce the following, which is an example of these distinguishers.

$$ (A^{60}, ACA) \xrightarrow{9R} ((UUBB)^{16}) $$

A : Active, C : Constant, U : Unknown, B : Balanced

Here, only the $2^{nd}$ bit in plaintext is constant, and the $(4 \times i)^{th}$ and $(4 \times i + 1)^{th}$ bits in 9-round ciphertexts are balanced. Note that the round key is not XORed with the plaintext in the first round (no pre-whitening key). Therefore, we can trivially extend integral distinguishers by one round, and GIFT-64 has 10-round integral distinguishers.

Then, we wanted to analyze to what extent our model could reduce the number of trails. In fact, we looked for trails for high-degree monomials for certain rounds, with and without callbacks to check trail validity. Indeed, to show the lower bounds on the algebraic degree we presented earlier, it is necessary to compute the total number of trails for high-degree monomials, and in particular the maximum degree monomials.

The reason we add the constraints in the callbacks rather than directly incorporating the Super SBox inequality tables is that precalculating the complete Super SBox tables would be inefficient. In fact, we expect that even with a small number of constraints, we could filter out a significant number of trails. This is what we observe and present in Table 9. We use *Constraints added* to denote constraints indicating that a trail found is not consistent through a Super SBox, thus it is no longer a solution. The *Super SBox layer* column contains the round numbers for which we check the
**Understanding the Division Property.** One of the most significant challenges I faced during my internship was grasping the concept of the Division Property in cryptography. Conducting a thorough literature review to understand Division Property was complicated by the existence of multiple definitions and interpretations of the concept. Each definition has its own nuances and applications, making it difficult to establish a concrete understanding. Navigating through different papers and interpretations required substantial effort to ensure that I fully comprehended the theory behind this property and its implications in practical cryptanalysis.

**Using Gurobi solver for MILP.** Another challenge was learning to use Gurobipy and Gurobi cpp for modeling in Mixed-Integer Linear Programming in Python and C++ respectively. Although I had some prior experience with Python, Gurobi presented its own set of challenges, particularly in terms of implementation and optimization. Learning to model cryptographic problems using Gurobi involved a steep learning curve, including mastering how to define constraints, objectives, and efficiently solve the models. This process was time-consuming but ultimately rewarding, as it allowed me to apply MILP to Ascon-128 and GIFT-64.

**Working with PySAT.** In addition to Gurobi, I encountered challenges while using PySAT, the toolkit I used for SAT problem solving. However, understanding how to effectively translate cryptographic problems into SAT instances and then solve them using PySAT required a significant amount of learning and experimentation. The abstraction level of SAT solvers differs from that of MILP, and adapting to this new framework involved understanding how to model logical constraints and interpret the solutions provided by the SAT solvers.

**Modeling MILP Callbacks.** Modeling MILP callbacks for the GIFT-64 encryption algorithm, especially the transitions through Super SBoxes, was another complex task. Implementing callbacks in MILP required not only technical knowledge but also a deep understanding of the GIFT algorithm's specifications. Debugging these callbacks proved to be particularly challenging, and I needed to seek help from my supervisor André, to resolve certain issues. This debugging process highlighted some difficulties in fully understanding the specifications of GIFT, as well as the intricate details of how Super SBoxes function within the algorithm. These challenges underscored the importance of collaboration and detailed documentation in tackling complex cryptographic problems.

As we will see in the next section, these challenges were integral to my learning experience during the internship. They pushed me to deepen my understanding of cryptographic principles and improve my technical skills in modeling and problem-solving.

## 6.2 Learnings and Contributions

Firstly, the tasks of my internship allowed me to learn a lot of new things about symmetric cryptography.

**Functioning of Ascon.** During my internship, I deeply studied the functioning of Ascon, a lightweight encryption algorithm that has been selected as a finalist in several international competitions. I learned how Ascon combines permutation, key addition, and XOR operations to ensure data confidentiality and integrity. The iterative process of the algorithm and the way data is mixed through several rounds provided me with
a better understanding of security concepts in the context of embedded systems and
the Internet of Things (IoT).

**Modeling in MILP.** I gained skills in mathematical modeling using Mixed-Integer Linear Programming (MILP). I learned how to formulate cryptographic problems in terms of linear constraints and how to use tools like Gurobi to solve these problems. I also learned to implement callbacks to refine the solutions obtained, enabling more efficient searching within the solution space. This process allowed me to explore how MILP models can be used to evaluate the security of cryptographic algorithms.

**Modeling in SAT.** In parallel, I learned to model cryptographic problems using SAT. I understood how to transform problems into CNF Boolean formulas and derive inequalities that can be solved by a SAT solver.

**Propagation tables for Division Property.** I developed skills in calculating propagation tables for the Division Property of SBoxes and Super SBoxes. This process helped me understand how SBoxes propagate inputs through the various layers of the algorithm. These propagation tables were then used to track the evolution of bits through SBoxes, which is crucial for deriving the ANF of this component and verifying the validity of trails. To achieve this, I employed the Möbius Transform, which I had not encountered before.

**Algebraic Normal Forms.** I learned to calculate the Algebraic Normal Forms (ANF) of cryptographic functions, an essential technique for analyzing the nonlinear properties of algorithms. The ANF is used to represent Boolean functions in a canonical form, which is useful for studying the resistance of algorithms to algebraic attacks.

Secondly, this research internship has been a source of contributions to the scientific research field in cryptography.

**Relevance of Modeling Approaches.** One of my significant contributions during this internship was demonstrating that certain cryptographic modeling approaches are less relevant than others. This finding helps guide future research by avoiding approaches that may not be optimal for analyzing certain algorithms.

**Contributions to GIFT-64.** I made real contributions to the GIFT-64 encryption algorithm. Specifically, I modeled the Super SBox structures to filter certain trails, which helped reduce the total number of trails to analyze. Additionally, I modeled GIFT with fixed keys in MILP to search for cube, which had only been done previously on GIFT with independent and well-chosen keys to eliminate trails. This paved the way for a more realistic analysis of the algorithm under less stringent assumptions. Finally, I worked on the idea of finding tightness results for GIFT-64, attempting to reduce the total number of trails required for 10 or 11 rounds.

## 6.3 Conclusion

In conclusion, my internship provided me with the opportunity to explore the intricacies of symmetric cryptography, particularly through the study of the GIFT-64 block cipher and its comparison to Ascon-128. By delving into the analysis of algebraic degree, I gained a deeper understanding of the challenges and considerations involved in cryptographic design and analysis. The process of modeling GIFT-64 with fixed
keys, using tools like SageMath and Gurobi, allowed me to develop practical skills
in applying mathematical concepts to cryptography. Despite the challenges encoun-
tered, such as understanding the Division Property and mastering the use of MILP
and SAT solvers, I was able to contribute to the research by exploring new approaches
to evaluating the security of lightweight ciphers. This experience has significantly en-
riched my knowledge and skills in cryptography, and I look forward to applying these
insights in my future.

References

[BCP22] Jules Baudrin, Anne Canteaut, and Léo Perrin. Practical cube attack against nonce-misused ascon. *IACR Trans. Symmetric Cryptol.*, 2022(4):120-144, 2022.

[BDPA13] Guido Bertoni, Joan Daemen, Michaël Peeters, and Gilles Van Assche. Keccak. In Thomas Johansson and Phong Q. Nguyen, editors, *Advances in Cryptology - EUROCRYPT 2013, 32nd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Athens, Greece, May 26-30, 2013. Proceedings*, volume 7881 of *Lecture Notes in Computer Science*, pages 313-314. Springer, 2013.

[BPP+17] Subhadeep Banik, Sumit Kumar Pandey, Thomas Peyrin, Yu Sasaki, Siang Meng Sim, and Yosuke Todo. GIFT: A small present - towards reaching the limit of lightweight encryption, 2017.

[Can16] Anne Canteaut. Lecture notes on cryptographic boolean functions, 2016.

[Car10] Claude Carlet. Boolean functions for cryptography and error-correcting codes, 2010.

[DEMS21] Christoph Dobraunig, Maria Eichlseder, Florian Mendel, and Martin Schläffer. Ascon v1.2: Lightweight authenticated encryption and hashing. *Journal of Cryptology*, 34, 2021.

[DR20] Joan Daemen and Vincent Rijmen. *The Design of Rijndael - The Advanced Encryption Standard (AES), Second Edition*. Information Security and Cryptography. Springer, 2020.

[DS09] Itai Dinur and Adi Shamir. Cube attacks on tweakable black box polynomials. In Antoine Joux, editor, *Advances in Cryptology - EUROCRYPT 2009, 28th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Cologne, Germany, April 26-30, 2009. Proceedings*, volume 5479 of *Lecture Notes in Computer Science*, pages 278-299. Springer, 2009.

[Gur24] Gurobi Optimization, LLC. Gurobi Optimizer Reference Manual, 2024.

[HLLT20] Phil Hebborn, Baptiste Lambin, Gregor Leander, and Yosuke Todo. Lower bounds on the degree of block ciphers. In Shiho Moriai and Huaxiong Wang, editors, *Advances in Cryptology - ASIACRYPT 2020 - 26th International Conference on the Theory and Application of Cryptology and Information Security, Daejeon, South Korea, December 7-11, 2020, Proceedings, Part I*, volume 12491 of *Lecture Notes in Computer Science*, pages 537-566. Springer, 2020.
[HLLT21] Phil Hebborn, Baptiste Lambin, Gregor Leander, and Yosuke Todo. Strong and tight security guarantees against integral distinguishers. In Mehdi Tibouchi and Huaxiong Wang, editors, *Advances in Cryptology - ASIACRYPT 2021 - 27th International Conference on the Theory and Application of Cryptology and Information Security, Singapore, December 6-10, 2021, Proceedings, Part I*, volume 13090 of Lecture Notes in Computer Science, pages 362-391. Springer, 2021.

[HLM+20] Yonglin Hao, Gregor Leander, Willi Meier, Yosuke Todo, and Qingju Wang. Modeling for three-subset division property without unknown subset. *IACR Cryptol. ePrint Arch.*, page 441, 2020.

[IMM18] Alexey Ignatiev, António Morgado, and João Marques-Silva. Pysat: A python toolkit for prototyping with SAT oracles. In Olaf Beyersdorff and Christoph M. Wintersteiger, editors, *Theory and Applications of Satisfiability Testing - SAT 2018 - 21st International Conference, SAT 2018, Held as Part of the Federated Logic Conference, FloC 2018, Oxford, UK, July 9-12, 2018, Proceedings*, volume 10929 of Lecture Notes in Computer Science, pages 428-437. Springer, 2018.

[LDW17] Zheng Li, Xiaoyang Dong, and Xiaoyun Wang. Conditional cube attack on round-reduced ASCON. *IACR Trans. Symmetric Cryptol.*, 2017(1):175-202, 2017.

[oSN23] National Institute of Standards and Technology (NIST). Lightweight cryptography: Nist selects ascon, 2023. Accessed: 2024-08-01.

[RHSS21] Raghvendra Rohit, Kai Hu, Sumanta Sarkar, and Siwei Sun. Misuse-free key-recovery and distinguishing attacks on 7-round ascon. *IACR Trans. Symmetric Cryptol.*, 2021(1):130-155, 2021.

[TM16] Yosuke Todo and Masakatu Morii. Bit-based division property and application to simon family. In Thomas Peyrin, editor, *Fast Software Encryption - 23rd International Conference, FSE 2016, Bochum, Germany, March 20-23, 2016, Revised Selected Papers*, volume 9783 of Lecture Notes in Computer Science, pages 357-377. Springer, 2016.

[Tod15] Yosuke Todo. Structural evaluation by generalized integral property. In Elisabeth Oswald and Marc Fischlin, editors, *Advances in Cryptology - EUROCRYPT 2015 - 34th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Sofia, Bulgaria, April 26-30, 2015, Proceedings, Part I*, volume 9056 of Lecture Notes in Computer Science, pages 287-314. Springer, 2015.