2005 08 19 Cryptography

A Brief History of Old School Cryptography: 

A Brief History of Old School Cryptography Presented by Vidiot at DC213 August 19, 2005

Cryptography: 

Cryptography Derives from the Greek words ‘kruptos’ meaning “secret” and ‘graphia’ meaning “writing”. “Secret Writing” Steganography (Hidden) Code Secret (Replace words) Writing Substitution Cryptography Cipher (Scrambled) (Replace letters) Transposition

Algorithms and Keys: 

Algorithms and Keys All cryptography uses algorithms and keys, no matter how simple or complex. E.g.. Rot13, Rot is the algorithm, 13 is the key Attack at dawn Nggnpx ng qnja Plaintext Ciphertext algorithm Key algorithm Key Attack at dawn Plaintext

The First Age of Cryptography: 

The First Age of Cryptography The Classical Years Caesar shifts and simple substitution ciphers

Caesar Shift: 

Caesar Shift Monoalphabetic substitution Also known as Rot According to the second century text Lives of the Caesars LVI by Suetonius, Julius Caesar encrypted messages by replacing each letter in a message by the letter three places further along in the alphabet. ABC becomes DEF, etc.

Queen Mary’s Cipher: 

Queen Mary’s Cipher The Babington Plot Plot to free Queen Mary, incite a rebellion, and murder Queen Elizabeth. The conspirators communicated with Queen Mary, who was being held prisoner by Elizabeth, via enciphered smuggled letters.

Queen Mary’s Cipher: 

Queen Mary’s Cipher Nomenclator – 23 symbols representing letters, and 35 symbols representing words Also contained four Null symbols and one Doubling symbol. Cracked by Thomas Phelippes at the first Cipher school in England, established in 1586 by Sir Francis Walsingham, Elizabeth’s Secretary and head of security.

Queen Mary’s Cipher: 

Queen Mary’s Cipher On July 17th Mary replied to a letter from Babington using the compromised cipher, sealing her fate. Phelippes added a forged postscript from Queen Mary asking Babington for the identities of the conspirators. He supplied them.

Queen Mary’s Cipher: 

Queen Mary’s Cipher Mary got the axe Babington and the six conspirators were emasculated, disemboweled, and then executed.

How it was Cracked: 

How it was Cracked Both these early ciphers were vulnerable to Frequency Analysis.

Frequency Analysis: 

Frequency Analysis First Described in the 9th century by Abu Al-Kindi, the “philosopher of the Arabs” in “A Manuscript on Deciphering Cryptographic Messages” Al-Kindi’s work was only rediscovered in 1987. Earliest known example, though he was almost undoubtedly not the first to use the technique.

Frequency Analysis: 

Frequency Analysis Al-Kindi realized that some letters repeat more frequently than others. English Language Frequency Charts:

Frequency Analysis: 

Frequency Analysis Not infallible: Georges Perec (1936 – 1982) French novelist, fascinated by Palindromes, anagrams, wordplays, and Lipograms. (Lipograms are texts in which one or more letters are not allowed to appear.) Wrote a 466 word text in which the only vowel allowed was the letter ‘A’ La Disparition – 200 page novel written in French that does not contain the letter ‘E’ - Amazingly, it was translated into English by Gilbert Adair in 1997 under the title The Void.

Defeating Frequency Analysis: 

Defeating Frequency Analysis Blaise de Vigenère Created the Vigenère Square. Published Traicte Des Ciffres in 1586. The same year that Thomas Phelippes cracked Babington’s cipher. Too bad Babington didn’t read it.

The Vigenère Square: 

