One-Time Pad and the Provable Security Mindset

Every cryptography story begins the same way: Alice wants to send a message to Bob. This would be an easy task if it weren't for Eve, who eavesdrops on their conversation.

1.1. Defining the problem

Alice (she/her) has a message $\ptxt$, called the plaintext, that she wants to send privately to Bob (he/him). She uses an encryption procedure, which we call $\Enc$, to transform the plaintext into a ciphertext $\ctxt$, which she can send to Bob. When Bob receives $\ctxt$, he runs a decryption algorithm $\Dec$ to recover the original plaintext.

Security is all about what can/can't happen in the presence of an attacker, usually referred to as the adversary. For now, let's consider an eavesdropping adversary—traditionally called Eve (she/her)—who observes the ciphertext during transit. Bob must know something that Eve does not: Otherwise, Eve would be able to do everything Bob can do, including decrypt the ciphertext. Some information about the decryption process must be secret, known to Bob but not Eve. But what exactly should be kept secret?

It's important to understand the difference between two similar-sounding questions:

• What should be kept secret in a real-world scenario? The more information you can keep from the adversary, the harder it is to attack. So if you have an opportunity to hide more information about the encryption/decryption methods, why not take it?

• What must be kept secret in order to prove a security guarantee? Every piece of information that must be secret is an assumption, a limit on the real-world relevance of our encryption method. Given the choice, wouldn't you prefer an encryption method whose security makes the fewest possible assumptions about what is kept secret from the adversary?

Naïve way of thinking about secrecy: For thousands of years, cryptography was based on the secrecy of the $\Enc$ and $\Dec$ algorithms themselves. There is nothing wrong in principle with making the encryption/decryption methods secret, but it's not ideal to base all your security guarantees on their secrecy.

• If encryption/decryption algorithms are required to be secret, and one hundred pairs of people want to send private messages, then they will need to invent one hundred sufficiently different but equivalently secure encryption methods. This level of cleverness doesn't scale well.

• If encryption/decryption algorithms are required to be secret, and the algorithms somehow fall into the adversary's hands, then it becomes necessary to redesign a new and sufficiently different method. It is difficult to keep algorithms secret, and easier to keep data secret.

• If encryption/decryption algorithms are required to be secret, how can we subject anyone's encryption method to scientific scrutiny? How can we develop a consensus about what makes for a good encryption method? Scientific consensus is an inherently public process.

Modern way of thinking about secrecy: These days, we partition the encryption process into secret and nonsecret parts. The secret part is called the key: It is a piece of data that is provided as input to both the encryption and decryption algorithms. Ideally the key is short, so it's easy to generate, store secretly, and replace if necessary.

The key is the only thing assumed to be secret. The encryption/decryption algorithms themselves do not need to be secret, and their security guarantees should apply even if the adversary knows these algorithms.

The nineteenth-century cryptographer Auguste Kerckhoffs was the first to clearly articulate the idea that encryption methods should remain public. We still refer to the idea by his name:

Remember: Kerckhoffs's principle doesn't say that you must make the algorithms public; it says that the system should be secure even if the algorithms are public.

1.2. One-time pad

One-time pad (OTP) is the oldest and simplest encryption method that we'll encounter in this book. The keys, plaintexts, and ciphertexts in OTP are each $n$-bit strings. The value $n$ can be any positive integer, and it can be known to the adversary. The encryption and decryption algorithms of OTP are as simple as it gets: Just xor the plaintext or ciphertext with the key. We can write these algorithms formally:

In order for OTP to be useful as a communication tool, the receiver should recover the intended plaintext when decrypting.

The key for OTP must be sampled from the uniform distribution (sampled “uniformly at random”). More precisely, when the key is sampled uniformly, we can actually prove something about the security of OTP.

1.3. How to formalize an attack scenario

In cryptography we prove things like, when you use this cryptographic algorithm in exactly this way, and the adversary has these capabilities, then you can expect this particular guarantee to hold. We can reason formally about such things using an attack scenario—a precisely defined interaction between one or more victims and an adversary—that specifies: (1) the “correct” usage of the cryptographic algorithms for the victim, and (2) the precise capabilities of the adversary. In this section, we discuss how to formalize an attack scenario for OTP; then in the next section, we will prove a security guarantee that holds in that scenario.

