Cryptanalysis of the Enigma

The Enigma cipher machine

Enigma machine Enigma rotors Breaking Enigma Polish Cipher Bureau Doubles Grill Clock Cyclometer Card catalog Bomb Sheets Bletchley Park Banburismus Herivel tip Bombe Hut 6 Hut 8 PC Bruno Cadix Ultra

This box: view • talk • edit

Cryptanalysis of the Enigma enabled the Allies in World War II to read substantial amounts of secret Morse-coded radio communications of the Axis powers enciphered using Enigma machines. This Allied reading yielded military intelligence which, along with that from other decrypted German radio transmissions, was given the name "Ultra."

Enigma decrypts thus contributed greatly to the success of Allied war efforts, for example in reversing the early disastrous tide of the Battle of the Atlantic beginning in the latter part of 1941, in frustrating Rommel's efforts to capture Cairo in 1942, and in the planning and execution of Operation Overlord (the Allied invasion of France) in 1944.^[1]

The Enigma machines were a family of portable cipher machines with rotor-based scramblers. Various German armed and secret services and civilian agencies used Enigma in somewhat different ways, and at various times made changes to their procedures for operating Enigma. The greatest differences in operating procedures were between those of the German Navy (Reichsmarine and Kriegsmarine) and those of other services and agencies; these differences will not be detailed here.

The German plugboard-equipped Enigma that would be the Third Reich's principal crypto-system was reconstructed, with the aid of French-supplied intelligence material, by the Polish General Staff's Cipher Bureau in December 1932, on the eve of Adolf Hitler's rise to power in Germany in January 1933. From then until the outbreak of World War II the Poles maintained a monopoly of decryption of this Enigma model.

As war drew near, at a Warsaw conference on 25 July 1939 the Polish Cipher Bureau initiated the French and British into their Enigma-breaking techniques and technology, thus greatly broadening the Allied (Polish, French, and particularly British and American) foundations for wartime decryption of German Enigma-enciphered communications.

[edit] General principles

Analysis of a monoalphabetic substitution cipher is relatively easy, so long as a message is long enough to provide a reasonably representative count of the letters of the alphabet. The resultant frequency count can then be compared with the known letter frequencies of the language in which the message is written.^[2]

In the 15th and 16th centuries, in Europe, the idea of a polyalphabetic substitution cipher was developed, among others by the French diplomat Blaise de Vigenère (1523-96).^[3] For some three centuries, the Vigenère cipher was considered to be completely secure (le chiffre indéchiffrable—"the indecipherable cipher"). Nevertheless, Charles Babbage (1791–1871) and later, independently, Friedrich Kasiski (1805–81) succeeded in breaking this cipher.^[4]

The cryptographic key for the Vigenère cipher consists of a word or phrase that is repeated many times to cover the length of the message. The key's letters indicate which line of the Vigenère square is used to encipher each letter of the plaintext so as to produce the ciphertext. It was this repetition that allowed Babbage and Kasiski to achieve their breaks.

During World War I, inventors in several countries realized that a purely random key sequence, containing no repetitive pattern, would make a polyalphabetic substitution, in principle, unbreakable.^[5] This led to the development, in several countries, of rotor cipher machines such as Arthur Scherbius' Enigma.

The presence of repetition or of guessable elements in either the key or the message are the weaknesses that allow cryptanalysts to seek patterns that can enable them to break a cipher. Finding such weak points in Enigma encipherment, before and during World War II, led to sustained Allied decryption of German Enigma ciphers.

[edit] Strengths of Enigma

The Enigma machine was used commercially from the early 1920s, and was adopted by the militaries and governments of various nations — most famously, Nazi Germany.

Enigma was designed to defeat analytic techniques by continually changing the substitution alphabet through the use of a scrambler comprising three—in some cases, four—rotors.

Like other rotor cipher-machines, Enigma generated a polyalphabetic substitution cipher with a long period. Given three single-notched rotors, the period was 16,900 (= 26 × 25 × 26).^[6] Such a long period prevented any detectable repetition in the enciphering sequence.

This property of the cipher was enhanced by each scrambler rotor having a variable starting position (it could be any letter of the alphabet) and by the sequence of the three rotors being selected from the six possible sequences.

