Actions

British WW2 Codebreaking

From Londonhua WIKI

British World War II Codebreaking

by Nicholas Johnson

British WW2 Codebreaking
Enigma.JPG
3 Rotor Enigma Machine
Location Bletchley Park

Abstract

This project was all about the impact of Enigma on World War II from its introduction to it being broken by British cryptographers. I have taken a history class covering World War II but not specifically on Enigma. I have always been very interested in the design of the machine so studying here in England is the best place for me to research and understand it. The opportunity to go to Bletchley Park, the location where all of the codebreaking was performed, and research this topic was amazing. The amount of information available and just the atmosphere there was astounding. I have learned so much about the British codebreaking efforts while in London which I have always wanted to do.

Introduction

This project milestone looks at the impact of the British codebreaking effort, specifically in terms of the Enigma machine. It covers what the Enigma machine is, who the key individuals were in breaking it and how it was broken. It also looks at the impact on the rest of the war and the future of cryptography after Enigma was used and then subsequently broken. Anyone with an interest in World War II, cryptography, or militaries would be very keen to learn about the Enigma machine because of its impact in History. I have not had a class cover Enigma in depth before so I choose it because of my fascination with the technology.

Section 1: Background


Enigma

Enigma Rotor

In order for the German Military to communicate with troops on the battlefield and submarines away from base, radio signals were utilized. This had advantages, but it did also have its drawbacks. Since it was radio signals the enemy could intercept them. To protect the messages, they needed to be enciphered. In the 1920s, a German Engineer named Arthur Scherbius designed many different cipher machines. He settled on a design and called it Enigma.[1] This original design for Enigma was based upon a 26 letter keyboard for inputting the plaintext message, 26 lamps to show the cipher letters, a power supply, three removable wired wheels that rotate around a common axis, a fixed reflector, and a fixed entry wheel. This setup introduced two important features; no letter can encipher itself, and there is symmetry of plain-cipher pairs, ex. if J enciphers M, then M enciphers J.[2] This scrambling of letters would have been the equivalent of a complex substitution cipher if the wheels didn't move, but they did. Whenever a key was pressed a mechanical mechanism advanced the wheel one position, so after 26 key presses the first wheel would return to its starting position. At this point the second wheel would then turn, and once that wheel made a full rotation then the third wheel would turn. This rotating mechanism made the enciphering process very complex as all three wheels would not have returned to their original positions until 16,900 letters would have been enciphered.[3] This rotating motion made deciphering difficult, but several other parts of the machine made things even more sophisticated. One of these was the option to take off the three wheels and reorder them in six different ways, this produced 101,400 different substitution alphabets. To add even more of a challenge for anyone trying to decrypt the messages, the rotors could be started in any one of the 26 positions which created 105,456 possible starting positions and substitution alphabets, and that's with having an Enigma machine which allowed one to know the wiring.[4]

Basic Enigma Diagram[5]

The German Military did not think this original design provided sufficient protection, so they made some changes to the design for their use. One major modification that they introduced was the plugboard. The plugboard used up to thirteen short cables, the German's used ten, to switch letters at input and output of the machine. If, for example, B was connected to R, then whenever a B was pressed it would go into the rotors as an R, and vice versa. Also, if an R came out of the rotors, the B light would turn on, and vice versa.[6] This increased the number of combinations even more, multiplying the already large amount of combinations by 150 million million.[7] Another modification made by the military was the addition of more rotors. They increased the number of rotors available from three to five, of which any three could be chosen, and put in any order giving 60 possible combinations for the rotor order.[8] Later in the war, the Navy wanted more security for their Enigma setup than was used in the Army and Air Force Enigma model, so a four rotor Enigma machine was developed and distributed. With the addition of an extra rotor slot the number of rotors available to choose from was increased to eight for the Navy. In addition to the additional rotors the Naval message indicators were disguised using a bigram table.[9] In order to determine the indicator these bigram tables needed to be known.


