Cryptanalyse d'Enigma

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Version américaine d'une machine de cryptanalyse d'Enigma.

La cryptanalyse d'Enigma, c'est-à-dire le décryptage des messages chiffrés par Enigma, fut un facteur des succès alliés pendant la Seconde Guerre mondiale.

Avant le début de la guerre, le mathématicien polonais Marian Rejewski élabore la première cryptanalyse, fondée sur une redondance : le cryptage de la clef choisie par le chiffreur était répété dans le préambule du message. Durant la guerre, les Britanniques améliorent la cryptanalyse de la machine grâce aux efforts d'Alan Turing et des très nombreux cryptographes de Bletchley Park.

Les pionniers[modifier | modifier le code]

Les premières versions commerciales d'Enigma remontent au début des années 1920. La machine apparaît alors comme très sûre, impossible à casser. Dès 1926, plusieurs pays tentent de percer les mystères d'Enigma. Mais les mathématiciens américains, britanniques et français échouent. Pendant ce temps, la marine allemande met en place des versions modifiées d'Enigma pour chiffrer ses transmissions.

Persévérance de la Pologne[modifier | modifier le code]

Machine exposée à Varsovie, Pologne
Biuro Szyfrów, Varsovie, 1932

Les Polonais commencent à travailler sur Enigma dès 1928, avec l'appui de leur service de renseignements. En 1929, ils interceptent une machine Enigma, envoyée de Berlin à Varsovie, qui aurait dû passer par la valise diplomatique. Cette erreur permet aux services polonais d'en examiner le contenu. Même s'il ne s'agit que d'une version commerciale a priori assez anodine, la machine confirme que les Allemands utilisent Enigma pour chiffrer leurs messages essentiels. Lorsqu'Enigma est adoptée par l'armée allemande, des années plus tard, les Polonais concentrent leurs recherches sur les évolutions de la machine. Débute alors une cryptanalyse intensive qui vise à définir les circuits de la version militaire, afin de trouver une méthode de déduction des clefs pour des messages donnés.

Marian Rejewski, mathématicien polonais de 27 ans, découvre alors un moyen mathématique de retrouver ces deux paramètres essentiels. Rejewski remarque une répétition de la clef. Le chiffreur choisit une combinaison de trois lettres qu'il chiffre deux fois. Cette clef chiffrée est l'un des articles du préambule du message.

Une fois Enigma disposée sur les réglages du jour, le chiffreur choisit au clavier trois lettres, ex. "WIK", la clef du message, qu'il tape deux fois : « WIKWIK ». Le tableau lumineux affiche, ex. « AXLQPB ». Rejewski compare les lettres deux à deux : la lettre « W » correspond à « A », mais également à « Q », la lettre « I » se transforme en « X » et en « P » et finalement la lettre « K » se chiffre en « L » et « B ».

Dans le cas de la lettre « W », trois rotations du disque produisent la lettre « Q », on fait la même observation pour les autres lettres. Cela veut dire qu'il y a un lien étroit entre ces correspondances, la rotation des rotors et le câblage interne de la machine. Même si les trois lettres originales sont inconnues, on sait que le nombre de câblages qui peuvent transformer ces trois lettres en une séquence particulière sont limités. Rejewski les nomme des « chaînes ».

Les chaînes[modifier | modifier le code]

Les Polonais exploitent les failles cryptographiques des Allemands. Leurs agents ont fourni un exemplaire d'un vieux manuel d'Enigma qui cite un exemple de chiffrement avec le texte en clair, la clé et le résultat une fois chiffré. Rejewski l'étudie attentivement.

Le nombre de chaînes possibles est 105 456. Mais, à l'époque, en l'absence d'une puissance de calcul suffisante, la recherche est quasi impossible. Grâce à Jerzy Różycki et Henryk Zygalski, l'équipe de Rejewski découvre plusieurs techniques d'accélération des calculs. L'une d'elles fait appel à des feuilles transparentes (feuilles de Zygalski), avec les schémas des rotors. Les feuilles sont superposées et les lettres composant une chaîne dite « impossible » sont rayées. À la fin de l'opération, les trois lettres restantes sont la clef du message.

Les Britanniques avaient développé le même genre de technique basée sur une grille, technique qui avait fait ses preuves sur l'Enigma commerciale, mais n'était pas adaptée pour « casser » la version militaire. Une variante de cette méthode consiste à utiliser des cartes perforées. À la fin, un alignement complet des trous indique la clef de trois lettres.

Bombe cryptographique

