Attaque "Square" sur AES 4 et 5 tours

Contexte et objectifs

Les fichiers 'sets/4_rounds_ciphertexts' et 'sets/5_rounds_ciphertexts' contiennent des paires de textes clairs/chiffrés (des lambda-sets) résultants respectivement d'un chiffrement AES-128 à 4 et 5 tours.

L'objectif est de retrouver les deux clés (128 bits) utilisées.

Usage

Requirements

• Linux (Windows pose trop de problèmes)
• gcc installé sur la machine et accessible depuis le bash pour compiler
• CUDA installé et nvcc accessible depuis le bash
• Une carte graphique NVIDIA pour lancer le code CUDA

Compile

make

Clean les objets / éxécutables

make clean

Run l'attaque 4 tours

build/main_4r

Run l'attaque 5 tours sur CPU

build/main_5r

Run l'attaque 5 tours sur GPU (CUDA)

build/main_cuda

Run les tests

test/tests

Notions fondamentales

État

Dans AES, un « état » (state) est la représentation intermédiaire du bloc de données (128 bits) pendant le chiffrement/déchiffrement. C'est une matrice 4 x 4 d'octets, notée $(s_{i, j})$. On la représentera de la façon suivante :

Cellule

Pour $i, j \in {0, 1, 2, 3}$, la cellule $(i, j)$ est $j$-ième colonne de la $i$-ème ligne d'un état.

Cellule active

Prenons $(s^{(t)})_t$ un ensemble de 256 états et fixons une cellule $(i, j)$. Cette cellule est dite active à travers $(s^{(t)})_t$ si

$$ {s_{i, j}^{(t)} : t = 0, ..., 256} = {0, ..., 255} $$

c'est-à-dire lorsque la cellule est traversée par tous les octets à travers les 256 états.

Cellule inactive

Soit $(s^{(t)})_t$ un ensemble de 256 états et fixons une cellule $(i, j)$. Cette cellule est dite inactive à travers $(s^{(t)})_t$ si

$$ {s_{i, j}^{(t)} : t = 0, ..., 255} = {c} $$

où $c$ est une valeur d'octet constante. C'est-à-dire que la cellule doit garder sa valeur constante au travers des 256 états.

$\Lambda$-set

On dit qu’un ensemble de 256 états $(s^{(t)})_{t=0...255}$ est un $\Lambda$-set si chacune de ses cellules est soit active, soit inactive.

Cellule équilibrée

Soit $(s^{(t)})_t$ un ensemble de 256 états et soit $(i, j)$ une cellule. On dit que cette cellule est équilibrée à travers $(s^{(t)})_t$ si le XOR des 256 valeurs prises par cette cellule dans $(s^{(t)})_t$ fait 0, c'est-à-dire lorsque

$$ \bigoplus_{t = 0}^{255} s_{i, j}^{(t)} = 0 $$

L'idée derrière l'attaque

L'idée est la suivante : lorsque l'on donne en entrée d'AES un $\Lambda$-set avec (au moins) une cellule active, toutes les cellules deviennent équilibrées en entrée du tour 4.

Plus précisément, si l'on note les cellules active en gris, les cellules inatives en blanc et les cellules équilibrées avec une flèche, voici comment se propage le $\Lambda$-set au fur et à mesure des opérations de l'AES :

Ceci va alors nous servir de distingueur pour rejeter des hypothèses de clé.

Principe de l'attaque

Sur AES 4 tours

On envoie, en entrée d'AES, 256 textes clairs (256 états) dont une cellule est active et les autres inactives. Une fois les chiffrés obtenus, on veut remonter le chiffré à l'état en entrée du tour 4.

