thoughts on one time pads

[bear]

On Thu, 26 Jan 2006, Travis H. wrote:

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

It's far easier and less error-prone to hand them a CD-ROM
full of symmetric keys indexed by date.

The problem is that most people will not take the care needed
to properly use a one-time pad.  For text communications like
this forum, they're great, and a (relatively) small amount of
keying material, as you suggest, will last for many years.

But modern applications are concerned with communicating *DATA*,
not original text; someone on the system is going to want to
send their buddy a 30-minute video of the professor explaining
a sticky point to the class, and where is your keying material
going then?  He wants to be ignorant of the details of the
cryptosystem; he just hits "secure send" and waits for magic
to happen.  Or if not a 30-minute video, then the last six
months of account records for the west coast division of the
company, or a nicely formatted document in a word processor
format that uses up a megabyte or two per page, or ...
whatever.  The OTP is nice for just plain text, but the more
bits a format consumes, the less useful it becomes.  And
fewer and fewer people even understand how much or how
little bandwidth something is; they think in terms of "human
bandwidth", the number of seconds or minutes of attention
required to read or listen to or watch something.

An OTP, as far as I'm concerned, makes a really good system,
but you have to respect its limits.  One of those limits is
a low-bandwidth medium like text-only messages, and in the
modern world that qualifies as "specialized."

Given a low-bandwidth medium, and indexing keying material
into daily chunks to prevent a system failure from resulting
in pad reuse, you get 600 MB on a CD-ROM.  Say you want a
century of secure communications, so you divide it into 8-
kilobyte chunks -- each day you can send 8 kilobytes and
he can send 8 kilobytes.  (Note that DVD-ROMs are better).

That gives you a little over 100 years (read, "all you're likely
to need, barring catastrophic medical advances,") of a very
secure low-bandwidth channel.

Of course, the obvious application for this OTP material,
other than text messaging itself, is to use it for key
distribution.

				Bear















>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
>
>

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

----- End forwarded message -----
--
Eugen* Leitl <a href="http://leitl.org">leitl</a> http://leitl.org
______________________________________________________________
ICBM: 48.07100, 11.36820            http://www.ativel.com
8B29F6BE: 099D 78BA 2FD3 B014 B08A  7779 75B0 2443 8B29 F6BE

[demime 1.01d removed an attachment of type application/pgp-signature which had a name of signature.asc]