PICSI

Sécurité prouvable contre les cryptanalyses différentielle et linéaire

  Comment passer d'une boîte S à un chiffrement

Dans leur article [4], K. Nyberg et L. Knudsen donnent une borne supérieure de sécurité prouvée pour un schéma de Feistel de trois étages et plus dans le cas où la fonction étage est une permutation et de quatre étages et plus dans le cas où la fonction étage est une fonction, les sous-clés étant supposées indépendantes et uniformément distribuées. Soit :

f : GF(2)m → GF(2)n, m ≥ n     E : GF(2)n → GF(2)m, une expansion affine     F : GF(2)n ×GF(2)m → GF(2)n     (X, ki) → f(E(X) ⊕ki)

où k_i appartenant à GF(2)^m désigne la sous-clé de l'étage i. On considère un chiffrement de type DES résultant d'un schéma de Feistel à r étages qui prend en entrée des blocs de taille 2n et applique la fonction F à la moitié du bloc courant. On définit alors p_max comme la meilleure probabilité d'une différentielle sur un tour :

pmax = maxβ maxαR ≠ 0DPF(α, β)

où α_R représente la partie droite de α. Théorème 1 Dans un chiffrement de type DES utilisant la fonction F comme fonction étage avec des clés k_i indépendantes et uniformément distribuées, la probabilité d'une différentielle sur s tours (s ≥ 4) est inférieure ou égale à 2p_max² :

∀α ≠ 0   , ∀β  , P(∆Xs = β|∆X0 = α) ≤ 2pmax2

où ∆X₀ représente la différence d'entrée et ∆X_s la différence à la sortie de l'étage s.

Théorème 2 Si f est une permutation dans un chiffrement de type DES et si les sous-clés sont indépendantes et uniformément distribuées, alors la probabilité d'une différentielle sur s tours (s ≥ 3) est inférieure ou égale à 2p_max².

Notons que pour le cas de la résistance à la cryptanalyse linéaire étudiée par K. Nyberg dans [3], on obtient les mêmes bornes en définissant

pmax = maxα maxβ ≠ 0LPF(α,β)

Cette borne a été améliorée à p_max² par K. Aoki et K. Ohta [1] dans le cas différentiel comme dans le cas linéaire avec des fonctions d'étage bijectives.

 

  MISTY : un exemple pratique de ces résultats

M. Matsui a conçu son chiffrement MISTY [2] pour qu'il résiste de façon efficace aux cryptanalyses différentielle et linéaire à l'aide de cette théorie. Rappelons tout d'abord que MISTY agit sur trois niveaux (voir figure ).
Figure 1: M'1 sur 5 étages, version modifiée de MISTY
Le premier est un schéma de Feistel classique dont la fonction étage est FO_i. Le deuxième représente la fonction FO_i et est un schéma de Feistel modifié sur trois étages faisant intervenir trois fois une fonction FI_ij. Le troisième niveau représente la fonction FI_ij sur trois étages d'un schéma de Feistel modifié séparant en deux blocs de taille n₁ et n₂ le bloc d'entrée et faisant intervenir deux boîtes S S₇ et S₉ et des opérations élémentaires de troncature et d'expansion à 0 (voir figure 1). M. Matsui prouve tout d'abord une borne supérieure pour chaque fonction FI_ij : si f₁, f₂ et f₃ sont les trois fonctions étages bijectives du schéma de Feistel modifié représentant une fonction FI_ij et si p_k=EDP^f_k (respectivement ELP^f_k) alors EDP^FI_ij (respectivement ELP^FI_ij) est plus petit que max{p₁p₂, p₂p₃,2^n₁−n₂p₁p₃}. De même, pour chaque fonction FO_i, si les trois fonctions FI_ij sont bijectives et si pour tout j valant 1, 2 ou 3 on a EDP^FI_ij ≤ p (respectivement ELP^FI_ij ≤ p) alors EDP^FO_i ≤ p² (respectivement ELP^FO_i ≤ p²). Les fonctions étage de FI sont ici les deux boîtes S S₇ et S₉, S₉ intervenant deux fois, et on a :

LPS7=DPS7=2−6 et LPS9=DPS9=2−8.

On obtient donc pour chaque fonction FI_ij une borne ELP^FI_ij=EDP^FI_ij ≤ 2⁻¹⁴. De même, pour chaque fonction FO_i, en appliquant le deuxième résultat aux trois fonctions FI_ij, on obtient : ELP^FO_i=EDP^FO_i ≤ 2⁻²⁸. Et donc sur trois étages d'un schéma de Feistel composé de trois fonctions FO_i, on obtient une borne supérieure pour les probabilités différentielle et linéaire égale à 2⁻⁵⁶, ce qui prémunit MISTY composé de 8 étages contre les attaques différentielle et linéaire. Il est cependant à noter que MISTY1 ne résiste pas sur un nombre réduit d'étages à une cryptanalyse d'ordre supérieur.

 

Références

[1]

K. Aoki and K. Ohta. Strict evaluation for the maximum average of differential probability and the maximum average of linear probability. IEICE Transactions on Fundamentals, E80-A:2-8, 1997.

[2]

M. Matsui. New block encryption algorithm misty. In Fast Software Encryption'97, Haifa, Israël, pages 54-68. Lectures Notes in Computer Science 1267, Springer-Verlag, 1997.

[3]

K. Nyberg. Linear approximation of block ciphers. In Advances in Cryptology -EUROCRYPT'94, Pérouse, Italie, pages 439-444. Lecture Notes in Computer Science 950, Springer-Verlag, 1994.

[4]

K. Nyberg and L.R. Knudsen. Provable security against differential attack. Journal of Cryptology, 8, no. 1:27-38, 1995.