Université Paris Diderot Paris

Gaëtan Leurent

Description

Niveau: Supérieur, Doctorat, Bac+8
Université Paris Diderot (Paris 7) École Normale Supérieure Équipe Crypto Thèse de doctorat Construction et Analyse de Fonctions de Hachage Spécialité : Informatique présentée et soutenue publiquement le 30 septembre 2010 par Gaëtan Leurent pour obtenir le grade de Docteur de l'université Paris Diderot devant le jury composé de Directeur de thèse : David Pointcheval (CNRS & École Normale Supérieure, France) Responsable scientifique : Pierre-Alain Fouque (École Normale Supérieure, France) Rapporteurs : Anne Canteaut (INRIA-Rocquencourt, France) Bart Preneel (Katholieke Universiteit Leuven, Belgique) Examinateurs : Alex Biryukov (Université du Luxembourg, Luxembourg) Orr Dunkelman (Weizmann Institute of Science, Israël) Arnaud Durand (Université Paris 7, France) Antoine Joux (Université de Versailles & DGA, France)

• thèse dans l'équipe crypto


• co-auteurs pour les collaborations fructueuses


• belle ville du monde


• années avec moi


• esprit scientifique

Sujets

• Cryptographie symétrique
• Durand
• Fouqué
• Biryukov
• Université du Luxembourg

Informations

• Publié par: profil-feym-2012
• Publié le: 01 septembre 2010
• Nombre de lectures: 61
• Langue: Français
• Poids de l'ouvrage: 3 Mo

Extrait