These changes made by the German Military made the number of possibilities unimaginable and theoretically unbreakable, but in use the Germans made several key mistakes. The first large mistake was the double encipherment of the message setting that occurred until May 1940. This double encipherment allowed the bypassing of the plugboard which had ensured the security of Enigma as analyzing 100 messages produced enough indicators to break the encipherment. Another mistake made by Germans was giving the full titles of the addressee and originator because, for use in the Bombe machines, lengthy cribs, likely plain-text messages, were needed. A third mistake was that operators sent the same message twice using different ciphers that were similar. The laziness of operators was key and was so common they got their own nickname. One of these was called Sillies, referring to an operator who used his girlfriend's name 'Cilli', which means easy to guess encoding of the message. Another of these techniques the British used was called the Herivel Tip which relied upon the operator not randomizing the key to encrypt the message from the ground setting for the day which led to patterns and allowed the 17,576 possible configurations to be reduced to close to 30. There were many techniques used to break Enigma because of the German's improper use of the machine. Many techniques came from different analysts who each saw unique patterns. In the end this paid off and allowed for many German messages to be decrypted throughout the war with the intelligence gained from them being given the code name 'Ultra'.[10]


To Operate an Enigma Machine[11]

1) The Operator would consult the table provided for the day's ground settings and turn the rotor's ring to those positions
2) The Operator would choose three random letters as the start position to encipher the message with
3) The Operator would then encode the start position twice (once after 1940)
4) The Operator would turn the rotors to the start position and encode the message
5) The radio operator then would transmit the encoded message using Morse code


To break Enigma[12]

1) Intercept Morse code signals using Y stations
2) Determine a crib
3) Set up a Menu
4) Run the crib on the Bombe with settings from the Menu
5) Use the possible starting positions from the Bombe on the Checking machine to determine the rest of the settings
6) Use Enigma or modified Typex machine with settings to decrypt messages
7) Translated to English
8) Analyzed for intelligence worth and possibly passed up chain of command



Bletchley Park

As the war approached, Britain prepared for another world war. One part of this preparation was secret intelligence groups known as MI6 and GC&CS, Government Code and Cypher School. During the war, the central location for this type of intelligence needed to be protected while still being in the proximity of London; Bletchley Park was an option and was the one chosen to host it.[13] In the beginning it was not a very large operation as it consisted of the Mansion and its outbuildings with about 150 staff.[14] As the operation was expanded and began breaking German Enigma codes resources were still lacking. After appealing to Winston Churchill a major building program began including Blocks for the workers and outhouses to house the Bombe machines.[15] In the end dozens of buildings were built, each with their own purpose but only known by their Hut number in the name of secrecy. Below is a list of key buildings and their purposes. There are more than what are listed but these are the most important. Also below are before and after pictures of Bletchley Park which shows the massive expansion that occurred.

Bletchley BeforeBletchley After

Buildings

  • Mansion - The Mansion was the main building of the initial site and housed many different groups throughout the war. The Intelligence Exchange group was housed here until it was moved to Hut 4. Most other rooms were used as offices and record keeping storage rooms.[16]
  • Hut 3 - Hut 3 was the intelligence hut for German Army and Air Force communications after having been processed by Hut 6. In February 1943 the Hut 3 reporting group was moved to Block D and the building was renamed Hut 23.[17]
  • Hut 6 - Hut 6 housed the Enigma processing machinery for the German Army and Air Force messages which then passed the information onto Hut 3 for translation and reporting. In February 1943 the Hut 6 Section moved to Block D and the building was renamed Hut 16.[18]
  • Hut 8 - Hut 8 was dedicated to the breaking of the German Naval Enigma messages. It was here that Alan Turing led his team in breaking the Naval Enigma codes. In February 1943, the Hut 8 Naval Enigma processing section moved to Block D and the building was renamed Hut 18.[19]
  • Hut 11 - Hut 11 housed the original Bombe Machines that were co-designed by Alan Turing and Gordon Welchman. It was at this location that the WRENS, Women's Royal Naval Service, worked in teams of two to set up the machines according to the menus they were given to find possible settings for the day's Enigma settings. These machines were eventually moved to Hut 11A so Hut 11 could be used to test new equipment being designed including Rob and Colossus.[20]
  • Block D - Block D was completed in January of 1943 as a one story building to be completed more quickly than the original two story design. Block D contained Huts 3, 6, and 8 which consisted of 40,000 square feet which at the time of completion was the largest building at Bletchley Park. To protect the building a weapons tower with machine guns was built on the roof to repulse any low-flying enemy aircraft.[21]



Alan Turing

Alan Turing from Paddington, England was not like everyone else. This was noticed by both students and headmasters as he worked his way through school.[22] He earned mediocre scores but outside of class excelled in his own studies. One incident that impressed his headmaster was that he found the infinite series for the inverse tangent function without elementary calculus.[23] His ability to be mediocre at most subjects and excel at Science and Mathematics allowed him to get a scholarship to King's College. Alan graduated with a degree in Mathematics and was elected a fellow shortly thereafter. It was this fellowship connection that put him on the radar of the GC&CS, Government Code and Cipher School, who then promptly recruited him in 1938.[24] Alan was placed in a group with Dillwyn Knox, John Jeffries, and Peter Twinn who made up the group responsible for breaking Enigma.[25]

