Breaking of the Commercial Enigma by Germans

• Rejewski's break of the
  Enigma rotor wiring
• Elizebeth Friedman's break of the
  Enigma rotor wiring
• Breaking of the Commercial Enigma by Germans (This Page).
• Buttoning-up
• Adding-up
• Boxing
• Rodding
• Rejewski's Catalog
• Cyclometer
• Rejewski's Bombe
• Zygalski's Sheets
• Turing's Bombe
• Turing / Welchman Bombe

Introduction : TICOM DF-38

After the end of World War II, US cryptographic agencies investigated through German archives and questionned POW (Prisonner Of War) about German cryptogaphic methods. This organization was called TICOM (Target Intelligence COMmittee).

The documents produced by TICOM were tagged TOP SECRET. Recently, these documents were declassified and many of them can be downloaded on Internet.

There are different kinds of document: A, D, DF, I, IF, … "I" correspond to the Interrogation of a POW (written P/W too) and "DF" a translation of a German document.

The DF-38 document is written by Dr. Rudolf Kochendörffer, a Geman mathematician belonging to OKH/In 7/IV (a cryptologic service of the Army). This document deals with the mathematical analysis of the commercial Enigma using permutations (like report written by Rejewski). This analysis allows the author to indicate how to recover the rotor wiring from in-depth messages.

According to Frode Weierund (the editor of this document), the report from which document DF-38 comes dates back to 1944.

The structure and the content of the DF-38 document

The structure of DF-38

1. Description of the Enigma
   
   1. The cipher wheels
   2. The wiring of a sequence of two wheels
   3. The turning of a wheel
   4. The reversing wheel
   5. The operation of the Enigma
2. Determining the wiring of an Enigma from a sequence of T26 (substitution alphabets)
   1. Cryptanlytic foundation.
   2. Theorical calculation of the wheel wiring.
   3. Practical calculation of the wheel wiring.

The Content of DF-38

• Description of the Enigma
  The great originality of Dr. Rudolf K.'s article is to use the mathematics of permutations that belong to the group theory of which he was a specialist. He begins with a summary of this part of mathematics, a bit equivalent to the Wikipedia web page on permutations: notation, composition, associativity, inverse permutations, identity, ... (cf. References).

  Then, the Enigma encryption formula is presented (cf. the following paragraph). The first part ends with the description of the advancement of the rotors.

• Determining the wiring of an Enigma
  The second part explains how to find the wiring of the rotors from in-depth messages and the permutations that describe the Enigma.

Mathematical vision of the Enigma encryption

The Dr. Rudolf K. (like Rejewski) used group theory and more specifically permutations to describe the Enigma encryption. Consider the following permutations:

• P = Permutation of the Enigma with the rotor positions at k (for right rotor), l (for middle rotor) and m (for left rotor).
• A = Permutation of the Rotor at the right position (the fast rotor)
• B = Permutation of the middle rotor
• C = Permutation of the left rotor
• U = Reflector permutation
• Z = Permutation of the rotation.

Note: In this formula, the input permutation, which can be the Qwertzu of the commercial Enigma or the steckers of the military Enigma, is not taken into account. Indeed, this permutation is fixed and must be known to the cryptanalyst. It is easy to eliminate it from the plaintext and the ciphertext, and ultimately we can ignore it from our reasoning.

In this Web Page, we have not used the same conventions as Dr. Rudolf. Indeed, we believe his method is almost equivalent to Turing's Boxing method. Consequently, we have used the same notation as in our page describing this method Boxing.

Moreover, we will use our Simplified Enigma view but with two rotors.

• E = Permutation of the Enigma with the rotor positions at i (for right rotor), and j (for middle rotor).
• N = Permutation of the Rotor at the right position (the fast rotor)
• M = Permutation of the middle rotor
• U = Reflector permutation (which includes the permutation of the left rotor)
• P = Permutation of the rotation.

Here is the correspondence between Dr Rudolf's conventions and mine:

