Attaque de D.E.S

 

Principe

Exemple

Extension

 

Principe

Une des attaques les plus classiques de D.E.S. est la méthode de cryptanalyse différentielle, inventée par Biham et Shamir. Elle ne donne pas de moyen de casser la fonction D.E.S. à 16 tours, mais elles permet une attaque efficace des variantes avec un nombre de tours plus réduit.

Le principe de cette attaque est d'ignorer la permutation initiale IP et son inverse : elles ne jouent aucun rôle dans la cryptanalyse.

La cryptanalyse différentielle étudie la comparaison entre le ou-exclusif de deux textes clairs et le ou-exclusif des textes chiffrés correspondant. En général on aura deux textes clairs L0R0 et L0*R0* avec un ou-exclusif spécifique L0'R0' = L0R0+L0*R0*

La meilleure façon d'étudier cette méthode est de prendre un exemple simple : un D.E.S à 3 tours.

Exemple

On commence avec une paire de textes clairs L0R0 et L0*R0* et leurs textes chiffrés L3R3 et L3*R3*.

On a R3 = L2+f(R2,K3) = R1+f(R2,K3)= L0+f(R0,K1)+f(R2,K3)

De même R3* = L2*+f(R2*,K3) = R1+f(R2*,K3)= L0+f(R0*,K1)+f(R2*,K3)

On a donc R3' = L0'+f(R0,K1)+f(R0*,K1)+f(R2,K3)+f(R2*,K3)

Si on suppose R0 = R0* on aurait f(R0,K1) = f(R0*,K1) alors R3' = L0'+f(R2,K3)+f(R2*,K3)

On peut calculer R3' à partir des textes cryptés et L0' à partir des textes clairs. On a alors f(R2,K3)+f(R2*,K3) = R3'+L0'

Or f(R2,K3)=P(C) et f(R2*,K3)=P(C*) où C et C* sont les sorties des huit boites S. Donc P(C)+P(C*) = R3'+L0'.

D'où C' = C+C* = P-1(R3'+L0')

R2 = L3 et R2* = L3* sont connus (ils font partie des textes chiffrés). On peut donc alors calculer E=E(L3) et E*=E*(L3*) à l'aide de la description de la fonction d'expansion. Ces valeurs sont les entrées des boites-S du troisième tour. On connait donc E,E* et C' dans le troisième tour. On peut alors appliquer de façon systématique le test suivant : testj(Ej,Ej*,Cj*) = {Bj+Ej : Bj E INj(Ej',Cj')}

où Ej' = Ej+Ej* et INj(Bj',Cj') = { Bj E (Z2)6 : Sj(Bj)+Sj(Bj+Bj') = Cj'}

On applique ce test sur les valeurs possibles de J1,...,J8. On trouve ainsi les 48 bits de K3, la clé du troisième tour. La clé de 56 bits se calcule ensuite par une recherche exhaustive sur les 2^8=256 possibilités des huit bits inconnus.

Extension

On peut utiliser la cryptographie différentielle sur des D.E.S à plus de tour (cela fonctionne bien sur 6 tours). Mais contre des D.E.S. à 8 tours cela nécessite 2^14 textes clairs, 10 tours 2^24 et 16 tours 2^39 !!