12
$\begingroup$

Occasionally I hear people say that one-time pads are "useless" or even "broken".

"modern cryptography knows more security definitions, under some of which the one-time pad is completely broken." -- How do we know a cryptographic primitive won't fail suddenly?

...

One time pad: why is it useless in practice?

...

"we don’t need (and shouldn’t want) to use one-time pads"

...

"The one-time pad is not a semantically secure encryption algorithm."

...

"One-time pads may be theoretically secure, but they are not secure in a practical sense." -- Bruce Schneier

What specifically are these "modern ... security definitions", and how exactly is the one-time pad completely broken?

Improve this question
$\endgroup$
8
  • 2
    $\begingroup$ I think he meant broken in the sense that it does not provide authenticity $\endgroup$
    – Richie Frame
    Commented Jun 5, 2015 at 1:47
  • 2
    $\begingroup$ @Bardi Hardborow: chacha20 as used e.g. in Chrome is a stream cipher (which keystream generator is generated by a CSPRNG, which is a PRF applied to a counter and a key); it is not an OTP, which keystream is true random, rather than derived from a key. $\endgroup$
    – fgrieu ♦
    Commented Jun 5, 2015 at 10:56
  • 1
    $\begingroup$ A onetime pad involves 3 components: plaintext, cyphertext, & keypad. Any party gets any two components, they can derive the third. In modern cryptography, we care about resisting attacks where an adversary has two of the components. Hence onetime pads are not applicable in most modern cryptographic attack scenarios. $\endgroup$
    – recursion.ninja
    Commented Jun 5, 2015 at 14:17
  • 1
    $\begingroup$ What? That's not even remotely correct. An attacker, even in a modern context, with the ciphertext and key can recover the plaintext. $\endgroup$
    – Stephen Touset
    Commented Jun 5, 2015 at 20:27
  • 1
    $\begingroup$ @StephenTouset I was obviously referencing weakness against the following: known-plaintext attack, chosen-plaintext attack, chosen-cyphertext attack, adaptive chosen-cyphertext. $\endgroup$
    – recursion.ninja
    Commented Jun 5, 2015 at 20:50

4 Answers 4

Reset to default
22
$\begingroup$

Modern security has moved beyond looking just at passive attacks (in which the attacker is just a passive eavesdropper seeking to learn what was said); attackers are generally considered to be able and willing to pull off active attacks of various types (in which the attacker can modify or forge messages to achieve some goal). One-time pads are extremely vulnerable to modification; if an attacker knows that a message says "Pay Robert \$100,000", they can trivially change it to "Pay Joseph \$999,999". They share this property with all stream ciphers; if your ciphertext is the plaintext XOR a keystream, then an attacker who knows $P_1$ and $C_1$ can easily compute $C_2=C_1\oplus (P_1\oplus P_2)$, which decrypts to $P_2$. Working around that requires some way to verify message authenticity, which a one-time pad doesn't do (and doesn't try to do). This is provided by message authentication codes (MACs), or by a cryptosystem that combines authentication and encryption (like AES-GCM).

Also, many security properties literally do not apply to OTPs, because the properties are along the lines of "given the ability to encrypt multiple messages with the key, do X."

