One-Time Pad & Kerckhoffs' Principle

You can’t learn about cryptography without meeting Alice, Bob, and Eve. This chapter is about the classic problem of private communication, in which Alice has a message that she wants to convey to Bob, while also keeping the contents of the message hidden from an eavesdropper Eve. As you will learn, there is more to cryptography than just private communication, but it is the logical place to start. After all, the word cryptography means “hidden writing” in Greek.

What Is [Not] Cryptography?

There’s more to security than just cryptography. Every security problem you care about probably involves both computers and humans, both of which are relatively complex systems. Having a security mindset means worrying about adversarial behavior in all parts of those complex systems.

Let’s take a closer look at our motivating scenario featuring Alice, Bob, and Eve, and establish some clear boundaries about what part of the problem we are actually trying to solve in this course. This discussion is going to look like a lot of excuses about why certain important things are not our problem! That’s the price we pay for not solving all the world’s problems, and being intellectually honest about it.

Encryption Basics & Terminology

In our idealized model, Alice has a message $m$ that she wants to send (privately) to Bob. We call $m$ the plaintext.plaintext We assume she will process that plaintext somehow to obtain a value $c$ (called the ciphertext)ciphertext that she will actually send to Bob. The process of transforming $m$ into $c$ is called encryption,encryption; $\textsf{Enc}$ and we will use $\textsf{Enc}$ to refer to the encryption algorithm.

We assume that the ciphertext may be observed by the eavesdropper Eve. Note that 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. We also are not concerned with how $c$ reliably gets from Alice to Bob. For now, we will not worry about an attacker that tampers with $c$ (causing Bob to receive a different value), but this scenario will be discussed later.

When Bob receives $c$, he runs a decryption algorithm $\textsf{Dec}$decryption; $\textsf{Dec}$ to (hopefully) obtain the original plaintext $m$.

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 $\textsf{Dec}$ algorithm 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 $\textsf{Enc}$ and $\textsf{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, the most famous of which is now known as Kerckhoffs' 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.secret key The key is just an extra piece of information given to both the $\textsf{Enc}$ and $\textsf{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,key generation; $\textsf{KeyGen}$ and we write $\textsf{KeyGen}$ to refer to the (randomized) key generation algorithm. We call the collection of three algorithms ($\textsf{Enc}$, $\textsf{Dec}$, $\textsf{KeyGen}$) an encryption scheme.encryption scheme Remember that Kerckhoffs' principle says that we should assume that an attacker knows the details of the $\textsf{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, Assumptions

Here are a few things that we will blatantly ignore.

We won't discuss how Alice and Bob actually obtain a common secret key. This is obviously an incredibly important problem (known as key distribution) in the real world. We will discuss some clever approaches to this problem much later in the book. In our defense, the problem we are solving is already quite non-trivial: once two users have established a shared secret key, how can they use that key to communicate privately?One of my favorite descriptions of cryptography is: "cryptography is a tool for turning lots of different problems into key management problems.'' I first heard this quote in a talk by Lea Kissner, principal security engineer at Google.

Throughout this course we also just 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.

For now, we will assume that both Alice and Bob each have a copy of the same key. Much later in the course we will also consider situations where Alice & Bob actually have different secret information.

Not Cryptography

People use many techniques to try to hide information, but many are "non-cryptographic'' since they violate Kerckhoffs' principle:

• Encoding/decoding methods like base64: \[ \texttt{\textcolor{a91616}{joy~of~cryptography}} \quad\leftrightarrow\quad \texttt{\textcolor{a91616}{aGFoYSwgSSBmb29sZWQgeW91IQ==}} \] are public algorithms that involve no secrets. Base64 is useful for incorporating arbitrary binary data into a structured file format. But it adds nothing in terms of security.
• Sometimes the simplest way to describe an encryption scheme is with operations on binary strings (i.e., $\texttt{\textcolor{a91616}{0}}$s and $\texttt{\textcolor{a91616}{1}}$s) 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. As above, representing things in binary has no effect on security since it does not involve the secret key.

Test: $ \{\texttt{\textcolor{a91616}{0}},\texttt{\textcolor{a91616}{1}} \}^\lambda $

Test: $\lib{cpa\$-real}^\Sigma$ $\textsc{SmallCaps}$