Pour ce faire il est facile d'inverser ShiftRows et SubBytes (il n'y a pas de MixColumns au dernier tour), mais il faut connaître la clé du tour 4 pour inverser $ARK$. On fait alors une hypothèse de clé pour chaque cellule de l'état final (autrement dit pour chaque octet de chaque chiffré on fait une supposition de clé). Cette cellule correspond à la position de notre hypothèse d'octet dans la clé $K_4$, ce sera notre cible. On veut savoir si cette cellule une fois ramenée au début du tour 4 est bien équilibrée. Notons que ShiftRows décale la cellule vers une autre position, mais cela ne change rien puisque de toutes façons toutes les cellules doivent être équilibrées.

Il suffit donc d'appliquer $ARK^{-1}$ à la cellule cible puis $SB^{-1}$ pour retrouver la valeur prise par la cellule décalée par ShiftRows en entrée du tour 4. Si le résultat ne donne pas une cellule équilibrée, alors l'hypothèse sur la clé était fausse. Sinon, on sauvegarde l'octet de clé à la position de notre cellule cible.

En faisant cela on trouve en moyenne deux candidats par octet de clé : la bonne valeur et un faux. En effet, XORer les 256 valeurs pour un octet de clé qui n'est pas le bon revient à du bruit/random donc le résultat est un nombre aléatoire entre 0 et 255, d'où le fait que l'on a une chance sur 256 que cela fasse 0 et que donc la cellule soit équilibrée. On a donc une chance sur 256 par hypothèse d'octet d'avoir un faux, mais comme on fait 256 hypothèses par octet, on a en moyenne un faux positif par octet en plus de la bonne valeur.

