18
historique Avec le temps, et les progrès de l'informatique, les 2 56 clés possibles du DES n'ont plus représenté une barrière infranchissable. Il est désormais possible, même avec des moyens modestes, de percer les messages chiffrés par DES en un temps raisonnable. En janvier 1997, le NIST (National Institute of Standards and Technologies) des Etats-Unis lance un appel d'offres pour élaborer l'AES, Advanced Encryption System. Le cahier des charges comportait les points suivants : évidemment, une grande sécurité. une large portabibilité : l'algorithme devant remplacer le DES, il est destiné à servir aussi bien dans les cartes à puces, aux processeurs 8 bits peu puissants, que dans des processeurs spécialisés pour chiffrer des miliers de télécommunications à la volée. la rapidité. une lecture facile de l'algorithme, puisqu'il est destiné à être rendu public. techniquement, le chiffrement doit se faire par blocs de 128 bits, les clés comportant 128,192 ou 256 bits. Le 2 octobre 2000, le NIST donne sa réponse : c'est le Rijndael qui est choisi,un algorithme mis au point par 2 belges, Joan Daemen et Vincent Rijmen. AES(Advanced Encryption Standard) Nouveau standard américain (NIST, 2000), un standard de cryptage symétrique remplaçant du DES. • FIPS 197 • Taille de bloc de 128 bits • Tailles de clé de 128, 192 et 256 bits AES AES est un algorithme de chiffrement par blocs, les données sont traitées par blocs de 128

Aes Brouillon

  • Upload
    slaill

  • View
    34

  • Download
    0

Embed Size (px)

DESCRIPTION

algorithme de cryptage

Citation preview

Page 1: Aes Brouillon

 historique

Avec le temps, et les progrès de l'informatique, les 256 clés possibles du DES n'ont plus représenté une barrière infranchissable. Il est désormais possible, même avec des moyens modestes, de percer les messages chiffrés par DES en un temps raisonnable. En janvier 1997, le NIST (National Institute of Standards and Technologies) des Etats-Unis lance un appel d'offres pour élaborer l'AES, Advanced Encryption System. Le cahier des charges comportait les points suivants :

évidemment, une grande sécurité. une large portabibilité : l'algorithme devant remplacer le DES, il est destiné à servir

aussi bien dans les cartes à puces, aux processeurs 8 bits peu puissants, que dans des processeurs spécialisés pour chiffrer des miliers de télécommunications à la volée.

la rapidité. une lecture facile de l'algorithme, puisqu'il est destiné à être rendu public. techniquement, le chiffrement doit se faire par blocs de 128 bits, les clés comportant

128,192 ou 256 bits.

Le 2 octobre 2000, le NIST donne sa réponse : c'est le Rijndael qui est choisi,un algorithme mis au point par 2 belges, Joan Daemen et Vincent Rijmen.

AES(Advanced Encryption Standard) Nouveau standard américain (NIST, 2000), un standard de cryptage symétrique remplaçant du DES.

• FIPS 197

• Taille de bloc de 128 bits

• Tailles de clé de 128, 192 et 256 bits

AES

AES est un algorithme de chiffrement par blocs, les données sont traitées par blocs de 128

Bits pour le texte clair et le chiffré. La clef secrète a une longueur de 128 bits, d’où le nom de

Version : AES 128 (il existe deux autres variantes dont la clef fait respectivement 192 et 256

Bits).

 Le Rijndael procède par blocs de 128 bits, avec une clé de 128 bit également. Chaque bloc subit une séquence de 5 transformations répétées 10 fois :

1. Addition de la clé secrète (par un ou exclusif). 2. Transformation non linéaire d'octets : les 128 bits sont répartis en 16 blocs de 8 bits (8

bits=un octet), eux-mêmes dispatchés dans un tableau 4×4. Chaque octet est transformé par une fonction non linéaire S. Le tableau est rempli colonnes par colonnes.

Page 2: Aes Brouillon

3. Décalage de lignes : les 3 dernières lignes sont décalées cycliquement vers la gauche : la 2ème ligne est décalée d'une colonne, la 3ème ligne de 2 colonnes, et la 4ème ligne de 3 colonnes.

