Skip to content

One-Time Pad

Table of contents

Open Table of contents

What it is

The One-Time Pad (OTP for short) also sometimes called the “Vernam Cipher” is a symmetric cipher that can be used to encrypt and decrypt arbitrary messages. When used properly it guarantees Information-Theoretic Security which means, that it’s proven to be unbreakable.

How it works

Note: We assume that the message mm and key kk are represented as bits (i.e. sequences of 00 and 11).

To use the One-Time Pad to encrypt a message mm, one first has to generate a key kk of length mm that consists of bits sampled uniformly at random. Next up, the XOR function (\oplus) is used to combine the plaintext message pp with the key kk which produces the ciphertext cc.

c=pkc = p \oplus k

Given that the inverse of XOR is XOR itself, we can XOR the ciphertext cc with the key kk to recover the plaintext message mm.

p=ckp=pkkp=pkkp=p\begin{aligned} p &= c \oplus k \\ p &= p \oplus k \oplus k \\ p &= p \oplus \cancel{k} \oplus \cancel{k} \\ p &= p \end{aligned}

That’s it. That’s how the One-Time Pad can be used to encrypt and decrypt messages.

However there are a few things to keep in mind when it comes to proper usage. These requirements also render the One-Time Pad highly impractical for real-world usage.

Security Requirements

The One-Time Pad looks deceptively simple as there are a few very important requirements that need to be met in order for it to be secure. The One-Time Pad can be broken easily if only one of these requirements isn’t considered.

Key Length

The key kk that’s used for encryption and decryption needs to have the exact same length as the plaintext message mm.

Key Exchange

The key kk needs to be exchange out-of-bound, meaning that a separate, secure channel needs to be used for key exchange.

Single Key Usage

The key kk must never be re-used.

Perfect Randomness

The bits used to generate the key kk must be sampled from a uniform distribution, meaning that each bit at each position should have an exactly 50% chance of being 00 or 11.

How to break it

Let’s see how misuse of the One-Time Pad can be exploited and therefore the security guarantees be broken.

Key Reuse

Reusing the same key kk twice completely undermines the security of the One-Time Pad.

In the first example, we assume that Alice communicates with Bob and both of them got access to the key kk through a secure channel. Alice now encrypts a message for Bob which she can send to him to communicate securely as this is the first time she used the key kk.

cbob=pbobkc_{bob} = p_{bob} \oplus k

However, let’s assume that Alice won’t rotate the key kk and will re-use the same key for subsequent communications with Bob. Eve, our adversary can now very easily get access to the key by pretending to be Bob and asking for the next encrypted message. This type of attack is also known as a Chosen-Plaintext Attack.

Eve can then take the ciphertext she gets form Alice and XOR it with her plaintext to recover the key.

ceve=pevekk=pevecevek=pevepevekk=pevepevekk=k\begin{aligned} c_{eve} &= p_{eve} \oplus k \\ k &= p_{eve} \oplus c_{eve} \\ k &= p_{eve} \oplus p_{eve} \oplus k \\ k &= \cancel{p_{eve}} \oplus \cancel{p_{eve}} \oplus k \\ k &= k \end{aligned}

In the second example we assume that an eavesdropper passively observes two ciphertexts c1c_1 and c2c_2 that were both encrypted using the same key kk.

c1=p1kc2=p2kc_1 = p_1 \oplus k c_2 = p_2 \oplus k

The attacker can then XOR both ciphertexts to get access to the result of the XORed plaintexts p1p_1 and p2p_2. This information can then be used to decrypt the message if even a small part of the plaintext is guessable or known (e.g. when a header is always prepended to a message).

pxor=c1c2pxor=p1kp2kpxor=p1kp2kpxor=p1p2\begin{aligned} p_{xor} &= c_1 \oplus c_2 \\ p_{xor} &= p_1 \oplus k \oplus p_2 \oplus k \\ p_{xor} &= p_1 \oplus \cancel{k} \oplus p_2 \oplus \cancel{k} \\ p_{xor} &= p_1 \oplus p_2 \end{aligned}

Imperfect Randomness

The bits that are used to generate the key kk must be chosen with exactly 50% chance (i.e. there’s a 50% chance that the bit in question is a 00 or a 11).

If there’s a bias and certain bits are chosen more often than others, then this bias is carried through to the ciphertext during the XOR operation which can be exploited during Cryptanalysis to break the cipher.

Key Smaller than plaintext

If the key is smaller than the plaintext it needs to be repeated to make up for the length difference. Doing so will result in patterns which allows an attacker to rule out potential ciphertexts to be possible message encryptions.

Perfect Secrecy

As stated in the beginning, if used properly the One-Time Pad can’t be broken and provides Information-Theoretic Security. This property is oftentimes also called “perfect secrecy”. But why is that?

Let’s pretend that Alice has sent Bob a 2-bit ciphertext cc that she obtained by using the One-Time Pad to encrypt her plaintext message pp with a key kk that has the exact same length as the plaintext message pp and was never used before. Furthermore the bits in the key kk were obtained by sampling them from a uniform distribution which ensures perfect randomness.

We were able to get access to the ciphertext 0101. So what message did Alice sent?

Given the construction of the One-Time Pad, we know that the plaintext must have the same length as the ciphertext and the key, which is 2-bits in our case. Let’s create a table with all the possibilities (i.e. we’re deploying a brute-force key search).

ppkkc=pkc = p \oplus k
000000
000101
001010
001111
---------
010001
010100
011011
011110
---------
100010
100111
101000
101101
---------
110011
110110
111001
111100

As we can see, every possible plaintext pp (0000, 0101, 1010 and 1111) is equally likely to be the plaintext Alice encrypted and sent over as a ciphertext to Bob. We haven’t learned anything new and are defeated as given this, it’s impossible to recover the plaintext and therefore also impossible to break the One-Time Pad.

Additional Resources