Uselessness is broader: even if you just need confidentiality, OTPs have serious issues for usability. That's because a OTP key has to be as long as the message and transmitted in secret; cryptography is most useful when you just need to transmit a little information secretly to encrypt a lot of stuff. An OTP is only as secure as the key exchange, so to be useful the keys have to be exchanged without relying on cryptography for security (else you're not getting perfect security). There are a few cases where they work well (like distributing in person to someone who's about to go on a mission and will need to send stuff back to you over an insecure channel), but they're rare.

Improve this answer
$\endgroup$
19
  • $\begingroup$ They also reveal the length of the message, if used without padding. And when you use them with padding you run into all the issues that can cause. $\endgroup$
    – SAI Peregrinus
    Commented Jun 5, 2015 at 2:54
  • 2
    $\begingroup$ @fkraiem There is a logical contradiction within your statement. Remember, in OTP, the O and T stand for "One Time". If the stream is used to encrypt more than one message, it is by definition not an OTP. $\endgroup$
    – Erwan Legrand
    Commented Jun 5, 2015 at 8:13
  • 1
    $\begingroup$ @fkraiem In the case of OTPs, the keystream generation algorithm is as follows: take the key which sits on top of the stack or, if the stack is empty, fail hard. $\endgroup$
    – Erwan Legrand
    Commented Jun 5, 2015 at 9:07
  • 1
    $\begingroup$ @ErwanLegrand That's not how I would define it (and since there is probably no universally agreed upon definition, I guess this discussion is pointless). $\endgroup$
    – fkraiem
    Commented Jun 5, 2015 at 9:23
  • 1
    $\begingroup$ @Aron How do I send a message that I don't have yet? $\endgroup$
    – 8bittree
    Commented Feb 19, 2019 at 20:30
5
$\begingroup$

fkraiem's answer is correct, but more context is required, in my opinion.

The one-time pad (the theoretical device) has not been broken. But real-world systems based on the one-time pad have failed in practice.

Systems based on one-time pads have failed in the past because key material has been reused, either by mistake or because the sender had ran out of fresh key material.

Remember, with a one-time pad, the secret key needs to be as least as long as the message.

Thus, modern cryptosystems are designed so that this issue no longer happens. They use a short key and a nonce (https://en.wikipedia.org/wiki/Cryptographic_nonce) and in the case of stream ciphers generate a keystream which is as long as required.

Note that the same issues (running out of keystream or using the same keystream twice) could theoretically happen with a modern cryptosystem, if cycles are found within the key stream or all possible nonces have been used. (And in some cases, it does, because of implementation issues.) In order to prevent this, the nonce space is made large enough. The exhaustion of a 128 bit nonce space will not happen.

Improve this answer
$\endgroup$
1
  • 2
    $\begingroup$ +1 one time pad has been proven to be the most secure encryption scheme one can possibly achieved, but at the same time the most impractical solution to everyday security needs. $\endgroup$
    – user1589188
    Commented Jun 5, 2015 at 11:01
5
$\begingroup$

In a lot of cases OTP will be completely impractical. If instead of a truly random pad you use a pseudo random pad, you will have something a lot more practical. But it is no longer OTP, and the security proofs about OTP means nothing in that case. I think this is the essence of the Bruce Schneier quote you mention.

If we for a moment ignore the impractical aspect of it and assume a setting in which the communicating parties have shared a random key in advance, then why might OTP be considered broken?

First of all OTP is all about confidentiality. A lot of people when they first learn about cryptography think that confidentiality is the most important aspect of cryptography. But in most cases it isn't. Integrity is usually more important. In fact confidentiality without integrity is rarely useful.

So all that provable confidentiality of OTP is useless unless you have provable integrity to go along with it. Luckily Wegman and Carter showed how to do that many years ago. Just like OTP the MAC by Wegman and Carter consumes key bits every time it is used. But the good news is that the MAC only consumes a constant number of bits each time, so much fewer bits are used for the MAC than for OTP which uses as many key bits as the length of the message.

Making it somewhat practical

The combination of OTP and Wegman Carter MAC (or a derivative) is proven secure. But to make it practical one need a source for a long common secret bitstring. I have only ever heard about one way to produce such a key if it wasn't shared among the two parties in advance, and that is through quantum cryptography.

Quantum cryptography does however require an authenticated classical channel. So you cannot bootstrap quantum cryptography without first sharing some secret between the communicating parties. But if you have shared enough key bits for a Wegman Carter MAC, then you can use quantum cryptography to produce a longer shared key for further communication.

The key material produced by quantum cryptography can be used to exchange messages on a classical channel using OTP + Wegman Carter for security. One of course has to save enough bits for the MAC on another round of the quantum communication to refill the pool of key bits.

Improve this answer
$\endgroup$
0
$\begingroup$

Modern definitions of security require being able to securely encrypt a large number of messages with the same key, which is by definition not possible with a one-time pad.

Improve this answer
$\endgroup$
1
  • $\begingroup$ +1, although this deserves a longer explanation, in my opinion. (Hence my answer.) $\endgroup$
    – Erwan Legrand
    Commented Jun 5, 2015 at 8:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.