Analyse de primitives symétriques

Algorithmes de chiffrement par bloc

Un algorithme de chiffrement par bloc, ou chiffrement (par bloc), ou chiffre (par bloc), est une famille d’applications injectives d’ensembles de départ et d’arrivée finis. On ne s’intéressera dans ce manuscrit qu’à des familles d’applications d’un ensemble de chaînes binaires de taille fixe vers lui-même, c’est à dire à des applications de type E∶ {0, 1} κ ×{0, 1} n → {0, 1}n telles que E(k, ⋅) est une permutation pour tout k ∈ {0, 1} κ . On appelle κ la taille de clef et n la taille de bloc de E. Les tailles habituelles sont κ ∈ {64, 80, 128, 192, 256} et n ∈ {64, 128, 256}, bien que les clefs de 64 ou 80 bits ne soient plus considérées de nos jours comme apportant une sécurité suffisante.

On requiert aussi que E et son inverse E−1 soient calculables efficacement, bien qu’en fonction des applications il puisse être suffisant qu’un seul des deux le soit. L’emploi le plus courant qui d’un chiffrement par bloc est d’assurer la confidentialité de communications. Deux entités A et B partageant une clef k pour le même chiffrement peuvent communiquer par l’intermédiaire de messages chiffrés c ∶= E(k, p), c ′ ∶= E(k, p′ ), etc. Le second argument p de E est généralement appelé texte clair, et le résultat c est généralement appelé texte chiffré. Nous ne nous intéresserons pas ici à la question de savoir comment A et B obtiennent le secret partagé k, les techniques utilisées à cette fin étant nettement différentes de celles employées pour les chiffrements par bloc. Si E est tel que la permutation E(k, ⋅) est difficile à inverser quand k est inconnu, A et B pourraient s’attendre à ce qu’un canal de communication sûr consiste à injecter leurs messages vers les chaînes m0∣∣m1∣∣ . . . ∣∣m` de tailles multiples de n et à envoyer les chiffrés E(k, m0)∣∣ E(k, m1)∣∣ . . . ∣∣ E(k, m`). Ce schéma comporte cependant deux problèmes de taille, indépendamment de la sécurité du chiffrement choisi : en premier lieu, le schéma est déterministe, c’est à dire que chiffrer le même texte clair plusieurs fois donne toujours le même chiffré pour résultat. Un adversaire passif espionnant la conversation sur le canal entre A et B peut donc détecter quand deux messages identiques ont été envoyés. En second lieu, la communication n’est pas authentifiée. Un adversaire actif présent sur le canal peut supprimer et modifier certains des blocs d’un message, ajouter des blocs d’un précédent message, ou encore ajouter des blocs générés aléatoirement. Tout ceci peut être fait sans que A et B ne détectent qu’une entité extérieure agit sur le canal avec des intentions hostiles.

Sécurité des chiffrements par bloc

Le but de cette section est d’expliquer brièvement en quoi consiste un bon chiffrement par bloc, d’un point de vue pratique. Nous commençons toutefois par d’abord définir une idéalisation de cette primitive, sous la forme du modèle du chiffrement idéal.

Définition 1.1 (Chiffrement par bloc idéal). Un chiffrement par bloc idéal E est une application {0, 1} κ × {0, 1}n → {0, 1}n telle que toutes les permutations E(k, ⋅) sont tirées aléatoirement et uniformément parmi les permutations de {0, 1}n .

