PICSI

Cette cryptanalyse, introduite par A. Corfdir et H. Gilbert pour cryptanalyser l'algorithme FEAL [2] et appliquée par M. Matsui au DES [5], est une attaque à texte clair connu qui consiste à chercher des approximations linéaires de la fonction d'étage f_ki, définie de {0,1}ⁿ dans lui-même. On cherche donc des relations de la forme :

a ·fki(X) = b ·X + c ·ki ou a ·fki(X) = b ·X + c ·ki + 1

vérifiées pour le plus grand nombre de valeurs de X possibles où · représente le produit scalaire modulo 2 et a, b, et c appartiennent à {0,1}ⁿ. k_i représente, comme dans le paragraphe précédent, la sous-clé de l'étage i. On peut donc voir la cryptanalyse linéaire comme une projection sur l'ensemble {0,1} de la relation liant les blocs d'entrée et de sortie de la fonction f_ki. On cherche alors des relations de ce type portant sur un nombre d'étages l. Notons X_i le chiffré du i-ème étage et p_i la probabilité linéaire de l'étage i définie par

pi(ai,bi) = 1 2 ±εi où εi = | #{Xi−1 | ai ·Xi = bi ·Xi−1 } − 2n−1 | 2n .

Une relation sur l étages est déduite en sommant les relations sur un étage. Pour cela, on cherche des suites de coefficients a_i et b_i dans lesquelles les coefficients des termes intermédiaires X_i s'éliminent par sommation. Pour calculer la probabilité linéaire p_{1 …l} sur l étages, il suffit comme dans le cas d'une caractéristique différentielle de multiplier les corrélations associées aux différentes relations et égales à 2 ·ε_i entre elles :

p(1 …l) = 1 2 ±ε(1 …l) avec ε(1 …l) =   l ∏ i=1  εi   ·2l−1

Le but est alors de rendre cette probabilité le plus éloignée possible de [1/2] pour obtenir le meilleur biais possible et donc le meilleur distingueur possible. On cherche donc une relation sur (r−1) étages L(X₀, X_r−1,[k₁, …, k_r−1]) de la forme :

L(X0, Xr−1, [k1, …, kr−1]) = a ·X0 + b ·Xr−1 = c ·[k1, …, kr−1]         (*)

ayant une probabilité de se produire p le plus éloignée possible de [1/2] et où [k₁, …, k_r−1] représente l'ensemble des sous-clés des r−1 étages.
À partir de cette relation qui représente un distingueur, on cherche à construire une attaque. Deux algorithmes ont été présentés par Matsui dans [5]. Le premier s'attache à dériver le coefficient c ·[k₁, …, k_r−1]. Sa probabilité de réussite est relativement élevée mais il ne permet d'attaquer que (r−1) étages. Nous nous intéresserons donc ici au deuxième algorithme décrit dans [5] qui représente un distingueur sur r étages et qui teste le biais de la relation (*) pour les différentes hypothèses sur les valeurs de la sous-clé du dernier étage k_r en utilisant uniquement la valeur absolue des déviations par rapport à la probabilité uniforme. Pour impliquer la sous-clé du dernier étage dans la relation (*), il suffit de considérer X_r−1 comme le déchiffré sur un étage de X_r. On obtient donc une relation du type :

a ·X0 + b ·f−1kr(Xr) = c ·[k1, …,kr−1]

On utilise alors l'algorithme suivant pour tester les hypothèses de clés :

Première Étape : Chiffrer N clairs pour obtenir une liste de (X0, Xr)

Deuxième Étape :

Pour chaque valeur kr(i) de kr faire

Ti reçoit le nombre de clairs tel que

a ·X0 + b ·f−1kr(i)(Xr) = 0

Tmax reçoit la valeur maximale des Ti et max le i correspondant

Tmin reçoit la valeur minimale des Ti et min le i correspondant

Si - Tmax−[N/2] - > - Tmin−[N/2] - alors

kr reçoit kr(max)

Si p > [1/2] alors c ·[k1, …, kr−1] = 0

Si p < [1/2] alors c ·[k1, …, kr−1] = 1

Si - Tmax−[N/2] - < - Tmin−[N/2] - alors

kr reçoit kr(min)

Si p > [1/2] alors c ·[k1, …, kr−1] = 1

Si p < [1/2] alors c ·[k1, …, kr−1] = 0

Il reste donc à évaluer la probabilité de réussite d'un tel algorithme. Pour cela, on utilise les lemmes suivants présentés dans [5] qui donnent une bonne approximation de ce taux : Soit N le nombre de clairs donné. Le taux de succès de l'algorithme ne dépend alors que du nombre de bits de clé impliqué dans l'expression b ·f⁻¹_kr(X_r) et de √N|p−[1/2]|. Soit q⁽ⁱ⁾ les probabilités de réussite de l'équation suivante pour chaque valeur k⁽ⁱ⁾ de k_r :

b ·f−1kr(X) = b ·f−1k(i)(X)

alors si les q⁽ⁱ⁾ sont indépendants, le taux de succès de l'algorithme est :

⌠ ⌡ ∞ x=−2√N|p−[1/2]|     ∏ k(i) ≠ kr  ⌠ ⌡ −x+4√N(p−[1/2])(1−q(i)) −x−4√N(p−[1/2])q(i)  1 √ 2 π e−y2/2 dy    1 √ 2 π e−x2/2 dx