Malgré cette performance, la recherche manuelle n'en est pas moins éreintante. Les Polonais construisent en 1938 une bombe cryptologique, la bomba kryptologiczna, calculateur électromécanique qui teste des milliers de combinaisons des trois rotors dont elle sélectionne les quelques solutions acceptables. Six exemplaires sont montés à Varsovie dans le bureau du chiffre, juste avant septembre 1939. Chacune contient l'équivalent de six machines Enigma commandées électriquement. Le volume occupé est par contre considérable, l'équivalent d'un atelier de 100 personnes, mais le gain de temps est significatif : il suffit de deux heures pour trouver la clef.

Les Polonais seront ainsi capables de déchiffrer, par intermittences, une certaine partie des transmissions de l'armée allemande, durant la Guerre civile espagnole, jusqu'à l'aube de la Seconde Guerre mondiale. Le renseignement avait joué un rôle. Dès 1931, un agent du SR-Guerre français, Hans-Thilo Schmidt, prête des documents liés à Enigma.

Invasion de la Pologne[modifier | modifier le code]

En 1939, les Polonais doivent se rendre à l'évidence : les Allemands ont compliqué la structure de leur machine. Au cours des années 1930, les Allemands avaient modifié quelques paramètres, mais rien qui n'avait pu empêcher les Polonais de trouver une parade. Cette fois-ci, avec la guerre qui s'annonce, la situation est plus grave. Jusqu'alors, seuls trois rotors étaient employés, mais l'armée allemande introduisit deux autres rotors. Le 1er mai 1940, suppression de la répétition de la clef citée dans le préambule du message. Du coup, les efforts des Polonais sont réduits à néant, puisque leur cryptanalyse repose sur cette redondance. L'armée allemande avait identifié cette répétition comme une faille. Cette suppression avait été prévue par Turing qui avait entrepris de chercher un autre mode d'entrée.

À l'été 1939, les Polonais partagent leurs secrets avec les Français et les Britanniques. Ils fournissent deux copies d'Enigma, la description précise de leurs trucs, méthode du gril, méthode de l'horloge, feuilles de Zygalski, et les plans de la bombe cryptographique qui inspireront la bombe électromécanique de Turing. Le 1er septembre 1939, la Pologne est envahie. Sur ordre, les cryptologues polonais fuient Varsovie. Près de Paris, au PC Bruno, ils travaillent pour le SR-Guerre, en liaison avec le GC&CS. A deux reprises, Alan Turing demeure quelques jours au PC Bruno où il est briefé par ses confrères polonais.

Le 24 juin 1940, les cryptologues polonais sont exfiltrés en Algérie. Ils reviennent en zone libre, au centre Cadix. Trois périssent noyés en Méditerranée, après un séjour en Algérie. En novembre 1942, invasion de la zone libre. En février 1943, Rejewski et Zygalski passent en Espagne où ils sont emprisonnés, au Portugal et à Gibraltar d'où ils gagnent le Royaume-Uni. En mars 1943, cinq, dont les deux chefs, Langer et Ciezki, sont capturés dans les Pyrénées. Deux meurent au camp de Sachsenhausen. En mars 1944, Langer et Ciezki interrogés admettent avoir réussi à décrypter certains messages, avant la guerre, mais ils taisent leurs activités après septembre 1939.

Bletchley Park[modifier | modifier le code]

Bletchley Park

Mis à l'écart d'Enigma, Rejewski et Zygalski sont affectés aux chiffres manuels allemands. La cryptanalyse d'Enigma est devenue une affaire britannique. Les méthodes polonaises ne lisent plus les trafics Enigma de la Heer et de la Luftwaffe.

Les attaques des Britanniques ressemblent à celles des Polonais. Une nouvelle attaque s'intéresse au réflecteur, qui garantit que toute lettre est différente après chiffrement. De plus, les Britanniques font appel à l'analyse des mots probables. Les messages ont de fortes chances de contenir des termes comme « Keine besondere Ereignisse (rien à signaler)», « Eins (chiffre 1) », « Répétez », « munition », « Wet (météo) », etc. Ces mots probables sont baptisés "cribs (antisèches)". Les cryptologues essaient de deviner le contenu des messages, en fonction de renseignements obtenus par ailleurs. En faisant quelques hypothèses sur le contenu et sachant qu'une lettre n'est jamais chiffrée par elle-même, il n'est pas impossible de retrouver une partie du texte clair, en essayant tous les alignements possibles. À partir des résultats positifs, on arrive parfois à deviner un texte presque complet. Cette attaque ressemble à celle des Polonais qui avaient tenté de deviner le préambule des messages. Turing découvre des « clicks », paires de lettres qui apparaissent plusieurs fois entre le message chiffré et sa version déchiffrée (il avait des copies d'Enigma à sa disposition). Comme Enigma est réversible, une correspondance A→J est équivalente à J→A.

