Cryptography

The History and Mathematics of Codes and Code Breaking

Author: yehj

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)

Weakening the Lucifer: An Abuse of Power

Not all ciphers are created equal. Some are mathematically simple and easy to crack while others are seemingly secure but impractical to use. Then there are the ciphers that are mathematically secure but watered down to be breakable. The Lucifer cipher, created by Horst Feistel in the 1970s, was a secure cipher algorithm that was intentionally weakened so that it could be broken by the government.

The National Security Agency limited the Lucifer cipher to 100 quadrillion keys. This number is extremely large, but the NSA wielded enough computing power to try all the possible keys used to encrypt a message and decrypt the message by finding the correct key. They argued that the encryption was still secure because only the NSA had the computing power to find the correct key, which meant that the cipher could be used for commercial purposes without being broken by rival companies (Singh 250).

The action taken by the NSA to inhibit the Lucifer cipher was unethical and unjustified. Lucifer had the potential to be genuinely unbreakable using available technology if the number of possible keys was unlimited. If the technology is available to generate an unbreakable cipher, then people should have the right to use it without having to use a modified governmental version of it. The argument that the cipher was secure to all computers except those of the NSA is inherently flawed. Even though the NSA may have the most powerful computers at a given time, they may not necessarily keep that status. If they do not even have the capability to develop the Lucifer cipher on their own or to develop the tools necessary to break it, they most likely will be behind in computer development as well. Moore’s law suggests that computing power increases exponentially (cnet.com), and at this dramatic rate of increase in technological progress, the NSA cannot guarantee that they will be the only ones able to break the cipher. They are jeopardizing commercial communications by granting themselves access to the cipher.

Parallels can be drawn between the NSA’s actions and an economic monopoly.  The NSA wants complete control over this cipher, so it weakens the cipher to a level that only the NSA’s computers can break. In a monopoly, one business eliminates their competition in a region so they raise prices without fear of losing customers (econlib.org). The government is abusing their power by purposely lowering the security of a cipher that millions of people depend on. If they want to decrypt messages, they should exploit potential weaknesses using cryptanalysis. Weakening the cipher is like changing the rules in the middle of a pokergame to give one person an advantage: it’s cheating.

Simon Singh, The Code Book

http://news.cnet.com/FAQ-Forty-years-of-Moores-Law/2100-1006_3-5647824.html

http://www.econlib.org/library/Enc/Monopoly.html

Image: "All In!" by Eduardo Carrasco, Flickr (CC)

Emotion vs. Logic: The Web of Trust

In Cory Doctorow’s novel, Little Brother, the protagonist Marcus Yallow and his comrades form a web of trust as a response to the DHS’s infiltration of the Xnet. The concept of a web of trust intrigued me. As a product of cryptography, the web of trust relies heavily on the actual trust between individuals and less so on the complexity of the cipher. The biggest weakness of the web of trust is not that the cipher can be broken, but that the people involved may be untrustworthy. In addition, one untrustworthy person can compromise the entire web because each person holds the others’ keys.  The danger of the web of trust is illustrated with Masha’s threat that she can compromise the whole web of trust because she is a part of it.

Another aspect of the web of trust that I found interesting was that it required the participants to meet in person. Although it reduces the convenience and accessibility of the web of trust, it greatly increases its security. As mentioned in the novel, public-key cryptography is vulnerable to the man-in-the-middle (in Marcus’s case, the DHS) and could result in the unknown interception and decryption of incriminating messages. With the web of trust, only those in the web have access to the public keys, and therefore all the messages received by others from the web are guaranteed to be legitimate.

The logic and encryption behind the web of trust is invincible to decryption. The intelligence of a cryptanalyst is irrelevant to breaking a web of trust; in fact, exploiting the instability of human relationships is the only method in which the web can be broken. Because the web’s security relies on human emotion and the trust between individuals, it could actually be potentially weaker than other forms of cryptography. The fickle nature of trust formed between friends and colleagues is a risk that could possibly equal the mathematical vulnerability of other ciphers.

Image: "wide web," by josef.stuefer, Flickr (CC)

The Temptation of the Beale Ciphers

The $20 million treasure of the Beale ciphers immediately grabs the attention of any amateur or professional cryptanalyst. The sheer amount of money involved with the Beale ciphers serves as the main attraction for those who want to break the cipher. In addition to monetary gain, the cryptanalyst who breaks the cipher will become famous, unlike the cryptanalysts who work in secretive military settings. As more people attempt to break the cipher and fail, the recognition and potential fame increase. The combination of money and fame is reason enough to try to pursue the solution of the Beale ciphers. However, an aspect of human nature also pushes people to try to crack the cipher. People naturally believe that they might notice a clue or hint that has been overlooked by others. They might see themselves as more cunning or clever, and therefore more capable of breaking the cipher. Also, because the second message has already been uncovered, the idea that the cipher is breakable exists. People naturally assume that the other two can be solved because one of the ciphers has already been solved. A more uncommon reason why someone might decide to pursue the cipher might be to try his/her luck. If the ciphers were viewed as a lottery, the person that happens to stumble upon the text used to create the cipher would colloquially “hit the jackpot.”

Image: "here's hoping," by Robert Donovan, Flickr (CC)

The Durability of the Rossignols' Great Cipher

The fact that the Rossignols' Great Cipher remained invincible to decryption for over 200 years can be linked to both the complexity of the cipher and its novelty. The 587 different numbers used in the cipher creates thousands of possibilities; with hundreds of substitutions, any combination of multiple letters can be represented by a variety of numbers, and multiple letters or combinations of letters can have more than one number assigned to them. In Simon Singh’s The Code Book, he says that Bazeries spent months testing theories, only to find that they were incorrect (56). Immense time and effort were required to test simple possible theories, and traps were laid by the Rossignol to derail decryption efforts.

Another important factor in the Great Cipher was its ability to render frequency analysis obsolete. The cryptanalysts’ most useful tool was useless against this cipher. In order to decrypt the cipher, cryptanalysts needed to develop a completely new method, not just adapt an old one. In addition, the use of the cipher slowly faded after the death of the Rossignols, so no new messages could be created and examined. The urgency to decrypt the cipher also lessened after the cipher was no longer being used; the value of the messages became purely historical and held no political, military, or strategic value. The industrialization of cryptanalysis occurred after the Great Cipher and focused on monoalphabetic ciphers and messages in circulations, so the Great Cipher remained relevant to historians, but not to those with power and resources.

Problem Solving: Then and Now

Whether it’s Baby Einstein, Sesame Street, or even iPad apps, kids today begin problem solving at an extremely early age. They continue problem solving as they grow older, solving math problems, logic puzzles, and other intellectually stimulating activities. In contrast, when frequency analysis was first “invented,” only scholars had access to the academic resources and problem solving skills that a teenager would have in today’s time. In my opinion, the idea of frequency analysis is easy to think of once one has the ability to actually perform frequency analysis. The reason frequency analysis may have been so obscure is because there were significantly fewer people with the required level of mathematical ability. But by today’s standards, this level of ability might equate to that of a middle school student. This disparity of knowledge attests to the intellectual progress that our society has achieved over these many centuries.

Similar to most innovations, frequency analysis developed out of necessity. Only scholars thought of frequency analysis because they were the ones breaking ciphers for powerful men and women. The average amateur cryptanalyst in the present time will also be in a situation where he or she wants to decipher a text (with much lower stakes). To help them break the cipher, both history’s scholar and today’s amateur might use frequency analysis; the intellectual leap is fairly simple. The major challenge of inventing frequency analysis centuries ago was reaching the point of having the knowledge to think of this technique. Singh described the minimum level of scholarship required for cryptanalysis as “sufficiently sophisticated.” In today’s context, that same level of scholarship would best be described as sufficient – for a 12 year old.

Image: "Rubik's Cube", by me

Powered by WordPress & Theme by Anders Norén