>From: "Travis H." <[EMAIL PROTECTED]> >Sent: Jan 26, 2006 6:30 AM >To: cryptography@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 [EMAIL PROTECTED]