The Vigenère Square By rotating the alphabet one place 26 times, and using each line to encipher one letter, any single letter can be represented by 26 different possible letters with EQUAL possibility. Traditional frequency analysis is useless. A B C D E F G H I J K L M N O P Q R S T U V W X Y Z A A B C D E F G H I J K L M N O P Q R S T U V W X Y Z B B C D E F G H I J K L M N O P Q R S T U V W X Y Z A C C D E F G H I J K L M N O P Q R S T U V W X Y Z A B D D E F G H I J K L M N O P Q R S T U V W X Y Z A B C E E F G H I J K L M N O P Q R S T U V W X Y Z A B C D F F G H I J K L M N O P Q R S T U V W X Y Z A B C D E G G H I J K L M N O P Q R S T U V W X Y Z A B C D E F H H I J K L M N O P Q R S T U V W X Y Z A B C D E F G I I J K L M N O P Q R S T U V W X Y Z A B C D E F G H J J K L M N O P Q R S T U V W X Y Z A B C D E F G H I K K L M N O P Q R S T U V W X Y Z A B C D E F G H I J L L M N O P Q R S T U V W X Y Z A B C D E F G H I J K M M N O P Q R S T U V W X Y Z A B C D E F G H I J K L N N O P Q R S T U V W X Y Z A B C D E F G H I J K L M O O P Q R S T U V W X Y Z A B C D E F G H I J K L M N P P Q R S T U V W X Y Z A B C D E F G H I J K L M N O Q Q R S T U V W X Y Z A B C D E F G H I J K L M N O P R R S T U V W X Y Z A B C D E F G H I J K L M N O P Q S S T U V W X Y Z A B C D E F G H I J K L M N O P Q R T T U V W X Y Z A B C D E F G H I J K L M N O P Q R S U U V W X Y Z A B C D E F G H I J K L M N O P Q R S T V V W X Y Z A B C D E F G H I J K L M N O P Q R S T U W W X Y Z A B C D E F G H I J K L M N O P Q R S T U V X X Y Z A B C D E F G H I J K L M N O P Q R S T U V W Y Y Z A B C D E F G H I J K L M N O P Q R S T U V W X Z Z A B C D E F G H I J K L M N O P Q R S T U V W X Y

The Vigenère Square: 

The Vigenère Square You could also use an offset keyword on all lines. Example: The word “KRYPTOS” changes the pattern of the alphabet across all lines. A B C D E F G H I J K L M N O P Q R S T U V W X Y Z A K R Y P T O S A B C D E F G H I J L M N Q U V W X Z B R Y P T O S A B C D E F G H I J L M N Q U V W X Z K C Y P T O S A B C D E F G H I J L M N Q U V W X Z K R D P T O S A B C D E F G H I J L M N Q U V W X Z K R Y E T O S A B C D E F G H I J L M N Q U V W X Z K R Y P F O S A B C D E F G H I J L M N Q U V W X Z K R Y P T G S A B C D E F G H I J L M N Q U V W X Z K R Y P T O H A B C D E F G H I J L M N Q U V W X Z K R Y P T O S I B C D E F G H I J L M N Q U V W X Z K R Y P T O S A J C D E F G H I J L M N Q U V W X Z K R Y P T O S A B K D E F G H I J L M N Q U V W X Z K R Y P T O S A B C L E F G H I J L M N Q U V W X Z K R Y P T O S A B C D M F G H I J L M N Q U V W X Z K R Y P T O S A B C D E N G H I J L M N Q U V W X Z K R Y P T O S A B C D E F O H I J L M N Q U V W X Z K R Y P T O S A B C D E F G P I J L M N Q U V W X Z K R Y P T O S A B C D E F G H Q J L M N Q U V W X Z K R Y P T O S A B C D E F G H I R L M N Q U V W X Z K R Y P T O S A B C D E F G H I J S M N Q U V W X Z K R Y P T O S A B C D E F G H I J L T N Q U V W X Z K R Y P T O S A B C D E F G H I J L M U Q U V W X Z K R Y P T O S A B C D E F G H I J L M N V U V W X Z K R Y P T O S A B C D E F G H I J L M N Q W V W X Z K R Y P T O S A B C D E F G H I J L M N Q U X W X Z K R Y P T O S A B C D E F G H I J L M N Q U V Y X Z K R Y P T O S A B C D E F G H I J L M N Q U V W Z Z K R Y P T O S A B C D E F G H I J L M N Q U V W X

The Vigenère Square: 

