Abstract

In 1918, German inventors Arthur Scherbius and Richard Ritter founded an engineering firm that would create one of the most fearsome encryption systems in history [1]. This system was given the name Enigma and was used primarily during World War II to encrypt German messages.

In 1926, British cryptanalysts began intercepting German communications that they could not decipher with their current methods. As a result, work to crack the new Enigma encryption system began immediately. As a testament to the strength of the Enigma, it was not until 1940 that a successful attack against the Enigma was developed. It was in fact Alan Turing who finalized the attack on the Enigma; however the attack was still reliant on a crib, or section of known plaintext in the encryption. Without this text, the attack was useless.

In 1995, James Gillogly developed a ciphertext only attack using an index of coincidence; however a large amount of characters were needed as well as significant computational power. In the following paper we will describe an implementation of the Enigma encryption system as well as an implementation of the index of coincidence attack described by Gillogly. We will then analyze the effectiveness of the attack based on its ability to find the Enigma key settings.

1. Introduction

In the years following Word War I, there were two important criteria that separated good encryption systems from bad. These criteria were high security and ease of use [2]. The Enigma found popularity because it met both of these conditions.

In one of the earliest versions of the Enigma used by the German government, the Enigma was capable of encrypting with any of its approximately 10¹⁶ keys [1]. Even larger key spaces were later developed as World War II progressed. The large key space gave the Germans what they believed to be a high level of security for their encrypted messages.

The Enigma met the second criteria by being a purely mechanical encryption system. This made encryption extremely easy and relatively error proof. The person performing the encryption typed the plaintext on a keyboard and the Enigma machine gave back the characters encrypted equivalent.

2. Background

The Enigma machine consists of several components that either adds to the complexity of the encryption or to its ease of use. The most important parts of the machine are the plugboard, rotors, and reflector.

When a user enters a character at the keyboard, an electrical signal starts through the machine. It first has to pass through the plugboard. The plugboard allows for 6 pairs of characters to be swapped while the remaining 14 characters are left unchanged. The settings of the plugboard are one of the initial settings that are part of the key for the Enigma. As an example, if the characters A and C were one of the six character pairs swapped by the plugboard, when a user entered an A at the keyboard, after passing through the plugboard the A would be changed to the value C. This can be seen in figure 1.

After passing through the plugboard, the current will next reach a sequence of three rotors. These rotors further rearrange the value of a given character. When a character enters on one side of a rotor, it exits on the other side in a different position. This position corresponds to a different letter. The current would proceed to pass through two more rotors, thus having its value changed two more times. Following figure 1, the C gets turned into F by the first rotor. The second rotor changes the F to a G, and finally the third rotor changes the G into J.

An important attribute of the rotors is that they can rotate. The first rotor would rotate by 1/26^th of a revolution after a single character had been encrypted. The second rotor would only rotate by 1/26^th of a revolution after the first rotor had made a complete revolution. Finally, the third rotor would only rotate by 1/26^th of a revolution following a complete rotation of the second disk. This rotation adds to the complexity of the encryption by generating 26³ possible starting positions for the three rotors.

Another important attribute of the rotors was that they were removable and hence they could be reordered. It was also possible to choose the three rotors used in the machine from some larger set of rotors. If there were n rotors to choose the 3 encryption rotors from, then equation 1 represents the number of resulting keys.

(1)

After the current passes through the rotors, it will reach the reflector. The reflector has no affect on the size of the key space; however it did serve a very important role within the machine. The reflector sends the current back, on a different path, through the rotors in reverse order and then through the plugboard. This was important because it allowed the same Enigma machine to both encrypt and decrypt text. If an A were encrypted as a M after passing through the Enigma, then a M would be encrypted as an A if no changes are made to the rotors or plugboard because it would follow the same path through the Enigma in reverse order (see figure 1) Following through our example, we see that the value J enters the reflector and is changed to a Q.

Figure 1: Encryption of A  M or M  A

After exiting the reflector the value gets changed next by going through the rotors in reverse order. The signal for the Q passes through the last rotor getting changed into an L. The second rotor converts the L into an N. Finally the first rotor converts the N into an M. Now the signal must pass through the plugboard to get the encrypted equivalent of an A. We can see in figure 1 that the plugboard has no effect on an M and hence the A has been encrypted into an M.

