Cryptography is not a magic spell that solves all security problems. Cryptography can provide solutions to cleanly defined problems that often abstract away important but messy real-world concerns. Cryptography can give guarantees about what happens in the presence of certain well-defined classes of attacks. These guarantees may not apply if real-world attackers "don’t follow the rules" of a cryptographic security model.
Always keep this in mind as we define (i.e., limit) the problems that we solve in this course.
Encryption Basics & Terminology
Let’s begin to formalize our scenario involving Alice, Bob, and Eve. Alice has a message \(m\) that she wants to send (privately) to Bob. We call \(m\) the plaintext. We assume she will somehow transform that plaintext into a value \(c\) (called the ciphertext) that she will actually send to Bob. The process of transforming \(m\) into \(c\) is called encryption, and we will use Enc to refer to the encryption algorithm. When Bob receives \(c\), he runs a corresponding decryption algorithm Dec to recover the original plaintext \(m\).
We assume that the ciphertext may be observed by the eavesdropper Eve, so the (informal) goal is for the ciphertext to be meaningful to Bob but meaningless to Eve.
Secrets & Kerckhoffs’ Principle
Something important is missing from this picture. If we want Bob to be able to decrypt \(c\), but Eve to not be able to decrypt \(c\), then Bob must have some information that Eve doesn’t have (do you see why?). Something has to be kept secret from Eve.
You might suggest to make the details of the Enc and Dec algorithms secret. This is how cryptography was done throughout most of the last 2000 years, but it has major drawbacks. If the attacker does eventually learn the details of Enc and Dec, then the only way to recover security is to invent new algorithms. If you have a system with many users, then the only way to prevent everyone from reading everyone else’s messages is to invent new algorithms for each pair of users. Inventing even one good encryption method is already hard enough!
The first person to articulate this problem was Auguste Kerckhoffs. In 1883 he formulated a set of cryptographic design principles. Item #2 on his list is now known as Kerckhoff’s’ principle:
Kerckhoffs’ Principle:
"Il faut qu’il n’exige pas le secret, et qu’il puisse sans inconvénient tomber entre les mains de l’ennemi."
Literal translation: [The method] must not be required to be secret, and it must be able to fall into the enemy’s hands without causing inconvenience.
Bottom line: Design your system to be secure even if the attacker has complete knowledge of all its algorithms.
If the algorithms themselves are not secret, then there must be some other secret information in the system. That information is called the (secret) key. The key is just an extra piece of information given to both the Enc and Dec algorithms. Another way to interpret Kerckhoffs’ principle is that all of the security of the system should be concentrated in the secrecy of the key, not the secrecy of the algorithms. If a secret key gets compromised, you only need to choose a new one, not reinvent an entirely new encryption algorithm. Multiple users can all safely use the same encryption algorithm but with independently chosen secret keys.
The process of choosing a secret key is called key generation, and we write KeyGen to refer to the (randomized) key generation algorithm. We call the collection of three algorithms (Enc, Dec, KeyGen) an encryption scheme. Remember that Kerckhoffs’ principle says that we should assume that an attacker knows the details of the KeyGen algorithm. But also remember that knowing the details (i.e., source code) of a randomized algorithm doesn’t mean you know the specific output it gave when the algorithm was executed.
Excuses, Excuses
Let’s practice some humility. Here is just a partial list of issues that are clearly important for the problem of private communication, but which are not addressed by our definition of the problem.
We are not trying to hide the fact that Alice is sending something to Bob, we only want to hide the contents of that message. Hiding the existence of a communication channel is called steganography.
We won’t consider the question of how \(c\) reliably gets from Alice to Bob. We’ll just take this issue for granted.
For now, we are assuming that Eve just passively observes the communication between Alice & Bob. We aren’t considering an attacker that tampers with \(c\) (causing Bob to receive and decrypt a different value), although we will consider such attacks later in the book.
We won’t discuss how Alice and Bob actually obtain a common secret key in the real world. This problem (known as key distribution) is clearly incredibly important, and we will discuss some clever approaches to it much later in the book.
In my defense, the problem we are solving is already rather non-trivial: once two users have established a shared secret key, how can they use that key to communicate privately?
We won’t discuss how Alice and Bob keep their key secret, even after they have established it. One of my favorite descriptions of cryptography is due to Lea Kissner (former principal security engineer at Google): "cryptography is a tool for turning lots of different problems into key management problems."
Throughout this course we simply assume that the users have the ability to uniformly sample random strings. Indeed, without randomness there is no cryptography. In the real world, obtaining uniformly random bits from deterministic computers is extremely non-trivial. John von Neumann famously said, "Any one who considers arithmetical methods of producing random digits is, of course, in a state of sin." Again, even when we take uniform randomness for granted, we still face the non-trivial question of how to \(use\) that randomness for private communication (and other applications), and also how to use only a manageable amount of randomness.
Not Cryptography
People use many techniques to try to hide information, but many are "non-cryptographic" since they don’t follow Kerckhoffs’ principle:
Encoding/decoding methods like base64 ...
... are useful for incorporating arbitrary binary data into a structured file format that supports limited kinds of characters. But since base64 encoding/decoding involves no secret information, it adds nothing in terms of security.
Sometimes the simplest way to describe an encryption scheme is with operations on binary strings (i.e., Os and 1s) data. As we will see, one-time pad is defined in terms of plaintexts represented as strings of bits. (Future schemes will require inputs to be represented as a bitstring of a specific length, or as an element of \(\mathbb{Z}_{n}\), etc.)
In order to make sense of some algorithms in this course, it may be necessary to think about data being converted into binary representation. Just like with base64, representing things in binary has no effect on security since it does not involve any secret information. Writing something in binary is not a security measure!