Conception, preuves et analyse de fonctions de hachage cryptographiques

Introduction à la cryptologie

Un peu d’histoire

La cryptologie est un domaine de recherche scientifique qui tire ses origines des techniques mises en œuvre pour protéger la confidentialité des communications militaires. Pour rendre un message inintelligible pour l’ennemi, son émetteur lui applique une transformation appelée chiffrement. Lors de la réception du message, le destinataire applique l’opération inverse, appelée déchiffrement. On parle de décryptement lorsqu’un attaquant parvient à retrouver le message clair (c’est-à-dire le message avant l’opération de chiffrement) à partir du chiffré. De telles techniques ont vu le jour dès l’antiquité, comme par exemple la scytale utilisée par les Spartiates dès le cinquième siècle avant Jésus-Christ, ou le chiffrement de César. D’abord très rudimentaires, les mécanismes cryptologiques se sont progressivement complexifiés et répandus dans le domaine militaire. De ce fait, le caractère secret des mécanismes employés est devenu de plus en plus difficile à garantir. En 1883, Auguste Kerckhoffs énonce un principe fondateur de la cryptologie moderne : les mécanismes de chiffrement et de déchiffrement doivent pouvoir être rendus publics, la confidentialité des messages doit être garantie uniquement par le secret d’une clé. Lors des deux guerres mondiales, la cryptographie a été beaucoup utilisée et la capacité à décrypter les communications ennemies a joué un grand rôle dans l’issue de ces conflits. Dans la deuxième moitié du vingtième siècle, avec l’essor de l’informatique et des télécommunications, la cryptologie a trouvé des applications dans le domaine civil et est devenue un domaine de recherche académique à part entière. Elle permet de protéger des transactions bancaires, des communications téléphoniques, de stocker des données de manière sécurisée, ou encore d’authentifier les utilisateurs d’un système informatique. Si la signification étymologique de cryptologie est science du secret, les problématiques traitées par ce domaine vont aujourd’hui bien au-delà de la confidentialité des communications. Dans le domaine de la cryptologie, on distingue la cryptographie, qui correspond à la conception de mécanismes cryptologiques, de la cryptanalyse, qui correspond à l’analyse de leur sécurité. Cette branche contient en particulier les attaques contre les mécanismes cryptographiques. Une autre distinction s’opère entre cryptographie symétrique et cryptographie asymétrique, que nous allons maintenant expliciter.

La cryptographie symétrique

La cryptographie symétrique, aussi appelée cryptographie à clé secrète, regroupe des mécanismes reposant sur la connaissance d’une clé secrète par deux personnes ou entités. Il s’agit de la branche la plus ancienne de la cryptographie. En effet, les systèmes cryptographiques historiques mettent en œuvre une même clé pour les opérations de chiffrement et de déchiffrement. La cryptographie à clé secrète remplit différentes fonctionnalités, dont les suivantes.

Chiffrement symétrique. Le chiffrement symétrique permet de protéger la confidentialité d’une donnée en la chiffrant avec une clé K. Un mécanisme de déchiffrement utilisant la même clé K permet à quiconque la possède de retrouver la donnée à partir du chiffré.

Intégrité d’une donnée. Pour certaines applications, l’intégrité d’une donnée, c’est-à-dire le fait qu’elle n’ait pas été modifiée après sa création, est au moins aussi importante que sa confidentialité. Par exemple, lors d’une transaction bancaire, il est indispensable que la somme d’argent mise en jeu ne soit pas modifiée. Certains mécanismes de la cryptographie à clé secrète permettent de garantir cette propriété. Ces mécanismes consistent à adjoindre à la donnée M à protéger un code d’authentification de message ou MAC (pour Message Authentication Code), qui dépend de M et d’une clé secrète K. La connaissance de M et K permet la vérification du motif d’intégrité. La validité d’un MAC garantit à la fois l’intégrité du message (il n’a pas été modifié après le calcul du MAC) et une forme d’authenticité appelée authenticité de message (leMAC a été calculé par un détenteur de K).

Authentification d’une entité. Certains mécanismes permettant à un utilisateur d’un système d’information de s’authentifier reposent sur la connaissance commune d’une clé secrète K et sur l’emploi de primitives de la cryptographie symétrique.

La cryptographie asymétrique 