The plugboard and rotors all contribute to a very large key space for the Enigma. The 3 rotors contribute possible arrangements. The order of the 3 rotors contributes another 6 possible arrangements if there are only 3 rotors to choose from. Finally, the number of possible arrangements of six pairs of characters by the plugboard is equal to 100,391,791,500. Multiplying these three numbers together yields 10,586,916,764,424,000. This is the total number of possible keys in the Enigma machine when a set of 3 rotors is used and 6 character pairs are swapped in the plugboard [1].

As World War II progressed, Germany increased the size of the key space by adding yet another rotor to the machine. This not only added another multiple of 26 to the previous equation, but also changed the 6 possible arrangements of the rotors to [3]. Even latter, the key space was increased by selecting the 4 rotors from a set of 8 possible rotors. At the same time, the number of interchanged pairs in the plugboard increased from 6 to 10 further increasing the key space [4].

2. Goal

There are several goals for this project. We would like to gain a full understanding of the underlying mechanisms that are used in the Enigma encryption system. Despite the large key space for the Enigma, we know that the system is breakable. Thus we would like to understand how the internal workings of the Enigma contribute to the encryption systems flaws. We will do this by examining a ciphertext only attack on the Enigma in which an index of coincidence is used to brute-force all the possible rotor arrangements to find the initial state of the rotors. From there a trigram score will be used to figure out the original plugboard settings.

3. Overview of Implementation:

At the center of the attack on the Enigma is a fully working Enigma simulator. Since the same Enigma machine result in encryption and decryption when the settings are unchanged, we will use the Enigma simulator to perform trial decryptions for the attack. We will first describe the implementation of our Enigma simulator. Following this we will describe the implementation of the ciphertext only attack that uses the Enigma simulator.

3.1 Enigma Simulator

The Enigma simulator allows for text files to be encrypted with any of the possible key settings. The key components of the Enigma, namely the plugboard, rotors, and reflector, are all maintained as integer arrays of size 26 where the values range from 0 through 25. The encryption process for a single character proceeds as follows (see Appendix A for a diagram of the following process).

1. Read the rotor arrays from a file and assign them a random order as well as a random starting position.

2. Randomly generate the 6 character pairings used in the plugboard.

3. Convert the character that is to be encrypted to its integer equivalent between 0 and 25.

4. Use this as an index into the plugboard array, extracting the value stored at this index.

5. Use this same procedure of using the proceeding value as an index into the next array through the 3 rotors as well as the reflector until a value is removed from the reflector.

6. With the new value from the reflector, search the last rotor array for this value recording the index where the value occurs.

7. Use this procedure of searching for the previous recorded value then recording the index through the middle rotor followed by the first rotor followed by the plugboard.

8. The last value extracted, which was the index in the plugboard, is now converted to its character value. This is the encrypted character.

Following the encryption of a character, the appropriate rotors must be rotated depending on their positions. We perform rotation by rotating the array one unit to the left. After every character encryption the first array is rotated by one unit. We must then check to see if the second rotor needs to be rotated. Along with every rotor array is an associated integer value that represents the value that will cause the next rotor to rotate. When this value moves passed the first index (to the last index) in the array it triggers the next array to rotate by one unit. If the second rotor is rotated then we must check to see if the third rotor needs to be rotated as well using the same methodology.

Once the rotors have all been successfully rotated, the next character in the text can be encrypted. This procedure continues until the entire file has been encrypted.

3.2 Gillogly Attack

The ciphertext-only attack designed by James Gillogly is possible because it separates finding the rotor settings from finding the plugboard settings. By doing this the computation is much easier then any brute-force attack on the system as a whole. The two part attack is first based on an index of coincidence to discover the rotor settings. Once the rotor settings are known, a trigram count is used to discover the plugboard settings.

To find the rotor settings, the index of coincidence attack requires the checking of every possible rotor arrangement and starting position. For each of these settings an index of coincidence is taken using the partially decrypted text. We must thus go through the possible starting positions for the rotors. Since there are 3 rotors, we must go through these settings for each possible ordering. Thus there are possible initial settings to check. The plugboard is initialized with no swaps because these will be dealt with later.

The next step is to decrypt the cipher text with every possible arrangement of the rotors. At this point, one of the decipherments will be the proper decrypted text. However we do not know which one it is because there are still swapped letters in the text since we have not yet taken into account the plugboard [4]. In order to figure out which rotor setting is most likely to be correct, an index of coincidence is used. Equation 2 represents the index of coincidence for a partially decrypted text where f_i is the frequency of the letter i in the decrypted text and N is the total number of characters in the decrypted text [4].

