Masque jetable : inviolable une fois, brisé à la seconde

Combinez chaque octet d’un message avec un octet aléatoire par un OU exclusif : le texte chiffré ne livre aucun indice à l’adversaire. Utilisez la même clé pour deux messages et celle-ci disparaît : faites défiler un mot présumé pour déchiffrer l’autre texte en transparence.

Exemple résolu — Masque jetable : inviolable une fois, brisé à la seconde

Caractères	14
Clés possibles pour cette longueur	5,2 × 10³³
Messages envisageables pour cette longueur	1,1 × 10²⁰

Ce sont les valeurs affichées par le calculateur à l’ouverture de la page. Modifiez une entrée ci-dessus pour les recalculer.

Chargement de la simulation interactive...

Leçon

La théorie — Masque jetable : inviolable une fois, brisé à la seconde

Le masque jetable combine chaque caractère d’un message avec un caractère de clé choisi au hasard, réservé à cet unique caractère et jamais réutilisé. Ici, la combinaison s’effectue par le OU exclusif bit à bit, octet par octet : C = P ⊕ K, le déchiffrement étant la même opération, P = C ⊕ K. Avec une clé aléatoire aussi longue que le message, le chiffre possède un secret parfait : intercepter le texte chiffré ne modifie en rien l’estimation du message émis. Utilisée sur deux messages, la clé s’annule, C₁ ⊕ C₂ = P₁ ⊕ P₂, et le glissement de mot probable consiste à faire défiler un mot w présumé le long de cette suite : partout où l’un des messages contient réellement w, l'expression w ⊕ C₁ ⊕ C₂ restitue l’autre message.

Ce que signifie chaque symbole

P: le message, à raison d’un octet par caractère
K: la clé : des octets aléatoires, en nombre égal aux caractères du message
C: le texte chiffré, P ⊕ K
⊕: le OU exclusif : chaque bit du résultat vaut 1 là où les deux bits diffèrent
w: le mot probable, un mot que l’on suppose présent dans l’un des messages

Suppose: Les messages sont formés de lettres minuscules et d’espaces codés en octets ASCII. Les octets de clé proviennent d’un générateur pseudo-aléatoire initialisé par une graine de 32 bits ; la page n'atteint donc que 2³² ≈ 4,3 × 10⁹ clés. Dès sept caractères, le nombre de clés devient inférieur au nombre de messages possibles : selon le critère de Shannon, le masque simulé ici n’est pas parfaitement secret. Un masque authentique requiert des octets que personne ne peut régénérer. Un fragment est jugé « vraisemblable » si chaque octet correspond à une lettre ou un espace et si chaque suite de trois caractères est attestée dans les deux premiers tiers du « Scarabée d’or » de Poe (1843) ; les paires mesurées proviennent du dernier tiers. Le XOR est préféré à l’addition modulo 26 des lettres car il est auto-inverse : le texte sous-jacent émerge directement, quel que soit le message auquel appartient le mot probable.

Tester toutes les clés révèle tous les messages 🖖

Parcourez Attaque à l’aube pas à pas et observez les deux dernières lignes : elles affichent la clé qui transformerait ce même texte chiffré en « retreat at ten ». Tapez 14 autres lettres et espaces dans le second champ, et une clé correspondante apparaît aussitôt. L'opération XOR est sa propre réciproque : le texte chiffré combiné à votre message engendre la clé requise. Un adversaire qui essaierait les 256¹⁴ clés possibles ne retrouverait donc jamais votre texte. Il obtiendrait indistinctement chacune des 27¹⁴ ≈ 1,1 × 10²⁰ séquences de cette longueur, chacune produite par une clé unique. Toutes les clés étant équiprobables au départ, l'interception du message chiffré ne rend aucun texte plus vraisemblable qu'un autre. Shannon a formalisé ce secret parfait en 1949 et a prouvé ce qu'il exige : au moins autant de clés que de messages concevables. Une clé de Vigenère, répétitive, en offre beaucoup moins, ce qui permet au dénombrement de la casser.

Les espaces transparaissent avant toute hypothèse 🖖

Cliquez sur Où sont les espaces. La clé s’est volatilisée : C₁ ⊕ C₂ équivaut à P₁ ⊕ P₂, octet par octet, sans qu’il n’en reste la moindre trace. Observez maintenant les octets surlignés en bleu : 19 sur les 50. Une lettre minuscule correspond à un octet entre 0x61 et 0x7a, et l’espace vaut 0x20. Or, seule l’opération entre une lettre et un espace active le bit 0x40. Chaque valeur égale ou supérieure à 64 indique donc avec certitude qu'exactement l’un des deux messages porte un espace à cet endroit. Avant toute déduction de mot, les frontières lexicales transparaissent déjà, même si l’on ignore encore à quel message chaque espace appartient. Sur 2 000 paires de séquences de 60 caractères issues du Scarabée d’or, près de 30 % des positions en trahissent un. Les télégrammes soviétiques que Meredith Gardner commença à lire en 1946, dans le cadre du projet américain Venona, additionnaient des chiffres de clé à des groupes codés au lieu d'effectuer un XOR binaire. Mais soustraire deux textes chiffrés annule la clé commune avec la même implacable simplicité. Ce réemploi tenait à une erreur matérielle : pressée par l’avancée allemande sur Moscou, l’imprimerie fabriquant les carnets du KGB en avait tiré environ 35 000 pages en double exemplaire.

Les deux espaces encadrant un mot probable font l'essentiel du travail 🖖

