Cryptanalysis of the Enigma

Cryptanalysis of the Enigma ciphering system enabled the western Allies in World War II to read substantial amounts of Morse-coded radio communications of the Axis powers that had been enciphered using Enigma machines. This yielded military intelligence which, along with that from other decrypted Axis radio and teleprinter transmissions, was given the codename Ultra.
The Enigma machines were a family of portable cipher machines with rotor scramblers. Good operating procedures, properly enforced, would have made the plugboard Enigma machine unbreakable to the Allies at that time.
The German plugboard-equipped Enigma became the principal crypto-system of the German Reich and later of other Axis powers. In December 1932 it was broken by mathematician Marian Rejewski at the Polish General Staff's Cipher Bureau, using mathematical permutation group theory combined with French-supplied intelligence material obtained from German spy Hans-Thilo Schmidt. By 1938 Rejewski had invented a device, the cryptologic bomb, and Henryk Zygalski had devised his sheets, to make the cipher-breaking more efficient. Five weeks before the outbreak of World War II, in late July 1939 at a conference just south of Warsaw, the Polish Cipher Bureau shared its Enigma-breaking techniques and technology with the French and British.
During the German invasion of Poland, core Polish Cipher Bureau personnel were evacuated via Romania to France, where they established the PC Bruno signals intelligence station with French facilities support. Successful cooperation among the Poles, French, and British continued until June 1940, when France surrendered to the Germans.
From this beginning, the British Government Code and Cypher School at Bletchley Park built up an extensive cryptanalytic capability. Initially the decryption was mainly of Luftwaffe and a few Heer messages, as the Kriegsmarine employed much more secure procedures for using Enigma. Alan Turing, a Cambridge University mathematician and logician, provided much of the original thinking that led to upgrading of the Polish cryptologic bomb used in decrypting German Enigma ciphers. However, the Kriegsmarine introduced an Enigma version with a fourth rotor for its U-boats, resulting in a prolonged period when these messages could not be decrypted. With the capture of cipher keys and the use of much faster US Navy bombes, regular, rapid reading of U-boat messages resumed. Many commentators say the flow of Ultra communications intelligence from the decrypting of Enigma, Lorenz, and other ciphers shortened the war substantially and may even have altered its outcome.

General principles

The Enigma machines combined multiple levels of movable rotors and plug cables to produce a particularly complex polyalphabetic substitution cipher.
During World War I, inventors in several countries realised that a purely random key sequence, containing no repetitive pattern, would, in principle, make a polyalphabetic substitution cipher unbreakable. This led to the development of rotor machines which alter each character in the plaintext to produce the ciphertext, by means of a scrambler comprising a set of rotors that alter the electrical path from character to character, between the input device and the output device. This constant altering of the electrical pathway produces a very long period before the pattern—the key sequence or substitution alphabet—repeats.
Decrypting enciphered messages involves three stages, defined somewhat differently in that era than in modern cryptography. First, there is the identification of the system in use, in this case Enigma; second, breaking the system by establishing exactly how encryption takes place, and third, solving, which involves finding the way that the machine was set up for an individual message, i.e. the message key. Today, it is often assumed that an attacker knows how the encipherment process works and breaking is often used for solving a key. Enigma machines, however, had so many potential internal wiring states that reconstructing the machine, independent of particular settings, was a very difficult task.

The Enigma machine

The Enigma rotor machine was potentially an excellent system. It generated a polyalphabetic substitution cipher, with a period before repetition of the substitution alphabet that was much longer than any message, or set of messages, sent with the same key.
A major weakness of the system, however, was that no letter could be enciphered to itself. This meant that some possible solutions could quickly be eliminated because of the same letter appearing in the same place in both the ciphertext and the putative piece of plaintext. Comparing the possible plaintext Keine besonderen Ereignisse, with a section of ciphertext, might produce the following:

Structure

The mechanism of the Enigma consisted of a keyboard connected to a battery and a current entry plate or wheel, at the right hand end of the scrambler. This contained a set of 26 contacts that made electrical connection with the set of 26 spring-loaded pins on the right hand rotor. The internal wiring of the core of each rotor provided an electrical pathway from the pins on one side to different connection points on the other. The left hand side of each rotor made electrical connection with the rotor to its left. The leftmost rotor then made contact with the reflector. The reflector provided a set of thirteen paired connections to return the current back through the scrambler rotors, and eventually to the lampboard where a lamp under a letter was illuminated.
Whenever a key on the keyboard was pressed, the stepping motion was actuated, advancing the rightmost rotor one position. Because it moved with each key pressed it is sometimes called the fast rotor. When a notch on that rotor engaged with a pawl on the middle rotor, that too moved; and similarly with the leftmost rotor.
There are a huge number of ways that the connections within each scrambler rotor—and between the entry plate and the keyboard or plugboard or lampboard—could be arranged. For the reflector plate there are fewer, but still a large number of options to its possible wirings.
Each scrambler rotor could be set to any one of its 26 starting positions. For the Enigma machines with only three rotors, their sequence in the scrambler—which was known as the wheel order to Allied cryptanalysts—could be selected from the six that are possible.

Left	Middle	Right
I	II	III
I	III	II
II	I	III
II	III	I
III	I	II
III	II	I

Later Enigma models included an alphabet ring like a tyre around the core of each rotor. This could be set in any one of 26 positions in relation to the rotor's core. The ring contained one or more notches that engaged with a pawl that advanced the next rotor to the left.
Later still, the three rotors for the scrambler were selected from a set of five or, in the case of the German Navy, eight rotors. The alphabet rings of rotors VI, VII, and VIII contained two notches which, despite shortening the period of the substitution alphabet, made decryption more difficult.
Most military Enigmas also featured a plugboard. This altered the electrical pathway between the keyboard and the entry wheel of the scrambler and, in the opposite direction, between the scrambler and the lampboard. It did this by exchanging letters reciprocally, so that if A was plugged to G then pressing key A would lead to current entering the scrambler at the G position, and if G was pressed the current would enter at A. The same connections applied for the current on the way out to the lamp panel.
To decipher German military Enigma messages, the following information would need to be known.
Logical structure of the machine

The wiring between the keyboard and the entry plate.
The wiring of each rotor.
The number and position of turnover notches on the rings of the rotors.
The wiring of the reflectors.

Internal settings

The selection of rotors in use and their ordering on the spindle.
The positions of the alphabet ring in relation to the core of each rotor in use.

External settings

The plugboard connections.
The rotor positions at the start of enciphering the text of the message.

Discovering the logical structure of the machine may be called "breaking" it, a one-off process except when changes or additions were made to the machines. Finding the internal and external settings for one or more messages may be called "solving" – although breaking is often used for this process as well.

Security properties

The various Enigma models provided different levels of security. The presence of a plugboard substantially increased the security of the encipherment. Each pair of letters that were connected together by a plugboard lead were referred to as stecker partners, and the letters that remained unconnected were said to be self-steckered. In general, the unsteckered Enigma was used for commercial and diplomatic traffic and could be broken relatively easily using hand methods, while attacking versions with a plugboard was much more difficult. The British read unsteckered Enigma messages sent during the Spanish Civil War, and also some [|Italian naval traffic] enciphered early in World War II.
The strength of the security of the ciphers that were produced by the Enigma machine was a product of the large numbers associated with the scrambling process.

It produced a polyalphabetic substitution cipher with a period that was many times the length of the longest message.
The 3-rotor scrambler could be set in 26 × 26 × 26 = ways, and the 4-rotor scrambler in 26 × = ways.
With L leads on the plugboard, the number of ways that pairs of letters could be interchanged was
*With L=6, the number of combinations was and with ten leads, it was .

However, the way that Enigma was used by the Germans meant that, if the settings for one day were established, the rest of the messages for that network on that day could quickly be deciphered.
The security of Enigma ciphers did have fundamental weaknesses that proved helpful to cryptanalysts.

A letter could never be encrypted to itself, a consequence of the reflector. This property was of great help in using cribs—short sections of plaintext thought to be somewhere in the ciphertext—and could be used to eliminate a crib in a particular position. For a possible location, if any letter in the crib matched a letter in the ciphertext at the same position, the location could be ruled out. It was this feature that the British mathematician and logician Alan Turing exploited in designing the British bombe.
The plugboard connections were reciprocal, so that if A was plugged to N, then N likewise became A. It was this property that led mathematician Gordon Welchman at Bletchley Park to propose that a diagonal board be introduced into the bombe, substantially reducing the number of incorrect rotor settings that the bombes found.
The notches in the alphabet rings of rotors I to V were in different positions, which helped cryptanalysts to work out the wheel order by observing when the middle rotor was turned over by the right-hand rotor.
There were weaknesses, in both policies and practice, in the way some Enigma versions were used.
Critical material was disclosed without notice.