Pour illustrer ce principe d'une manière très simplifiée, prenons la phrase suivante en clair : « ATTAQUECESOIRSURWIKIPEDIA ». On intercepte le message chiffré : « YAOPWMKLRBFZLVCXKTROTQALD ». Effectuons une première comparaison :

A T T A Q U E C E S O I R S U R W I K I P E D I A
Y A O P W M K L R B F Z L V C X K T R O T Q A L D

L'attaque de Turing se base sur la recherche de boucles entre le texte clair et le texte chiffré. La deuxième lettre du message en clair « T » donne un « A » chiffré. La 4e lettre du message en clair est un « A » qui se transforme en « P ». Finalement, la 21e lettre du crible est un « P », il se transforme en « T » et nous voilà donc avec une boucle car elle commence et se termine avec la même lettre.

A T T A Q U E C E S O I R S U R W I K I P E D I A
Y A O P W M K L R B F Z L V C X K T R O T Q A L D

La bombe teste les configurations qui permettent d'obtenir des boucles. Pour chaque possibilité, on cherche si le crible est compatible avec la boucle observée. Si ce n'est pas le cas, on passe à la configuration suivante. Le nombre des possibilités est 26*26*26*60 = 1 054 560. Impossible de calculer à la main mais pas impossible au moyen de la bombe de Turing. Pour calculer ces combinaisons, on ne peut se contenter d'une seule Enigma. Chaque bombe simule plusieurs Enigma montées en parallèle.

Cette première attaque part du principe que la lettre « T » n'est pas modifiée par le Steckerboard, tableau de permutations qui se limitait à 6 substitutions au début de l'utilisation d'Enigma. Les versions ultérieures de la bombe font appel à divers palliatifs de ce problème grâce à des optimisations mécaniques et algorithmiques astucieuses.

Le chiffreur prend 3 rotors et les dispose sur leur position initiale, conformément aux instructions du jour, par exemple I/IV/II "CHD". Ensuite, il frappe deux fois la clef du message, une suite de trois lettres choisies par lui, ex. "MARMAR". Ainsi, le 1er et 4e caractère une fois chiffré ne peuvent pas être ceux qu'il avait frappé, idem pour les 2 et 5èmes et les 3 et 6èmes, ce qui réduit les combinaisons possibles à 24*24*24*60 = 829 440.

Interceptions de messages[modifier | modifier le code]

Messages de test[modifier | modifier le code]

Surmenés, les opérateurs allemands aident involontairement les cryptanalystes. Il est arrivé une fois par exemple qu'un opérateur effectue un test en envoyant un message comprenant uniquement des T. Lisant ce message chiffré sans une seule occurrence de la lettre T, les cryptologues alliés déduisent qu'il s'agit d'un message composé uniquement de cette lettre, ce qui permet de reconstituer le réglage.

Cillies[modifier | modifier le code]

Certains chiffreurs Enigma utilisent toujours plus ou moins la même clef, par exemple les initiales d'un proche. Les Britanniques utilisent le terme « cillies » pour qualifier ces imprudences (à cause d'un chiffreur qui utilisait systématiquement les initiales C.I.L.), néologisme comparable à « silly », stupide en anglais.

Herivel Tips[modifier | modifier le code]

Certains chiffreurs de la Luftwaffe ne respectent pas toujours les instructions du jour, ils laissent les rotors sur la position initiale de la veille, à quelques lettres près. Quand les chiffreurs négligents sont nombreux, les combinaisons possibles de trois lettres descendent à une soixantaine, le premier jour. Une trentaine le second jour, etc. C'est le "Herivel Tip (tuyau d'Herivel)", du nom du cryptanalyste anglais qui avait prévu cette faute.

Banburismes[modifier | modifier le code]

Inspiré de la méthode polonaise de l'horloge, le Banburisme exploite une faiblesse du réglage de l'indicateur (clef du message) de l'Enigma navale. La position initiale des rotors est combinée à partir de listes valables 24 heures. Donc, tous les indicateurs de la journée, puisqu'ils sont tous chiffrés à partir du même réglage des rotors, sont réciproquement « en profondeur ». Normalement, deux messages n'emploient jamais le même indicateur, mais il peut arriver que, dans le cours d'un message, la position des rotors devienne identique à la position de départ des rotors d'un autre message. Les extraits des deux messages qui se chevauchent ainsi sont alors « en profondeur ».

