Cryptography

The History and Mathematics of Codes and Code Breaking

Author: overtocm

The Essence of the Security vs. Privacy Debate

When we talk about the battle between security and privacy, most of the discussion from both sides has to do with one of two topics: the effectiveness of electronic mass surveillance in deterring and stopping crime, or the effect that surveillance has on individual freedoms e.g. freedom of speech/expression. These are the most important questions in the debate, since we all agree that both individual freedom and safety are important, but the debate surrounds the way we prioritize those values and the effects that we perceive surveillance having on them. As a debater on either side of the topic, it is often tempting (and quite easy) to exaggerate the importance of either privacy or security, for example by claiming that by letting the government monitor our phone calls, we are condemning ourselves to an Orwellian future. Obviously, it is possible to live in a free and healthy democratic society where the government has access to its citizens phone calls. So instead of making that extreme claim, it might be more appropriate to simply note that we need to be deliberate and thoughtful about what freedoms we give up, and a similar approach applies to the safety side of the debate.

In addition to these value-driven issues, there is an important practical side to the debate that goes along with the above idea to be judicious in how we relinquish our freedoms, even when the end result is justified. It is important to keep in mind that any powers we grant to the government now are effectively permanent; they set a precedent for future regimes to do the same. So if we are going to give up a freedom in today's society, we should also be willing to give that up in a hypothetical society where our ruler is the kind of tyrant we fear the most. Obviously, our constitution is designed specifically to prevent such a government from coming to power, but recognizing the longstanding effects of our choices today is vital since we can't afford to get the answers to these questions wrong.

Pretty Good Anonymity

In Darkode, the hosts tell the story of a ransomware victim who was forced to buy 500 dollars worth of Bitcoin to gain access back to her files that had been stolen and encrypted. In the process, she came in contact with TOR which has as its central mission to provide anonymous communication between people through computers. Because of the secrecy it provides, the dark web (which can be accessed through TOR) is home to a host of cyber-crime including selling stolen financial information and other illegal goods and services. Similarly, the purpose of ZCash was to take the ledger system implemented by Bitcoin but to improve the product by also ensuring  mathematically guaranteed anonymity in every transaction. Although this is a significant upside, it also opens the currency up to some potentially dark uses, since this anonymity is exactly what criminals are looking for to be able to buy and sell goods illegally without arousing suspicion.

Although the days of perfect security are gone, this level of anonymity is pretty good. It allows anybody who uses these services to be confident that their identity is almost certainly anonymous, and this poses a significant challenge to the privacy vs. security debate: how can we allow people to have access to pretty good anonymity without losing the ability to track down criminals? After all, if ZCash worked as intended, you could easily see a list of all transactions that had taken place, but you couldn't figure out who was involved in them, creating the perfect smokescreen in which criminals can hide.

A comparison could be made to the selling of ski masks, gloves, and guns; all three can be used to do evil things, but all of them are still legal products that have legitimate uses. But the level of anonymity afforded by ZCash and other similar privacy-focused technologies goes far beyond what you could attain with a pair of gloves and a ski mask. Perhaps this nearly perfect anonymity has gone to far, enabling criminal activity without any significant benefits for legitimate uses. This is one of the most difficult questions to answer in the security vs. privacy debate, and one that could cast the deciding vote in which direction we as a society choose to go.

The Case for Strong Encryption

In my opinion, strong encryption should be available to the public, even terrorists and criminals, for two primary reasons, one theoretical and the other more practical.

The theoretical reason is the one that Singh identified as the primary argument in favor of strong encryption: privacy rights. As Singh notes, the Declaration of Human Rights protects privacy and communication from “arbitrary interference,” and this is a notion that most democratic governments seem to support and protect. But at the same time, virtually every government in the world conducts mass surveillance on its citizens which seems to conflict with the declaration of values. Is collecting, storing, and mining personally identifiable communications from innocent people not “arbitrary interference”? It seems that if that phrase is to mean anything at all, mass surveillance surely must be an example.

