Cryptanalysis of the Enigma
From Wikipedia, the free encyclopedia
 |
|
The Enigma machines were a family of portable cipher machines. This article discusses the cryptanalysis of Enigma.
[edit] Strengths of Enigma
|
Enigma was designed to defeat basic cryptanalytic techniques by continually changing the substitution alphabet. Like other rotor machines, it implemented a polyalphabetic substitution cipher with a long period. With single-notched rotors, the period of the machine was 16,900 (26 × 25 × 26). This long period helped protect against overlapping alphabets.
The Enigma machines added other possibilities. Each rotor had a variable starting position (e.g.ABC, as opposed to ACB); later Enigma models added a variable alphabet ring to each rotor. Most of the military Enigmas also featured a plugboard (German: Steckerbrett) which exchanged letters. Even so, this complex combination key could be easily communicated to another user, comprising as it did only a few simple items: rotors to be used, rotor order, ring positions, starting positions, and plugboard connections. Potentially this made the Enigma an excellent system.
[edit] Involution
The fact that encipherment was the same operation as decipherment 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 enciphering machine. These changed regularly (at first monthly, then weekly, then daily and even, toward war's end in some networks, many times a day) and were specified in key schedules distributed to Enigma users.
[edit] Security properties
The various Enigma models provided different levels of security. The presence of a plugboard (Stecker) substantially 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 helpful to cryptanalysts. First, 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; at Bletchley Park, this was termed a "crash."
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 this property was used in a number of codebreaking methods.
A weakness of many Enigma models was that the rightmost rotor turned a constant number of places before the next rotor turned.
Apart from the less-than-ideal inherent characteristics of the machine, the way Enigma was used proved its greatest weakness in practice. Mistakes by operators were common, and a number of the officially-specified procedures for using Enigma provided avenues for attack. It has been suggested by some of those working on its cryptanalysis at Bletchley Park that the Enigma should have been unbreakable in practice had its operators not been so error-prone, and had its operating procedures been better thought out. Post-war debriefings of German cryptographic specialists, conducted as part of project TICOM, tend to support this view - German cryptographers were well aware that Engima was theoretically breakable, but felt that the resources required to mount a purely mathematical brute-force attack on the system would require too much effort to be worthwhile. Had they considered the potential consequences of widespread operator error and poor procedure, it is likely that compromising Enigma would have proved impractical.
[edit] Unsteckered Enigma
The unsteckered Enigma — Enigma without a plugboard — was solved relatively easily. The British read messages sent during the Spanish Civil War, and also read some Italian traffic enciphered early in World War II (see Ultra).
- The unsteckered model was more of a stop gap communications device. It saw limited use in the Spanish Civil War and possible experimental use by the Italian Army (assumed user group) -- although there is only concrete evidence of its use in Spain.
- It is not known if the Italians used this model in Ethiopia or Libya (Cyrenaica).
[edit] Enigma with plugboard
[edit] Polish solution
In the early 1930s, the German Army began using an Enigma with a plugboard, greatly increasing Enigma's security. While British and French cryptanalysts had no success in their attempts to crack this version of Enigma, their Polish counterparts solved the rotor wiring and read German Enigma traffic.
[edit] Breakthrough
In December 1932, a 27-year-old Polish mathematician, Marian Rejewski, who had joined the Polish Cipher Bureau in September that year, made one of the most important breakthroughs in cryptologic history by using algebraic mathematical techniques to solve the Enigma wiring.
At the time, 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.
The Poles 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. 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.
[edit] Cryptologic bomb
Analysis of thousands of possibilities represents a vast human effort, if done by hand. To help with this, Marian Rejewski in about October 1938 invented an electro-mechanical device which was dubbed the "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 to "bombe." In mid-November 1938 the Polish bombs were ready, and reconstruction of daily keys went on apace. 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 daily keys. Each cryptologic 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 decrypt a large portion of German Enigma traffic from December 1932. Rejewski had been aided in his reconstruction of Enigma's wiring by documents obtained by French military intelligence from an agent in Berlin (Hans Thilo-Schmidt, codenamed Asché by the French) who had access to Enigma key-schedules and manuals.
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. As Rejewski wrote in a 1979 critique of appendix 1, volume 1 (1979), of the official history of British Intelligence in the Second World War, "we quickly found the [wirings] within the [new rotors], but [their] introduction [...] raised the number of possible sequences of drums from 6 to 60 [...] and hence also raised tenfold the work of finding the keys. Thus the change was not qualitative but quantitative. We would have had to markedly increase the personnel to operate the bombs, to produce the perforated sheets ..."
[edit] "Enigma doubles"
Polish intelligence had been reading Enigma-generated cryptograms since December 1932. Subsequent modifications in the machine and its operating procedures caused periodic "blackouts" requiring the Poles (and, after July 1939, also the British and French) 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 26, 1939[1], 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 "cryptologic bomb" (Polish: 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.
[edit] Between two giants
During the German invasion of Poland in September 1939, key Cipher Bureau personnel were evacuated southeastward and — after the Soviets invaded eastern Poland on September 17 — into Romania, on the way destroying their cryptologic 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, 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" and in French Algeria, at constant risk of discovery and imprisonment or worse. When Germany took over Vichy France in November 1942, the Poles 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 Portugal 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 put to work breaking German SS and SD ciphers at a Polish signals facility in Boxmoor; they were not invited to work on Enigma at Bletchley Park.
Until 1945, numerous enhancements were made to the system, although the Germans considered it unbreakable for all practical purposes.
- See also: Cyclometer, Perforated sheets.
[edit] World War II
British codebreakers had adopted the Polish Enigma-breaking techniques, but had to remain alert to German cryptographic advances. The German Army had changed its practices (more rotors, a more secure indicator system, etc.). The German Navy — some of whose Enigma ciphers the Poles had broken — had always used more secure procedures.
The Herivel tip (also known as Herivelismus), suggested by John Herivel, was an effect which relied on operators failing to choose random rotor positions for their indicators after changing the rotor ring settings, effectively sending the ring settings almost in the clear.
German Army and Air Force Enigma-machine operators also gave the decrypters immense help on a number of occasions. In one instance an operator was asked to send a test message, and simply hit the T key repeatedly and sent the resulting letters. A British analyst received from the intercept stations a long message without a single T in it, and immediately realised what had happened. In other cases, Enigma operators would constantly use the same settings as message keys, often their own initials or those of girlfriends (called "cillies," after an operator with the apparent initials "C.I.L."). Analysts were set to finding these messages in the sea of intercepts 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, in which case the same crib might be used every day.
[edit] The bombe
Alan Turing, chief of Hut Eight (Naval Enigma) at Bletchley Park, made important contributions to efficient Enigma-breaking, as did Gordon Welchman, head of Hut Six.
One important approach to breaking the ciphers 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 common German phrases such as "Heil Hitler" or "please respond," which might occur frequently in certain plaintexts; such a successful guess at a plaintext was known at Bletchley as a crib. With a probable plaintext fragment and the knowledge that no letter could be enciphered as itself, a corresponding ciphertext fragment could often 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 clue to message settings.
The British bombe, designed by Alan Turing and Gordon Welchman, relied on cribs. Assume that a triple loop is found, e.g. abc. That means that, with a crib, plaintext letter a is mapped to cipher b, plain b to c, and plain c to cipher a again within a short distance (ideally plain: abc, cipher: bca). Now the rotor mechanisms of three Enigmas are assembled serially in-line and set to the original rotor positions, with their offset (here 1 step each) accordingly. Then a corresponding physical wire closed loop is obtained. This can be detected with lamps connected to the rotor contacts. The lamp in the wire loop will stay dark. Now the rotor systems are turned synchronously. If only one lamp stays dark because of the one wire loop, the Steckerfeld (Plug Field) may be quickly calculated, and the positions with all lamps lit rejected. This typically happens several times in the 17,576 possible rotor settings.
[edit] Naval Enigma
Kriegsmarine procedures were much more secure, and the Navy Enigma variant featured a set of eight rotors from which the three operating ones were selected. This meant that there were 336 possible rotor combinations alone. Bletchley Park made no useful headway into Kriegsmarine Enigma until mid-1940 with the capture of the armed trawler, Polares. The latter yielded enough intact cryptographic material that by June or July 1940, Hut 8 at least knew what content to expect in Kriegsmarine messages, and knew the details of the encipherment and decipherment procedures. However, the 336 possible rotor selections, together with a lack of usable cribs, made the usual cryptanalysis methods almost useless.
Hut 8 therefore developed "Banburismus," a method using Bayesian statistics to derive a bombe menu from the "message settings" rather than the messages themselves. In doing so, they would identify at least the rightmost rotor being used in the cipher that day. If Hut 8 were lucky, they managed to identify the rightmost and middle rotors, leaving only six wheel orders to be run on the bombes.
Later in the war, British codebreakers learned to fully exploit a crucial security flaw associated with German weather reports: they were broadcast from weatherships to Germany in lower-level ciphers, easy to decrypt, then retransmitted to U-boats at sea in Enigma, thus giving Bletchley Park regular cribs. This was crucial in attacking the special four-rotor U-boat Enigma machine introduced in 1942.
Cipher material was captured at sea. The first capture of Enigma material occurred in February 1940, when rotors VI and VII, the wiring of which was at that time unknown, were captured from the crew of U-33. On May 7, 1941, the Royal Navy captured a German weather ship, together with cipher equipment and codes. They did it again shortly afterwards. And two days later U-boat U-110 was captured, complete with Enigma machine, codebook, operating manual and other information. As a result, Naval Enigma was readable directly through the end of June, and from then on Banburismus allowed it to be read fairly continuously until newer, faster Bombes rendered the procedure unnecessary in mid-1943.
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), two German weather-reporting trawlers, and a small vessel (the Krebs) captured during a raid on the Lofoten Islands off Norway. Several other imaginative techniques were dreamed up, including Ian Fleming's suggestion to crash captured German bombers into the sea near German ships, hoping the planes' crews would be rescued by the ships' crews, which would then be taken captive, along with the ships' cryptographic materials, by commandos concealed in the planes.
In order to solve Naval Enigma, both Britain and the US, but particularly the US, produced four-wheel bombes that could rapidly test thousands of possible keys. The American efforts on the M4 Enigma were led by Joseph Desch, an engineer working for the National Cash Register Corporation at the United States Naval Computing Machine Laboratory.
[edit] German suspicions
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 huge amounts of information, not all of which was properly used. For example, Rommel's actions at the Kasserine Pass were clearly foreshadowed in decrypted Enigma traffic, but the information was not properly appreciated.
After the war, American TICOM project teams found and detained a considerable number of German cryptographic personnel. Among the things the Americans 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. [2] When Abwehr personnel 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 advised that that was the least likely of all security problems.
[edit] Since World War II
Modern computers can be used to solve Enigma, using a variety of techniques[3]. There is even a project to decrypt some remaining messages [1], using distributed computing.
[edit] Notes
- ^ Ralph Erskine, "The Poles Reveal their Secrets: Alastair Denniston's Account of the July 1939 Meeting at Pyry", pp. 294-305, Cryptologia 30(4), December 2006
- ^ Bamford, J. (2001). Body of Secrets. Doubleday, 17. ISBN 0-385-49907-8.
- ^ Geoff Sullivan and Frode Weierud, "Breaking German Army Ciphers" in Cryptologia 24(3), July 2005, pp. 193–232 Online version (PDF - 6 MB).
[edit] References
- Stephen Budiansky, Battle of Wits: the Complete Story of Codebreaking in World War II, 2002, ISBN 0-7432-1734-9.
- Jim DeBrosse and Colin Burke, The Secret in Building 26: The Untold Story of America's Ultra War against the U-boat Enigma Codes, 2004, ISBN 0-375-50807-4.
- Kris Gaj, Arkadiusz Orłowski, Facts and Myths of Enigma: Breaking Stereotypes, EUROCRYPT 2003: 106–122. Online version (PDF).
- James Gannon, Stealing Secrets, Telling Lies: How Spies and Codebreakers Helped Shape the Twentieth Century, Washington, D.C., Brassey's, 2001, ISBN 1-57488-367-4.
- James J. Gillogly, "Ciphertext-only Cryptanalysis of Enigma," Cryptologia, 19 (4), 1995, pp. 405–412. Online version.
- David Kahn, Seizing the Enigma: the Race to Break the German U-Boat Codes, 1939-1943, Houghton Mifflin, 1991, ISBN 0-395-42739-8.
- Władysław 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. (A substantially revised and augmented translation of W kręgu enigmy, Warsaw, Książka i Wiedza, 1979, supplemented with additional appendices by Marian Rejewski.)
- Władysław Kozaczuk, Jerzy Straszak, Enigma: How the Poles Broke the Nazi Code, Hippocrene Books, 2004, ISBN 0-7818-0941-X. (Largely an abridgment of Kozaczuk's 1984 Enigma, minus Rejewski's appendices, here supplanted with appendices by other authors.)
- A. Ray Miller, The Cryptographic Mathematics of Enigma, 2001, [2].
- Hugh Sebag-Montefiore, Enigma: The Battle for the Code, John Wiley, 1984.
- 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): [3]
- Gordon Welchman The Hut Six Story: Breaking the Enigma codes, M & M Baldwin, 3rd Edition, 1997, ISBN 0-947712-34-8
- Gilbert Bloch, "Enigma before Ultra: Polish Work and the French Contribution," translated by C.A. Deavours, Cryptologia, July 1987.
- Zbigniew Brzezinski, "The Unknown Victors," pp.15–18 in Jan Stanisław Ciechanowski, ed., Marian Rejewski, 1905–1980: Living with the Enigma secret, Bydgoszcz, Bydgoszcz City Council, 2005, ISBN 83-7208-117-4.
[edit] External links
- Dayton Daily News, Dayton's Code Breakers.
- Dayton Codebreakers Web site, DaytonCodebreakers.org.
- About the Enigma (National Security Agency)
- "The Enigma Code Breach" by Jan Bury
- | The "Enigma" and the Intelligence
- www.enigmahistory.org