The British had spent months getting nowhere with their attempts but that changed quickly when the Poles came forward with their information. The Poles had received the wiring diagrams for Enigma from the French Secret Service in 1932 and were able to consistently break Enigma shortly thereafter.[26] The Poles used the indicators transmitted at the beginning of every message to search tables of all possible rotor combinations to determine what was in use. This manual process was time consuming so the Poles created a machine with Enigma rotors that searched these 6 x 17,576 core combinations for them. The downside of this was that each of the six possible rotor orders required its own machine. When the Germans introduced two more rotors to be used which brought the possible rotor orders up to 60, the Poles did not have the resources to build 60 machines to search for the combinations.[27] It was at this point that they passed their information onto the British and French. Alan took these ideas developed by the Poles to create an automated machine to search instead of a human. The big problem was, how do you incorporate so many physical combinations into a machine and have it know what it is searching for. The basis came from using a crib, a likely plain-text message, to compare against the encoded Enigma message. A major part of the Enigma machine was that it used a reflector which gave it a special property that no letter can encipher itself. Trying to find the exact location of a crib was made possible by this because if any letter lined up with itself then that could not be the correct position. This same phenomenon would be the basis for the Bombe machine and its search method as this contradiction helped eliminate possible plugboard combinations and make it feasible to solve.[28] It was a brilliant design by Alan Turing, but when Gordon Welchman saw the designs he saw a way to exploit Enigma even more. His ideas, that are explained below, made the Bombe machine designed by Turing practical.[29]



Gordon Welchman

Gordon Welchman, before the war, was a Algebraic Geometry professor at Sidney Sussex College, England. As the war began he was asked to assist with code breaking for intelligence at Bletchley Park. While there he oversaw Hut 6 which focused on breaking the German Army and Air Force codes while also offering ideas about how to improve the efficiency of the process to help scale up the code breaking process. In order to do this more talent was needed. With his connections to colleges he recruited from the Cambridge area colleges.[31] While he and his team worked to break Enigma with the hand technique developed by the Poles, the Germans changed their protocol. Previously the starting position for the German message was enciphered twice at the beginning of the message but then was changed to only be enciphered once after 1940. This change made the previous method worthless and new ideas had to be developed.[32]

With Alan Turing's machine built and installed it was supposed to be the savior of the code breaking operation, but it didn't really work. It had too many false positives and took far too long to be useful. After hearing about Turing's idea behind the machine Welchman came up with another idea. It was called the diagonal board. The process of code breaking was based upon educated guesses, and if that guess was wrong the Bombe just kept searching which led to it taking a very long time to find a solution. This diagonal board solved this problem by simultaneously scanning all possible combinations by allowing an unlimited number of reentries into the chain.[33] If a wire became live then there were up to 25 more possible false inputs that could also be checked to rule out that configuration.[34] This allowed the Bombe to find the solution magnitudes faster than previously.



Bombe

Bombe Wheel
Replica Bombe Machine
Enigma Menu[37]

In the multi-step process of breaking Enigma the Bombe was essential. All parts of the process were important but without the Bombe doing automated checking Enigma would have remained unbreakable. The purpose of the Bombe was to utilize a crib, likely plain-text message, to check the 17,576 possible configurations of the rotors, which it did in about 10.5 minutes.[38] To set up a Bombe, cryptographers created a menu which was formed from a plausible plain-text message. If the guess was correct the Bombe would stop giving the codebreakers a plausible starting position for the rotors and one of the plugboard connections.[39] To solve the rest of the plugboard connections a checking machine was used. The checking machine works the same way as an Enigma machine without the plugboard. Using a combination of the menu, starting positions from the Bombe, and the first plugboard connection from the Bombe all the other plugboard connections could be deduced with the checking machine. If there were contradicting letters then the Bombe gave a false stop and had to be restarted.[40]

To create a menu, a crib was lined up with the cipher-text and since no letter can be enciphered as itself a plausible relationship between the two could be made. If X was the sixth position of plain-text and O was the sixth position of cipher-text then it's possible that when the rotors had moved six places from the start X is enciphered as O.[41] This was done many times and created loops of letters enciphering each other. These loops when combined created a menu used to break Enigma. The drums on the front of the Bombe rotated checking for the rotor positions. On the back of the machine were miles of wires connected between different letters to use these menus to remove false positives from the system.[42]

