Sécurité de RSA-OAEP

Heureusement, OAEP est presque immédiatement sauvé par Fujisaki et al. [54]. Ces auteurs ont montré que : premièrement, l’utilisation d’une permutation à « sens-unique partielle » 3 à trappe dans OAEP garantit son niveau fort de sécurité ; deuxièmement, la fonction RSA est une permutation à sens-unique partielle à trappe sous l’hypothèse bien connue qu’elle soit simplement une permutation à sens-unique à trappe. La sécurité de RSA-OAEP est définitivement prouvée. Cependant, la réduction dans leur preuve n’est pas aussi bonne qu’espérée. En effet, le coût de la réduction du problème d’inverser partiellement la fonction RSA au problème de sécurité de RSA-OAEP est quadratique en temps. De plus, le coût de la réduction du problème d’inverser complètement la fonction RSA au problème d’inverser partiellement la fonction RSA est aussi quadratique en temps.

 Technique des jeux successifs

 Au cours du temps, l’exigence du niveau de sécurité grandit. Les notions de sécurité deviennent ainsi de plus en plus complexes. Par conséquent, il est de plus en plus difficile de prouver la sécurité d’un schéma et de la vérifier. À titre d’exemple, la construction OAEP a été utilisée pendant une longue période sans être ni prouvée sûre ni attaquée. Dans ce contexte, Shoup a introduit la technique des « jeux successifs » pour une construction progressive des preuves de sécurité. Chaque étape est donc simple et facile à vérifier. 

Description 

La sécurité d’un schéma peut être évaluée au travers d’un « jeu » d’attaque entre un « attaquant » et un « challengeur ». L’attaquant et le challengeur sont des algorithmes probabilistes interactifs. Ils génèrent ainsi un espace probabiliste. Normalement, la définition de sécurité est liée à un « événement » particulier Ev : l’attaquant casse le schéma. La sécurité exige que, pour tout attaquant, la probabilité d’occurrence de cet événement soit « très proche » d’une valeur « cible », typiquement 0 ou 1 2 . La technique de jeux successifs consiste à changer petit à petit, pour chaque jeu, le comportement du challengeur. Le changement est effectué de telle manière que, entre deux jeux successifs, la différence de probabilité d’occurrence de l’événement Ev est « négligeable ». L’objectif est d’obtenir, dans le jeu final, une estimation de la probabilité d’occurrence de l’événement Ev. L’un des avantages de cette technique est que l’on peut facilement vérifier la preuve grâce à la simplicité des transitions des jeux successifs. Les transitions entre deux jeux successifs les plus utilisées sont au nombre de trois : – Transition 1 : Transition basée sur l’indistinguabilité. Un attaquant qui détecte le changement peut être transformé en un algorithme efficace, capable de distinguer deux distributions indistinguables (statistiquement ou calculatoirement). – Transition 2 : Transition basée sur un événements d’échec. Les i-ème et (i + 1)-ème jeux procèdent de façon identique sauf si un événement d’échec Ech se produit. Autrement dit : Pr[Evi ∧ ¬Ech] = Pr[Evi+1 ∧ ¬Ech]. On constate que l’écart entre les probabilités d’occurrence des événements Evi et Evi+1 dans les deux jeux successifs est, elle-même, « négligeable » si la probabilité d’occurrence de l’événement d’échec Ech est « négligeable ». Ceci résulte du lemme suivant (dont la preuve est évidente) : Lemme 39 Soient E, F et G des événements dans un espace de probabilités, alors Pr[E ∧ ¬G] = Pr[F ∧ ¬G] =⇒ |Pr[E] − Pr[F]| ≤ Pr[G]. – Transition 3 : Transition de ré-écriture. Il s’agit d’une étape intermédiaire, qui décrit les façons équivalentes de calculer certaines quantités dans les jeux successifs. Cette transition semble inutile mais elle permet de suivre la preuve plus facilement. L’état de l’art de cette technique est dans [115].

Exemple 