Later Enigma models added a variable alphabet ring like a tyre around each rotor, that specified which letter was opposite the notch that caused the next wheel to advance. Later still, the three rotors that were in use were selected from a set of five or, in the case of the German Navy, eight rotors.

Military Enigmas also featured a plugboard (German: Steckerbrett) which exchanged letters.

This complex ground-key setting (German: Grundstellung) was distributed to all users of a network by means of "setting sheets" in a codebook.^[7] The setting sheets specified the three rotors to be used and their positions (German: Walzenlage), the letter positions of the rotors, the ring positions (German: Ringstellung) and the plugboard connections (German: Steckerverbindungen ).

The Enigma was potentially an excellent system.

The device featured the operational convenience of being symmetrical (or self-inverse). This meant that decipherment worked in the same way as encipherment — when the ciphertext was typed in, the sequence of lamps that lit yielded the plaintext. This of course required that the deciphering machine's plugboard and scrambler rotors be set identically to those of the enciphering machine.

In order to ensure that this would be the case, setting-sheets that specified plugboard and scrambler-rotor settings were distributed to users of particular networks. These setting-sheets changed the "ground key" regularly (at first monthly or weekly,^[8] but soon daily and even, toward war's end in some networks, many times a day).

Also, for each message, the transmitting operator would send an "indicator" specific to that message. The procedure for sending the indicator differed among networks and at different times, and contributed to the relative ease or difficulty of breaking into the traffic of a network.

[edit] Security properties

The various Enigma models provided different levels of security. The presence of a plugboard substantially increased the security of the encipherment. In general, the unsteckered Enigma was used for commercial and diplomatic traffic and could be broken relatively easily using hand methods, while attacking versions with a plugboard was much more difficult. The British read unsteckered Enigma messages sent during the Spanish Civil War,^[9] and also some Italian traffic enciphered early in World War II (see "Ultra").

The Enigma machine did, however, have major weaknesses 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 — in German, Umkehrwalze). This property was of great help in using cribs — short sections of plaintext thought to be somewhere in the ciphertext — and could be used to eliminate a crib in a particular position. For a possible location, if any letter in the crib matched a letter in the ciphertext at the same position, the location could be ruled out; at Britain's Government Code and Cipher School (GCCS) at Bletchley Park, this was termed a "crash".^[10] It was this feature that the British mathematician and logician Alan Turing would exploit in designing the British bombe.

A second Enigma weakness was that the plugboard connections were reciprocal, so that if A was plugged to N, then N likewise became A. It was this property that inspired mathematician Gordon Welchman at Bletchley Park to propose that a "diagonal board" be introduced into the bombe, substantially reducing the number of rotor settings that the bombe had to try.^[11]

A third weakness for many Enigma models was that the rightmost rotor turned a constant number of places before the next rotor turned.

A number of the officially-specified procedures for using Enigma also provided avenues for attack. Thus, for machines where there was a choice of more rotors than there were slots for them, a rule stipulated that no rotor should be in the same slot in the scrambler as it had been for the immediately preceding configuration.

Similarly, the plugboard-setup rules forbade a letter being connected to an adjacent one on the alphabet.

Once detected, these constraints reduced the number of alternatives that needed to be tried.

In any case, the Germans' specified Enigma-operating procedures, and good cryptologic practice, were not adhered to by all Enigma operators.

It has been suggested by some who worked at breaking Enigma at Bletchley Park that the Enigma should have been unbreakable in practice, had its operating procedures been better thought out and had its operators been less ill-disciplined. Postwar debriefings of German cryptographic specialists, conducted as part of project TICOM, tend to support this view — the Germans were well aware that Enigma was theoretically breakable, but felt that the resources required to mount a pure brute-force attack on the system would require too much effort to be worthwhile.

Had they considered the potential consequences of widespread poor operator procedure, and acted to correct the situation, it is likely that breaking Enigma on a regular basis would have proven impractical. To war's end, the Germans continued making improvements to the system, though they considered it to be for all practical purposes unbreakable.

[edit] Polish breakthrough

Polish General Staff building (the Saxon Palace), in Warsaw, where German Enigma ciphers were first broken (1932). The palace was destroyed in World War II and is to be rebuilt.

