 |
|
| ||||||||||||||||||||||||||
|
|
| ||||||||||||||||||||||||||
|
|
|
|
|
| ||||||||
| This article is the part of the series on the Enigma cipher machine. |
| Enigma machine |
| Cryptanalysis of the Enigma |
| Ultra |
Enigma is the name of a family of ciphering machines made famous by their use in World War II and the successful analysis of the cipher by Allied codebreakers.
This article discusses the techniques for solving Enigma and the circumstances in which they were developed and applied. See Enigma machine for a description of the machine itself, and Ultra for a discussion of the intelligence gained from reading Enigma.
Ciphers can, of course, be attacked, and the most effective attack method depends on the cipher and its vulnerabilities. By the opening of World War I cryptanalysis departments were often good enough that most ciphers used could be broken given enough time. However, most direct cryptanalytic techniques used then (and now) relied on gaining access to sufficient quantities of text enciphered with a particular key, from which patterns might be discerned with statistics and hard work. Enigma was designed to defeat these basic cryptanalysis techniques by continually changing the substitution alphabet.
The earliest cryptanalytic technique was frequency analysis, in which letter patterns unique to every language could be used to discover information about the substitution alphabet(s) in use in a monoalphabetic substitution cipher. For instance, in English, the plaintext letters E, T, A, O, I, N and S, are usually easy to identify in ciphertext on the basis that since they are very frequent (see ETAOIN SHRDLU), their corresponding ciphertext letters will also be as frequent. In addition, bigram combinations like NG, ST and others are also very frequent, while others are rare indeed (Q followed by anything other than U for instance). The simplest frequency analysis relies on one ciphertext letter always being substituted for a plaintext letter in the cipher: if this is not the case, deciphering the message is more difficult. For many years, cryptographers attempted to hide the telltale frequencies by using several different substitutions for common letters, but this technique was unable to fully hide patterns in the substitutions for plaintext letters. Such schemes were being widely broken by the 1500s.
In the mid-1400s, a new technique was invented by Alberti, now known generally as polyalphabetic ciphers, which recognised the virtue of using more than a single substitution alphabet; he also invented a simple technique for "creating" a multitude of substitution patterns for use in a message. Two parties exchanged a small amount of information (referred to as the key) and used it to create many substitution alphabets, and so many different substitutions for each plaintext letter over the course of a single plaintext. The idea is simple and effective, but proved more difficult to use than might have been expected. Many ciphers were only partial implementations of Alberti's, and so were easier to break than they might have been (eg, the Vigenère Cipher).
Not until the 1840s (Babbage) was any technique known which could reliably break any of the polyalphabetic ciphers. His technique also looked for repeating patterns in the ciphertext, which provide clues about the length of the key. Once this is known, the message essentially becomes a series of messages, each as long as the length of the key, to which normal frequency analysis can be applied. Charles Babbage, Friedrich Kasiski, and William F. Friedman are among those who did most to develop these techniques.
Cipher designers tried to get users to use a different substitution for every letter, but this usually meant a very long key, which was a problem in several ways. A long key takes longer to convey (securely) to the parties who need it, and so mistakes are more likely in key distribution. Also, many users do not have the patience to carryout lengthy, letter perfect evolutions, and certainly not under time pressure or battlefield stress. The 'ultimate' cipher of this type would be one in which such a 'long' key could be generated from a simple pattern (ideally automatically), producing a cipher in which there are so many substitution alphabets that frequency counting and statistical attacks would be effectively impossible. Enigma, and the rotor machines generally, were just what was needed since they were seriously polyalphabetic, using a different substitution alphabet for each letter of plaintext, and automatic, requiring no extraordinary abilities from their users. Their messages were, generally, much harder to break than any previous ciphers.
Fundamentally, Enigma had a library of 16,900 (26 × 25 × 26) substitution alphabets for any given set and ordering of rotors. As long as the message was not longer than 16,900 characters (not likely in practice), there could be no repeated use of a substitution alphabet. But the Enigma machines added other possibilities. The sequence of alphabets used was different if the rotors were started in position ABC, as opposed to ACB; there was a rotating ring on each rotor which could be set in a different position, and the starting position of each rotor was also variable. And most of the military Enigmas added a 'stecker' (a plugboard) which changed several key assignments (eight or more, depending on the model). Even so, this complex combination 'key' could be easily communicated to another user, being only a few simple values: rotors to use, rotor order, ring positions, starting position, and plugboard settings. Potentially, this made the Enigma an excellent system.
The fact that encryption was the same operation as decryption was, at the time, considered to be an advantage of the Enigma. The most common versions were symmetrical in the sense that decipherment works in the same way as encipherment — when one types in the ciphertext the sequence of lit lamps corresponds to the plaintext. However, this works only if the deciphering machine has the same starting configuration (that is, rotor choice, sequence, alphabet ring settings, and initial positions) as had the encrypting machine. These changed regularly (at first monthly, then weekly, then daily and even more often toward the end of the War on some networks) and were specified in key schedules distributed to Enigma users.
The various versions of Enigma provided different levels of security. The presence of a plugboard (stecker) significantly increased the complexity of the machine. In general, unsteckered Enigma could be attacked using hand methods, while breaking versions with a plugboard was more involved, and often required the use of machines.
The Enigma machine had a number of properties that proved very useful to cryptanalysts. Firstly, a letter could never be encrypted to itself (with the exception of the early models A and B, which lacked a reflector). This was of great help in finding cribs — short sections of plaintext that are known (or suspected) to be somewhere in a ciphertext. This property can be used to help deduce where the crib occurs. For a possible location, if any letter in the crib matches a letter in the ciphertext at the same position, the location can be ruled out; this was termed a crash at Bletchley Park.
Another property of the Enigma was that it was self-reciprocal: encryption is performed identically to decryption. This imposed constraints on the type of scrambling that Enigma could provide at each position, and the property was used in a number of codebreaking methods.
A weakness in many versions of the Enigma was that the rightmost wheel would rotate a constant number of places before the next would rotate. The United States declined to use the Hebern rotor machine in part for this reason.
Besides characteristics of the machine itself, the way in which Enigma was used — as a cryptosystem — proved to be the greatest weakness in practice. Mistakes by operators were common, and the procedures for using Enigma provided a variety of avenues for attack. It has been speculated that the Enigma would have been unbreakable if it was used securely.
The commercial Enigma machine was good, but not good enough. The British are said to have broken some messages when it was used in Spain during the Civil War there, and also to have read some Italian traffic encrypted with one of the commercial versions early in WWII (see Ultra). However, when the German Navy began using Enigma in the mid-1920s, decryption of their messages was impossible in practice, as it was also when the German Army began to use a slightly different version in the early 1930's. Reportedly, both British cryptanalysts of the GC&CS (Government Code and Cipher School) and French cryptanalysts gave up, regarding the German military Enigmas as unbreakable.
The effort which broke the German military Enigma more or less began in 1929 when the Poles intercepted an Enigma machine being shipped from Berlin to Warsaw which was mistakenly not protected as diplomatic baggage. It was not one of the military versions, as only the German Navy used the Enigma at the time, but it provided a hint about the German intentions. When the German Army first began using modified Enigmas a few years later, the Poles suspected an Enigma or something similar was being used and attempted to break the system by finding the wirings of the rotors used in the Army version and by finding a way to recover the key (ie, ground settings) used for particular messages.
A young Polish mathematician, Marian Rejewski, made one of the most significant breakthroughs in cryptanalytic history by using techniques from pure mathematics to find a way to do both. Rejewski noticed a pattern that was to prove vital; the indicator procedure was to encrypt an operator-selected message setting twice using a ground setting, and prepend it to their message.
For instance, if an operator picked QRS as their 'message setting', the operator would set the machine to the day's ground settings, and then type QRSQRS. This would might be encrypted as JXDRFT. The feature of Enigma that Rejewski exploited was that the disk moved three positions between the two sets of QRS — knowing that J and R were originally the same letter, as were XF and DT, was vital information. Although the original letters were unknown, it was known that, while there were a huge number of rotor settings, there were only a small number of rotor wirings that would change a letter from J to R, X to F and D to T, and so on. Rejewski called these patterns chains.
Finding the proper chains from the 105,456 possibilities was a tremendous task. The Poles, particularly Rejewski's classmates Jerzy Rozycki and Henryk Zygalski, developed a number of methods. One technique used clear strips for each rotor showing which letters could be chained, with the letters that could not chain being blacked out. Users would pick up the strips and lay them over each other, looking for selections where the three letters were clear all the way through. The British had also developed such a technique when they succeeded in breaking the common commercial Enigma, though they failed to break the military versions of the Enigma.
Of course, several thousand possibilities represent a vast amount of work to analyse by hand. To help with this, the Poles eventually built several "parallel enigma" machines which they called the bomba kryptologiczna (cryptologic bombs; it has been suggested that the name was chosen from a kind of local ice-cream dish, or from the ticking noise the machines made as they ran through the possibilities; the French later changed the name to 'bombe' and the English or Americans to 'bomb'). Possible sets of disks would be loaded into the machine and a message could be tried on the remaining settings one after another, reducing thousands of possibilities to hundreds.
The Poles were able to determine the wiring of the rotors then in use by the German Army and, using them, to decrypt a large portion of German Army traffic for much of the 1930s — until the beginning of WWII. They received some secret assistance from the French, who had an agent (Hans Thilo-Schmidt, codenamed Asch by the French) in Berlin who had access to some Enigma key schedules, manuals, etc. Rejewski's cryptanalytic breakthrough did not depend on that information, as he was not even aware of the agent's existence, and in any case was not given any of the material until after he had made his breakthrough.
Some sources claim that in 1938 a Polish mechanic employed in a German factory producing Enigma machines took notes of the components before being repatriated and, with the help of the British and French secret services, constructed a wooden mockup of the machine. Another story is that the Polish resistance ambushed a German Army vehicle carrying an Enigma machine. In neither case would the ground settings, much less the individual message settings chosen by the operators, be available and so that knowledge, however bravely gained, would be of little worth. Neither of them, nor others including exciting derring-do, are, thus, inherently plausible, as possession of a machine (wooden copy or not) would not be of much cryptanalytic help.
However, in 1939 the German Army increased the complexity of their Enigma use. They had initially distributed only three rotors, and simply moved them around in the slots, but they now introduced an additional two rotors, thus using any three out of five at any particular time. They also had their operators stop sending the individual three letter message settings twice at the beginning of each message, which eliminated the original method of attack.
The Poles, realizing time was running out before the Germans invaded, and unable to extend their techniques with available resources, decided in mid-1939 to share their work, and passed to the French and the British some of their ersatz 'Enigmas', information on Rejewski's breakthrough, and on the other techniques they had developed. The French share was shipped to Paris in diplomatic baggage; the British share went on to Bletchley Park. Until then, German military Enigma traffic had utterly defeated both the British and French, and they had faced the disturbing possibility that German communications would remain "black" for the entire war.
Nearly all the personnel of the Biuro Szyfrow left Poland during the invasion, and most ended up in France working with French cryptographers on German transmissions. Some Polish crypto workers were captured by the Germans before they could leave Poland or while in transit, but fortunately nothing was revealed of the Enigma work. It continued in France at 'Station PC Bruno' until the fall of France (and even somewhat after). Some of the French/Polish workers then managed to escape to England; none were used to help the British cryptanalytic effort against the Enigma networks. When Rejewski himself learned (shortly before his death) of the work at Bletchley Park which he had begun in Poland in 1932, and of its importance to winning WWII, he was astonished.
British attacks on the Enigmas were similar in concept to the original Polish methods, but based on different specifics. First, the German Army had changed their practices (more rotors, different 'message setting', etc), so the Polish techniques no longer worked without modification. Second, the German Navy -- with whom the Poles had not much concern -- had always used more secure procedures, and no one had broken any of their traffic. Alan Turing, the chief of Hut Six -- Naval Enigma -- at Bletchley Park, made important contributions here as did Gordon Welchman his eventual replacement in charge of Hut Six.
One new attack relied on the fact that the reflector (a patented feature of the Enigma machines) guaranteed that no letter could be enciphered as itself, so an A could never turn back into an A. This was combined with knowledge of various common German phrases, like "Heil Hitler" or "please respond", which were found to frequently be in this or that plaintext; successful guesses as to the plaintext were known at Bletchley as cribs. With a probable plaintext fragment and the knowledge that no letter could be enciphered as itself, it wasn't uncommon that a corresponding ciphertext fragment could be guessed by trying every possible alignment of the crib against the ciphertext, a procedure known as crib dragging. Out of the possible guesses, some would turn out to be true plaintext/cyphertext pairs. This provided a large hint as to the message settings, much in the same way the message setting codes had done for the Poles before the War started.
German operators themselves also gave the decrypters immense help on a number of occasions. In one instance an operator was asked to send a test message, so he simply hit the T key repeatedly and sent it. A British analyst received a long message without a single T in it from the interceptor stations, and immediately realised what had happened. In other cases, Enigma operators would constantly use the same settings for their message codes, often their own initials or those of their girlfriends. Analysts were set to finding these messages in the sea of intercepted traffic every day, allowing Bletchley to use the original Polish techniques to find the initial settings for the day. Other German operators used "form letters" for daily reports, notably weather reports, so the same crib could be used every day.
Had the Germans ever replaced every rotor at the same time, it is possible that the British would not have been able to break back into the system. However, both because of the expense and because of the difficulty of getting all those new rotors to all the necessary ships and units, it was never done. Instead the Germans simply added new rotors to the mix every so often, allowing the settings of the newest ones to be deciphered after a short period.
On 7 May 1941 the Royal Navy deliberately captured a German weather ship, together with cipher equipment and codes. They did it again shortly afterwards. And, 2 days later U-110 was captured, together with an Enigma machine, code book, operation manual and other information. Naval Enigma was readable through the end of June.
In addition to U-110, Naval Enigma machines or settings books were captured from a total of 7 U-boats and 8 German surface ships, including U-boats U-505 (1944), and U-559 (1942), as well as from 2 German weather-reporting boats, from some converted trawlers, a small vessel (the Krebs) captured during the raid in the Lofoten Islands off Norway, and so on. Several other more imaginative techniques were dreamed up, including Ian Fleming's suggestion to "crash" captured German bombers into the sea near German ships, hoping to be "rescued" by the crew, which would then be taken captive by the Commandos hiding in the plane and the crypto material captured intact.
However, like the Polish system, the new tricks only reduced the number of possible settings for a message. The number remaining was still huge, and due to the new rotors the Germans had added from time to time, that number was much larger than the Poles had been left with. In order to solve this problem the Allies, especially the US, "went industrial", and produced much larger versions of the Polish bomba that could test thousands of possible key settings very rapidly indeed.
By 1945 almost all German Enigma traffic (Wehrmacht, Navy, Luftwaffe, Abwehr, SD, etc.) could be decoded within a day or two, yet the Germans remained confident of its security. They considered Enigma traffic sufficiently secure that they openly discussed their plans and movements, handing the Allies a huge amount of very useful information, not all of which was properly used. For example, both Rommel's actions at the Kasserine Pass, and the preparations for Battle of the Bulge were clearly foreshadowed in decrypted German Enigma traffic, but the information was not properly appreciated in either case.
After the War, the American TICOM project teams found and detained a considerable number of German crypto personnel. Among the things they learned was that German cryptographers, at least, understood very well that Enigma messages might be read; they knew Enigma was not unbreakable. They just found it impossible to imagine anyone going to the immense effort required.
|
||||
| View Live Article | This article is from Wikipedia. All text is available under the terms of the GNU Free Documentation License | |
||
