Sécurité et efficacité des schémas cryptographiques

Un des plus grands soucis des cryptographes est le classement des schémas cryptographiques selon leur niveau de sécurité face aux attaquants. Ce problème a été étudié en profondeur, en particulier à partir de la naissance de la cryptographie à clef publique.

La cryptographie à clef publique introduite par Diffie-Hellman [41] permet un chiffrement à partir de la clef publique du destinataire. Seul ce dernier, muni d’une clef secrète associée à sa clef publique, peut déchiffrer le message. La cryptographie à clef publique est parfois appelée « cryptographie asymétrique » (le terme « asymétrique » vient de la différence entre la clef secrète et la clef publique) et comprend plusieurs domaines importants tels que le chiffrement à clef publique, la signature, l’échange de clef… Une des questions qui se posent suite à l’apparition de ce courant de recherche est de savoir si la cryptographie asymétrique rend obsolète la cryptographie conventionnelle (la cryptographie symétrique). La réponse est non ! Au contraire, elle stimule le développement de la cryptographie symétrique. En effet, n’exigeant pas de conversation au préalable pour convenir d’une clef commune, le chiffrement asymétrique dispose d’un avantage crucial. Cependant, il est très lent par rapport au chiffrement symétrique et ne sert donc pas en pratique au chiffrement de données. En réalité, la transmission de données est généralement assurée par une technique hybride qui utilise à la fois un chiffrement asymétrique et un chiffrement symétrique : par la technique « asymétrique », les parties s’échangent une clef «courte » qui servira ensuite au chiffrement des données de manière symétrique. Dans cette première partie sur « la sécurité prouvée », nous considérons des notions de sécurité aussi bien pour le chiffrement asymétrique que pour le chiffrement symétrique. Avant de présenter nos travaux, nous reviendrons sur la genèse des notions de sécurité et quelques résultats importants les concernant.

Notions de sécurité pour le chiffrement asymétrique

Sécurité parfaite et sécurité au sens de la complexité

La première étape dans l’évaluation de la sécurité est, bien évidemment, la compréhension de la notion de « sécurité ». À ce jour, on en connaît deux définitions majeures. La première, au sens de la théorie de l’information, a été initialement évoquée par Shannon [113]. Elle concerne l’« information » sur le texte clair « contenue » dans le texte chiffré : un schéma de chiffrement est parfaitement sûr si le texte chiffré ne contient aucune information au sujet du texte clair correspondant. Dans le cadre d’un schéma de chiffrement symétrique, il a été démontré que la sécurité parfaite n’est atteinte que si la clef utilisée est aussi longue que le message. Cette condition est une sérieuse limite en pratique. La deuxième approche, au sens de la théorie de la complexité, est actuellement utilisée dans l’analyse des schémas de chiffrement. Elle ne s’intéresse pas au contenu du texte chiffré mais met l’accent sur la « difficulté » d’extraire de l’information sur le texte clair à partir du texte chiffré. Cette difficulté est considérée au sens de la complexité et elle est souvent comparée à la difficulté d’un problème bien défini : la factorisation, par exemple. Remarquons que la notion de « sécurité parfaite » n’est pas applicable au chiffrement asymétrique car le texte chiffré contient toujours de l’information sur le texte clair. En effet, tout attaquant de puissance illimitée peut retrouver le texte clair à partir du texte chiffré grâce à une recherche exhaustive dans l’espace des textes clairs et éventuellement, dans un espace d’aléas (dans le cas d’un chiffrement probabiliste). Dans ce qui suit, nous présentons les différentes notions de sécurité d’un schéma de chiffrement qui sont caractérisées par deux éléments : la difficulté d’extraire de l’information et la puissance dont un attaquant dispose pour casser le schéma .

Réduction en terme de complexité

Dans les premiers schémas de chiffrement à clef publique comme RSA [107] ou MerkleHellman [81], la nature de la sécurité n’a pas été prouvée, faute d’une définition de la sécurité. En 1979, Rabin [103] a introduit un schéma où la capacité d’un attaquant d’extraire le message complet à partir d’un texte chiffré est calculatoirement équivalente à la factorisation. Le schéma de chiffrement de Rabin est décrit comme suit : chaque utilisateur choisit deux nombres premiers de même taille p, q (servant de clef secrète) et publie la clef publique n = pq. Le chiffrement d’un message m est c = m² mod n. Le receveur, grâce à la connaissance de p, q, peut facilement calculer les quatre racines carrées du chiffrement c et en choisir le message approprié (une façon pratique de conduire à un bon choix est de mettre de la redondance dans le message initial). La sécurité considérée pour ce schéma est dite à sens-unique (dénotée OW, par one-way en anglais). Un schéma est « à sens unique » si, à partir d’un challenge chiffré, l’attaquant ne peut retrouver le texte clair correspondant.

