Enigma is the name of a family of ciphering machines made famous by their use in World War II and the successful analysis of the cipher by Allied codebreakers. This article discusses the techniques for solving Enigma and the circumstances in which they were developed and applied. See Enigma machine for a description of the machine itself, and Ultra for a discussion of the intelligence gained from reading Enigma.

Strengths of Enigma

By the opening of World War I, national codebreaking agencies were often able to break the majority of ciphers given enough time. However, most direct cryptanalytic techniques used relied on gaining access to sufficient quantities of text enciphered with a particular key, from which patterns might be discerned with statistics and hard work. Enigma, like other rotor machines, was designed to defeat these basic cryptanalysis techniques by continually changing the substitution alphabet.

Enigma generated a long sequence of substitution alphabets, different for any given set and ordering of rotors. For example, with three single-notched rotors, the period of the machine was 16,900 (26 × 25 × 26). The long period helped protect against overlapping alphabets.

The Enigma machines added other possibilities. The sequence of alphabets used was different if the rotors were started in position ABC, as opposed to ACB; there was a rotating ring on each rotor which could be set in a different position, and the starting position of each rotor was also variable. And most of the military Enigmas added a plugboard (German Steckerbrett) which exchanged letters. Even so, this complex combination 'key' could be easily communicated to another user, being only a few simple values: rotors to use, rotor order, ring positions, starting position, and plugboard settings. Potentially, this made the Enigma an excellent system.

Involution

The fact that encryption was the same operation as decryption was, at the time, considered to be an advantage of the Enigma. The most common versions were symmetrical in the sense that decipherment works in the same way as encipherment — when one types in the ciphertext the sequence of lit lamps corresponds to the plaintext. However, this works only if the deciphering machine has the same starting configuration (that is, rotor choice, sequence, alphabet ring settings, and initial positions) as had the encrypting machine. These changed regularly (at first monthly, then weekly, then daily and even more often toward the end of the War on some networks) and were specified in key schedules distributed to Enigma users.

Security properties

The various versions of Enigma provided different levels of security. The presence of a plugboard (stecker) significantly increased the complexity of the machine. In general, unsteckered Enigma could be attacked using hand methods, while breaking versions with a plugboard was more involved, and often required the use of machines.

The Enigma machine had a number of properties that proved very useful to cryptanalysts. Firstly, a letter could never be encrypted to itself (with the exception of the early models A and B, which lacked a reflector). This was of great help in finding cribs — short sections of plaintext that are known (or suspected) to be somewhere in a ciphertext. This property can be used to help deduce where the crib occurs. For a possible location, if any letter in the crib matches a letter in the ciphertext at the same position, the location can be ruled out; this was termed a crash at Bletchley Park.

Another property of the Enigma was that it was self-reciprocal: encryption is performed identically to decryption. This imposed constraints on the type of scrambling that Enigma could provide at each position, and the property was used in a number of codebreaking methods.

A weakness in many versions of the Enigma was that the rightmost wheel would rotate a constant number of places before the next would rotate. The United States military had earlier (early 1920s) declined to use the Hebern rotor machine in part for this reason, which had been observed by William F. Friedman.

Besides less than ideal inherent characteristics of the machine, the way in which Enigma was used — that is, as a cryptosystem — proved to be the greatest weakness in practice. Mistakes by operators were common, and many of the officially specified procedures for using Enigma provided a variety of avenues for attack. It has been suggested, by some of those working on its cryptanalysis at Bletchley Park, that the Enigma would have been unbreakable had its operators not been so error prone, and had its prescribed procedures been better designed.

History of solution

Pre-World War II

The commercial Enigma machine was good, but not good enough. Further weakening of its cryptography was due to negligent German operators eavesdropped by keen foreign cryptanalysts. The British are said to have broken some messages when it was used in Spain during the Civil War there, and also to have read some Italian traffic encrypted with one of the commercial versions early in WWII (see Ultra). However, when the German Navy began using Enigma in the mid-1920s, decryption of their messages was impossible in practice, as it was also when the German Army began to use a slightly different version in the early 1930's. Reportedly, both British cryptanalysts of the GC&CS (Government Code and Cipher School) and French cryptanalysts gave up, regarding the German military Enigmas as unbreakable. Until 1945 there were numerous enhancements of the system despite the fact that it was considered unbreakable for all practical matters by the Germans, or considered clearly the least probable cause for the suspiciously high Allied battle success rate at some points.

