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 . 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   ou MerkleHellman  , la nature de la sécurité n’a pas été prouvée, faute d’une définition de la sécurité. En 1979, Rabin 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 = m2 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 textlair 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 7 Chapitre 1. Introduction à la sécurité prouvée (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.