|
|
|
|
Cryptanalysis of the Enigma
|
| |
|
| |
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 contributed greatly to the success of Allied war efforts—in the Battle of Matapan in March 1941; in reversing the early disastrous course of the Battle of the Atlantic, beginning in the latter part of 1941; in frustrating Rommel's efforts to capture Cairo in 1942; in the invasion of Sicily (1943) and mainland Italy (1943–44); in the planning and execution of Operation Overlord (the Allied invasion of France, 1944); and in the subsequent drive to and through Germany.
Discussion
Ask a question about 'Cryptanalysis of the Enigma' Start a new discussion about 'Cryptanalysis of the Enigma' Answer questions from other users |
Encyclopedia
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 contributed greatly to the success of Allied war efforts—in the Battle of Matapan in March 1941; in reversing the early disastrous course of the Battle of the Atlantic, beginning in the latter part of 1941; in frustrating Rommel's efforts to capture Cairo in 1942; in the invasion of Sicily (1943) and mainland Italy (1943–44); in the planning and execution of Operation Overlord (the Allied invasion of France, 1944); and in the subsequent drive to and through Germany. Evidence suggests that Soviet strategy and tactics against Nazi Germany likewise benefited from Ultra intelligence, conveyed to the Soviets by a variety of conduits.
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.
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 held 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 its 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.
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.
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). 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.
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. This led to the development, in several countries, of rotor cipher machines such as Arthur Scherbius' Enigma.
Rotor cipher machines alter each character in the plaintext to produce the ciphertext, by means of a scrambler comprising a set of rotors that alter the electrical path from character to character, between the input device (in Enigma, a keyboard) and the output device (in Enigma, a lampboard). This constant altering of the electrical pathway produces a very long period before the pattern—the key sequence or substitution alphabet—repeats.
Although Kerckhoffs' principle states that a cryptosystem should be secure even when everything about the system except the key is known to the enemy, the internal wiring of machines such as Enigma has so many possibilities that an important aspect of breaking them is deducing their logical structure.
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.
Strengths of Enigma
The Enigma was potentially an excellent system. It 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). Such a long period prevented any detectable repetition in the enciphering sequence.
The mechanism of the Enigma consisted of a keyboard connected to an entry plate or wheel (German: Eintrittswalze), at the right hand end of the scrambler (usually via a plugboard in the military versions). This contained a set of 26 contacts that made electrical connection with the set of 26 spring-loaded pins on the right hand rotor. The left hand side of each rotor in turn made electrical connection with the rotor to its left, and in the case of the leftmost, with the reflector (German: Umkehrwalze). The reflector provided a set of thirteen paired connections to return the current back through the scrambler rotors, and eventually to the lampboard.
There are 403 trillion trillion (26 factorial) ways that the connections within each scrambler rotor—and between the entry plate and the keyboard or plugboard or lampboard—can be arranged. For the reflector plate there are a mere six billion (13 factorial) options to its possible wirings.
Whenever a key on the keyboard was pressed, the stepping motion was actuated, moving the rightmost rotor on one position. Because it advanced with each key pressed it is sometimes called the 'fast' rotor. When the notch on that rotor engaged with a pawl on the middle rotor, that too moved. And similarly with the leftmost ('slow') rotor.
Each scrambler rotor could be set to any one of its 26 starting positions (any letter of the alphabet). For the Enigma machines with only three rotors, their sequence in the scrambler could be selected from the six that are possible.
Possible rotor sequences | Left | Middle | Right |
|---|
| I | II | III | | I | III | II | | II | I | III | | II | III | I | | III | I | II | | III | II | I |
Later Enigma models added a variable alphabet ring like a tyre around the core of 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.
Most military Enigmas also featured a plugboard (German: Steckerbrett) which exchanged letters reciprocally, so that if A was plugged to G then A would become G and G would become A either on input from the keyboard to the scrambler, or on output from the scrambler to the lamp panel.
Key setting
The machine 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, the complex ground-key setting (German: Grundstellung) was distributed to all users of a network by means of "setting sheets" in a codebook. These setting-sheets changed the ground key regularly (at first monthly or weekly, but soon daily and even, toward war's end in some networks, several times a day). The setting sheets specified for each date: the three rotors to be used and their positions (German: Walzenlage), the ring positions (German: Ringstellung) and the plugboard connections (German: Steckerverbindungen ).
Lastly, for each message, the transmitting operator would send the key specific to that message so that the receiving operator could align his rotors appropriately. This was called the "indicator" for that message and was the initial letters that would be visible through the windows on Enigma's top plate. This key setting was itself enciphered on the machine using an "indicator setting". At first this was specified on the setting sheets, but later on it was selected by the operator or, in the case of the German Navy, by a more complicated and secure procedure. Because of the danger that poor radio reception might lead to the message key being garbled, it was, until May 1940, sent twice.
Security properties
Despite the undoubted strengths of Enigma when used properly, if the settings for one day (or whatever period was represented by each row of the setting sheet) were established, the rest of the messages for that day could be decrypted.
The various Enigma models provided different levels of security. The presence of a plugboard (Steckerbrett) substantially increased the security of the encipherment. Each pair of letters that were connected together by a plugboard lead, were referred to as "stecker partners", and the letters that remained unconnected were said to be "self-steckered". 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, and also some Italian traffic enciphered early in World War II.
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. 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". 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.
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.
Polish breakthrough
In 1928 the German Army (German: Heer), Navy (German: Reichsmarine later Kriegsmarine ) and Airforce (German: Luftwaffe) began using a 3-rotor Enigma with a 6-cable plugboard. British, French and American cryptanalysts had no success in cracking this Enigma version. In Poland, however, the threat from Germany was much greater, and the Polish Cipher Bureau (Biuro Szyfrów) in Warsaw continued work on it. On 1 September 1932, a 27-year-old Polish mathematician, Marian Rejewski, joined the Bureau along with two somewhat younger fellow Poznan University mathematics graduates, Henryk Zygalski and Jerzy Rózycki.
In December that year, the Polish Cipher Bureau received from Captain Gustave Bertrand of French Military Intelligence two German documents and two pages of Enigma daily keys (for September and October 1932) that had been obtained by a French military intelligence agent, a German code-named Rex, from an agent who worked at Germany's Cipher Office in Berlin (Hans Thilo-Schmidt, whom the French code-named Asché). The documents were entitled "Gebrauchsanweisung für die Chiffriermaschine Enigma" ("Instructions for Using the Enigma Cipher Machine") and "Schlüsselanleitung für die Chiffriermaschine Enigma" ("Keying Instructions for the Enigma Cipher Machine").
The tables of daily keys, Rejewski would later recall, were "a great help to me, because thanks to [them] the number of unknowns in the equations [that Rejewski had set up] was reduced, and I was able to solve [the] equations, and... as I was sitting there writing, the internal connections just came out in the form... of letters or numbers, I don't recall [which]—the internal connections ["wiring"] for the first [rotor], the one... on the far right, which always... revolved at every depression of a key."
Rejewski told Richard Woytak that
about 1932, when he first broke Enigma]]
Rejewski thus made one of the most important breakthroughs in cryptologic history by using elementary group theory to solve the Enigma wiring and rotor settings. His method made it possible to derive the rotor settings independently of the plugboard connections.
A crucial inspired guess on Rejewski's part was that the connections between the keyboard and the entry ring were in alphabetical order, rather than in the order of the keys on a German typewriter keyboard: QWERTZUIO... — the order that was used in the commercial Enigma. Britain's Dilly Knox was astonished when he learned from the Poles, in Warsaw in July 1939, that the entry-ring order was so simple.
After Rejewski had reconstructed the plugboard-equipped Enigma machine, the Poles were 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.)
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). 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 decipher 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 was exploited by the Poles.) The receiving operator would then decipher the message, 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:
| First letter | A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z |
|---|
| Third letter | X | F | E | A | R | B | S | L | H | Q | I | G | C | V | D | Z | W | K | M | N | J | U | O | Y | T | P |
|---|
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.
| Cycle group starting at A (12 links) | (A, X, Y, T, N, V, U, J, Q, W, O, D, A) |
|---|
| Cycle group starting at B (2 links) | (B, F, B) |
|---|
| Cycle group starting at C (10 links) | (C, E, R, K, I, H, L, G, S, M, C) |
|---|
| Cycle group starting at P (2 links) | (P, Z, P) |
|---|
|
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).
This method stopped working for German naval Enigma messages on 1 May 1937, when the indicator procedure was changed substantially, making it very much more difficult to break.
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."
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."
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."
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. 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. This meant that the cycle-pattern method would no longer work.
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" or "Netz". 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" (in English, "females"—a term later used at Bletchley Park). 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.
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:
Polish bomba
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". 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 (one for each rotor arrangement) were ready, and reconstruction of daily keys went on apace.
Rejewski has written about the device:
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.
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.
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. 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. Now, from 1 January 1939, the number of plug connections was increased to between seven and ten.
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:
World War II
Italian Naval Enigma
During the Spanish Civil War, Italy, under Italian Fascism, was on the side of Francisco Franco's Nationalists. The Italian Navy used a version of Enigma that did not have a plugboard. In 1937 Dillwyn 'Dilly' Knox, a gifted British cryptanalyst veteran of World War I and the cryptanalytical activities of Room 40, managed to break this cipher, using a technique that he called 'buttoning up' to discover the rotor wirings and another that he called "rodding" to break messages. This relied heavily on cribs and on crossword expertise in Italian, as it yielded a limited number of spaced-out letters at a time.
When in 1940 Dilly Knox wanted to establish whether the Italian Navy were still using the same machine, he instructed his assistants to use rodding to see whether the crib PERX (per being Italian for 'for' and X being used to indicate a space between words) worked for the first part of the message. After three months there was no success, when Mavis Laver, a 19-year-old student, found that rodding produced PERS for the first four letters. She then (against orders) tried beyond this and obtained PERSONALE (Italian for 'personal'). This confirmed that the Italians were indeed using the same machines and procedures.
The subsequent breaking of Italian Naval Enigma ciphers led to substantial Allied successes. The cipher-breaking was disguised by sending a reconnaissance aircraft to the known location before attacking the warship, so that the Italians assumed that this was how they had been discovered. The British Royal Navy's victory at the Battle of Matapan (March 1941) was considerably helped by Ultra intelligence obtained from Italian Naval-Enigma signals.
Polish disclosures
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. 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:
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". Dilly Knox was a member of the British delegation. He commented on the fragility of the Polish system's reliance on the repetition in the indicator because it might, "at any moment be cancelled".
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.
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,
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.
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. 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.
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.
PC Bruno and Bletchley Park worked together closely from late 1939, communicating via a telegraph teletype line secured by the use of Enigma (!). The French would close their Enigma-enciphered messages with an appreciative "Heil Hitler!"
In January 1940, the British cryptologist Alan Turing spent several days at PC Bruno conferring with his Polish colleagues. He had brought the Poles "Zygalski sheets" that had been produced at Bletchley Park by John Jeffreys using Polish-supplied information, but which were not working. It turned out that the wirings in Enigma rotors IV and V that Rejewski had worked out, had been copied down wrongly. Correcting this error allowed the Poles to make, on 17 January 1940, the first break into wartime Enigma traffic—that from 28 October 1939.
During this period, until the collapse of France in June 1940, ultimately 83 percent of the Enigma keys that were found, were solved at Bletchley Park, the remaining 17 percent at PC Bruno. Rejewski comments:
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.
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" 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."
At this stage, to break the Germans' Enigma ciphers, the cooperating British at Bletchley Park and the Poles in France would have to rely on exploiting the operator weaknesses described below (particularly the cillies and the 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.
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.
The Cipher Bureau's chiefs, Colonel Gwido Langer and Major Maksymilian Ciezki, and some of the technical staff were captured by the Germans but, despite extensive interrogation, preserved the secret of Enigma decryption.
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ózycki, 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.
Operating shortcomings
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 them, 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."
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]..." 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; 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).
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.
Another important error perpetrated by German operators, was anticipated by John Herivel soon after his arrival at Bletchley Park in January 1940, although it did not occur until after the changes of 10 May that year, during the period of close collaboration between the British, French and Poles. Some operators, 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, they were effectively sending the ring settings almost in clear. This was called "Herivelismus" or the "Herivel tip". During the first part of 1940, this meant that the French duty cryptologist could, at a few minutes past midnight, read Wehrmacht signals at the same time as their intended recipients.
One operator was in the habit of using the positions of the rotors at the end of one message (or one quite close to it), as the indicator setting for the next message.
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. The resulting analytical short-cut was christened at Bletchley Park "Parkerismus" in honour of Reg Parker, who had, through his meticulous record-keeping, spotted this phenomenon.
Crib-based decryption
The term "crib" was used at Bletchley Park to denote any known plaintext or suspected plaintext at some point in an enciphered message. This cryptanalytic approach was thus a type of known-plaintext attack. A large part of the Polish successes had relied on the repetition within the indicator; as soon as Alan Turing moved to Bletchley Park, initially joining Dilly Knox in the research section, he set about seeking methods that did not rely on this weakness, as they anticipated, correctly, that the Germans might not continue it for long.
The Poles had used an early form of crib-based decryption in the days when only six leads were used on the plugboard, leaving 14 letters self-steckered. The technique became known as the "Forty Weepy" method for the following reason. When, on the basis of external evidence, a message was thought to be a continuation of a previous message, the plaintext would start with "FORT" (from Fortsetzung, meaning "continuation") followed by the time of the first message. At this time numerals were represented by the letters on the top row of the Enigma keyboard.
Top row of the Enigma keyboard and the numerals they represented | Q | W | E | R | T | Z | U | I | O | | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | | (Zero was represented by P) | |
To indicate that a letter or a string of letters represented numbers, a letter Y was placed either side of them. So, "continuation of message sent at 2330" was represented as "FORTYWEEPY".
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. Turing, a Cambridge University mathematician with an interest in cryptology and in machines for implementing logical operations—and who was regarded by many as a genius—had started work for GCCS on a part-time basis in 1938. Gordon Welchman, another Cambridge mathematician, had also received initial training in 1938, and both reported to Bletchley Park on 4 September 1939, the day after Britain declared war on Germany.
One fundamental feature of Enigma that was of enormous help to cryptanalysts was the fact that the reflector (a patented feature of Enigma machines) guaranteed that no letter could be enciphered as itself. Cryptologists combined an awareness of this fact with knowledge of cribs. With such a combination of probable plaintext fragment and the fact that no letter could be enciphered as itself, a corresponding ciphertext fragment could often be tested by trying every possible alignment of the crib against the ciphertext, a procedure known as crib-dragging. Of the possible guesses, some would turn out to be true plaintext-ciphertext pairs. This provided a clue to message settings. Crib-dragging allowed the elimination of possible crib positions. Comparing one crib that appeared quite frequently, "Keine besondere Ereignisse" (literally, "No special occurrences"—perhaps better translated as "Nothing to report"), with a section of ciphertext might produce the following, where the red cells represent "crashes", the co-occurrence of the same letter in the crib and the ciphertext:
Exclusion of possible positions for the crib "Keine besondere Ereignisse" | Ciphertext | O | H | J | Y | P | D | O | M | Q | N | J | C | O | S | G | A | H | L | E | I | H | Y | S | O | P | J | S | M | I | U |
|---|
| Position 1 | | | K | E | I | N | E | B | E | S | O | N | D | E | R | E | E | R | E | I | G | N | I | S | S | E | | | | |
|---|
| Position 2 | | | | K | E | I | N | E | B | E | S | O | N | D | E | R | E | E | R | E | I | G | N | I | S | S | E | | | |
|---|
| Position 3 | | | | | K | E | I | N | E | B | E | S | O | N | D | E | R | E | E | R | E | I | G | N | I | S | S | E | | |
|---|
| Positions 1 and 3 for the crib are impossible because of matching ciphertext letters.
Position 2 is a possibility. |
|---|
|
Crib-dragging was only one aspect of the processes of breaking a key. Derek Taunt, a Bletchley Park cryptanalyst, has written that the three cardinal personal qualities that were in demand were (1) a creative imagination, (2) a well-developed critical faculty, and (3) a habit of meticulousness. The use of the bombes allowed the rotor order, the rotor core starting positions and the stecker partner for a chosen letter to be discovered. However, considerable manual cryptanalytic work was required to design "menus" for the bombes, to test their various "stops" and to work out the remaining stecker partners (plugboard connections).
Sources of cribs
"Cribs" were a fundamental part of the British approach to breaking Enigma.
Mavis Lever, a member of Dilly Knox's team, recalled an occasion when there was an extraordinary message.
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, interrogated German revealed that Enigma operators had been instructed to encipher numbers by spelling them out, Alan Turing reviewed decrypted messages and determined that the number “eins” ("one") 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 rotor position, starting position, and key setting.
British bombe
Alan Turing, chief of Hut Eight (Naval Enigma) at Bletchley Park, and Gordon Welchman, head of Hut Six, made important contributions to efficient Enigma-breaking.
It was on cribs that the British bombe, designed by Alan Turing and Gordon Welchman, relied. Assuming that a triple loop were found, e.g. abc, this meant that, with a crib, plaintext letter a was 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 were assembled serially in-line and set to the original rotor positions, with their offset (here, 1 step each) accordingly. Then a corresponding wire closed loop was obtained. This could be detected with lamps connected to the rotor contacts. The lamp in the wire loop would stay dark. Now the rotor systems were turned synchronously. If only one lamp stayed dark because of the one wire loop, the Steckerfeld (plug field) could be quickly calculated, and the positions with all lamps lit rejected. This typically happened several times in the 17,576 possible rotor settings.
German Naval Enigma
Alan Turing decided, soon after arriving at Bletchley Park, to take responsibility for German Naval Enigma, as no one else was looking into it. That was because the superior operator discipline and procedure for conveying the daily key, rendered decryption much more difficult. Turing diagnosed the indicator system that was in use, but was unable to decrypt the traffic on a regular basis. As well as the Kriegsmarine procedures being much more secure, the naval Enigma variant featured a set of eight rotors, from which three were selected. This meant that there were 336 possible rotor combinations, alone.
Turing's first break into naval Enigma traffic came in December 1939—into signals that had been intercepted in November 1938. For routine breaking, he needed information from German codebooks. No useful headway was made until the capture of the armed trawler Polares on 26 April 1940, which became known as the Narvik Pinch. Keys for April 1940, an instruction manual, and codebooks were secured. As a consequence, by June or July 1940 Hut 8 at least knew what content to expect in Kriegsmarine messages and knew the details of encipherment and decipherment procedures. However, the numerous possible rotor sequences, together with a lack of usable cribs, made the usual cryptanalytic methods almost useless.
Turing 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, Hut 8 would identify at least the rightmost rotor being used in the cipher that day. If the cryptologists 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 cryptologists learned to fully exploit a serious security lapse 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 furnishing Bletchley Park with regular cribs. This was crucial to Bletchley's attacks on the U-boat four-rotor Enigma that was introduced in 1942.
Enigma-cipher material was captured at sea. The first such capture occurred in February 1940, when rotors VI and VII, whose wiring was then unknown, were captured from the U-33. On 7 May 1941 the Royal Navy captured a German weather ship, together with cipher equipment and codes. Shortly afterward the Royal Navy did it again. And two days later the U-110 was captured, complete with Enigma machine, settings book, operating manual and other information. As a result, Naval Enigma became readable directly through the end of June. From then on, Banburismus allowed it to be read fairly continuously until, in mid-1943, newer, faster bombes rendered Banburismus unnecessary.
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-559 (1942) and U-505 (1944), two weather trawlers, and a small vessel (the Krebs) captured during a raid on the Lofoten Islands off Norway.
Other schemes were dreamt up but not used, including Operation Ruthless by Ian Fleming (author of the James Bond novels—who was a Lieutenant Commander in Naval Intelligence), who suggested that a captured German bomber follow a departing bombing raid on Britain and be crashed into the sea near a German recovery vessel, hoping that the plane's crew would be rescued. The British crew would all be fluent German-speakers and would wear German Air Force uniforms. They would be armed and aim to capture the ship's cryptographic materials, including an Enigma. Alan Turing and Peter Twinn were very disappointed when this operation was canceled.
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.
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 openly discussed their plans and movements, handing the Allies huge amounts of information, not all of which was used effectively. For example, Rommel's actions at the Kasserine Pass were clearly foreshadowed in decrypted Enigma traffic, but the information was not properly appreciated by the Americans.
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. 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.
Since World War II
Modern computers can be used to solve Enigma, using a variety of techniques. There is even a project to decrypt some remaining messages, using distributed computing.
See also
External links
- Dayton Daily News, .
- Dayton Codebreakers Web site,
-
-
-
-
|
| |
|
|
.jpg)