Main article: Biuro Szyfrów

In 1928, the German Army began using a 3-rotor Enigma with a 6-cable plugboard.^[12] British, French and American cryptanalysts had no success in their attempts to crack this version of Enigma.^[13] In Poland, however, the threat from Germany was much greater, and the Polish Cipher Bureau (Biuro Szyfrów) in Warsaw continued to work on it. On 1 September 1932, a 27-year-old Polish mathematician, Marian Rejewski, joined the Bureau along with two somewhat younger fellow Poznań University mathematics graduates, Henryk Zygalski and Jerzy Różycki.

In December that year, the Poles received from French Army Captain Gustave Bertrand two documents that had been obtained by a French military intelligence agent, a German code-named Rex,^[14] from an agent who worked at the Cipher Office in Berlin (Hans Thilo-Schmidt, whom the French code-named Asché). The documents were entitled Gebrauchsanweisung für die Chiffriermaschine Enigma and Schlüsselanleitung für die Chiffriermaschine Enigma and provided instructions for using Enigma, and sufficient information to begin deducing the wirings of the three rotors and thus to build an Enigma double (a functioning replica of a 3-rotor Enigma).^[15]

Marian Rejewski about 1932, when he first broke Enigma

This enabled Rejewski, who had been doing preliminary mathematical analysis, to make one of the most important breakthroughs in cryptologic history by using elementary group theory to solve the Enigma wiring and rotor settings.^[16][17] He worked out a method which made it possible to derive the rotor settings independently of the plugboard connections. The Poles were then able to decrypt a substantial portion of German Enigma traffic through December 1938. (Thereafter they continued reading Enigma, but—due to changes in encipherment procedures—a smaller volume.)^[18]

At the time, the setting sheets specified the rotor positions in the machine, the ring settings, the plugboard connections, and the rotor settings as they appeared through the three windows on top of the machine.

The message indicator was a 6-letter sequence comprising the three letters of the message key, enciphered twice using the initial rotor position given in the ground setting (e.g., RAO).^[19] If the 3-letter message key chosen by the operator was IHL, he would encipher this after having set the rotors to RAO. The resultant ciphertext, say OTUNSD, would be transmitted, followed by the message, enciphered using message key IHL. The receiving operator would use the ground setting RAO to decypher the first six letters, yielding IHLIHL—assuming that there had been no distortion or "garbling" in the transmission or reception of the Morse.

It was the possibility of garbling that had led to the procedure of repeating the message key. This repetition was, however, a major security weakness that the Poles and, later, the British exploited.

The message would then be decrypted, using message key IHL.

In the example of OTUNSD being the ciphertext of the message key, it is known that the first letter O and the fourth letter N represent the same letter, enciphered three positions apart in the scrambler sequence. Similarly with T and S in the second and fifth positions, and U and D in the third and sixth. Rejewski exploited this fact by collecting a sufficient set of messages enciphered with the same ground key and assembling three tables for the 1,4, the 2,5, and the 3,6 pairings. Each of these might look something like the following:

A path from one first letter to the corresponding third letter, then from that letter as the first letter to its corresponding third letter, and so on until the first letter recurs, traces out a cycle group. The above table contains four cycle groups.

The letters in these cycle groups are changed by the plugboard settings but, importantly, their patterns (in this example, four groups with 12, 10, 2 and 2 links) are not. This reduces the number of possibilities from 10,000 trillion to 105,456 (the number of possible rotor settings).^[20]

[edit] Cyclometer

Cyclometer (mid-1930s), devised by Rejewski to catalog the cycle structure of Enigma permutations. 1: Rotor lid closed, 2: Rotor lid open, 3: Rheostat, 4: Glowlamp, 5: Switches, 6: Letters.

Main article: Cyclometer

The Poles set about creating a catalog of these cycle patterns. Rejewski about 1934 or 1935 devised a machine to facilitate this task, called a "cyclometer," which "comprised two sets of rotors... connected by wires through which electric current could run. Rotor N in the second set was three letters out of phase with respect to rotor N in the first set, whereas rotors L and M in the second set were always set the same way as rotors L and M in the first set."^[21]