La cryptographie asymétrique repose sur une idée exposée par Diffie et Hellman en 1976 dans [DH76] : le chiffrement et le déchiffrement sont deux opérations fonctionnellement différentes. Il n’y a donc aucune nécessité pour que les clés servant au chiffrement et au déchiffrement soient les mêmes. Dès lors que l’on utilise deux clés différentes pour le chiffrement et pour le déchiffrement et que la clé de déchiffrement ne peut pas être déduite de la clé de chiffrement, cette dernière peut être publique. De ce fait, la cryptographie asymétrique est également appelée cryptographie à clé publique. La clé de déchiffrement (ou clé privée) n’est connue que du destinataire. Ce dernier est l’unique détenteur de la clé privée. Différentes fonctions de sécurité peuvent être obtenues en utilisant des outils asymétriques.

Échange de clés. L’application découverte par Diffie et Hellman dans leur article était un mécanisme d’échange de clé secrète. En effet, un des problèmes posés par la cryptographie symétrique réside dans l’établissement de clés partagées entre deux entités. Le protocole d’échange de clés de Diffie et Hellman est encore le plus utilisé aujourd’hui.

Chiffrement asymétrique et chiffrement hybride. La découverte d’outils mathématiques ouvrant la voie à des applications concrètes de l’idée de Diffie et Hellman est arrivée un peu plus tard. En 1978, Rivest, Shamir et Adleman ont inventé l’algorithme RSA [RSA78]. D’autres algorithmes ont suivi, comme celui d’ElGamal [Gam84]. Pour des raisons de débit, le chiffrement à clé publique n’est généralement pas utilisé pour chiffrer directement des données. On utilise plutôt de telles primitives pour chiffrer des clés symétriques tirées aléatoirement. Ces clés servent ensuite au chiffrement de données à l’aide d’un algorithme de chiffrement symétrique. On parle alors de chiffrement hybride.

Signature électronique. Comme la signature manuscrite, la signature électronique permet de lier un document à un signataire. Dans les deux cas, les signatures peuvent être vérifiées publiquement. Les schémas de signature électronique sont donc fondamentalement asymétriques : la clé privée du signataire intervient dans l’algorithme de signature, et la clé publique correspondante sert à la vérification. La primitive RSA peut également être utilisée pour des applications de signatures, notamment en utilisant le format RSA-PSS [RSA02]. D’autres normes telles que DSA [NIS09] ou sa variante utilisant des courbes elliptiques ECDSA, décrite dans le même document, sont aussi fréquemment rencontrées.

Sécurité. Les mécanismes de la cryptographie à clé publique utilisent des outils mathématiques utilisant des fonctions fondamentalement asymétriques. Ces fonctions sont faciles à calculer et considérées comme difficiles à inverser. Leur sécurité est liée à celle de problèmes mathématiques conjecturés difficiles. Citons par exemple la factorisation de grands entiers pour RSA, ou le calcul de logarithmes discrets dans des groupes multiplicatifs pour DSA, ElGamal ou encore l’échange de clés Diffie-Hellman. La résolution de tels problèmes permet de retrouver la clé privée à partir de la clé publique. Les meilleures algorithmes permettant de résoudre ces problèmes sont plus efficaces qu’une recherche exhaustive sur la clé privée. A tailles de clés égales, la sécurité potentiellement offerte par les algorithmes symétriques est donc meilleure que la sécurité des algorithmes asymétriques. Réciproquement, pour un niveau de sécurité équivalent, les clés asymétriques sont donc plus longues que les clés symétriques.

Table des matières

