|
My crypto Home Page Enigma Cryptanalysis home Page
|
IntroductionSince the Anschluss (March 1938), the English had begun to seriously worry about the rise of Nazi Germany. It was at this time that the English approached the French to exchange information about the Enigma. The french Captain Bertrand, with the agreement of his superiors, provided a huge amount of data to the English. This information came mainly from the spy Hans Thilo Schmidt. The English also shared their knowledge with the French, notably the rodding method for finding the key to a message encrypted with the commercial Enigma. The French called this method "La méthode des batons". Bertrand felt somewhat helpless against the English, as neither he nor the French army cryptologists had any knowledge of cryptanalysis of cipher machines, particularly the Enigma. Bertrand then called upon the only French cipher machine specialist, Captain Henri Braquenié of the Air Force. Braquenié notably wrote a report describing how to find the message key from a cryptogram and a probable word (a crib). Knowledge of rotor wiring was a prerequisite. This webpage will describe Braquenié's method. Braquenié's own description of the methodIn Captain Bertrand's archives, we find a typed description of Braquenié's method, undoubtedly originating from Braquenié himself. Bertrand's archives are currently located at the SHD in Vincennes, near Paris. In the Reference section, I provide a link to download the original document. In the following section, I provide an English translation of this document. I believe that before the war, Bertrand transmitted Braquenié's method to the British. This was one of the elements included in the numerous exchanges between the French and the British. It seems that the British did not use the Braquenié's method, but continued to use their Rodding method. Mavis Batey is clear on this point (see her book cited in the References section). Braquenié's method (verbatim)
InformationSource: Air Force Method for decrypting ciphertexts with the commercial ENIGMA machine
PROBABLY WORD METHODThe decryption of the "ENIGMA" machine is based on the following observation: If we encrypt a word of about ten letters, we can practically consider the two left-hand rotors as forming a moving whole. We will therefore study, on the one hand, the two left-hand rotors, and on the other, the two right-hand rotors. The rotors can occupy 26 positions relative to each other. We have limited ourselves to studying the case where the rotors are located in the order IV, III, II, I, from left to right. Preparatory work:All the rings are set at A. This setting has no effect on the current flow. 1°/ Synthesis Study IV IIIWe have 26 possible positions of rotor III relative to rotor IV. In each of these 26 positions, we recorded the current inputs and outputs. The results are entered in Table I in the form of a bigram followed by a number indicating the offset between the two letters. Given the reciprocity of the machine, we have only 13 circuits for a timing of the two rotors, and the offset between two letters cannot be greater than 13.
2°/ - Study of System I IIWe will only focus on the letter E, which we will assume to be coded successively by A B C .... That is, 26 tables, each containing 676 possible combinations of rotors I II. We will represent opposite each of the 676 input and output keys of the current on the outer face of rotor II with a bigram and a number indicating the offset. These tables can be composed by a secretary very quickly by observing that the horizontal sequence of letters reproduces the random alphabet output from rotor II; it is sufficient to give the bigrams from the first column. Equivalences in I II. -We will demonstrate that any letter in the plaintext encrypted by any letter in any key can always be reduced to the case of E encrypted by a letter and in a suitably chosen key. Let's consider the ring of fixed pins directly connected to the keyboard: These pins are in the following order: Q W E R T Z U ..... I II If E was encrypted by T in the key .... G F W will be encrypted by R in the key .... H G Q will be encrypted by E in the key .... I H : : : : : : Indeed, by shifting the set of rotors I II by one step, we have not changed the internal connections of these two rotors. We have brought the system of connections that gave us E: T opposite W R. Rule.If a letter of rank N is encrypted by a letter of rank N + X in a key of the form CC, the letter of rank N + Y will be encrypted by the letter N + X - Y in a key of the form C + Y - C + Y. The two attached key letter equivalence tables allow you to solve the problem very quickly. This rule applies to the four-key rotor system. DECRYPTION -Given a probable word and its ciphertext, we will search for the key used for encryption. As soon as we find this key, the rest of the ciphertext will be encrypted normally. Length of the probable word.-A word of 5 to 10 letters is sufficient. Any shorter, and the decryption difficulties increase very rapidly. We will demonstrate the method using a concrete case. Consider the following text with the probable word INTELLIGENCE inserted:
K I Q L F A W E L L K S R F J D R I R C F K D R O J R Y J F V P I
I N T E L L I G E N C E
S O G H P W I I S B H I Z C W N
We will first look for the equivalence of the letters and keys in relation to E, taking AA as the first key for I: R. To do this, we will refer to the two equivalence tables and obtain (for 9 letters):
Plain: I:R N:F T:J E:D L:R L:I I:R G:C E:F
and
KEY : AA BA CA DA EA FA GA HA IA
EQUIVALENCE: E:M E:P E:G E:D E:U E:S E:M E:A E:F
FF WV EC DA BX CX LF SL AI
...
... I II: :I II A A: SA8 CV7 TU1 QI8 IC6 EZ11 YJ11 FJ4 JF4 :J A B A: GD3 KR7 NY11 GL5 KU10 FY7 OQ2 SD11 LU9 :KA A C A: EO10 JV12 SR1 PM3 FJ4 SO4 NV8 MQ4 HA7 :L A D A: WB5 HK3 QJ7 DP12 SQ2 AN13 KE13 UR3 ED1 :M A E A: FC3 LC9 OV7 XW1 AV5 PR2 YW2 AL11 TY5 :N A F A: ZU5 EI4 GP9 JH2 PE11 BY3 QF11 OP1 AQ10:O A G A: YJ11 AE4 W4II 4B10 BW5 TQ3 XN11 DN7 ON1 :P A H A: OQ2 BT8 IK2 MD4 TF12 DX6 5HII 4Z12 ES12:Q A I A: NV8 DU9 XE7 EY6 DM9 JS9 KW12 UY4 BZ2 :R A J A: RE13 ZA1 KS8 TN6 JH2 QKS WT3 VS3 VL10:S A K A: YW2 MD9 EG2 AZ1 QW6 VW1 MG6 JM3 PX8 :T A L A: QF11 VY3 IM4 OJ5 JT2 KM5 EC2 KG4 RM5 :U A M A: XM11 GQ10 FB4 EC2 RG11 K27 BZ2 IB7 JW13:V A N A: SH11 CN11 BO13 BU7 XC5 QB11 AQ10 FN3 IT11:WA A O A: KW12 FS13 NC11 VR4 QZ9 LA11 PR2 QO2 XJ12:X A P A: WI3 XZ2 YZ1 PS3 LQ5 UP5 HJ2 AV5 UY4 :Y A Q A: MG6 SL4 OJ5 RF12 UR3 AH7 CS10 MB11 VUA :Z A R A: EC2 WX1 ZH8 JA9 AJ9 EC2 VI13 EC2 ZH8::A B S A: BZ2 TM7 QK6 IE4 ES12 TV2 IY10 CK8: XC5 :B B T A: AQ10 XW1 LP4 XB4 TI11 IH1 JX12:DI5 AN13:C B U A: PR2 UT1 RI9 UX3 HY9 BJ8: LM1 YJ11 DZ4 :D B V A: HJ2 NJ4 AD3 WZ3 BX8: N42 BU7 BL10 OG8 :E B W A: CS10 ZY1 JU11 ZY1: NMI HB6 WH11 CX5 BP12:F B X A: VI13 OM12 MA13:XH10 HU13 IW12 IT11 DS11 CN11:G B Y A: IY10 GH11:SF13 AP11 IH1 BI7 XN10 ZA1 UR3 :H B Z A: JX12:OC12 ED1 DC1 BT9 RX6 YS6 IF3 JW13:I B Examination of the table:Up to and including key R A, rotors III and II have not moved relative to each other. Examining the first horizontal line, we find VC7 and IC6. These two bigrams are incompatible. C cannot be linked to both Y and I. Key AA must be rejected. We find similar incompatibilities in all other keys except for R A. For keys starting with R A, rotors II for certain letters of the word has been shifted one step relative to rotor I. On either side of the stepped line, the incompatibilities are no longer between letters of the same rank, but between letters of rank N and N = I. Examples: In line X A: M A I3 and C N II are incompatible. We have only studied keys of form A for II. We would now need to establish tables for keys of form B C D .... but R is certainly the key letter of rotor I. .... Indeed, in the sequence of keys in rotor II, the bigrams will undergo a circular permutation in each vertical line, and we will find the same incompatibilities on the same horizontal lines. Example: We eliminated key I II / A A by comparing V C and I C. In key A B, these bigrams have become G N and R N by circular permutation. We are therefore indeed faced with the same incompatibility. We therefore simply need to study the 26 combinations of rotor II with R from rotor I. We obtain them by subjecting the bigrams in line R A to a circular permutation. This is the purpose of the table below: I II R A EC02 WX01 ZH08 JA09 AJ09 EC02 VI13 EC02 ZH08 R B WN09 IJ01 YE06 QM04 " " GR11 " " R C ID05 RQ01 AW04 OK04 " " BZ02 " " R D RU03 ZO11 M14 HP08 " " TY05 " " " " " " " " " " " " "3°/ - Delete the keys that are impossible due to incompatibilities. Only one key should remain that gives us the right-hand letter of the real key. 4°/ - There are 26 possible keys left to establish the 26 lines of bigrams. 5°/ - Compare the numbers obtained on each line with the numbers at the bottom of table I. When these numbers appear in a rotor alignment, III and IV, verify that if a bigram of rotor II is aligned with a bigram of the same difference from rotor II, all the other bigrams are aligned with bigrams of rotor III having the same difference. .... Probable Word AlignmentWe know that a letter cannot be encrypted by itself, so we can already eliminate sequences that exhibit this characteristic. For the rest, we must successively align the probable word under each letter of the cipher and establish the 1°/ 2°/ 3°/ indicated above. If the probable word is long enough (8 to 10 letters), we will find incompatibilities on each line until we are within the exact alignment. Comments on the Braquenié's MethodIntroductionBraquenié's method allows one to find the key to a message encrypted with the commercial Enigma. Prerequisites include a crib and the rotors wiring. The method boils down to exploring a set of pre-calculated tables (see the following paragraphs). From these tables values related to the crib are extracted and any contradictions are checked. Two types of pre-calculated tables are used. The first ones are related to the two fast rotors (the right and middle ones). The second ones are related to the two slow rotors (the reflector and the left rotor). Each set of tables are treated separately. The left rotors are considered stationary during the crib encryption. Regarding the two fast rotors, the encryption of any letter is reduced to the encryption of the letter E to reduce the number of tables. The example providedBraquenié provides an example. He takes a cryptogram and assumes that the INTELLIGENCE crib is present. For each crib position, he checks for incompatibilities. A plausible position contains no contradictions. The longer the crib, the fewer plausible positions there are. For each pair cipher letter / plain letter (from the crib), he looks for the value in the tables indicating the incoming/outgoing current of the middle rotor at the interface with the left rotor. The tables give this interface to the left rotor for each relative position of the two right rotors (AA, AB,..., BA, BB,..., ZZ). Thus, assuming the first letter of the crib is encrypted with the AA key (right rotor I at A, middle rotor II at A):
Crib /crypto. I:R N:F T:J E:D L:R ... key (I,II) AA BA CA DA EA Value SA8 CV7 TU1 QI8 IC6 Since the left rotor and the reflector are supposed to remain stationary during crib encryption, the AA key is incorrect. Indeed, the CV and IC pairs are incompatible: if the current enters the left rotor through position C, it cannot exit once through V and again through I. The next key, BA, must be tried, and so on. Note: The number after a pair indicates the distance between the two letters in the alphabet: TU are 1 position apart, IC are 6 positions apart. The difference cannot be greater than 13. To reduce the number of tables, we transform each plain letter/cipher letter pair into an equivalent pair whose plain letter is the letter E. For example, I/R is transformed into E/M. Of course, the relative position of the rotors is no longer the same. Thus, if the key for the right rotors for the first I/R pair is assumed to be AA, the equivalent E/M pair will be FF. Once we have obtained the key for the right rotor and middle rotor assembly, we can search for the relative position of the left rotor and the reflector compatible with the input and output positions of the left rotor. The search is quick because we know the left rotor.
Once we have the key, we can decipher the cryptogram. If the method fails, we test the next position of the crib relative to the cryptogram. Then, if that fails, we move on to another pair of rotors (right rotor and middle rotor). The example given and my key finding softwareI wrote a program (scan_eD.py) that searches for the message key using a Crib. It calculates the plain text for each position of the rotors and print these positions if th plain-text found is equal (or close to) the crib. Using my program, I was able to find the message key corresponding to the INTELLIGENCE crib. I was then able to decrypt the whole message: LAMEMOIREETLINTELLIGENCESONTDEUXFACULTESDELESPRIT. In English : "MEMORY AND INTELLIGENCE ARE TWO FACULTIES OF THE MIND". $ cat /tmp/crypt RFJDRIRCGKDR $ cat /tmp/clair INTELLIGENCE $ pypy3 scan_eD.py -c /tmp/clair -W D-III,D-II,D-I -R AAAA -G AAAA:ZZZZ \ -E D-ETW -M PLN -m /tmp/crypt >> D-III,D-II,D-I D-UKW AAAA AAAA : 0.0833 - DGVFKOVIMFDI 1 0 mn 0 sec >> D-III,D-II,D-I D-UKW AAAA AACC : 0.2500 - PBVCZNFCDKQR 55 0 mn 0 sec >> D-III,D-II,D-I D-UKW AAAA AAJQ : 0.4167 - RGXDRINCUENI 251 0 mn 0 sec >> D-III,D-II,D-I D-UKW AAAA AEBQ : 0.5000 - RVJDRISCFYAC 2747 0 mn 0 sec >> D-III,D-II,D-I D-UKW AAAA FYXQ : 0.5833 - RZSDRIRCLIWR 104719 0 mn 1 sec >> D-III,D-II,D-I D-UKW AAAA UHBQ : 1.0000 - RFJDRIRCGKDR 356295 0 mn 3 sec $ echo KIQLFAWELLKSRFJDRIRCFKDROJRYJFVPISOGHPWIISBHIZCWN | python3 eD.py \ D-UKW D-III D-II D-I D-ETW AAAA UHBE LAMEMOIREETLINTELLIGZNCESONTDEUXFACULTESDELESPUIT $ Attempt at Partial Reconstruction of the TablesI attempted to reconstruct a small portion of the tables to better understand Braquenié's method. I used my commercial Enigma simulator (eD.py), which provided me with details of the encryption. For example, if we encrypt the letter I with the external key BJAA using the internal key IV-III-II-I and a Ringstellung of AAAA, we obtain the letter R, but we also obtain the intermediate steps: ETW transforms I into H, rotor I transforms H into A, rotor II transforms A into S, rotor III transforms S into A, the reflector (UKW or IV) transforms A into L, rotor III (inverted) transforms L into A, rotor II (inverted) transforms A into S, rotor I (inverted) transforms S into D, and ETW (inverted) transforms D into R. $ python3 eD.py syntax: enigmaD.py UKW LEFT MIDDLE RIGHT ETW RING GRUND [Debug] $ echo I | python3 eD.py D-UKW D-III D-II D-I D-ETW AAAA BJAZ D [0001] = B J A A = I -> H: A S A < L > A S D -> R R Tables for right rotors (right and middle rotors)Braquenié tables allow us to associate a ciphertext/plaintext pair with a pair corresponding to the inputs and outputs of the middle rotor (here, rotor II) interfacing with the left rotor (here, rotor III). In our example: I/R => SA. Note: we omitted the distance between the two letters, which is 18 here. Since we cannot exceed 13, we have a distance of 8 (26-18=8), and therefore the pair I/R => SA8. For the AA key and beyond, I obtain the following pairs (the message key is indicated in parentheses): SA (BJAA), CV (BZAB), TU (BPAC), QI (AEAD), IC (ARAE), … Here are the Braquenié data: SA (AA), CV (AB), TU (AC), QI (AD), IC (AE). The beginnings of the keys (left reflector and rotor) are not consecutive. This is normal, because the key is incorrect! Following this success, I wanted to reconstruct the table values for the right rotors in the case where the key is correct and therefore corresponds to the solution. Here are my results: $ echo INTELLIGENCE | python3 eD.py D-UKW D-III D-II D-I D-ETW AAAA UHBQ D [0001] = U H B R = I -> H : M V Z < J > M W D -> R [0002] = U H B S = N -> X : N H Q < Y > I H M -> F [0003] = U H B T = T -> E : Q X I < K > D L P -> J [0004] = U H B U = E -> C : I P O < G > L S L -> D [0005] = U H B V = L -> Z : S L G < O > P I D -> R [0006] = U H B W = L -> Z : M V Z < J > M W H -> I [0007] = U H B X = I -> H : C F P < E > Q O D -> R [0008] = U H B Y = G -> N : M V Z < J > M W U -> C [0009] = U H C Z = E -> C : Q Y L < M > B W N -> G [0010] = U H C A = N -> X : J F P < E > Q Y Q -> K [0011] = U H C B = C -> U : H O U < D > A U L -> D [0012] = U H C C = E -> C : X S X < N > C K D -> R RFJDRIRCGKDR
In summary:
Unfortunately, when I inspect Braquenié's results, they are different: Analyzing both approaches (mine and Braquenié's), I see that there is a difference of one position (for each rotor) each time: VN + 1 = WM, HI + 1 = IJ, XD + 1 = YE, PL + 1 = QM, … For the moment, I don't understand this discrepancy… Could it be due to a difference in the rotor wiring used by Braquenié and the ones I used (Twist effect, ...)? If any readers have any ideas…
Tables for left rotors (reflector and left rotor)How do I determine the relative key of the left rotor relative to the reflector? I think Braquenié uses the following table (for rotors IV-III): AA 1-2-4(2)-5(3)-6-8-10-13(3) AB 4-5(2)-6(3)-7-8-9-10(2)-11-13 AC 2-3-6-7(5)-8-9(2)-12-13 AD 2-3(2)-4-5(2)-6-7(2)-8-9-10-12 AE 1-3-4(3)-5-6-7-8(3)-9-10 AF 2-3(2)-4-5-6-7-8(2)-9-10(2)-12 AG 1-2(2)-4(2)-5-6-7(2)-8-9-10-12 AH 2(2)-3(3)-4(3)-5-7-9(2)-10 AI 2(2)-3(2)-5-6-8(2)-9(3)-10-11 AJ 1-2-4(2)-5-8-9-10(2)-11-12-13(2) AK 2-4-9-10(2)-11(7)-13 AL 2-5(3)-7-8-9(2)-10-11(2)-12-13 AM 1(2)-3-4-5(2)-7-10(3)-11(2)-13 AN 1(2)-3-4-5-6-7-8-9-10-11-12(2) AO 1-2-3(3)-4(2)-7(2)-8-11-12(2) AP 1-2(3)-4(2)-7(2)-8-11-12(2) AQ 1(2)-2-4-7(4)-8-10(3)-13 AR 2(3)-3-5-6(3)-7(3)-10-12 AS 1-2(3)-3(2)-5(2)-6-7-9-11-12 AT 2(2)-3-4(3)-6(3)-7-10-13(2) AU 2(4)-4-5-6-8(2)-9(2)-10-12 AV 1-3(3)-4-5-6-7-9(2)-10-11(2) AW 1-4-5(3)-6-8(2)-9-10(2)-11-13 AX 1-2-3-4-5(2)-6(2)-8(2)-9-10-12 AY 3-4-5-6(3)-7-9(2)-11(4) AZ 1(2)-2-3-5-6-7-8-9(2)-10(2)-12In this table, for example, for key AB, we have the following offsets: 4-5-5-6-6-6-7... This means that (for the first difference), if the current from the middle rotor enters the left rotor through one terminal, it exits through another terminal 4 positions away (example A, A+4=E). We note that for a given offset between the reflector and the left rotor (AB means that the left rotor is offset by one position relative to the reflector), not all current inputs/outputs are possible. Thus, for key AB, the pairs x+1, y+2, z+3 are not possible (a priori, we do not need to know x, y, and z). Example: Key RB corresponds to the key for the right rotors. We have the following pairs: WN09 IJ01 YE06 QM04 … GR11. Up to now we have not used the differences 9,1,6,4,…,11 These differences correspond precisely to the differences listed in the previous table. Thus the difference of 1 eliminates the keys AB, AC, AD, AF, … The difference of 4 eliminates the key AC. The difference of 11 eliminates AD and AF. In short, only the keys AN, AV, AW remain. The relative key AN is compatible with the key UH (the real solution) for which the two left rotors are spaced 13 positions apart. Efficiency of the methodBuilding cipher tables is slow, but this preliminary work only needs to be done once. Then, a 5-letter crib is often sufficient. From 8 letters, there are very few solutions to test (a bit like the stops of a Bombe). With a crib of 10 letters, you definitely get the complete key. The Braquenié Method versus the Rodding MethodThe Braquenié method is much more efficient than Dilly Knox's Rodding method. Not only is it faster, but it also requires a small crib. However, it requires knowledge of the wiring of all the rotors likely to be used (at least the two right rotors). Conversely, the Rodding method has the great advantage of being able to be used with only knowledge of the fast rotor (the rotor on the right). It can therefore be used as a preliminary to finding new wiring. ReferencesBooks and articles
Internet links |