The Vigenère Square Using the keyword “DEFCON”, the following enciphering alphabet would be created: A B C D E F G H I J K L M N O P Q R S T U V W X Y Z D E F G H I J K L M N O P Q R S T U V W X Y Z A B C E F G H I J K L M N O P Q R S T U V W X Y Z A B C D F G H I J K L M N O P Q R S T U V W X Y Z A B C D E C D E F G H I J K L M N O P Q R S T U V W X Y Z A B O P Q R S T U V W X Y Z A B C D E F G H I J K L M N N O P Q R S T U V W X Y Z A B C D E F G H I J K L M DEFCONDEFCON ATTACKATDAWN DXYCQXDXICKA This was the most common usage. A B C D E F G H I J K L M N O P Q R S T U V W X Y Z A A B C D E F G H I J K L M N O P Q R S T U V W X Y Z B B C D E F G H I J K L M N O P Q R S T U V W X Y Z A C C D E F G H I J K L M N O P Q R S T U V W X Y Z A B D D E F G H I J K L M N O P Q R S T U V W X Y Z A B C E E F G H I J K L M N O P Q R S T U V W X Y Z A B C D F F G H I J K L M N O P Q R S T U V W X Y Z A B C D E G G H I J K L M N O P Q R S T U V W X Y Z A B C D E F H H I J K L M N O P Q R S T U V W X Y Z A B C D E F G I I J K L M N O P Q R S T U V W X Y Z A B C D E F G H J J K L M N O P Q R S T U V W X Y Z A B C D E F G H I K K L M N O P Q R S T U V W X Y Z A B C D E F G H I J L L M N O P Q R S T U V W X Y Z A B C D E F G H I J K M M N O P Q R S T U V W X Y Z A B C D E F G H I J K L N N O P Q R S T U V W X Y Z A B C D E F G H I J K L M O O P Q R S T U V W X Y Z A B C D E F G H I J K L M N P P Q R S T U V W X Y Z A B C D E F G H I J K L M N O Q Q R S T U V W X Y Z A B C D E F G H I J K L M N O P R R S T U V W X Y Z A B C D E F G H I J K L M N O P Q S S T U V W X Y Z A B C D E F G H I J K L M N O P Q R T T U V W X Y Z A B C D E F G H I J K L M N O P Q R S U U V W X Y Z A B C D E F G H I J K L M N O P Q R S T V V W X Y Z A B C D E F G H I J K L M N O P Q R S T U W W X Y Z A B C D E F G H I J K L M N O P Q R S T U V X X Y Z A B C D E F G H I J K L M N O P Q R S T U V W Y Y Z A B C D E F G H I J K L M N O P Q R S T U V W X Z Z A B C D E F G H I J K L M N O P Q R S T U V W X Y

The Vigenère Square: 

The Vigenère Square You can also use a combination of both an offset keyword and a line ordering keyword. Example: A Vigenère square created with the keywords “KRYPTOS” and “PALIMPSEST” A B C D E F G H I J K L M N O P Q R S T U V W X Y Z P T O S A B C D E F G H I J L M N Q U V W X Z K R Y A B C D E F G H I J L M N Q U V W X Z K R Y P T O S L M N Q U V W X Z K R Y P T O S A B C D E F G H I J I J L M N Q U V W X Z K R Y P T O S A B C D E F G H M N Q U V W X Z K R Y P T O S A B C D E F G H I J L P T O S A B C D E F G H I J L M N Q U V W X Z K R Y S A B C D E F G H I J L M N Q U V W X Z K R Y P T O E F G H I J L M N Q U V W X Z K R Y P T O S A B C D S A B C D E F G H I J L M N Q U V W X Z K R Y P T O T O S A B C D E F G H I J L M N Q U V W X Z K R Y P

The Kryptos Sculpture: 

The Kryptos Sculpture A sculpture installed in 1990 in the courtyard of CIA’s campus in Langley, Virginia. Created by artist James Sanborn. Consists of four parts. Three have been solved. Part one was encrypted in a Vigenère square using “KRYPTOS” and “PALIMPSEST” as the keywords. It reads: Between subtle shading and the absence of light lies the nuance of iqlusion. Part 4 remains unsolved: ?OBKR UOXOGHULBSOLIFBBWFLRVQQPRNGKSSO TWTQSJQSSEKZZWATJKLUDIAWINFBNYP VTTMZFPKWGDKZXTJCDIGKUHUAUEKCAR

How Vigenère was Broken: 

How Vigenère was Broken Was considered unbreakable for almost 300 years. The work of Charles Babbage Babbage also attempted to build the first mechanical computer in 1821 when he proposed Difference Engine No. 1. A computing machine with 25,000 moving parts to be built with government funds. It was a failure. He then attempted to build Difference Engine No. 2. It also failed. The British government cut off his funding after he had wasted enough money to build two battleships.

How Vigenère was Broken: 

How Vigenère was Broken Babbage realized that repeating keywords would lead to repetitions in the ciphertext. DEFCONDEFCON ATTACKATDAWN DXYCQXDXICKA The length of the keyword might then be determined by finding the factors of the spacing between repetitions in the ciphertext. Example: The sequence T-H-J-D repeats after 18 spaces. The numbers 1, 2, 3, 6, and 9 are all factors of 18. Therefore, possibly: The key is 1 letter long and repeats 18 times. (Can be discounted) The key is 2 letters long and repeats 9 times. The key is 3 letters long and repeats 6 times. The key is 6 letters long and repeats 3 times. The key is 9 letters long and repeats 2 times.

