Devoir Maison 2017

Ce devoir est à réaliser dans un notebook Jupyter/SageMath. Utilisez les cellules ordinaires pour faire les calculs, et les cellules de texte (Markdown) pour ajouter vos commentaires et les réponses aux questions. Rappel : vous pouvez saisir des formules au format LaTeX entre les symboles $ (dollar).

Envoyez votre travail complet par mail. Vous pouvez soit l’exporter au format .ipynb (« File → Download as → Notebook (.ipynb) »), soit donner le lien du notebook sur https://bourbaki.math.uvsq.fr/ (et uniquement sur ce serveur).

Cryptanalyse algébrique

La cryptanalyse algébrique est une méthode très générale pour attaquer les systèmes cryptographiques, en particulier les systèmes symétriques. De façon générale, cela consiste à modéliser le secret par les inconnues d’un anneau polynomial (le plus souvent à coefficients dans $𝔽_2$), à encoder les relations entre les inconnues et les données connues (par ex., les paires clair-chiffré) dans un système polynomial, et à résoudre ce dernier par des techniques génériques, tels les SAT solvers ou les bases de Gröbner.

Dans ce devoir, nous allons étudier des cas particuliers de chiffrement par flot, qui se modélisent très bien par des systèmes polynômiaux.

On rappelle qu’un système de chiffrement par flot n’est rien d’autre qu’un générateur pseudo-aléatoire avec clef : il prend en entrée une donnée secrète, et il génère en sortie un flux infini de symboles (typiquement des bits). Le chiffrement se réalise en ajoutant le flot au clair, le déchiffrement en le soustrayant. Compromettre un système de chiffrement par flot revient à prédire la suite pseudo-aléatoire à partir d’une partie de ses bits ; dans toutes les attaques que nous allons réaliser, nous retrouverons toujours la clef secrète, ce qui permet de prédire la totalité de la suite.

LFSR

Un Linear Feedback Shift Register (LFSR) est un générateur pseudo-aléatoire très simple, qui peut être réalisé très efficacement par un circuit électronique.

Un LFSR est composé d’une suite de registres binaires, qui commencent dans un état initial (secret ou pas). À chaque itération la valeur dans le registre le plus à droite sort du LFSR pour aller constituer le bit suivant de la suite pseudo-aléatoire ; les valeurs de tous les registres sont ensuites décalées d’une position vers la droite, et les registres d’un sous ensemble prédéterminé (les taps) sont XORés (additionnés modulo 2) pour obtenir la nouvelle valeur du registre le plus à gauche. Ceci est schématisé dans la figure ci-dessous.

Dit autrement, la suite générée par un LFSR est une suite récurrente linéaire à coefficients dans $𝔽_2$. Dans l’exemple ci-dessus, la suite est définie par l’équation

$$x_{n+16} = x_n + x_{n+2} + x_{n+3} + x_{n+5}.$$

1. Un LFSR peut être représenté par un polynôme avec autant de variables que de registres. Écrivez une fonction (voir les notes sur les fonctions) qui prend en entrée

   • un polynôme à $n$ variables,
   • une liste contenant les $n$ valeurs initiales $(x_0,\ldots,x_{n-1})$,
   • un entier $i$,

   et qui renvoie $x_i$, le $i$-ème bit de la sortie du LFSR.

2. Comme le nom l’indique, un LFSR est une fonction linéaire de ses entrées. Dire quelle est la représentation matricielle de la fonction

   $$(x_0,\ldots,x_{n-1}) ↦ (x_1,\ldots,x_n).$$

   Écrire une fonction qui prend en entrée

   • une matrice $n × n$ représentant un LFSR
   • une liste contenant les $n$ valeurs initiales $(x_0,\ldots,x_{n-1})$,
   • un entier $i$,

   et qui renvoie $(x_i,\ldots,x_{n-1+i})$. Il est conseillé de consulter la documentation Sage sur les matrices

3. Jupyter permet de mesurer les performances du code Sage à l’intérieur d’une cellule. La clef magique %time au début d’une ligne, mesure le temps passé à l’exécuter.

   %time a = sum(range(10^7))
   

   Comparez les deux fonctions écrites précédemment à l’aide de %time. À partir de quelle valeur de $i$ la différence devient apparente ? Quelle est la meilleure fonction, et pourquoi ?

   Remarque : la fonction basée sur la représentation matricielle devrait pouvoir traiter des $i \sim 10^{1000}$ sans difficulté. Si cela n’est pas le cas, réfléchissez davantage, faute de quoi vous risquez de ne pas pouvoir aborder les questions suivantes.

4. Soit $L$ la matrice associée à un LFSR, le polynôme minimal du LFSR est le polynôme minimal de $L$. Montrer que le polynôme minimal définit uniquement le LFSR.

Cryptanalyse des LFSR

On suppose maintenant qu’on a accès à (une partie de) la sortie d’un LFSR à $n$ registres, mais qu’on ne connaît pas son polynôme minimal. Le but de la cryptanlyse va être de retrouver le polynôme secret définissant le LFSR.

1. Soit $x_0,x_1\ldots$ la suite générée par le LFSR, et soit $S$ la série formelle définie par

   $$S = \sum_{i≥0} x_i X^i.$$

   Soit $p$ de degré $n$ le polynôme minimal du LFSR, on définit

   $$\tilde{p} = X^n p(1/X)$$

   c’est à dire le polynôme obtenu en renversant les coefficients de $p$. Prouver que

   $$R = S · \tilde{p}$$

   est un polynôme de degré $<n$.

Soit $m≥2n$, et soit $s = S \mod X^m$. Retrouver $R$ et $\tilde{p}$ à partir de $s$ est un problème d’approximation de Padé. L’égalité prouvée au point précédent montre que

$$R = s · \tilde{p} + q · X^m.$$

Les polynômes $R$ et $\tilde{p}$ (et $q$) peuvent être calculés par une variante de l’algorithme d’Euclide étendu. Il suffit, en effet, d’exécuter l’algorithme usuel avec $s$ et $X^m$ en entrée, en arrêtant le calcul dès que l’on trouve un reste de degré $<n$.

Exemple : prenons $n=3$ et considérons la suite $(0,1,1,1,0,0,1,0)$, correspondant à la série formelle

$$S = X + X^2 + X^3 + X^6 + O(X^8)$$

Le pgcd étendu entre $X^8$ et $s$ donne successivement les relations

• $X^2 · s + X^8 = X^5 + X^4 + X^3$,
• $(X^3+X^2+1) · s + (X+1) · X^8 = X^2 + X$ ;

on déduit $\tilde{p} = X^3 + X^2 + 1$ et $R = X^2 + X$, la vérification est immédiate.

La preuve que $R$ apparaît effectivement dans la suite des restes de l’algorithme d’Euclide est simple, mais technique, c’est pourquoi nous évitons de la détailler. Le lecteur intéressé pourra se renseigner sur la théorie des sous-résultants.

2. Écrire un fonction qui prend en entrée la suite $s$ et le degré $n$ et qui calcule le polynôme minimal $p$.

   Suggestion : Vous pouvez vous inspirer de la fonction vue en TD.

   Suggestion : Berlekamp-Massey est un autre algorithme permettant de calculer le polynôme minimal $p$ à partir de la connaissance d’au moins $2n$ bits de la sortie du LFSR… et il est déjà implanté dans Sage ! Servez-vous-en pour vous aider à vérifier vos calculs.

3. Utilisez votre fonction pour trouver le polynôme minimal de la suite

   1,0,1,1,1,1,0,1,0,1,1,0,1,1,0,0,0,0,0,0,1,1,1,0,0,0,1,1,1,1,0,1,1,0,0,0,0,0,0,0,1,0,…

   (oui, $n$ n’a pas été précisé, il ne s’agit pas d’une erreur).

Générateurs non-linéaires

Il a toujours été reconnu que la linéarité des LFSR constitue une faiblesse cryptographique pour la conception des systèmes de chiffrement par flot. Néanmoins, on a cru que le simple ajout d’une couche non-linéaire pourrait suffire à définir un système robuste. Nous allons voir ici que cela n’est pas sans risques.

Soit $f$ la fonction booléenne (c.-à-d., à valeurs dans $𝔽_2$)

$$f = \sum_{i=0}^7 x_i x_{15-i}$$

et soit $L$ le LFSR défini par le polynôme

$$x^{16} + x^5 + x^3 + x^2 + 1.$$

On définit un générateur pseudo-aléatoire comme suit :

$$x_i = f(L^i(s_0,\ldots,s_{15})),$$

où $(s_0,\ldots,s_{15})$ est une clef secrète de 16 bits.

1. Écrire une fonction qui prend en entrée

   • la clef secrète ($s_0,\ldots,s_{15}$),
   • un entier $i$,

   et qui renvoie le bit $x_i$.