• P = Permutation of the Enigma with the rotor positions at x = j * m + i + 1. Where i is the position of the right rotor, j the position of the middle rotor, and m the number of contacts (here 6, but in the real Enigma, m = 26). In this page, E is used instead of P.
• A = Permutation of the Rotor at the right position (the fast rotor) : N here.
• B = Permutation of the middle rotor . Here, it is M.
• C = Permutation of the left rotor. Here, this permutation is included into U.
• U = Reflector permutation. CUC**-1 is equivalent to U in this web page.
• Z = Permutation of the rotation. Here, it is P.

Cryptanalytic and true reconstruction of the Enigma

The cryptanalysis made by Dr.K. does not allow an exact description of the rotors due to the twist and offset effects (cf. rotor).

In fact, in the header of the enemy messages the indicator contained the initial position of the rotors. In addition, this position corresponded to a pronounceable four-letter word. Thanks to this, the real wiring of the rotors could be reconstructed.

Reconstruction of the Fast Rotor Wiring - Theory

The general approach to finding the Enigma's wiring

In the general formula stated above, each permutation of the Enigma is related to the position of the rotors. Here are the results for two consecutive positions.

\( E_{00} = N(MUM^{-1})N^{-1} \)
\( E_{01} = (PNP^{-1})(MUM^{-1})(PN^{-1}P^{-1}) \)
We note that E, for positions which follow each other, only depends on the fast rotor N. With other similar formulas, we can find N.

If we then know N, we can create sequences Q that depend only on M.

If we pose: \( Q_{0,0} = N^{-1} E_{0,0} N = MUM^{-1} \)
Then: \( Q_{1,0} = N^{-1} E_{1,0} N = PMP^{-1}UPM^{-1}P^{-1} \)

We can therefore deduce M and then U (in the real Enigma, we can also find the left rotor).

The X permutation

If we pose: \( X = N \; P \; N^{-1} \; P^{-1} \)
We pose also: \( Y = X^{-1} = P \; N \; P^{-1} \; N^{-1} \)
We get: \( E_{01} = Y \; E_{00} \; Y^{-1} \)

Note: I didn't understand the demonstration of the equation which links \( E_{00} \: and \: E_{01} \).

After a complete revolution of the fast rotor we obtain a similar formula.

Finally, we have three equations from which we can find X:

1. \( E_{01} = Y \; E_{00} \; Y^{-1} \)
2. \( E_{11} = Y \; E_{10} \; Y^{-1} \)
3. \( E_{21} = Y \; E_{20} \; Y^{-1} \)

In general : \( E_{m+1,i+1} = Y \; E_{m,i} \; Y^{-1} \)
The value m = n * v, with n being the number of rotor contacts.

X and the fast rotor wiring (N)

We can create an equation from which we can find N.

\( X = N \; P \; N^{-1} \; P^{-1} \) Then
\( X \; P = N \; P \; N^{-1} \; P^{-1} \; P \) Then
\( X \; P = N \; P \; N^{-1} \)

Conclusion

We see that Dr. Rudolf's method is very similar to Turing's Boxing method. Indeed, Dr. Rudolf's X-permutation is simply the inverse of Turing's gamma permutation. The main difference between the two methods is that Turing uses the concept of Box, and Dr. Rudolf uses alphabets directly. In my opinion, using Boxes greatly speeds up calculations but is not theoretically necessary.

Reconstruction of the Fast Rotor Wiring - Pratice

Introduction

Dr. Rudolf's method allows, at a minimum, the reconstruction of the wiring of the right rotor (the fast rotor) and the middle rotor. Under good conditions, it allows the reconstruction of the wiring of all the rotors and the reflector. The Qwertzu is supposed to be known and correspond to the Qwertzu of the commercial Enigma.

In this section, we are only interested in the reconstruction of the right rotor (the fast rotor).

The data collected