How Vigenère was Broken: 

How Vigenère was Broken Once these factors have been charted, we see that the possible keys are either two or six characters in length.

How Vigenère was Broken: 

How Vigenère was Broken Let’s assume we’re dealing with a six character keyword. We don’t know the letters of the keyword, but we do know they repeat. Let’s call the letters L1, L2, L3, L4, L5, and L6. The first letter of the plaintext is enciphered using L1, the second using L2, etc. But the seventh letter is enciphered using L1 again, the eighth using L2, etc. This means we’re actually dealing with six monoalphabetic ciphers, each encrypting 1/6 of the message, instead of one polyalphabetic cipher. And we know how to solve monoalphabetic ciphers. Frequency analysis!

How Vigenère was Broken: 

How Vigenère was Broken We begin by listing the 1st, 7th, 13th, 19th letters, etc. Then the 2nd, 8th, 14th, 20th, etc. Now we have the frequency distributions for the six separate monoalphabetic ciphers. Now we compare these frequencies against the average frequencies of known plaintext.

How Vigenère was Broken: 

How Vigenère was Broken We scroll the values until the frequency distribution pattern begins to match that of known plaintext.

How Vigenère was Broken: 

How Vigenère was Broken It quickly becomes apparent that the L1 enciphering alphabet corresponds to a specific line of the Vigenère square, in this case the “T” line. Repeating this process will give us the keyword. A B C D E F G H I J K L M N O P Q R S T U V W X Y Z A A B C D E F G H I J K L M N O P Q R S T U V W X Y Z B B C D E F G H I J K L M N O P Q R S T U V W X Y Z A C C D E F G H I J K L M N O P Q R S T U V W X Y Z A B D D E F G H I J K L M N O P Q R S T U V W X Y Z A B C E E F G H I J K L M N O P Q R S T U V W X Y Z A B C D F F G H I J K L M N O P Q R S T U V W X Y Z A B C D E G G H I J K L M N O P Q R S T U V W X Y Z A B C D E F H H I J K L M N O P Q R S T U V W X Y Z A B C D E F G I I J K L M N O P Q R S T U V W X Y Z A B C D E F G H J J K L M N O P Q R S T U V W X Y Z A B C D E F G H I K K L M N O P Q R S T U V W X Y Z A B C D E F G H I J L L M N O P Q R S T U V W X Y Z A B C D E F G H I J K M M N O P Q R S T U V W X Y Z A B C D E F G H I J K L N N O P Q R S T U V W X Y Z A B C D E F G H I J K L M O O P Q R S T U V W X Y Z A B C D E F G H I J K L M N P P Q R S T U V W X Y Z A B C D E F G H I J K L M N O Q Q R S T U V W X Y Z A B C D E F G H I J K L M N O P R R S T U V W X Y Z A B C D E F G H I J K L M N O P Q S S T U V W X Y Z A B C D E F G H I J K L M N O P Q R T T U V W X Y Z A B C D E F G H I J K L M N O P Q R S U U V W X Y Z A B C D E F G H I J K L M N O P Q R S T V V W X Y Z A B C D E F G H I J K L M N O P Q R S T U W W X Y Z A B C D E F G H I J K L M N O P Q R S T U V X X Y Z A B C D E F G H I J K L M N O P Q R S T U V W Y Y Z A B C D E F G H I J K L M N O P Q R S T U V W X Z Z A B C D E F G H I J K L M N O P Q R S T U V W X Y

How Vigenère was Broken: 

How Vigenère was Broken Babbage probably discovered this technique in 1854, but he never published it. This is probably because the British government asked him not to as they were able to use it to gain advantage over the Russians in the Crimean War. It was re-discovered again independently by Friedrich Wilhelm Kasiski in 1863 and published in Die Geheimschriften und die Dechiffrir-kunst (‘Secret Writing and the Art of Deciphering’). It has since been know as the Kasiski Test.

One Time Pads: 

One Time Pads The only genuinely unbreakable cipher. Works when one unique key is used once to encipher/decipher one message. It works because, in this circumstance, all possible decryptions are equally as probable. Example: Two different meanings from the same ciphertext with two different keys. ATTACKATDAWN DXYCQXDXICKA RETREATBYDAY No way to know which key is correct. All keys are equally probable.

