Conception, preuves et analyse de fonctions de hachage cryptographiques

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, 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 (le MAC 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 à clé secrète repose principalement sur l’emploi de trois types d’algorithmes de base, ou primitives.

Les algorithmes de chiffrement par blocs. Un algorithme de chiffrement par blocs est une transformation inversible d’un bloc de taille fixe n paramétrée par une clé de taille k. En étant utilisé selon un mode opératoire, ce type de primitives permet notamment d’assurer des fonctionnalités de chiffrement symétrique ou de calcul de MACs. L’algorithme AES, conçu par Daemen et Rijmen [DR98, NIS01], est actuellement la primitive la plus utilisée pour les applications de chiffrement symétrique. Cet algorithme a remplacé l’ancienne norme DES en 2000.

Les algorithmes de chiffrement à flot. Ces algorithmes génèrent une suite chiffrante de longueur variable à partir d’une clé de k bits et d’une valeur d’initialisation publique. La suite chiffrante est ensuite combinée au message à chiffrer par une opération de OU EXCLUSIF. Les algorithmes de ce type présentent l’avantage d’offrir de très bons débits, mais malheureusement ils présentent souvent des failles de sécurité. C’est le cas notamment des algorithmes A5/1 et DSC, qui étaient respectivement utilisés pour le chiffrement de communications GSM et des communications par téléphone sans fil. Plus récemment, la compétition eSTREAM a permis la définition d’algorithmes de chiffrement à flot plus robustes.

Lire sur cLicours.com :  Lexique et dictionnaire de termes anglais français

Sécurité. En cryptographie, la sécurité des mécanismes utilisés n’est pas inconditionnelle, à de très rares exception près. Par exemple, en cryptographie à clé secrète, la taille de la clé étant fixe, il est toujours théoriquement envisageable pour un attaquant de tester toutes les valeurs possibles de la clé, jusqu’à identifier la bonne. Cette attaque est appelée recherche exhaustive. Les tailles de clés doivent donc être choisies de manière à éviter que cette attaque puisse être réalisée dans la pratique, c’est-à-dire en un temps de calcul réaliste.

Selon les primitives utilisées, d’autres attaques peuvent s’avérer plus performantes. La confiance dans les primitives de la cryptographie à clé secrète repose sur leur résistance aux tentatives de cryptanalyse à travers le temps .

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 Conclusion Générale

Cours gratuitTélécharger le document complet

Télécharger aussi :

Laisser un commentaire

Votre adresse e-mail ne sera pas publiée.