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