Même si les q⁽ⁱ⁾ ne sont pas indépendants dans le cas qui nous intéresse, ce lemme donne une bonne approximation du taux de succès de l'algorithme. Pour plus de lisibilité et comme présenté dans [5], nous donnons le tableau suivant qui fait correspondre le nombre de texte clairs N et le taux de succès de l'algorithme :

N	2 |p−[1/2]|−2	4 |p−[1/2]|−2	8 |p−[1/2]|−2	16 |p−[1/2]|−2
Taux de Succès	48.6 %	78.5 %	96.7 %	99.9 %

Précisons également que ce distingueur peut être étendu à (r+1) étages en ajoutant un étage au début et en considérant X₀ comme le chiffré sur un étage d'un texte clair P afin de faire intervenir la sous-clé k₀ du premier étage ajouté. Dans ce cas il ne reste plus qu'à appliquer à k₀ la deuxième étape de l'algorithme. Les taux de succès sont alors identiques et la complexité varie très peu.
Le distingueur présenté ici n'est qu'un exemple d'attaque utilisant les relations linéaires. La meilleure attaque connue du DES présentée dans [6] permet de trouver les 56 bits de la clé secrète à l'aide de 2⁴³ couples de clairs/chiffrés connus avec un taux de réussite de 85% grâce à un distingueur utilisant une relation portant sur les 14 tours centraux du DES. La complexité de cette attaque est donc de 2⁴³ chiffrements DES. Cette attaque a été améliorée expérimentalement par P. Junod et S. Vaudenay (voir [4]) : si la complexité reste la même que celle de l'attaque de Matsui, à savoir 2⁴³ chiffrements DES, alors seulement 2^42.5 clairs connus suffisent à cette attaque. On peut également en utilisant 2⁴³ clairs connus obtenir une attaque de complexité 2³⁹ chiffrements DES.

  Une approche simplifiée

Comme dans le cas différentiel pour simplifier les calculs de recherche d'expressions linéaires, on définit le coefficient LP^F où F est une fonction de E dans E′ par :

LPF(a, b) = (2 Pr(a ·X = b ·F(X))−1)2

avec X appartenant à E et tiré au hasard, a appartenant à E et b à E′. On définit également l'ensemble L_F par

LF (a, b) = { X ∈ E / a ·X = b ·F(X) }.

Dans le cas où la fonction F est paramètrée par une clé k prise dans un espace K, le coefficient LP dépend de la clé :

LPFk(a, b) = (2 Pr(a ·X = b ·Fk(X))−1)2

On calcule alors le coefficient ELP :

ELPF(a, b) = Ek ∈ K(LPFk(a,b))

où la fonction E désigne l'espérance mathématique sur l'espace des clés. Lorsque l'on souhaite monter une cryptanalyse linéaire sur la fonction F_k^r à r étages, considérée ici comme le chiffrement à attaquer, on crée un distingueur sur r−1 étages à partir d'une relation linéaire sur (r−1) étages dont la probabilité est ELP^Fr−1(a,b), a et b étant les valeurs qui maximisent le coefficient ELP et F^r−1 représentant la fonction F_k^r sur ses (r−1) premiers étages. Le nombre de clairs N à chiffrer pour qu'une telle attaque réussisse avec un taux de succès de 99.9 % est alors égal à

N= 16 ELPFr−1(a,b) .

En pratique et comme dans le cas de la cryptanalyse différentielle, si un algorithme de chiffrement est composé de r étages identiques constitués d'une série de boîtes S S_i, d'une permutation linéaire et d'une addition de clé, on cherche alors une relation linéaire parcourant les (r−1) premiers tours du chiffrement dont la probabilité est calculée d'abord sur un étage grâce aux coefficients ELP^S_i et sur r−1 étages en multipliant entre elles ces différentes probabilités sur un étage.

 

Références

[1]

A. Canteaut. Cryptanalyse des chiffrements à clefs secrète par blocs. Misc, mars 2002, 2001.

[2]

A. Corfdir and H. Gilbert. A known plaintext attack of feal-4 and feal-6. In Advances in Cryptology -CRYPTO'91, Santa Barbara, Californie, États-Unis, pages 172-181. Lectures Notes in Computer Science 576, Springer-Verlag, 1991.

[3]

H. M. Heys. A tutorial on linear and differential cryptanalysis. Technical Report CORR 2001-17, 2001.

[4]

P. Junod. On the complexity of matsui's attack. In Selected Areas in Cryptography - SAC'01, Toronto, Canada, pages 199-211. Lecture Notes in Computer Science 2259, Springer-Verlag, 2001.

[5]

M. Matsui. Linear cryptanalysis method for des cipher. In Advances in Cryptology -EUROCRYPT'93, Lofthus, Norvége, pages 386-397. Lecture Notes in Computer Science 765, Springer-Verlag, 1993.

[6]

M. Matsui. The first experimental cryptanalysis of the data encryption standard. In Advances in Cryptology -CRYPTO'94, Santa Barbara, Californie, États-Unis, pages 1-11. Lecture Notes in Computer Science 839, Springer-Verlag, 1994.

[7]

National Bureau of Standards (États Unis). Data Encryption Standard. Federal Information Processing Standard, 1977. Publication 46.

[8]

Wikipédia. Cryptanalyse linéaire.