Dans le cadre de notre attaque algébrique, on va supposer qu’on a intercepté une certaine quantité de bits de la sortie, et on veux retrouver la clef secrète. Nous allons utiliser comme exemple la suite de bits suivante, qui correspond aux 100 premiers bits de la sortie :

2. On considère l’anneau de polynômes $𝔽_2[x_0,\ldots,x_{n-1}]$. Quel est l’idéal de la variété $V=𝔽_2^n$ ?

3. Modéliser les bits secrets $(s_0,\ldots,s_{15})$ par autant de variables d’un anneau polynomial. Écrire un système d’équations mettant en rapport les variables secrètes avec les bits de sortie, et le résoudre à l’aide des bases de Gröbner. N’oubliez pas d’ajouter les équations vues au point précédent.

   Attention : plus on connaît de bits, plus on connaît d’équations, moins de temps prendra le calcul de la base de Gröbner. D’un autre côté, le calcul de chaque équation prend lui aussi du temps. Aidez-vous avec %time pour trouver le meilleur compromis. Le choix de l’ordre monomial a lui aussi un poids important sur le calcul de la base de Gröbner, quel ordre est le plus efficace ?

   Solution : pour vous aider à tester votre code, la suite donnée est générée aléatoirement à chaque rechargement de cette page. La clef secrète pour cette suite est… ().

Un secret de 16 bits, c’est loin d’être une taille cryptographique. Attaquons maintenant un secret de 80 bits, ce qui est largement infaisable par recherche exhaustive.

On va prendre la fonction $f$ définie par

$$f = \sum_{i=0}^{39} x_i x_{79-i},$$

et le LFSR défini par le polynôme

$$x^{80} + x^9 + x^4 + x^2 + 1.$$

Le générateur est défini comme auparavant par la composition de $f$ avec $L^i$.

4. Étant donnée la suite initiale de bits

   trouver la clef secrète.

   Attention : correctement réalisé, ce calcul nécessite de ~4GB de mémoire vive. Il est recommandé de l’effectuer sur https://bourbaki.math.uvsq.fr/, ou sur une autre machine suffisamment puissante. Il peut prendre une vingtaine de minutes à compléter : armez-vous de patience (rappel : si besoin « Restart » dans le menu « Kernel » arrête le calcul en cours).

   Suggestion : avant de vous attaquer à ce problème, il peut être judicieux de faire des essais avec des systèmes similaires ayant un secret plus petit (par exemple 32 ou 64 bits). Ceci vous permettra de vérifier que votre code est capable d’attaquer un problème de grande taille.

   Solution : Encore une fois, la clef secrète est générée à chaque rechargement. Dans ce cas, elle est… ().

Générateurs hautement non-linéaires

Dans l’exemple précédent, la vulnérabilité du système est due au bas degré des équations en jeu. Cette vulnérabilité est connue depuis longtemps, et c’est pourquoi des systèmes cryptographiques réels ont utilisé des fonctions non-linéaires de haut degré. Si ces systèmes ont pendant longtemps été considérés sûrs, au début des années 2000 une suite d’attaques astucieuses ont bouleversé le monde du chiffrement par flot.

Considérons la fonction booléenne

$$f = x_{31} + \sum_{i=0}^{14} x_i x_{29-i} + x_2 x_6 x_{10} x_{13} + x_2 x_3 x_5 x_7 x_{11} x_{13} x_{17} x_{19} x_{23} x_{29} x_{31} + \prod_{i=0}^{14} x_i,$$

et le LFSR défini par le polynôme

$$x^{32} + x^7 + x^3 + x^2 + 1.$$

Comme auparavant, on définit un générateur pseudo-aléatoire par

$$x_i = f(L^i(s_0,\ldots,s_{31})).$$

1. Lisez ce papier de Courtois et Meier et mettez en pratique l’attaque qu’y est décrite.

   Attention : l’anneau de polynômes standard en Sage se révèle bien trop lent pour mettre en pratique cette attaque. Il sera opportun d’utiliser une implantation spécifique pour les polynômes booléens.

   En remplaçant

   PolynomialRing(GF(2), n, 's')
   

   par

   BooleanPolynomialRing(n, 's')
   

   on obtient un objet qui représente l’anneau quotient

   $$𝔽_2[s_0,\ldots,s_{n-1}] / I(𝔽_2^n).$$

   la majorité des fonctionnalités qui étaient définies pour l’anneau de polynômes classique le sont encore, mais l’arithmétique est beaucoup plus rapide, quoique plus gourmande en mémoire.

   En utilisant cette structure, l’attaque devrait être réalisable en une dizaine de minutes.