thoughts on one time pads

[John Kelsey]

>From: "Travis H." <solinym at gmail.com>
>Sent: Jan 26, 2006 6:30 AM
>To: cryptography at metzdowd.com
>Subject: thoughts on one time pads

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

I think that's because you missed the point.  You're confusing manual
key distribution (which makes sense in some cases, but is unworkable
in others) with using a one-time pad (a specific method of encrypting
information that uses up key material very fast but has a security
proof).  

Manual key distribution means that I carry the key material to you by
hand.  This can be on a DVD or CD or tape or USB drive, or for that
matter on a piece of paper or punched card or cryptographic token.  

A one-time pad means that I take my key material, which must be
perfectly random for the proof to work, and XOR it with plaintext to
get ciphertext.  That can't possibly be cryptanalyzed, because there's
no information about the plaintext in the ciphertext, so long as the
key is unknown and random.  (Any plaintext could lead to any
ciphertext with equal probability.)   

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

You're talking about manual key distribution here.  This works the
same for both OTPs and conventional encryption.  The difference is
that managing the keys in a secure way is *much* easier when you're
doing conventional encryption.  The only advantage using a one-time
pad gives here is that you don't have to worry about cryptanalysis.

And one-time pad encryption can't be used with anything but manual key
distribution, or other methods that are at least as awkward (like
quantum key distribution).  You can't hand me a business card with
your PGP fingerprint on it and establish secure communications with me
using a one-time pad, but you can using PGP and conventional crypto.  

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

But then you're not using an OTP anymore.  And there's no need for a
station wagon full of DVDs, you can use a piece of paper with a
32-digit hex string on it to exchange the AES key, ugly though that
is to type in.  In fact, there are some procedures people have worked
out to do this.  But it doesn't scale well.  

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

Yep.  You've got to store the key material safely in transit and at
the endpoints either way, though, and that's much easier for 256 bit
AES keys (which can be put inside an off-the-shelf tamper-resistant
token), and easier still for hashes of public keys (which only have to
arrive unchanged--it doesn't matter if the bad guys learn the
hashes).  

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

Not to put too fine a point on it, it's because he's right and you're
wrong.  

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

You have to worry about securing the key material from cradle to
grave, and operationally makign sure you use the right key material
with the right person and never reuse it.  OTPs are terribly sensitive
to the randomness of your key material (if you screw up and use bits
biased 60/40 for your 128-bit AES key, you'll drop to 90+ bits of
security; if you do that for your OTP, you'll reveal quite a bit of
the normal ASCII text you send, because there's not very much entropy
per bit.).  

The issue of preventing reuse is enormous.  

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

If you dig around, Rivest wrote a paper at Crypto 82 or 83 about
randomizing encryption which is still pretty nice.  To a first
approximation, superencryption (encrypting the OTP-encrypted text with
AES-CBC or some such thing) is always okay.

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

There are provably secure authentication schemes that use much less
key material per message.  Google for universal hashing and IBC Hash,
and for provably secure authentication schemes.  I seem to recall that
Stinson has a really nice survey of this either webbed or in his
book.  (Anyone else remember?)  

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

Yep, you can flip bits, so long as you know the CRC polynomial.  If
the CRC polynomial is randomly chosen for each message, and used
correctly, you get one of those provably-secure authentication
schemes.  

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

Read The Friendly Literature.

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

--John Kelsey


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