Enigma machine
| File:Enigma.png |
| Fig. 1 - The Enigma Machine |
The Enigma was an electro-mechanical encrypting machine. It was developed by a Berlin company founded by the German Arthur Scherbius using several inventions the first of whose patent filings date from 1919 (one of these was by Scherbius himself). The first commercial version of the machine was offered for sale from 1923. It was bought and adapted by the German Navy in 1926, by the German Army a couple of years later, the Abwehr soon thereafter, etc. There were versioins for just about every Nazi military or party organization. In one or another version, it was very heavily used in World War II. The British war-time encryption machine (Typex) and the American one (SIGABA or M-134-C) were similiar in principle to Enigma, but far more secure.
Operation
The enigma machine was an electro-mechanical encoding device. In general terms a battery was used to provide an electrical current that travelled through the keys of a typewriter, lighting up a small light bulb whenever one of the keys was held down. In the picture to the right you can see the typewriter keys at the front of the machine, which are pushbuttons, and the lights are the small (barely visible) circles "above" the keyboard in the middle of the machine.
The heart of cypher system of the machine consisted of several connected rotors. A rotor is a round flat disk (somewhat similar to a hockey puck) with 26 contacts on each side, arranged in a circular manner around the edge of the disk. Every contact on one side of the disk is wired to a different contact on the other side. For instance, in a particular rotor the contact that would represent the letter A might be wired to the contact for J on the other side, B on one side to X, and so forth. Each rotor in an Enigma was wired differently than the others, and the German military/party models used different rotor wirings than did the commercial models.
Inside the machine was a ser of three slots into which the rotors could be placed. Inside the slots the rotors were "stacked" in such a way that the contacts on the "output" side of one rotor were in contact with the "input" contacts on the next. The third rotor was connected to a reflector which was hard wired to feed outputs of the third rotor back into different contacts of the third rotor, thence back to the first rotor, but by a different route. In the picture you can see the three stacked rotors at the very top of the machine, with a disk protruding from the surface that allows the rotors to be turned by hand.
When a key was pressed on the keyboard, the power of the battery for that letter, say A, would be fed into the A position of the first rotor. There it would travel through the rotor's internal wiring to the J. It would then go into the next rotor, perhaps turned such that the J was lined up with X. From there it would travel to the other side of the second rotor, and so on. By the time the signal had travelled through the rotors and back, some other letter would light up – thus substituting one letter for another, the key to all encryption systems.
All this allowed the final substituted letter to change simply by moving the rotors, either by substituting new rotors (the Navy initially issued a set of 5, of which 3 were used at any one time), by changing the order of the installed rotors, or by simply rotating them one or more positions. Users were provided with several rotors and would change their settings (order, initial position, ...) every day.
The machine was symmetrical in the sense that decryption works in the same way as encryption: type in the encrypted text and the sequence of lit lamps will correspond to the plain text. However, this works only if the decrypting machine has the same configuration as had the encrypting machine (rotor sequence, wiring, ring settings, and initial positions); these changed regularly (daily and later much more often) and were specified in key schedules distributed to Enigma users.
Encoding Methodology
If this were all the Engima did, it would serve to reduce the complexity of sending code books about (normally a very serious problem as any code book could, and often was, captured or copied). The Enigma operators could construct a (tremendously) large variety of different cyphers by selecting which disks and settings to use, as opposed to sending out a long book full of code substitutions. The rotors themselves would "build" the cyphertext automatically from those settings.
However this alone does not make the cypher itself more secure. All simple substitution cyphers can be attacked using a mathematical method that only requires enough encoded text from any one "key", in this case a collection of messages from any one day.
The true worth of the Enigma was that it changed the substitution pattern (this letter for that one) not just every day, but every time a letter on the keyboard was pressed. After each key press the end rotor was rotated one position through a mechanical linkage, which is why the keys are so "tall". If it had completed one full rotation (26 positions), the second rotor will advance by one position. After the second rotor advanced 26 times, the third rotor advanced one position. Some Enigma models caused a step motion of the next rotor after other than a single full rotation of the preceding rotor. But these models were not commonly used, which considerably helped Allied cryptographers for they would have been much more difficult to break.
This too was not thought to be enough to 'guarentee' safety of the encyphered messages. If every message used the same settings of the rotors, this would better, but not hugely better than other good substitution cyphers. Patterns would eventually be found if enough traffic from any one day could be found, and thousands of messages were encoded on Enigma every day.
German Army and Air Force operators were at first trained to use the system by setting up the machine in the morning using the initial settings which were sent out in a book once a month. For every message they wanted to send, they would select three letters at which to start the disks, called the message settings. They would then set the machine to the initial settings and type in the three message setting letters, writing down the encoded version. The rotors were then spun to the message settings, and the rest of the message encoded.
To decode such a message, the receiver sets his machine to the initial settings and types in the three letters at the start of the message. Now decoded, he spins his rotors to the message settings, and decodes the rest of the message.
The Navy's procedures were always more complex and continued to be so during the entire War.
This system of operation means that every single message sent will use different settings, and thus a completely different key. The Enigma's security relied on an immense number of possible keys, which could be selected with trivial ease. Since the rotors were connected together, simply rotating any of them a few positions resulted in a completely different sequence of subsitutions being generated.
In theory you could attack the message settings themselves (part of the key for a message) because all messages are set to the same settings every day for that portion of the message. But the technique ordinarily used to attack substitution cyphers relies on having lots of text in a known language. The message settings were simply too small to be used in this fashion, even if every single one was captured you would have too little text, and it wasn't in any known language, they were simply random letters.
Given that the keys were difficult to attack and yet easy to generate, and that any given key generated different substitutions for every letter in the message, the Enigma seemed foolproof. In the Enigma (and similar machines) the plaintext letter pattern was so well concealed that the usual statistical methods simply did not work. As long as the users didn't use the same sets of message settings again, the code was believed to be largely unbreakable as there were simply too many positions to test every one.
Breaking the Enigma
The efforts to break the German code began in 1929 when the Poles intercepted an Enigma machine being shipped from Berlin and mistakenly not protected in diplomatic baggage. It was not the military version of the machine, but seems to have provided some hint to the Poles the Germans would be using an Enigma type machine in the future. When the German Army began using modified Enigmas a few years later, the Poles 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 settings used for particular messages.
A young Polish mathematician, Marian Rejewski, made one of the most signficant breakthroughs in cryptanalytic history by using fundamental mathematical and statistical techniques to find a way to do both. His approach initially relied on a simple flaw in the system for using the Engima as particed by the German army users. In order to ensure that the initial settings — supposedly picked at random by every user – were received correctly at the far end, the operators encoded these settings twice at the start of every message.
Normally this would not be a problem, because while this "message" was being encoded with the same partial key every time (that day's initial settings), even at six letters long it was still too small to attack statistically. However Rejewski noticed another pattern that was to prove vital; since the code was repeated twice, you could guess the wiring of the rotor not by the letters themselves, but by the way they changed.
For instance let's say an operator picked ABC as their message settings. They would set the machine to the day settings, and then typed ABCABC. This would turn into something like JXDRFT. Now this looks like (and is almost) gibberish, but the clue was that the disk has moved three positions between the two sets of ABC – we know that J and R are originally the same letter, and the same for XF and DT. We don't know what the letters are, but nor do we care, because while there are a huge number of rotor settings, there are only a small number of rotors that will have a letter go from J to R, X to F and D to T. If you know the wiring for the rotors, you can go from billions of combinations to a few thousand. These patterns were known as chains.
Of course a few thousand is also a lot of codes to check. To solve this problem the Poles built a set of "parallel enigma" machines they called the bomba kryptologiczna (cryptologic bomb). (Suggestions are that the name was chosen from a kind of local ice cream dish, or from the ticking noise the machine made as it ran through the possibilities; the French later changed it to 'bombe' and the English to 'bomb'). Possible sets of disks would be loaded into the machine and then a message could be tried on all of the settings at once. Now you were down to hundreds.
The Poles were able to determine the wiring of the rotors then in use by the Germans and, using them, to decrypt a large portion of German traffic for much of the 1930s. They received some assistance from the French, who had an agent in Berlin who had access to Enigma key schedules, manuals, etc. Rejewski's cryptanalytic breakthrough did not, however, depend on that information.
However in 1939 the German Army increased the complexity of their Enigmas. Whereas in the past they had only three rotors and simply moved them from slot to slot, they now introduced an additional two rotors to the mix. They also had their operators stop sending the message settings twice, which eliminated the original method of attack. The Poles, realizing time was running out before the Germans invaded, gave copies of their achievements to the French and the British.
Some sources claim (without much support from participants' accounts) 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. There's also a story about an ambush by the Polish resistance of a German Army vehicle carrying an Enigma machine...
In any case, the Poles decided in mid-1939 to share their work, and passed to the French and the British some of their ersatz 'Enigmas', information on Rejeski's breakthrough, and on the other techniques they had developed. The information was shipped to France in diplomatic baggage and the British share on to Bletchley Park in England.
Breaking the cypher
With this massive assist, the British began to work on the German Enigma traffic themselves. Early in 1939 Britain's secret service set up its Code and Cypher School at Bletchley Park, 50 miles (80 km) north of London, for the purpose of intercepting the Germans' message traffic and controlling the distribution of the resultant secret information. There, British mathematicians and cryptographers, among them Alan Turing, conquered the problems presented by many of the German Enigma variations, and found means of cracking their ciphers. The information so produced was eventually termed Ultra. Strict rules were established to restrict the number of people who knew about the existence of the Ultra information and to ensure that no actions would alert the Axis powers that the Allies possessed knowledge of their plans.
Several raids and shipping heists were carried out to capture books containing the list of initial settings for the Naval Enigma, which was a much tougher problem than the Army or Air Force variants. During the war, Enigma machines or settings books were captured from U-boats U-110, U-505, and U-559, as well as a number of German weather reporting boats, some converted trawlers, and so on. Without these captures Bletchley Park would have not known any of the settings used by the Navy. And without them, Naval Enigma would have most likely remained essentially closed. On several occasions during the war the Germans (especially the Navy) changed their use of the Enigma or introduced new rotors, effectively blacking out the British efforts. They would continued to be blacked out until the next intercept of a setings book.
British attempts to decode the messages were similar in concept to the Polish systems, but used a different series of patterns to start with. One was that due to the way the Enigma rotors were wired, no letter encoded onto itself. That meant that an A on the keyboard could never be translated back into an A. In on famous instance an Enigma operator was asked to send a test message, and did so by repeatedly pressing the L key. One of the decoders in England noticed that a message had no L's, and emediately realized what had happened. It was only a few minutes before that days settings had been cracked.
Even without such lucky coincidences, this pattern could be used in a more "normal" fashion. The classic way to defeat a cypher is to guess at some of the original plaintext and see if you can find it in the cyphertext. In this case one could guess at some snippet of a message, say "message received", and then look for it by making sure that none of the letters lined up in the cyphertext. If you saw the initial m in the same location in the cyphertext you knew it couldn't be there, and shifted down one position and tried again. Sooner or later there would be no "hits", eliminating a huge number of possible settings.
Of course this required you to have some idea what the messages might contain. In order to get a set of such messages, the British took to enterprising schemes. In one example they dropped mines into the sea where they could easily be seen from shore or submarines, and then listened from messages broadcast from nearby. There was a very good chance the word "mine" would appear in the message, often along with coordinate information. Others simply looked at huge volumes of information during those times when they had up-to-date settings books and almost everything was being decoded. By 1943 they had collected a number of such snippets, and changes to the code books were no longer a problem.
However, like the Polish system, this attack only reduced the number of possible settings. The number remaining was still huge, and due to the new rotors the Germans had been adding, much larger than the numbers the Poles were left with. In order to solve this problem they simply "went industrial" and produced huge versions of the Polish bomba that could test hundreds of keys at once.
Many accounts of these events, and of other WWII crypto happenings, have been published. Several are unreliable in many respects. This is due to several reasons.
- First, not all of the authors were in a position to know (eg, several books have been published by those on the Ultra distribution side at Bletchley Park, but work there was very seriously compartmented making it difficult to credit some episodes when they are due only to such a source);
- second, the work done was tricky and quite technical (those without sympathy for it are not likely to have gotten all the details quite right);
- third, documents have been lost in secret archives, took decades to finally be released to the public, and in any case were not originally made with historical clarity in mind;
- fourth, governments have chosen to keep secret or release information to serve their purposes, not public knowledge;
- fifth, several authors have their own agendas (at least one incident is known of fabrication regarding British cryptanalytic progress on a particular WWII Japanese Navy crypto system -- the account was claimed to have been written from the unpublished memoirs of an Australian cryptanalyst, but important parts were simply invented to fit the writer's convenience);
- sixth, many writers have not done the research (the exact fate of Asch was not publicly known till Sebag-Montifiore chased his daughter down ca '99).
More than in most history, the history of cryptography, especially its 'recent' history, must be read carefully.
A responsible, and mercifully short, account of WWII cryptography which is essentially up-to-date as of this writing is Battle of Wits by Stephen Budiansky. It covers more than just the Engma story. Hugh Sebag-Montefiore's Enigma concentrates on the Engima and is both well written and accurate. David Kahn's Breaking the Engma is essentially about the problem of Naval Enigma; it's also accurate.