Pour prouver la sécurité, on effectue une réduction d’un problème algorithmique à un problème de sécurité. Dans ce schéma, les deux problèmes sont respectivement une solution de la factorisation et l’extraction du message complet à partir d’un texte chiffré. En entrée, une instance n du problème de factorisation est donnée (n est la multiplication de deux premiers). Le but est de résoudre le problème de factorisation pour l’instance n en utilisant un attaquant contre le schéma. L’attaquant, étant capable d’extraire le message complet à partir d’un texte chiffré, joue le rôle de boîte noire, i.e. il reçoit une entrée et en retourne une sortie sans que l’on ne connaisse le mécanisme. Pour utiliser cet attaquant, il nous faut donc construire un simulateur de l’environnement d’attaque. Le simulateur créera un environnement parfaitement similaire (ou au moins indistinguable aux yeux de l’attaquant) à l’environnement réel de l’attaque.

Dans le cas du chiffrement de Rabin, un tel simulateur peut être construit de façon simple. En effet, il publie le nombre n comme la clef publique, puis, choisit un texte aléatoire m et le chiffre comme c = m2 mod n. Le simulateur donne la clef publique et le chiffré c à l’attaquant. Comme il s’agit d’un attaquant passif (qui ne demande pas d’information supplémentaire au système), le simulateur n’a pas à simuler les informations à échanger. La simulation est alors parfaite. L’attaquant retournera les quatre racines carrées correspondant au chiffré c. Le simulateur choisit m parmi ces quatre racines carrées tel que m ≠ ±m mod n. Alors, un des deux facteurs de n est le plus petit diviseur commun de n et m − m , d’où la factorisation de n.

Le schéma de Rabin est ainsi le premier système dans lequel une hypothèse algorithmique — la difficulté de la factorisation au sens de la complexité — a été réduite à un problème de sécurité — la capacité d’extraire le message complet à partir d’un texte chiffré. Une telle réduction s’appelle aujourd’hui « une preuve de sécurité ».

Fonctions à sens-unique

Dans ce premier exemple, on peut traduire l’« hypothèse algorithmique » de la difficulté de la factorisation en propriété « à sens-unique » de la fonction de multiplication de deux nombres premiers, i.e. elle est facile à calculer mais difficile à inverser. Cette notion de fonction à sens-unique est fondamentale en cryptographie. Dans les schémas asymétriques, elle est souvent couplée avec une propriété supplémentaire : l’inverse peut être facilement calculé grâce à quelques informations additionnelles, i.e. une trappe. Un des candidats pour les permutations à sens unique à trappe est la fonction RSA où l’inversion est conjecturée difficile mais devient facile avec la connaissance de la factorisation du module utilisé. Une permutation à sens-unique à trappe implique naturellement un schéma OW contre les attaquants passifs. Cependant, la recherche en cryptographie considère d’autres notions de sécurité plus subtiles que la propriété à sens-unique et d’autres types d’attaquants plus puissants qu’un attaquant passif. À ce stade, une question importante est la suivante : « la cryptographie peut-elle être fondée uniquement sur les hypothèses générales telles que l’existence de fonctions (permutations) à sens-unique ou de fonctions (permutations) à sens-unique à trappe ? ».

Sécurité sémantique et indistinguabilité

Dans les années 80, les chercheurs ont formellement défini les notions de sécurité pour les primitives cryptographiques (notamment pour la signature [60, 61] et pour le chiffrement [59]). Goldwasser et Micali [59] ont introduit la notion de la sécurité sémantique et ont proposé la construction d’un chiffrement probabiliste qui peut garantir la sécurité sémantique.

La notion de sécurité sémantique est une notion très forte, elle couvre l’exigence de ne pas pouvoir extraire une information, même partielle (ne serait-ce qu’un seul bit) sur le clair à partir du chiffré. Elle coïncide avec la notion de la sécurité parfaite limitée aux attaques polynomiales probabilistes. La sécurité sémantique est la propriété désirée pour tout schéma de chiffrement, mais, en réalité, on étudie souvent la notion de l’indistinguabilité (dénotée IND), plus simple à analyser. Cette notion a également été introduite dans [59]. Goldwasser et Micali [59] (l’indistinguabilité implique la sécurité sémantique) et Micali, Rackoff et Sloan [82] (la sécurité sémantique implique l’indistinguabilité) ont démontré qu’elle était équivalente à la notion de la sécurité sémantique. Avec l’indistinguabilité, l’attaquant ne peut pas trouver deux textes clairs m0 et m1 dont il pourrait distinguer les chiffrements : il reçoit un challenge c, chiffré de m0 ou m1 et ne doit pas pouvoir deviner à quel texte clair c correspond.

