Sécurité à chiffrés choisis sans redondance

OAEP

Avec l’introduction de la notion formelle du modèle de l’oracle aléatoire en 1993, Bellare et Rogaway ont proposé un schéma efficace de chiffrement [10] pour optimiser l’efficacité. Cet objectif entraîne deux problèmes de minimisation : l’un concerne l’écart entre la taille du texte chiffré et celle du texte clair (i.e. la bande passante) et l’autre, la taille du chiffré par rapport à celle de la primitive utilisée. Leur construction, appelée OAEP, résout le deuxième problème d’optimisation : avec une permutation à sens-unique à trappe de n bits vers n bits, la longueur du texte chiffré peut être optimale, i.e. n bits. Cette construction, illustrée dans la figure 4.1, permet de convertir une permutation à sens-unique à trappe en un schéma de chiffrement [10] décrit comme suit :

Description Notations et paramètres communs

Le chiffrement et le déchiffrement utilisent deux fonctions de hachage : G, H, modélisées par des oracles aléatoires dans les analyses de sécurité. Les paramètres de sécurité satisfont n = k +  : G : {0, 1}k → {0, 1} H : {0, 1} → {0, 1}k . Le chiffrement utilise une famille de permutations à sens-unique (ϕpk) (pour simplifier les notations, la deuxième indice pk signifie l’espace des clef publiques) dont les inverses sont respectivement les ψsk, où sk est la clef secrète (i.e. la trappe) associée à la clef publique pk. Le symbole «  » dénote la concaténation des chaînes de bits. De plus, on identifie {0, 1}k × {0, 1} à {0, 1}n.

Algorithme de chiffrement 

L’espace des textes clairs est M = {0, 1}−k1. Le chiffrement utilise un aléa r ∈ R = {0, 1}k et retourne un texte chiffré c dans F = {0, 1}n : à partir du texte clair m ∈ M, on calcule : s = (m0k1) ⊕ G(r) t = r ⊕ H(s). Le texte chiffré correspondant est alors c = ϕpk(s, t)

Algorithme de déchiffrement

A partir du texte chiffré c, on calcule d’abord st = ψsk(c), où s ∈ {0, 1}k et t ∈ {0, 1} , puis r = t ⊕ H(s) M = s ⊕ G(r). Si les k derniers bits de M sont tous 0, le déchiffrement retourne le message m qui est M sans les k derniers bits. Dans le cas contraire, le déchiffrement retourne « chiffré non valable », i.e. le texte chiffré ne correspond à aucun texte clair. L’instantiation du schéma avec la fonction RSA [107], appelée RSA-OAEP, devient la norme pour le chiffrement RSA (PKCS#1 version 2, IEEE P1363). Ce schéma est très efficace en termes de temps de calcul et de l’expansion de message, il est aussi compatible avec des applications plus traditionnelles du chiffrement RSA. Outre son efficacité, la raison déterminante de la popularité de f-OAEP fut la confiance en sa sécurité : sémantiquement sûr contre des attaques à chiffrés choisis adaptatives, sous réserve que la permutation utilisée soit à sens-unique à trappe—malgré aucune preuve complète. Cependant, en 2001, Shoup [114] a montré que pour ce schéma, la sécurité ne peut reposer sur l’hypothèse générale de l’existence de permutations à sens-unique à trappe. En effet, il a introduit une nouvelle technique, appelée la technique des « jeux successifs », pour prouver la sécurité. Appliquée au schéma OAEP, Shoup s’est heurté à un obstacle insurmontable. Il en a alors déduit un contre-exemple pour mettre en évidence le problème de sécurité d’OAEP. Cette technique sera étudiée en détail dans la section 4.

 Attaque de Shoup 

Tout d’abord, on rappelle les étapes pour casser un schéma au sens de la sécurité sémantique : l’attaquant choisit deux messages m0 et m1 ; reçoit un challenge c-le chiffré d’un de ces deux messages ; et finalement, devine à quel message c correspond. Dans le jeu d’attaque CCA2, on peut accéder à l’oracle de déchiffrement à n’importe quel moment. L’idée de Shoup est décrite comme suit :Quand on reçoit le challenge c, on vise à produire un autre texte chiffré c tel que les valeurs r et r dans la construction de ces deux chiffrés soient égales. Dans le cas où r = r , on obtient une relation entre les deux texte clairs : m ⊕ m = s ⊕s . Par conséquent, si on connaît s, s , grâce à une seule requête de déchiffrement sur le texte chiffré c , on obtient m , puis le m correspondant au challenge c. Le problème restant est de comprendre la façon avec laquelle un tel texte chiffré c est généré. Pour cela, Shoup a introduit la notion de permutation à sens-unique à trappe « XOR-malléable » : pour une telle permutation f0, on peut, avec probabilité non-négligeable, calculer f0(t ⊕ a) à partir de f0(t) et a. Supposons maintenant que l’on dispose d’une permutation f0 à sens-unique à trappe « XOR-malléable ». Définissons f par f(s||t) = s||f0(t). Il est facile de montrer que f est également une permutation à sens-unique à trappe. Alors, du challenge c = f(s||t) = s||f0(t), on extrait directement s. On choisit aléatoirement s et calcule a = H(s) ⊕ H(s ). À partir de a, f0(t), grâce à la propriété de permutation XOR-malléable, l’attaquant peut calculer f0(t  = t ⊕ H(s) ⊕ H(s )). Considérons la valeur r du texte chiffré c = s ||f0(t  ) : r = t  ⊕ H(s ) = t ⊕ H(s) ⊕ H(s ) ⊕ H(s ) = t ⊕ H(s) = r. Par conséquent, par le même raisonnement, une fois que c est demandé à l’oracle de déchiffrement, on peut calculer le texte clair m du m retourné par l’oracle de déchiffrement. Dans son article, Shoup a construit un modèle de calcul non standard où il existe une permutation à sens-unique à trappe XOR-malléable. Par conséquent, il est impossible de formuler une preuve de la propriété IND−CCA2 sûr de f-OAEP en utilisant la fonction f comme une boîte noire. f-OAEP ne pourrait être IND − CCA2 sûr qu’avec des propriétés spécifiques de la fonction f

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 

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 simulation