Of course, one might argue that although it is interference, it is justified by the hopes of cracking down on and deterring crime, securing the safety of the people, and ensuring national security. But this leads to the more practical argument I see in favor of publicly available strong encryption, which is that despite strong encryption being publicly available, crime and terror are no more rampant now than they were prior to the advent of the internet. And of course, as exposed by Edward Snowden, even with strong encryption available, the NSA can still effectively conduct mass surveillance.

Even if strong encryption were outlawed, criminals would still find secure avenues to communicate. For example, breakable codes and ciphers could, in some instances, provide criminals with enough security to pass on time-sensitive information before law enforcement had time to decipher the message and act on its contents. Digital steganography is also a potential subtle form of communication that would obscure messages from law enforcement to stop them from even realizing a message was being sent. And of course, meeting in person is a reliable way of communicating which is much more difficult to wiretap than an email or phone call.

Mysterious Numbers

The 99% Invisible episode about numbers stations was interesting to me because radio is a unique form of communication as it relates to cryptography. Since radio is publicly broadcast, anyone can tune in, so while sending an encrypted message, you have to assume that your enemies are listening at all times. Because of this, using the radio to broadcast highly sensitive information such as important updates to spies in the field seems like an odd form of communication to choose. However, as was pointed out in the podcast, the benefit of using radio for communication is that it is accessible from anywhere, and it keeps the location of the recipient unknown, making it the perfect form of communication for spies who need to keep their heads down. This in addition to the use of one time pads which are in theory unbreakable without the key make numbers stations a surprisingly efficient way to distribute information.

In addition to the interesting content, there were a variety of techniques used to keep the podcast interesting to listen to. Even while people were talking, there was always background music, sometimes even a numbers station playing in the background. I would have thought that having someone listing numbers in the background would make it difficult to understand the podcast, but it was done in such a way that it actually made the audio more interesting to listen to, and it provided continuity between segments. In addition, even when there was dialogue going on, there was always something in the background to keep your ears fully engaged, and it strengthened the sense of continuity of the episode making it easier to listen to without zoning out.

Breaking (Almost) Unbreakable Ciphers

The strength of the Vigenère Cipher depends largely on the length of the keyword. If the keyword is just one letter, then it is nothing more than a simple shift cipher; if the keyword is the same length as the plain text, there will be little to no discernable pattern. However, Singh clearly demonstrates that even with a keyword as long as the text, breaking the Vigenère is doable by guessing common words like "the."

Even though it is relatively straightforward to break even these more secure ciphers, doing so in practice is often much harder. Primarily, this is because of the amount of guessing and checking required and the creative insights necessary to realize the best way to break the code. During the process of deciphering the message, and essential step is guessing words either in the plain text or in the keyword, and if your guess is wrong, you have to backtrack until you are confident that all of your work is correct and start from there again. This makes the process of cryptanalysis tedious and time-consuming.

Once you know what method to use to break the cipher, deciphering the message is only a matter of time, but often, figuring out how to approach a complicated cipher takes even the smartest cryptanalysts years to figure out on their own. For example, breaking the simple Vigenère cipher was not difficult; once Charles Babbage figured out how to break it, the Vigenère went from being an unbreakable cipher to extremely insecure overnight. This demonstrates that breaking the cipher itself is often not the most difficult part; the hardest part of breaking complex ciphers is coming up with a foolproof method which exploits weaknesses in the cipher.

Compromising: The Best Solution to a Difficult Problem

On the privacy versus security display at the Newseum, the responses to "What would you give up to feel safer?" run the gamut from those who feel that they have nothing to hide, to those who believe that privacy is too important to sacrifice.

However, the Benjamin Franklin quote in particular caught my eye since I had never heard that before, and I thought that was a striking way of summarizing the pro-privacy position, especially hundreds of years before the advent of electronic surveillance. After a quick Google search, it became clear that his quote has been misused. He wasn't speaking about government surveillance at the time; instead, Franklin's letter was about a tax dispute between the state legislature and the colonial government during a period of French and Indian attacks. In fact, the "essential liberty" Franklin was referring to was not an individual liberty, but actually the freedom of the government to provide security to the people. In this way, Franklin's argument has been fundamentally misunderstood; if anything, he is clearly in favor of the government ensuring the security of the people, although his stance on the relative importance of privacy is unclear.