Cette condition implique immédiatement que le chiffrement soit probabiliste. De ce fait, les chiffrements déterministes de RSA et de Rabin n’atteignent pas la sécurité sémantique. Les premiers schémas qui ont atteint cette notion forte sont le schéma de Goldwasser et Micali [59] qui repose sur la difficulté du problème de la résiduosité quadratique, et le schéma de Yao [120], fondé sur l’hypothèse générale de l’existence de fonctions injectives à sens-unique à trappe. Cependant, ces deux schémas sont totalement inefficaces car leurs chiffrements sont « bit par bit », i.e. chaque bit est chiffré de manière indépendante, elles conduisent à des chiffrés très larges. Un schéma plus efficace (à chiffrés plus courts) ayant atteint la propriété d’indistinguabilité est celui de Blum et Goldwasser [16]. Il est fondé sur la difficulté du problème de la factorisation. L’idée dans ce schéma est d’utiliser le générateur Blum Blum-Shub [14] pour générer des bits aléatoires qui masqueront ensuite le clair.

Table des matières

Introduction
Chapitre 1 Introduction à la sécurité prouvée
1.1 Notions de sécurité pour le chiffrement asymétrique
1.1.1 Sécurité parfaite et sécurité au sens de la complexité
1.1.2 Réduction en terme de complexité
1.1.3 Fonctions à sens-unique
1.1.4 Sécurité sémantique et indistinguabilité
1.1.5 Attaques à chiffrés choisis
1.1.6 Non-malléabilité
1.2 Notions de sécurité pour le chiffrement symétrique
1.2.1 Fonctions pseudo-aléatoires
1.2.2 Permutations (super) pseudo-aléatoires
1.3 Discussion
1.3.1 Du point de vue théorique
1.3.2 Du point de vue pratique
1.4 Formalisation de quelques notions de base
Chapitre 2 Analyse des notions de sécurité pour le chiffrement asymétrique
2.1 Notions de sécurité pour le chiffrement asymétrique
2.1.1 Schéma de chiffrement asymétrique
2.1.2 Niveau de sécurité
2.1.3 Puissance de l’attaquant
2.2 Relations concrètes entre les notions de sécurité
2.2.1 Discussion sur la non-malléabilité
2.2.2 Relations entre les notions de sécurité revisitées
2.2.3 Nouveau modèle d’attaque : CCAO2
Chapitre 3 Analyse des notions de sécurité pour le chiffrement symétrique
3.1 Notions de sécurité pour le chiffrement symétrique
3.1.1 Schéma de chiffrement symétrique
3.1.2 Chiffrement par bloc
3.1.3 Sécurité sémantique
3.1.4 Indistinguabilité : « find-then-guess »
3.1.5 Permutations pseudo-aléatoires et super pseudo-aléatoires
3.1.6 Equivalences .
3.2 Résultats sur l’indistinguabilité des chiffrements par bloc
3.2.1 Attaquant « normal » .
3.2.2 Attaquant adaptatif
3.3 Indistinguabilité et pseudo-aléatoire
3.3.1 IND−P1−C0 est équivalente à la propriété de permutations pseudoaléatoires
3.3.2 IND−P2−C2 est « presque » équivalente à la propriété de permutations super pseudo-aléatoires
3.4 Application à DES
3.5 Conclusion
Construction de nouveaux schémas de chiffrement asymétrique
Chapitre 4 Introduction
4.1 OAEP
4.1.1 Description
4.1.2 Attaque de Shoup
4.1.3 Sécurité de RSA-OAEP
4.2 Technique des jeux successifs
4.2.1 Description
4.2.2 Exemple
Chapitre 5 Sécurité à chiffrés choisis sans redondance
5.1 Chiffrement sans redondance
5.2 FDP : permutation sur un domaine complet
5.2.1 Description
5.2.2 Résultat de sécurité
5.2.3 Idée de la preuve
5.3 OAEP 3 tours : un padding générique et efficace
5.3.1 Relâchement de la sécurité CCA
5.3.2 Primitive de base
5.3.3 Description d’OAEP 3 tours
5.4 Résultat de sécurité
5.4.1 Permutations à sens-unique
5.4.2 Idée de la preuve
5.4.3 Preuve
5.4.4 Cas particulier
5.5 Conclusion
Chapitre 6 Padding optimal pour le chiffrement et la signature
6.1 Introduction
6.1.1 Redondance et aléa
6.1.2 Padding universel
6.2 Modèle de sécurité pour la signature
6.2.1 Infalsifiabilité
6.2.2 Signature et chiffrement
6.2.3 Permutations sans griffe
6.3 Padding optimal fondé sur des permutations aléatoires
6.3.1 Padding
6.3.2 Analyse de sécurité
6.3.3 Proposition de taille pour les paramètres
6.4 OAEP 3-tours pour le chiffrement et la signature
6.4.1 Description
6.4.2 Résultat de sécurité
6.4.3 Proposition de taille pour les paramètres
Conclusion

Télécharger le rapport complet