4. Brouillage des colonnes : Chaque colonne est transformée par combinaisons linéaires des différents éléments de la colonne (ce qui revient à multiplier la matrice 4×4 par une autre matrice 4×4). Les calculs sur les octets de 8 bits sont réalisés dans le corps à 28 éléments.

5. Addition de la clé de tour : A chque tour, une clé de tour est générée à partir de la clé secrète par un sous-algorithme (dit de cadencement). Cette clé de tour est ajoutée par un ou exclusif au dernier bloc obtenu.

l'AES est un standard, donc libre d'utilisation, sans restriction d'usage ni brevet. c'est un algorithme de type symétrique (comme le DES) c'est un algorithme de chiffrement par blocs (comme le DES) il supporte différentes combinaisons [longueur de clé]-[longueur de bloc] : 128-128, 192-128 et 256-128 bits

Page 3: Aes Brouillon

Les données sont stockées dans un « carré » de 4 x 4 = 16 cases

Chaque case contient 1 octet(8 x 16 = 128 bits d’état interne)

Fonction de tourLe nombre de tours

Suivant la version (la taille de la clé), ce nombre de tours noté nr est différent. Le nombre nr est donné dans le tableau suivant.

• Pour AES-128 (clé de taille 128 bits) t = 10 tours

• Pour AES-192 t = 12 tours

• Pour AES-256 t = 14 tours

La clé de tour

À partir de la clé initiale K , le système crée nr+ 1 clés de tour ayant chacune (tk= 16 , tk= 24 ou tk= 32octets) k0, k1, · · · , kt k−1. Ces octets sont aussi classés dans un tableau de 4 lignes et Nk colonnes (Nk= 4, Nk= 6 ou Nk= 8).

Page 4: Aes Brouillon

Nous verrons ultérierement comment sont calculées ces clés en fonc-tion de la clé K du système

Addition de la sous-clé

Page 5: Aes Brouillon

Substitution par Octet

S est une fonction fixe de 8 bits vers 8 bits

–Définie comme un tableau à 2^8= 256 entrées

Page 6: Aes Brouillon

–Nécessite donc 256 octets de mémoire

• Basée sur une opération algébrique :

S(X) = Affine(Inverse(X)) où l’inverse est pris dans GF(2^8)

La boîte S

Décalage par ligne

Décalage circulaire (vers la gauche) de i cases pour la ligne numéro i, 0 ≤i ≤3

Mélange par colonne

Page 7: Aes Brouillon

MixColumn() est appliquée à chaque colonne

Corps finis : GF(2^8)

Page 8: Aes Brouillon

Cet objet mathématique est utilisé pour définir la boîte S et dans MixColumn()

• Unique corps fini à 256 éléments

–Addition = XOR

–Multiplication = ?

definition

Un polynôme irréductible veut dire qu’il n’est pas divisible par aucun autre polynôme de degré infeieur.Elle ne peuvent pas être décomposé en produits de polynômes a degré inferieur.

Exemple

Page 9: Aes Brouillon

representation

Page 10: Aes Brouillon

Présentation du système AES

Le système de chiffrement à clé secrète AES est un système basé sur le système Rijdndael construit par Joan Daemen et Vincent Rijmen. Pour AES les blocs de données en entrée et en sortie sont des blocs de128 bits, c’est à dire de 16 octets.Les clés secrètes ont au choix suivant la version du système : 128 bits(16 octets), 192 bits (24 octets) ou 256 bits (32 octets).

Le système AES effectue plusieurs tours d’une même composition de transformations.

2.3 Vue globale du fonctionnement

Page 11: Aes Brouillon

La procédure suivante décrit le fonctionnement global du système AES.

Elle prend en entrée un tableau de données St (texte clair) qui est mo-difié par la procédure et renvoyé en sortie (texte chiffré).

Les procédures appelées Round et F inalRound sont elles-mêmes composées

Page 12: Aes Brouillon

Caractéristiques et points forts de l'AES

