Introduction to Cryptography: The Beauty of Adversarial Design
--
This article is intended to be an easy-to-understand introduction to cryptography for students and people with a semi-technical background. I am not qualified to talk about security except at a high level; I took (and highly enjoyed) CS 194, a cryptography class at Berkeley. I wrote this article to explain cryptography to my blockchain friends using some of the formal concepts I learned to avoid hand-waving.
The purpose of this article is to introduce cryptography by first describing how security models are constructed, and hopefully display the beauty of adversarial thinking. Every section will tie in an example using cryptocurrency. At the end, you should be able to: explain common cryptographic concepts, break down formal definitions of protocols in technical papers, and design a threat model for your own system.
What is cryptography?
Cryptography is the science of keeping secrets. It is used to encode and decode secret information, authenticate the origin of messages, prove unique identities, and other actions necessary for secure communication. In cryptography, there’s always a bad guy (an adversary) and the security of your cryptographic protocol is defined by how strong of an adversary it can defend itself against. As you can imagine, cryptography implementations used in modern day computing are incredibly math-heavy, but the basic concepts are not too difficult to understand.
Why Does Cryptography Exist?
Secrets are especially important in the digital world because, most likely, the people you communicate with will not have a direct, offline link to your computer. Most of what you do is online; your computer is connected to a vast network of other computers that relays your messages and data. If you want privacy, you need a way to encode your messages so those computers cannot read them. Another, equally important issue is authentication: since everyone looks the same on the internet, Alice proves to her friends that she is indeed Alice by showing she knows Alice’s secrets.
Why Care?
One subgoal of this article is to help you evaluate the security features of the cryptocurrencies and software-reliant products that you might be interested in. Before you put too much trust into “crypto magic,” learning some basic cryptographic concepts might help build a mental model of what is technically sound. Unless you’re a cryptographer or mathematician, there will always be a bit of hand-waving, but I believe that these principles should become 21st century-common sense.
Cryptography vs Cryptocurrency
Cryptography is what cryptocurrencies are based off of (they are distinct concepts but closely related). Cryptocurrencies such as Bitcoin are so named because they do not rely on trusted government agencies to regulate how money can be spent; the rules of ownership and transfer are strictly defined and enforced by cryptographic protocols. Essentially, owning a bitcoin is equivalent to knowing the secret to being able to spend it. Theoretically, as long as the underlying cryptographic protocols are secure, you can rest assured that your bitcoin cannot be stolen.
The Good Guys
All cryptographic protocols are defined as a set of algorithms that achieve some goal regarding some secrets. The good guy, traditionally denoted as Alice (sometimes she also communicates with Bob), uses the algorithms in her communications.
Keyed Functions
We all have locks on our house doors. We don’t want to completely redesign locking mechanisms from scratch for each household but, if all locks were exactly the same, we could use our keys to enter anyone’s home. Similarly, every protocol is merely a tool and should be usable by many parties, so all the algorithms are customizable keyed functions: there exists a key that is kept secret by the good guy(s) and is heavily involved with each algorithm. Base algorithms can be run by anybody, but output different results depending on the key inputted. Notation for a keyed function generally writes the key as a subscript after the function, but unfortunately Medium doesn’t support fancy mathematical notation.
A good rule of thumb in cryptography is that the security of your protocol should not rely on keeping your base protocol secret; the only secret you should really have is your key (this rule is called Kerchoff’s Principle). Either way, it would be cripplingly difficult to keep protocols secret — they are typically designed to be standard processes run on every computer.
How To Read Cryptography
Let’s use the classic symmetric key (same key used by all good guys) encryption scheme (used to encode secret messages) as an example. It’s designed to be used by two good guys, Alice and Bob, who share a secret key already and want to communicate secret messages to each other (it could also be Alice encrypting something for her future self).
We define our scheme: π = (Gen(n), Enc(m), Dec(c))
- Gen(n): Generates the secret key. This algorithm should be run first, and uses n (the security parameter) to generate one key to be used in the next two algorithms.
- Enc_k(m)*: Encrypts a plaintext message m using the key k. This algorithm is a keyed function as described before: k is a key to manipulate the function itself rather than the argument, so it is written as a subscript. It produces a ciphertext that can be sent across the internet; theoretically, nobody without the key can decipher what the message is.
- Dec_k(c): Decrypts a ciphertext message c using key k. This algorithm should recover the original message m as long as k is the same as the key used to encrypt it.
Not Included
These three algorithms encapsulate everything needed for Alice and Bob to communicate and keep their messages secret, but nothing else. It doesn’t say anything about how the messages are sent or even what medium to use. Notably, these processes don’t need to be computerized: children using fruits to refer to their crushes is also a form of encryption. The key is their pre-established secret code; replacing “Brian” with “Banana” is encryption, and understanding that “Banana” means “Brian” is decryption.
Completeness vs Security
In cryptography, every protocol has Completeness and Security properties. The Completeness property states that it will always work for the good guys: if you encrypt a message and then decrypt it, you should always get the original message back. But completeness is not enough — you could just be returning the plaintext as your ciphertext. Security defines what the bad guys shouldn’t be able to do. We’ll get to that in a bit.
The Good Guys In Bitcoin
Let’s briefly look under the hood and reveal what “crypto magic” Bitcoin uses. One key protocol is a Digital Signature Scheme (DSA), used to authenticate transactions: it’s how Alice proves she knows the secret to spending her bitcoin. The protocol is made up of three algorithms (Gen(n), Sign(m, sk), Verify(σ, pk). Gen(n) generates a secret key for Alice and a public key the world knows is Alice.
The bitcoin is publicly known to be owned by Alice’s public address (which is actually her hashed public key but don’t worry about it for now). When Alice wants to spend her bitcoin, she Signs a transaction using her secret key. Miners validate the transaction by calling Verify on her signature and public key. Bitcoin uses an Elliptic Curve Digital Signature Algorithm (ECDSA) called secp256k1. Let’s leave it at that for now, and dive deeper in a future article.
The Bad Guys
Like previously mentioned, all cryptographic schemes have a bad guy that the good guys are trying to keep their secrets from. Traditionally, the adversary is named Eve (for eavesdropper) or Mallory (for malicious), or some other punny name. The adversary may be attempting to do any number of things: forge a signature to impersonate Alice, retrieve her the key to decrypt all messages, or even just guess the first bit of an encrypted ciphertext.
Experiments
Experiments describe what a theoretical battle would look like between the good guys and the bad guys. They very explicitly state what the adversary can and cannot do. This experiment describes an attack against a Challenger (good guy) running a private (symmetric) key encryption scheme; the Adversary wins if she is able to forge a new signature.
The following is an example diagram of an experiment where the adversary is able to specify two plaintext messages, is provided the ciphertext of a random one, and has to guess which one was encrypted. It’s a decisional problem, which I’ll explain in a bit.
Here’s an elaborated version of the experiment that’s a little easier to understand.
The experiment name indicates that it is a Private Key experiment in which the adversary is an Eavesdropper; the challenger is using the encryption scheme π and the adversary is using an algorithm denoted as A. Note that the adversary has limited interactions: she must specify exactly two messages, and the messages have to be the same length. She also cannot query the challenger for more sample outputs; she is merely eavesdropping on the ciphertext output.
We can also define security models such as Chosen Plaintext Attack (CPA), where the adversary can query for any number of plaintexts to be encrypted for her, and Chosen Ciphertext Attack (CCA), where the adversary can additionally ask for the decryptions of ciphertexts. We can limit how many queries the adversary can make, when she is allowed to make them, and whether she can query for something identical to the problem she is trying to solve. All of these factors affect how “strong” the security is.
Mt. Gox and “That Time Bitcoin Was Hacked”
Let’s get this straight first: Bitcoin was never hacked. Mt. Gox (the biggest Bitcoin exchange at the time) held large sums of bitcoin in hot wallets, private keys were leaked and $450 million in bitcoins were stolen. No Bitcoin protocols were violated; in fact, one could argue that the bitcoins were rightfully spent by a possessor of the private key.
The major takeaway is that, even if you have an airtight protocol, you must be careful what assumptions you are building upon. In this case, Bitcoin assumed that private keys would be kept secret — which shouldn’t be unreasonable, but proved to be a successful attack vector. The Bitcoin community has found, exploited, and will likely continue to find smaller-scale security flaws in Bitcoin’s protocols, but an equally-important challenge lies in securing user-facing services.
The rest of the article describes how adversaries are designed to describe what kinds of security features are needed.
Defining What Winning Means
In any debate or battle, the easiest way to win is to define what winning means in your favor. Sometimes, an adversary wins if she can forge a signature or guess a password — but it is not always so stringently defined. Similar to the above experiment example, the adversary often just needs to guess between a “yes” or a “no.”
Computations vs Decisions
A computational problem is exactly what it sounds like: given some problem, the adversary must somehow compute the solution to the problem. Some examples include finding the discrete logarithm of a group element and finding the prime factors of a large number. A decisional problem requires the adversary to distinguish between two or more outputs such as pseudorandom vs truly random or an encrypted key vs a scrambled garbage string. Although decisional problems sound “easier,” they are not inherently less secure constructions than computational ones: in both cases, the adversary should only be able to do negligibly better than randomly guessing.
Indistinguishability is a core concept in adversarial design. Distinguishers are a type of adversary that tackle decisional problems, typically allowed to query a polynomial number of outputs and run polynomially bound algorithms to make the decision. It is a common proof technique to show two protocols have indistinguishable outputs and thus are equally secure.
Pseudorandomness
You may have heard the term pseudorandom, an adjective that describes something generated using a deterministic algorithm but mimics a random distribution. Since we don’t always have access to perfectly random inputs, we make Pseudorandom Functions (PRFs) and Pseudorandom Generators (PRGs) whose outputs look random, i.e. efficient distinguishers cannot distinguish from random. If you see 100 (or any polynomial number of) numbers spit out of a standard PRG, you should not be able to find any pattern that suggests it isn’t random.
Formal Verification
I don’t claim to be an expert on this, but I fear that formal verification will be used as a marketing ploy to woo security-concerned consumers, just like the word “organic” often gives grocers a false sense of cleanliness or health. For those not familiar with formal verification, it is essentially a rigorous auditing process to mathematically prove a piece of code is secure. I think (again, my opinion) it is excellent practice and an extremely useful tool for finding bugs, but by no means should consumers believe the words “formal verification” ensure security.
Let me illustrate more explicitly. In evaluating the security of an application, the first thing you should look at is how they define winning. A theoretically perfect smart contract (i.e. as a modular component, it has enforced preconditions and proven invariants) can still result in consumer harm if the base application mismanages read/write access to its data structure storing account balances, the underlying hash function is not collision-resistant, or if the transaction ends up in an orphaned block. Hell, the user could lose his private key.
Perfect vs Computational Worlds
Also known as: theory vs practice. In theory, we want our algorithms to be perfect: no matter how strong and efficient the adversary is, she shouldn’t be able to crack the code without entirely brute forcing it. Cryptographers try their hardest to make this the case, of course, but they aren’t magicians. And what if quantum computers become a reality?
Practicality
In case you were wondering, yes, perfect security does exist. One-Time Pad (OTP) is a private key encryption protocol that is extremely simple and, in fact, perfectly secret. To encrypt and decrypt, the key is xor’d with the message and ciphertext. The perfect security is easy to prove formally; as long as the key is drawn uniformly from the keyspace, every message is equally likely to correspond to a given ciphertext. The problem is the key needs to be as long as the message, and can only be used for one encryption. I mention this protocol to illustrate that there’s often a tradeoff between efficiency and security: one would think that security is always the highest priority but, in this case, we would prefer something more practical.
Defining Computational Security
Cryptographers typically use a more realistic way to argue that a scheme cannot be broken: given an efficient adversary, she only has a negligible probability of breaking the scheme. “Efficient” is defined as Probabilistic Polynomial Time (PPT): the adversary only has enough time to run an algorithm that takes polynomial time and can access randomness. “Negligible probability” has a precise definition you can read about [here]. It just means so unlikely that it’s practically impossible, like guessing one atom out of all the atoms in the universe. By limiting the adversary’s resources and allowing an extremely tiny probability for failure, practical security is possible.
If P=NP
If you’ve studied algorithms, you may have noticed that this definition seems to assume P is not equal to NP — that there exist search problems that are hard to solve. Indeed, much of modern cryptography relies upon this assumption or a similar variation (i.e. the computational “hardness” of discrete log, factoring large numbers, etc.). Most people consider these assumptions sound with a very high probability, but there are areas of cryptography research dedicated to the disastrous possibility that they aren’t.
Conclusion
Now, try to look at the world through the lens of a cryptographer: before you build anything, first design an adversary. Create experiments detailing every possible attack on your design. How secure a system is depends heavily on the adversary’s capabilities; be careful in what assumptions you make and protect your code from possible vulnerabilities in its dependencies. Make your product idiot-proof. Adversarial design is applicable to user research, debates and fights, and anything that might encounter bad guys.
Please follow Kevin Chang to be notified when the next part is published. The second article will ramp up into cryptographic primitives used as building blocks in cryptography.
Works Referenced
Introduction to Modern Cryptography, Second Edition. by Jonathan Katz and Yehuda Lindell
About Gloria
Gloria Zhao is President of Blockchain at Berkeley and a UC Berkeley student majoring in Computer Science and Psychology. She also teaches Blockchain Fundamentals, an undergraduate Berkeley EECS course.
