# Rapport de stage - Analyse d'une primitive symétrique opérant sur de grands corps

Aurélien Boeuf, Encadrant : Léo Perrin

MPRI M2

INRIA Paris, COSMIQ

14 mars 2022 - 28 août 2022

## Le contexte général

La cryptographie symétrique est un sous-domaine important de la cryptographie où l'on suppose que les parties communicantes partagent dès le début une clé secrète permettant de chiffrer et de déchiffrer leurs données.

Le standard le plus connu et utilisé en cryptographie symétrique de nos jours est le chiffrement AES (Advanced Encryption Standard) [DR02], standardisé par le NIST en 2001. Les attaques générales connues contre AES sont très peu efficaces, d'où son ubiquité. Il opère sur des blocs de données de taille fixée ; on appelle ce genre de chiffrement un chiffrement par blocs. Son architecture est dite de type SPN - *Substitution-Permutation Network*. Un autre standard très connu et utilisé est l'algorithme de fonction de hachage SHA-3 [D+15], également standardisé par le NIST en 2015, utilisant une structure dite *éponge*. Ces deux standards opèrent exclusivement sur des extensions fixées de $F_2$, le plus petit corps qui existe. Il s'agit classiquement de la manière de faire la plus efficace en complexité temporelle, les opérations étant décrites comme des fonctions booléennes.

Au fur et à mesure que de nouveaux sous-domaines de la cryptographie se développent, de nouveaux contextes et cas d'usage apparaissent, exigeant des primitives dont les approches sont différentes. Le MPC (Multi-Party Computing) [Gol98] et les systèmes de preuves de type zero-knowledge (ZK-STARK) [GO94] emploient des protocoles cryptographiques avancés, et les standards précédents ne sont plus adaptés. *Rescue* [AAB+19] est un chiffrement de type SPN *orienté arithmétisation*, conçu pour que sa description algébrique soit compacte. Il opère sur un grand corps fini $F_p$. Utilisé en tant que fonction de hachage avec la structure *éponge*, il est bien adapté aux cas d'usage décrits précédemment. C'est la primitive symétrique que j'ai étudiée au cours de mon stage.
## Le problème étudié

Expérimentalement, pour certaines clés sur des exemples simples, mon maître de stage a trouvé que le chiffrement par bloc *Rescue* présentait une **haute uniformité différentielle**. Cela suggère une vulnérabilité potentielle à la crypt-analyse différentielle. Savoir évaluer cette vulnérabilité est un problème clas-sique en cryptographie symétrique mais non trivial. Le but de mon stage était de comprendre ce phénomène, en particulier pour savoir s'il remet en cause la sécurité de cette primitive. Ma contribution pouvait être originale dans la mesure où cette vulnérabilité n'avait pas encore été totalement ex-plorée pour *Rescue*.

## La contribution proposée

J'ai réussi à identifier correctement le phénomène général causant la vulnérabilité observée dans les cas les plus simples. À partir de là, j'ai pu évaluer à quel point ce phénomène remet en cause la sécurité de *Rescue* dans le cas moyen des applications concrètes, et j'ai pu concevoir une version mal-honnête de *Rescue* (dite "backdoorée") utilisé comme fonction de hachage exploitant ce phénomène.

## Les arguments en faveur de sa validité

La validité mathématique de cette contribution se démontre par des preuves simples, et se vérifie expérimentalement. La version "backdoorée" de *Rescue* s'implémente correctement en machine, pour des paramètres réalistes. L'étude dans le cas moyen permet de comprendre la fréquence du phénomène étudié dans une application réaliste, non biaisée. La validité de la solution est robuste dans la mesure où les paramètres étudiés sont ceux utilisés dans une application concrète de la fonction de hachage.

## Le bilan et les perspectives

Il est bien sûr possible de regarder si ce phénomène s'applique également à d'autres protocoles. Cela concerne plutôt ceux de type SPN où la fonction de substitution vérifie les mêmes hypothèses que dans ce travail. On a essayé d'étudier de telles primitives au cours de mon stage, telles que *Poséidon* et *Streebog*. L'étude de propagation de sous-espaces est une approche classique en cryptanalyse, et ma contribution va dans ce sens d'une manière adaptée au protocole étudié. Il serait intéressant de comprendre plus profondément ce qui permet à ce genre d'approche de fonctionner dans le cas général et par exemple comment l'adapter dans le cas d'une extension de $\mathbb{F}_2$ plutôt que dans un corps simple $\mathbb{F}_p$ comme c'est le cas ici.
# 1 Concepts de base en cryptographie symétrique et notations

En cryptographie symétrique, un **chiffrement par bloc** [Sha49] est un algorithme opérant sur des groupes de bits de taille fixée, appelés des blocs. Typiquement, ils s'itèrent un certain nombre de fois, chaque itération étant appelée un **tour**. Chaque tour est censé rendre le chiffrement plus difficile à casser pour les attaquants, au prix d'opérations supplémentaires pour les parties communicantes.

Une architecture courante pour les chiffrements par blocs est la structure de **réseau de substitution-permutation** (Substitution-Permutation Network, ou SPN, en anglais), utilisée notamment dans AES et Rescue. Un schéma représentant un chiffrement par bloc de type SPN est donné ci-dessous, avec $S$ une bijection opérant sur les blocs et $P$ une permutation linéaire.

<figure><img src="image_1.png" /><figcaption>Figure 1: Schéma d'un SPN, https://www.iacr.org/authors/tikz/.</figcaption></figure>

Une **fonction de hachage** est une fonction $h: \{0,1\}^* \rightarrow \{0,1\}^l$ prenant en entrée un message de longueur quelconque et renvoyant un message de longueur fixée $l$. Utilisée à des fins cryptographiques, on exige d'une fonction de hachage qu'elle ait les propriétés suivantes (rappelées dans le papier introduisant SHA-3 $[D^{+15}]$, par exemple) :
* **Résistance aux préimages** : Étant donné une valeur $u$ de l'espace d'arrivée, il doit être difficile de trouver $m$ tel que $h(m) = u$.

* **Résistance aux collisions** : Il doit être difficile de trouver $m_1$ et $m_2$ tels que $h(m_1) = h(m_2)$.

* **Résistance aux secondes préimages** : Étant donné un message $m_1$, il doit être difficile de trouver un autre message $m_2$ tel que $h(m_1) = h(m_2)$.

Nous définissons une **fonction éponge** comme une fonction de hachage correspondant à la construction représentée dans le schéma ci-dessous. $f$ est ici une permutation de l'ensemble des états, chaque état étant divisé en un bloc de $r$ éléments (le **taux**) et un bloc de $c$ éléments (la **capacité**). $f$ peut être par exemple un chiffrement de type SPN sur $m = r + c$ blocs, où chaque bloc contient un élément, par exemple un élément de $\mathbb{F}_p$ (ce sera le cas ici).

<figure><img src="image_2.png" /><figcaption>Figure 2: Schéma d'une fonction éponge (Wikipedia, Sponge Function).</figcaption></figure>

Enfin, nous définissons une **matrice MDS** (maximum distance separable) de la manière suivante :

**Définition 1.1** (Matrices MDS). Une matrice $M$ de taille $m \times m$ est dite MDS si et seulement si l'ensemble des $2m$-tuples $(\vec{x}, M\vec{x})$ où $\vec{x} \in \mathbb{F}_p^m$ forme un code MDS. Cela signifie qu'il atteint la borne de Singleton, ou plus explicitement :

$$d_{min} = m + 1 \qquad (1)$$