Preparation of the "card catalog," using the cyclometer, was, says Rejewski, "laborious and took over a year, but when it was ready, obtaining daily keys was a question of [some fifteen] minutes."^[22]

On 1 November 1937, however, the Germans changed the Enigma reflector, necessitating the production of a new catalog—"a task which [says Rejewski] consumed, on account of our greater experience, probably somewhat less than a year's time."^[23]

On 15 September 1938 (the day that British Prime Minister Neville Chamberlain flew to the conference that led to the Munich Agreement) the indicator procedure was changed.^[24] It now comprised a 9-letter sequence. The setting, as stated in the setting sheet, no longer specified the initial rotor positions to be used. Instead the operator chose three letters, which were transmitted in clear as the first three of nine letters. These gave the key for setting the rotors for the next six letters, which constituted the 3-letter message key sent twice.^[25][26] This meant that the cycle-pattern method would no longer work.

[edit] Perforated sheets

Zygalski sheet

Main article: Perforated sheets

To decrypt Enigma messages, use was now made of a perforated-sheet apparatus that was devised about October 1938 by Henryk Zygalski and is therefore often called "Zygalski sheets." This method depended on a message key's repetition, but also relied on the situation in which a repeated letter of the key was enciphered to the same letter of ciphertext as it had been three letters previously.

Thus, if an intercepted message had the same first and fourth, second and fifth, or third and sixth letters, it was known that some scrambler settings could be eliminated. This phenomenon was, in effect, a zero-length cycle, and details of such cycles would have been available in the catalog.

These occurrences were called "samiczki"^[27] (in English, "females" — a term later used at Bletchley Park^[28][29]). If the first six letters of the ciphertext were SZVSIK, this would be termed a 1-4 female; if WHOEHS, a 2-5 female; and if ASWCRW, a 3-6 female.

Demonstration of two perforated sheets at Bletchley Park Museum

The probability of any message containing at least one female was about one in eight. Some ten females would be collected from a day's messages and subjected to the sheets apparatus.

There was a set of 26 sheets for each of the six possible sequences for inserting the three rotors into the scrambler. Each sheet related to the starting position of the left (slowest-moving) rotor. The 26 × 26 matrix represented the 676 possible starting positions of the middle and left rotors and was duplicated horizontally and vertically: a–z, a–y. The sheets were punched with holes in the positions that would allow a female to occur. Rejewski writes about how the perforated-sheets device was operated:

"When the sheets were superposed and moved in the proper sequence and the proper manner with respect to each other, in accordance with a strictly defined program, the number of visible apertures gradually decreased. And, if a sufficient quantity of data was available, there finally remained a single aperture, probably corresponding to the right case, that is, to the solution. From the position of the aperture one could calculate the order of the rotors, the setting of their rings, and, by comparing the letters of the cipher keys with the letters in the machine, likewise permutation S; in other words, the entire cipher key."^[30]

[edit] "Bomb"

Cryptologic bomb.
1: Rotors. 2: Electric motor. 3: Switches.

Main article: Cryptologic bomb

As an alternative to the Zygalski sheets, which required about ten "females", a method was developed that used only three. This required an exhaustive (brute-force) analysis of the 105,456 possible rotor settings.

If done by hand, such an analysis would have represented a vast human effort. To facilitate it, Rejewski in about October 1938 invented an electro-mechanical device that was dubbed the bomba kryptologiczna or "cryptologic bomb". ^[31] Each bomba contained six sets of Enigma rotors for the six positions of the repeated three-letter key.

In mid-November 1938, six Polish bomby^[32] (one for each rotor arrangement) 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." ^[33]

On 15 December 1938, the German Army increased the complexity of its Enigma operating procedures. Previously only three rotors had been in use, and their sequence in the slots was changed daily. Now two additional rotors were introduced; three of the five would be in use at any given time. This increased the number of possible rotor arrangements in the scrambler by a factor of ten.^[34]

Other German agencies likewise received the two new rotors at the same time. Had all these organizations used the same new operating procedures as the Army, it would have nullified any chance of the Poles continuing to decrypt Enigma. However, until 1 July 1939, just two months before Germany invaded Poland, the Sicherheitsdienst (S.S. Security Service), continued using its machines in the old way — like the Wehrmacht prior to 15 September 1938.^[35]

