PICSI

Les preuves de sécurité

Principe

Dans l'étude de la sécurité des algorithmes, nous avons présenté dans des attaques par distingueur qui comparent un système de chiffrement C à un système de chiffrement idéal C^* à l'aide d'une procédure de test (le distingueur) fournissant, pour un nombre q de requêtes au chiffrement C ou au chiffrement C^*, une réponse positive avec des probabilités différentes respectivement notées p et p^*. Si on obtient un avantage (|p−p^*|) suffisamment grand, cela signifie que l'on peut différencier C et C^* et donc ättaquer" l'algorithme C. Ce type d'études permet d'établir des bornes inférieures sur la probabilité de distinguer, avec un nombre de clairs et une complexité donnée, un algorithme cryptographique d'un chiffrement idéal. Luby et Rackoff dans [2] ont introduit une notion légèrement différente permettant de calculer des bornes supérieures sur la probabilité de distinguer, avec un nombre de clairs donné et des ressources de calcul illimitées, une construction cryptographique d'un chiffrement idéal : au lieu de distinguer des systèmes de chiffrement, ils ont utilisé la notion de distingueur sur des fonctions ou plus précisément ils ont comparé une fonction idéale à un schéma composé de fonctions idéales afin d'évaluer la qualité des schémas utilisés en chiffrement. Le principal exemple qu'ils ont développé est l'étude théorique d'un schéma de Feistel à trois étages. Ici, une fonction cryptographique dépendant de la clé peut être vue comme une fonction aléatoire associée avec une valeur de clé choisie aléatoirement. Ils prouvent la sécurité de ce schéma en comparant les distributions de probabilités entre la fonction de chiffrement engendrée par ce schéma et une fonction idéale. Ils démontrent ainsi une borne supérieure de sécurité sur l'avantage du distingueur obtenu. Après la publication de cet article, beaucoup d'autres études utilisant les principes de cette preuve de sécurité ont été menées. On peut citer ici la thèse de J. Patarin entièrement consacrée à ce sujet [3] qui replace la sécurité dans le modèle de Luby-Rackoff dans le cadre de la sécurité inconditionnelle définie par Shannon,... D'autres auteurs se sont également intéressés à d'autres schémas dérivés de celui de Feistel en prouvant leur sécurité dans le modèle de Luby-Rackoff ou à des modes opératoires d'algorithmes par blocs[1].

 

Références

[1]

M. Bellare, J. Kilian, and P. Rogaway. The security of cipher block chaining. In Advances in Cryptology -CRYPTO'94, Santa Barbara, Californie, États-Unis, pages 341-355. Lecture Notes in Computer Science 839, Springer-Verlag, 1994.

[2]

M. Luby and C. Rackoff. How to construct pseudorandom permutations from pseudorandom functions. SIAM Journal on Computing, 17, no. 2:373-386, 1988.

[3]

J. Patarin. Etudes des Générateurs de Permutations Pseudo-aléatoires Basés sur le Schéma du DES. PhD thesis, Université Paris VI, 1991.

La notion de distingueur

  Rappels Élémentaires sur les Fonctions Aléatoires

Si on considère un algorithme de chiffrement comme une fonction aléatoire, il est nécessaire de faire quelques rappels élémentaires sur les propriétés de ces fonctions aléatoires. On note F_n,m l'ensemble des fonctions de I_n dans I_m; on a # F_n,m=2^n.2m. On note P_n l'ensemble des permutations de I_n; on a # P_n=2ⁿ !. Définition 1 On définit une fonction aléatoire f^* comme parfaitement aléatoire si elle est prise aléatoirement dans F_n,m selon la loi uniforme, c'est à dire si elle est associée à une distribution de probabilité uniforme sur F_n,m. On définit de même une permutation c^* parfaitement aléatoire sur I_n comme un élément de P_n distribué uniformément sur celui-ci.

