Enigma/Key Length

Much discussion of cryptography involves the key length used in encryption algorithms, as this directly influences the security provided by the algorithm. For modern computerised encryption algorithms like RSA or AES, the key length is expressed as a number of bits in a binary representation of the number given as the key. For an Enigma machine, which doesn't use binary and doesn't have a single number as a key, it's a lot harder to determine what the effective "key length" is.

An Enigma machine's "key" is a combination of various machine settings applied before enciphering of the message:

• The reflector selection
• The rotor selection
• The ring settings on the rotors
• The plug board connections
• The indicator settings

Different models of Enigma machine have different numbers of possibilities for these selections (non-military ones have no plug board, for instance) so the key length calculation will be different for each model. The overall "key length" can be determined by multiplying the number of possibilities for each of these settings together, and taking the logarithm in base 2 of the result to give the number of bits in a theoretical binary representation.

Calculating the number of possible plug board settings

The plug board was used on German military machines to exchange connections of pairs of letters on the keyboard and lamp board. Before World War II varying numbers of jumper connections were used, but latterly they standardised on 10. The machine however is capable of using any number of connections from 0 to 13 (maximum number of pairs in 26 letters).

Working out the total number of possible combinations turns out to be somewhat complex (I initially tried to work this out myself and got it wrong, Ralph Simpson of ciphermachines.com kindly set me straight). Each arrangement with a certain number of jumpers is distinct from every arrangement with a different number of jumpers, so we calculate the combinations for each possible number of jumpers separately, then add them together. For each number of jumper connections, we calculate how many ways there are to divide the set of 26 letters into sets of jumpered letters and unjumpered letters. Then for the jumpered letters we calculate how many different ways they can be arranged in pairs. We then multiply the number of possible set divisions by the number of possible pairings to give the total number of possible settings with that number of jumpers.

Mathematically, the number of possible divisions is a k-Combination, C(26,k) where k is the number of jumpered letters; the number of possible pairs within k jumpered letters is a double factorial (k-1)!! .

Enigma M4

This model included a plug board, and used a thin reflector and an extra thin rotor taking the place of the normal reflector on a three-rotor Enigma M3 to increase the number of possible settings, so this will have a longer "key length" than many other models.

Settings Contributing to Effective Key Length

Reflector selection

There were two possible reflectors, "Thin B" or "Thin C".

Rotor selection

There were two possible rotors for the thin left-hand position ("Beta" and "Gamma"). The three other rotors were chosen, in any order, from a possible eight supplied with the machine (numbered "I" to "VIII"). This gives a total of 2*8*7*6 = 672 possibilities.

Ring settings

Each of the four rotors could have its outer ring rotated through 26 positions to change the alignment of the internal wiring. This gives 26*26*26*26 = 456,976 possibilities.

Plug board connections

Any number of jumpers (j below) from 0 to the maximum 13 with every letter connected to another could be used:

j	C(26,2j)	(2j-1)!!	Result
0	1	1	1
1	325	1	325
2	14,950	3	44,850
3	230,230	15	3,453,450
4	1,562,275	105	164,038,875
5	5,311,735	945	5,019,589,575
6	9,657,700	10,395	100,391,791,500
7	9,657,700	135,135	1,305,093,289,500
8	5,311,735	2,027,025	10,767,019,638,375
9	1,562,275	34,459,425	53,835,098,191,875
10	230,230	654,729,075	150,738,274,937,250
11	14,950	13,749,310,575	205,552,193,096,250
12	325	316,234,143,225	102,776,096,548,125
13	1	7,905,853,580,625	7,905,853,580,625
Total possibilities			532,985,208,200,576

Indicator settings

At the start of the message, the operator would turn the rotors so that a particular set of letters (or numbers on some models) were visible in the windows. Although this is part of the message key, it only adds any cryptographic complexity if the particular rotor being turned affects the stepping of the next rotor along; this is because the notches which control stepping and the indicator are both on the outer ring, whereas the internal wiring is on the inner part of the rotor and the 26 possible positions of that are already accounted for above in the "Ring settings" section. Therefore, only the indicator settings of the two right-hand rotors contribute to the effective key length, giving 26*26 = 676 possibilities.

Calculated Effective Key Length

Multiplying all these possibilities together (as they are all set independently) gives a total of:

2 * 672 * 456,976 * 532,985,208,200,576 * 676 = 221,286,292,668,406,558,235,295,744 possible keys

Log₂ of 2.213e26 is 87.52, so the effective key length of an Enigma M4 machine is between 87 and 88 bits, compared to today's typical 128-bit encryption of e-commerce web pages.

It's interesting to note that more than half that key length is due to the plug board settings (log₂ of 5.330e14 being 48.92) and that the plug board's part in the algorithm is a fixed substitution cipher; such ciphers are very susceptible to cryptanalysis using letter frequency counts, so the security provided is likely to be quite a bit less than this calculated effective key length suggests (not to mention the weakness of a letter never encrypting to itself, but that's another story!)

Further Reading

Miller, A. Ray (1995)

The Cryptographic Mathematics of Enigma, NSA Center for Cryptologic History