Un Write Up de cryptographie illustré, où l’on ne parle pas de réseaux euclidiens, où l’on n’explique pas comment transformer des polynômes en matrices, mais où l’on débat de l’importance de savoir faire la différence entre les 0 et les -1, et où l’on apprend que le bruteforce résout tous les problèmes mais qu’il vaut mieux optimiser aujourd’hui pour ne pas pleurer demain.
Ce challenge caché se débloque seulement une fois que Merry a été validé. Parce que Merry et Pippin bien sûr. Bon. Nous n’en avons donc définitivement pas fini avec FrodoKEM, on on espère juste que ce ne sera pas une trilogie à la seigneur des anneaux. On réouvre la documentation qu’on venait de fermer et on s’y remet.
L’énoncé nous explique que la faille de sécurité permettant l’attaque précédente a été résolue, et que désormais les bi-clés ne seraient réutilisées que pendant un nombre limité de requêtes. On se connecte au serveur et on constante effectivement une limite de 3000 requêtes. L’énoncé nous informe également que certaines valeurs ne sont pas correctement générées, mais nous n’avons pas accès au code source. Un dilemme se pose alors : doit-on tenter de deviner quelles sont les valeurs affectées et monter une nouvelle attaque pour les exploiter, ou bien peut-on essayer d’optimiser notre attaque précédente pour descendre en dessous des 3000 requêtes ?
On envisage brièvement l’hypothèse que $S$ et $E$ seraient générées de manière identique, ce qui nous donnerait l’égalité suivante :
$$\begin{equation} \begin{split} B & = A \cdot S + E\\ & = A \cdot S + S \\ & = (A + I) \cdot S \end{split} \end{equation}$$
et on pourrait donc retrouver $S$ de manière linéaire par une simple inversion de $A + I$. Néanmoins après quelques tentatives laborieuses on réalise que $A$ étant générée de manière aléatoire il y a de fortes chances pour qu’elle ne soit pas inversible. On décide donc d’optimiser l’attaque précédente, et on essaye de trouver une combinaison matricielle qui nous permette de deviner un coefficient en trois tentatives, plutôt qu’une ligne de 4 coefficients en 81 tentatives, ce qui nous ferait un total de $3 \times 1120 = 3360$ requêtes dans le pire des cas, donc statistiquement plutôt autour de $2240$, ce qui serait en dessous de notre limite de 3000 requêtes. On a toujours
$$Key = Dec(C - U\cdot S)$$ On pose tous les coefficients de $C$ à 0, à l’exception de $C[0][0]$ que l’on met à une valeur $c$ et on pose touts les coefficients de $U$ à 0, à l’exception de $U[0][0]$ que l’on met à une valeur $u$. Ainsi quand le serveur va calculer la clé, on aura $$Key = Dec\begin{pmatrix} c-u\cdot S[0][0] & -u\cdot S[0][1] & -u\cdot S[0][2] & -u\cdot S[0][3] \\ 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 \end{pmatrix}$$
Ainsi, si on veut isoler un seul bit, disons $S[0][0]$, il faut choisir $c$ et $u$ de telle sorte que tous les coefficients de $Key$ soit nuls à l’exception de $Key[0][0]$ et que $Key[0][0]$ dépende toujours de $S[0][0]$. Pour ça il faut choisir $u$ de telle sorte que $Dec(u) = 0$, et $c$ de telle sorte $Dec(c - u) \neq 0$. On généralise aux autres coefficients de $S$ en décalant $u$ et $v$ vers la droite. Malheureusement on constate que ce modèle nous permet seulement de distinguer les coefficients à 0 des coefficients à 1 dans $S$, et que les coefficients à -1 seront arrondis à 0 pendant notre attaque. Néanmoins cela nous permet en $2 \times 1026 = 2052$ requêtes au maximum et 1539 requêtes en moyenne de placer tous les 1 dans notre matrice $S$. Il nous reste donc environ 1500 tentatives pour distinguer les 0 des -1.
Pour cela on va reprendre notre première attaque qui consiste à deviner des lignes complètes, sauf qu’ici nous n’avons que 2 possibilités pour chaque coefficient (-1 ou 0) ce qui porte le nombre de lignes possibles à $2^4 = 16$ pour des lignes comprenant uniquement des 0 à ce stade. En effet, certaines lignes comprennent déjà des $1$ qui ne seront pas modifiés par l’attaque, donc pour chaque ligne le nombre de requêtes maximum à effectuer est de $2^{4-k}$ avec $k$ le nombre de $1$ dans la ligne. Si nous n’avions trouvé aucun 1 à l’étape précédente, nous devrions effectuer $16 \times 280 = 4480$ requêtes au maximum soit 2380 requêtes en moyenne pour distinguer les -1 des 0. C’est supérieur aux 1500 requêtes qu’il nous reste à utiliser mais si on suppose qu’il y a un 1 par ligne et qu’il nous reste donc seulement trois 0 à tester, on doit effectuer 1120 requêtes en moyenne.
Suite à de savants calculs mathématiques au doigt mouillé que nous ne reproduirons pas ici pour des raisons évidentes de crédibilité, nous décidons qu’il est possible que notre attaque se termine en moins de 3000 requêtes avec une probabilité non négligeable. On lance notre attaque sur le serveur de Merry pour pouvoir tester sa validité sans la contrainte de nombre de requêtes, et on a le plaisir de récupérer une seconde fois le flag au bout de seulement 2638 requêtes, et on se dit que c’était bien plus rapide que la dernière fois et qu’on aurait peut-être du optimiser notre attaque dès le début. On lance ensuite une première attaque attaque sur le serveur de Pippin, qui dépasse les 3000 requêtes et échoue. On la relance, et elle aboutit finalement au bout de 2297 requêtes et nous délivre le flag.
