The one-time pad (OTP) is a classic encryption method famous for achieving “perfect secrecy”. It works by XOR plaintext with a key that is
- truly random
- at least as long as the plaintext message
- used only once: reusing key can lead to vulnerabilities
The algorithm works like the following:
- Generating a random key
of the same length as the plaintext - Compute ciphertext
- To decrypt, compute
which leverages the property that XOR being its own inverse: .
Problems and Limitations
OTP is barely used in practice because of various limitations, including
- key generation: key must be genuinely random (not pseudo-random)
- key distribution: need a secure channel to share a key as big as the message
- key reuse: one must never reuse any part of the key as doing so destroys security
Key Distribution
If we have such a secure channel to share the key as big as the message, we can just use it to transmit the message instead. The whole point of cryptography is that such secure channel does not exist.
Key Reuse
As its name suggest, reusing key in one-time pad leaks information. 1 Consider two pieces of ciphertext encrypted using the same key
An attacker can then XOR the two ciphertext which cancels out the key and reveals information about the plaintext:
From there, the attacker can exploit this information via means such as frequency analysis.
Breaking of the VENONA project during the Cold War was a historical example of how key reuse in one-time pads lead to security failures.
Overcoming the Limitation
One can attempt to overcome the limitation of key length by using a shorter key but stretch it with a pseudorandom generator. This also solves the limitation on key reuse as we can derive multiple keys from the stretched key.