With the German Navy increasing the number of rotors from three to four the existing Bombe machines were modified to try and solve it, but were unable to. A special four rotor Bombe had to be designed to break the four rotor Enigma.[43] It was based upon the same concepts as the three rotor Bombe but included another row of rotors and was optimized for the four rotor job. The media player is loading...

The Impact on World War II and future encryption

There is no doubt that breaking Enigma had a significant impact on World War II. It is difficult to determine exactly how much of an impact but there were several key events that were influenced by the breaking of Enigma. During the North African campaign, German General Erwin Rommel had a victory at Gazala but due to Enigma intercepts the Allied forces were able to prevent him from capitalizing on that victory. In keeping Rommel out of Egypt in 1942 the conquest of North Africa stayed on track as a loss would have set Operation Overlord back until 1946. This kind of extension of the war would have had dire consequences for Britain due to the German assault that included weapons like the V-2.[44]
Moving beyond World War II and into the age of computers, data security became an important topic. How does one make sure everyone can communicate to someone they have never communicated to before but still remain secure. The evolution of encryption that has led to our current methods was introduced with the Diffie-Hellman key exchange system. This system was proposed by Diffie and Hellman in 1976 as a practical way to encrypt messages between two people, for example, Bob and Alice. As the two people have never met before the initial exchange must be an unsecured transmission. The system relies upon primes and the difficulty in determining very large prime numbers. Bob and Alice agree upon two integers, p (a large prime number) and m (a number that lies between 1 and p-1). Bob chooses a secret number x which lies between 1 and p-1. He then computes kx=mx(mod p) and sends it to Alice. Alice chooses a secret number y which lies between 1 and p-1. She then computes ky=my(mod p) and sends it to Bob. Now (kx)y=(ky)x=mxy(mod p). This allows messages sent both directions to be encrypted without the other knowing the secret key that would have been exposed by the unsecured transmission.[45] This method launched cryptography into the modern age as almost every current encryption system is based off this concept.

Section 2: Deliverable

Enigma Recreation


For my deliverable I recreated a German Enigma Machine that was in use by all branches of the German Military, until when the Navy used a more advanced version. The Machine is based around a visual representation of the machine to show the complexity of it and how complicated a job the codebreakers had. There is a short instruction video below that shows the different parts of the virtual machine.

To experience the Enigma machine click here.



The Math behind the Enigma

Enigma Type Rotor States Wheel Orders Plug Board Total Combinations
Commercial 263 3*2*1 1 105,456
Army and Air Force 263 5*4*3 26!/10!6!210 158 billion billion
Naval 264 8*7*6*5 26!/10!6!210 115,724 billion billion



Conclusion

In this milestone, many important points relating to Enigma have been discussed. The Enigma machine, what is it and what made it so important. The key location in breaking Enigma, Bletchley Park, and how it was utilized. Important figures in the fight to break Enigma, Alan Turing and Gordon Welchman, and what they contributed. The Bombe, what it was and how it was able to do its job. The impact of breaking Enigma on the war and the future of encryption put forth by Enigma. For my deliverable a visual web version of Enigma has been designed to illustrate the complexity of Enigma and the importance of the work that was done at Bletchley Park. In addition to the Enigma machine, also included is a chart that illustrates what made Enigma so mathematically complex.

For a future inquiry an important machine to look at would be the SZ42, Lorenz machine. It was used for German High Command communications as it was mathematically more complex than the Enigma machine, yet was broken without the cryptographers ever seeing the machine or diagrams of its wiring.

