One-Time Pad

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 $m$ and key $k$ are represented as bits (i.e. sequences of $0$ and $1$).

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

Given that the inverse of XOR is XOR itself, we can XOR the ciphertext $c$ with the key $k$ to recover the plaintext message $m$.

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 $k$ that’s used for encryption and decryption needs to have the exact same length as the plaintext message $m$.

Key Exchange

The key $k$ 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 $k$ must never be re-used.

Perfect Randomness

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

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 $k$ 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 $k$ 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 $k$.

However, let’s assume that Alice won’t rotate the key $k$ 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.

In the second example we assume that an eavesdropper passively observes two ciphertexts $c_1$ and $c_2$ that were both encrypted using the same key $k$.

The attacker can then XOR both ciphertexts to get access to the result of the XORed plaintexts $p_1$ and $p_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).

Imperfect Randomness

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

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 $c$ that she obtained by using the One-Time Pad to encrypt her plaintext message $p$ with a key $k$ that has the exact same length as the plaintext message $p$ and was never used before. Furthermore the bits in the key $k$ were obtained by sampling them from a uniform distribution which ensures perfect randomness.

We were able to get access to the ciphertext $01$. 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).

As we can see, every possible plaintext $p$ ($00$, $01$, $10$ and $11$) 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.

References

The following resources have been invaluable for me to learn the concepts discussed in this article.

You should definitely give them a read if you want to dive deeper into the topic.

• Wikipedia - One-Time Pad
• Why Are One-Time Pads Perfectly Secure?
• Wikipedia - Information-Theoretic Security
• Cryptography Stack Exchange - Simply put, what does “perfect secrecy” mean?
• Information Security - Stack Exchange
• YouTube - Cryptography, Perfect Secrecy and One Time Pads | Two Minute Papers #25