|
Break an Enigma Key with Bombe
Bombes: |
IntroductionIn order to be able to break a key with a bombe, it has been proven, you need a Crib. But from a practical standpoint, configuring a bombe requires electrical wiring that connects multiple Enigmas. It is an operator who realizes this configuration based on an abstract vision of this wiring and which reflects the association of the Crib and the cryptogram. This abstract vision is a drawing called Menu.
abcde fghij klmno pqrst uvwxy z
Crypto WCGLV EUTCF ZTQSA WJCSR FQOOZ Z
Crib KEINE BESON DEREN VORKO MMISS E
B V U zd zj au av
Input 6\ze| 7/8 L----N----F----M----Q
letter: E zf\ | /zg 12 13 14 15
zb \|/ az ay zh
C-------E-------Z-------S-------T
1 loop \ 1 ^ 5 4 /ax 9
1 aux.chain \ Input letter 3/ aw zc
16 letters \-----------------O-------I-------G
2 10 11
A Menu is designed as a series of segments, each connecting two letters. Thus the first link, C-E corresponds to the encryption of the letter E which gives the letter C. In the flow of the message, this encryption is carried out at the relative position “b” the second letter of the Crib. If we refer to the space of the three rotors, this corresponds to the ZZB position, or simply "zb" if all the letters in the Crib use the same position of the left rotor. Due to the reciprocity of the Enigma, if we cipher C we get E, and vice versa if we cipher E we get C. Thus, a link can be reversed: the C-E link is equivalent to the E-C link. A Menu actually represents an electrical circuit and which if possible contains loops. In the example above, the current is introduced at the letter E of the first link. Then, it goes through the letter C, then via the second link, we go through the letter O, then, through the third link, we end up with the letter S, then by the fourth link, we end up with the letter Z. Finally by the following link (the fifth) we return to the letter E: we have closed a loop (closure). We note that several links do not belong to loops (this is the case of links 6, 7 and 8). There is even an auxiliary chain (L-N-F-M-Q) which is not connected to the Main Menu. The theory of menus (and therefore of bombes)If we take a Theoretical point, based on the mathematical theory of Groups, the presence of loops is independent of the value of Steckers. This discovery was made by the Polish Rejewski. While the number of stecker combinations is astronomical, the probability of having one loop is low and the probability of having three loops in the same menu by pure chance is exceedingly low. The first bombes (those of Rejewski and that of Turing) explored all the combinations of rotors and their relative positions and looked for configurations compatible with a Menu deduced from a message or its header. If so, the Bombe would stop. We then checked whether this was a false positive or the real solution. Rejewski's bombe used menus called by the English “Query Menu”. They were derived from the indicators of messages for which the message key was twice encrypted (throw-on indicators). Knox predicted that if the Germans abandoned throw-on methods, Zygalski's sheets (the main method at the start of the war for breaking a key) and Rejewski's bombe would become obsolete. Turing then designed a bombe based not on the indicator but on the presence of a Crib (supposedly plain text of the cryptogram or part of the cryptogram). On the other hand, it was necessary, as for the bombe of Rejewski at least 3 loops. In the case of the Rejewski loop, these loops were called “females” and reduced to just two letters. Subsequently in the menus have them represented by two segments. For example in the following example: U ==== E. In the Turing bombe, the menu had to contain only loops that all have one letter in common. In addition, there had to be at least three loops. In addition, if there were turnover, it was necessary to know their position. In the following example, we have a menu made up of 4 loops, all passing through the letter E.
T
/|\
ZZM / | \
/ | \ ZBH
/ZZF| \
/ ZBG|ZZJ \
U=====E----R
ZDK | /
| /
ZBL| /ZDL
| /
|/
S
Needless to say, the Turing Bombe, admittedly interesting from a theoretical point of view, was not operationally usable. In early 1940 Welchman made an exceptional discovery. He told Turing that if we took into account the reciprocity of the Enigma (if we cipher E and the result is C then if we cipher C we get E), we could drastically reduce the number of Stops. After the adding of the diagonal board which implemented Welchman's ideas, the bombe (from Turing / Welchman) became the main tool for breaking Enigma keys. Of course, the more loops you have, the better the menu. A good menu is a menu with a low probability of causing stops, in practice no more than 4 on average. If there are more than 4 stops, the stop testing takes too long. But if you have enough connected segments, you need fewer loops and in the extreme you can have a menu without any loops. It is also possible to add auxiliary chains (several segments linked together but not linked to the main menu). You can also use two small menus, each using an input letter and which is generally equivalent to a single menu. Here is the impact of the number of loops (or closures) on the number of stops expected for a given Walzenlage (Wheel Order).
Letters Closures Stops/W.O.
6 4 1
7 3 5
8 3 2
9 3 1
10 2 10
11 2 4
12 2 1
13 1 7
14 1 2
15 0 7.5
16 0 1.5
The Turnover problemIn a menu, you have to know the relative position of the menu letters in the space of the three rotors. Another way to put it is to say that you have to know the position of the turnovers. As it is not possible to know the position of the turnovers, we can assume it and make several menus each with a different position of the turnover of the right wheel. At least two menus will be needed, assuming that the turnover appears in the first 13 letters of the menu or in the last 13. The two menus should also cause a maximum of 4 stops on average. This is rarely the case. Most often it will take 3 or even four menus to have only good menus (which does not cause more than 4 stops). In the following example, we create three menus based on the same Crib. In Menu 1 we assume that the turnover appears from the 21st letter. In Menu 2 we assume that the turnover appears in the first ten letters and in the third menu that the turnover appears between the 11th letter and the 20th letter.
Routine crib based menu
Menu 1 zzzzz zzzzz zzzzz zzzzz
Menu 2 zzzzz zzzzz zzzzz z
Menu 3 zzzzz zzzzz aaaaa a
abcde fghij klmno pqrst uvwxy z
Crypto WCGLV EUTCF ZTQSA WJCSR FQOOZ Z
Crib KEINE BESON DEREN VORKO MMISS E
If you have a crib from re-encoding, you only need two menus. Indeed, the cribs coming from a re-encoding are often long (several times 26 letters). They can span multiple lines of 26 letters. Be careful, do not take too many lines, otherwise the probability that the left rotor turns becomes important. In the following example, on purpose, we have taken very narrow menus (5 letters but 5 lines). It would probably have been smarter to only take menus 13 letters wide on two lines.
Menus based on crib from re-encodement
Menu 1 Menu 2
====== ======
abcd efgh ijkl mnop qrst uvwx yz
================================
NACH RICH TENF UEHR ERVO RLEG EN zz
kwtj xusv xutl kxge gwgg niiv ct
** **** *
XWEG ENVE RRAT DERT AKTI SCHE MG za
itjm iiqn muea fthc xhkz xryw ze
**** * **
LIED ERUN GEND UERF ENAU FKEI NE zb
rlti btmt ohen dqiw whxv ocve uw
* **** *
MFUN KNET ZBEI UNWI CHTI GEMV ER zc
njev izbv jooc etrc jlrl ybjz lz
* * *
KEHR ALLE FUNK STEL LENG ERUF EN zd
egpx tiyc owka bgzs fxgq vxwu lr
** * **** *
zca zza zce zaa zze 9
M-----N-----K-----I-----x=====R
\ 5 1 | 6 / 8 zdd
zad\ zda| /zae 10
\4 2| /
\ 3 | /7
\ zdb |/
G-----E <<---- Input Letter
| 11
Menu 1 zbc|
4 loops | zde 12
11 letters T------A
14\ /13
zab\ /zzb
\/
W
1 zaq
A========X
2 zbs |
3|zdr
| zdu
` Input letter >>> E-----V
/| 13 /
4/ | /12
Menu 2 zbq / | / zgs
4 loops / 14| /
12 letters / |/zzt zbu
W G-----O-----F
5| | 11 10 |
zzr| 15|zds 9| zdq
| zzu | zbr zcr |
R-----N-----H-----L
6 7 8
|