The majority of responses on the board though don't fall strictly on one side of the debate. They think it is best to strike a balance between surveillance (i.e. security) and privacy. Even the most radical advocates of privacy or surveillance must recognize that this is the most likely outcome in reality, since outspoken members on both sides will push back against the efforts of the opposite side once they try to tip the scales too much in their favor. I thought this was the main takeaway from the exhibit: there are people with strong convictions on both sides of the argument, and they will all fight for what they think provides the most benefit. Even if only one side can be correct in theory, in practice, we must strike a delicate balance between surveillance and privacy to keep everyone happy, free, and safe.

The Appeal of an Unbreakable Cipher

The unbroken Beale ciphers, likely enciphered using a book cipher, will remain nearly impossible to break until we figure out what key text was used to encipher them. Despite this, cryptanalysts have been trying to decipher the messages using various key texts, essentially guessing and checking in the hopes that they stumble upon the correct one. At this point, a reasonable guess is that the key text was a letter written by Beale himself, and without that letter, the ciphers will remain unbroken.

Nevertheless, people continue to try to break the ciphers with various different methods. Some test new key texts and hope to crack the cipher by pure luck; others try cracking the cipher in new ways in hopes that the messages were encoded with something other than a book cipher. Either way, these efforts require large amounts of time and creativity for even a minuscule chance of cracking either one of the ciphers.

The people who try to break these ciphers today are likely aware that they are nearly impossible to crack, and their motivation is probably not the wealth; there are many other ways to get wealthy if you are willing to put in that much time and effort. Rather, the reward they chase after is an intellectual one; they are hoping that, even by pure chance, in cracking the Beale cipher, they will be the first one to read his note, knowing that the knowledge it contains is entirely theirs until they decide to share it with the world. Even though the contents of the note are probably all related to the buried treasure which is of secondary importance, there is a unique appeal to being the first one to break a supposedly unbreakable cipher. The opportunity to become known as the person who did the impossible is tantalizing, and apparently to some, that satisfaction is worth chasing after no matter how unlikely it is that you will achieve it.

Same Evidence, Different Arguments: Value Conflicts in Little Brother

During the class discussion led by Ms. Galvez, Marcus cited a short passage from the Declaration of Independence to explain his attitude toward the DHA's extensive surveillance techniques and invasion of privacy, stating that the primary role of the government is to ensure the safety and happiness of the people, and that it derives its authority from the consent of the governed. However, in the next class, Mrs. Andersen, the new teacher, uses another quote from the declaration of independence about life, liberty, and the pursuit of happiness to support her view that the DHA is justified in extensive surveillance.

The interesting thing about this part of the book is that both sides of the argument are citing the same fundamental idea to support opposite positions; central to both passages is the idea that the government's primary purpose is to ensure the happiness and safety of the people. But this idea, while most people agree with it, can lead to drastically different visions of society depending on your interpretation.

Marcus takes the view that the government's invasion of personal privacy through mass surveillance limits personal freedoms to the point that it is nearly impossible to be happy while not meaningfully improving the safety of the people, so the government is failing to perform its primary duty. In contrast, Mrs. Anderson takes the view that "life, liberty, and the pursuit of happiness" are important in that order. That is, life is more important than liberty, and liberty is more important than happiness, so the government is justified in intensive surveillance to ensure the life of the people, even if it means sacrificing some liberties and happiness.

To resolve this conflict, we must realize that fundamentally, it is a conflict of values. Marcus is willing to sacrifice a marginal increase in safety for his freedom and right to privacy; Mrs. Andersen values her safety to the point that she is willing to sacrifice her privacy and some personal freedoms. I think in the extreme case Doctorow lays out in Little Brother, Marcus is clearly correct; the amount of freedom and happiness sacrificed to the DHS outweighs the tiny increase in safety they provide, but in general, both value rankings are potentially valid, and conversations about how we as a society prioritize our values are essential in settling disagreements and solving problems in the public sphere.

Mining Student Data Could Save Lives - or Make Life Harder

In his essay, "Mining Student Data Could Save Lives", Michael Morris argues that universities should implement data mining algorithms to detect patterns in student activities on their networks (e.g. any activity occurring on the WiFi network, school computers, or communications through university email accounts). According to Morris, the implementation of these algorithms could potentially prevent violent acts from occurring on campus; after all, almost every large-scale act of campus violence has been preceded by warning signs which, if recognized before the incident, would have indicated that an act of violence was imminent and could have been prevented.

Indeed, there is something compelling about Morris' argument. A student who purchased high-powered firearms on the school network sending emails on a clearly detailing plans to perpetrate an act of violence  clearly warrants a breach of individual privacy to ensure the safety of the campus community. However, very few scenarios are this clear cut since most evidence would not be as damning as an explicit description of a violent act sent on a university email.

This raises the issue of false positives, one that is inherent in all data mining algorithms. In the article, Morris specifically cites the example of banks using data mining to detect stolen credit cards. And while these algorithms are good at detecting stolen cards, they are equally adept at generating false positives, deactivating cards after valid transactions that were deemed suspicious. Similarly, algorithms designed to monitor communications on university networks would need to be extremely sensitive even to small red flags in order to effectively prevent violent acts. However, designing the algorithm in this way would lead to false positives being regularly detected, incriminating students who had no violent intentions simply for their normal browsing activities and communications with others. If even one student is called in to "have a conversation" because of something the algorithm detected, it has already failed to do its job at the cost of individual freedom and privacy.

In principle, Morris' idea is persuasive. The perfect data mining algorithm would be ideal for stopping campus violence without the need for extreme invasion of privacy or the generation of false positives. However, the implementation of a data mining algorithm in our complex world would require sacrificing students' digital privacy for little to no benefit.

Cryptography in the Modern World: Keeping a Information Secret in the Age of Computing

In the first chapter, the examples of cryptography Singh selected were confined to the upper echelons of society: nobles, scholars, religious and military leaders. But perhaps more telling is the affluence of cryptanalysts such as Thomas Phelippes, a linguist fluent in five languages and an accomplished code-breaker; knowing five languages is a feat even in the modern world, but acquiring a new language (much less five) prior to readily accessible educational resources is nothing short of extraordinary.

Phelippes' impressive education supports the hypothesis that cryptography and cryptanalysis are areas of study suitable for only those who have a sufficient understanding of an array of scholarly disciplines and the resources necessary to achieve it. This is perhaps more true of today's world, as modern ciphers and cryptographic techniques are far more complex and difficult to crack than simple substitution ciphers and thus require and even more comprehensive education than was necessary centuries ago.

Fortunately, modern society provides us with the ability to attain a level of education sufficient for developing and cracking substitution ciphers by the time we graduate high school; even people who have no formal training in cryptography are capable of employing advanced classical techniques such as frequency analysis to decrypt secret messages. The ubiquity of this approach is a testament to the modern educational system's ability to produce people capable of thinking creatively to solve new problems.

However, this amount of ingenuity entails a notable problem: it essentially renders substitution ciphers (and other ciphers with similar security levels) useless. If an enciphered message can be cracked by the average person (without the aid of a computer) in the matter of hours, a more secure method of encrypting messages is necessary to hide meaning. Although relatively secure encryption usually doesn't present much difficulty thanks to the advent of computing, it makes securely encrypting a message or quickly decrpyting a secure message without a computer nearly impossible; furthermore, with the power of modern computing at their fingertips, cryptanalysis are constantly working to develop faster ways to decrypt information, rendering insecure techniques that were among the best we had discovered just decades earlier. Modern cryptographers are then presented with a unique challenge: creating systems of encryption that allow the intended recipient to receive the message but are strong enough to remain unbreakable for decades to come.

Powered by WordPress & Theme by Anders Norén