PICSI

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.