Cette notion correspond intuitivement à ce qu’on peut atteindre de mieux étant donnée la définition d’un chiffrement par bloc. Pour de petites valeurs de n, par exemple 20, on peut implémenter un chiffrement idéal en utilisant un algorithme de génération de permutation, par exemple celui attribué de façon variable à Fisher, Yates, Knuth, etc. [FY48]. Un tel algorithme permet de tirer uniformément une permutation pour chaque clef, mais déterminer la permutation associée à une clef donnée a une complexité de O(2n ) en temps et en mémoire. Il n’est donc pas envisageable de suivre cette approche pour les tailles classiques de bloc n ≥ 64 utilisées en cryptographie. Même pour de petites valeurs de n, l’algorithme de Fisher et al. requiert une quantité considérable d’aléa paramétrisé par une clef, ce qui peut constituer un obstacle à son utilisation. En pratique, les chiffrements utilisés ne sont donc que des « approximations » de chiffrements idéaux. Une façon utile, bien qu’essentiellement théorique, de quantifier la sécurité d’un chiffrement par bloc est alors précisément de mesurer à quel point celui-ci est éloigné d’un chiffrement idéal. Informellement, ceci est fait en bornant supérieurement l’avantage sur une réponse aléatoire qu’a un adversaire de distinguer s’il interagit avec une permutation tirée aléatoirement ou avec une instance du chiffrement paramétré avec une clef inconnue. Cette proposition peut être précisée sous la forme suivante, similaire à celle qui peut être trouvée par exemple dans [BKR00] :

Définition 1.2 (Permutations pseudo-aléatoires (PRP)). Soit E un chiffrement par bloc de taille de clef κ et de taille de bloc n. On note Π2n l’ensemble des permutations sur les chaînes binaires de longueur n ; x$ ← S l’action de tirer x aléatoirement et uniformément parmi les éléments de l’ensemble S ; Af un algorithme ayant accès à un oracle f et qui retourne un unique bit. On définit alors l’ avantage PRP de A pour E, écrit AdvPRP E (A) comme : AdvPRP E (A) = ∣Pr[A f = 1 ∣ f $ ← Π2n ] − Pr[A f = 1∣ f ∶= E(k, ⋅), k $ ← {0, 1} κ ]∣.

La notion de PRP est utile pour par exemple prouver qu’une construction utilisant un chiffrement par bloc n’est pas significativement moins sûre que ce dernier. Un tel résultat est typiquement obtenu en définissant une fonction d’avantage pour la construction de haut niveau similaire à celle utilisée dans la sécurité PRP, et en montrant que cet avantage n’est pas plus qu’une fonction « raisonnable » de la sécurité PRP. Par exemple, dans le cas de [BKR00], la construction de haut niveau considérée est CBC-MAC. Toutefois, la définition 1.2 n’est pas constructive, dans le sens où elle ne donne pas de procédure efficace permettant de calculer la sécurité PRP d’un chiffrement par bloc en général. Un des objectifs majeurs de la cryptographie symétrique consiste à analyser explicitement des instances de chiffrements par blocs dans le but d’établir leur sécurité concrète contre certaines attaques. S’inspirant de la terminologie de la définition 1.2, ceci revient à trouver des algorithmes pour lesquels q, t et l’avantage PRP sont connus. Une telle attaque sur un chiffrement E permet alors de borner inférieurement sa sécurité PRP en un certain point (q, t). Cependant, en réalité, déterminer complètement le niveau de sécurité apporté par un chiffrement est plus complexe que ce que la définition 1.2 pourrait faire croire. Des caractéristiques importantes des attaques qui ne sont pas visibles dans cette définition sont la complexité en mémoire ; la quantité de calculs qui ont lieu en ligne ou hors ligne ; savoir si les attaques s’appliquent aussi bien à toutes les clefs ou à seulement certaines d’entre elles ; savoir si elles permettent de retrouver k quand f est une instance de E, ou un algorithme équivalent à E(k, ⋅), etc. Nous consacrons le reste de cette section à introduire quelques éléments caractéristiques d’attaques de chiffrements par bloc.

Table des matières

1 Introduction
2 Présentation de mes travaux
I Préliminaires
3 Introduction aux chiffres par bloc
4 Introduction aux fonctions de hachage
II Nouvelles attaques et constructions pour chiffres par bloc
5 Attaques en clefs liées améliorées sur les schémas Even-Mansour
6 Matrices de diffusion issues de codes géométriques
7 La boîte-S Littlun et le chiffre Fly
III Nouvelles attaques sur SHA-1
8 Présentation de SHA-1
9 Une brève histoire des attaques en collision sur SHA-1
10 Collisions à initialisation libre pour SHA-1
11 Attaques en préimages sur SHA-1
Table des matières
Conclusion
Liste des figures
Liste des tables
Bibliographie

Télécharger le rapport complet