Dans [9], outre la formalisation de la notion de l’oracle aléatoire, Bellare et Rogaway ont proposé une construction générique de chiffrement IND − CCA2 à partir de n’importe quelle permutation à sens-unique à trappe. Cette construction fait appel à deux oracles aléatoires G et H, à valeurs respectivement dans {0, 1}k et {0, 1} . L’algorithme de génération des clés définit une permutation ϕpk dans l’espace E de taille n bits, calculable grâce à la clé publique pk. Son inverse ψsk ne peut être calculée que grâce à la clef privée sk (la trappe). Pour chiffrer un message m ∈ {0, 1}k, on choisit r R ← E, puis calcule : E(m; r) = ϕpk(r)  m ⊕ G(r)  H(m, r). Le déchiffrement d’un chiffré C = a  b  c se fait en deux étapes : tout d’abord, on retrouve r = ψsk(a), grâce à la trappe sk, puis m = b⊕G(r); ensuite, avant de retourner le message m, on vérifie la consistance du chiffré, i.e. si c = H(m, r). Ce schéma est prouvé IND−CCA2 sûr sous l’hypothèse que la famille des permutation (ϕpk) ϕpk est à sens-unique. Théorème 40 [102] Considérons un attaquant A à chiffrés choisis adaptatif. Supposons qu’après qD requêtes à l’oracle de déchiffrement et qG, qH requêtes aux oracles G et H, A a un avantage ε en temps t, alors on peut inverser ϕ avec succès ε/2 − qD/2 , en temps t + (qG + qH )Tϕ, où Tϕ désigne le temps pour une évaluation d’une fonction ϕpk. Une preuve utilisant la technique des jeux successifs est présentée dans [102]. On va l’étudier plus en détails pour apprécier l’efficacité de cette technique. Preuve. Considérons l’attaquant A = (A1, A2) contre ce schéma. Dans les deux étapes, A1 et A2 ont accès à l’oracle de déchiffrement. Jeu J0: Il s’agit d’une simulation parfaite du comportement du challengeur. On exécute l’algorithme de génération de clés qui retourne une permutation ϕpk et son inverse ψsk. On génère également x R ← E et y = ϕpk(x). Après avoir vu la clé publique (la description de la fonction ϕpk), A1 retourne deux messages m0 et m1. Après avoir reçu le chiffré C = a  b  c du message mδ, A2 retourne un bit δ . On dénote r l’unique élément tel que C = E(mδ, r). Avec probabilité (ε + 1)/2, δ = δ. On note cet événement S0, ainsi que Si dans les jeux Jeui ci-dessous : Pr[S0] = (1 + ε)/2. Pour la suite, on pourra supposer que toute question H(, ρ) est précédée de la question G(ρ), ainsi q G = qH + qG, où q G est le nombre total de requêtes à l’oracle G. Jeu J1: dans un premier temps, on remplace les oracles G et H par des simulations classiques : pour toute nouvelle question à l’un de ces oracles, on répond par une chaîne aléatoire dans l’espace correspondant, puis on stocke les questions-réponses respectivement dans les listes G-List et H-List. Il s’agit de simulations parfaites, Pr[S1] = Pr[S0]. Commentaire. Il s’agit d’une transition de type 1 : la simulation des oracles aléatoires est parfaite, les deux distributions sont parfaitement identiques. Jeu J2: dans ce jeu, on simule l’oracle de déchiffrement. À la question C = a  b  c, pour a = f(r), si r n’est pas dans G-List, on rejette le chiffré ; si de même (b ⊕ G(r), r) n’est à son tour pas dans H-List, on rejette le chiffré ; dans les autres cas, on continue à utiliser l’oracle de déchiffrement. Avec l’hypothèse ci-dessus que toute question H(, ρ) est précédée de la question G(ρ), on ne peut refuser un chiffré valide que si (b ⊕ G(r), r) n’a pas été demandé à H. Mais alors, H(b ⊕ G(r), r) retourne un élément parfaitement aléatoire, qui est égal à c avec probabilité 1/2k1. Ainsi, | Pr[S2] − Pr[S1] | ≤ qD/2k1. Commentaire. Il s’agit d’une transition de type 2 : l’événement d’échec Ech est « r n’est pas dans G-List ou (b ⊕ G(r), r) n’est pas dans H-List ». À l’exception de cet événement, les deux jeux sont identiques. Jeu J3: on poursuit la simulation de l’oracle de déchiffrement, sur C = a  b  c, pour a = f(r). On sait que r ∈ G-List et (b ⊕ G(r), r) ∈ H-List. On peut alors trouver ce r (en testant si ϕpk(r) = a sur toutes les questions à G, grâce à la propriété de permutation de ϕpk), puis déchiffrer correctement : Pr[S3] = Pr[S2]. Commentaire. Il s’agit d’une transition de type 3 : le jeu J3 est identique au jeu 2 mais m est calculé de manière différente. En effet, dans le jeu 2 , r = f −1(a), alors que dans le jeu J3, r sera extrait de G-List (le cas où r n’est pas dans la liste est déjà exclu). Jeu J4: dans ce jeu, on définit a = y = f(x), b = mδ ⊕ g+ et c = h+, où x, g+ et h+ sont aléatoires. De plus, à la question G(x), on répond g+, et à la question H(mδ, x) on répond h+. Il s’agit simplement de spécifier certaines valeurs de G et H, par des valeurs aléatoires, on ne modifie donc pas les distributions : Pr[S4] = Pr[S3]. Commentaire. Il s’agit évidemment d’une transition de type 3. Cette transition est importante dans la mesure où l’instance x est insérée dans la génération du challenge. Jeu J5: maintenant, on supprime les modifications locales de G et H. Les réponses aux question G(x) et H(mδ, x) sont indépendantes de x et mδ. La seule différence apparaît si l’événement « x a été demandé », nommé AskG (impliqué aussi par la requête à H), a lieu : | Pr[S5] −Pr[S4] | ≤ Pr[AskG]. Cependant, dans ce dernier jeu, δ est indépendant de la vue de l’attaquant, ainsi Pr[S5]=1/2. L’inégalité triangulaire nous donne : ε 2 = 1 + ε 2 − 1 2 = |Pr[S0] − Pr[S5] | ≤ qD 2k1 + Pr[AskG]. Commentaire. Il s’agit d’une transition de type 2. L’événement d’échec est « x a été demandé », i.e. AskG. Il nous reste à montrer que la probabilité d’occurrence de cet événement est « négligeable ». Cependant, l’événement AskG permet d’inverser ϕpk(x) en testant toutes les questions posées à G, d’où le résultat. Cette construction est très efficace par rapport aux autres schémas dans le modèle standard. Cependant, elle n’est pas optimale car la taille du texte chiffré est encore longue, i.e. n + k +  bits, par rapport à k bits du texte clair. Cette remarque est la motivation de OAEP.

