Ecole normale superieure Ecole doctorale de l'Ecole polytechnique Departement d'informatique Direction du 3e cycle

Reynald Lercier

Description

Niveau: Supérieur, Doctorat, Bac+8

• redaction


• mémoire

Ecole normale superieure Ecole doctorale de l'Ecole polytechnique Departement d'informatique Direction du 3e cycle Mecanismes cryptographiques pour la generation de clefs et l'authentification THESE presentee et soutenue publiquement le 22 septembre 2008 pour l'obtention du Doctorat de l'Ecole polytechnique (specialite informatique) par Sebastien Zimmer Composition du jury Rapporteurs : Reynald Lercier (CELAR et Universite de Rennes 1) Bart Preneel (Katholieke Universiteit Leuven, Belgique) Directeur de thèse : David Pointcheval (Ecole normale superieure et CNRS) Examinateurs : Pierre-Alain Fouque (Ecole normale superieure) Adi Shamir (Weizmann Institute, Israel) Jacques Stern (Ecole normale superieure et Ingenico) Jean-Marc Steyaert (Ecole polytechnique) Serge Vaudenay (Ecole polytechnique de Lausanne, Suisse) Invite : Guillaume Poupard (Ministere de la defense) Laboratoire d'Informatique de l'Ecole normale superieure, 45 rue d'Ulm, 75230 Paris Cedex 05

• membres de l'équipe crypto de l'école normale


• ecole normale


• merci


• merci de ton soutien inconditionnel


• superieure ecole doctorale

Sujets

• Redaction
• Mémoire
• Fouqué
• Poupard
• Isnard
• École polytechnique
• Dubois

Informations

• Publié par: profil-zyak-2012
• Publié le: 01 septembre 2008
• Nombre de lectures: 301
• Langue: Français
• Poids de l'ouvrage: 1 Mo

Extrait

