Le masque jetable
Ce chiffrement est théoriquement impossible à casser. Il est, par contre, essentiellement théorique car il reste très complexe à réaliser.
Un peu d’histoire
Le masque jetable est un chiffrement qui a été inventé par Gilbert Vernam, un ingénieur américain de AT&T Bell Labs, en 1917.
Le nom « masque jetable » est la transcription française du terme originel américain « One time Pad » (OTP), la traduction mot à mot étant « tampon à usage unique » (pas de jeu de mots pourris, s’il vous plaît).
Il est basé sur une technique de chiffrement beaucoup plus ancienne appelée « le chiffre de Vigenère ».
Le masque jetable a encore été perfectionné par le général américain Joseph Mauborgne, qui inclut le caractère aléatoire de la clé de chiffrement.
Il consiste à chiffrer un message avec une clé en additionnant la clé au message, élément par élément. La clé ne doit être utilisée qu’une seule fois (d’où le jetable). Pour déchiffrer, on soustrait la clé au message.
Bon, l’histoire c’est bien mais dans les faits, comment ça marche ?
Fonctionnement
Pour pouvoir comprendre le masque jetable il faut déjà maîtriser (ou du moins comprendre) la congruence (ou modulo).
La base
On va commencer en utilisant des textes non aléatoires pour les clés. Attention, c’est juste histoire de démarrer doucement parce que là on est 0 au niveau sécurité.
On va prendre un texte de Bigflo&Oli comme message que l’on veut chiffrer et un texte de Georges Brassens comme clé.
Le message est tiré de « Alors alors » :
« Alors alors, On devait faire le tour de la Terre »
La clé est tirée de « Bancs publics » :
« Les gens qui voient de travers pensent que les bancs verts »
Vous avez le modulo en tête ? Bon, on va commencer par affecter un nombre à chaque lettre de notre alphabet :
A=0, B=1, C=2, D=3, E=4, F=5, G=6, H=7, I=8, J=9, K=10, L=11, M=12, N=13, O=14, P=15, Q=16, R=17, S=18, T=19, U=20, V=21, W=22, X=23, Y=24, Z=25
Donc, pour notre alphabet de 26 lettres on a les 26 premiers chiffres.
Chiffrement
Pour chiffrer, c’est simple, on additionne les lettres face à face. « Additionner des lettres, mais t’es perché ? » me direz vous, mais c’est pour ça qu’on leur a donné un équivalent en nombre, faut suivre un peu. Comme on n’a pas affecté de valeur à la virgule, on va l’enlever.
Allez, c’est parti :
« Alors alors On devait faire le tour de la Terre »
+
« Les gens qui voient de travers pensent que les bancs verts »
Le « A » de « Alors » + le « L » de « Les » = A + L = 0 + 11 = 11 = L
Ensuite le « l » + le « e » = l + e = 11 + 4 = 15 = p
Donc, petit à petit :
« Alors alors On devait faire le tour de la Terre »
+ + +
« Les gens qui voient de travers pensent que les bancs verts »
= = =
0 11 14
+ + +
11 4 18
= = =
11 15 32
= = =
L p ?
Effectivement pour l’addition de « o » et « s », on trouve 14 + 18 = 32 et là on a un soucis, on a pas de lettre avec une valeur de 32.
Mais, rappelez vous, la congruence (le modulo, tout ça, tout ça).
Vu qu’on a que 26 lettres, on va utiliser un modulo 26, histoire de rester dans ces valeurs.
Un petit coup de modulo 26 sur 32, ça fait
$$ 32 \pmod{26} \equiv 32 -26 \pmod{26} \equiv 6 \pmod{26} $$
Et 6, on a, c’est la lettre G.
Du coup, on peut finir notre calcul :
« Alors alors On devait faire le tour de la Terre »
+ + + ...
« Les gens qui voient de travers pensent que les bancs verts »
= = =
0 11 14
+ + +
11 4 18
= = =
11 15 32 mod(26)≡ 6 mod(26)
= = =
L p g …
Au final :
« Alors alors On devait faire le tour de la Terre »
+
« Les gens qui voient de travers pensent que les bancs verts »
=
« Lpgxw ndela Jb liitlx yrimi cw ishj hr eq Nicvw »
On a notre message chiffré.
Déchiffrement
Du coup, pour déchiffrer, on fait le contraire, on soustrait la clé au message chiffré.
On a le message chiffré « Lpgxw ndela Jb liitlx yrimi cw ishj hr eq Nicvw » et la clé « Les gens qui voient de travers pensent que les bancs verts ».
Donc :
« Lpgxw ndela Jb liitlx yrimi cw ishj hr eq Nicvw »
- - -
« Les gens qui voient de travers pensent que les bancs verts »
= = =
11 15 6
- - -
11 4 18
= = =
0 11 -12
= = =
A l ?
Donc, même problème qu’au chiffrement, on a pas de lettre qui corresponde à -12.
On applique le modulo 26 :
$$ -12 \pmod{26} \equiv -12 + 26 \pmod{26} \equiv 14 \pmod{26} \equiv o $$
On continue le calcul et on retrouve :
« Lpgxw ndela Jb liitlx yrimi cw ishj hr eq Nicvw »
- - - ...
« Les gens qui voient de travers pensent que les bancs verts »
=
« Alors alors On devait faire le tour de la Terre »
Mauborgne est dans la place
Bon, ça c’est bien joli, mais c’est pas très sûr. Pour renforcer la sécurité on va écouter le général Mauborgne et utiliser une clé aléatoire (ou du moins plus aléatoire).
Après avoir mis un générateur pseudo-aléatoire (oui, je sais, un terme incompréhensible, on y reviendra dans un article futur) dans mon ordinateur, roulé ma tête sur le clavier et fait marcher le chat dessus pour générer de l’entropie (oui, un autre terme incompréhensible), j’obtiens la clé suivante :
« snchfzrhqjlnveivpyonrkudrpqtpxptfwrildof »
On va chiffrer le message suivant, toujours de Bigflo&Oli, extrait de « Dommage » :
« Il croisait cette même fille, avec son doux parfum »
Chiffrement
Et c’est reparti :
« Il croisait cette même fille, avec son doux parfum »
+ +
« snchfzrhqjlnveivpyonrkudrpqtpxptfwrildof »
= =
8 11
+ +
18 13
≡ =
0 mod(26) 24
=
a y …
On arrive au message chiffré suivant :
« Il croisait cette même fille, avec son doux parfum »
+
« snchfzrhqjlnveivpyonrkudrpqtpxptfwrildof »
=
« ayeythjhycnroxmhtksszvfhrkuvhlcwtqoxlutze »
Déchiffrement
Je crois qu’à ce stade vous avez compris. Un petit exemple alors.
Toujours avec notre modulo(26), déchiffrez ce message :
« irszlg k wiu ladw »
avec la clé :
« xjgzpyisqbjmplcxhwfpijqrstghighnhylshqza »
Et tweetez, postez le résultat.
Le Che level
Bon, jusqu’à présent on était dans le mignon, maintenant on attaque le dur.
Che Guevara et Fidel Castro communiquaient avec une technique de cryptographie basée sur le masque jetable. Cependant, il y avait une petite complexité supplémentaire.
Ils n’utilisaient pas une suite de nombres comme nous l’avons fait, mais ils avaient affecté des nombres arbitrairement aux lettres de l’alphabet.
Voici leur substitution :
A=6, B=38, C=32, D=4, E=8, F=30, G=36, H=34, I=39, J=31, K=78, L=72, M=70, N=76, O=9, P=79, Q=71, R=58, S=2, T=0, U=52, V=50, W=56, X=54, Y=1, Z=59
Vous allez me dire « mais comment on fait une congruence avec ça ? », attendez un peu, ça vient.
En fait, ils ne transmettaient pas des lettres mais des chiffres et la clé était elle-même composée de chiffres. Ils utilisaient le modulo le plus connu (celui qu’on utilise sans savoir), le modulo 10.
Alors, comment faisaient-ils ? On va prendre un exemple.
Chiffrement
On veut chiffrer le message suivant :
« J’aime pas les framboises » (c’est un exemple, moi j’aime bien les framboises)
On remplace les lettres pas leur nombres :
« J A I M E P A S L E S F R A M B O I S E S » devient « 31 6 39 70 8 79 6 2 72 8 2 30 58 6 70 38 9 39 2 8 2 »
On va chiffrer ce message avec la clé :
« 4317892093088287991744997181628757157172 »
Pour ça, on additionne les chiffres face à face et on applique le modulo 10. Pour se faciliter la tâche, ils regroupaient d’abord les chiffres par paquet de 5.
Donc, le message :
« 31 6 39 70 8 79 6 2 72 8 2 30 58 6 70 38 9 39 2 8 2 »
devient :
« 31639 70879 62728 23058 67038 93928 2 »
On additionne avec le modulo 10 :
« 31639 70879 62728 23058 67038 93928 2 »
+
« 43178 92093 08828 79917 44997 18162 87571 57172 »
=
747 (7+3 ≡ 10 mod(10) ≡ 0) …
=
74707 62862 60546 92965 01925 01080 0
Le message chiffré est donc :
« 74707 62862 60546 92965 01925 01080 0 »
Déchiffrement
On soustrait la clé au message avec le modulo 10 :
« 74707 62862 60546 92965 01925 01080 0 »
-
« 43178 92093 08828 79917 44997 18162 87571 57172 »
=
« 31639 70879 62728 23058 67038 93928 2 »
Et ensuite, on transforme les nombres dans leur lettre respective. Et là, vous vous dites « Mais comment ils peuvent faire la différence entre la lettre de valeur 2 et la lettre de valeur 23 ? Comment ils peuvent savoir si c’est un nombre à 2 chiffres ou à 1 ? ».
Très simple, le chiffre utilisé pour les nombres à 1 chiffre n’est pas utilisé pour démarrer un nombre à 2 chiffres.
En fait, si on tombe sur 3, 7 ou 5, on sait que c’est un nombre à 2 chiffres et donc qu’il faut regrouper le chiffre suivant avec lui.
Dans notre cas, on commence avec un 3, donc on sait qu’on a un nombre à 2 chiffres, on colle le 1 au 3.
« 31 639 70879 62728 23058 67038 93928 2 »
Ensuite, le 6 n’est pas dans (3,7,5), donc c’est un nombre à un seul chiffre :
« 31 6 39 70879 62728 23058 67038 93928 2 »
Et ainsi de suite :
« 31 6 39 70 8 79 6 2 72 8 2 30 58 6 70 38 9 39 2 8 2 »
On remplace enfin les nombres par leurs lettres :
« J A I M E P A S L E S F R A M B O I S E S »
Voilà !
La perfection du chiffrement
Claude Shannon (encore du « name dropping » mais celui-là c’est le vaisseau amiral des cryptographes) prouve mathématiquement que le masque jetable est considéré cryptographiquement sûr, ou inconditionnellement sûr, durant la Seconde guerre mondiale. C’est à dire que le système ne peut pas être percé même si l’adversaire a des moyens illimités ou un temps illimité, tant qu’il ne connaît pas la clé secrète.
Claude Shannon prouve que le masque jetable est « à secret parfait », c’est à dire que si on a un texte chiffré par le masque jetable sous les yeux, il n’y a absolument aucun moyen de deviner quoi que ce soit sur le texte d’origine.
Cela veut dire qu’il est aussi résistant à une attaque par force brute. Si vous essayez toutes les clés de l’univers vous tomberez sur tout les messages de l’univers donc vous n’aurez aucun moyen de savoir lequel est le bon.
Je ne vais pas vous refaire les démonstrations mathématiques ici. Cet article a un but de large diffusion facilement accessible.
Mais pour réaliser cette perfection, il y a quelques problèmes.
Les difficultés
Les difficultés à surmonter pour réaliser un parfait masque jetable sont les suivantes :
La taille et la quantité des clés
Pour chaque échange il faut une nouvelle clé. Pour chaque échange, c’est à dire, chaque personne avec qui vous échangez et chaque texte que vous lui envoyez.
Donc, vous échangez 2 messages avec 2 personnes, ça fait 4 clés. 3 messages avec 3 personnes, 9 clés…
De plus, la clé doit être plus longue que le message.
Car si elle est plus courte et qu’on la répète pour finir le chiffrement, on augmente la probabilité d’apparition de certaines lettres et on peut voir des motifs apparaître donnant des indices sur le message. Ce problème est semblable à la nécessité de l’aléatoire pour créer les clés.
Cela pose des problèmes de stockage des clés de façon sécurisée, le masque s’effondrant si la clé est récupérée par l’adversaire.
L’aspect aléatoire des clés
En français, la lettre « e » est la lettre la plus couramment utilisée, puis c’est « a », puis « s »…
Et des motifs comme « le », « les » sont fréquents. La clé, en se répétant, augmente les probabilités de chiffrer de la même façon des mêmes motifs.
L’attaquant peut repérer ces motifs et parvenir à en déduire le moment où la clé est répétée.
Petit à petit, il peut recomposer la clé ou même faire sans.
Un exemple :
Imaginons la clé « Wesh », l’attaquant ne la connaît pas mais a trouvé que sa longueur était de 4 en analysant les fréquences de motifs récurrents.
Il peut découper ce texte chiffré en groupes de 4 lettres : « Uedl lsll ysfk wqfl myaz kvlp newu zsmj a » et soustraire les groupes entre eux :
Uedl - lsll = X ? + « Wesh » - (Y ? + « Wesh ») = X ? - Y ? + « Wesh » - « Wesh »
= X ? - Y ?
La clé a disparu et on a deux textes qui ne sont plus aléatoires soustraits l’un à l’autre. On analyse la fréquence d’apparition des lettres et on forme des hypothèses. Les lettres, issues de la soustraction, les plus fréquentes ont des probabilités plus élevées d’avoir un « e » dans l’une de leurs lettres de base, etc.
Étape par étape, en multipliant les hypothèses, on réduit les possibilités et on peut parvenir à trouver la clé ou déchiffrer des messages sans elle.
En conclusion, si vous faites une analyse des fréquences en faisant tourner votre ordinateur pendant trois jours, vous obtiendrez le message suivant :
« Y’a le pote condamné qui sortira en douce », toujours Bigflo&Oli, extrait de « Comme d’hab »
Cela vous semble obscur, incompréhensible. Pas de panique, un prochain article éclaircira tout ça avec des exemples.
Donc, pour faire en sorte que chaque lettre ait la même probabilité d’apparaître il faut des clés générées aléatoirement. Mais ça, c’est très compliqué à faire. On sait faire du pseudo-aléatoire mais comme son nom l’indique ce n’est pas complètement aléatoire, les probabilités d’apparition des lettres ne sont pas exactement les mêmes.
La transmission des clés
La transmission des clés n’est pas un problème pour de toutes petites clés (un article expliquera bientôt comment).
Mais cela devient très compliqué dés lors que les clés doivent dépasser une certaine taille (la taille minimale est à l’heure actuelle de 4096 bits voire dans certains cas de fou fou 8192 bits, c’est à dire 1024 octets, 1ko pour les informaticiens).
Donc, souvent, les clés sont échangées physiquement à l’avance. Ce n’est pas pratique et devient très compliqué pour envoyer beaucoup de messages à beaucoup d’interlocuteurs.
L’unicité d’usage
On en revient au même problème que pour la taille des clés et l’aspect aléatoire des clés.
Si on réutilise une clé, on perd l’aspect aléatoire et le message chiffré est de nouveau sensible à une analyse des fréquences.
Le problème est plus grave encore car l’unicité d’usage suppose la destruction de la clé après utilisation et il n’existe pas de moyen facile pour s’assurer que vos interlocuteurs ne gardent pas les clés dans un coin au risque de se les faire voler plus tard (dans 5 ans, 10 ans…) ou ne les réutilisent pas pour d’autres messages de leur côté.
L’empoisonnement du message
Le dernier soucis possible est l’empoisonnement des clés mais cela peut être réglé assez facilement (du moins temporairement) en informatique.
Comme le masque jetable est insensible à la force brute (toutes les clés de l’univers donnant tous les messages de l’univers), un attaquant peut s’amuser à modifier le message chiffré pour lui donner un sens différent.
Il peut aussi modifier la clé sans forcément la connaître et ainsi modifier le message en clair.
Exemple :
Reprenons notre fameux message :
« J’aime pas les framboises »
que l’on chiffre avec la clé :
« nzhtjplgpggsefirksxohsbyhkazsb »
en modulo 26 (donc sans l’apostrophe), on obtient :
« N zrry rrg yef eytvqzohky »
L’attaquant ne connaît que ce message secret mais il peut modifier la clé de chiffrement. Il remplace donc la clé par :
« ezjfuqjcltbmtcvihgdtgefirksxohsbyhkazsb »
Et ça donne le message clair suivant :
« Jaimebienlesfraisiers »
Donc, pas du tout le message original.
Pour éviter ça, en informatique, on peut signer et faire un hachage du message et des clés et donc un utilisateur peut vérifier que le message qu’il reçoit est bien conçu par la bonne clé et que la clé qu’il utilise est toujours la bonne.
Nous reviendrons sur le fonctionnement d’une signature et d’un hachage dans de prochains articles.
Je crois qu’on a déjà largement dépassé les 2000 mots. On va s’arrêter là.