Cryptanalyse d'Enigma

Un article de Wikipédia, l'encyclopédie libre.

La cryptanalyse d'Enigma, c'est-à-dire le déchiffrement des messages transmis et codés par Enigma, fut fondamentale au succès des Alliés pendant la Seconde Guerre mondiale.

Le mathématicien polonais Marian Rejewski a élaboré la première cryptanalyse, ceci avant le début de la guerre. Elle profitait d'une certaine redondance au début des messages : un code choisi par l'opérateur de la machine était doublé et chiffré pour être ensuite utilisé comme entête. Durant la guerre, les Britanniques améliorent la cryptanalyse de la machine grâce au travail d'Alan Turing et les nombreux collaborateurs de Bletchley Park.

[modifier] Les pionniers

Les premières versions commerciales d'Enigma remontent au début des années 20. La machine apparaît alors comme très sûre voire 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 dans cette difficile tâche. Pendant ce temps, la marine allemande met en place des versions modifiées d'Enigma pour chiffrer ses transmissions.

[modifier] La persévérance de la Pologne

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 vers Varsovie. Elle devait normalement être transportée par la valise diplomatique, mais une erreur lors de l'envoi 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, cela permet de confirmer que les Allemands utilisent massivement Enigma pour chiffrer leurs messages. Lorsque toute l'armée allemande se met à l'utiliser des années plus tard, les Polonais portent leur soupçon sur des variantes d'Enigma. Débute alors une cryptanalyse intensive dans le but de trouver le câblage utilisé dans la version militaire, et ultérieurement d'extraire les clés pour des messages donnés.

Marian Rejewski, un mathématicien polonais de 27 ans, découvre alors un moyen mathématique pour retrouver ces deux paramètres essentiels. Il s'agit là d'une découverte capitale tant au niveau technique que stratégique. Rejewski remarque une redondance lorsque les opérateurs militaires chiffrent leurs messages. L'opérateur sélectionne en effet un mot très court et le répète une deuxième fois. Cette séquence est chiffrée et placée au début du message. Ces informations proviennent aussi des services d'espionnage qui permettent d'avoir une meilleure idée des procédures en vigueur lors du chiffrement.

Par exemple, l'opérateur pouvait choisir « WIK » comme paramètre et ensuite configurer Enigma selon la clé en vigueur ce jour-là. Il tapait ensuite « WIKWIK » et obtenait un résultat chiffré et, bien entendu, variable selon la clé, disons « AXLQPB ». Rejewski observe alors ceci en comparant les lettres deux par 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é. Rejewski les appelle des « chaînes ».

[modifier] Trouver les bonnes chaînes

Les Polonais s'étaient spécialisés dans l'exploitation des failles cryptographiques introduites par les Allemands. Leurs espions ont pu leur fournir un exemplaire d'un vieux manuel d'Enigma. Celui-ci renfermait un exemple de chiffrement avec un texte en clair, la clé et le résultat une fois chiffré. Rejewski l'étudie alors attentivement.

Le nombre de chaînes possibles se monte à 105 456 et, à 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 pour accélérer les calculs. L'une d'entre elles fait appel à des feuilles transparentes, avec les schémas des rotors. Les feuilles sont superposées et les lettres composants une chaîne dite « impossible » sont rayées. À la fin de l'opération, les trois lettres restantes donnent le code utilisé pour l'entête.

On apprit par la suite que 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 le code à trois lettres.

Bombe cryptographique

Malgré cette performance, la recherche manuelle n'en demeure pas moins très pénible. Les Polonais construisent alors une bombe cryptologique, la bomba kryptologiczna, véritable ordinateur électromécanique qui date de 1938. Six exemplaires sont montés à Varsovie dans le bureau du chiffre juste avant le début de la Seconde Guerre mondiale. Chacune contient l'équivalent de six machines Enigma alimentées électriquement. Son volume est par contre considérable, l'équivalent d'un atelier pour 100 personnes, mais les gains sont significatifs : il suffit de deux heures pour obtenir la clé.

Les Polonais seront ainsi capables de déchiffrer une bonne partie des transmissions de l'armée allemande dès 1933, durant la Guerre civile espagnole et ceci jusqu'à l'aube de la Seconde Guerre mondiale. L'espionnage aura ici représenté un puissant allié dans le cassage du code grâce à des agents disséminés un peu partout. Le plus célèbre, Hans Thilo-Schmidt (nom de code « Asche » qui veut dire « cendre »), est au service des Français et a accès à des manuels et du matériel lié à Enigma.