Si on considère une fonction cryptographique f_k liée à une clé aléatoire k de l'ensemble K, on peut voir la fonction f=(f_k)_{k ∈ K} comme une fonction aléatoire de F_n,m. L'étude de la sécurité des primitives cryptographiques repose essentiellement sur la recherche de collisions internes pour un q-uplet d'entrées ou de sorties. Définition 2 [Probabilité de transitions multiples liée à f] Soit f une fonction aléatoire de F_n,m, on définit Pr[x→ ^f y] comme la probabilité de transition associée à un q-uplet x=(x₁, …, x_q) d'entrées de I_n et à un q-uplet y=(y₁, …, y_q) de sorties de I_m :

Pr[x f →   y] = Pr[f(x1)=y1 ∧f(x2)=y2∧... ∧f(xq)=yq].

Précisons quelques propriétés élémentaires que nous utiliserons par la suite : Propriété 1 Soit f^* une fonction parfaitement aléatoire de F_n,m, x un q-uplet d'entrées distinctes de I_n et y un q-uplet de sorties (distinctes ou non) de I_m, on a alors : Pr[x→ ^f* y] = [1/(|I_m|^q)] = 2^−m.q.

Propriété 2 Soit c^* une permutation parfaitement aléatoire de P_n, x un q-uplet d'entrées distinctes de I_n et y un q-uplet de sorties distinctes de I_n, on a alors : Pr[x→ ^c* y] = (I_n − q)!/|I_n|! = [((2ⁿ−q)!)/((2ⁿ)!)].

Beaucoup de fonctions d'étage étant construites à l'aide de x-or, on utilise souvent la propriété suivante : Propriété 3 Soit c^* une permutation parfaitement aléatoire de P_n, x et x′ deux éléments distincts de I_n et δ une valeur donnée de I_n, on a alors : Pr[c^*(x) ⊕c^*(x′) = δ] ≤ [2/(2ⁿ)].

Preuve : Si δ = 0, Pr[c^*(x) ⊕c^*(x′) = δ] = 0 puisque x ≠ x′. Si δ ≠ 0, Pr[c^*(x) ⊕c^*(x′) = δ]=[(2ⁿ ·(2ⁿ−2)…1)/(2ⁿ!)]=[1/(2ⁿ−1)] ≤ [2/(2ⁿ)]. Donc, Pr[c^*(x) ⊕c^*(x′) = δ] ≤ [2/(2ⁿ)].

  Formalisation de la Notion de Distingueur