(2)

This index of coincidence measures how close the partially decrypted text is to English plaintext [4]. Several of the best indexes of coincidence rankings are recorded as being the possible correct decryptions.

The final step in decryption is figuring out the plugboard settings. We must find the six swapped character pairs to be able to decrypt the message. Again we simplify the process by finding individual plugboard pairs one at a time until all six have been discovered.

To find a single plugboard setting, we decrypt the text with the known rotor settings as well as a guess at what the plugboard pair could be. Since there are 26 characters, there are 625 possible ways to pair these characters. Thus we will perform a decryption with each pairing in the plugboard. With the 625 decrypted texts, we will generate a score for each, and the best score will have its pair permanently added to the plugboard for the next round of plugboard pair guesses.

There are several ways that can be used for scoring a piece of text. We tried methods using both trigrams and an index of coincidence. For the trigram based scores, a data set of frequent English trigrams was generated using the Manifesto of the Communist Party as suggested by Gillogly. We recorded all the trigrams within the text when spacing was preserved and when spacing was removed. Along with each trigram we stored an associated number representing the frequency of the trigram within the text. To calculate the actual score for a partially decrypted text we tried all of the following methods based on either a trigram score or an index of coincidence score.

9. For every trigram in the partially decrypted text, if the trigram existed in our known list of trigrams then add its frequency to the score. If it didn’t exist do nothing.

10. The same procedure outlined above except if the trigram did not exist in the list, then subtract from the score the average trigram frequency to punish bad trigrams.

11. The same procedure outlined above except if the trigram was in the known trigram list then simply add 1 to the score. If it was not in the list then subtract 1.

12. Calculate the index of coincidence for the text based on the same formula used to discover the rotor settings.

To use these methods, each scoring was attempted with two separate approaches to calculating the best score. The first approach simply looped over the 625 possible plugboard pairs six times. For each of the iterations the largest scoring pair was permanently added to the plugboard. Thus 6 pairs would be found every time. The other method relies on the fact that as each pair is added to the plugboard, the highest score should be continually increasing. Thus instead of looping 6 times over all possible pairings, we looped while the highest score was improving over the previous score. We continued looping until the highest score was reached and the plugboard settings were discovered.

4. Results

To test the effectiveness of the decryption methods, we set up a test bed that would run the decryption on 40 randomly chosen texts from the Project Gutenberg web site (for a list of the texts see Appendix B).

To test the effectiveness of finding the rotor settings, we first encrypted the 40 texts with 40 random rotor and plugboard keys. We then broke each of the encrypted text files up into 10 smaller text files with the number of characters varying from 50 through 500 characters by steps of 50 characters. We then ran the attack using the index of coincidence to attempt to find the proper rotor arrangement.

We stored an array of size 105,456 to store each index of coincidence value for all possible rotor arrangements. We then recorded the index of the correct index of coincidence in this array for each of the decryptions. The lower the index, the closer the attack was to finding the correct setting. If the correct index of coincidence is located at an index of 0 in the array, then the attack found the correct rotor settings.

Figure 2: Average IOC Index

The data gathered suggests that as the size of the text increased the index of the index of coincidence rapidly decreases in the array. In fact, once the number of characters reaches approximately 350, on average, the proper rotor settings will be found in index 1 or 0. Once the size of the text reaches 500 characters the index of the index of coincidence was in the 0^th index for all 40 text files meaning that the rotor settings were found every time. See Appendix C for specific numbers.

Figure 2: Success Rate

Further analysis shows that for text sizes of approximately 250 characters the success rate of finding the correct rotor settings in index 0 is nearly 50% (see figure 2). Once the text size reaches 500 characters, there is a 100% success rate. See appendix D for a graph of all the data gathered.

Finding plugboard settings proved to be extremely difficult. Despite all the methods tried, it proved impossible to find one that would demonstrate any definitive success in finding the first plugboard setting. The reason for this is that nearly half of the letters are swapped as a result of the plugboard. Thus when trying to find the first plugboard setting it is very difficult because the text looks nothing like English, and hence trigram results are very misleading.

The index of coincidence does not help to find plugboard settings either. In order to use the index of coincidence successfully, the text must be very large [4]. The largest text sizes that I was testing were 500 characters in length since this is where I found a 100% success rate in rotor discovery. Hence the index of coincidence could not differentiate between good plugboard settings and bad.

5. Future Work

