Exemple d'attaque à texte clair connu: 2DES (II)

L'attaque ``Meet in the middle'' contre 2DES est une attaque à texte clair connu: on suppose qu'on connaît $x_1$, $x_2$, $y_1$ et $y_2$ tels que $y_1=e_{K_2}(e_{K_1}(x_1))$ et $y_2=e_{K_2}(e_{K_1}(x_2))$

L'attaque part du principe que $e_{K_1}(x)=d_{K_2}(y)$, c'est-à-dire que si je chiffre une fois seulement le texte clair, c'est la même chose que de déchiffrer une fois seulement le texte chiffré. En d'autres terme, je chiffre dans un sens, déchiffre dans l'autre, et les deux résultats se recontrent au milieu, d'où le nom.

Je commence par calculer les $2^{56}$ couples $(K,e_{K}(x_1))$, que je stocke.

Pour chaque clé $K'$, je calcule $d_{K'}(y_1)$, et je regarde si je trouve une correspondance dans ma table. Si oui, j'ai un couple de clé candidates $K_1=K$ et $K_2=K'$, et je vérifie si cela correspond avec $y_2=e_{K_2}(e_{K_1}(x_2))$. Si oui, j'ai une très forte probabilité d'avoir le bon couple de clés (je peux augmenter cette probabilité en essayant sur un troisième couple $x_3$, $y_3$), sinon je continue à chercher. Le nombre maximal d'essais que je devrai faire est $2\cdot 2^{56}=2^{57}$, soit loin des $2^{112}$ que je pouvais espérer d'un 2DES !

Cette attaque est valable pour tous les algorithmes chaînés, mais elle devient vite impraticable si la taille de clé est plus grande.