La deuxième notion essentielle à développer dans ce chapitre est celle de distingueur. C'est une machine de Turing probabiliste qui cherche à distinguer par un jeu de questions/réponses une fonction de chiffrement aléaoire f d'une fonction de chiffrement idéale f^* : Définition 3 Soit deux ensembles M₁ et M₂ et une fonction aléatoire f de M₁ vers M₂. Un distingueur pour la fonction f est une machine de Turing probabiliste A disposant d'un oracle O qui pour toute requête de M₁ envoie une réponse dans M₂. Après un certain nombre de calculs de l'oracle, le distingueur fournit la réponse "0" ou "1". On caractérise un distingueur par le nombre de requêtes q de l'oracle et le temps de calcul T. On mesure alors l'avantage de A à distinguer f de f^*, fonction de chiffrement aléatoire parfaite (i.e. tirée au sort selon la loi uniforme dans l'ensemble des fonctions de M₁ dans M₂), en calculant Adv_A(f,f^*) = |p − p^*| où p (respectivement p^*) représente la probabilité que A réponde 1 lorsque la fonction O = f est implémentée (respectivement O = f^*).

On peut également utiliser les distingueurs dans le cas de permutations aléatoires, on prend alors en compte les probabilités liées à ces permutations. Il existe deux types de distingueurs : les distingueurs dits "non-adaptatifs" qui préparent à l'avance toutes les requêtes et les distingueurs dits ädaptatifs" qui adaptent les requêtes en fonction des réponses précédentes, cette dernière notion étant bien évidemment plus forte. Étant donné une classe Cl de distingueurs, on définit le meilleur avantage sur cette classe :

AdvCl(f,f*) = max A ∈ Cl  AdvA(f,f*).

On définit alors trois classes particulières de distingueurs : Définition 4 [Cas d'un distingueur non-adaptatif] Soit un entier q. On note Cl_na^q la classe des distingueurs non adaptatifs limités à q textes clairs choisis. Pour construire une attaque faisant appel à cette classe de distingueurs, on choisit q textes clairs que l'on soumet à l'oracle et on obtient la réponse 0 ou 1.

Définition 5 [Cas d'un distingueur adaptatif] Soit un entier q. On note Cl_a^q la classe des distingueurs adaptatifs limités à q textes clairs choisis.

Définition 6 [Cas d'un distingueur super-pseudo-aléatoire] Soit q un entier. On note Cl_s^q la classe des distingueurs adaptatifs limités à q textes clairs ou chiffrés choisis. Pour attaquer un chiffrement C avec cette classe de distingueur, on peut utiliser soit le chiffrement C, soit son inverse C⁻¹.

Notons que l'utilisation d'un distingueur super-pseudo-aléatoire n'a de sens que dans le cas de l'étude de permutations.

  Distingueurs et Probabilités de Transitions d'une Fonction Aléatoire

Il est possible d'établir un lien entre Pr[x→ ^f y] et la notion de distingueur comme l'a le premier démontré J. Patarin dans [1]. Le meilleur avantage Adv_A(f,f^*) pour tout distingueur A à q requêtes de distinguer f de f^* est entièrement déterminé par Pr[x → ^f y], comme démontré dans [] : Théorème 1 [1] Soit f une fonction aléatoire de F_n,m et f^* une fonction aléatoire parfaite de F_n,m. Soit q un entier. On note X l'ensemble des x=(x₁,…,x_q) q-uplets de valeurs de I_n deux à deux distinctes. Si il existe un sous ensemble Y de I_m^q et deux nombres réels positifs ε₁ et ε₂ tel que :

1°) |Y| ≥ (1−ε₁)·|I_m|^q (i)

2°) ∀x ∈ X,    ∀y ∈ Y,   Pr[x → ^f y] ≥ (1−ε₂)·[1/(|I_m|^q)] (ii)

alors pour tout distingueur A adaptatif utilisant q requêtes, on a

AdvA(f, f*) ≤ ε1 + ε2

Preuve : On se limite dans cette démonstration au cas d'un distingueur adaptatif A, déterminé par un aléa ω, faisant appel à q requêtes supposées distinctes deux à deux. Les calculs possibles de A peuvent être partitionnés selon la valeur de l'aléa ω et de la réponse y=(y₁, …, y_q). En effet, si on note x=(x₁, …, x_q) le q-uplet d'entrées, la i-ème requête x_i est entièrement déterminée par la valeur de ω et par y₁, …, y_i−1. La réponse du distingueur A ne dépend donc que du couple (ω, y). On note A l'ensemble de tous les couples (ω, y) pour lesquels la réponse du distingueur est 1. On a :

AdvA(f, f*) = |p−p*| avec p = ∑ (ω, y) ∈ A  Pr[ω](Pr[x(ω,y) f →   y]

et p* = ∑ (ω, y) ∈ A  Pr[x(ω,y) f* →   y])

On obtient ces égalités en partionnant les valeurs de ω et f acceptées par A selon la valeur de la liste y de réponses qu'elles déterminent. On utilise alors la condition (ii) du théorème :
∀x ∈ X,   ∀y ∈ Y,   Pr[x → ^f y] ≥ (1− ε₂)Pr[x → ^f* y] sur l'espace Y pour obtenir :

p* − p ≤ ∑ (ω, y) ∈ A,  y ∈ Y  Pr[ω] ε2 Pr[x(ω, y) f* →   y] + ∑ (ω, y) ∈ A,  y ∉ Y  Pr[ω] Pr[x(ω, y) f* →   y]

On utilise alors la condition (i) pour borner la seconde partie du terme de droite de notre inégalité.
On réécrit la condition (i) de la manière suivante : ε₁ ≥ 1 − |Y| Pr[x(ω, y)→ ^f* y] soit ε₁ ≥ |[(Y)]|Pr[x(ω, y) → ^f*y]. L'inégalité devient donc :

p* − p ≤ ∑ (ω, y) ∈ A,   y ∈ Y  Pr[ω] ε2 Pr[x(ω, y) f* →   y] + ε1

De plus, on a :

∑ (ω, y) ∈ A,  y ∈ Y  Pr[ω] ε2 Pr[x(ω, y) f* →   y] ≤ ε2

car

∑ (ω, y) ∈ A,  y ∈ Y  Pr[ω] Pr[x(ω, y) f* →   y] ≤ |Im|q |Im|q

En considérant l'inverse de ce distingueur, à savoir celui dont la réponse est 0, on démontre la même inégalité pour p−p^*. On a donc bien :

AdvA(f, f*) ≤ ε1 + ε2

                                                                                                               ^[¯] L'utilisation de distingueurs permet donc l'étude théorique des fonctions de chiffrement, plus précisément des schémas de chiffrement construits à partir de fonctions d'étage idéales, en comparant leur distribution de probabilités de transition à celle d'une fonction aléatoire parfaite.

 

Références

[1]

J. Patarin. Etudes des Générateurs de Permutations Pseudo-aléatoires Basés sur le Schéma du DES. PhD thesis, Université Paris VI, 1991.

Un exemple de preuve de sécurité sur un schéma de Feistel

Nous présentons ici l'étude de la sécurité d'un schéma de Feistel à 3 étages, d'abord démontré par Luby et Rackoff en 1988 [] puis par J. Patarin en 1991 [], et enfin par U. Maurer en 1992. La démonstration présentée s'inspire de celle de [] qui utilise le théorème précédent.

Théorème 1 Soient F₁^*, F₂^*, F₃^* trois fonctions aléatoires parfaites indépendantes définies de 2^[m/2] dans lui-même et soit f^* une fonction aléatoire parfaite de 2^m dans 2^m. On note f=Ψ³(F₁^*, F₂^*, F₃^*) le schéma de Feistel à trois étages lié aux fonctions F₁^*, F₂^* et F₃^*. Alors, pour tout distingueur A adaptatif faisant appel à q requêtes, on a :

AdvA(f, f*) ≤ q2 ·2−[m/2].

Preuve :

Figure 1: Schéma de Feistel sur 3 étages
On note x=(x_i)_{i ∈ [1..q]}=(z_i⁰,z_i¹)_{i ∈ [1..q]} le q-uplet de requêtes et y=(y_i)_{i ∈ [1..q]}=(z_i³,z_i⁴)_{i ∈ [1..q]} le q-uplet de sorties correspondant. On note également z²=(z_i²)_{i ∈ [1..q]} le q-uplet d'éléments z_i² de I_[m/2] avec z_i²=z_i⁰ ⊕F₁^*(z_i¹). On note également z⁰=(z_i⁰)_{i ∈ [1..q]}, z¹=(z_i¹)_{i ∈ [1..q]} ,z³=(z_i³)_{i ∈ [1..q]} et z⁴=(z_i⁴)_{i ∈ [1..q]} les q-uplets correspondants aux différentes valeurs d'entrée et de sortie. On note Z l'ensemble des q-uplets de valeurs de z_i² deux à deux distinctes et comme dans le paragraphe précédent, X l'ensemble des x=(x₁,…,x_q) q-uplets de valeurs de I_m deux à deux distinctes.
On note Y l'ensemble défini par :

Y = { (y1, …, yq) ; ∀i < j,   zi3 ≠ zj3 }

Y correspond donc à l'ensemble des q-uplets de sortie dont les valeurs de la partie droite sont deux à deux distinctes. Le cardinal de cet ensemble est tel que :

|Y| ≥   1 − q(q−1) 2 ·2−[m/2]   2mq

On peut donc poser :

ε1 = q(q−1) 2 ·2−[m/2]

pour rester dans le cadre du théorème 11.
À présent, pour tout q-uplet x de l'ensemble X et pour tout q-uplet y de l'ensemble Y, on cherche à établir une borne inférieure pour la probabilité Pr[x→ ^f y] :

Pr[x f →   y] = ∑ z2 ∈ I[m/2] ,z3 ∈ I[m/2]  Pr[ (z2=z0⊕F1*(z1)) ∧(z3 = z1 ⊕F2*(z2))     ∧(z4 = z2 ⊕F3*(z3))]     ≥ ∑ z2 ∈ Z, z3 ∈ Y  Pr[(z3 = z1 ⊕F2*(z2)) ∧(z4 = z2 ⊕F3*(z3))]     ·Pr[(z2=z0 ⊕F1*(z1))]       (1)

On cherche alors à estimer l'inégalité (1).
Pour cela, pour tout q-uplet z² dans Z et pour tout q-uplet z³ de Y, on évalue tout d'abord Pr[(z³ = z¹ ⊕F₂^*(z²)) ∧(z⁴ = z² ⊕F₃^*(z³))] = Pr[(z¹ ⊕z³ = F₂^*(z²))] ·Pr[(z² ⊕z⁴ = F₃^*(z³))]. Comme z² appartient à Z et comme z³ appartient à Y, alors

Pr[(z3 = z1⊕F2*(z2)) ∧(z4 = z2 ⊕F3*(z3))] = (2−[m/2] )q ·( 2−[m/2] )q = 2−mq

De plus, comme les z² appartiennent à Z, on a :

Pr[(z2=zi0 ⊕F1*(zi1))] ≥ 1 − q(q−1) 2 ·2−[m/2]

On obtient donc

Pr[x f →   y] ≥ 2−mq ·   1 − q(q−1) 2 ·2−[m/2]  

On pose alors :

ε2 = q(q−1) 2 ·2−[m/2].

Il ne reste alors plus qu'à appliquer le théorème 11 sur l'ensemble Y, on obtient donc :

AdvA(f, f*) ≤ ε1 + ε2     ≤ q(q−1) 2[m/2]     ≤   q2 2 [m/2]

                                                                                                               ^[¯]

 

Références

[1]

M. Luby and C. Rackoff. How to construct pseudorandom permutations from pseudorandom functions. SIAM Journal on Computing, 17, no. 2:373-386, 1988.

[2]

J. Patarin. Etudes des Générateurs de Permutations Pseudo-aléatoires Basés sur le Schéma du DES. PhD thesis, Université Paris VI, 1991.

La théorie de la décorrélation

En 1998, S. Vaudenay a tenté d'unifier les différents modèles de sécurité à l'intérieur d'une théorie dite de la décorrélation (voir par exemple [2]). Elle généralise la notion de fonction universelle définie par Carter et Wegman dans [1]. Son but premier est de tenter d'unifier les différents résultats de cryptologie tant dans la résistance à des classes d'attaques que dans les différents modèles de preuves de sécurité à l'aide d'une théorie qui se veut plus globale.

Références

[1]

L. Carter and M. Wegman. New hash functions and their use in authentification and set equality. Journal of Computer and System Sciences, 22:265-279, 1981.

[2]

S. Vaudenay. Adaptative-attack norm for decorrelation and super-pseudorandomness. Technical Report LIENS-99-2, École Normale Supérieure, téléchargeable à ftp://ftp.ens.fr/pub/reports/liens/liens-99-2.A4.ps.Z, 1999.