The effort which broke the German military Enigma more or less began in 1929 when the Poles intercepted an Enigma machine being shipped from Berlin to Warsaw which was mistakenly not protected as diplomatic baggage. It was not one of the military versions, as only the German Navy used the Enigma at the time, but it provided a hint about the German intentions. When the German Army first began using modified Enigmas a few years later, the Poles suspected an Enigma or something similar was being used and attempted to break the system by finding the wirings of the rotors used in the Army version and by finding a way to recover the key (ie, ground settings) used for particular messages.

A young Polish mathematician, Marian Rejewski, made one of the most significant breakthroughs in cryptanalytic history by using techniques from pure mathematics to find a way to do both. Rejewski noticed a pattern that was to prove vital; the indicator procedure was to encrypt an operator-selected message setting twice using a ground setting, and prepend it to their message.

For instance, if an operator picked QRS as their 'message setting', the operator would set the machine to the day's ground settings, and then type QRSQRS. This might be encrypted as JXDRFT. The feature of Enigma that Rejewski exploited was that the disk moved three positions between the two sets of QRS — knowing that J and R were originally the same letter, as were XF and DT, was vital information. Although the original letters were unknown, it was known that, while there were a huge number of rotor settings, there were only a small number of rotor wirings that would change a letter from J to R, X to F and D to T, and so on. Rejewski called these patterns chains. Since the Poles had worked on Enigma from 1928 on, they became very experienced to exploit even very subtle cryptological mistakes the Germans made. A blatant one, however, was the printing of a complete set of plaintext-key-ciphertext as a training example in an early enigma manual, a copy of which Rejewski managed to put his hands on.

Finding the proper chains from the 105,456 possibilities was a tremendous task. The Poles, particularly Rejewski's classmates Jerzy Różycki and Henryk Zygalski, developed a number of methods. One technique used clear strips for each rotor showing which letters could be chained, with the letters that could not chain being blacked out. Users would pick up the strips and lay them over each other, looking for selections where the three letters were clear all the way through. The British had also developed such a technique when they succeeded in breaking the common commercial Enigma, though they failed to break the military versions of the Enigma.

Replica of a bombe machine

Of course, thousands of possibilities represent a vast amount of work to analyze by hand. To help with this, the Poles eventually built several machines which they called the bomba kryptologiczna ("cryptologic bomb"): the name originated from the characteristic muffled noise it produced when operating; alternative names puckishly given the device by Polish Cipher Bureau personnel were "washing machine" and "mangle." The French and British later modified the spelling, in conformity with their respective languages, to "bombe" and "bomb." Rejewski has written about the device: "The bomb method, invented in the fall of 1938, consisted largely in the automation and acceleration of the process of reconstructing the daily keys. Each cryptological bomb (six were built in Warsaw for the Cipher Bureau before September 1939) essentially constituted an electrically powered aggregate of six Enigmas. It took the place of about one hundred workers and shortened the time for obtaining a key to about two hours." (Rejewski, in Kozaczuk, Enigma 1984, p. 290.)

The Poles were able to determine the wiring of the rotors then in use by the German Army and, using them, to decrypt a large portion of German Army traffic for much of the 1930s — until the beginning of WWII. They received some secret assistance from the French, who had an agent (Hans Thilo-Schmidt, codenamed "Asche" by the French) in Berlin who had access to some Enigma key schedules, manuals, etc.

However, in 1939 the German Army increased the complexity of their Enigma use. They had initially distributed only three rotors, and simply moved them around in the slots, but they now introduced an additional two rotors, thus using any three out of five at any particular time. They also had their operators stop sending the individual three letter message settings twice at the beginning of each message, which eliminated the original method of attack.

Polish counterintelligence had been reading Enigma since early 1933, after which, however, the many modifications of the machine and its operation lead to several "blackouts", before the Poles/Allies gradually caught up in intervals. In April and May 1939 Poland entered into military alliances with Britain and France, respectively. The Poles, realizing the pace and the direction of the changes in political situation in Europe decided in mid-1939 to fully share their work, and passed to the French and the British some of their ersatz 'Enigmas', information on Rejewski's breakthrough, and on the other techniques they had developed, including the bomba's. The French share was shipped to Paris in diplomatic baggage; the British share went on to Bletchley Park. Until then, German military Enigma traffic had utterly defeated both the British and French, and they had faced the disturbing possibility that German communications would remain "black" for the entire war.

Nearly all the personnel of the Biuro Szyfrow left Poland during the invasion, and most ended up in France working with French cryptographers on German transmissions. Some Polish crypto workers were captured by the Germans before they could leave Poland or while in transit, but fortunately none of them revealed any of the Enigma work. It continued in France at 'Station PC Bruno' until the fall of France (and even somewhat after). Alan Turing came to station Bruno for several days in January 1940 to receive latest information by fellow mathematician Rejewski. Some of the French/Polish workers then managed to escape to England; none were used to help the British cryptanalytic effort against the Enigma networks. Instead they set up their own decryption center in Boxmoore, reading German and Russian traffic.

When Rejewski himself learned (shortly before his death) of the work at Bletchley Park which he had begun in Poland in 1928, and of its importance to winning WWII, he was astonished.

See also: Perforated sheets

During the war

British attacks on the Enigmas were similar in concept to the original Polish methods, but based on different specifics. First, the German Army had changed their practices (more rotors, different 'message setting', etc.), so the Polish techniques no longer worked without modification. Second, the German Navy -- with whom the Poles had not much concern -- had always used more secure procedures, and no one had broken any of their traffic. Alan Turing, the chief of Hut Eight -- Naval Enigma -- at Bletchley Park, made important contributions here as did Gordon Welchman the head of Hut Six.

One new attack relied on the fact that the reflector (a patented feature of the Enigma machines) guaranteed that no letter could be enciphered as itself. This was combined with knowledge of various common German phrases, like "Heil Hitler" or "please respond", which were found to frequently be in this or that plaintext; successful guesses as to the plaintext were known at Bletchley as cribs. With a probable plaintext fragment and the knowledge that no letter could be enciphered as itself, it wasn't uncommon that a corresponding ciphertext fragment could be guessed by trying every possible alignment of the crib against the ciphertext, a procedure known as crib dragging. Out of the possible guesses, some would turn out to be true plaintext/ciphertext pairs. This provided a large hint as to the message settings, much in the same way the message setting codes had done for the Poles before the War started.

One of Turing's main contributions to the british bombe relied on probable-plaintext-attacks: Assume you find a triple loop, e.g. abc. That means that with a crib you find plaintext letter a mapped to cipher b, plain b to c, and plain c to cipher a again within short distance (ideally plain: abc, cipher: bca ). Now assemble the rotor mechanisms of three enigmas serial-in-line and set it to the original rotor positions, with their offset (here 1 step each) accordingly. Then you get a corresponding physical wire closed loop. You can detect this with lamps connected to the rotor contacts. The lamp in the wire loop will stay dark. Now you turn the rotor systems synchronously. If only one lamp stays dark because of the one wire loop, you can quickly calculate the Steckerfeld, and reject those positions with all lamps lit. However, this typically happens several times in 17000 permutations.

German operators themselves also gave the decrypters immense help on a number of occasions. In one instance an operator was asked to send a test message, so he simply hit the T key repeatedly and sent it. A British analyst received a long message without a single T in it from the interceptor stations, and immediately realised what had happened. In other cases, Enigma operators would constantly use the same settings for their message codes, often their own initials or those of their girlfriends (so called "cillies" after an operator with the appearent initials C.I.L. ). Analysts were set to finding these messages in the sea of intercepted traffic every day, allowing Bletchley to use the original Polish techniques to find the initial settings for the day. Other German operators used "form letters" for daily reports, notably weather reports, so the same crib could be used every day. Later in the war the codebreakers learned to fully exploit the crucial security failure associated with the German weather reports: they were broadcast from weatherships to Germany in lower level code, easy to decipher, and then they were retransmitted to U-boats at sea encoded by Enigma, thus giving the decoders a regular crib.

Had the Germans ever replaced every rotor at the same time, it is possible that the British would not have been able to break back into the system. However, both because of the expense and because of the difficulty of getting all those new rotors to all the necessary ships and units, it was never done. Instead the Germans simply added new rotors to the mix every so often, allowing the settings of the newest ones to be deciphered after a short period.

On 7 May 1941 the Royal Navy deliberately captured a German weather ship, together with cipher equipment and codes. They did it again shortly afterwards. And, 2 days later U-110 was captured, together with an Enigma machine, code book, operation manual and other information. Naval Enigma was readable through the end of June.

In addition to U-110, Naval Enigma machines or settings books were captured from a total of 7 U-boats and 8 German surface ships, including U-boats U-505 (1944), and U-559 (1942), as well as from 2 German weather-reporting boats, from some converted trawlers, a small vessel (the Krebs) captured during the raid in the Lofoten Islands off Norway, and so on. Several other more imaginative techniques were dreamed up, including Ian Fleming's suggestion to "crash" captured German bombers into the sea near German ships, hoping to be "rescued" by the crew, which would then be taken captive by the Commandos hiding in the plane and the crypto material captured intact.

However, like the Polish system, the new tricks only reduced the number of possible settings for a message. The number remaining was still huge, and due to the new rotors the Germans had added from time to time, that number was much larger than the Poles had been left with. In order to solve this problem the Allies, especially the US, "went industrial", and produced much larger versions of the Polish bomba that could test thousands of possible key settings very rapidly indeed.

By 1945 almost all German Enigma traffic (Wehrmacht, Kriegsmarine, Luftwaffe, Abwehr, SD, etc.) could be decrypted within a day or two, yet the Germans remained confident of its security. They considered Enigma traffic sufficiently secure that they openly discussed their plans and movements, handing the Allies a huge amount of very useful information, not all of which was properly used. For example, both Rommel's actions at the Kasserine Pass, and German preparations for the Battle of the Bulge were clearly foreshadowed in decrypted Enigma traffic, but the information was not properly appreciated in either case.

After the War, the American TICOM project teams found and detained a considerable number of German crypto personnel. Among the things they learned was that German cryptographers, at least, understood very well that Enigma messages might be read; they knew Enigma was not unbreakable. They just found it impossible to imagine anyone going to the immense effort required. When Abwehr agents who had worked on Fish cryptography and Russian traffic were interned at Rosenheim around May 21,1945, they were not at all surprised that Enigma had been broken, only that someone had mustered all the resources in time to actually do it. Admiral Dönitz had been informed that it was the least probable of all security problems.

References

• Stephen Budiansky, Battle of Wits: the Complete Story of Codebreaking in World War II, 2002, ISBN 0743217349.
• James J Gillogly, "Ciphertext-only Cryptanalysis of Enigma," Cryptologia, 19 (4), 1995, pp. 405–412. Online version.
• Marian Rejewski, "An Application of the Theory of Permutations in Breaking the Enigma Cipher," Applicationes mathematicae, 16(4), 1980. Online version (PDF).
• Alan M. Turing, "Treatise on Enigma" (parts online, PDF): [1]
• Wladyslaw Kozaczuk , Enigma: How the German Machine Cipher Was Broken, and How It Was Read by the Allies in World War Two, edited and translated by Christopher Kasparek, Frederick, MD, University Publications of America, 1984. (This remains the standard reference on the Polish part in the Enigma-decryption epic.)
• Wladyslaw Kozaczuk, Jerzy Straszak, Enigma: How the Poles Broke the Nazi Code, Hippocrene Books, 2004, ISBN: 078180941X.