My crypto Home Page
|
IntroductionA new traffic appearsIn January 1940, the American cryptographic service of the Coast Guard intercepted messages of unknown origin. Since 1937, this service had been headed by Elizebeth Smith Friedman. Thanks to a recently declassified document, we know the details of the analysis of these messages. From more than a hundred in-depth messages, Elizebeth and her team managed to find the wiring of two of the rotors of the Enigma machine at the origin of these messages. She developed original methods without knowing the British work (Dilly Knox, Alan Turing) and the Poles's ones (Rejewski, ...). She can be credited with being at the origin of the first methods of breaking an Enigma rotor on American soil. In fact, Elizebeth and her team realized that in fact, the messages came from the Swiss army. At the time, this used a commercial Enigma (A26) whose rotor wiring was already known. Unfortunately the content of the messages (in German) was not strategic. American cryptographic servicesIn the 1950s, the NSA brought together all American cryptographic services. The NSA thus copied the GCHQ service, the new name of the GC&CS which centralized the British cryptographic resources during the Second World War. On the other hand, between the two world wars, there was a plethora of American cryptographic services (as with the Germans): the Army service, that of the navy, that of the FBI, that of the Coast Guard, ... In 1942, the cryptographic service of the Coast Guard merged with that of the navy (OP-20-G). Elizebeth Smith FriedmanElizebeth Smith met W.F. Friedman in 1916 when she joined Colonel Fabyan's Riverbank Laboratories. She fell in love with him and they both became passionate about cryptography. After the war she did several cryptographic assignments for the State Department. In 1923 she was hired by the Navy. In 1925, she joined the Coast Guard Cryptologic Service. In 1937, she headed this small service of 4 people (including herself). The Achievements of the Coast Guard ServiceIn 1945, a Navy cryptologist, Jones c, described the work done by the Coast Guard Cryptologic Service during the war (1940 to 1945) in a report that was recently declassified: History of Coast Guard Unit #387, 1940-1945. We learn about the different works and methods used to decipher messages using different techniques: Double transposition, the Kryha cipher machine, the Enigma cipher machine ...We have just noticed it, Jones' report describes several works. As for the traffic that began in January 1940, the part that interests us is entitled: "PART II – C – Enigma wiring unknown – 1 – Single turnover" , it begins on page 216. The recover of the wiring of the fast rotorUsing our simplified 6-contacts EnigmaThe History of Coast Guard Unit written by Jones c, is not easy to read due to the poor condition of the document. Stuart Boersma in 2024 writes an article (cf. References) that tries to make the methods of Elizebeth and her team understandable. He uses a simulator written in Python emulating a Military Enigma without steckers. One of the advantages is that the military Enigma does not have Qwertzu and therefore the calculations are simpler and more readable. Personally, I want to be even more readable by using my ultra simplified version of the Enigma which uses only one rotor, no steckers, no Qwertzu and only 6 contacts instead of 26. Using Python and the SymPy library, I can easily perform calculations on permutations. The first stepsAfter several months, about 110 messages were intercepted, some of which were about 200 characters long. How to determine the meaning of the messages? Whatever the encryption method, even the most sophisticated and even the most recent, there is one method that can always be used, which is to deduce the plaintext messages from the cryptograms ... if they have been encrypted with the same key. In this case, they are said to be in-depth. It is understood that a message should never be encrypted with a key that has already been used. This rule was often ignored in the 1930s and 1940s by cryptologists who used the first encryption machines and who believed a little too quickly in their invulnerability. By analyzing these messages, Elizebeth and her team easily realized that the messages were in-depth. Indeed, thanks to the coincidence index invented by her husband, it was possible to have a scientific measure that proves it. Moreover, several coincidences followed one another (they therefore corresponded to bigrams, trigrams or words). Thus the fact that the messages were in-depth was no longer in doubt. Discovering the plain text from messages in-depth, is more or less simple depending on the encryption method. Thus, only two cryptograms encrypted with the M-209 machine at the same key, are enough to find the plain text of the two messages. If it is a rotor machine, Elizebeth's husband estimated in 1930 that about 50 messages were needed. Elizebeth and her team had 110 messages in-depth, so determining the plain text of the messages was possible. In fact, obviously Elizebeth did not start her analysis after receiving 110 messages. But no results were obtained until 60 messages had been intercepted. It must be kept in mind that from the first messages, the only thing known was that the messages were in-depth. From 60 messages, the first plain texts were deduced. Of course, the more messages accumulated, the more the deductions multiplied and became more reliable. Elizebeth realized that the language used was German. Then, the fact that a letter could not be encrypted by itself undoubtedly allowed Elizebeth to conclude that the method used was the commercial Enigma (the other Enigmas were a priori almost unknown at the time by the Americans). W.F. Friedman probably informed his wife directly (or the various American cryptology services including the Coast Gueard) about the details of the Commercial Enigma cipher, a copy of which he had purchased for the Army. In addition, she also realized that the letter X was used to separate words. By reading the manual of the commercial Enigma, she had confirmation of this practice and that the letters on the first line of the keyboard were used to translate the numbers: Q W E R T Z U I O P 1 2 3 4 5 6 7 8 9 0The letter Y indicated switching to digital mode and the letter X (in addition to separating words) indicated returning to text mode. Encryption performed by our EnigmaFrom the many in-depth messages available, Elizebeth was able to reconstruct several alphabets and to establish the Enigma cipher table and thus encrypt / decrypt any message using the same keys. The following table (Table 1) is an example of a cipher table. Note: In the case of our simplified Enigma, the table can cipher / decipher any message because it uses only one rotor. In the case of the table established by the Coast Guard service, the middle rotor can move forward. It must be remembered that we do not know the location of the turnover (for now). The column headers correspond to the letters of the alphabet (0 to 5 for our 6-contacts Enigma, A to Z for the commercial Enigma). The ordinate corresponds to the position of the rotor. If we encrypt the message 1132 from position 2, we obtain the cryptogram 3454. If we decrypt, still from position 2, we obtain 1132, because encryption is equivalent to encryption.
Table 1
-------------
0 1 2 3 4 5
0 1 0 5 4 3 2
1 4 5 3 2 0 1
2 4 3 5 1 0 2
3 5 4 3 2 1 0
4 4 2 1 5 0 3
5 3 5 4 0 2 1
Note: If we inspect Jones' paper, the encryption table contains some holes. These are due to the fact that the various in-depth messages do not cover all encryption possibilities. The mathematical view of the EnigmaElizebeth Friedman had a clear (mathematical) vision of the functioning of the commercial Enigma thanks to that the Americans had this machine and thanks to the work done by her husband when he broke Hebern's cipher machine equipped with five rotors. On the other hand, this vision, although operational, is inferior to the one used today and which is based on permutations. This vision was however known to Polish (Rejewski, …) and British (Turing, …) and Germans cryptanalysts. This is the one we will use for the following. Note: those who wish to know the Friedman vision of rotor machines, can read The Friedman's report about Hebern 5 rotors machine, which explains how W. F. Friedman broke this machine. The first chapters described the machine and how the encryption was performed. A paper representation of the machine summarized its operation and can be used to encrypt and decrypt a message ... when you know the wiring of the rotors. We have already described the Enigma cipher, but in its military version, here is the formula adapted for the commercial Enigma (there are no steckers):
We can make some simplifications:
In short, we get a much simpler equation (i being the position of the fast rotor):
\( E_i = P^{i} \cdot N \cdot P^{-i} \cdot Q \cdot P^{i} \cdot N^{-1} \cdot P^{-i} \) We have the following permutations:
This formula is also correct in the case of our simplified Enigma. Of the four permutations, N, Q, P and E, only the E and rotation P are known to us.
Here are the different powers of the rotation: Notes:
Elimination of the rotation of the fast rotorElizebeth then tries to eliminate (as much as possible) the action of the rotation of the fast rotor. To do this she uses strips of paper to do the operations. Unlike the Friedmans, we know the permutations. We will be able to express Elizebeth's operations by the following formula:
\( Fri_i = P^{-i} \cdot E_i \cdot P^{i} \) Notes:
In the following, we do the calculations using Sympy:
>>> from sympy.combinatorics import Permutation >>> P = Permutation([1,2,3,4,5,0]) >>> E0 = Permutation([1, 0, 5, 4, 3, 2]) >>> E1 = Permutation([4, 5, 3, 2, 0, 1]) >>> E2 = Permutation([4, 3, 5, 1, 0, 2]) >>> E3 = Permutation([5, 4, 3, 2, 1, 0]) >>> E4 = Permutation([4, 2, 1, 5, 0, 3]) >>> E5 = Permutation([3, 5, 4, 0, 2, 1]) >>> Fri_0 = (P**-0)*E0*(P**0) >>> Fri_0 == E0 True >>> Fri_1 = (P**-1)*E1*(P**1) >>> Fri_2 = (P**-2)*E2*(P**2) >>> Fri_3 = (P**-3)*E3*(P**3) >>> Fri_4 = (P**-4)*E4*(P**4) >>> Fri_5 = (P**-5)*E5*(P**5) >>> Fri_1.array_form [2, 5, 0, 4, 3, 1] >>> Fri_2.array_form [2, 4, 0, 5, 1, 3] >>> Fri_3.array_form [5, 4, 3, 2, 1, 0] >>> Fri_4.array_form [5, 3, 4, 1, 2, 0] >>> Fri_5.array_form [4, 3, 5, 1, 0, 2] >>> Here is the resulting table (table 2): Table 2 ------------- 0 1 2 3 4 5 0 1 0 5 4 3 2 1 2 5 0 4 3 1 2 2 4 0 5 1 3 3 5 4 3 2 1 0 4 5 3 4 1 2 0 5 4 3 5 1 0 2 Discovery of regularities in table 2Elizebeth was surprised to find anomalies in table 2. A perfect encryption system only generates randomness. Finding anomalies in relation to this randomness, therefore, corresponds in fact to regularities due to structures that are expressed (in short, here, the rotation of the fast rotor). Study of anomalies with our simplified EnigmaIn the case of our simplified Enigma, we can see these anomalies: In each column (a letter of the alphabet), we see that two letters are doubled and follow each other: 2255, 4433, 5500, 1144, 3311, 0022. Let's highlight these doubled letters.
Table 2 Repetitions
------------- -------------
0 1 2 3 4 5 0 1 2 3 4 5
0 1 0 5 4 3 2 0 . . 5 4 3 2
1 2 5 0 4 3 1 1 2 . 0 4 3 .
2 2 4 0 5 1 3 2 2 4 0 . 1 .
3 5 4 3 2 1 0 3 5 4 . . 1 0
4 5 3 4 1 2 0 4 5 3 . 1 . 0
5 4 3 5 1 0 2 5 . 3 5 1 . 2
5 4 2
0 4
0
Study of anomalies with the military EnigmaIn 2024, Stuart Boersma reproduced Elizebeth's work using a military Enigma. Starting with alphabet 5 (5 indicates the position of the fast rotor relative to the first letters ciphered from messages), we note in the column corresponding to the letter A, the repetition of the pair VD eight lines further. In column B, we note the repetition of the pair DW, always eight lines away. In the following columns, we note similar repetitions. These repetitions end at alphabet 30. However, other anomalies appear afterwards.
Study of anomalies with the commercial EnigmaIn the data collected by the Coast Guard service, we find in the first 4 columns of alphabets 1 to 4 (lines 1 to 4), the pairs LL, FF, II and TT. From alphabet 5, we find two pairs that follow each other: OHOH, AZAZ, MDMD, ZQZQ, … These repetitions end at alphabet 30. On the other hand, other anomalies appear afterwards. Elizebeth will interpret these discontinuities as coming from the turnover taking place at alphabet 5 and then at alphabet 31 (5+26=31) Anagram of the columns of table 2, wiring of the fast rotorElizebeth had the idea of making an anagram of the columns of table 2 so that they form regular diagonals. This gives table 3. She correctly interpreted the column heads as well as the diagonals: they correspond to the wiring of the fast rotor (actually to the reverse rotor).
Anagram Table 3
------------- -------------
0 1 5 3 2 4 0 1 5 3 2 4
0 0 1 0 2 4 5 3
1 2 1 2 5 1 4 0 3
2 2 4 2 2 4 3 5 0 1
3 5 4 0 3 5 4 0 2 3 1
4 5 3 0 1 4 5 3 0 1 4 2
5 3 2 1 5 5 4 3 2 1 5 0
2 4 5 4
4 0 4
0 3
3
Due to the twist effect (cf. rotors), we obtain one version among others of the reverse of the fast rotor wiring. Thus the following two solutions are equivalent: 015324 and 153240. Note: I made my test set using the following wiring: 0 1 5 3 2 4 (Yay!). >>> from sympy.combinatorics import Permutation >>> N = Permutation([0,1,4,3,5,2]) >>> P = Permutation([1,2,3,4,5,0]) >>> Q = Permutation([1,0,4,5,2,3]) >>> >>> (~N).array_form [0, 1, 5, 3, 2, 4] >>> >>> N*Q*N**-1 Permutation(0, 1)(2, 5)(3, 4) >>> N.array_form [0, 1, 4, 3, 5, 2] >>> E0 = N*Q*N**-1 >>> E0.array_form [1, 0, 5, 4, 3, 2] >>> E1 = (P**1)*N*(P**-1)*Q*(P**1)*(N**-1)*(P**-1) >>> E1.array_form [4, 5, 3, 2, 0, 1] ... Reconstruction of the wiring of the middle rotorBy removing the effect of the fast rotor, Elizebeth and her team were able to deduce from the traffic, the wiring of the middle rotor (see references). The results of the Coast Guard service analysisThe recovering of the rotors wiring by the Coast GuardAt the end of the report concerning the traffic of January 1940, the rotor wiring which have been reconstructed are presented:
- Fast rotor: 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 E S M J R U O A H Z D Q B P V G L F I T N X W Y K C - Middle rotor: 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 W Z A N D F I E C M R U Q G T X P S Y O H J L V K B - The extended reflector (reflector and left rotor) 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 Y I Z E D R P O B T W S U Q H G N F L J M X K V A C (AY)(BI)(CZ)(DE)(FR)(GP)(HO)(JT)(KW)(LS)(MU)(NQ)(VX) From these wirings, the Signal Corps identified these wheels as coming from an old commercial Enigma (Lot A-766) and the Navy identified the traffic as coming from the Swiss Army. The order of the wheels being 1-3-2 (from left to right, as one faces the machine). Unambiguous identification of rotorsJones' report thus identified the machine at the origin of the traffic as being the Commercial Enigma with its standard rotors. Unfortunately because of various phenomena, including the twist, it is not easy to identify a rotor. A few years ago, I created a program that allows to create a kind of signature for a rotor and thus to identify it even if its wiring comes from a cryptanalysis (see my Web page on rotors). In the following example, I inspect the wiring reconstructed by Elizebeth (ESMJRUOAHZDQBPVGLFITNXWYKC) with the wiring of the commercial Enigma rotor II in reverse mode (SEWYMGDLOIUBTXKVJPAFZCNHRQ). Although the wirings appear different, they have the same signature: [1, 11, 17, 1, 13, 19, 22, 7, 2, 19]. $ python3 signa_cgcs.py -R =ESMJRUOAHZDQBPVGLFITNXWYKC -p -r PI direct PI : ESMJRUOAHZDQBPVGLFITNXWYKC Signature: [1, 11, 17, 1, 13, 19, 22, 7, 2, 19] SHIFTS: [4, 17, 10, 6, 13, 15, 8, 19, 25, 16, 19, 5, 15, 2, 7, 17, 21, 14, 16, 0, 19, 2, 0, 1, 12, 3] CG&CS : 12(1),11(3),10(3),9(2),7(1),6(5),5(1),4(3),3(1),2(2),1(2),0(2), PI reverse PI : HMZKARPISDYQCUGNLEBTFOWVXJ Signature: [1, 11, 23, 4, 12, 10, 15, 16, 23, 18] SHIFTS: [7, 11, 23, 7, 22, 12, 9, 1, 10, 20, 14, 5, 16, 7, 18, 24, 21, 13, 9, 0, 11, 19, 0, 24, 25, 10] CG&CS : 12(1),11(5),10(5),9(2),8(1),7(2),6(1),5(2),4(4),3(1),2(1),1(1), $ python3 signa_cgcs.py -R =SLVGBTFXJQOHEWIRZYAMKPCNDU -p -r PI direct PI : SLVGBTFXJQOHEWIRZYAMKPCNDU Signature: [1, 11, 23, 4, 12, 10, 15, 16, 23, 18] SHIFTS: [18, 10, 19, 3, 23, 14, 25, 16, 1, 7, 4, 22, 18, 9, 20, 2, 9, 7, 8, 19, 16, 20, 6, 16, 5, 21] CG&CS : 12(1),11(5),10(5),9(2),8(1),7(2),6(1),5(2),4(4),3(1),2(1),1(1), PI reverse PI : SEWYMGDLOIUBTXKVJPAFZCNHRQ Signature: [1, 11, 17, 1, 13, 19, 22, 7, 2, 19] SHIFTS: [18, 3, 20, 21, 8, 1, 23, 4, 6, 25, 10, 16, 7, 10, 22, 6, 19, 24, 8, 12, 5, 7, 17, 10, 19, 17] CG&CS : 12(1),11(3),10(3),9(2),7(1),6(5),5(1),4(3),3(1),2(2),1(2),0(2), Rotor identification with Alan Turing classesA few months after inventing a method to identify a rotor, I discovered that Alan Turing used another method based on the concept of classes (see rotors). To calculate the class, you need to use two versions of the rotor wiring: either a wiring offset by one position or by two positions. Let's do the math.
Wiring : ESMJRUOAHZDQBPVGLFITNXWYKG -1 (RS,LM,...) RLIQTNZGYCPAOUFKEHSMWVXJBD -2 (KLM,HIJ,...) KHPSMYFXBOZNTEJDGRLVUWIACQ Let's calculate the permutation that allows you to go from wiring to wiring -1: (ERTMISL)(JQAGKBOZCDPUNWXVFHY). The class (type I) is 7.19. Let's calculate the permutation that allows us to go from wiring to wiring -2: (EKCQNUYAXWILGDZOFRMP) (SHBTVJ). The class (type II) is 6.20. If we read the article "Enigma Variations" by D.H. Hamer & all (see References), these classes correspond to the rotor II of the commercial Engima. Finding the message keyWe have just demonstrated that the fast rotor was rotor II of the commercial Enigma. It seems logical to deduce that the other rotors also come from the same machine. We can now consider finding the key to the messages received in-depth. All we have to do is take a column, for example the column N, of our encryption table and find the corresponding key. I have written a software to do this (scan_eD.py):
C:\> more MSGS\cry_N LJUXHZWDQXXBZHCEPQLSJVGJX C:\> more MSGS\pln_N NNNNNNNNNNNNNNNNNNNNNNNNN C:\> python scan_eD.py -c MSGS\cry_N -W D-I,D-III,D-II -R AAAA:AAAZ -M PLN -m MSGS\pln_N >> D-I,D-III,D-II D-UKW AAAB AAAA : 0.0800 - BBVKGNPKDUECGAOPVNAFKYTGR 2 0 mn 0 sec >> D-I,D-III,D-II D-UKW AAAK AAAA : 0.1200 - NBOKGRFCMHHWSGXVNDTNDBBVF 11 0 mn 0 sec ... >> D-I,D-III,D-II D-UKW AAAG FIAZ : 0.9600 - NNNNNNNNNNNNNNNNSNNNNNNNN 2426145 0 mn 33 secWe have found the key:
ETW: JWULCMNOHPQZYXIRADKEGVBTSF (reverse of QWERTZU...) I: LPGSZMHAEOQKVXRFYBUTNICJDW II: SLVGBTFXJQOHEWIRZYAMKPCNDU III: CJGDPSHKTURAWZXFMYNQOBVLIE UKW: IMETCGFRAYSQBZXWLHKDVUPOJN Reconstruction of the encryption tableSince we have found the encryption machine that was used to generate the traffic intercepted by the coast guards and we know the encryption key, it is possible to reconstruct the encryption table that appears on page 216 of the report... but without the gaps!
C:\> python eD.py
syntaxe: enigmaD.py UKW LEFT MIDDLE RIGHT ETW RING GRUND [Debug]
C:\> python -c "for i in range(84): print('Q',end='')" |
python eD.py D-UKW D-I D-III D-II D-ETW AAAG FIAZ
DIWKPLZENRZOBKUPBNCFLDPWWOMRNWKV
YSJPMVJIASDWIUZYZOIEOSICMUFCAAYK
BWXXFDNSCPXIHMXHJXPA
This encryption must be repeated for all letters of the alphabet, but in the order of the ETW input disk (QWERTZU...BNLM).
Q W E R T Z U I O A S D F G H J K P Y X C V B N M L 1 D V F B Y K H M C J G Q E S U A Z X T P O W R L I N 2 I B V O U H T Q R M L P X Y Z N C D G F K E W J A S 3 W Q C Z Y R N S L X I M V P B K J G T A E F H U D O 4 K G R E C B H M D P Y O L W U V Q A S N T J Z X I F 5 P B X C I S O T U F Z M A K N L G Q V E R Y W H D J 6 L K H O J N F B R G M Y U A E T W X D P V C I Z S Q 7 Z N F A Y Q C X D R J O E P L S V G T I U K M W B H 8 E I Q V M F J W P Y H N Z X S U B O A G L R K D T C 9 N Z G I S W L R H P T Y M E O K J A D V B X C Q F U 10 R G Z Q M E I U H V L C B W O Y P K J N D A F X T S 11 Z C O A U Q T L E R F P S J Y G V D H N W K M X B I 12 O M F G V H A C Q U P Y E R Z K J S D L I T N B W X 13 B X O V F N K G E L D S T I M P U J C W Y R Q Z H A 14 K G R E I M B T F D V A O W N C Q L X Y J S U H Z P 15 U H A L V O Q G Z E B K X I W Y D M J F N T S C P R 16 P B N H K O J F Z M Y L I V R U T Q S C X G W E A D 17 B R K W X V M C L G P J H A F D E S N T I Z Q Y U O 18 N G U B X D E A K I Y Z L W J H O M S T V C R Q P F 19 C R O W V B F D E M H I U P S Y X G J K Q T Z L A N 20 F E W I Z T A R B U N Y Q C V M X L D K G H O S J P 21 L V K P G U Z B Y S A M C T X N E R O H F W I J D Q 22 D S M I J K C R F H W Q O P A T Z G X Y U N L V E B 23 P T F C W K I U H D J A E N O S Z Q M L R B V G Y X 24 W Q D P U V T X H M L E Y B O N C R F I K Z G J A S 25 W Q A C J V H S G E I K M O U T D Y P N R Z L X F B 26 O Y B L D M F V Q C X T U K P N G H W S A I E J Z R 27 M N K L S O J C Z V T H P X D U E F B G I A Y W Q R 28 R P J Q L K A Y X U C N B M V E Z W I O S H F D G T 29 N M S T R U Z O I Y E P J K L F G D A B V C X Q W H 30 W Q D I G O J R Z Y C E M T L U B N A V S X K P F H 31 K J Z S B E C M G L R P H O F W Q D X Y U N T V I A 32 V R D W N F O A U I H E Z L S Y P K J B M Q X T C G 58 U G T S E B Q V H M R Y C W O P L J D N F I Z X A K 84 A R H W J B D L X Q M U G F E T C V N O K P Z Y S I ConclusionIt is interesting to note that in 1940, the Swiss army used the commercial Enigma using its original rotors. It is known that afterwards, frequently, the Swiss army changed the wiring of rotors I, II, III (the reflector remaining unchanged). We can also note the low cryptological skills of the Swiss army which issued more than 100 messages using the same key. This is a very serious error which allowed the Coast Guard to read the Swiss traffic. ReferencesBooks & Articles
Internet Links
|