Cryptanalysis of the Enigma

fr:Cryptanalyse d'Enigma Template:EnigmaSeries 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.

Contents

Strengths of Enigma

Missing image
Enigma-baldwin.jpg
The Enigma machine was used commercially from the early 1920s on, and was also adopted by the military and governmental services of a number of nations — most famously, by Nazi Germany before and during World War II (WWII).

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 in practice 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 using 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, in practice, impossible; as it also was in the early 1930's, when the German Army began to use a slightly different version. 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 they 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 27-year-old Polish mathematician, Marian Rejewski, made one of the most important breakthroughs in cryptologic history by using mathematical techniques to find a way to do both. Rejewski noticed a crucial pattern: the indicator procedure was to encrypt an operator-selected message setting twice, with the machine at its "ground setting," and to place the twice-encrypted message setting at the opening of the 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 onwards, they became very experienced in exploiting 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 get 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  machine
Enlarge
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 its Enigma operating procedures. Initially only three rotors had been in use, and their sequence in the slots was changed periodically. Now two additional rotors were introduced; three of the five would be in use at any given time. The Germans also stopped transmitting a twice-enciphered individual three-letter message setting at the beginning of a message, thus putting an end to one of the Poles' original methods of cryptological attack.

Polish intelligence had been reading Enigma-generated cryptograms since early 1933. Subsequently modifications in the machine and its operating procedures caused periodic "blackouts" requiring the Poles (and, after July 1939, also the British) to find new ways of breaking into the ciphers. In April and May 1939 Poland contracted military alliances with Britain and France. The Poles, realizing the pace and direction of changes in the European political situation, decided in mid-1939 to share their work. At a conference in Warsaw on July 25, 1939, they pledged to give the French and British each a Polish-reconstructed Enigma, along with details of Enigma-solving techniques that they had developed, such as Zygalski's "perforated sheets" and the "cryptologlical bomb" (bomba kryptologiczna). The two "Enigma doubles" were shipped to Paris, whence Gustave Bertrand brought one to London for the British, turning it over at Victoria Station, as he was to recall in his Enigma, to Stewart Menzies of Britain's Secret Intelligence Service. Until then, German military Enigma traffic had utterly defeated the British and French, and they had faced the disturbing prospect that German communications would remain "black" to them for the duration of the coming war.

During the German invasion of Poland in September 1939, the key personnel of the Biuro Szyfrów were evacuated southeastward and — after the Soviets invaded eastern Poland on September 17 — into Romania, on the way destroying their cryptological equipment and documentation. Eventually, crossing Yugoslavia and still-neutral Italy, they reached France. There, at PC Bruno outside Paris, they resumed their work on breaking German Enigma ciphers, continuing it into the subsequent Battle of France. Several months before the German invasion of France, however, in January 1940, British mathematician Alan Turing came to Bruno for several days to confer with his Polish mathematician colleagues.

After the French-German armistice, the Polish Cipher Bureau continued its work in France's southern "Free Zone" (Vichy France) and in French Algeria, at constant risk of discovery and imprisonment or worse. When Germany took over Vichy France, they once again had to flee. The Cipher Bureau's chiefs, Colonel Gwido Langer and Major Maksymilian Cięźki, and some of the technical staff were captured by the Germans but, despite extensive interrogation, managed to preserve the secret of Enigma decryption. The mathematicians Marian Rejewski and Henryk Zygalski, after a perilous Odyssey that took them across France, into a Spanish prison, to Portual and at last by ship to Gibraltar, finally made it to Britain. (The third mathematician, Jerzy Róźycki, had perished in the sinking of a passenger ship while returning in 1942 to southern France from a tour of duty in Algeria.)

In Britain, Rejewski and Zygalski were inducted as privates into the Polish Army. Eventually they were promoted to second lieutenant, then lieutenant, and they were put to work breaking German SS and SD ciphers at a Polish signals facility in Boxmoor. Their solutions would doubtless have contributed to the Allies' stock of intelligence and of cribs for Enigma decryption. The latter, however, had become a British and, eventually, also an American monopoly.

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 (http://members.fortunecity.com/jpeschel/gillog1.htm).
  • Marian Rejewski, "An Application of the Theory of Permutations in Breaking the Enigma Cipher," Applicationes mathematicae, 16(4), 1980. Online version (PDF) (http://frode.home.cern.ch/frode/crypto/rew80.pdf).
  • Alan M. Turing, "Treatise on Enigma" (parts online, PDF): [1] (http://frode.home.cern.ch/frode/crypto/Turing/index.html)
  • 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. (Largely an abridgement of Kozaczuk's 1984 Enigma, minus all of Rejewski's extensive documentation.)
Navigation

  • Art and Cultures
    • Art (https://academickids.com/encyclopedia/index.php/Art)
    • Architecture (https://academickids.com/encyclopedia/index.php/Architecture)
    • Cultures (https://www.academickids.com/encyclopedia/index.php/Cultures)
    • Music (https://www.academickids.com/encyclopedia/index.php/Music)
    • Musical Instruments (http://academickids.com/encyclopedia/index.php/List_of_musical_instruments)
  • Biographies (http://www.academickids.com/encyclopedia/index.php/Biographies)
  • Clipart (http://www.academickids.com/encyclopedia/index.php/Clipart)
  • Geography (http://www.academickids.com/encyclopedia/index.php/Geography)
    • Countries of the World (http://www.academickids.com/encyclopedia/index.php/Countries)
    • Maps (http://www.academickids.com/encyclopedia/index.php/Maps)
    • Flags (http://www.academickids.com/encyclopedia/index.php/Flags)
    • Continents (http://www.academickids.com/encyclopedia/index.php/Continents)
  • History (http://www.academickids.com/encyclopedia/index.php/History)
    • Ancient Civilizations (http://www.academickids.com/encyclopedia/index.php/Ancient_Civilizations)
    • Industrial Revolution (http://www.academickids.com/encyclopedia/index.php/Industrial_Revolution)
    • Middle Ages (http://www.academickids.com/encyclopedia/index.php/Middle_Ages)
    • Prehistory (http://www.academickids.com/encyclopedia/index.php/Prehistory)
    • Renaissance (http://www.academickids.com/encyclopedia/index.php/Renaissance)
    • Timelines (http://www.academickids.com/encyclopedia/index.php/Timelines)
    • United States (http://www.academickids.com/encyclopedia/index.php/United_States)
    • Wars (http://www.academickids.com/encyclopedia/index.php/Wars)
    • World History (http://www.academickids.com/encyclopedia/index.php/History_of_the_world)
  • Human Body (http://www.academickids.com/encyclopedia/index.php/Human_Body)
  • Mathematics (http://www.academickids.com/encyclopedia/index.php/Mathematics)
  • Reference (http://www.academickids.com/encyclopedia/index.php/Reference)
  • Science (http://www.academickids.com/encyclopedia/index.php/Science)
    • Animals (http://www.academickids.com/encyclopedia/index.php/Animals)
    • Aviation (http://www.academickids.com/encyclopedia/index.php/Aviation)
    • Dinosaurs (http://www.academickids.com/encyclopedia/index.php/Dinosaurs)
    • Earth (http://www.academickids.com/encyclopedia/index.php/Earth)
    • Inventions (http://www.academickids.com/encyclopedia/index.php/Inventions)
    • Physical Science (http://www.academickids.com/encyclopedia/index.php/Physical_Science)
    • Plants (http://www.academickids.com/encyclopedia/index.php/Plants)
    • Scientists (http://www.academickids.com/encyclopedia/index.php/Scientists)
  • Social Studies (http://www.academickids.com/encyclopedia/index.php/Social_Studies)
    • Anthropology (http://www.academickids.com/encyclopedia/index.php/Anthropology)
    • Economics (http://www.academickids.com/encyclopedia/index.php/Economics)
    • Government (http://www.academickids.com/encyclopedia/index.php/Government)
    • Religion (http://www.academickids.com/encyclopedia/index.php/Religion)
    • Holidays (http://www.academickids.com/encyclopedia/index.php/Holidays)
  • Space and Astronomy
    • Solar System (http://www.academickids.com/encyclopedia/index.php/Solar_System)
    • Planets (http://www.academickids.com/encyclopedia/index.php/Planets)
  • Sports (http://www.academickids.com/encyclopedia/index.php/Sports)
  • Timelines (http://www.academickids.com/encyclopedia/index.php/Timelines)
  • Weather (http://www.academickids.com/encyclopedia/index.php/Weather)
  • US States (http://www.academickids.com/encyclopedia/index.php/US_States)

Information

  • Home Page (http://academickids.com/encyclopedia/index.php)
  • Contact Us (http://www.academickids.com/encyclopedia/index.php/Contactus)

  • Clip Art (http://classroomclipart.com)
Toolbox
Personal tools