thoughts on one time pads

Jack Lloyd lloyd at randombit.net
Thu Jan 26 14:24:30 EST 2006


On Thu, Jan 26, 2006 at 05:30:36AM -0600, Travis H. wrote:

[...]
> 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.
[...]
> 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?

Your use case above suggests that you are still willing to trust conventional
ciphers to be secure, so, practically speaking, what is the difference between:

Key #1: 128 bits of one time pad
Key #2: AES_{masterkey}(counter++)

I'm not an "expert", but the reason I'd call it a bad idea (versus just not
worth the effort, which is all the AES/OTP comparison is suggesting) is it
introduces a need for synchronization, and that can be a hard thing to do
between arbitrary parties on a network.

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

I don't think attacks are the problem, so much as susceptibility to errors. To
even get started, you need a CD of truly random bits, which is fairly
non-trival to do on many platforms (and it's difficult to tests if your bits
are actaully random or just look that way). More importantly, the key
management issues seem annoying and highly prone to catastrophic failure. For
example, I send you a message using the first N bits of the pad, my machine
crashes, I restore from backup (or a filesystem checkpoint), and then my index
into the pad is reset back to the start. Then I resend a second message using
the same pad bits. Problem.

I think your characterization of the possible attacks is pretty fair. But
compare the OTP failure mode "access to it would compromise past and future
communications", to the failure mode of, say, RSA authenticated DH key
exchange, which provides PFS and requires an active attack in order to attack
communications even after the key is compromised. Is OTP so much more secure
than a simple PK-based key exchange that it is worth even this single tradeoff
(not to mention the initial key exchange hassles and the need to store
megabytes of pad with anyone I might want to talk to)?

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

That sounds prone to a man in the middle attack; what is to stop someone from
taking your authentication packet with the N bits of unguessable pad, cause
your connection to drop and then authenticating as you using the pad you sent
earlier?

You could probably do a challenge-response authentication based on pad bits
pretty easily, however, though doing it in a way that doesn't require a secure
hash might be a little trickier.

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

There are some attacks against WEP along those lines (they used RC4 to encrypt
the checksum, instead of a one time pad, but it would end up about the same, I
would think). Using HMAC keyed with pad bits seems a lot more sane to me...

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

I think that this question needs to be asked at all points to one of the flaws
of OTP from a practical standpoint.

-Jack

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



More information about the cryptography mailing list