Cryptanalyse d'Enigma

Image manquante
Key-crypto-sideways.png

Cet article est une ébauche concernant la cryptologie, vous pouvez partager vos connaissances en le modifiant.

La cryptanalyse d'Enigma a été élaborée par le mathématicien polonais Marian Rejewski et ceci avant le début de la Seconde Guerre mondiale. 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 une 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.

Sommaire

1 Les pionniers

2 La persévérance de la Pologne

3 Trouver les bonnes chaînes

4 L'invasion allemande

5 Bletchley Park

6 Attaque par l'indice de coïncidence

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 même impossible à casser. Dès 1926, plusieurs pays tentent de percer les mystères d'Enigma. Mais les mathématiciens américains, anglais 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.

La persévérance de la Pologne

Les Polonais commencent à travailler sur Enigma dès 1928, avec l'appui de l'espionnage. En 1929, ils interceptent une machine Enigma envoyée de Berlin vers Varsovie. Elle devait normalement être transportée dans une valise diplomatique mais une erreur lors de l'envoi permit aux services polonais d'en examiner le contenu. Même s'il ne s'agissait que d'une version commerciale à priori assez anodine, cela permettait de confirmer que les Allemands utilisaient massivement Enigma pour chiffrer leurs messages. Lorsque toute l'armée allemande se mit à l'utiliser des années plus tard, les Polonais portèrent leur soupçon sur des variantes d'Enigma. Débute alors une cryptanalyse intensive dans le but de trouver le cablâge 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 voulait dire qu'il y avait un lien étroit entre ces correspondances, la rotation des rotors et le cablâge interne de la machine. Même si les trois lettres originales étaient inconnues, on savait que le nombre de cablâges qui pouvaient transformer ces trois lettres en une séquence particulière était limité. Rejewski les appelle des « chaînes ».

Trouver les bonnes chaînes

Les Polonais s'étaient spécialisés dans l'exploitation des failles cryptographiques introduites par les Allemands. Les 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 faisait appel à des feuilles transparentes, avec les schémas des rotors. Les feuilles étaient superposées et les lettres composants une chaîne impossible étaient rayées. À la fin de l'opération, les trois lettres restantes donnaient le code utilisé pour l'entête. On apprit par la suite que les Britanniques avaient développés le même genre de technique basée sur une grille, elle avait fait ses preuves sur l'Enigma commerciale mais n'était pas adaptée pour le cassage de la version militaire. Une variante de cette méthode consistait à utiliser des cartes perforées. À la fin, un alignement complet des trous indiquait le code à trois lettres.

Image manquante
Bombe-wh.700px.jpg

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 guerre. Chaque bombe 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 d'Espagne et ceci jusqu'à l'aube de la Deuxième 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.

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és 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 Anglais, devenus leurs alliés (milieu de 1939). Durant l'été 1939, ils fournissent à la France et à l'Angleterre 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étruise 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 janvier 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 la Grande-Bretagne. 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.

Bletchley Park

Rejewski et Zygalski ne seront 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éressait plus particulièrement au réflécteur, un élément qui garantissait que toute lettre était nécessairement différente après chiffrement. De plus, les Anglais firent 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 assaults 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, prennons la phrase suivante que l'on suppose présente dans le message originale : « 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ème 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 Anglais vont introduire une parallélisation astucieuse de la machine Enigma.

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

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"