Enigma Home Page
|
IntroductionThe method developed by the Pole Zygalski (called Netz by Polish [it is a German word], Net by English and "filet" by French), is highly significant in the history of Allied code-breaking. Its use at the beginning of World War II foreshadowed the employment of the Turing-Welchman Bombes. The use of Bombes remained the primary method for cracking Enigma messages throughout the remainder of the war. History of the sheetsAs early as 1932, Polish cryptanalysts, exploiting a weakness in the Enigma's indicator system (used to encrypt the message key) and aided by secret information from the French (notably key tables), cracked the Enigma system. After employing various methods that capitalized on operator errors, the Poles developed the "catalog method," which also relied on the indicator system's vulnerability. In September 1938, the Germans changed their indicator system, rendering the catalog method obsolete. Polish cryptanalyst Zygalski realized that the new indicator method remained flawed and devised a technique to exploit this weakness. Zygalski’s method required the creation of a vast number of perforated sheets, a task the Poles began to undertake. Unfortunately, in late 1938, the Germans added two new rotors to the existing three; the Poles lacked the resources to produce enough sheets to utilize their new method. Collaboration with their allies became essential. In July 1939, near Warsaw, the Poles shared their expertise with the French and British, specifically the wiring of the Enigma components (the entry stator, the five rotors, and the reflector), which allowed for the physical reconstruction of the Enigma, as well as Zygalski’s method for cracking daily keys. Unfortunately, war broke out too soon, in September 1939, and Poland was defeated within days. The Polish cryptanalysts made their way to France to work alongside their French and Spanish counterparts (refugees from the Spanish Civil War). British cryptanalysts produced the sheets, and a copy was sent to their colleagues working in France. As early as January 1940, Zygalski sheets enabled the first wartime decryptions of Enigma messages. Traffic was light during the "Phoney War" (Drôle de guerre), but from April 1940, coinciding with the Battle of Narvik, Enigma encrypted traffic surged, resulting in a flood of decrypted intelligence reaching Allied headquarters. Unfortunately, when the Germans invaded Luxembourg, Belgium, and France in May 1940, they changed their message indicator procedures, rendering the Zygalski sheets obsolete. The British had anticipated this event and developed the "Bombes" machines (Turing/Welchman). Unlike previous methods, the Bombes did not rely on indicators; instead, they utilized "cribs" (matching a known plaintext phrase to a specific section of the ciphertext). However, in May 1940, the Bombes were not yet operational. Manual methods (developed by Knox and Herivel) that exploited operator errors allowed decryption efforts to continue until the Bombes came online. An Enigma cryptogram : structure and recordingThe Enigma indicator system in 1938Starting on September 15, 1938, the Germans changed their indicator system. Here is the beginning of a message: 1755 145 OUN ULZNU WDKYD JMZFM TZSOX ZBEBJ IU...
Key tableEach network, identified by its Kengruppe, has a key table that allows operators to encrypt indicators and messages. Here is an excerpt from a key table for the "Yellow" network (an Allied designation); there is a different key for each day of the month:
Tag Walzenlage Ring. Steckerverbind. K.E.G. Kenngruppen
31 I II III 22 15 14 AE BC FI JT KM NP OR QS UW XZ 1 ndq nuz opw vxz
30 II I III 3 14 24 AM HU DY EG PS BN KT FJ OZ QX 1 jfa fiq fin rul
29 II III I 1 21 8 HN TW EI GX LV JM DU OQ FP CZ 1 qwp xcd hhd mig
...
Notes :
BlistTo use Zygalski sheets, the Allies recorded the headers of intercepted messages in a document called the Blist (Bannister List). Number Call-sign Time Part number Length Grund. The first Three groups 236 2EX RN2 1525 176 =DOT= OUPWO NEQAI JKLFU 237 TOH IDM 1755 2TL=1TL 145 =OUN= ULZNU WDKYD JMZFM 238 TOH IDM 2TL 69 =BNC= ARNDQ CEPKN DDGKRNote: By analyzing multi-part messages, one can easily deduce the Kengruppe belonging to the same network. In the example, the kengroups ZNU and NDG identify the same network. The Zygalski's method: The TheoryThe Cyclometer and cyclesIf we examine the two indicators QTNEFE and EGRQHA, ciphered at the same Grundstellung, we observe that the Q in the first position is associated with the letter E in the fourth position. These two letters correspond to the same plaintext letter. Then, in the second indicator, the situation is reversed: the first letter is an E and the fourth is a Q. This forms a cycle of length 2 (see Rotor). Q -> E -> Q (cycle of length 2) The letter pairs of the indicators 1-4, 2-5, and 3-6 correspond to three independent cycles. Note: these indicators were created as follows: $ echo CCCCCC |python3 M3.py B III II I "" ZZZ AAF QTNEFE $ echo LLLLLL |python3 M3.py B III II I "" ZZZ AAF EGRQHAThe Cyclometer allows one to find all cycles existing at a given Grundstellung (initial rotor setting) for a given Walzenlage (rotors order) in the absence of Steckers (plugboard connections). Here is an excerpt from the catalog for Walzenlage III-II-I, which I generated using a program that emulates the Cyclometer. $ python3 cyclometer.py -W III,II,I -R ZZZ Walhs Ring Grund pln cry - signature cycles grund (left, mid, rig) ================================================================ 13-13 PRKGBNMQODSHZ:WEIJALUCVTYFX III,II,I ZZZ AAA 1-1-12-12 SWQMPOIVZHNX:FEGLTUBRYAKJ:D:C III,II,I ZZZ AAB 2-2-11-11 NMYRUZJCEDW:TQPOLHFAIGK:VX:BS III,II,I ZZZ AAC 6-6-7-7 RHCUZLI:STAPFOG:EYNXKJ:BVQWDM III,II,I ZZZ AAD 2-2-11-11 WYQFZGBCEVR:IHTMKLADPNX:SO:UJ III,II,I ZZZ AAE 2-2-4-4-7-7 MRDOKWG:TYANHPZ:XIJV:UBSF:QE:LC III,II,I ZZZ AAF 1-1-2-2-10-10 YTOFRNVZQJ:UCWBPIDSXE:HG:LA:M:K III,II,I ZZZ AAG 6-6-7-7 YLOKHFT:PWQRBAJ:NEXZUV:MCIGDS III,II,I ZZZ AAH ...Note: It is observed that the AAF Grundstellung (at ZZZ Ringstellung, for Walzenlage III,II,I) is associated with 6 cycles: MRDOKWG, TYANHPZ, XIJV, UBSF, QE, LC, with respective lengths of 7, 7, 4, 4, 2, and 2. IMPORTANT: The cycle length for a specific Grundstellung is independent of the presence or absence of Steckers. This catalog made it possible to find the key by studying the cycles deduced from the indicators at Grundstellung and Grundstellung +1 and +2. Indeed the Grundstellung being part of the key of the day. When the Grundstellung was chosen by the operator it was no longer possible to use the catalog as is. FemalesIf we take cycles of length 1, the same letter will be repeated, for example in position 1 and in position 4. This is the case for the following indicators: MWNMRJ and KETKZZ. Since the cycle has a length of 1, no additional indicators are needed to continue it; thus, a single indicator can contain a complete cycle. The Poles referred to these length-1 cycles as "females." However, not all Grundstellungs necessarily possess "females." The probability of this occurring is only 40%. Notes
If a letter (e.g., K) is encrypted at position 1 when no plugboard connections are present, the result is necessarily a different letter (e.g., M). If the same letter K is encrypted at position 4 given a configuration (Grundstellung) that involves a "female", the result is the letter M. Now, If we encrypt the letter M, in positions 1 and 4, we necessarily get the letter K. Thus, "females" come in pairs, and the two letters constituting the pair correspond to the plaintext letter and the ciphertext letter at positions 1 and 4. The Zygalski's methodThe Zygalski method is simple. It consists of determining which "females" (in an absolute reference frame), correspond to the "females" extracted from the traffic (in a reference frame linked to the day's key). One moves from the absolute reference to the reference linked to the day's key using the Ringstellung, via the formula: RING = GRUND - POS - [1,1,1]
Note: In the formula above, I use the mappings A=0, B=1, C=2, ... Z=25. The Germans and the Allies used the mappings A=1, B=2, ... Z=26. Not all "females" can be usedThe "females" derived from the cyclometer and recorded on the sheets were produced without Steckers and also without turnovers. Therefore, any "females" whose Grundstellung result in a turnover must be discarded. These account for approximately 15% of the "females." Fortunately, it is easy to identify the Grundstellung (initial rotor settings) where a turnover occurs. Turnovers depend on the rotor: Q for rotor I, E for rotor II, and V for rotor III. Thus, if testing the rotor order III, II, I, the turnover will occur at position Q for the right-hand rotor. In short, Grundstellung ending in N, O, P, or Q (the letters preceding the turnover) are excluded (for 1-4 female). Here is an example that causes turnover: $ echo DOTDOT | python M3.py B III II I "" ABC ABN x [0001] = A B O = D -> D : V Y Q < E > P U T -> T [0002] = A B P = O -> O : X V M < O > Z S Q -> Q [0003] = A B Q = T -> T : C D H < D > B J C -> C [0004] = A C R = D -> D : D R W < V > L N J -> J [0005] = A C S = O -> O : V E J < X > K J T -> T [0006] = A C T = T -> T : W U K < N > N X V -> V TQCJTVFurthermore, there must be no errors. The selected Grundstellungs must be reliable; otherwise, recovering the Ringstellung might prove impossible. Consequently, cryptanalysts will only use cryptogram headers that have been intercepted multiple times and possess a high reliability rating (indicating good radio signal reception). Note: This best practice will continue to be applied when subsequently creating the "Bombe" menus. A very simple implementationThe algorithmBefore studying the method using sheets, I wrote a small computer program with a very simple algorithm:- INPUT : = WALZENLAGE : the selected rotor order = FEMALES : the set of all possible females for the selected Walzenlage = GRUNDS : the Grundstellungs derived from the day's traffic containing females - OUTUP : = RING : all traffic-compatible RINGs def calculated_females( aRing, GRUNDS ) : """ calculates the absolute positions of the females using the formula: aPOS_calculated = aGRUND - aRing – [1,1,1] """ return all_POS_calculated for aRING in all_possible_ring : current_females = calculated_females( aRing, GRUNDS ) if current_females in FEMALES : print( aRING )Note: current_females, FEMALES, are the rotor positions prior to the encryption of the first letter of the pair (1-4, ...). It is a Grundstellung but with a Ringstellung of ZZZ. An exampleI am using the data from Frank Carter (see References). Message headers containing females:Grund. Indicator Grund(s) of the female(s) SIZ CXWCGU SIZ FTC FGPFYV FTC APV FLSFTN APV BAU NBZNNF BAU MID UXMUXL MID, MIE HFV GIIGSC HFV JDY GCFGXM JDY NLR RPARML NLRNotes:
The solution is found when testing rotor order III, II, I (321) : If only three Grundstellungs are used, there are nearly 1,000 solutions. With eight Grundstellungs there are only 9 possibilities. Finally, there is a single solution (Ring: KEN) with nine Grundstellungs (SIZ,FTC,APV,BAU,MID,MIE,HFV,JDY,NLR). $ python3 zygalski.py 321 SIZ,FTC,APV | wc -l 966 $ python3 zygalski.py 321 SIZ,FTC,APV,BAU,MID,MIE,HFV | wc -l 9 $ python3 zygalski.py 321 SIZ,FTC,APV,BAU,MID,MIE,HFV Ring: BOM Ring: GDU Ring: JUM Ring: KEN Ring: LAP Ring: OSE Ring: RXJ Ring: SWF Ring: YAQ $ python3 zygalski.py 321 SIZ,FTC,APV,BAU,MID,MIE,HFV,JDY,NLR Ring: KEN The Zygalski method: using sheetsBroad overviewA sheet contains all the "females" associated with one of the 26 Grundstellungs of the left rotor for a given Walzenlage, for example, Sheet Hxx, 321. An abstract sheet consists of a grid where the coordinates of a cell are the 26 possible Grundstellungs of the middle rotor (y-axis) and the 26 possible Grundstellungs of the right rotor (x-axis). A grid cell (e.g., HCM) contains a hole if its coordinates correspond to a "female"; otherwise, the cell remains solid (as is the case for HCO). Note: The method (as we shall see later) involves stacking sheets while offsetting them. To ensure that data from multiple sheets align correctly, physical sheets are used that replicate the abstract sheet in both directions (x and y axes); thus, one physical sheet corresponds to four copies of the same abstract sheet. We stack the sheets corresponding to the "menu": we take one sheet for each Grundstellung derived from the intercepted traffic. The problem is that the Ringstellung, specifically that of the left rotor, is unknown. The solution is simple: we test all 26 possible Ringstellungs of the left rotor. The sheets are stacked over a light source. If the Ringstellung is correct for the sheets being used, certain holes will align, allowing light to pass through. A fixed frame placed above the sheets allows each sheet to be positioned with the appropriate offset (C, D, E, etc.). If the correct "females" have been found, the inverse coordinates on the frame (Z, Y, X, etc.) reveal the Ringstellung. Let’s be more preciseIf we take the set of sheets corresponding to the Grundstellungs derived from the traffic, we can be certain that the "females" in absolute notation (represented by holes) are present. If, for each sheet, you subtract the Grundstellung value derived from the traffic, you obtain the negative Ringstellung value (based on the formula POS = GRUND - RING - [1,1,1]) ... for all the female elements present on that sheet! However, only one of these females elements is correct. If this operation is performed for every Grundstellung (i.e., every sheet), the female element(s) compatible with the data will share the same Ringstellung. This manifests as the holes (female elements) on the various sheets aligning and allowing light to pass through. As more Grundstellung (sheets) are added, the number of overlapping holes and thus the number of possible Ringstellungs decreases. Ultimately, only a single hole remains, revealing the correct Ringstellung value. Subtraction along one of the axes (x or y) is achieved by shifting the sheet within a reference frame (A, B, C...) in the direction that reduces the origin value (to align it with the Grundstellung) for example, if the Grundstellung is C, the reference frame will be (C, D, E, ...). The (negative) Ringstellung is then read using a reverse reference frame (Z, Y, X...). Example1) Extract the correct sheetsLet us revisit the previous example using the first four Grundstellungs: SIZ, FTC, APV, BAU. Assuming the correct Walzenlage is 321 (all Walzenlage settings must be tested) and the Ringstellung of the left rotor is K, (all left Ringstellung must be tested), we take the following four sheets (all belonging to set 321): POS = GRUND - RING - [1,1,1] Hxx = SIZ - Kxx – [1,1,1] = 18 - 10 -1 = 7 (H) Uxx = FTC - Kxx – [1,1,1] = 5 – 10 – 1 + 26 = 20 (U) Pxx = APV – Kxx – [1,1,1] = 0 – 10 – 1 + 26 = 15 (P) Qxx = BAU – Kxx – [1,1,1] = 1 – 10 – 1 + 26 = 16 (Q)To find the Ringstellung for middle and right rotors, we therefore stack sheets H, U, P, and Q. 2) Offsetting the sheetsPreliminary note: We will focus only on offsets along the x-axis (abscissae); the reasoning is the same for the y-axis (ordinates).
Note: We assume the solution is known. Thus, considering only the x-coordinate, we have female elements (holes) at the following coordinates:
RING_right = GRUND_relative – POS_absolue – 1If the female parts at absolute or relative coordinates are the same for each sheet, the ring setting of the right-hand rotor must be identical for each female part:
3) Graphical representation (like the sheets)a) Before the shifts (the "females" in absolute values)
Sheet H : A B C D E F G H I J K L M N O P Q R ...
*
Sheet U : A B C D E F G H I J K L M N O P Q R …
*
Sheet P : A B C D E F G H I J K L M N O P Q R ...
*
Sheet Q : A B C D E F G H I J K L M N O P Q R …
*
b) After the offsets (the females in relative terms)
Sheet H : Z A B C D E F G H I J K L M N O P Q ...
*
Sheet U : C D E F G H I J K L M N O P Q R S T ...
*
Sheet P : V W X Y Z A B C D E F G H I J K L M ...
*
Sheet Q : U V W X Y Z A B C D E F G H I J K L ...
*
c) The Ringstellung is read on the reverse scale (to simulate subtraction).
Z Y X W V U T S R Q P O N M L K J I ... *The Ringstellung of the right rotor is obtained: N Example of a sheetExample of the H sheet for Walzenlage 321. Only an abstract sheet (one-quarter of a physical sheet) is shown.
$ python3 zygal_sheets.py 321 Z HAA
...
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Z Y X W V U T S R Q P O N M L K J I H G F E D C B A
A Z * * * * * * * * * * * * *
B Y * * * * * * * * * * * * * * * * *
C X * * * * * * * * * * *
D W * * * * * * * * *
E V * * * * * * * * * *
F U * * * * * * * * * * *
G T * * * * * * * * *
H S * * * * * * * * * * *
I R * * * * * * * *
J Q * * * * * * * * * * * * * *
K P * * * *
L O * * * * * *
M N * * * * * * * * * * *
N M * * * * * * * * * * *
O L * * * * * * * * * * * * * *
P K * * * * * * * * * * * *
Q J * * * * * * *
R I * * * * * * * * * * * * * * *
S H * * * * * * * *
T G * * * * *
U F * * * * * * * * * *
V E * * * * * * * * * *
W D * * * * * * * * * * *
X C * * * * * * * * * *
Y B * * * * * * * *
Z A * * * * * * * * *
My program 'zygal_sheets.py' allows a sheet to be displayed, but its main
purpose is to display a stack, and thus to determine the Ringstellung,
just like my previous program, 'zygalski.py.
$ python3 zygal_sheets.py 321 K SIZ,FTC,APV,BAU,MID,MIE
...
Grunds: ['SIZ:H', 'FTC:U', 'APV:P', 'BAU:Q', 'MID:B', 'MIE:B']
A stacked sheets for left Ring K and Walzenlage 321
E F G H I J K L M N O P Q R S T U V W X Y Z A B C D
Z Y X W V U T S R Q P O N M L K J I H G F E D C B A
I Z
J Y
K X
L W
M V
N U
O T *
P S
Q R
R Q
S P
T O
U N
V M *
W L
X K
Y J
Z I
A H
B G
C F *
D E *
E D
F C
G B
H A
Note: The probable Ringstellungs include KTW, KMR, KFO, and KEN: the correct value.
Number of Stacks to Test, The Key RulesAll possible Walzenlage configurations must be tested. For three rotors, there are only 6 Walzenlages configurations to test (123, 132, 213, 232, 312, 321). However, from the end of 1938 and the beginning of the war (1939, 1940), since five rotors were used, there are 60 Walzenlage configurations to test. Furthermore, for each Walzenlage configuration, 26 stacks must be tested, one for each Ringstellung of the left-hand rotor. Therefore, a maximum of 60 x 26 = 1560 stacks must be tested, and on average half that number (760). Of course, the stacks corresponding to different Walzenlage configurations can be performed in parallel by different people because they are not using the same set of sheets. But this still makes for an impressive number of tests to be carried out. Fortunately, the Germans, for a given network, did not use randomly selected Walzenlages every day. They followed rules, called "Key Rules" by the Allies. These rules drastically reduced the number of Walzenlages to be tested. Here are the rules used by the Luftwaffe network in 1940 (called RED by the Allies):
ConclusionZygalski sheets enabled the first decipherments of World War II. However, the most significant point is that Welchman, in order to utilize these sheets to decrypt Enigma traffic, established a highly structured organization known as Hut 6. This organization subsequently persisted when the "Bombes" became operational. References
|