0.8: Cracking the Enigma Machine
Polish Cryptanalysis of the Enigma Codes
In the years leading up to
WWII a somewhat simpler version of the Enigma was used by the Germans. It only
had 3 rotors and it had fewer plugboard connections. Even so, the following
description of the cryptanalysis has necessarily been extremely simplified,
leaving out some portions of the effort.
Before the outbreak of WWII,
Poland acquired technical documentation and certain setting information from
France who had an informant in the German military. The Polish used the
commercial version of the Enigma machine as a starting point for creating a copy
of the military version. A Polish mathematician, Marian Rejewski (pronounced
ray-ev-ski), worked with this data and was able to reconstruct the wiring of the
rotors. During WWI, only basic algebra and statistics was used in code breaking.
For the most part, linguists were employed as cryptanalysts. However, machines
like the Enigma required more advanced mathematical theory and the Polish were
the first to realise the necessity for mathematicians.
Rejewski used the
message settings sent to construct "chains". For example, if two message
settings, RWNGKS and GPQIBF were sent, he could begin a chain RGI, since he knew
from the documentation that the first and fourth ciphertext letters were the
same plaintext letters. With enough of these message settings to analyse, he
found that these chains would close on themselves. No chain was ever all 26
letters, instead there would be one of three groups of chains that included all
26 letters: two chains of length 13, six with lengths 10, 10, 2, 2, 1, and, 1,
or six with lengths 9, 9, 3, 3, 1, and 1. Using group theory to analyse these
chains, he discovered that he could ignore the plugboard in attempting to
determine the wiring of the rightmost (or fastest) rotor. Knowing the plugboard
settings would be important for recovering the plaintext, but for this part of
the cryptanalysis, one of the components that was relied upon for enhancing
security was irrelevant.
Once the wiring was discovered, there was still
the task of decoding messages. Theoretically, there were no flaws with the
security of the machine. However, practically, the operators introduced three
flaws that were important to cryptanalysts. The doubling of the message setting
was again useful and the fact that operators chose this setting also reduced the
security of the system. Initially, operators often chose repetitive keys such as
CCC, which was not only easier to guess, but increased the chances that two
operators would send messages with the same settings. Later, when this error in
strategy was discovered, operators were required to use no repetition. Even so,
their keys were not entirely random since they tended to choose letters nearby
on the keyboard, such as QWE. The third flaw was that many messages began with
An, German for To. In fact, the cryptanalysts found that one in
five messages began this way, which provided another valuable clue. These
factors made it possible for Rejewski and some assistants to come up with a
method that allowed them to decrypt messages in a day rather than 900 million
years, which is what would be needed on average for a properly implemented
enigma message.
The Polish cryptanalysts built machines called
bomby, to test possible keys. The machines tested for inconsistencies
that would eliminate keys and would stop when they found a key that was deemed
possible. Then, the cryptanalysts could try decoding the message. Even with some
swapped letters due to the plugboard, they could usually determine if it was a
valid German message or just gibberish. If it was the latter, they would start
the machine again to find the next possible key. Until 1938, this method was
extremely successful; the Polish had managed what neither the French nor the
British had even believed possible. But in 1938, the additional 2 rotor choices
were added and required 10 times as much equipment to test, for which the Polish
did not have the resources. In any case, shortly afterwards, Poland was invaded
and the cryptanalysts evacuated through Romania to France.
British Cryptanalysis of the Enigma Codes
Bletchley Park, the home
of British cryptanalytic efforts in WWII, took over the study of Enigma after
the outbreak of the war. Alan Turing, a mathematical genius, joined Bletchley
Park three weeks after they received technical documentation about the Polish
bomby. Turing devised a great improvement for the bomby, which the British
called bombe after the Polish name for the code breaking machines.
Turing matched a probable word or phrase of some length to an
intercepted message and had the bombe test if any rotor setting made this
encipherment possible. The Polish machines found non-contradictory links between
known and assumed keys. Turing's bombes found non-contradictory links between
assumed plaintext and assumed keys. This method had two advantages: it removed
the need for special conditions in message keys (repeated letters in certain
positions) which the Polish method relied upon and it allowed cryptanalysts to
exploit the human aspect of the messages. By using unencrypted radio traffic,
other solved ciphers, and other knowledge of German communication and movements,
they could deduce words and phrases likely to appear in messages.
The
British were able to continue using the mistakes of German operators to speed up
their tests as well. Message settings continued to be far from random: operators
picked letters close on the keyboard, the first letters of obscene words, or the
first letters of girlfriends names.
Another important improvement to the
bombe was made by Gordon Welchman. Welchman noted the reciprocal nature of the
Enigma cipher. If B was encrypted as Y, then Y was encrypted as B. He wired an
addition to the bombe so that this reciprocal relationship was accounted for in
the tests, thus reducing the number of erroneous stops.
Despite these
advances and others, Bletchley Park still found it nearly impossible to reliably
crack the Navy version of Enigma. The German navy may have been more strict
about message settings, but their machine also had eight, rather than five,
rotor choices. The wiring of these additional rotors was discovered through the
capture of a German ship, but decoding messages still relied on other lucky
circumstances. Often, identical messages were sent encoded in two different ways
since some less important ships did not have Enigma machines. If important
orders or news had to be sent to all ships, the operator would send an identical
message, not realising the danger. The British could crack one of the other navy
codes and used this information to help come up with suspected plaintexts to
crack Enigma messages sent at the same time. German weather ships provided much
in this department after the British laid their hands on the Short Weather
Cipher used to relay weather reports.
Throughout the war, the efforts in
cracking the Enigma and other ciphers were extremely useful as insights into
German plans. The Enigma intercepts came to be known by the codename ULTRA and
while they were perhaps not directly responsible for winning the war as
sometimes credited, the information provided by the Bletchley Park cryptanalysts
certainly shortened the war and saved many lives.
Kahn, David. 1991. Seizing the Enigma. Houghton Mifflin: Boston.
NEXT PAGE