Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

I have seen from time to time questions about various OTP schemes and "OTP" (i.e. stream cipher) schemes. The most common OTP troubles appear to be:

  • How to extend size of previously generated key or how to generate key.
  • How to get key material securely to the recipient.

In electronic communication or storage encryption OTP appears scheme that is impossible to make work and if it works benefits are not clear. Requirement that the key needs to be the same size than input seems to be unbearable for many of modern use cases for encryption.

Is there any practice where OTP is useful in modern cryptography except:

  • As a component used on some proofs.
  • As a example ideal of encryption algorithm.

I.e.: Is it possible to base on OTP and provide the "information theoretic" strength to hashing (apparently not), authentication, etc.

share|improve this question
    
No, it's not really useful anywhere, I'm afraid, outside of the two scenarios you've listed. There's some research into information-theoretically secure constructions for other primitives (e.g. MACs), but that's not exactly involving one-time pads. –  Reid Oct 13 '13 at 20:09
1  
1  
@RickyDemer Thanks. Any more important uses? QKD qualifies, because it indeed is electronic communication and used in practice. –  user4982 Oct 13 '13 at 21:25
1  
Well, information-theoretically secure authentication is usually part of QKD, $\hspace{1.66 in}$ although you may have already realized that. $\:$ –  Ricky Demer Oct 13 '13 at 22:26
    
A good summary about one time pads was given by Schneier in 2002, and it is still valid: Cryptanalysis is well understood, so common encryption algorithms are fairly secure. On the other hand key management is hard, and REAL OTP has to be one-time and truly random... and there are no convenient solutions for this. –  tylo Oct 14 '13 at 14:22

2 Answers 2

up vote 1 down vote accepted

Surprisingly yes. One-time-pads are used in many "quantum encryption schemes." Typically these schemes are actually standard one-time-pad encryption with the key being distributed using Quantum Key Distribution(QKD). They are, theoretically unbreakable since there is no way to intercept the key thanks to quantum physics(in practice, there are some problems).

In theory, this is useful for highly sensitive messages that need to remain secure for ever no matter what breaks in known cryptographic primitives happen or what advances in computational power (particularly quantum computing) occur.

There are commercial QKD schemes, though I do not know how much they are actually used.

share|improve this answer
    
I was hoping there would be an answer more practical than "QKD" found to this question. This is because OTP shares lot of same premise with OTP: theoretically unbreakable, but in practice often is misimplemented. Nevertheless, I'll accept this answer, but Ricky Demer actually suggested this answer a long time ago. –  user4982 Oct 22 '13 at 20:03

The OTP is more a theoretical construction than a real world construction. The OTP suffers from three core problems:

  1. Key Generation.
  2. Key Distribution.
  3. Key Destruction.

Let's deal with each one in turn.

Key Generation

Key generation is surprisingly difficult. In order to get the full security proof for the OTP, you need to each bit to be independent of every other bit and for there to be no bias whatsoever in the output.

Now practically every hardware RNG you're going to get does not fufil this in practice. They almost always run the bits through a hash function or some sort of entropy extraction routine. However, these routines do not carry a security proof that they preserve the underlying independent non-bias nature of the bits passed to them.

It's quite possible that if you the entropy extraction routine over enough bits, that a very small bias would be observed. However, any such bias, no matter how small would destroy the OTP security proof.

So you need to design your own RNG using only de-biasing techniques that maintain the security proof. Worse, you need to build an RNG with no detectable bias whatsoever over gigabits of output.

Key Distribution

Key distribution is a pain because the key has to be as long as the message. This immediately raises the question of why bother with encryption if you already have a secure channel of transmitting the key. Even with this massive key you haven't authenticated the cipher-text! You need provisions for that too.

This limits the OTP to scenarios where you want to time-shift a secure channel. It works okay in scenarios like the following. If Alice lives in Hong Kong and Bob lives in New York, they can meet twice a year and exchange a gigabyte or two of pad and be on their way.

Even if you're using QKD you've just moved the problem elsewhere. The problem now moves from a key distribution problem to an engineering problem. You've got to make a QKD device that is 100% reliable, doesn't have any side channel attacks, and is not susceptible to induced errors. Such as slightly overpowering/underpowering device to get duplicate photons, shinning a laser at the device to subtly break it or some other error inducing attack.

You've got many of the same problems of hardware quality as you had with the PRG. Good luck with that!

Key Destruction

Once you've used the key you have to make sure it is properly destroyed in both places. This is again more tricky than it seems at first.

If you don't do this properly and you use the key-stream twice, you have no security at all. If the program that manages the pad for you suffers some sort of error and fails to delete the used portion of the pad then re-use becomes quite likely.

Worse, because the pad is the same length as the message there's quite a lot of key stream to leak. This can leak in a number of ways. Parts of the key stream might have been paged to disk, for example, during encryption/decryption process.

An attacker could then decipher parts of your ciphertext by simply XORing bytes from your recovered hard-drive against the ciphertext.

Conclusion

The reason that the OTP isn't really fielded is that despite its strong security proof, the practical considerations around it actually render it insecure.

This is actually quite common in cryptography. Things with strong security proofs tend to be unworkable.

For every section of my reply, there is a documented case where precisely the problem I've raised has led to OTP messages being compromised.

OTPs are really hard to use properly and are typically less secure overall than a conventional scheme.

Small secrets, by virtue of them being small, are less likely to be leaked, easier to generate, easier to destroy and easier to transmit. All of these properties make them more secure.

share|improve this answer
    
very good answer, thanks. Next time somebody asks about OTP it is good to add link to this answer. In my opinion, OTP and QKD are sometimes good ideas when transporting data that has been already protected using some other cryptographic means, but alone they easily fall victim to one of these problems. BTW, in key generation another practical problem is often speed, entropy collection process is usually slow. –  user4982 Oct 23 '13 at 14:11

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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