Cryptography

The History and Mathematics of Codes and Code Breaking

Tag: Cryptonomicon

Math Behind the Shark

In a section of Cryptonomicon entitled "Cycles," there are a few pages that go into detail explaining how the three wheels in the enigma machine give it a certain security level and how the adding of the fourth wheel in the system Shark increased the security of the machine. It is explained by comparing the chain of letters created by the enigma machine to a bicycle with a weak link in the chain. The "weak link" in the enigma machine is the first chain that is created to encipher the first letter and when the same chain is used again which occurs 17,576 letters later. When the Germans added another wheel they increased the number of links in the chain to 456,976 and since their messages were hardly ever that long the weak link usually never came into play.

This section of the book added onto my understanding of the enigma machine and how the 4th wheel added so much more security. The increased security was explained through a number of pages with a lot of mathematics on them which helped me see more clearly what factors were actually playing a role in increasing the security of the enigma machine when adding the fourth wheel and creating Shark.

 

 

 

 

 

 

Image: "Chain," by Pratanti, Flickr (CC)

1 Comment

Better Safe than Sorry

In the “Tube” chapter, Captain Waterhouse visits Detachment 2702 and discusses with Colonel Chattan the possible height problem of the women working the bombes. All of the women that work with the bombes need to be tall enough to wire up the tall machines, and Waterhouse and Chattan entertain the idea that the Germans can obtain the personnel record of Detachment 2702. The personnel record would reveal that there are an abnormally large number of tall women working at 2702. Waterhouse and Chattan then assume that the Germans have an open channel to retrieve the records and discuss possible solutions.

The dilemma that Waterhouse and Chattan face resembles a situation in which two parties are exchanging messages but do not know that a third party is reading the messages. As seen with Mary Queen of Scots, assuming that one’s cryptosystem is secure can lead to carelessness and result in severe consequences. The conclusion reached in class discussion is to act like there is a third party that can decrypt one’s messages and to take extra measures to conceal the meaning of the message through euphemisms or symbols. The military officers in this scene assume the position that their enemy is able to access their data freely.

Their solution to this problem is quite innovative. Instead of outright closing the channel and blocking their enemy’s access, they keep the channel open so the Germans won’t suspect anything. They also decide to feed false information through the channel to fix the height anomalies in their personnel records. Their strategy effectively turns their disadvantage into an advantage. Using an enemy’s advantage (breaking the cipher) to manipulate them (feeding them false information) is an ingenious strategy. But this strategy requires the knowledge that the original cipher is broken and that a third party can read the message. Employing this strategy requires an essential assumption discussed earlier in the course: no message is completely secure, and to be safe (and paranoid), one should act like the cipher is broken.

Image: "Bombe detail," by Garrett Coakley, Flickr (CC)

Computer Cryptography

In the chapter titled “Forays,” of Neal Stephenson’s Cryptonomicon, bit-key encryption is introduced as a method maintaining secrecy between the characters Randy and Avi. Unlike the other characters of the novel, Randy and Avi occupy the modern times and must resort to computer cryptography in order to protect Epiphyte, which is no more than “an idea, with some facts and data to back it up,” thus making it “eminently stealable.” They therefore employ a program referred to as “Ordo,” which converts their e-mails and data into streams of digital “noise,” or indistinguishable numerical nonsense. Interestingly enough, the function by which Ordo operates has recently been a topic of discussion in class.

by NIMATARADJI Photography

In the passage, Randy is directed to choose a key length of 4096 in order to communicate securely with Avi. This key length, as suggested by Randy, is entirely secure. However, because random generation of a larger key length requires tiresome effort on Randy’s behalf, he argues that even an inconceivably large super computer would have no hope of breaking a 4096-bit encryption key. Avi retorts with the implications of Moore’s Law, which argues that computing power doubles approximately every two years, and the prospect of quantum computers further validates the possibility for factoring large numbers with ease. The length of a key is thus of utmost importance, even if it is impervious to the efforts of current computing power.

A 4096-bit key, however, is notably secure, as this key length equates to  24096 possible keys. As mentioned in the novel, a key 2048 or 3072 bits in length would halt even the greatest cryptanalysts in their tracks, whereas a 768-bit key would provide security for years to come. This is because a key length does not directly signify the number of possible keys, provided that a key length of 400 generates double the number of possible keys as does 399-bit key.

This passage was captivating for me because my new found knowledge of computer cryptography and key length allowed me to appreciate its implications within the novel just that much more. Furthermore, the argument of Moore’s Law was quite noticeable to me, despite its lack of explicit mention in the passage. Most interesting to me, however, was the theoretical argument that a supercomputer composed of every particle in existence would take “longer than the lifespan of the universe” to crack a 4096-bit key encryption.

1 Comment

Intuition

The part of Cryptonomicon that caught my attention was Lawrence Waterhouse's attempt to solve the cipher, or "mathematical exercise" given to him and others by Commander Schoen. Schoen writes out the cipher, a list of 5 groups each with 5 numbers. The numbers are either 1 or 2 digits. Waterhouse instantly recognizes that the greatest number provided is 25, thus he assumes that the numbers must represent the letters in the alphabet. He then decides to run a frequency analysis test using the numbers on the board and realizes the number 18 occurs 6 times. Waterhouse then makes an assumption that the number 18 must be the letter E so he mentally substitutes the letter E into the cipher. Next, Waterhouse observes that the opening 4 numbers are '19 17 17 19'. He then knows that if 19 is a vowel, 17 must be a consonant or vice versa, and since 19 is twice as common in the cipher, he assumes that 19 is a vowel (specifically A). Waterhouse then proceeds by using the context of the message as provided by Commander Schoen earlier. Schoen had said that the message was intended for a naval officer. Using this, Waterhouse was able to guess that the first word was ATTACK. Immediately, he saw the rest of the cipher decrypt before his eyes so he stood up and stated his findings emphatically. The message read: "Attack Pearl Harbor December Seven"

The methods Waterhouse used to solve the cipher reminded me of the discussion we had earlier than year about the use of intuition to solve puzzles. Waterhouse used problem solving techniques and pure logic to decrypt the cipher. By assuming the first word was 'ATTACK' and recognizing that the numbers represented individual letters in the first place, Waterhouse demonstrated the problem solving techniques we have all acquired through basic learning.

From Letters to Numbers

"Triple Locked" by Darwin Bell

Though Neal Stevenson's novel Cryptonomicon is fictional, its story of cryptography geniuses Lawrence Waterhouse, Alan Turing and Rudy von Hacklheber during World War II gives a very accurate account of the processes and drama experienced by these experts in their field. World War II fueled one of the greatest transformations in cryptography, and these three men were at the head of the changes. Cipher analysis had always been based off of knowledge of language, pattern recognition and frequency analysis, but Waterhouse, Turing and von Hacklheber shifted the focus away from language analysis and toward mathematical analysis.

In one of the turning points of the novel and cryptography history, Waterhouse discovers non-Enigma messages in the German U-boat U-553 that have stumped his analysts. After further examination, Waterhouse discovers that the code is made of a 32 letter alphabet. This number is significant because it is a power of two, meaning that each letter in the alphabet was first substituted by a number and then by a five character binary sequence. This type of code is called the Baudot code and was used by the Germans on teletype machines. The teletype machines converted 32 characters into five number sequences of 1's and 0's. These could then be represented by either holes or no holes on a strip of paper or could be transmitted by wire or radio through changes in electrical voltages to represent the 1 or 0.

By encrypting the Baudot code again through one time pads, the Germans further increased their security. What the Germans failed to realize was that their "random" one time pads were generated through an algorithm and where therefore only "pseudo-random." Though truly random one-time pads are impossible to crack, Turing and Waterhouse were able to design a precursor to the modern computer called Colossus that could find the weakness in the one-time pads.

Turing and Waterhouse's transformation from using frequency analysis to using formulas and computers to decipher a message marks a sudden change in cryptography history. Turing's first computers and the use of binary to encode messages would forever change the standard methods of cryptography. No longer was cryptography power based on weak letter based codes, but rather almost unbreakably powerful number based codes that would revolutionize cryptography less than a century later with public key encryption.

The Interference of Secrecy

 

 

 

 

 

 

 

 

The Cryptonomicon brings up an interesting idea when Sergeant Shaftoe, Corporal Benjamin and Lieutenant Monkberg get in an argument after they ram their ship into Normandy. The reader already knows the purpose of the mission because it is alluded to in earlier chapters, but only Lieutenant Monkberg knows the exact orders, which causes problems when he tells them to do something that seemed like treason. The purpose of the mission was to leave behind the Allies' code book in order to have an excuse to change their codes, which they know the Germans have cracked, without alerting the Germans that they have cracked Enigma. Hiding the fact that they have cracked Enigma while still taking advantage of what they know  is basically the entire purpose of Detachment 2702. The concept of Detachment 2702 raises an interesting point because they have to deliberately hurt themselves in order to not reveal their resources. The concept behind 2702 is an answer to one of the things discussed in class, mainly the problem of revealing that a code has been cracked. Because of Detachment 2702, the Allies were able to fool the Axis into believing that Enigma was same and because of that, the Allies were able to keep a crucial advantage that was desperately needed in order to gain the upper hand in World War II. The Allies even had 2702 fooled, they couldn't possibly comprehend why they would ever leave behind the code book, though this secrecy turned into a double sided sword. When Corporal Benjamin is told to leave behind the code book, the Corporal assumes that his commanding officer is a spy and it didn't help that Lieutenant Monkberg was the only person that had received the orders. If they would have continue with taking the code book with them, they would have failed in their mission though they wouldn't realize it and it would have ended up costing Allied lives because the Allies would have needed to come up with a new way in which to justify switching code books, and until then all Allied conveys would be at risk of being destroyed by German U-boats.

Picture: U-Boat Surrender by Wessex Andy (Flickr)

 

 

 

The Onetime Pad

In “The Castle,” Lawrence Waterhouse arrives at the Castle in Outer Qwghlm, serving as the advance party to Detachment 2702. He is responsible for surveying the Castle and setting up appropriate accommodation away from the prying eyes of the servants. He finds a place that can adequately serve the purposes of Detachment 2702 and requests the required materials using a onetime pad to encrypt his message.

The onetime pad has been proved to be the only unbreakable method of encryption and its security lies in the randomness of its keys. Sheets of paper, or pads, containing these random keys are distributed to men in the field, and messages are enciphered accordingly. To increase the strength of its security, Waterhouse discards the letter ‘J’ and replaces it with ‘I’ in his messages. He also only uses every third line of the onetime pad. In addition, instead of simply enciphering his message using the conventional Vigenere square, he uses modular arithmetic to convert the letters into numbers and then back to letters again.

One of the impracticalities of the onetime pad is guaranteeing that everyone is using the correct sheet of keys. To overcome this obstacle, serial numbers that are unique to each sheet are typed across the top to indicate which sheet is being used. Another problem facing people who use the onetime pad is the generation of truly random keys. The men in Detachment 2702 get around this issue by using a device used in bingo parlors to produce random letters. The device containing 25 balls, to represent the 25 letters of the alphabet exclusing ‘J’, is rotated and a random ball is selected. The letter on the ball is then typed onto the sheet and so on.

In conclusion, Cryptonomicon has enhanced my understanding of onetime pads by suggesting several ways of strengthening this encryption technique as well as offering methods of overcoming the obstacles associated with its use.

 

Blindly Building

The most interesting passage from Cryptonomicon that relates to a discussion earlier in the course is found on page 89. Here, Lawrence describes the most intriguing machine found at Station Hypo: at machine built by Commander Schoen and designed to break Japan’s INDIGO cipher. According to the book’s description, INDIGO was similar to ENIGMA, in that it was enciphered using a machine. However, unlike ENIGMA, none of the cryptanalysts had seen the INDIGO machine, so they had no idea how to tackle it. Amazingly, Schoen was able to reverse-engineer the cipher machine simply by analyzing the encoded messages and finding patterns in the numbers.

Of course, this section directly relates to our discussion of ENIGMA and its downfall. The main difference between the two, though, seems to be where the bulk of the security was. With ENIGMA, cryptanalysts struggled to break the code, even with the machine in front of them. According to the book, the major breakthrough with INDIGO was creating a copy of the machine.

After reading the passage, I was convinced that Stephenson had fabricated this part of the story. I found it highly unlikely that any person could reverse-engineer an elaborate mechanism by simply searching for patterns in encrypted knowledge. However, after a quick Wikipedia search, I found that this instance was actually based off of a real-life occurrence.

The actual cipher was named PURPLE (INDIGO was a great name for Stephenson to pick) and the main storyline remains the same: a machine was being used to encipher messages and no one knew what it looked like. The biggest difference between reality and the fictionalized story is that multiple people worked together to create the PURPLE machine, compared to the lone Commander Schoen in Cryptonomicon. Nevertheless, creating a complex machine by analyzing the numbers it output is still genius.

Image: "COBOL Rube Goldberg" by Phil Manker

Turning's Bicycle and Modular Arithmetic

 

A passage that I found especially intriguing in Neal Stephenson’s Cryptonomicon, is when Waterhouse and Turning are on a bike ride in the English countryside. In these few complex mathematical pages, we are taught about modular arithmetic, which helps us understand how the Germans used the Enigma machine during the war. The part of this passage that I grasped, is when they are describing modular arithmetic through the cycles of Turning’s bike, which has one bent spoke on the back wheel. Turning knows that when the link and the spoke come in contact with each other, the chain will break and the bike will be useless. However, he figures out a way around this malfunction as it only occurs when the wheel and the chain happen to coincide.

Stephenson incorporates math when he proceeds to introduce variables.  He lets l stand for the number of links in the chain, n for the number of spokes, and C for the position of the chain. In order to calculate the value of C, you must do modular arithmetic. Stephenson explains the steps by saying “if the chain has a hundred links (l=100) and the total number of links that have moved by is 135, then the value of C is not 135, but 35” (166). The values of C, each time the wheel spins one full rotation, is n mod l, 2n mod l, etc. Ultimately this tells us that the chain will fall off his bike, when some multiple of n happens to match up with a multiple of l as well. This passage is a clever way to describe modular arithmetic, which we have covered in class.

 

Powered by WordPress & Theme by Anders Norén