où $d_{min}$, la distance minimale du code, correspond au nombre minimum d'éléments non nuls dans les tuples $(\vec{x}, M\vec{x})$ avec $\vec{x} \neq \vec{0}$ (ce qu'on appelle leur poids).

Rescue est un chiffrement par blocs de type SPN. Nous considérons qu'il est ici utilisé comme la fonction de permutation d'une fonction de hachage de type éponge. Ses paramètres sont:
• *p*, un nombre premier et la taille du corps fini $\mathbb{F}_p$ utilisé dans le protocole.

• *m*, le nombre d'éléments du corps qui définissent un état (i.e. le nombre de blocs).

• *M*, une matrice MDS de taille *m* × *m* qui définit la couche linéaire de diffusion du chiffrement.

• *N*, le nombre de tours. Ici, cela correspond à chaque application d'une seule boîte S (*S* or *S*⁻¹). Ainsi *S* et *S*⁻¹ se succèdent, de sorte que *N* est pair. Dans certains papiers, c'est plutôt N/2 qui est considéré.

• *r* = (*r*₁, *r*₂, ..., *r*ₙ), la liste des constantes de tours, chacune étant un vecteur de $\mathbb{F}_p^m$.

En définissant $\alpha$ comme étant le plus petit nombre tel que $\text{pgcd}(p - 1, \alpha) = 1$, la boîte-$S$ est définie par la permutation $x \mapsto x^{\alpha}$ dans $\mathbb{F}_p$, appliquée à chacun des $m$ éléments d'un état donné. Pour la plupart des valeurs de $p$, on a $\alpha = 3$. De même, $S^{-1}$ est définie par $x \mapsto x^{\frac{1}{\alpha}}$.

## 2 Le chiffrement Rescue

Une description schématique du protocole est donnée en **Figure 3**. Voici une description algorithmique :

Le protocole Rescue prend comme entrée l'état $\vec{s} = (s_1, ..., s_m)$ dans $(\mathbb{F}_p)^m$. Du tour 1 au tour *N*, le tour *i* est défini ainsi, selon le schéma SPN :

1. si le numéro de tour *i* est **impair**, appliquer $S$ à l'état $\vec{s}$: pour tout $j$,
   $s_j \leftarrow s_j^{\alpha}$. Si le numéro du tour est **pair**, appliquer $S^{-1}$: pour tout $j$,
   $s_j \leftarrow s_j^{\frac{1}{\alpha}}$.

2. Multiplier l'état $\vec{s}$ par la matrice $M: \vec{s} \leftarrow M\vec{s}$.

3. Additionner l'état $\vec{s}$ et les constantes de tours : $\vec{s} \leftarrow \vec{s} + \vec{r}_i$.

<figure><img src="image_3.png" /><figcaption>Figure 3: Les deux premiers tours de Rescue avec $m = 3$.</figcaption></figure>
# 3 Hautes uniformités différentielles dans Rescue

## 3.1 Définitions

Dans le domaine de la cryptographie symétrique moderne, une des méthodes de cryptanalyse les plus importantes est la cryptanalyse différentielle. C'est historiquement une des vulnérabilités du précédent standard principal de communication symétrique, le protocole DES [BS91]. La métrique principale utilisée pour évaluer la vulnérabilité d'une fonction à la cryptanalyse différentielle est l'uniformité différentielle, quantité que les concepteurs de primitives souhaitent diminuer, mais difficile à étudier.

**Définition 3.1 (Uniformité différentielle).** L'uniformité différentielle d'une fonction F est définie comme le nombre maximum de solutions de l'équation suivante d'indéterminée x, où le maximum est pris sur $\alpha \neq 0$ et $\beta$ parcourant chacun $(\mathbb{F}_p)^m$ :

$$F(x + \alpha) - F(x) = \beta. \qquad (2)$$

En pratique, pour déterminer l'uniformité différentielle de la fonction, on calcule la *Difference Distribution Table* (DDT) de la fonction.

**Définition 3.2 (DDT).** La DDT d'une fonction F est un tableau de taille $p \times p$ dont les coefficients sont :

$$DDT_F[\alpha, \beta] := |\{x | \Delta_{\alpha} F(x) = \beta\}|. \qquad (3)$$

et on extrait l'uniformité différentielle, soit :

$$\delta(F) := \max_{\alpha \neq 0, \beta} DDT_F[\alpha, \beta]. \qquad (4)$$