Cliquez sur Sans les espaces. En position 26, « the » donne « org ». Ce ne sont que des lettres, et chaque suite de trois lettres figure bien dans le texte de référence ; pourtant, aucun des deux messages ne contient « the » à cet endroit. Rétablissez les espaces — « the » — et seules les occurrences authentiques passent le filtre sur cette paire. Sur 2 000 paires d’extraits de 60 caractères tirées du dernier tiers du Scarabée d’or, resté inconnu de la référence, « the » a été validé sur 3 661 positions et correspondait au texte réel 3 281 fois, soit près de 9 fois sur 10. Sans espaces, « the » a franchi le filtre 9 615 fois pour seulement 4 169 présences effectives : moins de la moitié. L'explication réside dans les octets bleus. Un espace placé dans le mot probable ne peut produire une lettre qu'en face d'un octet supérieur ou égal à 64, et un espace qu'en face d'un 0. Partout ailleurs, le résultat n'est même pas une lettre. Chaque espace du mot probable doit donc coïncider avec une coupure réelle dans l'un des messages, et une mauvaise position aligne rarement un tel doublé.

Problème entièrement résolu

Cinq lettres extraites de deux messages partageant un masque 4 étapes
Deux messages de 50 caractères ont été transmis sous un même masque jetable. Aux positions 32 à 36, C₁ ⊕ C₂ affiche 54 06 09 0c 4e en hexadécimal. Supposons que l’un des messages contienne « the » à cet endroit, soit les octets 20 74 68 65 20. Que contient l’autre message sur ces cinq positions ? Si cette hypothèse s'applique au message 2, dont le texte chiffré vaut 9d 8e 23 40 9e, quels sont les cinq octets de la clé ? Cliquez ensuite sur Exercice résolu et suivez l’étape suivante à l’écran.

Ouvrez ce problème dans l'outil
1. Écrivons la première paire en binaire : 0x54 donne 01010100 et l’espace 0x20 donne 00100000. Le XOR place un bit 1 là où les deux diffèrent, ce qui donne 01110100, soit 0x74 : la lettre t. Le bit 0x40 de 0x54 révélait d’ailleurs déjà, avant toute déduction, que l’un des messages avait un espace en position 32.
  
  $0x54 \oplus 0x20 = 01010100 \oplus 00100000 = 01110100 = 0x74 = t$
2. Pour les quatre autres : 0x06 ⊕ 0x74 = 0x72, r ; 0x09 ⊕ 0x68 = 0x61, a ; 0x0c ⊕ 0x65 = 0x69, i ; 0x4e ⊕ 0x20 = 0x6e, n. L’autre message révèle « train », et ses trois trigrammes, « tra », « rai » et « ain », figurent tous dans la référence.
  
  $54 06 09 0c 4e \oplus 20 74 68 65 20 = 74 72 61 69 6e = train$
3. Si « the » appartient au message 2, la clé s'écrit C₂ ⊕ P₂ : 0x9d ⊕ 0x20 = 0xbd, 0x8e ⊕ 0x74 = 0xfa, 0x23 ⊕ 0x68 = 0x4b, 0x40 ⊕ 0x65 = 0x25, 0x9e ⊕ 0x20 = 0xbe. Si le mot probable avait appartenu au message 1, le message 2 donnerait « train » et les octets de clé vaudraient C₁ ⊕ « the ». C₁ ⊕ C₂ est identique dans les deux cas : le calcul seul ne peut donc trancher.
  
  $K = C_{2} \oplus P_{2} = 9d 8e 23 40 9e \oplus 20 74 68 65 20 = bd fa 4b 25 be$
4. Sur la page, « the » est validé dans le message 2 en position 32, et le champ du mot probable reçoit « train » en position 31, en pariant que « train » forme un mot entier dans le message 1. On voit alors apparaître « y the r » pour le message 2 : des lettres et des espaces, dont chaque trigramme est connu. Validez-le dans le message 1 et les deux lignes s’étendent à sept caractères.
  
  $(C_{1} \oplus C_{2})_{31..37} \oplus 20 74 72 61 69 6e 20 = 59 54 06 09 0c 4e 52 \oplus 20 74 72 61 69 6e 20 = 79 20 74 68 65 20 72$
Réponse

« train », et les octets de clé bd fa 4b 25 be si le mot appartenait au message 2. Rien dans C₁ ⊕ C₂ n’indique quel message renferme « the », et rien ne le permettra jamais : échanger intégralement les deux messages laisse C₁ ⊕ C₂ inchangé. L'hypothèse suivante décide seulement quels fragments appartiennent au même message. La page compte aussi le nombre de caractères retrouvés exacts car elle dispose des deux messages d'origine. Un intercepteur, lui, n'a sous les yeux que les deux lignes et leur intelligibilité.

$train, K_{32..36} = bd fa 4b 25 be$

Parcours

Comment casser les chiffres

Références (2)

The first insight's perfect secrecy and its cost in keys, and the Vigenère link: C. E. Shannon, "Communication Theory of Secrecy Systems," Bell System Technical Journal 28(4), pp. 656–715, October 1949. §10 "Perfect Secrecy", Theorem 6 (pp. 679–682).
The second insight's Venona history: the additive key, the duplicate pages, Gardner's first message: "VENONA: An Overview," Cryptologic Almanac 50th Anniversary Series, Center for Cryptologic History, National Security Agency. DOCID 3575728, approved for release 2009.

Par l’équipe 42Math · Vérifié sur des sources publiées. Corrections bienvenues.