La cryptographie symétrique
Dans la famille de la cryptographie symétrique, nous pouvons distinguer plusieurs méthodes de chiffrement, d’intégrité ou d’authentification. Nous détaillons ici brièvement certaines de ces constructions.
Les systèmes de chiffrement à flot
Les systèmes de chiffrement à flot sont aussi appelés chiffrement à la volée. Dans un système de chiffrement à flot, la clé utilisée est une suite chiffrante que l’on additionne bit à bit au message clair. La sécurité des systèmes de chiffrement à flot repose alors sur le comportement aléatoire de la suite chiffrante. Les systèmes de chiffrement à flot sont des systèmes de chiffrement rapides et bien adaptés pour les implémentations matérielles courantes.
Les systèmes de chiffrement par bloc
Parallèlement aux systèmes de chiffrement à flot, où le chiffrement se fait à la volée, on définit ce que l’on appelle système de chiffrement par bloc. Pour chiffrer un message en utilisant un système de chiffrement par bloc, on découpe ce message en blocs et on applique une fonction de chiffrement E à chacun de ces blocs. Cette fonction de chiffrement est paramétrée par une clé secrète K. Un mode opératoire nous permet alors de définir le lien entre le clair et le chiffré d’un bloc avec ceux des autres blocs. Dans la suite de cette thèse, on étudie plus particulièrement cette famille de systèmes de chiffrement symétrique.
Les fonctions de hachage
Une fonction de hachage est une fonction qui prend en entrée une chaîne de longueur arbitraire finie et qui retourne un haché de longueur fixe . Soit h une fonction de hachage :
h : {0, 1}∗ → {0, 1} m où m est la taille du haché et {0, 1} ∗ signifie ensemble des chaînes binaires de taille quelconque.
Les fonctions de hachage ne sont pas des systèmes de chiffrement puisqu’elles ne nécessitent pas l’utilisation d’une clé. Et pourtant, on les classe naturellement dans la famille des algorithmes symétriques car la plupart du temps, elles sont construites à partir de primitives dérivées de systèmes de chiffrement par bloc ou de systèmes de chiffrement à flot.
Code d’authentification de message
Ce type d’application cryptographique est plus connue sous le nom anglais « message authentification code » ou encore sous l’abréviation MAC. Les codes d’authentification permettent d’assurer l’intégrité du message ainsi que de l’authentifier. Lors de l’envoi du message on y ajoute un code d’authentification qui est l’empreinte du message obtenue grâce à un haché paramétré par une clé.
Dans cette thèse on s’intéresse plus particulièrement aux systèmes de chiffrement par bloc, et en particulier à la primitive utilisée pour chiffrer un bloc.
Système de chiffrement itératif
Les systèmes de chiffrement par bloc actuels sont itératifs. C’est-à-dire qu’une même fonction est utilisée plusieurs fois de façon itérative avec une clé différente à chaque tour. Chaque clé est appelée clé de tour. Il est courant d’utiliser un algorithme de cadencement de clé pour dériver les clés de tour à partir de la clé maître.
Définition 1.3. Un algorithme de cadencement de clé relié au système de chiffrement itératif est une fonction qui permet à partir d’une clé maître K de dériver des clés de taille égale ou inférieure. Ces clés sont appelées clés de tours. On note par Ki la clé du tour numéro i. La structure de l’algorithme de cadencement de clé est détaillée dans la section 1.3.3. Les fonctions que l’on appelle fonctions de tour sont des fonctions paramétrées par les clés de tour Ki (et donc indirectement par la clé maître K).
Chiffrement de type substitution-permutation
Une autre grande famille de systèmes de chiffrement itératif que nous allons étudier sont les schémas de type substitution-permutation (SPN : »Substitution Permutation Network »). Définition 1.8. Un système de chiffrement par bloc itératif est dit de type substitutionpermutation si la fonction de tour peut se décomposer en trois grandes étapes : une étape dite d’ajout de clé, une étape de substitution qui est non-linéaire et une étape de permutation qui est linéaire. Afin de permettre le déchiffrement la fonction de tour doit être une bijection. La figure 1.3 représente les trois étapes importantes de la fonction de tour d’un système de chiffrement de type substitution permutation. Cette définition très large nous permet de faire rentrer un grand nombre de systèmes de chiffrement dans la catégorie des SPN. L’exemple le plus connu de système de chiffrement de ce type est “Rijndael”. Plusieurs versions ont été standardisées par le NIST en 2000 [DR99] sous le nom de « Advanced encryption standard » (AES). Une description de cet algorithme est donnée dans la section 1.4.2. Outre l’AES, dans cette thèse nous nous sommes particulièrement intéressés au système de chiffrement PRESENT [BKL+07]. Tout au long de ce manuscrit nous faisons référence à ce système de chiffrement de type substitution-permutation. Une description de cet algorithme est faite dans la section 1.4.1.
Les différentes primitives
La partie de confusion
La partie de confusion du système de chiffrement est la seule partie non-linéaire du système de chiffrement par bloc. Dans un système de chiffrement de type substitutionpermutation elle correspond à la partie de substitution. Dans cette thèse on s’intéresse aux systèmes de chiffrement pour lesquels l’état interne de la partie de substitution est divisé en mots de petite taille . Une application non-linéaire est appliquée en parallèle à chacun de ces mots. Cette application non-linéaire qui peut être la même ou être différente pour chacun des mots du système de chiffrement est appelée boîte-S. Dans les systèmes de chiffrement de type substitution-permutation la fonction de tour doit être bijective afin de pouvoir déchiffrer. Ainsi les boîtes-S qui composent ce système de chiffrement sont toujours bijectives. Dans les systèmes de chiffrement de type Feistel nous n’avons pas besoin de cette contrainte de bijectivité. Pour le DES par exemple les boîtes-S sont de 6 bits vers 4. Mais pour des soucis d’implémentation la plupart des systèmes de chiffrement comportent des boîtes-S inversibles. Il existe plusieurs façons de définir les boîtes-S. On peut, par exemple, comme dans le cas de l’AES (section 1.4.2), la définir en identifiant l’espace vectoriel F n 2 au corps fini F2n et définir une permutation sur ce corps fini. L’autre méthode tout aussi utilisée pour définir une boîte-S est de donner l’image point par point de la fonction (c’est le cas par exemple de la définition de la boîte-S de PRESENT donnée dans le tableau 1.1).
La partie de diffusion
Dans un système de chiffrement de type substitution-permutation cette partie de diffusion correspond à la permutation. Il existe plusieurs manières de diffuser l’information entre les tours. Dans le système de chiffrement PRESENT (voir la description de PRESENT dans la section 1.4.1), la permutation effectuée est une permutation dite “bit à bit”. Un autre exemple de permutation que l’on peut citer est la permutation dite “mot à mot” qui mélange des ensembles de bits de taille fixe. C’est ce type de permutation qui est faite dans la fonction “ShiftRows” et “MixColumns” de l’AES (voir la description de l’AES dans la section 1.4.2). Pour les schémas de Feistel, les deux types de permutations citées précédemment sont utilisés dans la partie linéaire de la fonction interne.
|
Table des matières
INTRODUCTION
1 Introduction
1.1 La cryptographie symétrique
1.2 Les systèmes de chiffrement par bloc
1.2.1 Définition
1.2.2 Chiffrement de type Feistel et ses généralisations
1.2.3 Chiffrement de type substitution-permutation
1.3 Les différentes primitives
1.3.1 La partie de confusion
1.3.2 La partie de diffusion
1.3.3 Le cadencement de clé
1.4 Quelques systèmes de chiffrement par bloc
1.4.1 PRESENT et SMALLPRESENT-[s]
1.4.2 Rijndael
1.5 Les attaques statistiques
1.5.1 Introduction
1.5.2 Les attaques statistiques
1.5.3 Les attaques sur le dernier tour
1.5.4 Complexité d’une attaque statistique
1.5.5 Les variables aléatoires étudiées
2 La cryptanalyse différentielle et ses généralisations
2.1 La cryptanalyse différentielle
2.1.1 Définition d’une attaque différentielle
2.1.2 Les primitives utilisées pour résister aux attaques différentielles
2.1.3 Calcul théorique des probabilités d’une différentielle
2.1.4 Comment retrouver de l’information sur la clé
2.1.5 Quantités importantes dans la cryptanalyse différentielle
2.1.6 Les probabilités utilisées
2.2 La cryptanalyse différentielle tronquée
2.2.1 Définition
2.2.2 L’attaque
2.2.3 Les variables aléatoires
2.2.4 Calcul théorique des probabilités
2.2.5 Attaques existantes
2.2.6 Lien avec les autres cryptanalyses
2.3 La cryptanalyse différentielle impossible
2.3.1 Définition
2.3.2 L’attaque en elle même
2.3.3 Les variables aléatoires
2.3.4 Lien avec les autres cryptanalyses
2.4 La cryptanalyse différentielle d’ordre supérieur
2.4.1 Définition
2.4.2 L’attaque
2.4.3 Les variables aléatoires
2.4.4 Lien avec les autres cryptanalyses
3 Autres attaques statistiques
3.1 Les attaques “boomerang”
3.1.1 Description
3.1.2 Les variables aléatoires étudiées
3.1.3 Lien avec les autres attaques
3.2 La cryptanalyse linéaire
3.2.1 La cryptanalyse linéaire
3.2.2 Attaque linéaire de type 1 et de type 2
3.2.3 Distribution des variables aléatoires
3.2.4 La cryptanalyse linéaire multiple et multidimensionnelle
3.3 La cryptanalyse différentielle-linéaire
3.3.1 Définition
3.3.2 L’attaque
3.3.3 Les variables aléatoires
3.4 L’attaque par saturation ou attaque intégrale
3.4.1 Description
3.4.2 Les variables aléatoires
3.4.3 Lien avec les autres cryptanalyses
3.5 Les attaques à clés liées
3.5.1 Attaque différentielle à clés liées
3.5.2 Les variables aléatoires
3.5.3 Lien avec d’autres attaques
CONCLUSION
Télécharger le rapport complet