The Beale Papers: 

The Beale Papers In January 1820 a stranger named Thomas J. Beale checked into the Washington Hotel in Lynchburg, Virginia. He was a mysterious figure, and left suddenly in March. Beale returned in January of 1822, and left again in spring, but he left behind a locked iron box that he entrusted to the innkeeper Robert Morris. On May 9th 1822 Morris received a mysterious letter from Beale asking him to hold onto the box for a period of ten years. The letter stated that the box contained documents relating to a large sum of money which “will be unintelligible to you without the aid of a key to assist you.” It also said that if Beale didn’t return to collect the box within ten years, a friend of Beale’s would mail the necessary keys to him in June 1832. Morris never heard from Beale or his friend again.

The Beale Papers: 

The Beale Papers Finally, in 1845, after waiting 23 years Morris’s curiosity forced him to open the box. It contained three sheets of cipher text, and a letter to Morris in plain english. The letter revealed that in April of 1817 Beale and 29 other men had traveled to Santa Fe, and during the trip had discovered a large deposit of gold, which they mined for 18 months. The men agreed to hide the treasure back in their home state of Virginia while they continued to work the mine. Beale brought the treasure and buried it right before coming to the Washington hotel the first time. The ciphers were meant to guard the treasures location, but still make it available to the men’s relatives if something should happen to them.

The Beale Papers: 

The Beale Papers Morris attempted to solve the ciphers on his own until 1862. At the age of 84 Morris finally confided in a friend who’s identity is unknown. In 1885 this friend anonymously published a pamphlet containing the facts of the story and all the Beale papers. The anonymous author claimed that he had no success breaking the last two ciphers, but that he had cracked the first one using the Declaration of Independence as a key.

The Beale Papers: 

The Beale Papers The first cipher is a Book Code. In a Book Code, each word of a book or text is numbered. The first letter of each word is then used to decipher the message. Example: The first Beale cipher begins with 71, 194, 38, 1701, 89, 76, 11, 83, 1629, 48, 94, 63, 132, 16, etc. Using the first letter from the corresponding words of the Declaration of Independence the following message emerges: I have deposited…

The Beale Papers: 

The Beale Papers The first deciphered Beale paper reads: I have deposited in the county of Bedford, about four miles from Buford’s, in an excavation or vault about six feet the following articled belonging jointly to the parties whose names are given in “3”: The first deposit consisted of one thousand and fourteen pounds of gold, and three thousand eight hundred and twelve pounds of silver, deposited November, 1819…etc.

How the remaining Beale Papers were cracked: 

How the remaining Beale Papers were cracked They weren’t. The cipher remains impervious. Some believe that the anonymous publisher was actually acting on behalf of the deceased author Edgar Allen Poe, and that the entire episode was a work of fiction. There is some circumstantial evidence to back up this claim. People still travel to Buford Virginia in search of it.

The Key Distribution Problem: 

The Key Distribution Problem So why aren’t one time pads used for everything? Because of the Key Distribution Problem. One time keys must be at least as long as the messages they encipher. Keys must be communicated between parties outside of the enciphered channel. Keys can only be used once. This problem affects (almost) all types of cryptography. Even with ROT13 you still have to agree upon 13 with the other party.

The Second Age of Cryptography: 

The Second Age of Cryptography Machines and Mathematicians

Machines and Mathematicians: 

Machines and Mathematicians Lasted from approximately 1920 until 1980 Most cryptography during this period was performed with mechanical assistance. Was the birthplace of many early parts of computer science.

Enigma: 

Enigma The Enigma was invented in 1918 by Arthur Scherbius. It used an innovative combination of moving rotors and a plug board that allowed the machine to produce a minimum of 10,000,000,000,000,000 possible encoding combinations. Later more advanced versions could produce up to 26,672,901,348,424,004,787,290,112 possible encoding combinations. The Enigma was initially meant to be used by both business and the military. It was offered in a basic model similar to the one shown, and a luxury model that included a printer instead of a light board. But at a cost of $40,000 in today's dollars it never became popular.

How Enigma Worked: 

How Enigma Worked The Enigma consisted of a lamp board, keyboard, plug board, three rotors, and a “reflector.” The “Key” to the cipher lay in the initial configuration of these components. A B C D E a b c d e Lamp Board Key Board Plug Board Rotor1 Rotor2 Rotor3 Reflector F f (Note: The rotors and reflector show are actually in reverse order.)