By listening to the enemy traffic, the Germans realized that it was in-depth messages originating from an Enigma machine. From these in-depth messages, the Germans deduced the plaintext of the messages and ultimately the substitution alphabets for several positions of the Enigma rotors.

Note: The fact that the enemy indicated the external key as an indicator was a great help in verifying the in-depth aspect of the messages.

• E00 = ((1,0)(2,5)(3,4)) N at position 0 and M at position 0.
• E01 = ((0,4)(1,5)(2,3)) N at position 1 and M at position 0.
• E10 = ((0,5)(1,3)(2,4))
• E11 = ((0,2)(1,4)(2,4))
• E20 = ((0,3)(1,4)(2,5))
• E21 = ((0,1)(2,3)(4,5)) N at position 1 and M at position 2.

Notes:

• Elizebeth Friedman followed the same reasoning and (presumably) intercepted the same traffic (see link).
• Let us give the correspondence between our notation and that of Dr. Rudolf:
  \( E_{0,0} == P_1, \; E_{0,1} == P_2, \; E_{1,0} == P_{27}, \; E_{1,1} == P_{28} \)

Calculate the X permutation

We have two equations from which we can deduce the permutation X.
If we pose: \( Y = X^{-1} \)

1. \( E_{01} = Y \; E_{00} \; Y^{-1} \)
2. \( E_{11} = Y \; E_{10} \; Y^{-1} \)

We know E00 and E01. If we want to find the X permutation, we just put E00 under E01 and assume that it is the encryption of E01.

Unfortunately, for each pair E01/E00, there are several solutions. In fact there are 12 solutions (n = 2 * 3!, cf. rotors). Let's give three solutions:

     E01  = ((0,4)(1,5)(2,3))        ((0,4)(3,2)(1,5))       ((0,4)(1,5)(2,3))	
     E00  = ((0,1)(2,5)(3,4))        ((0,1)(2,5)(3,4))       ((4,3)(1,0)(2,5))
     Ya1  = ((0)(4,1,2,3)(5))  Ya2 = ((0)(4,1,3,2,5))  Ya3 = ((0,4,3,5)(1)(2))   ...

For the E10/E11 pair, there are also 12 solutions, among them, there are:

     E11  = ((0,2)(1,4)(3,5))        ((0,2)(4,1)(3,5))       ((0,2)(1,4)(3,5))
     E10  = ((0,5)(1,3)(2,4))        ((0,5)(1,3)(2,4))       ((4,2)(1,3)(5,0))
     Yb1  = ((0)(2,5,4,3)(1))  Yb2 = ((0)(2,5,4,1,3))  Yb3 = ((0,4,3,5)(2)(1))   ...

The correct solution must be common for each pair (E00/E01 and E10/E11). Unfortunately there are still 6 solutions common to the two pairs (including Ya2 and Ya3):

• (0)(4,1,3,2,5)
• (0,4,3,5)(1)(2)
• (0,1,5,2,3,4)
• (0,2,4,5,1)(3)
• (0,3)(1,2)(4)(5)
• (0,5,3,1,4,2)

Fortunately, X can also be calculated from E20 and E21:

     E21  = ((0,1)(2,3)(4,5))        ((0,1)(2,3)(4,5))        ((0,1)(2,3)(4,5)) 
     E20  = ((0,3)(1,4)(2,5))        ((0,3)(2,5)(1,4))        ((0,3)(5,2)(1,4))  
     Yc1  = ((0)(1,3,4,2)(5))  Yc2 = ((0),(1,3,5,4)(2)) Yc3 = ((0)(1,3,2,5,4))   ... 

The correct value of Y is then ((0)(4,1,3,2,5)) which corresponds to Ya2, Yb2 and Yc3. This is the only solution common to all three pairs (E00/E01, E10/E11 and E20/E21). Then X is equal to the reverse permutation ((0)(5,2,3,1,4)).

Important note: number of Alphabet pairs required

Manuel Vázquez & Paz Jiménez–Seral pointed out my error. They also pointed out the link between Rejewski's solution, the Boxing method, and Dr. Rudolf's method: to find the permutation N corresponding to the fast rotor, several alphabets are required, at least five. As you can see, an alphabet corresponds to the permutation of an Enigma at a particular rotor position. But furthermore, when using pairs of alphabets (like Turing or Dr. Rudolf), at least three pairs are required, therefore at least six alphabets (complete or partial). As a reminder, Rejewski found the wiring of the fast rotor from the five alphabets A, B, C, D, E (but he calculated six: A to F).

Reconstitution of the permutation N (the fast rotor)

If we take the formula which links X to the rotor wiring (N) we have:

\( X \; P = N \; P \; N^{-1} \)

We have a conjugation, so we can calculate N as we did previously for calculation of X. We obviously have several solutions, for example:

	X * P = ((0,1,5,3,2,4))
	P     = ((0,1,2,3,4,5))
	N0    = ((0)(1)(5,2,4)(3))

>>> X = Permutation(0)(5,2,3,1,4)
>>> P
Permutation(0, 1, 2, 3, 4, 5)
>>> X * P
Permutation(0, 1, 5, 3, 2, 4)
>>> N0 = Permutation([[0],[1],[5,2,4],[3]])
>>> X * P == N0 * P * ~N0
True
>>>

Verification (a posteriori) of the formula linking X and E

With Sympy:

>>> E00
Permutation(0, 1)(2, 5)(3, 4)
>>> E01
Permutation(0, 4)(1, 5)(2, 3)
>>> N.full_cyclic_form
[[0], [1], [2, 4, 5], [3]]
>>> X = N * P * ~N * ~P
>>> E01 == ~X * E00 * X
True
>>> E11 == ~X * E10 * X
True

Origin of the traffic analyzed: the Swiss hypothesis

The report by Dr. Rudolf K. aims to show how to find the wiring of a commercial Enigma from in-depth messages. But where does this traffic come from?

I think it comes from the Swiss army. Indeed, we know that the Swiss were equipped with Commercial Enigmas. On the other hand, that at least at the beginning of their use, dozens (or even hundreds) of messages were sent with the same key (in-depth messages). On the other hand, the reflector had not been modified (This is the case of the machine analyzed by Dr. Rudolf K.). Finally, we know that the Germans deciphered the Swiss Enigma traffic. All these clues together lead us to deduce that the messages analyzed by Dr. Rudolf K. come from the Swiss army.

Christos' article (see References) describes the breaking of the Swiss Commercial Enigma by several countries, including Germany. It so happened that it was precisely the OKH/In 7/VI service, to which Dr. Rudolf K. belonged, which was responsible for analyzing Swiss traffic. Still in Christos' article, we learn that Originally the indicator (showing the starting position of the rotors) was sent in the clear but from August 1942 it was enciphered (see below). As far as I am concerned, this last clue convinces me that it is indeed a Swiss traffic that is handled by Dr. K.

The American Coast Guard, in 1940, were confronted with the a Commercial Enigma whose traffic had the same characteristics and it was indeed traffic of Swiss origin (link).

We are not certain about the origin of the messages but we can say that the cryptologists who created the encryption procedures used were not experts. Indeed, two major mistakes were made:

• Sending several dozen in-depth messages. This is the main mistake. No system can resist it.
• Sending the rotors' position in plain text. This procedure alone could have jeopardized the system. The indicator must be encrypted!

Acknowledgements

I would like to thank Manuel Vázquez & Paz Jiménez–Seral for enlightening me on several elements concerning the mathematics of the Enigma.

References

Internet links

• The Enigma Collection, Editor: Frode Weierud.
  DF-38, The Enigma by Dr. Rudolf Kochendörffer. (link).
• Wikipedia: Permutation
• Christos military and intelligence corner.
  The compromise of the Swiss diplomatic Enigma K cipher machine in WWII (link)