# Cryptanalyse de primitives orientées-arithmétisation basées sur des boîtes S split-and-lookup

Antoine Bak

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

## To cite this version:

Antoine Bak. Cryptanalyse de primitives orientées-arithmétisation basées sur des boîtes S split-and-lookup. Informatique [cs]. 2024. hal-04910908

HAL Id: hal-04910908

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

Submitted on 24 Jan 2025

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_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Cryptanalyse de primitives orientées-arithmétisation basées sur des boîtes S *split-and-lookup*

Antoine Bak

encadré par Léo Perrin

équipe COSMIQ, INRIA Paris

9 septembre 2024

## Le contexte général

Ce stage a pour objet l'analyse de certaines primitives symétriques *orientées arithmétisation*, c'est-à-dire ayant été définies avec des contraintes de composabilité avec des protocoles de preuves à divulgation nulle de connaissance. On étudie en particulier une nouvelle stratégie de design basée sur les boîtes S *split-and-lookup*.

Ce problème vient de nouveaux besoins de fonctions de hachage utilisées pour améliorer l'efficacité des protocoles de preuves, demandant à la fois une grande efficacité en temps d'évaluation, mais également que l'équation $H(x) = y$ puisse être décrite par un circuit de faible complexité multiplicative. Les *split-and-lookups* semblent être une bonne solution à ce problème en raison de leur rapidité d'évaluation et de leurs garanties de sécurité face aux attaques algébriques.

Les fonctions de hachage REINFORCED CONCRETE, TIP5 et MONOLITH se basent toutes les trois sur des *split-and-lookups*. Il n'y a à l'heure actuelle aucune cryptanalyse de ces primitives autre que celle donnée par les designers.

## Le problème étudié

On cherche à évaluer la sécurité de ces primitives en trouvant des attaques et des critères pertinents pour faire certains choix dans le design de ce type de fonction.

Une telle analyse permet notamment d'avoir une meilleure idée de la marge de sécurité de ces fonctions de hachage et donne à de futurs designers des outils pour mieux choisir les boîtes S pour leurs primitives.

Les designs se basant sur des *split-and-lookups* étant récents (la première date de 2021), aucune cryptanalyse autre que celle des designers n'a été effectuée sur ces primitives.

## La contribution proposée

On donne dans ce rapport une attaque par collision sur une version de TIP5 réduite à 4 tours (sur 5) et à une capacité de 320 bits. Cette attaque se base sur des manières de contourner les boîtes *split-and-lookups* afin de mener une attaque algébrique. Cela contredit l'analyse de sécurité des auteurs qui donnaient une marge de sécurité de 2 tours. On donne également un distingueur intégral sur la permutation complète sans la première couche de boîtes S.

Ces attaques n'exploitant que la présence de monômes dans la permutation, elles ne dépendent en particulier pas du choix des boîtes *split-and-lookups*.

Enfin, nous avons trouvé une manière efficace d'évaluer les probabilités de certaines approximations linéaires des *split-and-lookups*. Appliquée à MONOLITH et TIP5, cette méthode donne de meilleures approximations linéaires que celles prévues par les designers dans leurs analyses de sécurité.
## Les arguments en faveur de sa validité

Notre analyse de sécurité améliore celle des designers de TIP5 en donnant une attaque sur 4 tours, au lieu de 2 selon les designers. Cette attaque a été implémentée et fonctionne en pratique.

Cette attaque dépend cependant de manière cruciale de la structure de TIP5 et de la présence de monômes dans la couche de boîte S. Elle ne s'applique donc ni à REINFORCED CONCRETE, ni à MONOLITH. Elle reste également limitée à 4 tours et il n'y a pas de manière immédiate de la prolonger à plus de tours.

En ce qui concerne l'algorithme de calcul des approximations linéaires, il permet une évaluation efficace de la probabilité d'une approximation linéaire pour certaines constantes. Cet algorithme a en particulier été appliqué à TIP5, MONOLITH (donnant des meilleurs approximations linéaires que celles prévues par les designers) et dans une moindre mesure à REINFORCED CONCRETE.

## Le bilan et les perspectives

Ce rapport donne une première analyse de la sécurité de TIP5 et donc une meilleure idée de sa marge de sécurité. On a également apporté des outils permettant d'analyser les approximations linéaires des boîtes S *split-and-lookup*, ce qui sera utile dans de futurs designs.

Il reste à présent à trouver des fonctions *split-and-lookup* conciliant une bonne efficacité en terme d'implémentation en opérations processeur (comme MONOLITH) avec des bonnes propriétés en terme d'approximations linéaires. On peut de plus chercher des décompositions des nombres premiers utilisés dans REINFORCED CONCRETE donnant lieu à moins de points fixes.

Le problème de trouver des attaques sur des versions réduites de MONOLITH et REINFORCED CONCRETE meilleures que celles annoncées par les designers reste ouvert.
# Table des matières

<table><tr><td>1 Introduction</td><td>1</td></tr><tr><td>2 Préliminaires</td><td>2</td></tr><tr><td>2.1 Notations</td><td>2</td></tr><tr><td>2.2 Structure SPN</td><td>2</td></tr><tr><td>2.3 Résolution d'équations polynoniales</td><td>3</td></tr><tr><td>2.4 Fonctions de hachage</td><td>3</td></tr><tr><td>2.5 Attaques statistiques</td><td>4</td></tr><tr><td>2.6 Boîte S split-and-lookup</td><td>5</td></tr><tr><td>3 Analyse structurelle de Tip5</td><td>6</td></tr><tr><td>3.1 Design de Tip5</td><td>6</td></tr><tr><td>3.2 Exploiter les monômes pour sauter les 3 premiers tours</td><td>7</td></tr><tr><td>3.3 Contourner le dernier tour</td><td>9</td></tr><tr><td>3.4 Applications</td><td>9</td></tr><tr><td>4 Approximations linéaires des boîtes split-and-lookup</td><td>12</td></tr><tr><td>4.1 Calcul de la corrélation linéaire</td><td>12</td></tr><tr><td>4.2 Calcul des approximations linéaires : cas de petits coefficients</td><td>13</td></tr><tr><td>4.3 Application : cas de TIP5, MONOLITH et REINFORCED CONCRETE</td><td>16</td></tr><tr><td>5 Conclusion</td><td>18</td></tr><tr><td>A Preuve de la bijectivité des boîtes S split-and-lookup</td><td>21</td></tr><tr><td>B Bilan des approximations linéaires trouvées</td><td>21</td></tr></table>

# 1 Introduction

Les récents développements dans les protocoles avancés comme les SNARKs, STARKs et Bulletproofs ont motivé l'introduction de nouvelles primitives dites *orientées arithmétisation*. À la différence des primitives classiques définies sur $\mathbb{F}_2$ cherchant une efficacité en terme d'implémentation sur les processeurs, celles-ci sont définies sur un corps $\mathbb{F}_q$ avec $q$ de grande taille et visent à minimiser le nombre de multiplications dans ce corps. Plus précisément, vérifier $H(x) = y$ doit se faire en évaluant un circuit arithmétique de complexité multiplicative la plus faible possible.

On peut diviser les primitives orientées arithmétisation en 3 familles, reposant à chaque fois sur des stratégies différentes en suivant la classification de [Rec23] :

- Type I : H s'écrit comme une suite d'opérations de bas degré.

- Type II : H s'écrit comme une suite d'opérations CCZ-equivalentes à des fonctions de bas degré.

- Type III : on utilise des boîtes S split-and-lookup afin de casser les structures algébriques introduites par la faible complexité multiplicative.

On s'intéresse dans ce rapport aux primitives de Type III [GKL$^+$21, SLS$^+$23, GKL$^+$23], qui ont été conçues dans le but d'être efficaces en terme de temps d'évaluation sans perdre trop de performances pour l'arithmétisation. L'idée derrière ces designs est que les boîtes split-and-lookup protègent les primitives des attaques algébriques et permettent donc de réduire fortement le nombre de tours. Ces primitives ont pour le moment reçu peu d'attention de la part des cryptanalystes, les seules analyses de ces primitives provenant des designers.

Une première approche pour étudier ces designs provient de la cryptanalyse structurelle. Cela consiste à partir de la structure générale d'un design et à trouver des bornes inférieures sur le nombre de tours, branches... pour avoir une construction sécurisée. On sait par exemple qu'un chiffrement par bloc de la forme SASAS où S représente une rangée de boîtes S arbitraires et A une couche affine ne peut pas être sécurisé [BS01]. Ce résultat a ensuite été généralisé à un
nombre arbitraire de tours, moyennant une condition sur la taille des boîtes S par rapport à la
taille de l'état interne [BKP16].

On se propose dans ce rapport d'étudier la structure de TIP5 en donnant des conditions suffi-
santes sur les paramètres d'une permutation de la forme de TIP5 pour ne pas aboutir à une fonc-
tion de hachage sécurisée. On exploitera pour cela la présence de monômes, dont les propriétés
homomorphes ont déjà conduit à des attaques sur RESCUE [BBLP22, BCP23]. On verra en
particulier une attaque par collision sur une permutation de la forme A(S|Mon)A(S|T)A(S|T)A
(Mon représente des monômes, T une permutation de bas degré, S arbitraire) lorsque t >
max(c, s) + c + s, d > s avec t le nombre de branches, c la capacité, s le nombre de boîtes S non
monomiales par tour et d la taille du digéré. Cela donne en particulier une bien meilleure idée
de la sécurité de TIP5, puisque les analyses initiales concluaient que 3 tours étaient suffisants
pour la rendre sécurisée, là où notre analyse montre que les 5 tours sont en fait nécessaires.

On s'intéresse également aux distingueurs intégraux à clé connue et à leurs généralisations
sur $\mathbb{F}_p$ [SWMSP17, BCD<sup>+</sup>20]. On montre que lorsque $t > 2s$, une permutation de la forme
ASA(S|Mon)A(S|T)A(S|T)A a un ensemble d'entrées-sorties sommant à 0 de taille $p$. Dans le
cas A(S|T)A(S|Mon)A(S|T)A(S|T)A, $t > 3s$, ce résultat peut être affiné et donne une attaque
de complexité $max(deg T^{-1}, deg \text{Mon} \cdot deg T^2) + 2$. On note que ces résultats s'appliquent à TIP5
sans sa première couche de boîtes S.

Ces résultats n'étudient que la structure de la permutation, sans regarder les détails des
choix de boîtes S, matrices MDS, constantes... La seconde partie de ce rapport donne donc des
méthodes pour étudier les boîtes *split-and-lookup* introduites dans ces designs. Les critères de
choix de ces boîtes S ont été assez peu étudiés par les designers, les seuls auteurs ayant explicité
des critères étant ceux de MONOLITH qui avaient pour critère l'efficacité en terme de nombre
d'opérations machines et l'absence de points fixes autres que ceux demandés par la construction
*split-and-lookup*. On s'intéressera en particulier aux approximations linéaires de ces boîtes S,
puisqu'elles peuvent conduire à des attaques algébriques par linéarisation. On donne ici une
méthode permettant de calculer le nombre de solutions d'une équation linéaire $S(x) = a \cdot x + b$,
qui est efficace lorsque $a$ s'écrit comme $p/q$ avec $|p|, |q|$ petits. Nous appliquons ensuite cette
méthode aux boîtes S de TIP5 et MONOLITH, trouvant des approximations linéaires qui ont des
probabilités significativement plus élevées que celles trouvées par les auteurs dans leurs analyses
de sécurité. Si nos résultats ne conduisent pas directement à une attaque, ils donnent cependant
des critères permettant de comparer de telles boîtes S, ce qui pourrait être utile dans de futurs
designs.