Le choix de cet algorithme répond à de nombreux critères plus généraux dont nous pouvons citer les suivants :

securité ou l'effort requis pour une éventuelle cryptanalyse. facilité de calcul : cela entraine une grande rapidité de traitement besoins en ressources et mémoire très faibles flexibilité d'implémentation: cela inclut une grande variété de platformes et

d'applications ainsi que des tailles de clés et de blocs supplémentaires (c.f. ci-dessus). hardware et software : il est possible d'implémenter l'AES aussi bien sous forme

logicielle que matérielle (cablé) simplicité : le design de l'AES est relativement simple

Si l'on se réfère à ces critères, on voit que l'AES est également un candidat particulièrement approprié pour les implémentations embarquées qui suivent des règles beaucoup plus strictes en matière de ressources, puissance de calcul, taille mémoire, etc... C'est sans doute cela qui a poussé le monde de la 3G (3ème génération de mobiles) à adopter l'algorithme pour son schéma d'authentification "Millenage".

Page 13: Aes Brouillon

Détails techniquesL'AES opère sur des blocs de 128 bits (plaintext P) qu'il transforme en blocs cryptés de 128 bits (C) par une séquence de Nr opérations ou "rounds", à partir d'une clé de 128, 192 ou 256 bits. Suivant la taille de celle-ci, le nombre de rounds diffère : respectivement 10, 12 et 14 rounds.

Le schéma suivant décrit succintement le déroulement du chiffrement :

BYTE_SUB (Byte Substitution) est une fonction non-linéaire opérant indépendament sur chaque bloc à partir d'un table dite de substitution.

SHIFT_ROW est une fonction opérant des décalages (typiquement elle prend l'entrée en 4 morceaux de 4 octets et opère des décalages vers la gauche de 0, 1, 2 et 3 octets pour les morceaux 1, 2, 3 et 4 respectivement).

MIX_COL est une fonction qui transforme chaque octet d'entrée en une combinaison linéaire d'octets d'entrée et qui peut être exprimée mathématiquement par un produit marticiel sur le corps de Galois (28).

le + entouré d'un cercle désigne l'opération de OU exclusif (XOR). Ki est la ième sous-clé calculée par un algorithme à partir de la clé principale K.

Le déchiffrement consiste à appliquer les opérations inverses, dans l'ordre inverse et avec des sous-clés également dans l'ordre inverse.

Page 14: Aes Brouillon
Page 15: Aes Brouillon

Les attaquesL’AES resiste aux attaques les plus courants tel que :

Attaques par dictionnaires

Attaques par cryptanalyse différentielle (DC)

Attaques par cryptanalyse linéaire (LC)

La faille de AESLes chercheurs de Microsoft, de l’université belge de Leuven et de l’ENS de Paris ont découvert une faille dans l’algorithme de chiffrement AES.

Les travaux des chercheurs Dmitry Khovratovich de Microsoft Research, de Andrey Bogdanov de l’Université de Leuven et de Christian Rechberge de l’Ecole Nationale Suppérieure de Paris ont été faits dans le cadre d’un projet de "cryptanalyse".

Les chercheurs ont publié une méthode d’attaque permettant de récupérer la clé secrète utilisée pour un chiffrement AES et ce de manière cinq fois plus rapide que dans les estimations des experts en raccourcissant l’algorithme AES de deux bits.

L’attaque serait applicable à toutes les versions du chiffrement AES.

Cependant, malgré la rapidité de la méthode, elle reste très complexe et difficilement réalisable en utilisant les technologies actuelles. « Avec un trillion de machines, chacune pouvant tester un milliard de clés par seconde, cela prendrait plus de deux milliards d'années pour récupérer une clé AES 128 bits », expliquent les chercheurs.

L’attaque n’aurait donc pas, pour l’instant, d'implication pratique sur la sécurité des données des utilisateurs. Mais elle met fin au mythe du chiffrement AES, considéré auparavant comme incassable.

Les créateurs de l’algorithme AES auraient par ailleurs reconnu la validité de cette attaque