March 8, 2011

The Enigma Machine Part 2 The Science of Secrets

The Enigma Machine (00:03:40 min)



World War II Mind of a Code Breaker 2/12 (00:10:01m)



Cryptology is the science of secrets. Throughout history there has been an endless array of techniques devised and used by the military, government, and business to encrypt important information. It's as old as ancient history. We have come a long way since Herodotus in the fifth century B.C. when he tattooed a secret message on the shaven head of a slave, under regrown hair. Or Julius Caesar who was reported to have used cryptography in his communications during the course of his battles, and often relied on what we consider to be its most simplest form -  substitution cyphers; the systematic substitution of letters of the alphabet or groups of letters, with other letters or groups of letters. Even the Kama Sutra recommended cryptography to lovers, which allowed them to communicate with each other without the danger of having their relationship discovered. It wasn't until the ninth century and the discovery of frequency analysis by an Arab mathematician, Al-Kindi, that such classical cyphers could easily be broken.

The creation of the polyalphabetic cipher lay the groundwork for the eventual development of the famous Enigma Machine. The polyalphabetic system was first described by Giovan Battista Bellaso in his 1553 book about ciphers, however, through misattribution, it was called the Vigenere cipher, after the  French diplomat and cryptographer, Blaise de Vigenere. The "Vigenere" cipher was the first one of its kind to employ multiple substitution alphabets, albeit in a simplistic form. The Enigma, though also based on the same principle, is far more complex.