References

  1. Churchhouse, R. (2002). Codes and ciphers: Julius Caesar, the Enigma, and the Internet. Cambridge University Press. pp 111.
  2. Churchhouse, R. (2002). Codes and ciphers: Julius Caesar, the Enigma, and the Internet. Cambridge University Press. pp 112-115.
  3. Churchhouse, R. (2002). Codes and ciphers: Julius Caesar, the Enigma, and the Internet. Cambridge University Press. pp 119.
  4. Churchhouse, R. (2002). Codes and ciphers: Julius Caesar, the Enigma, and the Internet. Cambridge University Press. pp 119-120.
  5. Churchhouse, R. (2002). Codes and ciphers: Julius Caesar, the Enigma, and the Internet. Cambridge University Press. pp 114.
  6. Churchhouse, R. (2002). Codes and ciphers: Julius Caesar, the Enigma, and the Internet. Cambridge University Press. pp 121.
  7. Greenberg, J. (2014). Gordon Welchman: Bletchley Park's Architect of Ultra Intelligence. Frontline Books. pp 213.
  8. Turing, D. (2014). Bletchley Park Demystifying the Bombe. pp 6.
  9. Turing, D. (2014). Bletchley Park Demystifying the Bombe. pp 59.
  10. Welchman, G. (1982). The Hut Six Story: Breaking the Enigma Codes. Penguin Books. pp 164-167.
  11. Churchhouse, R. (2002). Codes and ciphers: Julius Caesar, the Enigma, and the Internet. Cambridge University Press. pp 123.
  12. Welchman, G. (1982). The Hut Six Story: Breaking the Enigma Codes. Penguin Books. pp 149-161
  13. Storm Clouds Gather. (n.d.). Retrieved May 26, 2017, from [1]
  14. Cottage Industry. (n.d.). Retrieved May 26, 2017, from [2]
  15. Intelligence Factory. (n.d.). Retrieved May 26, 2017, from [3]
  16. Bonsall, A. (2009). History of Bletchley Park Huts & Blocks 1939-45. pp 27-32.
  17. Bonsall, A. (2009). History of Bletchley Park Huts & Blocks 1939-45. pp 8-9.
  18. Bonsall, A. (2009). History of Bletchley Park Huts & Blocks 1939-45. pp 11.
  19. Bonsall, A. (2009). History of Bletchley Park Huts & Blocks 1939-45. pp12.
  20. Bonsall, A. (2009). History of Bletchley Park Huts & Blocks 1939-45. pp 14.
  21. Bonsall, A. (2009). History of Bletchley Park Huts & Blocks 1939-45. pp 24.
  22. Hodges, A. (1983). Alan Turing: the enigma. Vintage. pp 4-5.
  23. Hodges, A. (1983). Alan Turing: the enigma. Vintage. pp 25.
  24. Hodges, A. (1983). Alan Turing: the enigma. Vintage. pp 148-149.
  25. Hodges, A. (1983). Alan Turing: the enigma. Vintage. pp 161.
  26. Hodges, A. (1983). Alan Turing: the enigma. Vintage. pp 170.
  27. Hodges, A. (1983). Alan Turing: the enigma. Vintage. pp 172-174.
  28. Hodges, A. (1983). Alan Turing: the enigma. Vintage. pp 179.
  29. Hodges, A. (1983). Alan Turing: the enigma. Vintage. pp 182.
  30. Hodges, A. (1983). Alan Turing: the enigma. Vintage. pp 268.
  31. Greenberg, J. (2014). Gordon Welchman: Bletchley Park's Architect of Ultra Intelligence. Frontline Books. pp 31-35.
  32. Greenberg, J. (2014). Gordon Welchman: Bletchley Park's Architect of Ultra Intelligence. Frontline Books. pp 43.
  33. Greenberg, J. (2014). Gordon Welchman: Bletchley Park's Architect of Ultra Intelligence. Frontline Books. pp 63.
  34. Turing, D. (2014). Bletchley Park Demystifying the Bombe. pp 38.
  35. Gordon Welchman. (n.d.). Retrieved June 01, 2017, from [4]
  36. Greenberg, J. (2014). Gordon Welchman: Bletchley Park's Architect of Ultra Intelligence. Frontline Books. pp 233.
  37. Greenberg, J. (2014). Gordon Welchman: Bletchley Park's Architect of Ultra Intelligence. Frontline Books.
  38. Turing, D. (2014). Bletchley Park Demystifying the Bombe. pp 10, 12.
  39. Turing, D. (2014). Bletchley Park Demystifying the Bombe. pp 11.
  40. Turing, D. (2014). Bletchley Park Demystifying the Bombe. pp 43-47.
  41. Turing, D. (2014). Bletchley Park Demystifying the Bombe. pp 14.
  42. Turing, D. (2014). Bletchley Park Demystifying the Bombe. pp 23.
  43. Turing, D. (2014). Bletchley Park Demystifying the Bombe. pp 61.
  44. Lycett, A. (2011, February 17). History - World Wars: Breaking Germany's Enigma Code. Retrieved June 01, 2017, from [5]
  45. Churchhouse, R. (2002). Codes and ciphers: Julius Caesar, the Enigma, and the Internet. Cambridge University Press. pp 166-167.



External Links

Bletchley Park Website