The Cipher Bureau immediately exploited this incoordination between the Army and the S.D. and by about the turn of the year had reconstructed the wirings in rotors IV and V. Nevertheless, even with Rejewski's cryptologic bomb and Zygalski's perforated sheets, the new keying procedure and the increased number of rotors posed some major problems.^[36] These were exacerbated when, on New Year's Day 1939, the Germans increased the number of plug connections in the plugboard. Previously, from 1 October 1936, the number of plug connections had been variable, ranging between five and eight.^[37] Now, from 1 January 1939, the number of plug connections was increased to between seven and ten.^[38]

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 [...] and to manipulate the sheets."^[39]

[edit] World War II

On 15 March 1939, German forces marched into Bohemia and Moravia. On 31 March Britain and France pledged their support for Poland in the event of any action that threatened her independence.^[40] Then, on 27 April, Germany withdrew from the German-Polish Non-Aggression Pact of January 1934. The Polish General Staff, realizing the pace and direction of changes in the European political situation, decided in mid-1939 to share their work on Enigma decryption with their western allies. Rejewski later wrote:

"[I]t was not [as Harry Hinsley suggested, cryptological] difficulties of ours that prompted us to work with the British and French, but only the deteriorating political situation. If we had had no difficulties at all we would still, or even the more so, have shared our achievements with our allies as our contribution to the struggle against Germany."^[41]

At a conference in Warsaw on 26 July 1939, the Poles revealed to the French and British that they had broken Enigma and pledged to give each a Polish-reconstructed Enigma, along with details of their Enigma-solving techniques and equipment, including Zygalski's "perforated sheets" and Rejewski's "cryptologic bomb."^[42][43]

The two "Enigma doubles" were sent to Paris, whence Gustave Bertrand brought one to London for the British. He turned it over at Victoria Station, as he was to recall in his Enigma, to Stewart Menzies of Britain's Secret Intelligence Service.^[44]

Until then, German military Enigma traffic had defeated the French and British, and they had faced the disturbing prospect that German radio communications would remain undecipherable during the coming war. As British cryptologist Gordon Welchman has written,

"Ultra would never have gotten off the ground if [the British] had not learned from the Poles, in the nick of time, the details... of the German military... Enigma machine and of the operating procedures that were in use."^[45]

Apart from some less-than-ideal inherent characteristics of the Enigma, in practice the machine's greatest weakness was the way that it was used. Errors by German Army and Air Force Enigma operators were common, and the Poles had become very experienced at exploiting even very subtle cryptographic mistakes made by the Germans.

One blatant mistake made by the Germans, Rejewski recalled, had been the inclusion, in an early Enigma manual, of a genuine plaintext and its genuine ciphertext, together with the genuine message key. When Rejewski was given this in December 1932, it "made [his reconstruction of the Enigma machine] somewhat easier."^[46]