2 Préliminaires

2.1 Notations

Dans ce qui suit, on note $\mathbb{F}_q$ le corps fini à $q$ éléments, $[a, b]$ l'intervalle entier $\{a \dots b\}$,
$Z_{s_i} = [0, s_i - 1]$, $A \coprod B$ l'union disjointe de A et B. Pour $a, b \in \mathbb{F}_p^n$, on note $a \cdot b = \sum_{i=1}^n a_i b_i$.

2.2 Structure SPN

La permutation TIP5 est définie par une structure *substitution-permutation network* (SPN).
Nous en donnons ici une définition.

**Définition 1 (Structure SPN)** On dit que $f: \mathbb{F}_p^t \to \mathbb{F}_p^t$ est une permutation SPN si elle est de la forme $f = f_R \circ \cdots \circ f_1$, avec pour tout $i$, $f_i(\cdot) = A_i \circ S(\cdot)$ où :

— $A_i$ est une fonction affine sur $\mathbb{F}_p^t$ invertible.

— $S(x) = (S_1(x_1) \dots S_{t/m}(x_{t/m}))$, avec $m|t$, $x_j \in \mathbb{F}_p^m, S_j: \mathbb{F}_p^m \to \mathbb{F}_p^m$ une permutation.

Dans le cas de TIP5, on a R = 5, m = 1. La structure de TIP5 est représentée Figure 2.
## 2.3 Résolution d'équations polynomiales

Ce rapport utilisera des résultats de complexité de résolution d'équations polynomiales. On énonce dans cette section les résultats connus pour la résolution d'équations univariées et multivariées.

**Théorème 1 (Résolution d'équations univariées [BBLP22])** Soit $P \in \mathbb{F}_q[X]$, $\delta = \text{deg } P$. Il est possible de trouver l'ensemble des racines de $P$ dans $\mathbb{F}_q$ en $O(\delta \cdot \log \delta \cdot (\log \delta + \log q) \log \log \delta)$ opérations arithmétiques dans $\mathbb{F}_q$.

L'idée de l'algorithme est de commencer par calculer $R = X^q - X$ mod $P$ par exponentiation rapide. On prend ensuite le pgcd de $R$ et $P$, dont les racines sont exactement les racines de $P$ dans $\mathbb{F}_q$. On obtient alors en général un polynôme de degré constant, que l'on peut factoriser efficacement.

**Résolution d'équations multivariées [BFS15, FGHR14]** : Soit un système d'équations polynomiales $P_1(X_1, \dots, X_n) = \dots = P_n(X_1, \dots, X_n) = 0$, avec $\text{deg } P_i = d_i$. Sous certaines hypothèses<fnref n="1" />, il est possible d'en trouver une solution avec complexité<fnref n="2" />

$$O\left(nD_{reg}\binom{n + D_{reg} - 1}{D_{reg}}^{\omega} + nd^{\omega}\right)$$

où $D_{reg}$ est le degré de régularité du système qui peut être borné par $D_{reg} \le 1 + \sum_{i=1}^{n}(d_i - 1)$, $d$ est le degré de l'idéal $(P_1, \dots, P_n)$ qui peut être borné par $d \le \prod_{i=1}^{n}d_i$ et $2 \le \omega \le 3$ est l'exposant de l'algorithme de multiplication de matrices (que nous prendrons égal à 3 dans nos analyses).

## 2.4 Fonctions de hachage

L'objet de ce rapport est l'étude de fonctions de hachage définies sur $\mathbb{F}_p$. On rappelle donc ici certaines définitions et constructions utiles dans l'étude des fonctions de hachage.

**Définition 2 (Fonction de hachage)** On dit que $H: \mathbb{F}_p^* \to \mathbb{F}_p^d$ est une fonction de hachage cryptographique si les trois problèmes suivants sont difficiles :

- Preimage resistance : étant donné $y \in \mathbb{F}_p^d$, trouver $x \in \mathbb{F}_p^*$ tel que $H(x) = y$.

- Second preimage resistance : étant donné $x_1 \in \mathbb{F}_p^*$, trouver $x_2 \in \mathbb{F}_p^*$ tel que $H(x_1) = H(x_2)$.

- Collision resistance : trouver $x_1, x_2 \in \mathbb{F}_p^*$ tels que $H(x_1) = H(x_2)$.

Dans ce rapport, on étudiera en particulier la résistance de Tip5 aux collisions. On rappelle que le paradoxe des anniversaires permet toujours de trouver une collision avec grande probabilité en évaluant une fonction de hachage en environ $p^{d/2}$ points choisis aléatoirement. Une attaque par collision est donc une attaque trouvant une collision plus efficacement que l'attaque des anniversaires.

La fonction de hachage Tip5 peut être définie à partir de la permutation associée par la construction suivante.

**Définition 3 (Sponge construction [BDPVA07])** Soit $f: \mathbb{F}_p^t \to \mathbb{F}_p^t$ une permutation. Soit $0 < r, c, d < t$ avec $r + c = t$. Soit $\text{pad}: [0, r-1] \to \cup_{i=1}^{r} \mathbb{F}_p^i$ avec $\text{pad}(i) \in \mathbb{F}_p^{r-i}$.

Une construction en éponge basée sur $f$ définit une fonction de hachage $H$ de la manière suivante :

- Pour $m = m_1||\dots||m_s$ avec $m_j \in \mathbb{F}_p^r$ si $j < s$ et $m_s \in \mathbb{F}_p^i$, on calcule $m' = m||\text{pad}(i) = m'_1||\dots||m'_{s'}$.

<footnote n="1">1. Le système est régulier.</footnote>

<footnote n="2">2. On commence par calculer une base de Gröbner dans l'ordre *grevlex* à l'aide de l'algorithme F5 (premier terme de la complexité), puis on la convertit dans l'ordre *lex* à l'aide de l'algorithme FGLM (second terme de la complexité). Cela nous ramène à une équation univariée de degré au plus $d$ qui peut être résolue en temps quasi-linéaire en $d$.</footnote>
— Soit $y_0 = IV \in \mathbb{F}_p^t$, pour $i$ allant de 1 à $s'$, on calcule $y_i$ de la manière suivante :

— on évalue $y'_{i-1} = y_{i-1} + m'_{i}||0^c$.

— on définit $y_i = f(y'_{i-1})$.

— On retourne les d premières coordonnées de $y_{s'}$.

En particulier, si $f$ est une permutation pseudo-aléatoire, trouver une collision sur $H$ prend un temps $p^{\min(c,d)/2}$.

<figure><img src="image_3.png" /><figcaption>FIGURE 1 – Construction en éponge [Jea16].</figcaption></figure>

La construction en éponge reposant cruciallement sur le fait que la permutation agisse comme une permutation aléatoire, il peut être intéressant d'exhiber une propriété non générique de la famille de permutation utilisée. On donne ici un exemple d'une telle famille de distingueurs, généralisant les distingueurs intégraux à clé connue sur $\mathbb{F}_2$.

**Définition 4 (Distingueur intégral à clé connue)** Soit $(f_k)_{k \in K}$ une famille de permutations. On dit que $((a_i)_{i \in [1,n]}, \mathcal{X}, \mathcal{Y})$ est un distingueur intégral à clé connue pour $(f_k)_{k \in K}$ si pour tout $k \in K$, il est facile de trouver $(x_i)_{i \in [1,n]}$ tels que

$$ \sum_{i=1}^{n} a_i \cdot f_k(x_i) \in \mathcal{Y}, \sum_{i=1}^{n} a_i \cdot x_i \in \mathcal{X}. $$

Pour que cette propriété soit intéressante, on doit avoir $\mathcal{X}, \mathcal{Y}$ facilement reconnaissables tels que $|\mathcal{X}|, |\mathcal{Y}| \ll p^t$. On dit alors qu'on a un distingueur intégral à clé connue de complexité $n$.

## 2.5 Attaques statistiques

On définit dans cette section des généralisations naturelles des probabilités linéaires et différentielles à $\mathbb{F}_p$. On note que cela conduit à deux définitions différentes pour la probabilité linéaire en fonction de si l'on considère la corrélation linéaire ou les approximations exactes, sans que l'on ait de lien direct entre les deux dans le cas général [BSV07]. Ces deux définitions coïncident cependant dans le cas usuel où $p = 2$.

**Définition 5 (Corrélation linéaire [BSV07])** Soit $S: \mathbb{F}_p^n \to \mathbb{F}_p^m$, on définit pour $a \in \mathbb{F}_p^m, b \in \mathbb{F}_p^n$ la quantité :

$$ C_{a,b}^{S} = \sum_{x \in \mathbb{F}_p^n} \zeta_p^{a \cdot S(x) - b \cdot x}, $$

où $\zeta_p \in \mathbb{C}^*$ est une racine $p$-ième de l'unité.
**Définition 6 (Approximation linéaire)** Soit $S: \mathbb{F}_p^n \to \mathbb{F}_p^m$, on définit pour $a \in \mathbb{F}_p^m, b \in \mathbb{F}_p^n, c \in \mathbb{F}_p$ la quantité :

$$L_{a,b,c}^{S} = \mathbb{P}_{x}(a \cdot S(x) = b \cdot x + c).$$

Nous verrons Section 4 une manière efficace d'évaluer ces deux quantités dans le cas où $S$ est une boîte split-and-lookup.

**Définition 7 (Probabilité différentielle)** Soit $S: \mathbb{F}_p^n \to \mathbb{F}_p^m$, on définit pour $a \in \mathbb{F}_p^n, b \in \mathbb{F}_p^m$ la quantité :

$$D_{a,b}^{S} = \mathbb{P}_{x}(S(x + a) - S(x) = b).$$

## 2.6 Boîte S split-and-lookup

On donne une définition des boîtes S split-and-lookup englobant celles données dans [GKL$^{+}$21] et [GKL$^{+}$23]. Ces boîtes S ont été introduites afin de protéger les primitives des attaques algébriques sur $\mathbb{F}_p$. Les arguments de sécurité reposent sur le degré élevé et la densité des représentations polynomiales de ces permutations.

**Définition 8 (Split-and-lookup)** Soit $p$ premier, $s_1...s_n \in \mathbb{N}_{\ge 2}$. Soit $p-1 = \sum_{k=1}^{n} \prod_{i=1}^{k-1} s_i \cdot v_k$ avec $0 \le v_k < s_k$.

Soit $I_{\text{low}} \prod I_{\text{up}} = \{1...n\}$ une partition de $\{1...n\}$ et $S_1...S_n$ telles que :

- $S_k: \mathbb{Z}_{s_k} \to \mathbb{Z}_{s_k}$ est une permutation.

- $S_k(x) = x$ quand $0 \le x \le v_k$ et $k \in I_{\text{low}}$.

- $S_k(x) = x$ quand $v_k \le x < s_k$ et $k \in I_{\text{up}}$.

On définit la fonction $S: \mathbb{F}_p \to \mathbb{F}_p$ par

$$S = \text{Comp} \circ S_1 \times \dots \times S_n \circ \text{Decomp}$$

où :

- **Decomp**: $\mathbb{F}_p \to \prod_{k=1}^{n} \mathbb{Z}_{s_k}$ associe à $x = \sum_{k=1}^{n} \prod_{i=1}^{k-1} s_i \cdot x_k$, avec $0 \le x_k < s_k$ l'élément $(x_1...x_n) \in \prod_{k=1}^{n} \mathbb{Z}_{s_k}$.

- $S_1 \times \dots \times S_n$: $\prod_{k=1}^{n} \mathbb{Z}_{s_k} \to \prod_{k=1}^{n} \mathbb{Z}_{s_k}$ est définie par

$$(S_1 \times \dots \times S_n)(x_1 \dots x_n) = (S_1(x_1) \dots S_n(x_n)).$$

- **Comp**: $\prod_{k=1}^{n} \mathbb{Z}_{s_k} \to \mathbb{F}_p$ est définie par

$$\text{Comp}(x_1 \dots x_n) = \sum_{k=1}^{n} \prod_{i=1}^{k-1} s_i \cdot x_k.$$

Alors $S$ est une permutation de $\mathbb{F}_p$.

La preuve que $S$ est une permutation utilise le fait que **Decomp**: $\mathbb{F}_p \to \prod_{k=0}^{n} \mathbb{Z}_{s_1} \times \dots \times \mathbb{Z}_{s_{k-1}} \times [0, v_k - 1] \times \{v_{k+1}...v_n\}$ est une bijection. L'ensemble $\prod_{k=0}^{n} \mathbb{Z}_{s_1} \times \dots \times \mathbb{Z}_{s_{k-1}} \times [0, v_k - 1] \times \{v_{k+1}...v_n\}$ est stable par $S_1 \times \dots \times S_n$. Enfin, comme $\text{Comp} \circ \text{Decomp} = \text{Id}_{\mathbb{F}_p}$, on a en particulier Comp: $\prod_{k=0}^{n} \mathbb{Z}_{s_1} \times \dots \times \mathbb{Z}_{s_{k-1}} \times [0, v_k - 1] \times \{v_{k+1}...v_n\} \to \mathbb{F}_p$ bijective. Les détails de la preuve sont donnés Annexe A.

Par exemple, les permutations utilisées dans MONOLITH [GKL$^{+}$23] et TIP5 [SLS$^{+}$23] utilisent toutes deux des permutations split-and-lookup où $s_i = 2^8$ pour $i = 1...8$ et $v_1 = \dots = v_4 = 0, v_5 = \dots = v_8 = 2^8 - 1$. Dans ce cas, on fait le choix de $I_{\text{low}} = \{1...4\}$ et $I_{\text{up}} = \{5...8\}$. Ainsi, les seuls points fixes des $S_i$ sont 0 et 255. Une autre instanciation de MONOLITH définie sur $p_{\text{mers}} = 2^{31} - 1$ utilise $s_4 = 2^7, s_3 = s_2 = s_1 = 2^8$. Ce cas est particulier puisque notre définition demanderait $v_4 = 2^7 - 1, v_2 = v_3 = 2^8 - 1, v_1 = 2^8 - 2$, or on voit que $2^8 - 2$ n'est pas
un point fixe de $S_1$. Dans ce cas particulier, il n'y a en fait besoin que du fait que $2^8 - 1$ soit un point fixe de $S_1, S_2, S_3$ et que $2^7 - 1$ soit un point fixe de $S_4$. Cela afin que $2^{31} - 1$ soit envoyé sur $2^{31} - 1$.

Dans le cas de REINFORCED CONCRETE [GKL+21], les auteurs ont fait le choix de prendre $I_{\text{low}} = \emptyset$ et $I_{\text{up}} = \{1...n\}$ dans toutes leurs instanciations. Les valeurs des $s_i$ et $v_i$ dépendent quant à elles de la valeur de $p$.

# 3 Analyse structurelle de Tip5

## 3.1 Design de Tip5

Tip5 [SLS+23] est une fonction de hachage orientée arithmétisation définie à partir d'une permutation $f: \mathbb{F}_p^t \to \mathbb{F}_p^t$, où $t = 16$ et $p = p_{\text{goldi}} = 2^{64} - 2^{32} + 1$. Cette permutation est utilisée pour définir une fonction de hachage en sponge mode, ou comme fonction de compression en Jive mode. Elle peut être utilisée en sponge mode avec $c = 6, d = 5$ pour un niveau de sécurité de $d \log_2 p/2 \approx 160$bits [SLS+23]. Une autre version avec $c = d = 4$, utilisée en sponge ou Jive mode pour un niveau de sécurité de $d \log_2 p/2 \approx 128$bits a ensuite été publiée [Sal23].

La permutation $f$ est définie selon une structure SPN sur 5 tours :

- $A_i(x) = Mx + c_i$, où $c_i \in \mathbb{F}_p^t$ sont des constantes de tour générée à partir du haché d'une chaîne de caractères choisie par les auteurs et $M \in \mathcal{M}_t(\mathbb{F}_p)$ est une matrice MDS.

- La couche non-linéaire $\mathbf{S}$ comprend deux types de permutations de $\mathbb{F}_p$ :

- $s = 4$ d'entre elles sont des fonctions en split-and-lookup décrites Section 4.3.

- Les $t-s = 12$ restantes sont des monômes $T: x \mapsto x^\alpha$, avec $\alpha = 7$ (l'entier 7 est minimal tel que $\gcd(\alpha, p-1) = 1$).

On remarque que la première couche de boîtes $\mathbf{S}$ et les constantes du dernier round sont inutiles puisqu'elles ne créent pas de diffusion [BBLP22]. Nous les ignorerons donc dans nos analyses de sécurité.

<figure><img src="image_4.png" /><figcaption>FIGURE 2 – Structure de la permutation Tip5.</figcaption></figure>

Intuitivement, les arguments de sécurité de Tip5 se basent sur le fait que les monômes protègent la permutation des attaques statistiques en raison de leur faible linéarité et uniformité différentielle et que les boîtes split-and-lookup la protègent des attaques algébriques en raison de leur degré algébrique très élevé.

L'analyse de sécurité des designers de Tip5 concluait que la fonction de hachage était sécurisée au bout de 3 tours. Les auteurs ont alors choisi d'ajouter 2 tours de marge de sécurité.

**Lemme 1 (Propriétés différentielles et linéaires d'un monôme)** Soit $1 < \alpha < p$, alors on a :

- Pour $a \in \mathbb{F}_p^\times, b, c \in \mathbb{F}_p$, la probabilité linéaire $L_{a,b,c}^{x^\alpha} = \mathbb{P}_x(a \cdot x^\alpha = b \cdot x + c)$ vérifie

$$L_{a,b,c}^{x^\alpha} \leq \frac{\alpha}{p}.$$

- Pour $a \in \mathbb{F}_p^\times, b$, la probabilité différentielle $D_{a,b}^{x^\alpha} = \mathbb{P}_x((x+a)^\alpha - x^\alpha = b)$ vérifie

$$D_{a,b}^{x^\alpha} \leq \frac{\alpha - 1}{p}.$$
**Preuve 1** C'est une conséquence directe du fait que pour $a \in \mathbb{F}_p^\times$, $b, c \in \mathbb{F}_p$, le polynôme $a \cdot X^\alpha - b \cdot X - c$ est de degré au plus $\alpha$ et le polynôme $(X+a)^\alpha - X^\alpha - b$ est de degré au plus $\alpha - 1$.

**Lemme 2 (Degré algébrique des split-and-lookups de Tip5 [GKL$^{+}$23])** Le degré de $S$ vu comme une fonction de $\mathbb{F}_p[X]$ vérifie

$$ \deg S > 2^{57}. $$

**Preuve 2** Pour $x \in [0, 2^{56} - 1] \cup (254 \cdot 2^{56} + [0, 2^{56} - 1])$, on a $S(x + 2^{56}) - S(x) = 7 \cdot 2^{56}$ (car $S(1) - S(0) = S(255) - S(254) = 7$ et on n'active qu'une seule boîte $S$).

Comme il existe $x \in \mathbb{F}_p$ tel que $S(x + 2^{56}) - S(x) \neq 7 \cdot 2^{56}$, on a le polynôme $S(X + 2^{56}) - S(X) - 7 \cdot 2^{56} \neq 0$. D'où

$$ \deg S - 1 \geq \deg(S(X + 2^{56}) - S(X) - 7 \cdot 2^{56}) \geq 2^{57}. $$

## 3.2 Exploiter les monômes pour sauter les 3 premiers tours

Nous décrivons maintenant une stratégie donnant une attaque sur une version de Tip5 réduite à 4 tours. Cette attaque n'exploite que la forme monomiale de certaines boîtes S de la permutation. Cela nous donne une estimation plus fine de la véritable marge de sécurité de la fonction de hachage. Nous donnons de plus un distingueur intégral couvrant l'ensemble de la permutation, sans la première rangée de boîtes S. Si un tel distingueur ne mène pas nécessairement à une attaque par collision, cela permet toutefois d'exhiber une propriété non générique de la permutation utilisée par Tip5.

### 3.2.1 Saut de 2 tours

Il est déjà connu que les boîtes S monomiales permettent de sauter les deux premiers tours dans une attaque algébrique. Cela a par exemple été utilisé dans la cryptanalyse algébrique de Rescue et de Poseidon [BBLP22]. Le premier alterne entre des couches non-linéaires constituées de monômes $x^\alpha$ et de leur permutation inverse $x^{1/\alpha}$ et le second utilise des couches complètes de monômes $x^\alpha$ pour se protéger des attaques statistiques, suivies de tours n'utilisant qu'un seul monôme afin d'augmenter le degré de la permutation au prix d'un faible nombre de multiplications.

L'idée de cette méthode est de sauter deux tours en trouvant un espace affine $V = \vec{a} \cdot \mathbb{F}_p + \vec{b} \subset \mathbb{F}_p^t$ non trivial, tel que tout élément de $(f_2 \circ f_1)^{-1}(V)$ ait les coordonnées correspondant à la capacité fixées à 0.

Cette technique exploite le fait que les monômes soient multiplicatifs, c'est-à-dire

$$ (a \cdot X)^\alpha = a^\alpha \cdot X^\alpha. $$

Pour cela, on cherche $\vec{a}', \vec{b}' \in \mathbb{F}_p^t$ tels que pour tout $X \in \mathbb{F}_p$ :

1. $f_1^{-1}(\vec{a}' \cdot X + \vec{b}') \cdot \vec{e}_i = 0$ pour $i = t - c + 1 \dots t$, où $\vec{e}_i$ est $i^e$ vecteur de la base canonique de $\mathbb{F}_p^t$.

2. il existe $\vec{a}, \vec{b}$ tels que $f_2(\vec{a}' \cdot X + \vec{b}') = \vec{a} \cdot X^\alpha + \vec{b}$.

On donne ici deux conditions suffisantes pour avoir ces deux propriétés :

1. Pour tout $X \in \mathbb{F}_p$, $i \in [t - c + 1, t]$, $M^{-1} \cdot (\vec{a}' \cdot X + \vec{b}' - c_1) \cdot \vec{e}_i = 0$.

2. $\vec{a}', \vec{b}'$ sont deux vecteurs à support disjoints [BCP23] et $[1, s] \cap \text{Supp}(\vec{a}') = \emptyset$.

La première condition provient du fait que $0^{1/\alpha} = 0$ et la seconde de la multiplicativité des monômes.
<figure><img src="image_5.png" /><figcaption>FIGURE 3 – Saut d’un tour de monômes.</figcaption></figure>

### 3.2.2 Extension au tour 3

Dans le cas de Tip5, il est intéressant d'étendre ce résultat à un tour de plus en contournant les boîtes S split-and-lookup du tour 3 afin que le degré de $f_3(\vec{a} \cdot X + \vec{b})$ soit faible (égal à $\alpha$). On souhaite de plus garder le fait que pour tout $X \in \mathbb{F}_p, i \in [t-c+1, t]$, on ait

$$(f_2 \circ f_1)^{-1}(\vec{a} \cdot X + \vec{b}) \cdot \vec{e}_i = 0.$$

**Théorème 2** Soit $f: \mathbb{F}_p^t \to \mathbb{F}_p^t$ une permutation SPN de 3 tours, telle que la couche S soit définie par $s < t$ permutations arbitraires de $\mathbb{F}_p$ et de $t-s$ monômes de degré $\alpha$. Soit $c$ entier tel que

$$t \ge \max(c, s) + c + s + 1,$$

alors il existe $\vec{a} \in \mathbb{F}_p^t - \{0\}, \vec{b} \in \mathbb{F}_p^t$ tels que pour tout $X \in \mathbb{F}_p$ et $i \in [t-c+1, t]$ on ait

$$(f_2 \circ f_1)^{-1}(\vec{a} \cdot X + \vec{b}) \cdot \vec{e}_i = 0.$$

et

$$\deg_X(f_3(\vec{a} \cdot X + \vec{b})) \le \alpha.$$

De plus, ces vecteurs peuvent être trouvés en temps $s^2 \alpha \binom{s \cdot \alpha}{s-1}^\omega + s \cdot \alpha^{s\omega}$ où $\omega$ est l'exposant de la complexité de la multiplication de matrices.

**Preuve 3** On reprend la méthode permettant de sauter les deux premiers tours à l'aide d'un espace affine.

On prend $\text{Supp}(\vec{b}') = [1, s] \cup \{i_{s+1}, \dots, i_c\}$ et $\text{Supp}(\vec{a}') = [1, t] - \text{Supp}(\vec{b})$. De cette manière, $|\text{Supp}(\vec{b}')| = \max(c, s)$ et $\text{Supp}(\vec{a}') \cap \text{Supp}(\vec{b}') = \emptyset$.

La condition $\forall X \in \mathbb{F}_p, i \in [t-c+1, t], M^{-1} \cdot (\vec{a}' \cdot X + \vec{b}' - c_1) \cdot \vec{e}_i = 0$ est alors vérifiée lorsque $M^{-1} \cdot \vec{a}' \cdot \vec{e}_i = 0$ et $M^{-1} \cdot (\vec{b}' - c_1) \cdot \vec{e}_i = 0$ pour $i \in [t-c+1, t]$.

- La première condition restreint $\vec{a}'$ à un sous-espace vectoriel de dimension $t' = t - \max(c, s) - c$ de $\mathbb{F}_p^t$. On note donc $\vec{a}' = \sum_{i=1}^{t'} \lambda_i \cdot \vec{a}'_i$ avec les $\vec{a}'_i$ une base de l'espace vectoriel des vecteurs $\vec{a}'$ valides.

- La seconde condition revient à résoudre un système linéaire en $\vec{b}'$. Ce système a une solution car $M$ est inversible.

En appliquant la couche de monômes puis la matrice $M$ au vecteur $\vec{a}'$, on obtient un vecteur $\vec{a}(\lambda_1 \dots \lambda_{t'})$ qui est un polynôme homogène de degré $\alpha$ en les $\lambda_i$.

Trouver un vecteur donnant des constantes en entrée des split-and-lookups de la troisième couche de S-boxes revient à annuler les coefficients $a_1 \dots a_s$ de $\vec{a}$. Cela nous donne un système multivarié homogène de degré $\alpha$ en les $\lambda_i$. Pour avoir une solution non triviale, on peut par exemple fixer $\lambda_1 = 1$.

Comme $t' - 1 = t - \max(c, s) - s - 1 \ge s$, ce système est bien déterminé. En supposant que le système soit régulier, l'algorithme F5 permet d'en trouver une base de Gröbner pour l'ordre grevlex en temps $s^2 \alpha \binom{s \cdot \alpha}{s-1}^\omega$ (car $D_{reg} \le s \cdot (\alpha - 1) + 1$ et il y a s équations à s inconnues). L'algorithme FGLM change l'ordre de grevlex en lex en temps $s \cdot \alpha^{s\omega}$ (le degré de l'idéal est borné par $\alpha^s$ car il y a s équations de degré $\alpha$).
En pratique, le système généré par cette méthode n'a pas toujours de solution dans $\mathbb{F}_p$. Il est cependant possible de générer plusieurs systèmes différents dans le cas $c > s$ en faisant d'autres choix de $i_{s+1} \dots i_c$ dans le support de $\vec{a}$.

Par exemple, dans le cas de Tip5, le système pour $i_5, i_6 = 5, 6$ n'avait pas de solution, en revanche, $i_5, i_6 = 6, 7$ en avait une.

<figure><img src="image_6.png" /><figcaption>FIGURE 4 – Paramétrisation du vecteur $\vec{a}$.</figcaption></figure>

## 3.3 Contourner le dernier tour

Dans cette section, on donne une méthode permettant de contrôler la sortie de la fonction dans le cas où $d > s$ à partir du moment où on a une fonction de bas degré en entrée du dernier tour.

Plus précisément, il existe un hyperplan $H \subset \mathbb{F}_p^d$ vérifiant la propriété suivante :

— Soit $\vec{c} \in \mathbb{F}_p^c$ la valeur prise par les éléments dans la capacité.

— Soit $\sigma: \mathbb{F}_p \to \mathbb{F}_p^{t-c} \times \{\vec{c}\}$ une fonction injective telle que $(f_{R-1} \circ \dots \circ f_1)(\sigma(X))$ soit une fonction de degré $\delta$ en $X$.

Alors il est possible de trouver $x \in \mathbb{F}_p^{t-c} \times \{\vec{c}\}$ tel que si $y = f(x)$, alors $(y_1 \dots y_d) \in H$. Ce vecteur $x$ peut être trouvé en temps quasi-linéaire en $\delta \cdot \alpha$.

Pour cela, on remarque que les boîtes S split-and-lookup ne couvrent pas toute la dernière couche. Ainsi, en notant $(P_1(X) \dots P_t(X)) = (f_{R-1} \circ \dots \circ f_1)(\sigma(X))$ le vecteur en sortie du tour $R-1$, alors on obtient le vecteur

$$ (S(P_1(X)) \dots S(P_s(X)), P_{s+1}(X)^\alpha \dots P_t(X)^\alpha) $$

en sortie des boîtes S.

En notant $S_i(X) = S(P_i(X))$, on a alors $\Lambda \in \mathbb{F}_p^{t \times s}$ tel que la sortie de la permutation soit :

$$ \Lambda \cdot (S_1(X) \dots S_s(X)) + M \cdot (0 \dots 0, P_{s+1}(X)^\alpha \dots P_t(X)^\alpha) + c_R . $$

En particulier, en prenant $\tilde{\Lambda} \in \mathbb{F}_p^{d \times s}$ la matrice formée des $d$ premières lignes de $\Lambda$, on trouve un haché de la forme

$$ \tilde{\Lambda} \cdot (S_1(X) \dots S_s(X)) + (\tilde{P}_1(X) \dots \tilde{P}_d(X)) $$

où les $\tilde{P}_i$ sont de degré au plus $\delta \cdot \alpha$.

Comme $d > s$, $\tilde{\Lambda}$ ne peut pas être de rang plein. On peut donc trouver un vecteur $\tilde{\lambda} \in \mathbb{F}_p^d - \{0\}$ tel que $\tilde{\lambda} \cdot \tilde{\Lambda} = 0$.

En prenant $\tilde{y}(X) \in \mathbb{F}_p^d$ le haché, on a alors $\tilde{\lambda} \cdot \tilde{y}(X) = \tilde{\lambda} \cdot (\tilde{P}_1(X) \dots \tilde{P}_d(X))$ qui est de degré au plus $\delta \cdot \alpha$ en $X$.

Une racine de ce polynôme nous donne alors une sortie dans l'hyperplan $H = \tilde{\lambda}^\perp \subset \mathbb{F}_p^d$. Une telle racine peut être trouvée dans $\mathbb{F}_p$ avec une complexité quasi-linéaire en $\delta \cdot \alpha$.

## 3.4 Applications

### 3.4.1 Attaque par collision dans le cas $c = d = 5, R = 4$

Dans le cas $c = d = 5$, on a $\max(c, s) + c + s + 1 = 5 + 5 + 4 + 1 = 15 \le 16 = t$. On peut donc utiliser la paramétrisation permettant d'avoir des polynômes de degré $\delta = \alpha$ en sortie du tour 3.
<figure><img src="image_7.png" /><figcaption>FIGURE 5 – Contournement des boîtes S du dernier tour.</figcaption></figure>

La complexité pour générer le vecteur $\vec{a}$ vaut dans ce cas $s^2\alpha(\sum_{s-1}^{s\alpha})^\omega + s\alpha^{s\omega} = 4^2 \cdot 7(\sum_{3}^{28})^3 + 4 \cdot 7^{12} \sim 2^{41.7}$. On note qu'il s'agit d'un pré-calcul<fnref n="3" /> ne dépendant que de la matrice MDS M.

De plus, comme $d = 5 > 4 = s$, on peut également obtenir une sortie dans un hyperplan en résolvant un polynôme de degré $\alpha \cdot \delta = \alpha^2$.

On peut alors générer des hachés dans l'hyperplan de la manière suivante :

- On prend une entrée arbitraire $x_1 \in \mathbb{F}_p^r$ où $r = t - c$ pour le premier bloc.

- Étant donné $\vec{c} \in \mathbb{F}_p^c$ la valeur de la capacité en sortie de la permutation, on peut alors trouver une valeur $x_2 \in \mathbb{F}_p^r$ donnant une sortie dans l'hyperplan<fnref n="4" /> en résolvant un polynôme de degré $\alpha^2$.

En supposant que les hachés sont répartis uniformément dans l'hyperplan de dimension $d-1$, le paradoxe des anniversaires nous donne une collision au bout de $p^{(d-1)/2}$ itérations. La résolution d'un polynôme univarié de degré $\delta$ dans $\mathbb{F}_p$ a une complexité en $O(\delta \log(\delta) \cdot (\log(p) + \log(\delta)) \cdot \log(\log(\delta)))$. On trouve donc une collision en environ $\alpha^2 \cdot 2 \cdot \log(\alpha) \cdot (\log(p) + 2 \cdot \log(\alpha)) \cdot p^{(d-1)/2}$ opérations arithmétiques.

Dans le cas de TIP5, on a $\alpha = 7$, $p_{\text{goldi}} = 2^{64} - 2^{32} + 1$, $d = 5$. Cela nous donne donc une collision en temps $2^{143.54}$ au lieu de $2^{160}$.

### 3.4.2 Attaque intégrale sur la permutation complète

On donne dans cette section un distingueur intégral à clé connue sur l'ensemble de la permutation, sans la première couche de boîtes S (qui ne joue aucun rôle dans la sécurité de la permutation).

On montre les résultats suivants :

**Théorème 3** Soit une permutation de type TIP5 définie sur $R = 5$ tours, sans la première couche de boîtes S :

- Si $t \ge 2 \cdot s + 1$, alors il existe un distingueur intégral à clé connue de complexité $p$.

- Si $t \ge 3 \cdot s + 1$, cette complexité peut être réduite à $\alpha^{-1} + 2$, où $0 \le \alpha^{-1} < p - 1$ désigne l'inverse de $\alpha$ modulo $p - 1$.

**Attaque dans le cas $t \ge 2 \cdot s + 1$ (complexité $p$) :**

Pour construire ce distingueur, on va utiliser le résultat suivant :

**Lemme 3 (Saturation d'une branche)** Soit $f: \mathbb{F}_p \to \mathbb{F}_p$ fonction polynomiale telle que $\deg f < p - 1$, alors :

$$ \sum_{x \in \mathbb{F}_p} f(x) = 0. $$

On se place à l'entrée du tour 3. Soit $\vec{a} = (0 \dots 0, a_{s+1} \dots a_t)$, en mettant la valeur $\vec{a} \cdot X$ à l'entrée de ce tour, on trouve la valeur $M \cdot \vec{a}^\alpha \cdot X^\alpha + c_3$ en sortie.

<footnote n="3">3. Ces calculs ont été implémentés à l'aide de MAGMA et ont pris environ 2h38.</footnote>

<footnote n="4">4. Une implémentation de cette attaque est disponible à l'adresse https://github.com/AntoineBak/split-and-lookup-analysis.git.</footnote>
En annulant les $s$ premières coordonnées du vecteur $M \cdot \vec{a}^{\alpha}$ (possible en résolvant un système linéaire à $s$ inconnues car $t-s \ge s+1$), on obtient une fonction de degré au plus $\alpha^2$ en $X$ en sortie du tour 4. Enfin, passer par le dernier tour donne la somme d'une fonction de degré $\alpha^3$ avec un élément d'un espace vectoriel $F$ de dimension $s < t$.

Comme $\alpha^3 < p-1$, sommer sur les sorties pour $X \in \mathbb{F}_p$ donne un élément de $F = \text{Im}(\Lambda)$, où $\Lambda \in \mathbb{F}_p^{t \times s}$ est la matrice définie Section 3.3.

En ce qui concerne les entrées, $(f_2 \circ M)^{-1}(\vec{a} \cdot X)$ applique sur $X$ :

- une fonction affine.

- une couche de boîtes $S$.

- une fonction affine.

La fonction affine est de degré 1 en $X$. Une permutation sur $\mathbb{F}_p$ étant au plus de degré $p-2$, la sortie avant les boîtes $S$ du premier tour est de degré au plus $p-2$ en $X$. En sommant sur $X \in \mathbb{F}_p$, on obtient une somme à zéro sur les entrées.

On a donc bien $((1)_{i \in [1,p]}, \{0\}, F)$ un distingueur intégral à clé connue sur Tip5, de complexité $p$.

**Attaque dans le cas** $t \ge 3 \cdot s+1$ (complexité $(\alpha^{-1} \mod (p-1)) + 2)$ :

Dans le cas où $t \ge 3 \cdot s+1$, il est possible de réduire la complexité du distingueur en utilisant le résultat suivant :

**Lemme 4 (Différentielle d'ordre supérieur [SWMSP17])** Soit $f: \mathbb{F}_p \to \mathbb{F}_p$ fonction polynomiale telle que $\text{deg} f < k$, alors :

$$ \sum_{i=0}^{k} (-1)^{k-i} \binom{k}{i} \cdot f(i) = 0. $$

Dans ce cas, on réutilise les résultats de saut de tours de manière à avoir :

- Une fonction affine en $X$ en entrée du tour 3.

- Les valeurs des boîtes split-and-lookup des tours 2, 3, 4 fixées et indépendantes de $X$.

Cela est possible en considérant les branches entrant les split-and-lookups du tour 2 comme la capacité que l'on cherche à fixer, puis à appliquer le saut de tours sur les tours 3 et 4 (ce qui est possible car $t \ge 3 \cdot s+1$).

La sortie devient alors la somme d'une fonction de degré au plus $\alpha^3$ en $X$ et d'un élément d'un espace vectoriel $F$ de dimension $s < t$. L'entrée du tour 2, quant à elle n'est que l'application de monômes $x \mapsto x^{1/\alpha}$ à une fonction affine de $X$. Elle est donc de degré au plus $\alpha^{-1} \mod (p-1)$.

En utilisant les mêmes $\mathcal{X}, \mathcal{Y} = \{0\}, F$ que dans le cas précédent, on trouve :

$$ \sum_{i=0}^{k} (-1)^{k-i} \binom{k}{i} \cdot f_5 \circ f_4 \circ f_3(\vec{a} \cdot i) \in F $$

et

$$ \sum_{i=0}^{k} (-1)^{k-i} \binom{k}{i} \cdot (f_2 \circ M)^{-1}(\vec{a} \cdot i) = 0 $$

$$ \text{où } k = (\alpha^{-1} \mod (p-1)) + 1. $$

On a donc $(((-1)^{k-i} \binom{k}{i})_{i \in [0,k]}, \{0\}, F)$ un distingueur intégral à clé connue de complexité $k+1 = (\alpha^{-1} \mod (p-1)) + 2$.

Dans le cas de Tip5, $t = 16 \ge 13 = 3 \cdot s+1$. On peut donc appliquer le second résultat qui nous donne un distingueur de complexité

$$ (7^{-1} \mod p-1) + 2 \sim 2^{63.2}. $$

On note que trouver une telle famille de vecteurs $(\vec{x}_i)_{i \in [0,k]}$ dans le cas d'une permutation $R: \mathbb{F}_p^t \to \mathbb{F}_p^t$ aléatoire peut se faire des deux manières suivantes :
<figure><img src="image_8.png" /><figcaption>FIGURE 6 – Attaque intégrale sur la permutation complète.</figcaption></figure>

— Choisir $(\vec{x}_i)_{i \in [0,k]}$ tel que $\sum_{i=0}^k a_i \cdot \vec{x}_i = 0$. On a alors $\sum_{i=0}^k a_i \cdot R(\vec{x}_i) \in F$ avec probabilité $\frac{|F|}{p^t} = p^{s-t} \sim 2^{-768}$.

— Choisir $(\vec{y}_i)_{i \in [0,k]}$ tel que $\sum_{i=0}^k a_i \cdot \vec{y}_i \in F$. On a alors $\sum_{i=0}^k a_i \cdot R^{-1}(\vec{y}_i) = 0$ avec probabilité $p^{-t} \sim 2^{-1024}$.

Notre attaque trouvant ces vecteurs en temps $2^{63.2}$ au lieu de $2^{768}$, il s'agit bien d'un distingueur à clé connue sur la permutation.

# 4 Approximations linéaires des boîtes split-and-lookup

Dans cette section, on donne des manières efficaces d'évaluer les approximations linéaires des boîtes split-and-lookup, à la fois du point de vue de la corrélation et des approximations linéaires exactes. On note que les approximations exactes ont une importance particulière dans les analyses de sécurité puisqu'elles permettent d'évaluer l'efficacité d'une attaque algébrique par linéarisation. Même si l'intérêt de la corrélation linéaire dans une telle analyse de sécurité est moins clair, on donne tout de même une méthode de calcul des coefficients de Fourier de la boîte S pour rendre l'étude la plus complète possible.

On applique enfin les résultats de la section à l'étude des boîtes S utilisées dans TIP5, MONOLITH et aux différentes instances de REINFORCED CONCRETE. Même si nos résultats ne donnent pas directement lieu à une attaque sur ces primitives, elles permettent d'affiner les analyses de sécurité. En particulier, on remarque que les boîtes S de TIP5 ont des approximations linéaires ayant des probabilités plus élevées que celles prévues par les auteurs de l'article $(57360/p_{\text{goldi}} \sim 2^{-48.2}$ contre $241/p_{\text{goldi}} \sim 2^{-56.1})$. Le cas de MONOLITH pour $p_{\text{goldi}}$ étant particulièrement parlant puisqu'on trouve une approximation linéaire ayant une probabilité $2^{-22.24}$.

## 4.1 Calcul de la corrélation linéaire

On donne dans cette section une méthode permettant d'évaluer efficacement la corrélation linéaire d'une telle boîte S.

**Théorème 4 (Corrélation linéaire d'une split-and-lookup)** Soit S une permutation split-and-lookup, alors sa corrélation linéaire peut être calculée de la manière suivante :

$$C_{a,b}^{S} = \sum_{k=0}^{n} \prod_{j=1}^{k-1} C_{a,b}^{S_j} \cdot C_{a,b}^{\text{low},S_k} \cdot \prod_{i=k+1}^{n} C_{a,b}^{v,S_i},$$

avec

$$C_{a,b}^{v,S_i} = \zeta_p \prod_{j=1}^{i-1} s_j \cdot (a-b) \cdot v_i,$$
$$C_{a,b}^{\text{low},S_i} = \sum_{0 \le x < v_i} \zeta_p^{\prod_{j=1}^{i-1} s_j \cdot (a \cdot S_i(x) - b \cdot x)}$$

et

$$C_{a,b}^{S_i} = \sum_{x \in \mathbb{Z}_{s_i}} \zeta_p^{\prod_{j=1}^{i-1} s_j \cdot (a \cdot S_i(x) - b \cdot x)}.$$

**Preuve 4** Par définition,

$$C_{a,b}^{S} = \sum_{x \in \mathbb{F}_p} \zeta_p^{a \cdot S(x) - b \cdot x} \\ = \sum_{(x_1 \dots x_n) \in \text{Decomp}(\mathbb{F}_p)} \prod_{k=1}^{n} \zeta_p^{\prod_{i=1}^{k-1} s_i \cdot (a \cdot S_k(x_k) - b \cdot x_k)}.$$

Réécrire la somme en écrivant $\text{Decomp}(\mathbb{F}_p)$ comme l'union disjointe

$$\text{Decomp}(\mathbb{F}_p) = \prod_{k=0}^{n} \mathbb{Z}_{s_1} \times \dots \times \mathbb{Z}_{s_{k-1}} \times [0, v_k - 1] \times \{v_{k+1} \dots v_n\}$$

nous donne le résultat annoncé.

Cette formule permet en particulier de calculer le coefficient $C_{a,b}^S$ en $\sum_{i=1}^n s_i$ opérations au lieu de $p$.

## 4.2 Calcul des approximations linéaires : cas de petits coefficients

Dans cette section, on détaille une méthode permettant de calculer les $L_{a,b,c}^S$ efficacement lorsque $|a|, |b|$ vus comme des entiers sont petits.

En particulier, notre méthode permet de calculer $L_{a,b,c}^S$ en environ

$$n \cdot (|a| + |b|)^{\omega+1} + \sum_{i=1}^{n} s_i$$

opérations arithmétiques, où $\omega$ est un exposant de multiplications de matrices. À titre de parapaison, calculer $L_{a,b,c}^S$ sur $S$ quelconque demande $p$ opérations arithmétiques.

Cette méthode ne marche que quand $|a| + |b| + 1 < s_i$ pour tout $i$. Il est cependant possible de traiter le cas $|a| + |b| + 1 \ge s_i$ en regroupant certaines boîtes $S$, par exemple en posant $s'_i = s_{2i-1} \cdot s_{2i}$ et

$$S'_i: \quad \begin{array}{ccc} \mathbb{Z}_{s'_i} & \rightarrow & \mathbb{Z}_{s'_i} \\ x_{2i-1} + s_{2i-1}x_{2i} & \mapsto & S_{2i-1}(x_{2i-1}) + s_{2i-1}S_{2i}(x_{2i}) \end{array}$$

Regrouper les boîtes $S$ augmente cependant la complexité de l'algorithme, en augmentant la valeur de $\sum_{i=1}^n s_i$.

### 4.2.1 Approximations de $S_1 \times \dots \times S_n$

Dans cette section, on pose deux fonctions $S_1: [0, s_1 - 1] \to [0, s_1 - 1]$, $S_2: [0, s_2 - 1] \to [0, s_2 - 1]$ et on cherche à évaluer le nombre de paires $(x_1, x_2) \in [0, s_1 - 1] \times [0, s_2 - 1]$ telles que $a \cdot (S_1(x_1) + s_1 \cdot S_2(x_2)) = b \cdot (x_1 + s_1 \cdot x_2) + c$, avec $a, b, c \in \mathbb{Z}$.

Une première borne inférieure peut être apportée en décomposant $c$ en $c = c_1 + s_1 \cdot c_2, c_1 < s_1$, puis en calculant $n_1$ le nombre de $x_1$ tels que $a \cdot S_1(x_1) = b \cdot x_1 + c_1$ et $n_2$ le nombre de $x_2$ tels que $a \cdot S_2(x_2) = b \cdot x_2 + c_2$. Le nombre de solutions $(x_1, x_2)$ peut ainsi être minoré par $n_1 \cdot n_2$.
Cette stratégie sous-estime cependant le nombre de solutions. En particulier, on ignore complètement les solutions de la forme $a \cdot S_1(x_1) = b \cdot x_1 + c_1 + k \cdot s_1$, $a \cdot S_2(x_2) = b \cdot x_2 + c_2 - k$ qui sont pourtant des solutions valides. On verra par la suite que cela peut avoir une influence non négligeable sur le nombre d'approximations linéaires, notamment dans le cas de TIP5.

Ce genre de phénomène motive l'introduction des matrices de retenues, qui vont être une première étape dans le calcul efficace des $L_{a,b,c}^S$.

**Définition 9 (Matrice de retenue)** Soit $S: \llbracket 0, s-1 \rrbracket \to \llbracket 0, s-1 \rrbracket$, $a, b, c \in \mathbb{Z}$, $|a|+|b|+1 < s$. Les ensembles $\{x \in \llbracket 0, s-1 \rrbracket \mid a \cdot S(x) = b \cdot x + c + s \cdot i - j\}$ pour $i, j \in \llbracket -(a^- + b^+ + 1), a^+ + b^- \rrbracket$ ($x^+ = \max(x, 0)$ et $x^- = \max(-x, 0)$) sont deux à deux disjoints. On pose alors :

$$m_{ij} = \#\{x \in \llbracket 0, s-1 \rrbracket \mid a \cdot S(x) = b \cdot x + c + s \cdot i - j\}.$$

La matrice de retenue $M_{a,b,c}^S$ est la matrice dont les coefficients sont les

$$(m_{ij})_{i,j \in \llbracket -(a^- + b^+ + 1), a^+ + b^- \rrbracket}.$$

**Propriété 1** Soit $S_1: \llbracket 0, s_1 - 1 \rrbracket \to \llbracket 0, s_1 - 1 \rrbracket$, $S_2: \llbracket 0, s_2 - 1 \rrbracket \to \llbracket 0, s_2 - 1 \rrbracket$. On définit

$$S_1 \times S_2: \begin{array}{ccc} \llbracket 0, s_1 \cdot s_2 - 1 \rrbracket & \to & \llbracket 0, s_1 \cdot s_2 - 1 \rrbracket \\ x_1 + x_2 \cdot s_1 & \mapsto & S_1(x_1) + S_2(x_2) \cdot s_1. \end{array}$$

Alors on a pour $a, b, c \in \mathbb{Z}$ tels que $|a| + |b| + 1 < s_1$ et $c \in \llbracket 0, s_1 \cdot s_2 - 1 \rrbracket$, $M_{a,b,c}^{S_1 \times S_2} = M_{a,b,c_2}^{S_2} \cdot M_{a,b,c_1}^{S_1}$ où $c = c_1 + s_1 \cdot c_2$ et $0 \le c_1 < s_1$.

**Preuve 5** Soit $a, b \in \mathbb{Z}$, $c \in \llbracket 0, s_1 s_2 - 1 \rrbracket$ tels que $|a| + |b| + 1 < \min(s_1, s_2)$, $i, j \in \llbracket -(a^- + b^+ + 1), a^+ + b^- \rrbracket$ et $x \in \llbracket 0, s_1 \cdot s_2 - 1 \rrbracket$ tel que

$$a \cdot S_1 \times S_2(x) - b \cdot x = c + i \cdot s_1 s_2 - j.$$

On se propose de montrer qu'il existe $k \in \llbracket -(a^- + b^+ + 1), a^+ + b^- \rrbracket$ tel que $a \cdot S_1(x_1) = b \cdot x_1 + c_1 + k \cdot s_1 - j$ et $a \cdot S_2(x_2) = b \cdot x_2 + c_2 + i \cdot s_2 - k$.

On peut réécrire cela comme

$$(a \cdot S_2(x_2) - b \cdot x_2 - c_2 - i \cdot s_2) \cdot s_1 + (a \cdot S_1(x_1) - b \cdot x_1 - c_1 + j) = 0.$$

Autrement dit, $a \cdot S_1(x_1) - b \cdot x_1 - c_1 + j$ est divisible par $s_1$. On peut donc écrire $a \cdot S_1(x_1) = b \cdot x_1 + c_1 + k \cdot s_1 - j$ avec $k \in \mathbb{Z}$ et donc $a \cdot S_2(x_2) = b \cdot x_2 + c_2 + i \cdot s_2 - k$.

De plus, $k \in \llbracket -(a^- + b^+ + 1), a^+ + b^- \rrbracket$. En effet, $k \cdot s_1$ vérifie les inégalités

$$k \cdot s_1 = a \cdot S_1(x_1) - b \cdot x_1 - c_1 + j \le (a^+ + b^-)(s_1 - 1) + (a^+ + b^-) \le (a^+ + b^-) \cdot s_1$$

et

$$k \cdot s_1 = a \cdot S_1(x_1) - b \cdot x_1 - c_1 + j \ge -(a^- + b^+ + 1)(s_1 - 1) - (a^- + b^+ + 1) \ge -(a^- + b^+ + 1) \cdot s_1.$$

Réciproquement, il est clair que s'il existe $k \in \llbracket -(a^- + b^+ + 1), a^+ + b^- \rrbracket$ tel que $a \cdot S_1(x_1) = b \cdot x_1 + c_1 + k \cdot s_1 - j$ et $a \cdot S_2(x_2) = b \cdot x_2 + c_2 + i \cdot s_2 - k$, alors $a \cdot S_1 \times S_2(x) - b \cdot x = c + i \cdot s_1 s_2 - j$.

Cela nous donne bien :

$$m_{ij}^{S_1 \times S_2} = \sum_{k \in \llbracket -(a^- + b^+ + 1), a^+ + b^- \rrbracket} m_{ik}^{S_2} \cdot m_{kj}^{S_1},$$

et donc

$$M_{a,b,c}^{S_1 \times S_2} = M_{a,b,c_2}^{S_2} \cdot M_{a,b,c_1}^{S_1}.$$
Il devient donc possible de calculer efficacement la matrice $M_{a,b,c}^{S_1 \times \cdots \times S_n}$ en utilisant :

$$M_{a,b,c}^{S_1 \times \cdots \times S_n} = M_{a,b,c_n}^{S_n} \cdots M_{a,b,c_1}^{S_1}.$$

Cela requiert $n-1$ multiplications de matrices de taille $|a| + |b| + 2$, d'où une complexité de $(n-1) \cdot (|a| + |b| + 2)^\omega$ opérations arithmétiques.

En particulier, le coefficient $m_{0,0}^{S_1 \times \cdots \times S_n}$ nous donne le nombre de $(x_1 \dots x_n) \in \prod_{i=1}^n \mathbb{Z}_{s_i}$ tels que $a \cdot \sum_{i=1}^n \prod_{j=1}^{i-1} s_j \cdot S_i(x_i) = b \cdot \sum_{i=1}^n \prod_{j=1}^{i-1} s_j \cdot x_i + c$ dans $\mathbb{Z}$. Cela nous donne une première approximation de $L_{a,b,c}^S$ ne prenant pas en compte les réductions modulo $p$ ou le fait que les entrées soient toutes dans $\text{Decomp}(\mathbb{F}_p)$.

### 4.2.2 Approximations de $S_1 \times \cdots \times S_n \circ \text{Decomp}$

Nous avons vu jusque là comment calculer le nombre de $x \in [0, \prod_{i=1}^n s_i - 1]$ satisfaisant une approximation linéaire donnée. Cependant, les entrées $S$ étant dans $\mathbb{F}_p$, il est possible que certaines valeurs soient comptées plusieurs fois (lorsque $x \ge p$, $x$ et $x-p$ sont comptées comme des valeurs différentes).

Pour traiter cela, on reprend notre décomposition

$$\text{Decomp}(\mathbb{F}_p) = \prod_{k=0}^{n} \mathbb{Z}_{s_1} \times \cdots \times \mathbb{Z}_{s_{k-1}} \times [0, v_k - 1] \times \{v_{k+1} \dots v_n\}$$

et on calcule le nombre d'approximations dans chacun des termes de cette union.

Pour le terme $\mathbb{Z}_{s_1} \times \cdots \times \mathbb{Z}_{s_{k-1}} \times [0, v_k - 1] \times \{v_{k+1} \dots v_n\}$, on considère les matrices $M_{a,b,c_l}^{S_l}$ pour $1 \le l < k$, la matrice $M_{a,b,c_k}^{\text{low},S_k}$ ayant pour coefficients $m_{ij}^{\text{low}} = \#\{x \in [0, v_k - 1] \mid a \cdot S_k(x) = b \cdot x + c_k + s_k \cdot i - j\}$ pour $l=k$ et la matrice $M_{a,b,c_l}^{v,S_l}$ ayant pour coefficients $m_{ij}^v = \delta_{a \cdot S_l(v_l)=b \cdot v_l+c_l+s_l \cdot i-j}$ pour $l > k$.

La méthode précédente appliquée à ces nouvelles matrices nous donne le nombre d'approximations dans l'ensemble $\mathbb{Z}_{s_1} \times \cdots \times \mathbb{Z}_{s_{k-1}} \times [0, v_k - 1] \times \{v_{k+1} \dots v_n\}$. En sommant les résultats, on trouve bien la matrice de retenue de $S$ dans $\mathbb{F}_p$.

$$M_{a,b,c}^{S} = \sum_{k=0}^{n} M_{a,b,c_n}^{v,S_n} \cdots M_{a,b,c_{k+1}}^{v,S_{k+1}} \cdot M_{a,b,c_k}^{\text{low},S_k} \cdot M_{a,b,c_{k-1}}^{S_{k-1}} \cdots M_{a,b,c_1}^{S_1}.$$

Cette somme peut se calculer en $4n$ multiplications et $n-1$ additions de matrices, d'où une complexité en $4n \cdot (|a| + |b| + 2)^\omega$ opérations arithmétiques.

### 4.2.3 Approximations de $S$

Jusqu'ici, nous avons traité le cas des approximations linéaires de $S: \mathbb{F}_p \to [0, \prod_{i=1}^n s_i - 1]$ où les sorties sont considérées comme des entiers sans réduction modulo $p$. On explique dans cette section une manière de traiter les réductions modulo $p$ de la sortie, c'est à dire $S: \mathbb{F}_p \to \mathbb{F}_p$.

On s'intéresse donc au nombre de $x \in [0, p-1]$, $k \in \mathbb{Z}$ tels que $a \cdot S(x) = b \cdot x + c + k \cdot p$.

Tout d'abord, il est possible de borner $k$ par $-(a^{-} + b^{+} + 1) \cdot p \le k \cdot p = a \cdot S(x) - b \cdot x - c \le (a^{+} + b^{-}) \cdot p$ lorsque $0 \le x, c < p$. Ainsi,

$$-(a^{-} + b^{+} + 1) \le k \le (a^{+} + b^{-}).$$

On prend ensuite pour chaque $k$ la division euclidienne $c + k \cdot p = c' + k' \cdot \prod_{i=1}^n s_i$ avec $0 \le c' < \prod_{i=1}^n s_i$. On peut alors évaluer la matrice de retenue $M_{a,b,c'}^S$.

Son coefficient $m_{k'0}$ nous donne alors exactement le nombre de $x \in \mathbb{F}_p$ tels que $a \cdot S(x) = b \cdot x + c + k' \cdot \prod_{i=1}^n s_i = b \cdot x + c + k \cdot p$.

En sommant ces valeurs pour les différents $k$, on trouve le nombre total d'approximations de $S: \mathbb{F}_p \to \mathbb{F}_p$.
Il y a une matrice $M_{a,b,c'}^S$ à évaluer pour chacun des $-(a^- + b^+ + 1) \le k \le (a^+ + b^-)$, soit $|a| + |b| + 2$ matrices à calculer. La génération des coefficients pour les matrices $M_{a,b,c_i}^S$ peut se faire en calculant une seule fois chaque $a \cdot S_i(x_i) - b \cdot x_i$ pour $i \in [1, n]$, $x_i \in \mathbb{Z}_{s_i}$. Cela se fait en temps $\sum_{i=1}^n s_i$.

La complexité totale vaut donc :

$$4n \cdot (|a| + |b| + 2)^{\omega+1} + \sum_{i=1}^{n} s_i.$$

À titre de comparaison, l’algorithme naïf pour calculer $L_{a,b,c}^S$ demande de l’ordre de $p$ opérations arithmétiques. Cela devient très coûteux lorsque $p$ est un nombre premier de 64 bits, et infaisable en pratique lorsque $p$ est de l’ordre de 256 bits. Notre algorithme a permis de calculer ces valeurs en moins d’une seconde pour toutes les approximations traitées Section 4.3.

## 4.3 Application : cas de Tip5, Monolith et Reinforced concrete

### 4.3.1 Boîte S de Tip5

Les boîtes S de Tip5 sont définies de la manière suivante [SLS$^+$23] :

$$S: \begin{array}{rcl} \mathbb{F}_{2^8+1} - \{2^8\} & \rightarrow & \mathbb{F}_{2^8+1} - \{2^8\} \\ x & \mapsto & (x+1)^3 - 1 \end{array}$$

où les éléments de $\mathbb{Z}_{2^8}$ sont interprétés comme des éléments de $\mathbb{F}_{2^8+1} - \{2^8\}$. Cette fonction définit bien une permutation et a 0 et 255 pour points fixes.

Une première observation intéressante sur cette boîte S est qu’elle a une différentielle de probabilité 1 lorsqu’elle est interprétée comme une fonction booléenne. On note que même si cette propriété semble forte, elle est difficile à exploiter dans une attaque puisque les opérations sur $\mathbb{F}_p$ cassent à priori les structures que l’on peut trouver sur $\mathbb{F}_2^n$.

**Propriété 2** Pour $x \in \{0,1\}^8$, on a :

$$S(\mathbf{1} \oplus x) = \mathbf{1} \oplus S(x),$$

où **1** représente le vecteur $11111111$ et $\oplus$ représente le bitwise xor.

**Preuve 6** Le vecteur $\mathbf{1} \oplus x$ dans $\{0,1\}^8$ correspond à $-2 - x$ dans $\mathbb{F}_{2^8+1} - \{2^8\}$. En effet, $-2 = 255$ et $255 - x = \text{not}(x)$.

On vérifie donc que $S(-2 - x) = -2 - S(x)$ :

$$S(-2 - x) = (-1 - x)^3 - 1 = -(x + 1)^3 - 1 = -((x + 1)^3 - 1) - 2 = -2 - S(x).$$

En ce qui concerne les approximations linéaires, la meilleure approximation que l’on a trouvé est l’approximation

$$S(x) = -x + 606306544323790996$$

qui fonctionne avec probabilité $\frac{57360}{p} \sim 2^{-48.2}$.

Cet exemple permet de mettre en lumière l’intérêt des matrices de retenue dans l’étude des approximations des boîtes split-and-lookup. En effet, lorsque l’on regarde les probabilités des $S(x) = -x + c$, les meilleures constantes donnent une approximation fonctionnant pour 3 valeurs de $x$. Prendre une telle constante pour chaque boîte $S$ en parallèle nous donne une approximation fonctionnant pour $3^8 = 6561 \sim 2^{12.68}$ valeurs de $x \in \mathbb{F}_p$.

En revanche, en utilisant les matrices de retenue, il est possible de remarquer que $S(x) = -x+8$ pour 3 valeurs de $x$ et $S(x) = -x+264$ pour 3 autres valeurs de $x$. De plus, $S(x) = -x+106$ pour 3 valeurs et $S(x) = -x+105$ pour 2 valeurs.

En combinant les 2 approximations, on trouve $S \times S(x) = -x+8+256 \cdot 106$ pour $3 \cdot 3+2 \cdot 3 = 15$ valeurs de $x \in \mathbb{Z}_{2^{16}}$. Cela nous donne donc une approximation fonctionnant sur $15^4 \sim 2^{15.63}$ valeurs de $x \in \mathbb{F}_p$. Il est possible d’améliorer cette quantité grâce aux réductions modulo $p$ pour arriver à $57360 \sim 2^{15.81}$.
### 4.3.2 Boîte S de Monolith

La boîte S utilisée dans MONOLITH [GKL+23] est définie à partir de la fonction $\chi$ de Daemen, à laquelle on ajoute une rotation circulaire pour supprimer certains points fixes.

On note $\odot$ le et logique bit à bit, $\lll$ $k$ la rotation circulaire de $k$ bits vers la gauche. Soit

$$ \chi_8(x) = x \oplus ((\bar{x} \lll 1) \odot (x \lll 2) \odot (x \lll 3)) $$

pour $x \in \mathbb{F}_2^8$, et

$$ \chi_7(x) = x \oplus ((\bar{x} \lll 1) \odot (x \lll 2)) $$

pour $x \in \mathbb{F}_2^7$.

Dans le cas de $p_{\text{goldi}} = 2^{64} - 2^{32} + 1$, les huit boîtes $\mathcal{S}$ des split-and-lookups valent $\chi_8 \lll 1$. Pour $p = 2^{31} - 1$, les auteurs utilisent 3 boîtes $\chi_8 \lll 1$ et une boîte $\chi_7 \lll 1$.

Le premier défaut de ce choix de boîte S est que la fonction $\chi_8$ a de nombreux points fixes. En effet, $x$ est un point fixe lorsque $(\bar{x} \lll 1) \odot (x \lll 2) \odot (x \lll 3)$ s'annule, ce qui a une grande probabilité d'arriver puisqu'il s'agit d'une multiplications de trois vecteurs booléens. En pratique, la fonction $\chi_8$ a exactement 48 points fixes sur 256.

Si le circular shift semble retirer des points fixes, il se résume en réalité à une multiplication par 2 dans les entiers lorsque le bit de poids fort est nul. Cela donne donc 34 valeurs de $x$ telles que $(\chi_8(x) \lll 1) = 2 \cdot x$. Une simple analyse des approximations bloc par bloc nous donne

$$ S(x) = 2 \cdot x $$

pour au moins $34^8 \sim 2^{40.7}$ valeurs de $x$ (dans le cas $p_{\text{goldi}} = 2^{64} - 2^{32} + 1$). Les matrices de retenues nous permettent d'atteindre $3726693261568 \sim 2^{41.76}$ solutions.

Le cas $p_{\text{mers}} = 2^{31} - 1$ donne un nombre un peu moins élevé d'approximations, en partie grâce à la fonction $\chi_7$ qui a un moins grand nombre de points fixes (on ne fait le bitwise and que de deux bitstrings). On n'a ainsi $(\chi_7(x) \lll 1) = 2 \cdot x + 1$ et $(\chi_7(x) \lll 1) = 2 \cdot x + 2$ que pour 5 valeurs de $x \in \mathbb{Z}_{128}$. En ne prenant que les approximations bloc par bloc, on a déjà $S(x) = 2 \cdot x + 2^{24}$ et $S(x) = 2 \cdot x + 2^{25}$ pour au moins $5 \cdot 34^3 \sim 2^{17.58}$ valeurs de $x$. Les matrices de retenues nous permettent de voir que la meilleure de ces deux approximations est

$$ S(x) = 2 \cdot x + 2^{24} $$

qui fonctionne pour $335928 \sim 2^{18.35}$ valeurs de $x$.

### 4.3.3 Boîte S de Reinforced Concrete

Les auteurs de REINFORCED CONCRETE [GKL+21] définissent différentes instances de la fonction de hachage selon le nombre premier utilisé, avec à chaque fois des $s_i$ différents pour le découpage. Ils prennent ensuite un nombre premier $p' \le \min_{i=1}^n v_i$, où les $v_i$ représentent la décomposition de $p-1$ en base $(s_i)_i$.

Chaque boîte S est définie par

$$ S_i: \begin{cases} \mathbb{Z}_{s_i} & \rightarrow \mathbb{Z}_{s_i} \\ x & \mapsto \begin{cases} \text{MIMC}(x) & \text{si } x < p' \\ x & \text{si } x \ge p' \end{cases} \end{cases} $$

où MIMC est une permutation sur $\mathbb{F}_{p'}$ définie dans [AGR+16].

La permutation a été définie pour trois nombres premiers $p_{\text{BLS}} \sim 2^{255}$, $p_{\text{BN254}} \sim 2^{254}$ et $p_{\text{ST}} \sim 2^{250}$, les deux premiers pour des applications dans les SNARKs et le dernier pour des applications ne demandant pas de nombres premiers compatibles avec des courbes elliptiques pairing-friendly.

Contrairement au cas de TIP5 et MONOLITH où le choix des $I_{\text{up}}$, $I_{\text{low}}$, $(s_i)_{i \in [1,n]}$ ne forçait que 241 points fixes dans le cas $p_{\text{goldi}}$ et ne force pas de point fixe dans le cas $p_{\text{mers}}$, ici le choix des $s_i$ crée déjà $\prod_{i=1}^{n-1} (s_i - v_i)$ points fixes. Le choix de prendre une permutation sur $\mathbb{F}_{p'}$ avec un
nombre premier $p'$ inférieur ou égal à tous les $v_i$ au lieu d'une permutation sur $\mathbb{Z}_{v_i}$ fait monter cette quantité de points fixes forcés à

$$ \sum_{i=1}^{n} \prod_{j=1}^{i-1} (s_j - p') \cdot (v_i - p') $$

(cette quantité ayant été majorée par $\prod_{i=1}^{n}(s_i - p')$ dans l'analyse de sécurité de REINFORCED CONCRETE).

En prenant en compte les points fixes des instances de MIMC choisies, on peut avoir une estimation plus précise du nombre de points fixes de $S$. Les nombres de points fixes pour les différentes instanciations de REINFORCED CONCRETE sont consignés dans le tableau 7.

# 5 Conclusion

Notre première cryptanalyse de TIP5 nous donne une idée plus précise de la marge de sécurité de la fonction de hachage. On passe en particulier de 2 tours de marge à aucune marge de sécurité pour les attaques par collision et on voit que la permutation complète sans la première couche de boîte S possède des propriétés qui la distinguent d'une famille de permutation aléatoire. La présence d'une première rangée de boîte S sans diffusion étant particulièrement surprenante puisqu'elle introduit un coût sans aucune garantie de sécurité supplémentaire. Il pourrait donc être intéressant d'ajouter une matrice MDS avant ce premier tour puisque cela rajoute de la diffusion, pour un coût faible.

Les boîtes split-and-lookup semblent être une manière prometteuse de concevoir des fonctions à la fois efficaces en évaluation et en preuve. Les approximations linéaires semblent être un critère de choix pertinent pour ces boîtes S puisqu'une telle approximation peut être exploitée dans une attaque algébrique. Notre méthode donne une première approche pour évaluer ces probabilités mais se limite à des petits coefficients $a, b$. Il pourrait être intéressant dans un futur travail d'étendre ces méthodes à de plus grand coefficients. Aussi, la recherche des meilleures constantes $c$ pour $a, b$ fixés a été faite à la main et il serait intéressant d'avoir des méthodes systématiques permettant de trouver de bonnes constantes, mais aussi des bornes supérieures sur ces probabilités d'approximation.

Enfin, nous n'avons pour le moment qu'une attaque sur TIP5 ainsi que des observations sur les boîtes S de TIP5, MONOLITH et REINFORCED CONCRETE. Il serait intéressant de chercher des attaques sur les deux dernières primitives, que ce soit en exploitant leur structure ou des faiblesses de leurs split-and-lookups.
Références

[AGR<sup>+</sup>16] Martin Albrecht, Lorenzo Grassi, Christian Rechberger, Arnab Roy, and Tyge Tiesen, *MiMC : Efficient encryption and cryptographic hashing with minimal multiplicative complexity*, Cryptology ePrint Archive, Paper 2016/492, 2016, https://eprint.iacr.org/2016/492.

[BBLP22] Augustin Bariant, Clémence Bouvier, Gaëtan Leurent, and Léo Perrin, *Algebraic attacks against some arithmetization-oriented primitives*, IACR Transactions on Symmetric Cryptology (2022), 73–101.

[BCD<sup>+</sup>20] Tim Beyne, Anne Canteaut, Itai Dinur, Maria Eichlseder, Gregor Leander, Gaëtan Leurent, María Naya-Plasencia, Léo Perrin, Yu Sasaki, Yosuke Todo, et al., *Out of oddity–new cryptanalytic techniques against symmetric primitives optimized for integrity proof systems*, Advances in Cryptology–CRYPTO 2020 : 40th Annual International Cryptology Conference, CRYPTO 2020, Santa Barbara, CA, USA, August 17–21, 2020, Proceedings, Part III 40, Springer, 2020, pp. 299–328.

[BCP23] Aurélien Boeuf, Anne Canteaut, and Léo Perrin, *Propagation of subspaces in primitives with monomial Sboxes : Applications to Rescue and variants of the AES*, IACR Transactions on Symmetric Cryptology **2023** (2023), no. 4, 270–298.

[BDPVA07] Guido Bertoni, Joan Daemen, Michaël Peeters, and Gilles Van Assche, *Sponge functions*, ECRYPT hash workshop, vol. 2007, 2007.

[BFS15] Magali Bardet, Jean-Charles Faugère, and Bruno Salvy, *On the complexity of the F5 Gröbner basis algorithm*, Journal of Symbolic Computation **70** (2015), 49–70.

[BKP16] Alex Biryukov, Dmitry Khovratovich, and Léo Paul Perrin, *Multiset-algebraic cryptanalysis of reduced Kuznyechik, Khazad, and secret SPNs*, IACR Transactions on Symmetric Cryptology **2016** (2016), no. 2.

[BS01] Alex Biryukov and Adi Shamir, *Structural cryptanalysis of SASAS*, Advances in Cryptology–EUROCRYPT 2001 : International Conference on the Theory and Application of Cryptographic Techniques Innsbruck, Austria, May 6–10, 2001 Proceedings 20, Springer, 2001, pp. 395–405.

[BSV07] Thomas Baigneres, Jacques Stern, and Serge Vaudenay, *Linear cryptanalysis of non binary ciphers : (with an application to SAFER)*, International Workshop on Selected Areas in Cryptography, Springer, 2007, pp. 184–211.

[FGHR14] Jean-Charles Faugère, Pierrick Gaudry, Louise Huot, and Guénaël Renault, *Sub-cubic change of ordering for Gröbner basis : a probabilistic approach*, Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation, 2014, pp. 170–177.

[GKL<sup>+</sup>21] Lorenzo Grassi, Dmitry Khovratovich, Reinhard Lüftenegger, Christian Rechberger, Markus Schofnegger, and Roman Walch, *Reinforced concrete : A fast hash function for verifiable computation*, Cryptology ePrint Archive, Paper 2021/1038, 2021, https://eprint.iacr.org/2021/1038.

[GKL<sup>+</sup>23] ————, *Monolith : Circuit-friendly hash functions with new nonlinear layers for fast and constant-time implementations*, Cryptology ePrint Archive, Paper 2023/1025, 2023, https://eprint.iacr.org/2023/1025.

[Jea16] Jérémy Jean, *TikZ for Cryptographers*, https://www.iacr.org/authors/tikz/, 2016.

[Rec23] Christian Rechberger, *On the history of FHEMPCZK-friendly symmetric crypto*, https://who.paris.inria.fr/Leo.Perrin/rescale/slides/Christian-STAP-2023.pdf, 2023.

[Sal23] Robin Salen, *Two additional instantiations from the Tip5 hash function construction*, https://toposware.com/paper tip5.pdf, 2023.
[SLS+23] Alan Szepieniec, Alexander Lemmens, Jan Ferdinand Sauer, Bobbin Threadbare, et al., *The tip5 hash function for recursive starks*, Cryptology ePrint Archive (2023).

[SWMSP17] Ana Sălăgean, Richard Winter, Matei Mandache-Sălăgean, and Raphael C-W Phan, *Higher order differentiation over finite fields with applications to generalising the cube attack*, Designs, Codes and Cryptography 84 (2017), 425–449.
# A Preuve de la bijectivité des boîtes S split-and-lookup

On prouve ici que les split-and-lookups telles que définies dans Définition 8 sont bijectives sur $\mathbb{F}_p$. On commence par prouver le lemme suivant :

**Lemme 5 (Décomposition de $\mathbb{F}_p$) La fonction**

$$ \text{Decomp: } \mathbb{F}_p \to \prod_{k=0}^{n} \mathbb{Z}_{s_1} \times \cdots \times \mathbb{Z}_{s_{k-1}} \times [0, v_k - 1] \times \{v_{k+1} \dots v_n\} $$

est bijective.

**Preuve 7 On commence à montrer que les sorties de Decomp sont toutes dans $\prod_{k=0}^{n} \mathbb{Z}_{s_1} \times \cdots \times \mathbb{Z}_{s_{k-1}} \times [0, v_k - 1] \times \{v_{k+1} \dots v_n\}$. Soit $0 \le x \le p-1$ et Decomp($x$) = ($x_1 \dots x_n$).**

- Si pour tout $k$, $x_k \ge v_k$, alors $x = \sum_{k=1}^{n} \prod_{i=1}^{k-1} s_i \cdot x_k \ge \sum_{k=1}^{n} \prod_{i=1}^{k-1} s_i \cdot v_k = p-1$, donc $x = p-1$ et Decomp($x$) = ($v_1 \dots v_n$).

- Sinon, il existe $k$ tel que $x_k < v_k$. En prenant le plus grand $k$ tel que cela arrive, on a pour $i > k, x_i \ge v_i$. De plus, pour $i > k$, on a $\sum_{j=i+1}^{n} \prod_{l=1}^{j-1} s_l \cdot v_j + \prod_{l=1}^{i-1} s_l \cdot (v_i+1) > p-1$. Cela implique donc que $x_i \le v_i$ pour $i > k$. On a donc bien Decomp($x$) $\in \mathbb{Z}_{s_1} \times \cdots \times \mathbb{Z}_{s_{k-1}} \times [0, v_k - 1] \times \{v_{k+1} \dots v_n\}$.

Comme

$$ \left| \prod_{k=0}^{n} \mathbb{Z}_{s_1} \times \cdots \times \mathbb{Z}_{s_{k-1}} \times [0, v_k - 1] \times \{v_{k+1} \dots v_n\} \right| = 1 + \sum_{k=1}^{n} \prod_{i=1}^{k-1} s_i \cdot v_k = p = |\mathbb{F}_p| $$

et Decomp est déjà injective de $\mathbb{F}_p$ dans $\prod_{i=1}^{n} \mathbb{Z}_{s_i}$, elle est bien bijective.

Il reste à montrer que $\prod_{k=0}^{n} \mathbb{Z}_{s_1} \times \cdots \times \mathbb{Z}_{s_{k-1}} \times [0, v_k - 1] \times \{v_{k+1} \dots v_n\}$ est stable par $S_1 \times \cdots \times S_n$. Pour cela, on remarque que $S_k(v_k) = v_k$ et que pour $0 \le x_k < v_k$ on a $0 \le S_k(x_k) < v_k$ (indépendamment de si $k \in I_{\text{low}}$ ou $k \in I_{\text{up}}$). Cela prouve la bijectivité de S.

# B Bilan des approximations linéaires trouvées

<table><caption>FIGURE 7 – meilleures approximations linéaires pour les boîtes S considérées.</caption><thead><tr><th>Primitive</th><th>p (log)</th><th>approximation (log)</th><th>source</th></tr></thead><tbody><tr><td rowspan="2">TIP5</td><td rowspan="2">p<sub>goldi</sub> (64)</td><td>7.9</td><td>[SLS<sup>+</sup>23]</td></tr><tr><td><b>15.81</b></td><td>Section 4.3.1</td></tr><tr><td rowspan="2">MONOLITH</td><td rowspan="2">p<sub>goldi</sub> (64)</td><td>7.9</td><td>[GKL<sup>+</sup>23]</td></tr><tr><td><b>41.76</b></td><td>Section 4.3.2</td></tr><tr><td rowspan="5">REINFORCED CONCRETE</td><td rowspan="2">p<sub>mers</sub> (31)</td><td>4</td><td>[GKL<sup>+</sup>23]</td></tr><tr><td><b>18.35</b></td><td>Section 4.3.2</td></tr><tr><td rowspan="2">p<sub>BLS</sub> (255)</td><td>134.54</td><td>[GKL<sup>+</sup>21]</td></tr><tr><td>140.6</td><td>Section 4.3.3</td></tr><tr><td rowspan="2">p<sub>BN254</sub> (254)</td><td>131.17</td><td>[GKL<sup>+</sup>21]</td></tr><tr><td>132.6</td><td>Section 4.3.3</td></tr><tr><td rowspan="2">p<sub>ST</sub> (250)</td><td>86.35</td><td>[GKL<sup>+</sup>21]</td></tr><tr><td>88.6</td><td>Section 4.3.3</td></tr></tbody></table>

Les nombres marqués en **gras** indiquent une amélioration substantielle par rapport aux analyses de points fixes des analyses de sécurité initiales.