PICSI

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.