thoughts on one time pads

[Travis H.]

In this article, Bruce Schneier argues against the practicality of a
one-time pad:

http://www.schneier.com/crypto-gram-0210.html#7

I take issue with some of the assumptions raised there.

For example, you may have occasional physical meetings with a good
friend, colleague, family member, or former co-worker.  Let's say you
see them once every few years, maybe at a conference or a wedding or a
funeral or some other occasion.  At such times, you could easily hand
them a CD-ROM or USB flash drive full of key material.  Then, you
could use that pad to encrypt messages to them until the next time you
meet.  Let's say you send them ten 1kB messages per year.  Then a $1
CD-ROM would hold enough data for 70000 years of communication!  Heck,
I could put the software on the image and make a dozen to keep with
me, handing them out to new acquaintances as a sort of preemptive
secure channel.

Bruce acknowleges this by saying "[t]he exceptions to this are
generally in specialized situations where simple key management is a
solvable problem and the security requirement is timeshifting."  He
then dismisses it by saying "[o]ne-time pads are useless for all but
very specialized applications, primarily historical and non-computer."

Excuse me?  This would in fact be a _perfect_ way to distribute key
material for _other_ cryptosystems, such as PGP, SSH, IPSec, openvpn,
gaim-encryption etc. etc.  You see, he's right in that the key
distribution problem is the hardest problem for most computer
cryptosystems.  So the OTP system I described here is the perfect
complement for those systems; it gives them a huge tug on their
bootstraps, gets them running on their own power.

I'm not sure it is even limited to this use case.  For example, before
a ship sets out to sea, you could load it up with enough key material
to last a few millenia.  How much key material could a courier carry? 
I bet it's a lot.  As they say, "never underestimate the bandwidth of
a station wagon full of tapes".  And don't embassies have diplomatic
pouches that get taken to them and such?

So my questions to you are:

1) Do you agree with my assessment?  If so, why has every crypto
expert I've seen poo-pooed the idea?

2) Assuming my use case, what kind of attacks should I worry about? 
For example, he might leave the CD sitting around somewhere before
putting it in his computer.  If it sits around on CD, physical access
to it would compromise past and future communications.  If he copies
it to flash or magnetic media, then destroys the CD, we can
incrementally destroy the pad as it is used, but we have to worry
about data remanence.

3) How should one combine OTP with another conventional encryption
method, so that if the pad is copied, we still have conventional
cipher protection?  In this manner, one could use the same system for
different use cases; one could, for example, mail the pad, or leave it
with a third party for the recipient to pick up, and you
opportunistically theoretical security if the opponent doesn't get it,
and you get empirical (conventional) security if they do.

4) For authentication, it is simple to get excellent results from an
OTP.  You simply send n bytes of the OTP, which an attacker has a
2^-8n chance in guessing.  How do we ensure message integrity?  Is it
enough to include a checksum that is encrypted with the pad?  Does it
depend on our method of encipherment?  Assuming the encipherment is
XOR, is a CRC sufficient, or can one flip bits in the message and CRC
field so as to cancel each other?  If so, how should we compute a MIC?
 Just SHA-1, and include that right after the plaintext (that is, we
encrypt the MIC so as to not reveal a preimage if SHA-1 is found to be
invertible)?

5) How should one decouple message lengths from plaintext lengths?

6) How should one detect and recover from lost, reordered, or partial messages?

All I've got to say is, I'm on this like stink on doo-doo.  Being the
thorough, methodical, paranoid person I am, I will be grateful for any
pointers to prior work and thinking in this area.  I recall Jim Choate
from the Austin cypherpunks saying he was working on a OTP system, but
never heard any more about it (let's not discuss him though please,
this thread is about one time pads).
--
"The generation of random numbers is too important to be left to chance."
  -- Robert R. Coveyou -><- http://www.lightconsulting.com/~travis/
GPG fingerprint: 50A1 15C5 A9DE 23B9 ED98 C93E 38E9 204A 94C2 641B

---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com