I Introduction Générale
1 Introduction
1.1 Introduction à la cryptologie
1.1.1 Un peu d’histoire
1.1.2 La cryptographie symétrique
1.1.3 La cryptographie asymétrique
1.2 Les fonctions de hachage en cryptographie
1.2.1 Définition et origines
1.2.2 Sécurité des fonctions de hachage cryptographiques
1.2.3 Utilisations en cryptographie
2 Extension de domaine
2.1 Autour de la construction de Merkle-Damgård
2.1.1 Algorithme de Merkle-Damgård
2.1.2 Extension de messages
2.1.3 Multicollisions
2.1.4 Recherche de secondes préimages
2.2 Algorithmes d’extension de domaine récents
2.2.1 La construction wide pipe
2.2.2 Fonctions éponges
2.2.3 Encodage sans préfixe
2.3 Arguments de sécurité
2.3.1 Conservation de propriétés de sécurité de la fonction de compression
2.3.2 Indifférenciabilité d’un oracle aléatoire
3 La famille MD-SHA
3.1 Constructions classiques de fonctions de compression
3.2 La famille MD-SHA
3.2.1 Les premières fonctions
3.2.2 SHA-1
3.2.3 La famille SHA-2
3.3 La cryptanalyse différentielle
3.3.1 Idée de la cryptanalyse différentielle
3.3.2 Application à SHA-1
3.3.3 Améliorations possibles
3.3.4 Conséquences sur la famille SHA
3.4 La compétition SHA-3
3.4.1 Déroulement de la compétition
3.4.2 Le deuxième tour
3.4.3 Les cinq finalistes
II Conception et preuves de sécurité
4 Description et analyse de Shabal
4.1 Description de la fonction
4.1.1 Conventions et notations
4.1.2 Algorithme d’extension de domaine
4.1.3 Permutation paramétrée P
4.2 Performances et implémentations
4.3 Principes de conception de Shabal
4.3.1 Principes de conception de l’algorithme d’extension de domaine
4.3.2 Principes de conception de P
4.4 Évaluation de la sécurité de P
4.4.1 Diffusion imparfaite par P−1
4.4.2 Distingueurs différentiels
4.4.3 Points fixes
4.4.4 Distingueurs rotationnels
4.5 Conclusion
5 Extension de domaine et indifférenciabilité d’un oracle aléatoire
5.1 Représentation générique d’algorithmes d’extension de domaine
5.2 Techniques de preuve d’indifférenciabilité
5.2.1 Le modèle d’indifférenciabilité
5.2.2 Élements de construction du simulateur
5.2.3 Preuves par séquence de jeux
5.2.4 Lemme de différence
5.2.5 Simulation d’une fonction aléatoire
5.2.6 Identification d’évènements d’échec
5.2.7 Simulation de F et détection d’évènements d’échec
5.3 Preuve d’indifférenciabilité lorsque F est une fonction
5.3.1 Borne sur l’avantage du distingueur
5.3.2 Esquisse de la séquence de jeux
5.3.3 Séquence de jeux
5.3.4 Majoration de l’avantage de l’attaquant
5.3.5 Évaluation de l’avantage de l’attaquant en fonction du nombre de requêtes
5.3.6 Application à Chop-MD
5.3.7 Borne d’indifférenciabilité lorsque l’encodage est sans préfixe
5.4 Preuve d’indifférenciabilité lorsque F est une permutation
5.4.1 Modélisation d’une permutation paramétrée
5.4.2 Description de la séquence de jeux
5.4.3 Majoration de l’avantage de l’attaquant
5.4.4 Évaluation de l’avantage de l’attaquant en fonction du nombre de requêtes
5.5 Borne d’indifférenciabilité avec des tours à blanc et un compteur
6 Le modèle d’indifférenciabilité généralisé
6.1 Preuves d’indifférenciabité et attaques par distingueur
6.2 Modélisation de primitives imparfaites
6.2.1 Adaptation immédiate de la preuve
6.2.2 Représentation algorithmique d’une fonction biaisée
6.3 Indifférenciabilité d’un oracle aléatoire public de la construction Chop-MD avec une fonction de compression biaisée
6.3.1 Principes de conception du simulateur
6.3.2 Description du simulateur
6.3.3 Esquisse de la preuve par séquence de jeux
6.3.4 Construction de la séquence de jeux
6.3.5 Majoration de l’avantage de l’attaquant
6.4 Indifférenciabilité forte de Chop-MD dans le cas biaisé
6.4.1 Insuffisance de la caractérisation du biais par ε et τ
6.4.2 Limitation sur le biais de F
6.4.3 Indifférenciabilité forte pour un biais limité
6.4.4 Preuve par séquence de jeux
6.4.5 Majoration de l’avantage de l’attaquant
6.4.6 Application
6.5 Majoration des probabilités d’échec des simulateurs
6.5.1 Probabilité d’occurrence de Echec[5]
6.5.2 Probabilité d’occurrence de Echece[6]
III Conclusion Générale

Télécharger le rapport complet