The encryption algorithm of OTP has two inputs and one output:

Our attack scenario assigns the victim and adversary to different parts of this interface.

• The victim is responsible for choosing the key.

• The adversary is responsible for choosing the plaintext input.

• The adversary receives the ciphertext output.

The attack scenario fully prescribes what the victim “should” do. In our OTP attack scenario, the victim is expected to sample the key uniformly at random and use each key to encrypt only a single ciphertext. Our security proof for OTP relies on the fact that the key is chosen in precisely this way. If a real-world application doesn't involve a uniformly sampled key, then the security proof may not apply and its guarantee may not hold.

The behavior of the adversary is arbitrary and unspecified. Assigning the adversary to part of the OTP raw interface is our way of saying that there are no assumptions on how this part of the interface is used. There are no restrictions on how the plaintext input to $\Enc$ is chosen, in the sense that the security proof does not assume anything about how it is chosen (subject to some subtlety, mentioned in section 1.6). There are no restrictions on what kinds of computations can be done on the ciphertext output.

We can express the attack scenario even more precisely if we focus exclusively on the adversary's view of the interaction. The adversary is an arbitrary program that can invoke the following subroutine:

Everything about the attack scenario is captured in the code of this single subroutine. By inspecting this subroutine, you can see that the calling program (adversary) can choose the input $\ptxt$ and see the output $\ctxt$ but has no control over $\key$ since it is sampled inside the subroutine. This reflects the fact that the attack scenario fixes the victim's behavior; the adversary cannot influence it.

Here are two more important things to keep in mind when interpreting the code of the attack scenario:

• Even though OTP's $\Enc$ algorithm is deterministic, this attack subroutine is randomized: Calling it twice, even on the same input, may give different results. This is because the victim samples a fresh key for each encryption, making its overall behavior randomized.

• The variable $\key$ is privately scoped to this subroutine. The calling program cannot see $\key$; it sees only the subroutine's explicit return value $\ctxt$.

Remember, the attack subroutine is not a description of the adversary's behavior, but rather the description of everything in the attack scenario except the adversary. The adversary is some unspecified algorithm that gets to call this subroutine on inputs of its choice and see the resulting output.

When we prove a security guarantee in the next section, we will prove what is/isn't possible by calling this attack subroutine. You can interpret such a proof as saying,

We will use subroutines of this kind to reason about all security properties throughout the rest of the book.

General Mindset For Understanding Attack Scenarios: Every security definition in this book involves some kind of attack scenario. With practice, you will get more comfortable understanding them and interpreting their guarantees.

The victim always controls the secret key material and is responsible for running the cryptographic algorithms as specified. Secret keys are privately scoped to the attack scenario subroutine, which reflects Kerckhoffs's principle that security stems from secrecy of the key. But in OTP, security stems from not just the secrecy of the key but also the fact that a new key is sampled for each encryption. We might revise Kerckhoffs's principle slightly:

“Correct key management” means different things in different attack scenarios. To understand what it means for a particular cryptographic algorithm, we just need to consult the source code of the attack scenario subroutine, since that's where the victim's behavior is prescribed. As a user of cryptography, you can enjoy the resulting security guarantee as long as you ensure that the keys are being managed in precisely this way.

Besides the secret key input, the other inputs and outputs of cryptographic algorithms are generally left at the mercy of the adversary, and they become the adversary's interface to the attack scenario. Letting the adversary choose an input is the worst case; letting the adversary see an output is the worst case. As cryptographers, we strive to build things that are secure even in the worst case!

1.4. How to define and prove security of OTP

Now that we have characterized an attack scenario as a subroutine, what do we do with it? You might be expecting us to formalize explicit goals for the adversary. For example, the adversary can't find the plaintext, or the adversary can't recover the secret key. These bad outcomes are important to consider, but they are not how we formalize what it means to be “secure.”

Instead, we will consider something to be “secure” if the adversary sees only “random junk” in the attack scenario. More precisely, our goal will be to prove that the adversary sees uniformly distributed values. (The uniform distribution is the randomest junk there is!) Applying this principle to our attack scenario for OTP, we formulate security as follows:

Recall what it means for something to follow the uniform distribution: Every outcome is equally likely. In this case, the outcome is the $n$-bit return value of the attack subroutine. There are $2^n$ possible outcomes, so each one should happen with probability $1/2^n$, regardless of the choice of $\ptxt$.