A couple questions came to mind while working on this project. When running the tests to find the rotor settings, there were a couple texts that did not have the settings found until they had 500 characters. What is it about these texts that make them hard to decrypt? Are there ways based on these texts to write messages that are not susceptible to the index of coincidence attack? If there are such methods, then the Enigma encryption system is strengthened in terms of the ciphertext only attack.

Is there a better way to perform trigram analysis to find the first plugboard character pairing? The fact that the partially decrypted text did not resemble English threw off the attacks we have outlined. What is a good measurement to use when finding the first plugboard pair? Should English trigram statistics be used or some other form of statistics? We attempted to use statistics from partially decrypted Enigma text, but due to the large key space, every time we changed either the rotor settings or the English plaintext we would get new statistics.

6. Conclusion

As a result of the texts that I was able to find rotor settings for, it is clear that texts of length around 50 are relatively secure to an index of coincidence attack. The distribution of the index the correct index of coincidence in the array appears to be very random.

As the size of the text increases from 50 characters, the security of the encryption rapidly decreases. As we saw, success rate for proper rotor setting discovery were at 50% for 250 characters and 100% for 500 characters. Thus sending message of significant size with the Enigma is not secure.

The reason for this lack of security is that the Enigma text can be analyzed based on just the rotor settings and the plugboard settings. Hence the problem of examining the approximately 10¹⁶ Enigma keys is cut down into two smaller problems of examining 105,456 rotor keys and 3,750 plugboard keys.

In conclusion, the Enigma encryption system proved to be a secure encryption for several years due to the fact of its large key space. However, like many classical ciphers, analysis of the ciphertext eventually lead to an attack that was possible of breaking the system. However, despite the fact that the attack is successful, for small texts of around 50 characters, the encryption is not susceptible to a index of coincidence based attack.

References:

13. Simon Singh. The Code Book. New York: Anchor Books, 2000.

14. Robert Churchhouse. Codes and Ciphers: Julius Caesar, the Enigma, and the Internet. Cambridge: Cambridge University Press, 2002.

15. David Kahn. The Codebreakers: The Story of Secret Writing. New York: Scribner, 1996.

16. James J Gillogly. Ciphertext-only Cryptanalysis of Enigma. Cryptologia. 19(4) 405-412.

Appendix A:

Appendix B:

Daniel Bryton -- Personal Memoir Of Daniel Drayton For Four Years And Four Months A Prisoner (For Charity's Sake) In Washington Jail

Bob Evans -- The Forest Monster of Oz

Jeffery Farnol -- The Money Moon

Elbert Hubbard -- Love, Life & Work

Frederic Stewart Isham -- A Man and His Money

John Rushworth Jellicoe -- The Crisis of the Naval War

William MacLeod Raine -- Man Size

Charles Norris Williamson -- The Powers and Maxine

Samuel Hopkins Adams -- The Unspeakable Perk

Andy Adams -- The Outlet

Joseph Edmond Collins -- The Story of Louis Riel: The Rebel Chief

Henry van Dyke -- Joy & Power

Edgar A. Guest -- Making the House a Home

Peter T. Harkness -- Andy the Acrobat

Peter B. Kyne -- The Long Chance

Elizabeth McCracken -- The American Child

Henry Seton Merriman -- The Vultures

Howard Pyle -- Stolen Treasure

Burton E. Stevenson -- Affairs of State

Henry Hawkins Brampton -- The Reminiscences Of Sir Henry Hawkins

Victor Appleton -- Tom Swift and His Motor-Cycle

Victor Appleton -- Tom Swift and his Wireless Message

William Stearns Davis -- A Day In Old Athens

H. Rider Haggard -- Love Eternal

Tobias Smollett -- The Adventures of Roderick Random

Robert Levine -- The Deeds of God through the Franks

John McElroy -- Andersonville, v3

James Oliver Curwood -- Baree, Son of Kazan

James George Frazer -- The Golden Bough

Anthony Trollope -- The Courtship of Susan Bell

Ben Johnson -- Cynthia's Revels

Ethel C. Pedley -- Dot and the Kangaroo

Arthur Christopher Benson -- Escape and Other Essays

L. Muhlbach -- Frederick the Great and His Court

Eugen Neuhaus -- The Galleries of the Exposition

T.S. Arthur -- The Hand But Not the Heart

Charlotte M. Yonge -- My Young Alcides

Georges Duhamel -- The New Book Of Martyrs

James Otis -- Neal, the Miller

J. H. Fabre -- The Wonders of Instinct

Appendix C: