Advanced Encryption Standard

L’AES (Advanced Encryption Standard) aussi appelé algorithme Rijndael est un algorithme de chiffrement symétrique (c’est-à-dire qui se chiffre et se déchiffre avec une même clé secrète).

Histoire :

L’AES fut inventé par les Belges Joan Daemen et Vincent Rijmen en 2000. Il remporta alors le concours AES (Advanced Encryption Standard process) qui était organisé dans le but de  remplacer le chiffrement des organisations du gouvernement des États-Unis (le DES, standard depuis 1970).

Cryptographie :

L’algorithme fonctionne par blocs de 128 bits (c’est-à-dire 16 octets) avec une clé de 128, 192 ou 256 bits.

Nous savons que l’algorithme DES (déprécié du fait de ses clés de 56 bits) a approximativement 7.2 × 1016 clés possibles. En revanche l’AES, avec seulement des clés de 128 bits, permet 3.4 × 1038 clés possibles, ce qui représente environ 4,7 × 1021 fois plus de clés. Si nous savions craquer une clé DES par seconde (c’est-à-dire tester 255 clés par seconde), alors craquer l’AES prendrait environ 32 mille milliards d’années (les clés de 256 bits, permettant 1.1 × 1077 clés, augmentent à environ 1060 le rapport de possibilités avec le DES, ce qui représente environ 3 × 1052 années).

Pour chiffrer le message, nous le découpons en blocs de 128 bits. Puis nous plaçons chacun de ces blocs dans une matrice de 4 × 4. Par exemple le bloc 0x3243f6a8885a308d313198a2e0370734 devient:

32 88 31 e0
43 5a 31 37
f6 30 98 07
a8 8d a2 34

Nous faisons la même chose avec la clé qui est ici de 128 bits :

2b 28 ab 09
7e ae f7 cf
15 d2 15 4f
16 a6 88 3c

A désigne la matrice du texte de base et B désigne la matrice de la clé.
Nous effectuons tout d’abord C = A  B
Cela nous donne C =

19 a0 9a e9
3d f4 c6 f8
e3 e2 8d 48
be 2b 2a 08

Le chiffrement se fait alors dans une boucle qui se répète 10 fois pour une clé de 128 bits, 12 fois pour 192 bits et 14 fois pour 256 bits.