Université Paris Diderot École Normale Supérieure
(Paris 7) Équipe Crypto
Thèse de doctorat
Construction et Analyse
de Fonctions de Hachage
Spécialité : Informatique
présentée et soutenue publiquement le 30 septembre 2010 par
Gaëtan Leurent
pour obtenir le grade de
Docteur de l’université Paris Diderot
devant le jury composé de
Directeur de thèse : David Pointcheval (CNRS & École Normale Supérieure, France)
Responsable scientifique : Pierre-Alain Fouque (École Normale Supérieure, France)
Rapporteurs : Anne Canteaut (INRIA-Rocquencourt, France)
Bart Preneel (Katholieke Universiteit Leuven, Belgique)
Examinateurs : Alex Biryukov (Université du Luxembourg, Luxembourg)
Orr Dunkelman (Weizmann Institute of Science, Israël)
Arnaud Durand (Université Paris 7, France)
Antoine Joux (Université de Versailles & DGA, France)Remerciements
Je tiens tout d’abord à remercier l’ENS, qui m’a fourni un environnement agréable, stimulant
et épanouissant pendant mes années de normalien, et ensuite durant ma thèse dans l’équipe
Crypto. Plus que la qualité des cours, c’est la liberté de cursus, l’ambiance, et les élèves qui font
la richesse de cette École.
Merci à tous mes amis qui ont partagé ces années avec moi, et qui ont fait de Paris la plus
belle ville du monde. Je ne vais pas tenter de faire une liste exhaustive, mais je suis sûr qu’ils se
reconnaîtront. Merci aussi à toute l’équipe Crypto avec qui j’ai eu plaisir à travailler.
Je suis reconnaissant en particulier à tous ceux qui ont aiguillé mon parcours pour m’amener
jusqu’ici : mes parents, bien sûr, qui ont cultivé mon esprit scientifique et m’ont toujours
encouragé dans mes études, puis mes professeurs d’informatique en prépa qui m’ont fait découvrir
l’algorithmique, et Louis Granboulan qui s’occupait du cours de cryptographie symétrique. C’est
ensuite à Pierre-Alain Fouque et Phong Nguyen que je dois d’être tombé dans les fonctions de
hachage. Le jeu entre les concepteurs et les cryptanalystes, et la façon dont chaque attaque
demande d’inventer de nouvelles techniques m’a tellement plu que j’ai continué jusque ici, encadré
par Pierre-Alain. Pierre-Alain a su me diriger en me laissant une grande liberté d’action, et la
réussite de ma thèse lui doit probablement beaucoup.
J’ai eu l’occasion d’écrire de nombreux articles durant ces quatre ans de thèse et je remercie
tous mes co-auteurs pour les collaborations fructueuses que nous avons pu mener.
Je remercie aussi les organismes qui ont financé mes recherches et mes déplacements durant
ma thèse : la DGA pour ma bourse de thèse, l’ENS et l’INRIA pour l’environnement matériel, le
projet européen ECRYPT (puis ECRYPT II), et le projet français SAPHIR (puis SAPHIR II).
Enfin, je remercie chaleureusement Anne Canteaut et Bart Preneel qui ont dû relire un
manuscrit imposant, ainsi que les autres relecteurs qui m’ont signalé des erreurs dans le manuscrit :
Pierre-Alain bien sûr, mais aussi Yann et Orr. Je remercie aussi les membres du Jury d’avoir
accepté d’être là aujourd’hui, en particulier ceux qui viennent de l’étranger.
iÀ Los PumasSommaire
1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
2 Présentation de mes travaux . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
I Analyse de la famille de MD4 35
3 L’attaque de Wang et al. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
4 Applications des attaques de Wang et al. . . . . . . . . . . . . . . . . . . . . . . . 81
5 Une attaque en preimage contre MD4 . . . . . . . . . . . . . . . . . . . . . . . . . 103
II La fonction de hachage SIMD 115
6 Construction de SIMD . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119
7 Analyse de SIMD . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141
III Nouvelles techniques de cryptanalyse 171
8 Auto-similarités . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 175
9 Attaques par annulation contre les schémas de Feistel généralisés . . . . . . . . . 189
IV Annexes 227
A Bestiaire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 229
Table des matières . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 239
Liste des figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 241
Liste des tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 242
Liste des algorithmes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 243
Liste des chemin différentiels . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 244
Bibliographie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 245
ivTable des matières
1 Introduction 1
1.1 Introduction à la cryptographie . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.1.1 Aperçu des systèmes cryptographiques . . . . . . . . . . . . . . . . . . . . 2
1.2 Les fonctions de hachage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.2.1 Fonctions de hachage cryptographiques . . . . . . . . . . . . . . . . . . . 5
1.2.2 Utilisations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.2.3 Définition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.3 Mode opératoire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.3.1 Construction de Merkle-Damgård . . . . . . . . . . . . . . . . . . . . . . . 12
1.3.2 Réduction de sécurité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.3.3 Attaque par extension . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
1.3.4 Attaques génériques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
1.4 Description de la famille de MD4 . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
1.4.1 Cryptanalyse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
1.4.2 La compétition SHA-3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2 Présentation de mes travaux 21
2.1 Attaques contre la famille de MD4 . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.1.1 Attaques de Wang et al. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.1.2 Attaque contre APOP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.1.3 A contre HMAC-MD4 . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.1.4 Attaque en préimage contre MD4 . . . . . . . . . . . . . . . . . . . . . . . 23
2.2 La fonction de hachage SIMD . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
2.2.1 Construction de SIMD . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
2.2.2 Analyse de sécurité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.3 Nouvelles attaques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
2.3.1 Attaques contre Lesamnta . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
2.3.2 A contre SHAvite-3 . . . . . . . . . . . . . . . . . . . . . . . . . 28512
2.3.3 Attaques contre Edon-R . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
2.3.4 A contre ESSENCE . . . . . . . . . . . . . . . . . . . . . . . . . . 30
2.3.5 Attaques contre IFSB . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
2.4 Autres travaux . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
2.4.1 Attaque par canal auxiliaire contre HMAC-SHA1 . . . . . . . . . . . . . . 31
2.4.2 Remarques sur le modèle de l’oracle aléatoire . . . . . . . . . . . . . . . . 32
2.5 Mes publications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
vNotations
F une fonction de hachage
H un haché
M un message
f une fonction de compression
x une variable de chaînage
m un bloc de message
32Z 32 l’anneau des entiers modulo 22
F le corps à 257 éléments257
nkx une rotation de k bits appliquée à x
addition modulaire
∨ ou bit-à-bit (opération booléenne)
∧ et (op bo
⊕ ou exclusif bit-à-bit (opération booléenne)
le mot de 32-bit composé uniquement de zéros (0x00000000)
le mot de composét de uns (0xffffffff)
x le complémentaire de x
[k] [k]x le k+1-ème bit de x, i.e. x = (xok) mod 2
x← $ x est choisi aléatoirement
On utilisera des indices entre 0 et n− 1 pour indexer n éléments.
vi
10Chapitre 1
Introduction
1.1 Introduction à la cryptographie
La cryptographie est utilisée depuis l’antiquité pour les communications militaires, mais elle
prend toute son importance au vingtième siècle avec le développement des télécommunications.
Elle permet d’assurer la confidentialité des données, mais aussi de garantir l’intégrité d’un
document et d’identifier son auteur de façon certaine