How Enigma Worked: 

How Enigma Worked The rotors advanced as keys were pressed. Once rotor one completed a complete revolution of 26 characters, rotor two would click forward once, and so on.

How Enigma Worked: 

How Enigma Worked The rotors are each a self-contained monoalphabetic cipher. A B C D E F G H I J K L M N O P Q R S T U V W X Y Z Rotor 1 E K M F L G D Q V Z N T O W Y H X U S P A I B R C J Rotor 2 A J D K S I R U X B L H W T M C Q G Z N P Y F V O E Rotor 3 B D F H J L C P R T X V Z N Y E I W G A K M U S Q O This gave the three rotors a total of 17,576 possible cipher alphabets. 26 * 26 * 26 = 17,576

How Enigma Worked: 

How Enigma Worked Pressing the ‘a’ key would cause a circuit to be created through the rotors and illuminate the letter ‘B’ on the lamp board. ‘B’ is the ciphertext. The first rotor would then click forward one position. A B C D E a b c d e Lamp Board Key Board Plug Board Rotor1 Rotor2 Rotor3 Reflector F f

How Enigma Worked: 

How Enigma Worked The rotors could be placed in the Enigma in 6 different orders. 123, 132, 213, 231, 312, 321 This gave six times as many cipher alphabets.. 17,576 * 6 = 105,456

How Enigma Worked: 

How Enigma Worked The ‘steckerbrett’, or plug board, allowed the operator to switch six pairs of letters. (i.e. The electrical path that would normally be used when you pressed “A” would be used for “B” instead.) It left 14 letters unswitched.

How Enigma Worked: 

How Enigma Worked While the plug board alone simply created a monoalphabetic cipher, and did not change during encryption, it vastly increased the possible number of initial enciphering configurations. For example: Five five letters can be arranged in 5 * 4 * 3 * 2 * 1 = 120 different arrangements. Six pairs of character swaps out of 26 characters gives us the following: 1 pair: 325 2 pairs: 44,850 3 pairs: 3,453,450 4 pairs: 164,038,875 5 pairs: 5,019,589,575 6 pairs: 100,391,791,500 100,391,791,500 possible plug board settings.

How Enigma Worked: 

How Enigma Worked Potential Enigma Configurations: 3 rotors 17,576 6 rotor orientations 6 6 plug board settings 100,391,791,500 17,576 * 6 * 100,391,791,500 = 10,586,916,764,424,000 10,586,916,764,424,000 Possible Keys (10.5 quadrillion)

How Enigma was Broken: 

How Enigma was Broken Who cracked Enigma?

How Enigma was Broken: 

How Enigma was Broken Marian Rejewski Came from an area of Poland that belonged to Germany until 1918, so was fluent in German. Philosophy student at Poznań University, Poland. Did postgraduate work in Germany studying statistics to pursue a career in insurance. He took a course in Cryptology offered by the Polish General Staff. He left Poznań in 1932 to join the Biuro Szyfrów (Cipher Bureau) of Polish Military Intelligence.

How Enigma was Broken: 

How Enigma was Broken Espionage User Error Mathematics

How Enigma was Broken: 

How Enigma was Broken Espionage On November 8, 1931 a disgruntled employee of the German Chiffrierstelle (Cipher Office) named Hans-Thilo Schmidt sold two Enigma operations manuals to French intelligence. The manuals didn’t contain specific information about how the Enigma was assembled, but did explain how to use it. The French thought them useless and passed them on to the Polish government.

How Enigma was Broken: 

How Enigma was Broken The manuals gave Rejewski enough clues to deduce the inner wiring of the rotors. This allowed Rejewski to build a replica Enigma machine. The manuals also explained the layout of German Code books (plug board settings, rotor arrangements, and rotor settings): A/F – P/Y – U/H – L/G – D/C – R/J 3-2-1 F-H-D This is a “Day Key” used for every message sent in a day.

How Enigma was Broken: 

How Enigma was Broken User Error The Germans recognized the weakness of using the same Day Key for hundreds of messages sent during a day, so they took the clever step of using random “Message Keys” that were only used once. Sometimes called “Cillies.” Message Keys have the same plug board settings and rotor arrangements as the day keys, but different rotor settings. This increases the security when used correctly…but the Germans did it wrong. The Day key is only used to encode the first six letters of the message, which is the randomly selected Message Key repeated twice. The remainder of the message is encoded using the Message Key rotor orientations.