´ ´ ´Ecole normale sup´erieure Ecole doctorale de l’Ecole polytechnique
eD´epartement d’informatique Direction du 3 cycle
M´ecanismes cryptographiques pour la
g´en´eration de clefs et l’authentification
`THESE
pr´esent´ee et soutenue publiquement le 22 septembre 2008
pour l’obtention du
´Doctorat de l’Ecole polytechnique
(sp´ecialit´e informatique)
par
S´ebastien Zimmer
Composition du jury
Rapporteurs : Reynald Lercier (CELAR et Universit´e de Rennes 1)
Bart Preneel (Katholieke Universiteit Leuven, Belgique)
´Directeur de thèse : David Pointcheval (Ecole normale sup´erieure et CNRS)
´Examinateurs : Pierre-Alain Fouque (Ecole normale sup´erieure)
Adi Shamir (Weizmann Institute, Isra¨el)
´Jacques Stern (Ecole normale sup´erieure et Ingenico)
´Jean-Marc Steyaert (Ecole polytechnique)
´Serge Vaudenay (Ecole polytechnique de Lausanne, Suisse)
Invit´e : Guillaume Poupard (Minist`ere de la d´efense)
´Laboratoire d’Informatique de l’Ecole normale sup´erieure, 45 rue d’Ulm, 75230 Paris Cedex 05Remerciements
De nombreuses personnes ont concouru, de manière directe ou indirecte, à l’élaboration de
cette thèse. Voici quelques temps déjà que je souhaite leur exprimer ma reconnaissance et je pro-
fite de l’occasion que m’offre ce mémoire pour leur formuler ces quelques sincères remerciements.
Ma plume s’adresse d’abord conjointement à David Pointcheval, mon directeur de thèse, et
à Pierre-Alain Fouque, qui a guidé mon travail au quotidien. Travailler avec vous deux a été à la
fois un plaisir et une chance : un plaisir car vous m’avez témoigné votre amitié, une chance car
j’ai bénéficié de vos deux savoir-faire scientifiques complémentaires. J’ai trouvé en vous plus que
des collègues et j’ai beaucoup appris à vos côtés.
Je souhaite aussi exprimer ma gratitude à tous les membres de l’équipe crypto de l’École
normale supérieure, passés et présents, permanents, post-doc, thésards et stagiaires. Vous avez
tous contribué à la bonne rédaction de ce mémoire, par vos apports scientifiques et en me per-
mettant de travailler dans la bonne humeur. J’adresse une pensée particulière à Vivien Dubois,
Jean-Baptiste Note et Nicolas Gama avec qui j’ai partagé de nombreux repas, passé des heures
entières à discuter et même, des fois, travaillé.
Je veux aussi remercier tous mes co-auteurs, sans lesquels aucune de mes contributions scien-
tifiques n’aurait vu le jour, en particulier Charles Bouillaguet pour m’avoir invité à participer
aux travaux qu’il avait entamés sur les attaques en seconde préimage.
Je veux exprimer des remerciements chaleureux à Reynald Lercier pour avoir rempli le rôle
de parrain au sein de la DGA et m’avoir prodigué ses précieux conseils lorsque j’étais perdu. Je
le remercie également, ainsi que Bart Preneel, pour avoir assumé la lourde tâche de rapporteurs.
Vous avez eu le courage de vous perdre dans le dédale des preuves pour vérifier leur exactitude
et je vous en suis reconnaissant.
Je veux également adresser ma gratitude à Guillaume Poupard, Adi Shamir, Jacques Stern,
Jean-Marc Steyaert et Serge Vaudenay qui me font l’amitié de participer à mon jury.
Je remercie Joëlle Isnard et Valérie Mongiat pour leur soutien logistique efficace.
J’aimerais aussi remercier le RER C, qui est un lieu propice à la réflexion de Pierre-Alain
et qui a servi de pépinière à de nombreuses idées présentes ici. Combien de fois l’ai-je entendu
arriver le matin en disant : «J’ai pensé ce matin dans le RER...».
Merci à Gwenaëlle et Nelly pour m’avoir prêté leur compagnon respectif lors des veillées
précédant les soumissions.
Enfin, je me tourne vers Alice, la dernière de ces quelques lignes mais la première dans mon
cœur. Merci pour ton soutien inconditionnel, même lors des conférences à l’étranger, et merci
pour ta relecture du manuscrit alors que tu n’y comprenais goutte. Ce mémoire te doit plus que
je ne saurais le dire.
Que tous ceux que j’aurais pu involontairement oublier me pardonnent et trouvent ici expri-
mée ma reconnaissance.
Merci à ceux qui auront le courage de tourner ces pages, je vous souhaite une bonne lecture.
iiiÀ Alice (et tant pis pour Bob),
À mon grand-père.
iiiivTable des matières
Table des figures xi
Notations xiii
Partie I Introduction Générale 1
Chapitre 1
Introduction
1.1 Brève histoire de la cryptologie . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.1.1 De l’antiquité aux premiers ordinateurs . . . . . . . . . . . . . . . . . 3
1.1.2 De la naissance d’une science . . . . . . . . . . . . . . . . . . . . . . . 4
1.2 Établissement d’un canal sécurisé . . . . . . . . . . . . . . . . . . . . . . . . 5
1.2.1 Les trois principes fondamentaux . . . . . . . . . . . . . . . . . . . . . 5
1.2.2 Modularité des protocoles . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.2.3 Constitution d’un protocole établissant un canal sécurisé . . . . . . . 6
1.3 Dérivation de clefs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.4 Modes opératoires de fonctions de hachage . . . . . . . . . . . . . . . . . . . 9
Chapitre 2
Introduction aux preuves de sécurité
2.1 Machine de Turing, réduction et adversaires . . . . . . . . . . . . . . . . . . . 12
2.1.1 Machine de Turing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.1.2 Cadre des définitions de sécurité . . . . . . . . . . . . . . . . . . . . . 13
2.1.3 Techniques de preuves . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.2 Modèle de la théorie de l’information . . . . . . . . . . . . . . . . . . . . . . 14
2.2.1 Distance statistique . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.2.2 L’entropie et ses mesures . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.2.3 Les extracteurs d’aléa . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
vTable des matières
2.3 Modèle standard . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.3.1 Hypothèses calculatoires . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.3.2 Primitives cryptographiques . . . . . . . . . . . . . . . . . . . . . . . 23
2.4 Modèles de l’oracle aléatoire et du chiffrement idéal . . . . . . . . . . . . . . 24
2.4.1 Modèle du chiffrement idéal . . . . . . . . . . . . . . . . . . . . . . . . 24
2.4.2 Modèle de l’oracle aléatoire . . . . . . . . . . . . . . . . . . . . . . . . 25
2.5 Fonctions de hachage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.5.1 Résistance aux collisions . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.5.2 Résistance en seconde préimage . . . . . . . . . . . . . . . . . . . . . 26
2.5.3 Résistance en préimage . . . . . . . . . . . . . . . . . . . . . . . . . . 26
2.5.4 Mode cascade . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
Partie II Création d’un canal sécurisé et authentifié 29
Chapitre 3
Authentification multi-facteurs et génération de clefs
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
3.1.1 Facteurs d’authentification . . . . . . . . . . . . . . . . . . . . . . . . 31
3.1.2 Clefs asymétriques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
3.1.3 Mot de passe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
3.1.4 Traits biométriques . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
3.2 Modèle de sécurité d’un échange de clefs authentifié classique . . . . . . . . . 35
3.2.1 Notions de sécurité . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
3.2.2 Modélisation et pouvoir de l’attaquant . . . . . . . . . . . . . . . . . . 36
3.3 Modèle de sécurité d’un échange de clefs multi-facteurs . . . . . . . . . . . . 37
3.3.1 Notions de sécurité . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
3.3.2 Modélisation et pouvoirs de l’attaquant . . . . . . . . . . . . . . . . . 38
3.4 Schéma proposé . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
3.4.1 Présentation du schéma . . . . . . . . . . . . . . . . . . . . . . . . . . 39
3.4.2 Preuve de sécurité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
3.5 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
3.5.1 Optimalité de la preuve . . . . . . . . . . . . . . . . . . . . . . . . . . 46
3.5.2 Paramètres pratiques . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
Chapitre 4
Analyse d’un schéma de chiffrement authentifié symétrique
vi4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . .