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