There is nothing particularly special about $\ptxt = \bit{01}$ in this example. The output of $\subname{attack}(\ptxt)$ is uniformly distributed for any $\ptxt$, which we now prove:

1.5. How to interpret a security proof

Even if you followed all the steps of this proof, you probably still have a lot of questions about what this proof means.

1.6. Limitations of security proofs

It's amazing that we can prove anything at all about security! But it's also important to maintain some humility and perspective.

Cryptography cannot address every important security aspect of a real-world system. OTP doesn't attempt to address any of the following questions, even though they are all important to the problem of private communication:

• How can Alice and Bob obtain a secret key known only to them?

• How can they keep $\key$ secret?

• How can a computer sample from the uniform distribution?

• How can Alice ensure that $\ctxt$ is sent reliably to Bob?

• How can Alice hide the fact that she is talking to Bob (rather than hide only the content of her messages)?

• How can Alice be sure that she is communicating with Bob, not an impostor?

• How can we incentivize Alice and Bob to use encryption?

• Should the government be allowed to obtain a warrant to read Alice and Bob's encrypted communications?

• and so on$\ldots$

For now, we have addressed only the following, much narrower question, which I hope you agree is still nontrivial:

A security proof is a guarantee that holds only within one specific attack scenario. The adversaries in our security proofs always “play by the rules” that we have defined. But real-world adversaries may behave in ways that are outside of the attack scenario. The proof tells us nothing about what happens in such a situation.

More concretely, our simple OTP attack scenario contains many implicit assumptions about the adversary's behavior:

• The adversary cannot force a victim to reuse a key for more than one encryption (although the key can repeat by chance).

• The adversary merely observes the ciphertext $\ctxt$ but does not tamper with it before it reaches Bob.

• The adversary cannot make the choice of $\ptxt$ depend on $\key$: In the attack subroutine, $\key$ is sampled after $\ptxt$ has been chosen.

• The adversary learns absolutely nothing about the choice of $\key$.

• The adversary cannot influence how $\key$ is sampled, not even slightly.

• The adversary cannot coerce or trick the victim into running a different algorithm than the expected $\Enc$.

• The adversary cannot see how many clock cycles it took for the victim to encrypt the plaintext.

• The adversary cannot see how the encryption algorithm accesses virtual memory, or whether certain memory accesses hit or missed the CPU's cache.

• The adversary cannot see how many watts the victim's CPU was consuming while it encrypted the plaintext.

• and so on$\ldots$

If you use OTP in a real-world scenario that violates any of these assumptions, you do so at your own risk! Our simple security proof no longer applies, so OTP may or may not provide its expected security guarantee. To know for sure, you would need to formalize an updated attack scenario, making all of the adversary's capabilities explicit, and prove something about that new scenario.

With a little practice, you'll get better at interpreting these formal attack scenarios and spotting their implicit assumptions.

1.7. What's so special about xor?

The security proof for OTP certainly took advantage of some algebraic properties of xor. What happens if we use a different operation to combine the key and plaintext?

In case this doesn't feel like an “attack” to you, we can illustrate the problem more concretely. Plaintext $\bit 0^n$ is always encrypted to ciphertext $\bit 0^n$. So if you observe any nonzero ciphertext, you can conclude that the plaintext could not have been $\bit{0}^n$. You learned something about the plaintext that you did not know before you saw the ciphertext!

So, xor is not the only operation that can be used for a secure variant of OTP. However, xor is a fast, native operation in computer hardware, and it also conveniently causes $\Enc$ and $\Dec$ to be identical algorithms.

Exercises

1. The OTP encryption of plaintext $\bit{mario}$ (when converted from ascii to binary in the standard way (most significant bit first); for example, $\bit{a} = \texttt{61}_{\text{hex}} = \texttt{01100001}_{\text{bin}}$) under key $\key$ is:

   $\bit{1000010000000111010101000001110000011101}.$

   What is the one-time pad encryption of $\bit{luigi}$ under the same key?