Le principe du Banburisme est simple, il ressemble à l'attaque par indice de coïncidence. Si deux phases sont épelées l'une au-dessus de l'autre, on compte combien de fois une lettre d'un message est la même que la lettre correspondante de l'autre ; il y aura davantage d'appariements que si les phrases n'étaient que des séries aléatoires de lettres. Dans une séquence aléatoire, le taux attendu de répétition de lettres isolées est de 1 pour 26. Dans les messages de l'Enigma navale, le taux est de 1 pour 17. Si les deux messages sont en profondeur, alors les appariements se produisent exactement comme ils le faisaient dans le texte clair. Cependant, si les messages n'étaient pas en profondeur, alors les deux textes chiffrés sont comparés comme s'ils étaient aléatoires, leur taux de répétition est alors d'environ 1 pour 6. Ce qui permet au décrypteur de prendre deux messages dont les indicateurs ne diffèrent que par leur troisième lettre et de les faire glisser l'un contre l'autre, en cherchant la révélatrice constante de répétition qui montre qu'ils sont alignés en profondeur.

Il est plus facile de comparer les deux messages une fois transcrits sur des bandes de carton perforé de 25 cm de large sur plusieurs mètres de long, en fonction de la longueur du message. Au sommet de la colonne d'une carte, un trou représente le A dans cette position, un autre trou à la base représente le Z. Les deux cartons sont superposés au-dessus d'un panneau lumineux. Quand la lumière passe, c'est qu'il y a répétition. La procédé simplifie la détection et le décompte des répétitions. Imprimées à Banbury, les cartes sont baptisées « Banburies » par les cryptanalystes, et la procédure « Banburismus ».

Cribs[modifier | modifier le code]

Dans le parler des écoliers anglais, les cribs (antisèches) sont ces traductions disponibles dans le commerce qui permettent d'adoucir la corvée des versions et des thèmes. Les météorologues en mer rédigent des messages qu'ils envoient en Allemagne, après chiffrage par Enigma. Ces messages font alors l'objet d'une diffusion générale dans toute la Kriegsmarine, souvent à l'aide de codes mineurs. Les messages météo chiffrés par Enigma sont transmis aux U-Boot dans le format rigoureux propre aux sous-mariniers. Or la météo allemande a été décodée par les Alliés qui sont alors en mesure d'essayer des cribs.

Capture de documents[modifier | modifier le code]

Les Alliés mettent sur pied plusieurs opérations afin de capturer des documents de la Kriegsmarine, telle l'opération Claymore (raid sur les iles Lofoten), ou encore l'arraisonnement de navires météo allemands en Atlantique-Nord. Des équipes de prise britanniques et américaines sont descendues dans les entrailles de sous-marins allemands en perdition, grenadés par les Alliés, sabordés et abandonnés par leur équipage, afin de fouiller le poste de commandement et le local radio. D'autres opérations restent sagement au stade de projet, comme la rocambolesque opération Sans-Pitié imaginée par Ian Fleming, favori du directeur du Naval Intelligence, visiteur régulier de Bletchley Park, et futur père de James Bond.

Yoxallisme[modifier | modifier le code]

Le Yoxallisme est un truc imaginé par Leslie Yoxall, 26 ans, qui aide à lire les messages des U-Boot quand ils sont chiffrés deux fois. Ces messages « officiers » ne sont décryptés que rarement, et toujours par hasard. Il arrive que les gens de BP reconstituent l'ordre des rotors, mais pas les permutations des fiches du tableau de connexions. Grâce à Yoxall, on peut reconstituter l'enfichage.

Codage avant chiffrement[modifier | modifier le code]

La Kriegsmarine utilise pour ses transmissions des manuels de messages courts qui permettent de résumer les ordres et les compte-rendus les plus détaillés en quelques lettres incompréhensibles à qui n'a pas les bons documents. L'ajout d'un quatrième rotor à l'Enigma navale ne change pas grand chose. Les très courts messages des sous-marins ne mettent en œuvre que les premiers rotors. D'autre part, il aurait fallu que les messages chiffrés à quatre rotors puissent être décryptés au moyen de machines à trois rotors et que tous les navires et unités soient en possession des mêmes machines. Si le trafic des U-Boot est illisible du 1er février 1942 à la mi-1943, c'est que les messages sont d'abord codés avant d'être deux fois chiffrés, les alphabets et les nombres manipulés, les consignes données de bouche à oreille juste avant l'appareillage, etc.

Messages illisibles[modifier | modifier le code]