Pour savoir lequel est le bon on peut soit refaire l'attaque avec un autre $\Lambda$-set en entrée puis faire l'intersection des ensembles candidats (c'est ce que fait notre code), soit tester toutes les clés possibles avec ces candidats et voir laquelle est la bonne.

Avec plusieurs $\Lambda$-sets, la probabilité de trouver un faux pour un guess est $1/256^{\text{nb de sets}}$.

Notons que l'on obtient alors la clé du tour 4. Il faut encore utiliser invKeySchedule pour remonter à la clé maître.

Pour s'assurer que l'on a retrouvé la bonne clé on peut alors chiffrer des messages avec la clé obtenue et comparer les chiffrés avec ceux des $\Lambda$-sets.

Sur AES 5 tours

L'idée reste la même : en partant du chiffré (sortie du cinquième tour), on veut remonter à l'état en entrée du tour 4 et vérifier si c'est équilibré.

Cependant il y a une complication. Les primitives SubBytes et ShiftRows (il n'y a pas de MixColumns au dernier tour) effectuent des permutations entre les octets mais ne les mélangent pas entre eux. Cela nous permet, lors de l'attaque sur AES 4 tours, de faire des hypothèses sur un seul octet de clé afin d'inverser ARK : la cellule ciblée est permutée par $SB$ et $SR$ puis on la XOR avec un octet de $K_4$.

Pour l'attaque sur 5 tours, la cellule ciblée lors de l'entrée du tour 4 est permutée par $SB$ et $SR$, puis est mélangée avec les autres octets de la colonne. Ensuite il y a $ARK_4$, qui va donc XORer la colonne avec 4 octets de clé, puis $SB_5$, $SR_5$ et $ARK_5$.

Ainsi, pour chaque cellule on doit faire 4 hypothèses d'octets afin d'annuler $ARK_5$, et de même ensuite pour annuler $ARK_4$. Par ailleurs, étant donné une cellule $(i, j)$, nous avons besoin de connaître les positions des 4 octets à XORer avec les hypothèses de clé : pour les connaître il faut partir de la cellule $(i, j)$ et suivre leur déplacement lors de $SR$ et $MC$ ($SB$ et $ARK$ modifient les valeurs en place).

Donc pour résumer : pour chaque cellule, on déduit les positions des 4 octets à XORer par $ARK_5$, idem pour $ARK_4$. Ensuite pour chaque chiffré des $\Lambda$-set on applique $ARK_5$ avec les hypothèses d'octets sur les 4 positions trouvées, on inverse $SR$, $SB$, idem pour $ARK_4$, puis on inverse $MC$, $SR$ et $SB$. À ce stade on peut alors vérifier si notre cellule est équilibrée ou non.

En réalité cette version naïve est très coûteuse (comme expliqué plus bas dans la section du la complexité). On peut cependant l'accélérer grandement. L'idée est d'appliquer InvMixColumns avant $ARK$ pour remonter le tour 4, de sorte qu'il ne reste qu'un octet à supposer au lieu de 4 pour $ARK_4$.

Voilà pourquoi cela fonctionne : MixColumns est une application linéaire, notons par $M$ la matrice correspondante. On a $Ms \oplus k$ si on applique d'abord MixColumns puis ARK avec l'hypothèse $k$, et $M(s \oplus k) = Ms \oplus Mk$ si on fait l'inverse. La différence entre les deux est donc $Mk \oplus k$ et ne dépend pas de l'état $s$. Donc lors du calcul d'équilibre, cette constante est sommée 256 fois, ce qui fait 0. Donc cela ne change rien au résultat sur l'équilibre des cellules.

Coût des attaques

Pour AES 4 tours

Pour chaque cellule (il y en a 16 en tout), on fait 256 hypothèses d'octet de clé. Ensuite on applique $ARK^{-1}$, $SR^{-1}$, et enfin $SB^{-1}$ à chaque chiffré (on en a 256 par $\Lambda$-set), ce qui fait en tout $\simeq 16 \times 256 \times 256 = 2^{20}$ inversions du tour 4.

Ceci est tout à fait abordable de nos jours avec un ordinateur personnel.

Pour AES 5 tours

Pour chaque colonne on fait 256 hypothèses pour chaque octet dont on a besoin dans la clé $K_5$ (on a besoin de 4 octets), 256 pour l'octet de la clé $K_4$, et on fait les opérations pour chaque élément du $\Lambda$-set (256), ce qui fait :

$$4 \times 256^4 \times 256 \times 256 = 2^{50}$$

inversions des tours 4 et 5.

Notons que sans l'astuce d'appliquer MC avant ARK on serait à

$$4 \times 256^4 \times 256^4 \times 256 = 2^{74}$$

$2^{50}$ est énorme pour un ordinateur personnel, et est infaisable en temps raisonnable sur un processeur (cela prend des dizaines de jours malgré les optimisations).

Cependant il est possible de paralléliser le calcul et de l'envoyer sur carte graphique. Cela peut faire gagner un temps énorme.

Résultats

De l'attaque sur AES 4 tours

Calculé sur CPU i7 9700K.

De l'attaque sur AES 5 tours

Notons que pour obtenir ces résultats, les calculs ont été faits sur RTX 2060, ce qui a permis de diviser le temps par au moins 20 (voire 40) par rapport au CPU (i7 9700K).

Cette attaque est massivement parallélisable et la RTX 2060 n'est pas suffisamment puissante (et n'a pas assez de threads) pour réellement paralléliser sur plus que deux octets par colonne. Cependant, avec une meilleure carte graphique (voire plusieurs en même temps), on peut encore énormément diviser le temps de calcul.

Petite remarque

L'attaque a été faite de manière réaliste : les clés utilisées pour obtenir les $\Lambda$-sets des fichiers '4_rounds_ciphertexts' et '5_rounds_ciphertexts' nous étaient inconnues au départ. L'objectif du projet était de retrouver les clés. Les autres sets ont été générés par notre code avec une clé connue pour des tests. D'ailleurs, le code n'utilise jamais les clés secrètes pour parvenir à faire l'attaque (pas de triche).

Remerciements

Je dois le début de ma compréhension de l'attaque sur 4 tours et les images explicatives de ce README à Kévin Duverger. Merci Kévin ! Le travail de nvietsang (voir son github sur cette même attaque) m'a aussi beaucoup aidé pour implémenter l'attaque sur 5 tours sur CPU.