[modifier] L'invasion allemande

En 1939, les Polonais doivent se rendre à l'évidence : les Allemands ont complexifié la structure de leur machine. Au cours des années 30, les Allemands avaient souvent 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 introduit deux rotors supplémentaires. De plus, le début de la guerre marque l'arrêt de la procédure de répétition du code au début des messages et tous les efforts des Polonais sont réduits à néant puisque leur cryptanalyse repose sur cette redondance. Il est probable que le service cryptographique de l'armée allemande eut vent des progrès polonais ou tout au moins soupçonne ou même découvre une faille dans leur procédé de chiffrement.

Les Polonais partagent alors le résultat de leurs travaux avec la France et les Britanniques, devenus leurs alliés (milieu de 1939). Durant l'été 1939, ils fournissent à la France et au Royaume-Uni des copies d'Enigma, la description précise de l'attaque, la technique de la grille et les plans de la bombe cryptographique. En septembre 1939, l'invasion de la Pologne par les Nazis débute. Les Soviétiques s'introduisent en Pologne par l'est. Face au conflit imminent, les cryptologues polonais évacuent dans l'urgence leur bureau à Varsovie (Biuro Szyfrów) et détruisent le matériel confidentiel durant leur escapade. En passant par la Yougoslavie et l'Italie (neutre en 1939), ils atteignent la France. Près de Paris, au PC Bruno, les Polonais se mettent au service de la France et recommencent à travailler sur Enigma. Peu avant l'invasion de la France en mai 1940, le mathématicien britannique Alan Turing demeure quelques jours au PC Bruno où il sera briefé par ses confrères polonais.

Après l'armistice, les cryptologues se déplacent dans le sud de la France et en Algérie, avec les risques que cela pouvait représenter. Certains officiers supérieurs (le Colonel Gwido Langer et le Major Maksymilian Cięźki) furent capturés et malgré de terribles interrogatoires, le secret au sujet de la cryptanalyse d'Enigma demeura intact. Quant à Marian Rejewski et Henryk Zygalski, c'est une épopée qui les attend. Tout d'abord à travers l'Espagne où ils seront temporairement emprisonnés, le Portugal et finalement Gibraltar d'où ils pourront gagner le Royaume-Uni. Jerzy Róźycki aura beaucoup moins de chance puisqu'il meurt noyé lors d'un naufrage en 1942 au sud de la France, après un voyage en Algérie.

[modifier] Bletchley Park

Bletchley Park

Rejewski et Zygalski ne sont toutefois pas incorporés directement à la section qui s'occupe d'Enigma, ils sont gradés et s'occupent d'autres méthodes de chiffrement utilisées par les Allemands. La cryptanalyse d'Enigma était devenue entre temps une affaire britannique et américaine. Les méthodes polonaises ne fonctionnaient plus sur les versions militaires d'Enigma et la variante d'Enigma pour la marine allemande avait toujours été supérieure en terme de sécurité. Les Polonais ne s'étaient pas vraiment intéressés aux transmissions de la marine, alors que celles-ci étaient capitales pour les forces alliées à cause des nombreuses pertes dans l'Atlantique. C'est Alan Turing qui va s'occuper de l'analyse de l'Enigma navale. Turing est le chef de la huitième section à Bletchley Park, un manoir proche de Londres où se sont retranchés tous les cryptologues et mathématiciens alliés. Avec Gordon Welchman, ils seront à l'origine du déchiffrement complet d'Enigma. Les membres de Bletchley Park travaillent dans le secret le plus total, toute fuite pouvant avoir des conséquences désastreuses sur la suite de la guerre.

Les attaques développées par les Britanniques ressemblent à celles des Polonais. Une nouvelle attaque s'intéresse plus particulièrement au réflecteur, un élément qui garantissait que toute lettre était nécessairement différente après chiffrement. De plus, les Britanniques font appel à des techniques basées sur l'analyse des mots probables. Les messages avaient de forte chance de contenir des termes comme « Heil Hitler », « Panzer », « Führer », « Stuka », etc. Ces estimations du contenu du message étaient appelées des cribles. Les cryptologues pouvaient à posteriori deviner le contenu des messages en fonction de l'actualité et des assauts ennemis. En faisant quelques hypothèses sur le contenu et sachant qu'une lettre est obligatoirement modifiée lors du chiffrement, il n'était pas impossible de retrouver une partie du texte chiffré en essayant tous les alignements possibles. À partir des résultats positifs, on arrivait à retrouver le texte complet. Cette attaque ressemblait à celle des Polonais qui tentaient de deviner l'entête des messages. Turing avait découvert des « clicks », c'est-à-dire des paires de lettres qui apparaissaient plusieurs fois entre le message chiffré et sa version déchiffrée (n'oublions pas qu'il avait des machines Enigma à sa disposition pour tester). Comme Enigma est réversible, une correspondance A->J est équivalente à J->A.

Pour illustrer ce principe d'une manière simplifiée, prenons la phrase suivante que l'on suppose présente dans le message original : « ATTAQUECESOIRSURWIKIPEDIA ». On intercepte le message chiffré : « YAOPWMKLRBFZLVCXKTRORQALD ». Effectuons une première comparaison :

L'attaque de Turing se base sur la recherche de boucles entre le texte en clair et chiffré. La deuxième lettre du message en clair « T » donne un « A » chiffré. La 4ème lettre du message en clair est un « A » qui se transforme en « P ». Finalement, la 21^e 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.

La bombe testait en fait les configurations qui permettaient d'obtenir des boucles. Pour toutes les possibilités, on cherchait si le crible était compatible avec la boucle observée. Si ce n'était pas le cas, on continuait avec la configuration suivante. Le nombre de possibilités se montait à 26*26*26*60 = 1 054 560, impossible à la main mais pas impossible pour la bombe de Turing. Pour calculer ces combinaisons, on ne pouvait se contenter d'une machine. Les Britanniques vont introduire une parallélisation astucieuse de la machine Enigma.

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

[modifier] Interceptions des messages

Les opérateurs allemands aidèrent involontairement les cryptanalystes à maintes occasions. On pouvait demander à un opérateur d'effectuer un test en envoyant un message comprenant uniquement des T. En découvrant un message sans T, on comprenait qu'il s'agissait d'un message de ce type. Certains des opérateurs d'Enigma utilisaient les mêmes paramètres au début des messages, par exemple les initiales d'un proche. Les Britanniques utiliseront le terme de « cillies » d'après un opérateur qui utilisait C.I.L, ce néologisme est à comparer avec « silly » (stupide en anglais).

Un énorme travail devait être fait en amont pour trier les messages et retenir ceux qui étaient intéressants. Avec suffisamment de messages, il était possible de déterminer les paramètres journaliers. D'autres opérateurs ajoutaient une entête constante selon le type de message, par exemple WET (de Wetter, temps météo en allemand) s'il s'agissait d'un rapport météo.

Plus tard dans la guerre, ces bulletins d'informations météorologiques furent une pièce maîtresse de la cryptanalyse : les météorologues en mer rédigaient les messages et les envoyaient en Allemagne à l'aide d'un système de chiffrement moins robuste qu'Enigma (la météo n'étant pas une information véritablement secrète). Une fois arrivés dans les quartiers généraux, ces messages étaient expédiés quasiment sans modifications aux U-Boot, mais cette fois-ci en chiffrant avec Enigma. Les Alliés disposaient de textes clairs qu'ils pouvaient ainsi mettre en rapport avec les textes chiffrés d'Enigma dans le but d'établir des cribles.

Si les Allemands avaient changé les rotors plus souvent, il est possible que les efforts des experts de Bletchley Park soient restés vains. L'envoi de nouveaux rotors demandait une infrastructure qu'il n'était pas possible de déployer durant la guerre. Il fallait entre autres s'assurer que tous les navires et unités étaient en possession des bons rotors. Les Allemands optèrent pour l'ajout de rotors sans modifier les autres, en particulier pour la Kriegsmarine. Ce changement eut pour effet de rendre les communications navales assez sûres de février à octobre 1942, et ce d'autant que les opérateurs des U-boot évitaient les messages-types et autres « cillies ».

Face au danger que cela représentait, et notamment une éventuelle défaite dans la Bataille de l'Atlantique, les Alliés se devaient de réagir, et mirent sur pied plusieurs opérations pour voler les carnets de code allemands. Certaines virent le jour, et furent efficaces, d'autres restèrent au stade de projet, comme l'Opération Sans-Pitié imaginée par Ian Fleming, le futur « père » de James Bond et officier dans le renseignement naval britannique. Ainsi, les cryptanalystes eurent quelques difficultés lors de ces remplacements mais parvinrent rapidement à obtenir les paramètres des machines.

[modifier] Attaque par l'indice de coïncidence

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 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é crypté par une Enigma comme celle utilisée par la Wehrmacht (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 wikipedia il faut ecrire plus d articles et surtout terminer cet article de cryptanalyse"

Machines et dispositifs de chiffrement

Modifier