La plupart du temps, les messages des U-Boot restent illisibles après décryptage, tant ils se réfèrent à des documents inconnus des briseurs de code. Exemple de message de U-boot une fois déchiffré  : « CKSA KBXO MBGV QQYY OJ ». Sans les bons manuels, comment deviner le sens (« Convoi en vue, carré BE4131, route au Sud, signé U-276 ») ? Seule la radiogoniométrie permet de localiser les submersibles.

Indice de coïncidence[modifier | modifier le code]

Une autre méthode, plus adaptée aux moyens modernes, consiste à essayer toutes les possibilités et à calculer l'indice de coïncidence du texte déchiffré. Un message proche au contenu aléatoire aura un indice proche de 0,0385 (1/26) alors qu'il se montera aux environs de 0,075 pour du français. L'indice varie selon la langue mais il est invariant aux substitutions monoalphabétiques. Dans le cas d'Enigma, on peut essayer toutes les combinaisons des rotors et regarder l'indice obtenu. Soit un message intercepté chiffré par une Enigma comme celle utilisée par la Heer (armée de terre) et la Luftwaffe (3 rotors) :

RFCNT RAONM CVIJZ CBRWS XOTJG SMOMX DUWFW LBYBK BPOFY AOEQW PHNLJ MXMYM JDVPI TOHOC MUIYW WYQRZ LTBEI HUDJE Y

Maintenant, essayons toutes les configurations des rotors et calculons l'indice de coïncidence après déchiffrement, voici un extrait des résultats :

Rotors Message IC
ONS GKNQC CJIBD GYEFO ZQCBH OWJVU AYYLR IXJTC URIEA LVCLS KIVVR GQFEQ DBTMU GIAAY FXVRH RRBPO TQEFF XNQBV ZFMGZ J 0.03909
ONT DWRIE GMZSA RQVWC NEGNJ GLFAQ PDANF RAZVG DOKHW NUEPO USNUZ KOXCV VLYPX SHOWP BJYKV QDCLT CVKLO JGEKS EKYPM O 0.03492
ONU ATTAQ UECES OIRSU RWIKI PEDIA ILFAU TECRI REPLU SDART ICLES ETSUR TOUTT ERMIN ERCET ARTIC LEDEC RYPTA NALYS E 0.07473
ONV CLRHE MPTBX LPUVM FOGOE DBNKW FNNWN PGGPN QHXNE AFYWF LFQHM IPGSU YSXNF MUEMM AKWVL AAYQL ZNVWN NNKHF WGRMY K 0.04591

Au vu des résultats et en présence d'un indice proche de 0,074, on peut en conclure que la configuration « ONU » est probablement la bonne alors que les autres ont un indice largement inférieur et proche d'une distribution uniforme. Pour plus d'assurance, on pourrait procéder à une analyse de la fréquence des lettres dans le message. On se rendrait compte que le message « ONU » contient un grand nombre de 'E' et de 'A' et qu'il est probablement en français.

Le message est de ce fait « ATTAQ UECES OIRSU RWIKI PEDIA ILFAU TECRI REPLU SDART ICLES ETSUR TOUTT ERMIN ERCET ARTIC LEDEC RYPTA NALYS E », que l'on transforme en « attaque ce soir sur Wikipédia il faut écrire plus d'articles et surtout terminer cet article de cryptanalyse ».

Conclusion[modifier | modifier le code]

Une fois découverte la clef quotidienne d'un réseau, c'est-à-dire, dès qu'une vingtaine de mots allemands lisibles ont été alignés au moyen d'une clef, les cryptanalystes passent la main aux décrypteurs qui, en principe, sont alors en mesure de déchiffrer tout le trafic que ce réseau a émis à l'aide de cette clef, ce jour-là. Truffés de jargon militaire allemand, de termes et abréviations techniques inconnus, les messages déchiffrés sont livrés aux traducteurs et aux conseillers…

Les quelques techniques sommairement évoquées ici ne rendent pas compte de l'extraordinaire complexité du problème. Le GC&CS a toujours eu les plus grandes difficultés à accomplir sa mission. Les périodes de trous noirs ont été nombreuses. Les messages ne sont souvent décryptés que trop longtemps après leur réception. En particulier, l'Enigma navale a donné beaucoup de fil à retordre.

Lorsque la capacité combinée des centaines de bombes électromécaniques anglo-saxonnes permet enfin de lire Enigma presque sans trous ni délais, la Wehrmacht est déjà brisée par l'Armée rouge et surclassée par la puissance industrielle et militaire des Alliés.

Articles connexes[modifier | modifier le code]