2. You have intercepted two OTP ciphertexts:

   $\begin{aligned}\ctxt_1 &= \bit{1111100101111001110011000001011110000110}; \\\ctxt_2 &= \bit{1111101001100111110111010000100110001000}.\end{aligned}$

   You know that both ciphertexts were encrypted with the same key. You know that either $\ctxt_1$ is an encryption of $\bit{alpha}$ and $\ctxt_2$ is an encryption of $\bit{bravo}$ or $\ctxt_1$ is an encryption of $\bit{delta}$ and $\ctxt_2$ is an encryption of $\bit{gamma}$ (all converted from ascii to binary in the standard way).

   Which of these two possibilities is correct, and why? What was the key?

3. Suppose Alice encrypts two plaintexts $\ptxt$ and $\ptxt'$ with OTP, under the same key. What can the adversary learn if it sees both ciphertexts (assuming the adversary knows that Alice has reused the key)?

4. Alice uses OTP and notices that when her key is the all-zeros string $\key = \bit0^n$, her plaintext is sent in the clear as $\Enc(\bit0^n, \ptxt) = \ptxt$. To avoid this problem, she decides to exclude the all-zeros key. Now the set of possible keys is $\bits^n \setminus \{\bit0^n\}$, the set of all $n$-bit strings except $\bit0^n$. The key is now chosen uniformly from this set of $2^n-1$ possibilities.

   Update the formal attack scenario to reflect this change. Does the adversary still see a ciphertext that is uniformly distributed over $\bits^n$? Justify your answer.

5. When the plaintext is equal to the key itself, the ciphertext is always the all-zeros string! So if an adversary sees the all-zeros ciphertext, she learns that Alice encrypted the key itself. Does this contradict claim 1.4.1? Why or why not?

6. Describe the flaw in this argument:

   Consider the following attack against OTP: When the adversary sees ciphertext $\ctxt$, it tries decrypting it under every possible candidate key $\key \in \bits^n$. When it has found the correct key, it outputs the resulting plaintext $\ptxt$, which is bound to be the original plaintext. This contradicts the argument that the adversary learns nothing about the plaintext.

7. In the OTP attack scenario, the adversary chooses the plaintext $\ptxt$ and learns the ciphertext $\ctxt$. Describe how the adversary can compute the key $\key$. Why is it not a security problem that the adversary can do this?

8. When a string is sampled from the uniform distribution over $\bits^n$, each bit is $\bit0$ or $\bit1$ with independent probability 0.5. What happens when the secret key in OTP is sampled from a biased distribution?

   Let's write $\key \xleftarrow[0.4]{0.6} \bits^n$ to mean that each bit of $\key$ is $\bit0$ with probability 0.4, and $\bit1$ with probability 0.6. Update the formal attack scenario to reflect OTP keys sampled in this way, instead of uniformly. Does the adversary still see uniformly distributed output?

9. Suppose Alice and Bob share two OTP secret keys. Alice encrypts a plaintext with one key, then encrypts the resulting ciphertext with the second key. The adversary gets to see the final ciphertext.

   1. If the two keys are chosen independently, then we can formalize the attack scenario as follows:

      $\subname{attack}(\ptxt)$:

      $\key_1 \gets \bits^n$

      $\ctxt_1 := \key_1 \oplus \ptxt$ // $\Enc(\key_1,\ptxt)$

      $\key_2 \gets \bits^n$

      $\ctxt_2 := \key_2 \oplus \ctxt_1$ // $\Enc(\key_2,\ctxt_1)$

      return $\ctxt_2$

      Is the output distributed uniformly for all choices of $\ptxt$? Justify your answer.

   2. Show how the attack scenario changes if the two keys are identical—that is, if we replace the line $\key_2 \gets \bits^n$ with $\key_2 := \key_1$. What is the resulting output distribution?

10. If $\key$ is also included in the output, does the attack subroutine still produce uniformly distributed output (in this case, over the set of pairs $(\bits^n)^2$)?

    $\subname{attack}(\ptxt)$:

    $\key \gets \bits^n$

    $\ctxt := \key \oplus \ptxt$

    return $(\hl{\key},\ctxt)$

