Soutenance mémoire
Qu’est-ce qu’une fonction de hachage ?
Avant de voir une définition précise et mathématique d’une fonction de hachage, nous allons en donner un avant-goût à l’aide de métaphores culinaires. “Hacher”, littéralement, c’est réduire en petits morceaux en mélangeant. Imaginons deux plats légèrement différents que l’on hache et dont on extrait une petite cuiller. Juste en goûtant cette cuiller, on doit pouvoir savoir de quel plat cela provient. On authentifie le plat. En revanche, il nous est impossible ou extrêmement difficile d’élaborer un plat qui donnera le même “haché”. En informatique, les objets que l’on va hacher sont des fichiers, autrement dit des suites finies de 0 et de 1, ce que l’on peut également assimiler à des nombres entiers. L’idée est donc de construire une fonction, de préférence rapidement calculable, qui va de l’ensemble des entiers naturels vers un ensemble fini H qui contient tous les hachés – ou empreintes numériques – possibles. Dans la pratique H est l’ensemble de tous les mots de n bits, avec n qui vaut au moins 224 actuellement. Comme les nombres sont un peu long à écrire en binaire, on va grouper les bits par 16 et écrire une empreinte en hexadécimal. Prenons un exemple : la célèbre fonction de hachage MD5, inventée par Rivest en 1991, est fournie avec la plupart des système Unix (Linux, MacOs …). Si on calcule le haché d’un fichier vide on trouve d41d8cd98f00b204e9800998ecf8427e, chaque lettre ou chiffre représente 4 bits, il y a donc 4 × 32 = 128 bits. Ainsi chaque empreinte prend très peu de place en mémoire, 32 caractères sur notre exemple. La fonction de hachage idéale doit en fait se comporter comme une fonction aléatoire. C’est à dire que la connaissance de certaines valeurs de la fonction ne doit en aucun cas nous donner des indices pour le calcul d’une nouvelle empreinte. En cuisine, rajouter un grain de sel à un plat ne va peut être pas changer son haché. Mais, pour notre fonction idéale, changer un seul bit, ou un seul chiffre, va nous donner une empreinte radicalement différente. En effet, le nombre d’empreintes possibles est énorme : 2224 ≈ 1067, donc obtenir la même valeur ou une valeur proche est très improbable. On a, par exemple, une chance sur 20 millions de gagner au loto. Donc trouver une valeur proche serait comme gagner 9 fois de suite au loto ! Regardons maintenant le haché MD5 d’un fichier contenant juste la lettre « a » : 60b725f10c9c85c70d97880dfe8191b3 !
L’intégrité des données
On sait que lorsque l’on stocke longtemps des fichiers, ils peuvent se trouver altérés. De même, des données transmises via un réseau peuvent être légèrement modifiées. Pour vérifier l’intégrité des données, on a besoin qu’un calcul de l’empreinte ait été fait préalablement et qu’elle soit stockée ou transmise de manière sûre. On calcule alors de nouveau l’empreinte et on compare les deux valeurs. Si les empreintes diffèrent, il y a eu des modifications des données. Si elles sont semblables, on est pratiquement certain que les données n’ont pas été modifiées. C’est aussi un moyen de vérifier qu’un fichier n’a pas été échangé avec un autre contenant des virus par exemple, et ceci en gardant uniquement en mé moire l’empreinte numérique. On peut imaginer plusieurs scénarii où l’échange d’un programme par un autre peut s’avérer très dommageable.
Les mots de passe
Il est dangereux de stocker des mots de passe dans des serveurs. Si jamais un pirate accède au fichier des mots de passe, il pourra faire énormément de dégâts, y compris sur d’autres ordinateurs où les mêmes mots de passe sont utilisés. Un moyen simple de corriger cette faille est de stocker les empreintes des mots de passe. Ainsi, lorsqu’un utilisateur rentre son mot de passe, on le hache pour le comparer avec la valeur stockée. Même si une personne prend connaissance des empreintes, il ne pourra retrouver les mots de passe qu’en les essayant un par un. Cette façon de faire comporte malgré tout quelques problèmes de sécurité, comme l’existence de tables inverses qui révèlent le mot de passe en fonction de l’empreinte. Sur internet ce genre de tables fleurissent, par exemple pour la célèbre fonction de hachage md. Elles donnent ainsi tous les empreintes de mots du dictionnaire, à un ou deux caractères près. Un moyen d’éviter cette attaque est de bien choisir son mot de passe, et là encore on peut utiliser une fonction de hachage. Le mieux est d’utiliser une fonction de hachage privée,ce qui peut s’obtenir assez facilement avec une fonction de hachage publique. On lui demande l’empreinte d’un mot ou d’une phrase simple, et on se sert de l’empreinte, ou d’une partie de l’empreinte, comme mot de passe. L’inconvénient de cette méthode est qu’elle nécessite d’avoir toujours sa fonction de hachage privée avec soi, ou bien de retenir un mot de passe très bizarre.
Les schémas à divulgation nulle de connaissance
Une preuve à divulgation nulle de connaissance (Zero-knowledge Proof) est un concept utilisé en cryptologie dans le cadre de l’authentification et de l’identification. Cette expression désigne un protocole sécurisé dans lequel une entité nommée « fournisseur de preuve », prouve mathématiquement à une autre entité, le « vérificateur », qu’une proposition est vraie sans toutefois révéler une autre information que la véracité de la proposition. En pratique, ces schémas se présentent souvent sous la forme d’un protocole de type « stimulation/réponse » (challenge/response). Le vérificateur et le fournisseur de preuve s’échangent des informations et le vérificateur accepte ou rejette la preuve. Les premiers schémas Zero-knowlegde ont été basés sur le problème de la factorisation (voir par exemple Fischer-Micali-Rackoff en 1984, ou Fiat-Shamir en 1986), ou encore sur le problème d’isomorphisme de graphes. Puis, en 1991, O. Goldreich, S. Micali et A. Widgerson ont montré que tout problème NPcomplet admet une preuve Zero-Knowledge( [17]). Cependant le problème de la factorisation n’est pas supposé NP-complet (puisqu’il est dans NP et dans Co NP) et on a un algorithme sous-exponentiel (NFS par exemple) et même il existe un algorithme polynômial avec des ordinateurs quantiques (algorithme de Shor). De plus, la construction générale d’un algorithme Zero-Knowledge à partir de tout problème NP-complet n’est pas très efficace (cf [17]). C’est pourquoi, différents schémas Zero Knowledge ont été construits à partir de problèmes NP-complets bien choisis et basés sur des problèmes combinatoires supposés de difficulté exponentielle, PKP d’ Adi Shamir [59], PP de David Pointcheval [50] ou CLE ou SD [61] de Jacques Stern par exemple.
|
Table des matières
I Clé privée
1 Cryptanalyses de schémas de Feistel
1.0.1 Schémas avec attaques « 2-points »
1.0.2 Schémas avec attaques deux points et attaques rectangles
2 Théorie du miroir
2.1 Introduction
2.2 Notations, premier exemple
2.3 Les résultats obtenus dans la théorie du miroir
2.3.1 Définitions
2.3.2 Le Théorème Pi ⊕ Pj
2.3.3 Trois exemples de valeurs remarquables pour H
2.3.4 Généralisations
2.4 Théorème Pi ⊕ Pj : Exemples d’applications aux preuves de sécurité en cryptographie
2.5 Conjectures
2.5.1 Conjectures relatives à la somme de deux bijections
2.5.2 Conjectures relatives au théorème Pi ⊕Pj lorsque ξmax =2 et q =M
2.6 Somme de deux bijections
2.6.1 Programmation
2.6.2 Généralisation
2.6.3 Détails des résultats pour les groupes commutatifs
2.7 Algorithme de calcul de valeurs de h et h
2.7.1 Rappel du problème et notations
2.7.2 Choix des λ
2.7.3 Dénombrement des (Pi)
2.7.4 Résultats
II Hachage
3 Les fonctions de hachage
3.1 Introduction
3.1.1 Qu’est-ce qu’une fonction de hachage ?
3.1.2 À quoi ça sert ?
3.2 Définitions
3.3 Paradoxe des anniversaires
3.4 Construction de fonctions de hachage par le procédé de MerkleDamgård
3.5 Une histoire sanglante
4 Un sha-3 candidat : CRUNCH
4.0.1 La fonction de hachage construite pour la compétition du NIST : CRUNCH
4.0.2 Caractéristiques de CRUNCH
4.0.3 Résistance aux attaques
III Authentification à clé publique
5 Généralités sur le Zero-Knowledge
5.1 Définitions utiles
5.1.1 Problèmes de la classe P, NP et NP C
5.1.2 Fonctions à sens unique, prédicats sûr
5.1.3 Les schémas de mise en gage
5.2 Les schémas à divulgation nulle de connaissance
5.2.1 Introduction
5.2.2 Un exemple : le problème des 3 couleurs
5.2.3 Notations – Définitions
6 ZK avec un Rubik’s cube
6.1 Notations et définitions
6.1.1 Notations mathématiques standards et définitions
6.1.2 Représentation mathématique du Rubik’s cube
6.1.3 Le groupe de repositionnement
6.2 Différents problèmes de factorisation
6.3 Protocole à partir du Rubik’s cube 3 × 3 × 3
6.3.1 Introduction
6.3.2 Dissimuler le secret
6.3.3 Le protocole Zero-Knowledge
6.3.4 Preuves du protocole
6.3.5 Choix du nombre de tours pour le Rubik’s cube 3 × 3 × 3
6.4 Rubik’s cube 5 × 5 × 5
6.4.1 Représentation mathématiques
6.4.2 Dissimuler le secret
6.4.3 Protocole Zero knowledge
6.4.4 Choix de d et du nombre de tours pour le cube 5 × 5 × 5. 97
6.5 Les connections entre les problèmes liés au Rubik’s cube et les problèmes P-space complets et NP Complets
6.6 Un nouveau puzzle appelé S41
7 ZK avec des polynômes à plusieurs variables
7.1 Le schéma ZK(3)
7.2 Le schéma ZKg(3)
IV Conclusion
8 Contributions essentielles et perspectives
8.1 Contributions essentielles
8.2 Perspectives
V Annexes
A Schémas de Feistel hypercubique
A.1 Introduction
A.2 Hypercube Feistel Schemes, Notations
A.3 Paramètres
A.4 Application : la fonction de chiffrement HFS-162
B Recherche d’une solution des équations de Brent
B.1 Introduction
B.2 Description de l’algorithme
B.2.1 Notations
B.2.2 Les équations de Brent
B.2.3 Quelques espaces vectoriels particuliers
B.2.4 Étude des symétries
B.2.5 L’algorithme
B.2.6 Résultats obtenus et prolongements possibles
Télécharger le rapport complet