A Dutchman by the name of Hugo Koch invented a rotor machine for the purposes of encryption, though it was meant for commercial purposes only. It was patented on October 7, 1919 (Netherlands patent# 10700).   Another inventor by the name of Arthur Scherbius, a German electrical engineer also applied for a patent on February 23, 1919 for his cipher machine based on rotating wired wheels. In the same year his company, Scherbius & Ritter purchased the rights of the patent for the rotor machine invented by Hugo Koch, thereafter naming it the Enigma. Scherbius tried to market it to the Imperial German Navy but initial reactions were lukewarm. In 1923 the patent rights were bought by a firm Chiffriermaschinen AG, who commercialized the Enigma. The first Enigma - Model A came on the market that year.

The early models of the Enigma were very heavy and bulky and attracted little, if any, interest from the German military.By 1926 however the Enigma design had improved considerably, and being lighter and more compact found favour with military and diplomatic services across Europe. The German Navy purchased the Enigma and adapted it for its own use. It became the standard cipher machine of the German military forces and was used at all levels throughout the chain of command, from top echelons to front-line tactical units as well as airplanes, tanks and ships.

By the end of the war over 100,000 Enigmas had been produced

Enigma Machine

Like those of other rotor machines that preceded its inception, the Enigma also featured a complex mechanical and electrical system. It included elements of a keyboard, a set of rotors (rotating disks attached along a spindle, and components that turned one or more of the rotors one full stop which each press of the keys. While one rotor may turn with every key press, another rotor may turn with less frequency which resulted in a far more complex encryption process.

Rotor Assembly of the Wehrmacht Enigma

The Enigma was designed so that whenever a key is pressed, the electrical current flows through the wiring and illuminates one of the display lamps to indicate the output letter. For example, let's say you were to encrypt a message beginning with the letters "FED" - pressing "F" would light up a lamp indicating the substitution perhaps "M", then pressing "E" followed by "D" which would result in substitution letters for each. Considering that there are 26 lamps and 26 keys, several plugs and rotors, the combinations were virtually infinite.

A typical three-rotor Enigma with reflector and six plug connections could generate the following number of theoretical coding combinations.

3,283,883,513,796,974,198,700,882,069,882,752,878,379,955,261,095,623,685,444,055,315,226,
006,433,616,627,409,666,933,182,371,154,802,769,920,000, 000,000

That is roughly the same as 3.283 x 10114

Enigma in use (1943)
Whenever a key is pressed an electrical current flows from the battery (1) through a depressed bi-directional letter-switch (2) to the plugboard (3). The plugboard gives the operator the flexibility to rewire some letter connections between the keyboard (2) and the fixed entry wheel (4).  Subsequently, the current travels through the plug (3) (unused in this example, so shown closed) via the entry wheel (4) through the wiring of the three installed rotors (5) (as in the Wehrmacht Enigma, or in the case of Kriegsmarine M4 and Abwehr variants there were four rotors) and enters the reflector (6). The reflector returns the current through a completely different route, through the rotors (5) and entry wheel (4), proceeding through plug 'S' connected with a cable (8) to plug 'D', and another bi-directional switch (9) to light the appropriate lamp.

Enigma Illustration of Current Flow

A very high level of security was attained by repeated changes in the electrical paths through the Enigma's scrambler, implemented by a polyalphabetic substitution encryption. The diagram below illustrates the changes to the electrical pathway caused by each key depression, which in turn causes rotation of at least the right hand rotor. The electrical current passes into the set of rotors, into and back out of the reflector, and out through the rotors again. Note that the faded lines of the illustration indicate just a few of the other possible paths within each rotor. These are hard-wired from one side of each rotor to the other.

Diagram of scrambling action of the Engima Rotors

For example, when the letter A is pressed, it will encrypt differently with each consecutive key press, first to G, and then to C, etc. The reason is that the right hand rotor has stopped moving and has sent the signal on a completely different route.

Subsequently the other rotors will also respond to each key press resulting in varyed routes of the electrical currents.

The rotors are the core of an Enigma machine. Each rotor is a disc measuring approximately 10cm (3.9 in) in diameter and made from hard rubber or bakelite. It features brass spring-loaded pins on one side arranged in a circle while the other side has a corresponding number of circular electrical contacts.
Rotor contact detail  (E-bay photo)

The pins and contacts represent the 26 letters of the alphabet, that is letters A–Z. When the rotors are mounted side-by-side on the spindle, the pins of one rotor rest against the contacts of the adjacent rotor thus establishing an electrical connection. Inside the mechanism of the rotor the 26 wires connects each pin on one side to a contact on the other side in a complex pattern.

The rotor itself can only perform a simple substitution cipher.For example the pin corresponding to the letter E might be wired to the contact for letter T on the opposite face, and so on. However, when the Enigma machine uses several concurrent rotors (usually three or four) and implementing its regular stepping movements, it thus creates a highly secure poly-alphabetic substitution cipher.

Each rotor can be set to one of 26 possible positions. Once inserted it can be adjusted manually, merely by turning the grooved finger-wheel (which protrudes when the lid is closed over the Enigma machine.) The operator was able to know the position of each rotor by the letter of the alphabet visible through a small window. (In earlier Enigma models the alphabet ring was fixed to the rotor disk however subsequent models made it possible to adjust the alphabet ring relative to the rotor disk)

The setting of the rotor was the preliminary process in every operating session, and whose settings were referred to as the "key".

STEPPING MOTION OF THE ROTORS

Stepping Motion of Enigma Machine
The movement of the rotors is controlled by a mechanism of the ratchet and pawl. Every time an operator pressed a key, each of the pawls, corresponding to a particular rotor, would move forward one step in unison in the attempt to engage with a ratchet.  However, the movement was varied due to the insertion of a thin metal ring to each rotor (upon which the pawl rode).  As this metal ring rotated with its adjacent rotor, its notch would would eventually align itself with the pawl permitting it to drop into position, engage with the ratchet thus advancing the rotor.

While the first rotor always stepped or advanced with every key press, the movement of the adjacent rotors were variable dependent on the position of the notches - which could be adjusted by changing the letter ring. (Some of the rotors used by the Kriegsmarine had two notches instead of one.)

Consequently, Rotor 1 would step 26 times for every step of Rotor 2, and Rotor 2 would step 26 times for every step of Rotor 3. As simple as that sounds, there is much more to the Enigma machine.

In a feature known as double stepping, the rotors deviate from odometer-style regular motion. This is due to each pawl being aligned with both the ratchet of its rotor and the rotating notched ring of the neighbouring rotor.

When a pawl finally engaged with a ratchet by aligning itself with a notch, it moved forward and pushed both the ratchet and the notch, thus advancing both rotors at the same time. But in the case of a three-rotor machine, the double-stepping would affect only Rotor 2.

Rotor 2, if in moving forward allowed the ratchet of Rotor 3 to be engaged, would move again on the subsequent keystroke, thus resulting in two consecutive steps. Rotor 2 also pushes Rotor 1 forward - after 26 of its steps, but as rotor one moves forward with every keystroke anyway, there is no double-stepping.

With three wheels and only single notches in the first and second wheels, the machine had a period of 26 × 25 × 26 = 16,900 (not 26 × 26 × 26 because of the double stepping of the second rotor).

Historically, messages were typically limited to a few hundred letters thus eliminating any chances of repeating the exact combination of rotor positions from a specific encrypting session. Hence cryptanalysts were denied a valuable clue to the substitution used.

In 1942 a fourth rotor was added, which made it necessary for the reflectors to be much thinner. No other changes were made to the machine. With only three pawls, the fourth rotor never stepped, but could be manually set into one of its 26 possible positions.

Before the end of the war a device was designed but never implemented: the Lückenfüllerwalze(gap-fill wheel) which created irregular stepping. It featured notches in all 26 positions. If the number of notches was a relative prime of 26 and the number of notches were different for each wheel, the stepping would be more unpredictable. In addition it permitted Its internal wiring to be reconfigured, like that of Umkehrwalze-D.

THE ENTRY WHEEL

The current entry wheel or entry stator, connects the plugboard to the rotor assembly.(However in models without a plugboard, the entry stator would connect directly to the keyboard and lampboard.)
Its configuration proved to be an obstacle to Allied cryptologists during WWII. While British Intelligence remained baffled as to the alphabetic configuration, the problem was easily resolved by Marian Rejewski in a flash of inspiration.

In the commercial model of the Enigma, the keys were connected in the same sequence as the German keyboard, that Q to A, W to B, E to C and so forth whereas, in the military version connected the letters followed in logical sequence, that is: A to A, B to B, C to C, etc. (Typical of German ordnung!)

REFLECTOR

The reflector connected outputs of the last rotor in pairs, and redirected the current back to the rotors through by a different route. In doing so, the reflector ensured that the process would be self-reciprocal: that is, decryption would be the same as encryption. The only flaw in the system was that no letter was ever encrypted to itself, a factor which was exploited by the Allied code-breakers.

A distinctive feature of the early models of Enigma placed the last rotor before a reflector. However, In the commercial Enigma (Model C) the reflector could be inserted in all 26 positions, (though stationary) or, as in case of the Abwehr Enigma, the reflector stepped during encryption in the same way as did the other wheels.

In the Enigma models used by the  German Army and Air Force, reflector was fixed and did not rotate. There were four versions:  The original version "A" was replaced by Umkehrwalze "B" (translated "reverse roll") November 1, 1937. Umkehrwalze C was used only briefly in 1940 until it was solved by
Hut 6 (of Bletchley Park).  Umkehrwalze D was first encountered on January 2, 1944, and had a rewireable reflector which allowed the Enigma operator to change the connections as part of the key settings.

PLUGBOARD

Each cable inserted into plugboard connected letters up in pairs; thatis, E and Q might be a steckered pair. The effect was to switch those letters before and after the main rotor scrambling unit. For example, when an operator presses "E", the signal is diverted to the letter "Q" before entering the rotors. Up to thirteen pairs of steckered pairs might be used at one session, though normally it did not exceed 10 pairs at any one time.

Enigma Plugboard

Electrical current flowed from the keyboard through the plugboard, and proceeded to the entry-rotor. Each letter on the plugboard had two jacks: the insertion of a plug disconnected the upper jack (from the keyboard) and the lower jack (to the entry-rotor) of that letter. The plug at the other end of the crosswired cable was inserted into another letter's jacks, thereby switching the connections of the two letters!

The plugboard permitted the operator to easily change the wiring making a stronger encryption - even stronger than could have been achieved by adding an extra rotor.

Without a plugboard (unsteckered). Enigma encryptions could easily be resolved manually. However, the addition of a plugboard meant that Allied cryptanalysts had to use special machines to solve it.

The steckered plugboard raised the number of possible enciphers by a factor of 2 to 3 billion, to a staggering 10 quadrillion. To better illustrate the virtual infinite number of possiblities try to imagine If 1000 operators with captured machines were to tested four keys a minute 24 hours a day, it would take them 900 million years to try them all. It is no wonder then that the Germans were convinced that their codes were quite unbreakable.

ACCESSORIES
Schreibmax, printer accessory for the Enigma Machine

The Schreibmax was a feature used on some M4 Enigmas. It was a small printer which could print the 26 letters on a narrow strip of paper ribbon. It was placed on top of the Enigma machine and was connected the lamp panel, however, its installation required that the lamp cover and light bulbs all be removed.  The printer eliminated the necessity of having a second operator present to write down each letter.  Moreover, it provided operational security as the printer could be installed remotely so that the signal officer no longer had to see the decrypted plaintext information.

The remote lamp panel was another accessory, which made it possible for a person to read the decrypted plaintext without the operator seeing it. 

Uhr attachment for Enigma 
In 1944 the Luftwaffe introduced a variation of the plugboard switch called the Uhr ( or clock) which replaced the standard plugs. It consisted of a little box containing a switch with 40 positions.  After connecting the plugs, according to the daily "key" sheet, the operator turned the switch into one of the 40 positions. Each position produced a different combination of plug wiring which unlike the default plugs, were not pair-wise. In one switch position,  the Uhr did not switch any letters, but simply emulated the 13 stecker wires with plugs.
 

OPERATION

The encryption of messages on the Enigma were based on a vast network of settings, called keys. Each session was assigned a specific key for its Enigma and changed constantly. For messages to be correctly and quickly decrypted, both sender and receiver had to adjust their Enigma machines using identical settings in rotor selection and order, starting position, and plugboard connections. German Command distributed the codebooks which provided the daily keys to be used.

The "key" determines the setting of the following elements of the Enigma machine:

Wheel order: the choice of rotors and the order in which they are fitted.
Initial position of the rotors: chosen by the operator, and changed for each message.
Ring settings: the position of the alphabet ring relative to the rotor wiring.
Plug settings: the connections of the plugs in the plugboard.
In very late versions, the wiring of the reconfigurable reflector.

NB: Although the ring settings were a required part of the setup process, they did not affect the message encryption because the rotors were positioned independently of the rings. The ring settings were useful only to the extent of determining the initial rotor position. Once the receiver had set his rotors to the indicated positions, the ring settings no longer played any role in the encryption.

Enigma was secure so long as the wiring was secret: if the wiring was secret, the total number of possible configurations could have been calculated to be around 10114 (approximately 380 bits). With the discovery of the wiring, and other operational obstacles, this is reduced to around 10²³ (76 bits).

Navy Codebook for German Enigma

Procedures used by the Kriegsmarine were more elaborate than those used by other services of the German military. Navy codebooks were printed in red, water-soluble ink on pink paper so that they could easily be destroyed if they were at risk of being seized by the enemy.This codebook was taken from the captured U-505.

INDICATOR

Typically a key was kept constant for a pre-determined period of time, usually a day.However, in a process similar to initialisation vector in modern cryptography, a different initial rotor position was used for each message.

The reason is that, messages encrypted using identical settings could easily be attacked using a statistical formula such as Friedman's Index of coincidence. To prevent that possibility, an enciphered message would be transmitted indicating the starting position for the rotors, just prior to transmitting the ciphertext. The exact method used was termed the indicator procedure. Ultimately, the Enigma messages were broken due to the design weakness of the Enigma as well as operator sloppiness in applying these indicator procedures.

PROCEDURE

The operator would set up his machine according to his settings list, which included a global initial position for the rotors. In this example, AOH is the key. The operator turns the rotors until AOH is visible through the rotor windows then chooses his own arbitrary starting position for a message. He  may select, EIN, which is typed into the machine twice. The resulting encryption might show up as XHTLOA, which is transmitted before the actual message. The operator would turn the rotors to the same message settings, EIN and typed the plaintext of the message.

The operation was reversed at the receiving end where the operator would set his machine to the initial settings and type the first six letters of the message XHTLOA. The lamps on his Enigma would indicate the letters EINEIN, thereby indicating how the rotors are to be set. At this point the operator can decipher the message by typing in the ciphertext.

Polish cryptologists were able to break Enigma messages using such indicator procedures.

Despite its ingenious design, the procedure was seriously flawed and rendered weak due to two factors: the use of a global ground setting, and the repetition of the indicator. The global ground setting was later changed to allow the operator to select his initial position to encrypt the indicator.  However the repetition made it possible to discover the relationship of letters, that is the first and fourth, second and fifth and third and sixth characters. Hence the Polish Cipher Bureau was able to break into the pre-war Enigma as early as 1932.  However, from 1940 onward, the Germans changed procedures to improve security.

Codebooks were used daily to set up the rotors,ring settings and the plugboard. For each message, the operator selected a random start position, let's say WZA, and a random message key, perhaps SXT, as follows:

1. He set the rotors to the WZA start position and encoded the message key SXT. (Assume the result was UHL.)

2. He then set up the message key, SXT, as the start position and encrypted the message. 

3. He transmitted the start position,WZA, the encoded message key, UHL, and then the ciphertext.

4. The receiver set up the start position according to the first trigram, WZA, and decoded the second trigram, UHL, to obtain the SXT message setting. 

5. Next, he used this SXT message setting as the start position to decrypt the message.

This new procedure, used exclusively by the Wehrmacht and Luftwaffe, was an improvement over the previous method. It avoided the security flaws of double-encoded message settings because each ground setting was different. To complicate matters, they transmitted messages into five-letter groups, while the Kriegsmarine converted messages into four-letter groups.

EPILOGUE

Since the World War II, information about the Enigma had been carefully safeguarded and it wasn't until the mid-1970s that the secrets of the Enigma became known to the public. Original Enigma machines are on display in museums around the world. Some machines under private ownership have been sold at auction garnering $20,000 (US).


The world has been fascinated by the Enigma, and its allure continues to grow. It has been dramatized in many fictional productions, the most controversial being the 2001 British film called "Enigma" (based on Robert Harris' 1995 novel of the same title). The screenplay for the film was written by Tom Stoppard, produced by Mick Jagger and Lorne Michaels, directed by Michael Apted and starred Kate Winslet and Dougray Scott. (Incidentally, Mick Jagger owns one of the Enigma machines.)

The screenplay made drastic changes to the plot, and as a result has been widely lambasted for its historical inaccuracies. It completely ignores the role of the Polish Cipher Bureau (Biuro Szyfrow) in breaking the Enigma code and worse - portrays the Polish as villains!!

Marian Rejewski wrote several articles on how it was possible to break the Enigma code through mathematical applications. The following are just a few of his publications are as follows:
 
Marian Rejewski: 'An Application of the Theory of Permutations in Breaking the Enigma Cipher'; in: Applicaciones Mathematicae. 16, No. 4, Warsaw 1980.  In the above-mentioned publication 
Rejewski wrote,
" It should be mentioned that the present paper is the first publication on the mathematical background on the Enigma cipher breaking. There exist, however, several reports related to this topic by the same author: one - written in 1942 - can be found in the General Wladyslaw Sikorski Historical Institute in London, and the other - written in 1967 - is deposited in the Military Historical Institute in Warsaw.


Flag of the Polish Home Army (Armia Krajowa)



NEXT:
The Enigma Machine Part 3 The Science of Secrets 
How the Poles Cracked the Enigma Code




N.B.  Sources and references will be provided at the end of this special series.
 

No comments:

Post a Comment