How Enigma was Broken: 

How Enigma was Broken Message Keys Example: Operator selects a random Message Key, say C-I-L. The operator encrypts this Message Key twice, as the first six letters of the message. Ex. CILCIL becomes FMHYUJ in the first six characters of the ciphertext. The operator then resets the rotors to the C-I-L positions and begins encrypting the message.

How Enigma was Broken: 

How Enigma was Broken Why this repetition of the day key was a Bad Idea™: Rejewski realized repetition leads to patterns The 1st and 4th letters of each cipher text were encryptions of the same letter. As were the 2nd and 5th, and the 3rd and 6th. 1st 2nd 3rd 4th 5th 6th 1st message F M H Y U J 2nd message G K E H K L 3rd message K L V Q Y A 4th message C O F X T N This allowed Rejewski to deduce some initial constraints on how the rotors were oriented. For example: the letters F and Y are closely related, as are M and U, and H and J. It doesn’t seem like much, but this relationship adds up as more and more ciphertext is intercepted. All these relationships are reflections of the initial settings of the enigma machine, the Day Key.

How Enigma was Broken: 

How Enigma was Broken Rejewski would collect these letter relationships, starting with the first and fourth letters. (F,Y) (G,H) (K,Q) (C,X) He would then begin building a table: 1st letter ABCDEFGHIJKLMNOPQRSTUVWXYZ 4th letter X YH Q If he had enough messages, he could complete the table: 1st letter ABCDEFGHIJKLMNOPQRSTUVWXYZ 4th letter VFXJBYHIMACUSKTQZLWGNDROPE

How Enigma was Broken: 

How Enigma was Broken He would then look for links within the list of letters: 1st letter ABCDEFGHIJKLMNOPQRSTUVWXYZ 4th letter VFXJBYHIMACUSKTQZLWGNDROPE Example: A V D J A 4 Links B F Y P Q Z E B 7 Links C X O T G H I M S W R L U N K C 15 Links (Always 26 links total)

How Enigma was Broken: 

How Enigma was Broken Rejewski realized that the number of links in the chains was dependant upon the rotor settings. The plug board could be ignored. This meant that instead of searching through 10.5 quadrillion possible keys, he only had to search through 105,456 to find the ones which matched each set chains. Rejewski spent a year making a catalog of the chain lengths of all 105,456 possible rotor settings.

How Enigma was Broken: 

How Enigma was Broken Once Rejewski had the chain lengths for the day’s messages, all he had to do was consult his catalog to determine the rotor settings. Now, deciphering the plug board settings became easy: He would begin with no wires in the plug board, and start typing in text from a captured message. Occasionally a recognizable word would emerge from the gibberish. Ex. He might see ‘sebttonerlib’, which would change to “sent to Berlin” once the letters N and B were swapped on the plug board. He could quickly find all six swapped letter pairs. Now he could read everything for the day.

How Enigma was Broken: 

How Enigma was Broken Rejewski then created a mechanized version of his cataloging system called a “bombe.” It consisted of 6 sets of rotors all driven by a single motor. He was able to get the keys and begin decrypting messages in about 20 minutes to 2 hours.

How Enigma was Broken: 

How Enigma was Broken All fell apart in 1939 The Germans added two more rotors They also added an additional 4 sets of plug board cables. Enigma decryption came to a standstill. Poland was about to be invaded, so Rejewski and his team handed their work over to the allies and moved to France.

How Enigma was Broken: 

How Enigma was Broken Potential Enigma Configurations: 3 rotors 17,576 60 rotor orientations 60 10 plug board settings 150,738,274,937,250 17,576 * 60 * 150,738,274,937,250 = 158,962,555,217,826,360,000 158,962,555,217,826,360,000 Possible Keys (158 quintillion)

How Enigma was Broken: 

How Enigma was Broken The British established the Government Code and Cipher School at Bletchly park in 1939. The British quickly mastered the Polish techniques and built upon them. They also changed their strategy and began using mathematicians alongside linguists for the first time. They recruited the best and brightest, not just those with “connections.” They established a collaborative system. The famous “Hut 6” group would pass ciphers around the room, each man working on it until he hit a wall, and then passing it onto the next man.

How Enigma was Broken: 