Cette boucle contient 4 étapes sauf pour la 10ème boucle, voici ces 4 étapes :

  1. SubBytes
    Cette étape se fait avec la Rijndael S-BOX, c’est-à-dire une table de substitution qui permet de casser la linéarité de la structure du chiffrement. Celle-ci est constante.

    x0 x1 x2 x3 x4 x5 x6 x7 x8 x9 xA xB xC xD xE xF
    0x 63 7c 77 7b f2 6b 6f c5 30 01 67 2b fe d7 ab 76
    1x ca 82 c9 7d fa 59 47 f0 ad d4 a2 af 9c a4 72 c0
    2x b7 fd 93 26 36 3f f7 cc 34 a5 e5 f1 71 d8 31 15
    3x 04 c7 23 c3 18 96 05 9a 07 12 80 e2 eb 27 b2 75
    4x 09 83 2c 1a 1b 6e 5a a0 52 3b d6 b3 29 e3 2f 84
    5x 53 d1 00 ed 20 fc b1 5b 6a cb be 39 4a 4c 58 cf
    6x d0 ef aa fb 43 4d 33 85 45 f9 02 7f 50 3c 9f a8
    7x 51 a3 40 8f 92 9d 38 f5 bc b6 da 21 10 ff f3 d2
    8x cd 0c 13 ec 5f 97 44 17 c4 a7 7e 3d 64 5d 19 73
    9x 60 81 4f dc 22 2a 90 88 46 ee b8 14 de 5e 0b db
    Ax e0 32 3a 0a 49 06 24 5c c2 d3 ac 62 91 95 e4 79
    Bx e7 c8 37 6d 8d d5 4e a9 6c 56 f4 ea 65 7a ae 08
    Cx ba 78 25 2e 1c a6 b4 c6 e8 dd 74 1f 4b bd 8b 8a
    Dx 70 3e b5 66 48 03 f6 0e 61 35 57 b9 86 c1 1d 9e
    Ex e1 f8 98 11 69 d9 8e 94 9b 1e 87 e9 ce 55 28 df
    Fx 8c a1 89 0d bf e6 42 68 41 99 2d 0f b0 54 bb 16

    Ainsi 0x19 devient 0xd4 car, à l’intersection de la ligne 1 et de la colonne 9, nous avons la valeur 0xd4.
    C devient après la première étape de la première boucle :

    d4 e0 b8 1e
    27 bf b4 41
    11 98 5d 52
    ae f1 e5 30

     

  2. ShiftRows
    Cette étape consiste à décaler les lignes vers la gauche, la 1ère ligne aura un décalage de 0, la 2ème aura un décalage de 1, la 3ème aura un décalage de 2 et la 4ème aura un décalage de 3.
    C devient après cette étape de la première boucle :

    d4 e0 b8 1e
    bf b4 41 27
    5d 52 11 98
    30 ae f1 e5

     

  3. MixColumns
    Pour cette étape qui ne sera pas effectuée pour la dernière boucle, nous allons effectuer un calcul : la multiplication d’une matrice appartenant au corps de Galois GF(28) par un vecteur constant à 4 coordonnées.
    Cette multiplication est notée « • ».
    Une multiplication d’une matrice par un vecteur de même nombre de lignes se fait de la forme suivante pour chacune de ses colonnes :Multiplication de GF
    Nous admettons que x • 1 = x et que x • 3 = x  (x • 2) dans un corps de Galois. Nous admettons également que x • 2 consiste à insérer un 0 à la suite de x en binaire et si le 9ème bit en partant de la droite est un 1 faire x = x  0x1b. Nous appliquons ensuite un modulo 0x100 sur le résultat obtenu.
    En suivant notre vecteur, nous effectuons la multiplication de la colonne de la matrice :
    d4 = 11010100 ;
    d4 • 1 = 0xd4 ;
    d4 • 2 = 110101000 ⊕ 0x1b = 110101000 ⊕ 11011 = 110110011 = 10110011 (mod 0x100) ;
    d4 • 3 = d4 • 2  d4 • 1 = 110110011 ⊕ 11010100 = 101100111 ;
    Nous faisons ensuite la même chose pour les autres :

    bf • 1 = 10111111;
    bf • 2 = 1100101;
    bf • 3 = 11011010;
    5d • 1 = 1011101;
    5d • 2 = 10111010;
    5d • 3 = 11100111;
    30 • 1 = 110000;
    30 • 2 = 1100000;
    30 • 3 = 1010000;

    Donc d4 deviendra (2•d4)  (3•bf)  (1•5d)  (1•30) = 04
    bf deviendra (1•d4)  (2•5d)  (3•5d)  (1•30) = 66
    5d deviendra (1•d4)  (1•5d)  (2•5d)  (3•30) = 81
    30 deviendra (3•d4)  (1•5d)  (1•5d)  (2•30) = e5

    Cette opération s’effectuant 9 fois par bloc de 128 bits, elle s’effectuera 576 fois pour 1024 octets. Dans un souci de temps, les informaticiens ont alors directement intégré les tables 2, 3 (MixColumns), 9, 11, 13 et 14 (InverseMixColumns) de la multiplication de GF(28) aux processeurs de nos ordinateurs.

    La matrice est donc devenue après cette étape de la première boucle :

    04 e0 48 28
    66 cb f8 06
    81 19 d3 26
    e5 9a 7a 4c

     

  4. AddRoundKey
    Cette étape va utiliser RCON :

    1 2 4 8 10 20 40 80 1b 36
    0 0 0 0 0 0 0 0 0 0
    0 0 0 0 0 0 0 0 0 0
    0 0 0 0 0 0 0 0 0 0

    Nous allons nous servir de notre dernière clé utilisée pour en générer une nouvelle. Pour trouver la première colonne de la nouvelle clé, nous allons décaler d’une ligne vers le haut la dernière colonne de la dernière clé utilisée. Comme dans l’étape SubBytes, nous allons remplacer chaque valeur de la colonne par son remplaçant dans la S-BOX. Nous allons ensuite calculer la première colonne de l’ancienne clé ⊕ ce que nous venons d’obtenir ⊕ la colonne correspondante au nombre de fois où nous avons effectué la boucle dans RCON. Nous obtenons la première colonne de notre clé. Pour calculer les autres colonnes nous aurons seulement besoin de faire la colonne correspondante dans l’ancienne clé ⊕ la colonne précédente. Nous calculons ensuite C = C ⊕ la clé obtenue.

    Par exemple pour calculer notre première clé:
    image001image003image005image007image009image011image013

    Ainsi C deviendra après cette étape de la première boucle :

    a4 68 6b 02
    9c 9f 5b 6a
    7f 35 ea 50
    f2 2b 43 49

    Une fois ces boucles effectuées, C est devenu :

    39 02 dc 19
    25 dc 11 6a
    84 09 85 0b
    1d fb 97 32

    Le message chiffré sera donc 0x3925841d02dc09fbdc118597196a0b32