11. Alice rolls two standard six-sided dice and adds their values. Bob has two weird six-sided dice: one with sides labeled 1, 2, 2, 3, 3, 4; and the other with sides labeled 1, 3, 4, 5, 6, 8. He rolls both and adds their values. Is there any difference in how their sums are distributed?

    This question is equivalent to asking whether the following two subroutines induce the same output distribution:

    $\subname{alice}(\,)$:

    $r \gets \{1,2,3,4,5,6\}$

    $s \gets \{1,2,3,4,5,6\}$

    return $r+s$

    $\subname{bob}(\,)$:

    $r \gets \{1,2,2,3,3,4\}$

    $s \gets \{1,3,4,5,6,8\}$

    return $r+s$

    The notation “$r \gets \{1,2,2,3,3,4\}$” means that the outcomes 1 and 4 happen each with probability $\nicefrac{1}{6}$, but the outcomes 2 and 3 happen each with probability $\nicefrac{2}{6}$.

12. In the OTP attack scenario, the adversary cannot make the choice of $\ptxt$ depend on $\key$. Are encryptions of $\ptxt=\key$ uniformly distributed?

13. Keys should not be reused in OTP. Is there a similar restriction about reusing plaintexts, if they are encrypted with independently chosen keys? Explain how to make sense of your answer in light of the formal attack scenario involving the attack subroutine.

14. Show that if $\key = (\ctxt - \ptxt) \pct \nmod$ then $(\key + \ptxt) \pct \nmod = \ctxt$.

15. Consider a variant of OTP in which keys, plaintexts, and ciphertexts are from the set $\{1, \ldots, n-1\}$, and encryption is defined by multiplication mod $\nmod$. (We exclude 0 because it doesn't play well with multiplication.) Update the formal attack scenario to reflect this change.

    1. Does the adversary still see uniformly distributed output when $\nmod=5$?

    2. Does the adversary still see uniformly distributed output when $\nmod=6$?

    3. What is the pattern? Which values of $\nmod$ will work, and why?

16. The xor operation can be thought of as addition mod 2 in every bit. Consider a variant of OTP where encryption is defined by addition over the integers in every bit. If we write this operation as $A \boxplus B$, then $\bit{0011} \boxplus \bit{0101} = \bit{0112}$. The result of this operation may contain $\bit{0}$s, $\bit{1}$s, and $\bit{2}$s. Update the formal attack scenario to reflect this change. Does the adversary still see uniformly distributed output?

17. Write the decryption algorithm that corresponds to encryption algorithm $\Enc(\key,\ptxt) = (\key+\ptxt) \pct \nmod$.

18. You have been asked to audit some software, in which you find a reasonable implementation of OTP encryption with just one unexpected property: Instead of xor, encryption is performed with unsigned addition of 64-bit integers. The plaintexts, ciphertexts, and keys are all 64-bit strings.

    1. What will you look for in the implementation of OTP decryption?

    2. What are the security implications of replacing xor with unsigned integer addition?

Chapter Notes

Alice and Bob made their first appearance as cryptographic protagonists in the seminal 1978 “RSA” paper of Rivest, Shamir, and Adelman [189]. They (Alice and Bob) have become obligatory rhetorical devices in cryptography research papers ever since. According to tradition, Alice's preferred pronouns are she/her and Bob's are he/him, conveniently allowing us to refer to them unambiguously using gendered English pronouns. Eve (she/her) the eavesdropper made her first appearance in the 1988 paper of Bennet, Brassard, and Robert [33].

Auguste Kerckhoffs published his cryptographic design guidelines, La Cryptographie Militaire, in 1883 [132]. He described six design principles, the second of which is now commonly called Kerckhoffs's principle. A biography of Kerckhoffs can be found in [62].

One-time pad is also known as Vernam's cipher, after Gilbert Vernam, a telegraph engineer who patented the method in 1919 [215]. However, there is evidence that OTP was (independently) invented by Frank Miller in 1882 [32].

What I'm calling Kissner's maxim is from a keynote presentation at the 2018 IACR Crypto conference by Lea Kissner, who at the time was lead of privacy technology at Google. The video can be found at https://youtu.be/pw8-6LUlIJY?t=2531.

Exercise 1.4 modifies OTP so that a plaintext never encrypts to itself. The German Enigma machine, used in World War II, encrypted text one character at a time, but would never encrypt a character to itself. This is one of the flaws in Enigma that allowed the Allies to break it.

The special six-sided dice from exercise 1.11 are called Sicherman dice, after their discoverer George Sicherman [55,105].

1. Next Chapter2. Rudiments of Provable Security