Chiffrement sans redondance

 Dans le schéma OAEP ainsi que dans les variantes dont la primitive de base est une permutation à sens-unique à trappe (SAEP, SAEP+ [19] et OAEP+ [114]), le texte clair est toujours complété avec de la redondance avant d’être chiffré. D’autres paddings, applicables à des familles de fonctions plus générales, ont été proposés par Fujisaki et Okamoto [53, 52], Pointcheval [100] et Okamoto et Pointcheval [93]. La sécurité y est également garantie par de la redondance, mais dans ce cas, la redondance concerne le texte chiffré : avant de retourner le texte chiffré, on lui ajoute de la redondance. L’introduction de redondance dans le texte clair ou dans le texte chiffré a toujours le même objectif : un texte chiffré qui n’est pas proprement généré à partir d’un texte clair n’est valide qu’avec une probabilité négligeable. Cette propriété est formellement définie par la notion de plaintext-awareness dans [10, 7]. Elle entraîne le fait que l’oracle de déchiffrement ne donne aucune information aux attaquants. Ainsi, la redondance renforce la sécurité. Cependant, dans certains cas, elle est source d’attaques. En effet, le mécanisme de déchiffrement pour les textes chiffrés valides pourrait être différent de celui pour les textes chiffrés invalides : après un test de validité, l’algorithme de déchiffrement continue la phase de calcul si le texte chiffré vérifie la forme de redondance, sinon il retourne immédiatement la réponse que le texte chiffré est invalide. Par conséquent, des attaques peuvent être menées [13, 79]. A ce stade, le problème qui se pose est donc d’éviter ces redondances dans le chiffrement. Ceci éviterait d’éventuelles attaques et, surtout, améliorerait l’efficacité du schéma. 5.2 FDP : permutation sur un domaine complet Dans le même esprit que Full-Domain Hash signature [11, 34], nous proposons un chiffrement dans un nouveau modèle appelé permutation sur un domaine complet (FullDomain Permutation). Dans ce modèle, nous appliquons d’abord une permutation aléatoire sur le couple texte clair – chaîne aléatoire, le résultat est ensuite chiffré avec une permutation à sens-unique à trappe. Cette construction conduit au premier schéma de chiffrement IND − CCA2 sûr, à bande passante optimale et sans redondance, i.e. tout chiffré est valide.

Description

Le chiffrement FDP est doté d’une grande efficacité grâce à l’utilisation d’une permutation aléatoire P (qui est un oracle aléatoire bijectif ou un chiffrement idéal avec une clef particulière, 0 par exemple, voir aussi [108]). L’algorithme de génération de clef sélectionne une permutation à sens-unique à trappe ϕpk (son inverse ψsk, calculable à l’aide de la trappe sk) sur {0, 1}+k, et une permutation aléatoire P sur le même espace {0, 1} × {0, 1}k qui est identifié à {0, 1}+k. La clef publique définit la permutation ϕpk, alors que la clef secrète sk définit l’inverse ψsk de ϕpk. Ainsi, Epk(m; r) = ϕpk(P(m, r)) Dsk(c) = m, où (m, r) = P−1 (ψsk(c)). L’espace des textes clairs est {0, 1} , alors que celui des aléas r est {0, 1}k. Remarquons que P et P−1 sont des permutations publiques. 5.2.2 Résultat de sécurité Les avantages de ce schéma sont au nombre de trois : – Le premier, comme déjà mentionné, est la validité de tout texte chiffré : n’importe quel élément de l’espace d’arrivée de l’algorithme de chiffrement peut être atteint par cet algorithme. – Le deuxième découle du résultat de sécurité dans le théorème 41 ci-dessous : il atteint la sécurité IND − CCA2 sous la seule hypothèse de la difficulté d’inverser ϕ. – Le troisième vient de l’optimalité de la bande passante : pour un niveau de sécurité 2k, on n’a besoin que d’une chaîne aléatoire de k bits. Évidemment, cette remarque est applicable uniquement au cas général où  ≥ k (e.g., k = 80 et k +  = 1024).