L'idée de la cryptanalyse différentielle est que si l'uniformité différentielle de la fonction est trop élevée, il est alors possible d'extraire des chemins différentiels pouvant être exploités par l'attaquant (par exemple, pour extraire une partie de la clé secrète dans le cas d'une fonction de chiffrement). Une permutation idéale est une permutation où $\delta(F) = 2$. De telles fonctions sont qualifiées de *Almost Perfect Nonlinear Functions* (fonctions APN) [BCCLC06], et la recherche d'une éventuelle caractérisation de ces fonctions constitue un grand problème actuel. En pratique, on se contente d'un $\delta$ légèrement au-dessus de 2.

## 3.2 Interprétation des hautes uniformités différentielles de quelques instances de Rescue

Dans certaines petites instances de Rescue, des uniformités différentielles anormalement hautes ont été mesurées [BCL+20] (strictement plus grandes que $p$, ce qui serait inquiétant dans les cas réels, lorsque $p \approx 2^{64}$). Malheureusement, lorsque $p$ est trop grand, calculer l'uniformité différentielle
est concrètement impossible. Nous pouvons craindre que ce phénomène se reproduise pour certaines instances du cas pratique. Le premier but de mon stage était de comprendre ce phénomène, afin d’évaluer sa fréquence et son impact sur la sécurité lorsque $p$ est grand.

Premièrement, nous avons dressé la DDT de Rescue (avec l’équation (2)) sur des instances où les paramètres sont petits, et listé les coefficients et les messages qui étaient la source de la haute uniformité différentielle (typiquement $p = 13$ et $m = 2$).

Dans les cas qui nous intéressaient, parmi les messages solutions de (1) pour $\alpha$ et $\beta$ maximisant $\delta(F)$, nous avons pu identifier un espace affine complètement envoyé sur un autre espace affine par la permutation (ceci donnant $p$ solutions à (1)). Ainsi, pour des constantes données $a, b, c, d, e, f, g, h, z$ et une variable $X$ dans $\mathbb{F}_p$ :

$$ \begin{pmatrix} z \\ X \end{pmatrix} \xrightarrow{2 \text{ tours}} \begin{pmatrix} aX + b \\ cX + d \end{pmatrix} \xrightarrow{2 \text{ tours}} \begin{pmatrix} eX + f \\ gX + h \end{pmatrix}. $$

<caption>Figure 4: Le genre de transformation qu'on observe dans les instances de Rescue sur 4 tours où $\delta(F)$ est élevée, expliquant pourquoi $\delta(F)$ est élevée. $X$ parcourt $\mathbb{F}_p$.</caption>

On peut voir sur la **Figure 4** que non seulement l'ensemble des entrées et l'ensemble des sorties sont des espaces affines, mais de plus l'algorithme est *lui-même* une fonction affine sur ces entrées. D'une part, c'est grâce à cette association spécifique que l'on a autant de solutions à l'équation (2) (ce que l'on peut voir en remplaçant les paramètres de l'équation (2) par les expressions de la **Figure 4**). Mais d'autre part, il semble potentiellement plus intéressant d'étudier le cas plus général où un espace affine est envoyé sur un autre d'un point de vue purement ensembliste, sans que la transformation elle-même soit affine (ce qui ne garantirait plus de solutions à l'équation (2)).

J'ai pris le parti de changer la direction de cette étude vers le cas plus général. En effet, si nous pouvons comprendre exactement comment ces espaces affines se chaînent, cela pourrait mettre en évidence des vulnérabilités en dehors du contexte de la cryptanalyse différentielle. À l'inverse, on pourrait assurer que ce phénomène se produit trop rarement dans le cas moyen ou à trop faible amplitude pour qu'on doive s'en inquiéter dans le cas encore plus contraint où l'*uniformité différentielle* est élevée.

Nous sortons donc du cadre de la cryptanalyse différentielle.
# 4 Chaînes d'espaces affines

Un espace affine de dimension $n \le m$ est défini par une famille de $n$ vecteurs libres de $\mathbb{F}_p^m$ notés $(\vec{v}_1, \vec{v}_2, ..., \vec{v}_n)$, dite la base de l'espace et un vecteur de $\mathbb{F}_p^m$ noté $\vec{a}$, dit l'origine de l'espace. L'ensemble défini par cet espace affine est :

$$E := \{\vec{a} + X_1\vec{v}_1 + X_2\vec{v}_2 + ... + X_n\vec{v}_n | X_1, X_2, ..., X_n \in \mathbb{F}_p\}. \quad (5)$$

On pourra également noter cet ensemble de manière plus simple :

$$E := \vec{a} + X_1\vec{v}_1 + X_2\vec{v}_2 + ... + X_n\vec{v}_n. \quad (6)$$

Notons que la notion de base est également présentée comme la notion de direction dans la littérature, mais nous préférons cette notation qui rendra plus claire la relation entre les vecteurs d'espaces affines chaînés.

Le but de cette section va être de montrer l'existence d'espaces affines d'une certaine forme, tels que leur image par la fonction de tour sera également un espace affine. De plus, dans le cas des espaces de dimension 1, si certaines équations sont vérifiées par les constantes de tours et par les coefficients de la base et de l'origine, l'espace affine image sera lui-même envoyé sur un espace affine. De proche en proche, il est ainsi possible de créer des chaînes d'espaces affines de taille arbitraire.

Pour la suite, nous nous intéresserons uniquement aux **espaces affines de dimension 1**, car nous allons voir que les espaces de dimension strictement supérieure à 1 ne peuvent pas être membres de chaînes couvrant 2 tours ou plus.

## 4.1 Représentation unique d'espaces affines de dimension 1

Afin d'avoir une représentation unique base/origine de chaque espace affine de dimension 1, nous adoptons les conventions suivantes :

* L'espace étant invariant par multiplication de son vecteur de base par un scalaire non nul, la valeur de $\vec{v}$ sur sa $1^{re}$ coordonnée non nulle $i_S$ est imposée égale à 1. Notons qu'elle existe puisque $\vec{v} \neq \vec{0}$.

* Sur cette même coordonnée $i_S$, on impose à l'origine : $a_{i_S} = 0$. En effet, le représentant de l'origine est défini modulo addition par la base $\vec{v}$, et il y a un unique représentant $\vec{a}$ dont la coordonnée en $i_S$ vaut 0, puisque $v_{i_S} \neq 0$.

## 4.2 Espaces affines séparés

La clé du phénomène de chaînes d'espaces affines que nous avons expérimentalement observé réside dans un certain type d'espaces affines, que nous nommons espaces affines séparés.
**Définition 4.1** (Espaces affines séparés). Un espace affine de dimension 1 noté $\vec{a} + X\vec{v}$ selon la représentation unique définie précédemment est dit séparé si et seulement si :

$$ \forall 1 \le i \le m, a_i \cdot v_i = 0. \qquad (7) $$

ou dit de manière équivalente, $\text{supp}(\vec{a}) \cap \text{supp}(\vec{v}) = \emptyset$.

Notons que la représentation unique définie précédemment est bien choisie par rapport à cette définition. En effet, un espace non séparé pour le représentant $\vec{a}$ défini ainsi ne le sera pas quel que soit le représentant. Dès lors qu'on lui ajoute un multiple non nul de $\vec{v}$ (notons $\vec{a}' = \vec{a} + \lambda\vec{v}$), on aura selon les notations précédentes $a'_{i_S} = \lambda v_{i_S} \neq 0$, d'où $a'_{i_S} \cdot v_{i_S} \neq 0$.

Nous définissons également un type de propriété vérifié par certaines S-box, et en particulier celles de Rescue.

**Définition 4.2** (S-box additivement permutante). Une S-box est dite additivement permutante lorsqu'elle envoie un sous-groupe additif de $\mathbb{F}_p^m$ sur un autre sous-groupe additif de $\mathbb{F}_p^m$ selon une permutation $\pi$ qui ne dépend pas du sous-groupe de départ. Cette propriété est décrite par l'équation suivante :
Il existe $\pi$, une permutation de $F_p$, telle que :

$$ \forall \vec{v} \in \mathbb{F}_p^m, \forall X \in F_p, S(X\vec{v}) = \pi(X)S(\vec{v}). \qquad (8) $$

En particulier, on a le lemme suivant:

**Lemme 4.3.** Les S-box de Rescue sont additivement permutantes.

*Preuve.* $\forall \vec{v} \in \mathbb{F}_p^m, \forall X \in F_p, S(X\vec{v}) = X^\alpha S(\vec{v}) \text{ et } S^{-1}(X\vec{v}) = X^{\frac{1}{\alpha}} S^{-1}(\vec{v})$. $\square$

Le résultat principal permettant de chaîner les espaces affines est le suivant.

**Théorème 4.4.** Dans un tour F d'une structure de type SPN (S-box → application linéaire $M \rightarrow$ addition de constantes $\vec{r}$), un espace affine séparé de dimension 1 est envoyé sur un espace affine de dimension 1 selon la relation suivante :

$$ F(\vec{a} + X\vec{v}) = \vec{a} + X'\vec{v}. \qquad (9) $$

où

* $\vec{v}' = M \circ S(\vec{v})$,

* $\vec{a}' = M \circ S(\vec{a}) + \vec{r} - \lambda\vec{v}'$ où $\lambda$ est choisi afin que $\vec{a}'$ satisfasse les conditions définies en section 5,

* $X' = \pi(X) + \lambda$.
*Preuve.* Ce résultat se voit en procédant étape par étape dans la fonction de tour. Nous allons uniquement faire la preuve pour $S$, mais le résultat se déduit de manière équivalente dans le cas général en remplaçant $S$ par $S^{-1}$ puisque les deux sont additivement permutantes.

Puisque l'espace de départ est séparé, on a $\forall X \in \mathbb{F}_p, \forall 1 \le i \le m, a_i = 0$ ou $Xv_i = 0$, ce qui permet de noter $S(a_i + Xv_i) = S(a_i) + S(Xv_i)$.

Comme de plus $S$ est additivement permutante, on peut noter :

$$S(\vec{a} + X\vec{v}) = S(\vec{a}) + \pi(X)S(\vec{v}).$$

Ensuite, la multiplication par $M$ étant linéaire, on en déduit directement

$$M \circ S(\vec{a} + X\vec{v}) = M \circ S(\vec{a}) + \pi(X)M \circ S(\vec{v}).$$

On retrouve $\vec{v}' = M \circ S(\vec{v})$. Enfin, l'addition par $\vec{r}$ complète la fonction de tour, et une dernière manipulation de notation avec $\lambda$ permet d'écrire :

$$F(\vec{a} + X\vec{v}) = M \circ S(\vec{a}) + \vec{r} - \lambda\vec{v}' + (\pi(X) + \lambda)\vec{v}'.$$

Ce qui permet de conclure la preuve. □

## 4.3 Conditions pour chaîner des espaces affines séparés

Le **Théorème 4.4** nous dit qu'un espace affine séparé sera nécessairement envoyé sur un espace affine. En revanche, on n'a aucune garantie que l'espace affine d'arrivée soit lui-même un espace affine séparé. Afin de garantir que la chaîne soit préservée pour le tour d'après, il est possible d'établir les équations devant être vérifiées pour que l'espace affine d'arrivée soit également séparé. Plus grand est le nombre d'équations vérifiées, plus grande sera la chaîne.

**Théorème 4.5.** *L'image d'un espace affine séparé par un tour $F$ tel que dans le Théorème 4.4, en reprenant les mêmes notations, est également séparé si et seulement si :*

$$\forall i \in \text{supp}(\vec{v}'), \quad r_i = \lambda v'_i - M \circ S(\vec{a})_i. \qquad (10)$$

*Preuve.* L'espace affine d'arrivée est séparé si et seulement si $\forall i \in \text{supp}(\vec{v}'), a'_i = 0$, c'est-à-dire $M \circ S(\vec{a})_i + r_i - \lambda v'_i = 0$. □

## 4.4 Limites du chaînage dues à la matrice MDS

L'intérêt de formuler ce théorème ainsi est que l'on en extrait un système de $|\text{supp}(\vec{v}')|$ équations. Pour rappel, $\lambda$ est choisi de sorte à garder la représentation unique définie en **section 5**, c'est-à-dire afin de résoudre la première de ces équations.
Notons qu'en conséquence, si on a $|\text{supp}(\vec{v}')| = 1$, le système est forcément vérifié. De manière générale, réduire la taille du support des directions $\vec{v}$ successives de la chaîne réduit à son tour le nombre d'équations. Il n'est cependant pas possible que deux directions successives aient chacune un support de taille 1, car la matrice est MDS. Le résultat suivant va limiter notre capacité à faire des chaînes :

**Théorème 4.6.** Si M est une matrice MDS de taille $m \times m$, alors :

$$ \forall \vec{v} \in \mathbb{F}_p^m \setminus \{0\}, \quad |\text{supp}(\vec{v})| + |\text{supp}(M\vec{v})| \ge m + 1. \quad (11) $$

Ce résultat reste vrai en remplaçant $\text{supp}(M\vec{v})$ par $\text{supp}(M \circ S(\vec{v}))$.

*Preuve.* La matrice M étant MDS, le code de matrice génératrice $(I_m|M)$ atteint la borne de Singleton. Ainsi, tous ses mots sont de poids supérieur ou égal à $m+1$, et comme ses mots sont les concaténations de $\vec{v}$ et de $M\vec{v}$, on obtient l'équation (11).

La fin du théorème est vraie car $S(x) = 0$ si et seulement si $x = 0$, d'où $\text{supp}(\vec{v}) = \text{supp}(S(\vec{v}))$. En remplaçant $\vec{v}$ par $S(\vec{v})$ dans (10) et en appliquant cette égalité on obtient le résultat.

□

Ce résultat est la raison pour laquelle nous ne considérons que des espaces affines de dimension 1. En effet, pour qu'un espace affine de dimension 2 (de directions $\vec{v}_1$ et $\vec{v}_2$) soit séparé, il faut que $\text{supp}(\vec{v}_1) \cap \text{supp}(\vec{v}_2) = \emptyset$. Cela est possible, et le **Théorème 4.4** reformulé en conséquence reste vrai, mais l'espace affine d'arrivée de directions $M \circ S(\vec{v}_1)$ et $M \circ S(\vec{v}_2)$ ne peut pas être séparé :

**Lemme 4.7.** Soit $\vec{v}_1$ et $\vec{v}_2$ dans $\mathbb{F}_p^m$ tels que $\text{supp}(\vec{v}_1) \cap \text{supp}(\vec{v}_2) = \emptyset$. Alors $\text{supp}(M \circ S(\vec{v}_1)) \cap \text{supp}(M \circ S(\vec{v}_2)) \neq \emptyset$.

*Preuve.* Supposons qu'on ait $\vec{v}_1$ et $\vec{v}_2$ vérifiant $\text{supp}(\vec{v}_1) \cap \text{supp}(\vec{v}_2) = \emptyset$. Alors, $|\text{supp}(\vec{v}_1)| + |\text{supp}(\vec{v}_2)| \le m$ d'après le principe des tiroirs.

Si on avait de plus $\text{supp}(M \circ S(\vec{v}_1)) \cap \text{supp}(M \circ S(\vec{v}_2)) = \emptyset$, alors de même $|\text{supp}(M \circ S(\vec{v}_1))| + |\text{supp}(M \circ S(\vec{v}_2))| \le m$, d'où en ajoutant ces inégalités :

$$ |\text{supp}(\vec{v}_1)| + |\text{supp}(M \circ S(\vec{v}_1))| + |\text{supp}(\vec{v}_2)| + |\text{supp}(M \circ S(\vec{v}_2))| \le 2m. $$

Cela contredirait le **Théorème 4.6** qui stipule que la quantité de gauche doit être supérieure ou égale à $2m+2$. □

En résumé, nous avons maintenant des conditions suffisantes pouvant garantir la présence d'espaces affines entre les fonctions de tour. Il s'agit maintenant d'exploiter ce phénomène afin de créer une version "backdoorée" de Rescue.
# 5 Version "backdoorée" de la fonction de hachage de Rescue

## 5.1 Le problème CICO

Pour rappel, le mode d'opération de la fonction de hachage de Rescue cor-
respond à la structure éponge définie précédemment. L'état courant du cir-
cuit contient donc une partie taux, contenant l'entrée et la sortie de la
fonction, ainsi qu'une partie capacité, imposée à 0 au début du chiffre-
ment. L'idée est que la capacité ajoute un degré de confusion et ne doit
pas être maîtrisable par l'attaquant au cours de l'algorithme. Un des prob-
lèmes clés de l'état de l'art de l'analyse des fonctions éponge est le problème
CICO (Constrained-input constrained-output), qui doit être difficile. Sans
cela, les hypothèses sur lesquelles la sécurité de la fonction de hachage se
repose sont compromises. C'est le problème qu'il fallait résoudre dans le
cadre des ZK Hash Function Cryptanalysis Bounties 2021 de la fondation
Ethereum (https://www.zkhashbounties.info/), qui a attiré l'attention
de mon équipe avant mon stage [BBLP22]. Il est défini comme suit :

**Définition 5.1** (Le problème CICO). *Soit $f : \mathbb{F}_q^m \to \mathbb{F}_q^m$ une fonction, et $c < m$ un entier. Le problème CICO consiste à trouver $\vec{x} \in \mathbb{F}_q^m$ tel que les c derniers éléments de $\vec{x}$ et de $f(\vec{x})$ soient égaux à 0.*

**Remarque 1.** L'ensemble des éléments de $\mathbb{F}_q^m$ dont les c derniers éléments sont à 0 est un espace affine séparé de dimension r. De manière plus restreinte, nous pouvons considérer les espaces affines séparés de dimension 1 dont les c derniers éléments de la base et de l'origine sont à 0. Cette correspondance entre les entrées et sorties des solutions au problème CICO d'une part et les espaces affines séparés n'est pas anodine et sera exploitée pour la backdoor.

## 5.2 Schéma général de la backdoor

Le concept de *backdoor* en cryptographie correspond au scénario qui suit, dont les acteurs sont les *concepteurs malicieux*, les *utilisateurs* et les *crypt-analystes*. Le but des concepteurs malicieux est de créer une primitive cryptographique contenant une vulnérabilité cachée dont les cryptanalystes n'ont pas connaissance, tout en argumentant qu'elle est sécurisée pour qu'on l'utilise. Les concepteurs obtiennent ainsi le monopole des données chiffrées des utilisateurs.

La suite de ce rapport décrit la conception d'une version "backdoorée" de
Rescue, non pas pour l'implémenter en pratique, mais pour montrer que c'est
hypothétiquement faisable. Ainsi, si des concepteurs malicieux ont la même
idée à l'avenir, nous pourrons l'identifier. L'étude de backdoors potentielles
dans les standards cryptographiques est d'une importance capitale pour des
questions de confiance et de transparence entre les acteurs.
Par souci de simplicité, et car c'est un cas d'usage courant, nous allons prendre $c = 1$ et $t = 2$. Cependant, les méthodes décrites se généralisent tant que $c < r$ (condition nécessaire, cf. la **section 4.4**).

L'idée est la suivante : nous allons choisir des constantes de tour $r$ et une matrice $M$ de sorte à ce que les solutions du problème CICO soient les couples $(x, y)$ tels que $x$ et $y$ appartiennent respectivement à deux espaces affines séparés de dimension 1 notés $E_0$ et $E_N$. Cette notation est due au fait que nous allons construire une chaîne reliant $E_0$ et $E_N$. Un tel objectif fait sens vis-à-vis de la **Remarque 1**. En particulier, le dernier élément de la *base* et celui de l'origine doivent être à 0.

## 5.3 Calcul de $r$ et de $M$

Considérons une éventuelle chaîne $E_0 \to E_1 \to E_2... \to E_N$. En reprenant les notations de la **section 4**, nous allons écrire, pour tout $0 \le i \le N$ :

$$E_i = \vec{a}_i + X\vec{v}_i. \qquad (12)$$

Le cas échéant, le premier indice désigne le tour et le deuxième le fil. Pour rappel, Rescue utilise $S$ et $S^{-1}$. Nous allons écrire $S_i = S$ lorsque $i$ est pair et $S^{-1}$ lorsque $i$ est impair.

En juxtaposant les relations entre les espaces affines séparés et les conditions pour qu'ils se suivent définies en **section 4.3**, nous obtenons le système d'équations régissant cette chaîne ($\lambda_{i+1}$ est choisi pour satisfaire les conditions en **section 4.2**):

$$\forall 0 \le i \le N-1, \quad \left\{ \begin{array}{l} \overrightarrow{v_{i+1}} = M \circ S_i(\vec{v}_i) \\ \overrightarrow{a_{i+1}} = M \circ S_i(\vec{a}_i) + \vec{r}_i - \lambda_{i+1} \overrightarrow{v_{i+1}} \\ \forall j \in \text{supp}(v_{i+1}), a_{i+1,j} = 0. \end{array} \right. \qquad (13)$$

Pour la backdoor que nous souhaitons créer, on a de plus, vis-à-vis du problème CICO :

$$\left\{ \begin{array}{l} v_{0,m} = 0 \\ a_{0,m} = 0 \\ v_{N,m} = 0 \\ a_{N,m} = 0. \end{array} \right. \qquad (14)$$

De proche en proche, on a $\vec{v}_N = (M \circ S^{-1} \circ M \circ S)^{N/2}(\vec{v}_0)$. Il ne paraît pas évident au premier abord de trouver un $\vec{v}_0$ satisfaisant $v_{0,m} = 0$ et $v_{N,m} = 0$. C'est là que le choix de $M$ entre en jeu. Nous allons choisir $M$ tel qu'il existe un vecteur $\vec{v}$ avec $v_m = 0$ (qui sera, en fait, $\vec{v}_0$) et un scalaire $\mu$ vérifiant :

$$M \circ S(\vec{v}) = M \circ S^{-1}(\vec{v}) = \mu \vec{v}. \qquad (15)$$

Ce n'est pas tout à fait un vecteur propre de $M$. Cela joue en faveur des concepteurs malicieux, car il serait facile pour un cryptanalyste de dresser la
liste des sous-espaces propre de $M$ et de se rendre compte que l'un d'entre eux a sa dernière coordonnée constamment nulle. Cela paraîtrait peu naturel.

Le fait que Rescue utilise à la fois $S$ et $S^{-1}$ limite un peu notre choix de $\vec{v}_0$.

Pour simplifier notre tâche, nous allons prendre $\vec{v}_0$ tel que $S(\vec{v}_0) = S^{-1}(\vec{v}_0)$.

Comme $S(x) = x^{\alpha}$, cela revient à trouver des coefficients vérifiant l'équation :

$$x^{\alpha^2} = x. \qquad (16)$$

Autrement dit, les coefficients de $\vec{v}_0$ seront des racines ($\alpha^2 - 1$)-ièmes de l'unité. En particulier, on pourra forcément trouver des racines pgcd($\alpha^2 - 1, p - 1$)-ièmes primitives de l'unité. De plus, comme $\alpha$ et $p$ sont impairs,

$$\text{pgcd}(\alpha^2 - 1, p - 1) \geq 2. \qquad (17)$$

On préférerait éviter que tous les coefficients de $\vec{v}_0$ soient égaux, afin que $\vec{v}_0$ ne finisse pas comme un vecteur propre de $M$. Il est donc rassurant de constater qu'on pourra toujours définir $\vec{v}_0$ comme une succession de 1 et de $-1$ (en tant que racines 2-ièmes de l'unité) avec un 0 à la dernière coordonnée. Cependant, on peut créer un résultat un peu plus subtil en mettant des racines pgcd($\alpha^2 - 1, p - 1$)-ièmes si on le souhaite.

## 5.4 Exemple de calcul de $v_0$

Par exemple, expérimentalement, j'ai pu prendre $p = 1844674407370955155$, $\alpha = 3$ et $m = 3$ (paramètres des instances de ZK Hash Bounties). On a ici pgcd($\alpha^2 - 1, p - 1$) = 4, et j'ai donc pu définir, avec $\rho$ une racine 4-ième primitive (il y en a 2 possibles dans $\mathbb{F}_p$, vérifiant $\rho^2 = -1$) :

$$\vec{v}_0 = \begin{pmatrix} 1 \\ \rho \\ 0 \end{pmatrix}. \qquad (18)$$

Alors, on a bien :

$$S(\vec{v}_0) = S^{-1}(\vec{v}_0) = \begin{pmatrix} 1 \\ -\rho \\ 0 \end{pmatrix}. \qquad (19)$$

Cela nous aidera bien pour la suite. Il reste à calculer $M$ et les constantes de tours.

## 5.5 Calcul de la matrice MDS M

Maintenant que l'on a $\vec{v}_0$, il nous faut encore trouver $M$ MDS vérifiant l'équation (15). En pratique, il est possible de générer des matrices aléatoires vérifiant cette équation jusqu'à en trouver une qui soit MDS. En effet, la probabilité qu'une matrice aléatoire soit MDS n'est pas trop faible. C'est ce
que j'avais fait en premier lieu, en prenant comme critère calculatoire le fait qu'une matrice est MDS si et seulement si tout ses mineurs sont non nuls ([MS77], Ch.11).

Il est possible d'être un peu plus subtil. Un moyen assez courant de générer des matrices MDS est de plutôt prendre des matrices de Cauchy, dont la définition est plus constructive, et qui sont nécessairement MDS. La définition d'une matrice de Cauchy est comme suit :

**Définition 5.2 (Matrices de Cauchy).** Une matrice $M$ de taille $(m \times m)$ est dite de Cauchy si et seulement si il existe des scalaires $\sigma_1, \sigma_2, \dots, \sigma_m, \tau_1, \tau_2, \dots, \tau_m$ tels que, pour tout $1 \le i, j \le m$, $\sigma_i + \tau_j$ est non nul et le coefficient de $M$ en $(i, j)$ peut s'écrire $\frac{1}{\sigma_i + \tau_j}$. De manière plus visuelle :

$$ M = \begin{pmatrix} \frac{1}{\sigma_1 + \tau_1} & \frac{1}{\sigma_1 + \tau_2} & \cdots & \frac{1}{\sigma_1 + \tau_n} \\ \frac{1}{\sigma_2 + \tau_1} & \frac{1}{\sigma_2 + \tau_2} & \cdots & \frac{1}{\sigma_2 + \tau_n} \\ \vdots & \vdots & \ddots & \vdots \\ \frac{1}{\sigma_n + \tau_1} & \frac{1}{\sigma_n + \tau_2} & \cdots & \frac{1}{\sigma_n + \tau_n} \end{pmatrix}. \qquad (20) $$

Le calcul de $M$ consiste maintenant à calculer des coefficients $\sigma_1, \sigma_2, \dots, \sigma_m, \tau_1, \tau_2, \dots, \tau_m$ vérifiant les contraintes dues à l'équation (15), en remplaçant les coefficients de $M$ comme il se doit. Au total, cela nous donne $m$ équations pour $2m + 1$ inconnues (en n'oubliant pas $\mu$). Malheureusement, les équations obtenues ainsi ne sont pas linéaires. En multipliant chaque ligne $i$ par $(\sigma_i + \tau_1)(\sigma_i + \tau_2)\dots(\sigma_i + \tau_m)$, on peut les mettre sous la forme suivante (écrite pour $m = 3$ par souci de lisibilité) :

$$ \left\{ \begin{array}{l} (\sigma_1 - \tau_2)v_1^\alpha + (\sigma_1 - \tau_1)v_2^\alpha - \mu(\sigma_1 - \tau_1)(\sigma_1 - \tau_2)v_1 = 0 \\ (\sigma_2 - \tau_2)v_1^\alpha + (\sigma_2 - \tau_1)v_2^\alpha - \mu(\sigma_2 - \tau_1)(\sigma_2 - \tau_2)v_2 = 0 \\ (\sigma_3 - \tau_2)v_1^\alpha + (\sigma_3 - \tau_1)v_2^\alpha = 0. \end{array} \right. \qquad (21) $$

De manière générale, on obtient ainsi $m$ équations, dont $m-1$ de degré $m-1$ et une de degré $m-2$. On remarque que résoudre ce système ne pose pas de grand problème pour des petites valeurs de $m$, comme c'est typiquement le cas. Une autre observation est que si l'on fixe $\mu$ et $\tau_1, \dots, \tau_m$, on obtient $i$ équations univariées indépendantes de degré $m-1$ ($m-2$ pour la dernière).

Dans la pratique, j'ai tiré aléatoirement $\mu, \tau_1, \dots, \tau_m$ jusqu'à ce que le solveur univarié fourni par sage [The20] trouve pour chaque équation $i$ au moins une solution $\sigma_i$ différente de $-\tau_i$ (généralement, un seul tirage aléatoire me suffit). Des approches plus subtiles sont sans doute possibles pour le cas plus général, mais je n'ai pas trop voulu m'attarder là-dessus car le
besoin ne s'est pas fait ressentir. De plus, s'il était trop difficile de résoudre
le système, il serait toujours possible de générer une matrice MDS aléatoire,
pas forcément de Cauchy.

5.6 Calcul des constantes de tour

Nous avons à présent $\vec{v}_0$ et une matrice MDS (de Cauchy) $M$ vérifiant
$M \circ S(\vec{v}_0) = M \circ S^{-1}(\vec{v}_0) = \mu \vec{v}_0$. Avec ça, dans une éventuelle chaîne
d'espaces affines partant de $E_0$, les bases successives seront nécessairement
des multiples de $\vec{v}_0$. En particulier, le dernier coefficient de la base de l'espace
en sortie $E_N$ sera nécessairement 0.

Comme on a pris un $\vec{v}_0$ dont tous les coefficients sauf le dernier sont non
nuls (ce sont des racines de l'unité), et comme $E_0$ doit être un espace affine
séparé dont le dernier coefficient est constamment nul, il est nécessaire de
prendre comme origine $\vec{a}_0 = \vec{0}$.

Il ne reste plus qu'à trouver des constantes de tour $\vec{r}_1, \vec{r}_2, \dots, \vec{r}_N$ telles qu'on ait bien une chaîne d'espaces affines séparés commençant par $E_0$ et finissant par $E_N$. De plus, il faut que le dernier coefficient de l'origine $\vec{a}_N$ soit nul.

Par nos choix de $\vec{v}_0$ et $M$, on a :

$$
\forall 0 \le i \le N, \operatorname{supp}(\vec{v}_i) = \{1, 2, \dots, m-1\}. \quad (22)
$$

Les conditions du **Théorème 4.5** pour le tour $1 \le i \le N$ se réécrivent donc :

$$
\forall 1 \le j \le m-1, (\vec{r}_i)_j = \lambda_i(\vec{v}_i)_j - M \circ S(\overrightarrow{a_{i-1}})_j . \quad (23)
$$

Pour rappel, le paramètre $\lambda_i$ est choisi pour chaque espace $i$ de sorte à ce que
le premier coefficient $(\vec{a}_i)_j$ tel que $(\vec{v}_i)_j \neq 0$ soit nul (choix d'un représentant
dans la classe des origines possibles). Cela équivaut ici à prendre $\lambda_i$ satis-
faisant la première de ces $m-1$ équations. Il est donc tout à fait possible
pour le calcul de $\vec{r}_i$ de tirer $(\vec{r}_i)_1$ (et $(\vec{r}_i)_m$ qui n'a pas de contrainte) aléa-
toirement dans $\mathbb{F}_p$ et d'injecter l'expression de $\lambda_i$ dans les autres équations,
ce qui donne des équations explicites pour calculer $\vec{r}_i$ :

$$
\forall 1 \le i \le N, \left\{
\begin{array}{l}
(\vec{r}_i)_1, (\vec{r}_i)_m \in \mathbb{F}_p \\
\forall 2 \le j \le m-1, (\vec{r}_i)_j = \frac{(\vec{r}_i)_1 + M \circ S(\vec{a}_i)_1}{(\vec{v}_i)_1} (\vec{v}_i)_j - M \circ S(\overrightarrow{a_{i-1}})_j.
\end{array}
\right.
\tag{24}
$$

Il y a une petite exception pour le dernier tour, où $(\vec{r}_N)_m$ doit être pris de
sorte à ce que $(\vec{a}_N)_m = 0$ pour résoudre le problème CICO. Il faut donc,
comme pour les autres coordonnées :

$$
(\vec{r}_N)_m = \frac{(\vec{r}_N)_1 + M \circ S(\vec{a}_N)_1}{(\vec{v}_N)_1} (\vec{v}_N)_m - M \circ S(\overrightarrow{a_{N-1}})_m \quad (25)
$$

Par comparaison avec un vrai tirage aléatoire uniforme des constantes de
tour, la distribution ainsi obtenue est restreinte par la présence des $m-2$
contraintes à chaque tour ($m-1$ pour le dernier tour). On peut voir, sur l'équation (23), que ça revient à prendre, pour tout $i$, $\vec{r}_i|_{\text{supp}(\vec{v}_i)}$ aléatoirement dans un espace affine de base $\vec{v}_i|_{\text{supp}(\vec{v}_i)}$ et d'origine $-M \circ S(\vec{a}_{i-1})|_{\text{supp}(\vec{v}_i)}$. Ce motif paraît difficilement identifiable sans connaissance préalable de la technique utilisée pour insérer la backdoor. De plus, le résultat a l'air assez "chaotique" pour ne pas éveiller de soupçons. C'est particulièrement le cas lorsque $m=3$, où chaque vecteur $\vec{r}_i$ n'a qu'une contrainte linéaire. Par contre, grâce à ces travaux, une telle backdoor serait maintenant facilement détectée.

Finalement, par construction, ce choix de $M$ et des $\vec{r}_i$ garantit que l'espace en entrée $E_0$ sera envoyé sur l'espace en sortie $E_N$, les deux ayant leur dernière coordonnée constamment nulle. Le constructeur possède donc exactement $p$ solutions du problème CICO, ce qui ouvre potentiellement la porte à diverses vulnérabilités.

J'ai pu réaliser une implémentation de cette version "backdoorée" de Rescue en **sage**, et j'ai pu vérifier qu'elle renvoie les sorties correctes sur plusieurs entrées. J'ai aussi pu vérifier que la backdoor est exploitable pour générer facilement des solutions au problème CICO.

Une chose importante à constater est que notre construction n'implique aucune autre chaîne d'espaces affines sur $N$ tours. On peut même s'attendre à ce qu'il n'y ait aucune chaîne de longueur supérieure ou égale à 3, ce qui sera expliqué dans la prochaine partie. Un cryptanalyste ne connaissant pas l'astuce ne risque donc pas de tomber par hasard sur une chaîne que nous n'avons pas considérée. Avoir trop de solutions au problème CICO mettrait en péril la crédibilité de la backdoor.

# 6 Observations et améliorations possibless

## 6.1 Limites de la version "backdoorée"

Outre le fait que la version "backdoorée" fonctionne comme on voudrait, il peut y avoir quelques problèmes vis-à-vis de sa crédibilité. En particulier, la construction que l'on a faite pour $m=3$ possède un défaut : comme l'origine de $E_0$ est nulle, $E_0$ est un espace vectoriel. Le problème est que notre chiffrement envoie le vecteur $\vec{0}$ sur un vecteur de $E_N$, c'est-à-dire que $\vec{0}$ et son image forment une solution du problème CICO. $\vec{0}$ est une entrée particulière, et un chiffrement $F$ dont les paramètres sont pris aléatoirement n'a une probabilité que de $\frac{1}{p} \approx 2^{-64}$ d'avoir $(\vec{0}, F(\vec{0}))$ comme solution du problème CICO. Un cryptanalyste pourrait avoir l'idée de mettre $\vec{0}$ en entrée et se rendre compte qu'il y a un problème.

Le seul moyen de contourner ce problème est de faire en sorte que $\vec{a}_0 \neq 0$. Comme $E_0$ est un espace séparé dont la dernière coordonnée est constamment nulle, cela implique nécessairement que $|\text{supp}(\vec{v})| \leq m-2$. Cette inégalité
doit être conciliée avec la relation $M \circ S(\vec{v}) = \mu \vec{v}$, et en particulier le fait que la matrice est MDS. En effet, on a le lemme suivant :

**Lemme 6.1.** Si $M$ est MDS et $M \circ S(\vec{v}) = \mu \vec{v}$ pour certains $\mu \neq 0$ et $\vec{v}$, alors :

$$2|\mathrm{supp}(\vec{v})| \geq m + 1. \qquad (26)$$

*Preuve.* On a $\mathrm{supp}(M \circ S(\vec{v})) = \mathrm{supp}(\mu \vec{v}) = \mathrm{supp}(\vec{v})$. L'inégalité découle du **Théorème 4.6** relatif aux matrices MDS. $\square$

Donc si on a $|\mathrm{supp}(\vec{v})| \leq m - 2$, il faut nécessairement $2m - 4 \geq m + 1$, c'est-à-dire $m \geq 5$. Ce défaut est forcément présent dans le cas $m = 3$ sur lequel je me suis concentré. Réciproquement, on peut le corriger dans le cas $m \geq 5$, en prenant un $\vec{v}_0$ dont le support est de taille $m - 2$ et $\vec{a}_0$ dont le support est de taille 1, de sorte que :

$$\mathrm{supp}(\vec{v}_0) \cup \mathrm{supp}(\vec{a}_0) = 1, 2, \dots, m - 1. \qquad (27)$$

Le calcul de la matrice $M$ de Cauchy de la **section 5.5** est pratiquement inchangé, si ce n'est qu'une des équations de degré $m-1$ devient une équation de degré $m-2$. C'est assez encourageant. De manière générale, prendre un vecteur $\vec{v}$ de support plus petit (mais toujours $\geq \frac{m+1}{2}$) simplifie le calcul de $M$, au risque de diminuer le nombre de solutions.

Une deuxième limite potentielle (néanmoins rassurante du point de vue honnête) est que si l'on connaît la méthode de construction, ou du moins une partie de cette méthode, il est possible de trouver l'espace $E_0$ donnant $p$ solutions du problème CICO. Dans le cas $m = 3$, c'est facile : en utilisant le fait que $\vec{a}_0 = \vec{0}$ et l'équation (17) pour $i = 1$, on trouve que :

$$\frac{\vec{r}_{02}}{\vec{r}_{01}} = \frac{\vec{v}_{02}}{\vec{v}_{01}}. \qquad (28)$$

Et avec $\frac{\vec{v}_{02}}{\vec{v}_{01}}$, on déduit un représentant possible $\begin{pmatrix} 1 \\ \frac{\vec{v}_{02}}{\vec{v}_{01}} \\ 0 \end{pmatrix}$ de la base de $E_0$.

Lorsque $m \neq 3$ et $\vec{a}_0 \neq \vec{0}$, des méthodes similaires sont possibles. Si l'on connaît les détails de la méthode, il suffit de tester tous les $\vec{v}_0$ possibles (ses coefficients étant chacun 0 ou une racine pgcd($\alpha, p-1$)-ième de l'unité. Sinon, on peut chercher les solutions de l'équation (13). On peut calculer les coefficients $\sigma_1, \dots, \sigma_m, \tau_1, \dots, \tau_m$ à partir de la matrice $M$ et d'utiliser le système décrit en (15) pour retrouver $\vec{v}_0$ ($m$ équations de degré $\alpha$ à $m$ inconnues). Quoi qu'il en soit, les méthodes ne manquent pas.
## 6.2 Faisabilité dans un chiffrement honnête

La première question que je me suis posé une fois la backdoor implémentée, c'est de savoir si on peut appliquer la même stratégie au vrai chiffrement. Cela reviendrait à trouver des chaînes d'espaces affines permettant de ré-soudre le problème CICO, ou a minima de le simplifier. Cela ne donne malheureusement (ou heureusement) pas grand chose.

Lorsqu'on considère un chiffrement honnête, on peut considérer que les constantes de tour $\vec{r}_1, ..., \vec{r}_N$ sont prises uniformément aléatoirement dans $\mathbb{F}_q^m$ et fixées. De même, on considère que $M$ est une matrice MDS aléatoire.

Considérons le premier tour. En entrée, nous pouvons mettre des espaces affines séparés tels que $(\vec{v}_0)_m = (\vec{a}_0)_m = 0$. Le nombre d'espaces affines distincts possibles à mettre en entrée est dicté par le théorème suivant :

**Lemme 6.2.** Pour tous $m \ge 2$ et $p$ premier, le nombre d'espaces affines séparés de dimension 1 distincts de $\mathbb{F}_q^m$ est :

$$A_{p,m} = \frac{1}{p-1} \left[ (2p-1)^m - p^m \right] \underset{p \to \infty}{\sim} (2^m - 1)p^{m-1}. \quad (29)$$

et le nombre d'espaces affines séparés de dimension 1 distincts dont la dernière coordonnée est constamment nulle est $A_{p,m-1}$.

*Preuve.* On dénombre selon un entier $k$ allant de 1 à $m$ qui représente la taille de supp($\vec{v}$). À $k$ fixé, il y a $\binom{m}{i}$ support possibles. La représentation unique de la base et de l'origine des espaces affines séparés fixe la première coordonnée non nulle de $\vec{v}$ à 1 et les coordonnées de $\vec{a}$ dans supp($\vec{v}$) à 0. Il reste $p-1$ choix pour les $k-1$ autres coordonnées de $\vec{v}$ et $p$ choix pour les $m-k$ autres coordonnées de $\vec{a}$. Ainsi :

$$ 
\begin{align*}
A_{p,m} &= \sum_{k=1}^{m} \binom{m}{k} (p-1)^{k-1} p^{m-k} \\
&= \frac{1}{p-1} \left( \sum_{k=0}^{m} \binom{m}{k} (p-1)^k p^{m-k} \right) - \frac{p^m}{p-1} \\
&= \frac{1}{p-1} \left[ (2p-1)^m - p^m \right] \\
&\underset{p \to \infty}{\sim} (2^m - 1) p^{m-1}.
\end{align*}
$$

Le cas où on se limite aux espaces dont la dernière coordonnée est constamment nulle revient à faire le même dénombrement en éliminant la dernière coordonnée, il y en a donc $A_{p,m-1}$.

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

Si l'on prend un de ces espaces affines et qu'on le fixe, on peut évaluer les chances que son image après le $1^{er}$ tour reste un espace affine séparé. Pour
cela, il faut que les contraintes sur les constantes de tour en (9) soit vérifiées,
en considérant que $\lambda$ est pris de sorte à satisfaire la première de ces équations
(cf section 5.6). Il reste $|\text{supp}(M \circ S(\vec{v}))| - 1$ contraintes, et comme les
$\vec{r}_i$ sont considérés uniformément aléatoires et indépendants, chacune de ces
équations sera résolue indépendamment des autres avec une probabilité $\frac{1}{p}$.

Cela fait au total une probabilité $(\frac{1}{p})^{|\text{supp}(M \circ S(\vec{v}))|-1}$ que l'espace consid-
éré au début ait comme image un espace affine séparé. Sur $N$ tours, cette
probabilité devient $(\frac{1}{p})^{N|\text{supp}(M \circ S(\vec{v}))|-1}$. Avec $A_{p,m-1} \approx (2^{m-1} - 1)p^{m-2}$
espaces possibles au départ pour trouver des solutions au problème CICO et
$|\text{supp}(M \circ S(\vec{v}))| \ge 1$, on en déduit que trouver une chaîne sur $m$ tours ou
plus a une probabilité inférieure à $2^m/p$. C'est donc très improbable.

De manière générale, on peut vérifier que la probabilité de trouver des
chaînes de longueur strictement supérieure à 3 est également de l'ordre de
$\frac{1}{p}$ (nonobstant l'action de $N$ et $m$ qui resteront par design petits), mais
par souci de brièveté je n'entrerai pas en détail dans les calculs justifiant
cela. On en conclut (et on peut observer expérimentalement) qu'il n'est pas
réalisable de trouver des chaînes d'espaces affines simplifiant réellement le
problème. Les instances honnêtes de Rescue ne sont donc pas vulnérables à
cette approche, et les cas simplifiés qui ont aiguillé le début de mon étude
restent marginaux en général.

7 Conclusion et remerciements

J'ai été agréablement surpris quand j'ai constaté que le phénomène des
hautes uniformités différentielles observé expérimentalement pouvait être
modélisé et généralisé dans un contexte plus attrayant. Tout ce processus
m'a permis de comprendre plus en profondeur les subtilités des chiffrements
par blocs, en plus d'apporter une nouvelle approche sous la forme des chaînes
d'espaces affines. Cette approche ne fonctionne pas sur des instances hon-
nêtes de Rescue, ce qui est, malgré une légère déception de ma part, rassurant
pour les concepteurs. Néanmoins, d'autres chiffrements par blocs pourraient
être sujets à ce genre de propagation de structures algébriques, et cela con-
stituera la suite de mes études.

Je remercie mon directeur de stage, Léo Perrin, pour m'avoir guidé et
présenté à la communauté des cryptographes au cours de mon stage. Je
remercie également Clémence Bouvier, Augustin Bariant, Jules Baudrin et
Anne Canteaut pour m'avoir écouté dans mes débâcles et donné des conseils
souvent précieux.
Appendice A - Bibliographie

[AAB$^{+}$19] Abdelrahaman Aly, Tomer Ashur, Eli Ben-Sasson, Siemen Dhooghe, and Alan Szepieniec. Design of symmetric-key prim- itives for advanced cryptographic protocols. Cryptology ePrint Archive, Report 2019/426, 2019. https://eprint.iacr.org/ 2019/426.

[BBLP22] Augustin Bariant, Clémence Bouvier, Gaëtan Leurent, and Léo Perrin. Practical Algebraic Attacks against some Arithmetization-oriented Hash Functions. Research report, In- ria, January 2022.

[BCCLC06] Thierry P Berger, Anne Canteaut, Pascale Charpin, and Yann Laigle-Chapuy. On almost perfect nonlinear functions over $F_{2^k}$. *IEEE Transactions on Information Theory*, 52(9):4160–4170, 2006.

[BCL$^{+}$20] Tim Beyne, Anne Canteaut, Gregor Leander, Maria Naya-Plasencia, Leo Perrin, and Friedrich Wiemer. On the security of the rescue hash function. Cryptology ePrint Archive, Paper 2020/820, 2020. https://eprint.iacr.org/2020/820.

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

[D$^{+}$15] Morris J Dworkin et al. Sha-3 standard: Permutation-based hash and extendable-output functions. 2015.

[DR02] Joan Daemen and Vincent Rijmen. *The Design of Rijndael: AES - The Advanced Encryption Standard (Information Security and Cryptography)*. Springer, 1 edition, 2002.

[GO94] Oded Goldreich and Yair Oren. Definitions and properties of zero-knowledge proof systems. *Journal of Cryptology*, 7(1):1–32, 1994.

[Gol98] Oded Goldreich. Secure multi-party computation. *Manuscript. Preliminary version*, 78:110, 1998.

[MS77] Florence Jessie MacWilliams and Neil James Alexander Sloane. *The theory of error correcting codes*, volume 16. Elsevier, 1977.

[Sha49] Claude E. Shannon. Communication theory of secrecy systems. *Bell Systems Technical Journal*, 28(4):656–715, 1949.

[The20] The Sage Developers. *SageMath, the Sage Mathematics Software System (Version 9.1)*, 2020. https://www.sagemath.org/