Another German mistake described by Rejewski was the use of easily-guessed keys such as "AAA" or "BBB", or sequences that reflected the layout of the Enigma keyboard, such as "three [typing] keys that stand next to each other [o]r diagonally [from each other]..."^[47] At Britain's Bletchley Park these would become known as "cillies"—either the name of a German operator's girlfriend, used as a key, or a burlesque of "sillies," for some of the foolish things that operators did despite regulations to the contrary;^[48] or because one of the first message settings that was worked out at Bletchley Park, using cillies, was "CIL" (the word "cilli" then being a cross between "CIL" and "silly," describing Bletchleyites' view of such German practices).^[49]

Equally silly of the Germans, from a cryptologic perspective, was repeatedly using, in messages, the same stereotypical expressions — what Bletchley Park later would term "cribs": the same standard salutations, titles and addresses. Thus, for example, Rejewski recalled that "The last phase in reconstructing daily keys was finding the settings of the rings [on the rotors]. In that phase, we relied on the fact that the greater number of messages began with the letters "ANX"—German for "to", followed by "X" as a spacer.^[50]

Rejewski has described yet another error perpetrated by German operators, which was anticipated by John Herivel soon after his arrival at Bletchley Park in January 1940, but which did not occur until after the changes of 10 May that year, during the period of close Polish-British collaboration. The Germans, after setting their Enigmas in the starting position and closing the metal lid, were selecting as the message key (Spruchschlüssel) the letters that were visible in the glass windows. These letters were often identical with, or close to, the settings on the Enigma's internal rings. As a result, a few minutes past midnight the duty cryptologist would already know the cipher key for that day, and the French could read Wehrmacht signals at the same time as their intended recipients.^[51] This came to be known as the "Herivel tip."^[52][53]

During the German invasion of Poland in September 1939, key Cipher Bureau personnel were evacuated southeast and — after the Soviets invaded eastern Poland on 17 September — 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, on 20 October 1939 they resumed work on German Enigma ciphers, continuing it in the subsequent Battle of France.^[54]

As late as December 1939, when Lt. Col. Gwido Langer, chief of the Polish Cipher Bureau, and French Air Force Captain Henri Braquenié, visited London and Bletchley Park, the British asked that the Polish cryptologists be turned over to them. Langer, however, took the position that the Polish team must remain where the Polish Armed Forces were being re-formed—on French soil.^[55] Actually, the mathematician-cryptologists might have reached Britain much earlier than they eventually would (that is, the two who were still alive) in 1943; but in Bucharest, Romania, when they had gone to the British Embassy, they had been brushed off by preoccupied British diplomats.^[56]

Some personnel of the Cipher Bureau's German section who had worked with Enigma, and most of the workers at the AVA Radio Company that had built Enigma doubles and cryptologic equipment for the German section, had remained in Poland. Some were interrogated by the Gestapo, but no one gave away the secret of Polish mastery of Enigma decryption.^[57]

PC Bruno and Bletchley Park worked together closely from late 1939, communicating via a teletype (telegraph) line secured by the use of Enigma (!). The French would close their Enigma-enciphered messages with an appreciative "Heil Hitler!"^[58]

During this period, until the collapse of France in June 1940, ultimately 83 percent of Enigma keys were solved at Bletchley Park, the remaining 17 percent at PC Bruno. Rejewski comments:

How could it be otherwise, when there were three of us Pol[ish cryptologists] and [there were] at least several hundred British cryptologists, since about 10,000 people worked in Bletchley... Besides, recovery of keys also depended on the amount of intercepted cipher material, and that amount was far greater on the British side than on the French side. Finally, in France (by contrast with the work in Poland) we ourselves not only sought for the daily keys, but after finding the key also read the messages.... One can only be surprised that the Poles had as many as 17 percent of the keys to their credit.^[59]

The Germans, just before opening their 10 May 1940 offensive in the west that would trample Belgium, Luxemburg and Holland in order to reach the borders of France, once again changed their procedure for enciphering message keys, rendering the Zygalski sheets "completely useless"^[60][61] and temporarily defeating the joint British-Polish cryptologic attacks on Enigma. According to Gustave Bertrand, "It took superhuman day-and-night effort to overcome this new difficulty: on May 20, decryption resumed."^[62]

Now, to break the Germans' Enigma ciphers, the British at Bletchley Park and the Poles in France would have to rely on the various cryptologic tricks described above (particularly the cillies and Herivel tip), as well as on some others, such as the non-uniformly-placed notches in rotor alphabet-rings that caused the rotor to the left to move one space when the first rotor reached its particular letter-notch.^[63]

After the Franco-German armistice, the Polish cryptological team resumed 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.^[64] 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, preserved the secret of Enigma decryption.^[65]

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 into the Polish Army as privates (they would eventually be promoted to lieutenant) and put to work breaking German SS and SD hand ciphers at a Polish signals facility in Boxmoor. They were not invited to work on Enigma at Bletchley Park.^[66]

[edit] Crib-based decryption

Britain's Government Code and Cipher School (GCCS), before its move to Bletchley Park, had realized the value of recruiting mathematicians and logicians to work in codebreaking teams. In 1938 Alan Turing, a Cambridge University mathematician with an interest in cryptology and in machines to implement logical operations — and who was regarded by many as a genius — had started work for GCCS on a part-time basis.^[67] Gordon Welchman, another Cambridge mathematician, also received initial training in 1938.^[68] Both reported to Bletchley Park on 4 September 1939, the day after Britain declared war on Germany.

Turing recognized that the Germans would likely stop using the insecure method of sending the message key twice, and determined to find an alternative method of cracking Enigma traffic. He also decided to take responsibility for German Naval Enigma, as no one else was looking into it. That was because the superior operator discipline and method of conveying the daily key, rendered the task much more difficult. Turing diagnosed the indicator system that was in use, but was unable to decrypt the traffic on a regular basis. His first break into Enigma naval traffic came in December 1939, into signals that had been intercepted in November 1938.

In January 1940, Turing spent several days at PC Bruno conferring with his Polish mathematician colleagues. He had brought the Poles "Zygalski sheets" that had been produced, using Polish-supplied information, at Bletchley Park but that were not working well there. It turned out that the wirings in the fourth and fifth Enigma rotors that Rejewski had worked out, had been copied down erroneously. Correcting this error allowed the Poles to make, on 17 January 1940, the first break into wartime Enigma traffic — from 28 October 1939.^{[69] [70]}

"Cillies" and Herivel tips were being used by the cooperating British and Polish-French cryptological centers. John Herivel had noticed that German operators were sometimes lazy about choosing random rotor positions for their indicators after changing the rotor ring settings, and so were effectively sending the ring settings almost in clear.^[71]

Later in the war, a German responsible for preparing settings sheets, re-used some of the columns of wheel orders, ring settings or plugboard connections from previous months.^[72] The resulting analytical technique was christened "Parkerismus" in honor of Reg Parker, who had spotted this German error.

The inter-Allied cryptologic collaboration prevented duplication of effort and facilitated discoveries. Before fighting had started in Norway in April 1940, the Polish-French team solved an uncommonly hard three-letter code used by the Germans to communicate with fighter and bomber squadrons and for exchange of meteorological data between aircraft and land. The code had first appeared in December 1939, but the Polish cryptologists had been too preoccupied with Enigma to give the code much attention. With the German assault on the west impending, however, the breaking of the Luftwaffe code took on mounting urgency. The trail of the elusive code (whose system of letters changed every 24 hours) led back to Enigma. The first clue came from the British, who had noticed that the code's letters did not change randomly. If "a" changed to "p," then elsewhere "p" was replaced by "a." The British made no further headway, but the Poles realized that what was manifesting was Enigma's "exclusivity principle" that they had discovered in 1932. The Germans' carelessness meant that now the Poles, having after midnight solved Enigma's daily setting, could with no further effort also read the Luftwaffe signals.^[73][74]

[edit] Sources of cribs

The word "crib" was coined at Bletchley Park to denote any plaintext that was thought or hoped to be present at some point in an enciphered message. "Cribs" were a fundamental part of the British approach to breaking Enigma.

One German operator was asked to send a test message and simply hit the T key repeatedly, then radioed the resulting string of letters. A British analyst received from the intercept stations a long message without a single T in it, and immediately realized what had happened.

Some Enigma operators used "form letters" for daily reports, notably weather reports, in which case the same crib might be used every day. One individual regularly reported that he had "Nothing to report."

In another common operational error, an entire source message (e.g., a weather forecast intended for submarines) would be re-sent after a change of settings. This gave additional advantage to the cipher-breakers.

When a captured and interrogated German revealed that Enigma operators had been instructed to encode numbers by spelling them out, Alan Turing reviewed decrypted messages and determined that the number “eins” ("1") appeared in 90% of messages. He automated the crib process, creating the Eins Catalogue, which assumed that “eins” was encoded at all positions in the plaintext. The catalogue included every possible position of the Enigma's rotors, starting positions, and key-settings.

[edit] British bombe

Main article: Bombe

Replica of a 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 weather ships 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 7 May 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, settings book, 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 seven U-boats and eight 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.

[edit] American bombe

In order to solve Naval Enigma, both Britain and the U.S., but particularly the U.S., 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. ^[75] When Abwehr personnel who had worked on Fish cryptography and Russian traffic were interned at Rosenheim around May 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.^[76] There is even a project to decrypt some remaining messages,^[77] using distributed computing.

[edit] See also

• Tadeusz Pełczyński

[edit] Notes

[edit] References