Nous pouvons représenter le chiffrement et le déchiffrement à l’aide de ce schéma, ⊕ représentant C = C  B, K représentant notre clé et KN représentant notre clé numéro N.

Le principe de ce chiffrement est que chacune de ses fonctions est réversible. De plus, l’AES ne peut être décrypté totalement qu’avec une attaque par force brute ou une attaque matérielle (notamment avec l’analyse différentielle de la consommation).

Cependant, en regardant cette image chiffrée avec AES par blocs de 4 pixels, nous pouvons apercevoir la redondance :

En effet, quand des blocs de 4 pixels sont répétés plusieurs fois, ils donneront toujours la même chose, la forme sera donc visible. Pour pallier cela, nous pouvons utiliser un chiffrement à rétroaction.

Pour cela nous allons chiffrer un vecteur d’initialisation (IV) avec notre clé en AES, ce vecteur est aléatoire et sera transmis avec le message, en clair.

Nous avons ensuite plusieurs solutions, dont 2 étudiées ici :

  • La méthode Cipher FeedBack (OFB) : faire un xor avec le message en clair et le IV chiffré, cela nous donnera le premier bloc à envoyer. Pour chiffrer le second bloc, nous allons chiffrer le message précédemment chiffré puis faire un xor avec le message en clair comme dans le schéma ci-dessous :

 

  • La méthode Cipher Block Changing (CBC) : faire un xor avec le message en clair et le IV puis chiffrer le tout, ce qui nous donnera le premier bloc à envoyer. Pour chiffrer le second bloc, nous allons faire un xor avec notre précédent message et notre message en clair, ce que nous allons chiffrer comme dans le schéma ci-dessous :

L’image chiffrée avec ces méthodes deviendra alors :

L’AES-128 est utilisé pour les documents classés SECRETS tandis que l’AES-256 est utilisé pour les documents classés TOP-SECRETS.

Vous pouvez utiliser le programme mis à votre disposition ici : https://rudelune.fr/AES.jar; son code source est disponible ici : https://github.com/rudelune/aes-128_tpe.

Pour l’ouvrir vous aurez besoin de définir votre variable d’environnement de java, d’aller dans l’invite de commandes et, faire « java -jar le-chemin-vers-AES.jar ».

Laisser un commentaire

Votre adresse de messagerie ne sera pas publiée. Les champs obligatoires sont indiqués avec *

Ce site utilise Akismet pour réduire les indésirables. En savoir plus sur comment les données de vos commentaires sont utilisées.