Travaux dirigés : le masque jetable

Ces quelques exercices éprouvent, sur des cas concrets, la théorie du secret parfait et ses limites. On y voit à la fois pourquoi le masque jetable est inviolable lorsqu’il est bien employé, et avec quelle brutalité il s’effondre dès qu’on transgresse ses conditions d’usage.

Les propriétés du XOR

Tout repose sur les identités du OU exclusif, dont on ne dira jamais assez qu’elles font toute la simplicité du procédé :

$A\oplus B=C⟺A=B\oplus C,(X\oplus Y)\oplus Y=X,X\oplus X=0,X\oplus 0=X.$

Le chiffrement OTP en découle directement : $\mathrm{Enc}(k,m)=m\oplus k$ et $\mathrm{Dec}(k,c)=c\oplus k$. L’involution du XOR fait que déchiffrer, c’est rechiffrer.

Chiffre de César : parfait pour un seul symbole

Sur l’alphabet $A={\mathbb{Z}}_{26}$, avec $M=C=K=A$ et $e:(m,k)\mapsto c\equiv m+k(\mathrm{mod}26)$, on fixe un clair $m$ et un chiffré $c$. Il existe alors une unique clé $k\equiv c-m(\mathrm{mod}26)$. Si $K$ est uniforme sur $A$ et indépendante de $M$, alors

$\mathrm{Pr}(C=c\mid M=m)=\mathrm{Pr}(K=c-m)=\frac{1}{26}=\mathrm{Pr}(C=c).$

Le chiffré est donc indépendant du clair : César est parfaitement sûr — mais seulement pour un unique symbole chiffré avec une clé à usage unique.

Vigenère : parfait si la clé est assez longue

En passant à des mots de longueur $n$, avec $M=C=K=A^n$ et une addition coordonnée par coordonnée, la clé reste unique pour $(m,c)$ fixés, et le même calcul donne $\mathrm{Pr}(C=c\mid M=m)=26^{-n}=\mathrm{Pr}(C=c)$ : parfaite sûreté, dès lors que la clé est au moins aussi longue que le message et utilisée une fois.

L’échec survient si la clé, de longueur $t<n$, est répétée. Le même $k_i$ sert alors à plusieurs positions, ce qui impose, pour tous $i\equiv j(\mathrm{mod}t)$, la contrainte $(c_i-m_i)\equiv (c_j-m_j)(\mathrm{mod}26)$. Certains couples $(m,c)$ deviennent dès lors impossibles tandis que d’autres restent réalisables, et $\mathrm{Pr}(C=c\mid M=m)$ se met à dépendre du message. Ainsi, pour $n=4$ et $t=2$, si $c_1-m_1\not\equiv c_3-m_3$, aucune clé n’existe : la sûreté parfaite est perdue.

Déchiffrer par involution

L’exercice est immédiat : $m=c\oplus k$. Par exemple, pour c = 01011101 et k = 10011011, on obtient $m=\text{11000110}$. Pour $k$ fixé, l’application $m\mapsto c$ est bijective.

La faute mortelle : réutiliser la clé

C’est le point le plus instructif. Si $c_1=m_1\oplus k$ et $c_2=m_2\oplus k$, alors la clé s’annule dans le XOR des chiffrés :

$c_1\oplus c_2=m_1\oplus m_2.$

L’attaquant travaille dès lors sans la clé, sur le seul XOR des clairs. La technique du crib consiste à faire une hypothèse de clair sur $c_1$, à en déduire la clé candidate $k=c_1\oplus \text{clair}$, puis à la vérifier sur $c_2$. Dans le TD, l’hypothèse alpha / bravo est cohérente et livre la clé, quand l’hypothèse delta / gamma échoue — toute la sécurité du masque a fondu par sa seule réutilisation.

Variantes et leurs verdicts

Deux variantes montrent, a contrario, ce que la structure du XOR apportait.

Un OTP « mod 4 » sur l’alphabet $\{0,1,2,3\}$, défini coordonnée par coordonnée par $\mathrm{Enc}(k,m)=m+k\mathrm{mod}4$, conserve l’unicité de la clé ($k\equiv c-m\mathrm{mod}4$) et donc, avec $K$ uniforme, la sûreté parfaite : $\mathrm{Pr}(C=c\mid M=m)=4^{-\ell }=\mathrm{Pr}(C=c)$. La logique du binaire s’y transpose sans accroc.

Une variante « AND », en revanche, ruine tout : elle n’est pas injective, car $k_i=0$ force $c_i=0$ quel que soit $m_i$. On a alors $\mathrm{Pr}(C=0^{\ell }\mid M=0^{\ell })=1$ face à $\mathrm{Pr}(C=0^{\ell }\mid M=1^{\ell })=\mathrm{Pr}(K=0^{\ell })$ : la loi de $C$ dépend de $M$, et la sûreté parfaite disparaît.

Enfin, exclure la clé nulle — tirer $K$ uniformément sur $\{0,1{\}}^{\ell }\setminus \{0^{\ell }\}$, avec $\mathrm{Pr}(K=k)=\frac{1}{2^{\ell }-1}$ — semble anodin mais casse aussi la perfection. Car si $c=m$, la clé requise serait précisément $0^{\ell }$, désormais interdite ; d’où

$\mathrm{Pr}(C=c\mid M=m)=\{\begin{array}{ll}0& \text{si }c=m,\\ \frac{1}{2^{\ell }-1}& \text{sinon.}\end{array}$

La distribution dépend à nouveau de $M$ — pour un gain de sécurité nul, une perte bien réelle.

Le coût du masque : consommation de clé

Reste la raison profonde de l’impraticabilité du OTP : il consomme un bit de clé par bit de message. En rapportant la capacité de quelques supports à divers débits, on mesure l’absurdité du procédé à l’échelle réelle.

Support	40 b/s	64 kb/s	140 Mb/s
CD-R (≈ $5,6\times 10^9$ bits)	≈ 4,4 ans	≈ 1 j	≈ 40 s
DVD (≈ $3,8\times 10^{10}$ bits)	≈ 30 ans	≈ 7 j	≈ 4 min 30
Blu-ray (≈ $4,0\times 10^{11}$ bits)	≈ 317 ans	≈ 72 j	≈ 48 min

Un Blu-ray entier de clé ne couvre qu’une poignée de minutes de flux vidéo : voilà pourquoi, malgré sa perfection théorique, le masque jetable cède la place aux chiffrements à sécurité calculatoire.