How Enigma was Broken The Hut 6 cryptographers identified a number of flaws in Enigma: It could not encipher a letter as itself. Identified mistakes the Germans made in operating Enigma: German Enigma operators were often lazy and picked predictable Message Keys (called Cillies) such as Q-W-E or A-S-D. No rotor could remain in the same position two days in a row. No letter could be switched with it’s neighbor on the plug board.

How Enigma was Broken: 

How Enigma was Broken Alan Turing Famous for his paper “On Computable Numbers” published in 1937. He confirmed Gödel's work and determined that not all undecidable questions in mathematics can be identified. In doing so he laid down the framework of modern computer science with the concept of his “Universal Turing Machine.” Joined Bletchly in 1939.

How Enigma was Broken: 

How Enigma was Broken Bletchly believed that the Germans would soon abandon the double enciphering of Message Keys and assigned Turing the job of finding another way to crack the cipher system. Turing began by studying old decrypted messages and realized that the Germans used rigid and predictable structure in their message formats. These bits of predictable plaintext provided “cribs” to the ciphertext.

How Enigma was Broken: 

How Enigma was Broken For example, he knew that at a particular point in the ciphertext the letters ETQWKF probably decrypted to ‘wetter’ (the German word for ‘weather.’) The challenge was to find the settings that turned ETQWKF into WETTER.

How Enigma was Broken: 

How Enigma was Broken He followed Rejewski’s lead by trying to find a way to disentangle the rotor settings from the plug board, thus simplifying the decryption task to about 1,054,560 possible combinations. He ignored the Message Keys and looked for links between the ciphertext and guessed plain text.

How Enigma was Broken: 

How Enigma was Broken Example: Enigma Setting S S+1 S+2 S+3 S+4 S+5 Guessed Plaintext W E T T E R Known Ciphertext E T Q W K F

How Enigma was Broken: 

How Enigma was Broken Turing imagined three Enigma machines, with rotors set to the same states as those in the loop, each trying to encipher one letter: S machine attempts to encipher W as E S+1 machine attempts to encipher E as T S+3 machine attempts to encipher T as W

How Enigma was Broken: 

How Enigma was Broken Turing then envisioned connecting the three machines so that they created an electrical loop. When the three machine found the correct rotor settings, the circuit would be completed. W E E T T W Also, because each pair of plug boards cancels out the other, the plug board settings can be disregarded.

How Enigma was Broken: 

How Enigma was Broken This meant that the complexity was reduced to: 3 rotors 17,576 rotor arrangements 60 17,576 * 60 = 1,054,560

How Enigma was Broken: 

How Enigma was Broken Turing improved upon Rejewski’s Bombe concept and created a systems of bombes that were essentially 60 sets of three Enigma’s running in parallel, thus checking all possible rotor settings in about 5 hours.

What ever became of…: 

What ever became of… Arthur Scherbius died in horse carriage accident in 1929. He never saw Enigma’s success or failure. Hans-Thilo Schmidt was arrested by the Gestapo in 1943 for being a spy. He committed suicide in prison. Marian Rejewski returned to Poland after the war where he was denounced by the communists for being a ‘decadent’ westerner. He died in 1980.

What ever became of…: 

What ever became of… Alan Turing Arrested and prosecuted for being Homosexual in 1952. Underwent abusive therapy including being forced to take hormone shots. Committed suicide in 1954 by eating an apple poisoned with cyanide. An urban legend says that the Apple logo is an homage to Turing. "It was fortunate that the authorities did not know during the war that Turing was a homosexual, otherwise the Allies might have lost the war". -Jack Good, Bletchly Cryptologist

What ever became of…: 

What ever became of… The Enigma machines themselves… -Approximately 200 survive worldwide -About 30 of those are in North America After the war the Allies ordered that all Enigma machine be destroyed by being blow up with hand grenades. This is what most of them look like today.

Enigma lives on: 

Enigma lives on http://www.enigma-replica.com/ An engineering project by Mr. Jim Oram to create exact replicas of the original Enigma machines and make them available for sale.

Enigma lives on: 

Enigma lives on Tatja Van Vark http://www.tatjavanvark.nl

Unsolved Codes: 

Unsolved Codes The Beale Papers Kryptos Sculpture Voynich Manuscript Linear A The Phaistos Disk Chinese “Gold Bar” Ciphers Zodiac Killer Ciphers

Links: 

Links http://www.enigma-replica.com http://www.tatjavanvark.nl http://www.elonka.com http://www.w1tp.com/enigma http://www.simonsingh.com