Two researchers have introduced new techniques for breaking Enigma messages. Using these techniques they have deciphered hitherto unsolved Enigma cryptograms from World War II.
As is well known, Polish mathematicians Rejewski, Zygalski and Różycki were the first to break messages encrypted by the Germans with the Enigma.
Bomba and Cyclometer
The three Polish mathematicians even constructed two codebreaking machines named Cyclometer and Bomba in order to automize their cryptanalysis work.
The Polish mathematicians benefitted from a faulty key setting protocol the Germans used. Instead of using the key provided for a certain day to encrypt a certain message, German Enigma operators would choose a message key by random, encrypt it with the day key and send it as a prefix to the cipher message. To avoid transmission errors, the message key was encrypted and prefixed twice. This double key prefix turned out to be a serious mistake, as the Polish codebreaking machines could derive the day key from it.
Based on the Polish expertise, British codebreakers developed another codebreaking machine, the Bombe (also known as Turing-Welshman Bombe), which enabled them to read hundreds of thousands of Enigma messages during World War II.
Contrary to the Polish devices, the Bombe realized a guessed plaintext attack. The British codebreakers would guess a word in an Enigma message, e.g. WETTERVORHERSAGE, and configure it with a number of plugs on the backside of the machine. Subsequently, the Bombe automatically searched for a rotor setting that fit with this word.
In order to support their British colleagues, US codebreakers built a number of Bombes, too. Their task was to break the four-rotor Naval Enigma, which was especially hard to decipher.
After World War II breaking Enigma messages for military reasons soon became obsolete. Only in the 1990s crypto historians started new efforts to decipher Enigma cryptograms – of course, using a computer. In 1995 Jim Gillogly, a reader of this blog, described a new computer-based ciphertext-only attack on Enigma messages. He used an exhaustive search for all 60 wheel orders, 676 ring settings, and 17,576 wheel starting positions of an Enigma. However, this was not enough, as the Enigma (in most variants) also used a plugboard on the front side as a part of the key.
The Enigma plugboard can be configured in 150,738,274,937,250 ways, which is way too much for exhaustive search, especially as each plug combination must be tested with each wheel order, ring setting, and wheel starting position. As a solution, Jim searched for the plug combination with hill climbing, a technique I have mentioned a few times before on this blog.
The most important part of a hill climbing cryptanalysis is the fitness function. When Frode Weierud and Geoff Sullivan, two more readers of this blog, started their project “Breaking German Wehrmacht Ciphers“, they improved the fitness function used by Jim Gillogly. Their work proved to be successful, as they decrypted hundreds of messages from the Flossenbürg concentration camp and Hitler’s Soviet Union campaign “Unternehmen Barbarossa”. Details can be read in my book Nicht zu knacken – Von ungelösten Enigma-Codes zu den Briefen des Zodiac-Killers.
In spite of all the progress, breaking very short Enigma messages is still a problem. Israelian codebreaker George Lasry therefore included the breaking of short Enigma messages (less than 70 letters) in a list of unsolved crypto problems he presented last year in Kassel.
A few days ago, Frode Weierud and Olaf Ostwald published a paper titled Modern breaking of Enigma ciphertexts in the magazine Cryptologia. Frode and Olaf have developed a further improved fitness function for detemining the plug combination of an Enigma via hill climbing. With their method, the two could break hitherto unsolved Enigma messages, the shortest of which had only 32 letters. The following message from 1941 is a little longer (72 letters without the discriminant group), but still unbroken until recently: