[Cryptography] One-time pads in modern crypto software?

[Jerry Leichter]

> Should we design it so that purported traffic must
> contain a random challenge that will cause the recipient to NOT consume
> any of their local pad if it doesn't match?  How is THAT challenge
> secured without using vulnerable algorithms?  How do we manage to keep
> the pads on both sides of a long-term (months) intermittent connection
> in sync?  How do we absolutely prevent any portion of the pad from being
> re-used ever (c.f. Venona)?  Etc.

There's room here for some new thinking, as we're changing underlying assumptions.  Here's a trial balloon for a way to use a one time pad for authentication:  Expand each bit of the plaintext into two bits.  The first it the actual plaintext bit; the second is the plaintext bit XOR'ed with the next bit of the one-time pad.  Encrypt afterwards with another one-time-pad stream.  Or do the authentication on the ciphertext - in this case, order shouldn't matter.

An attacker's chance of generating n bits that have the right pattern is 1/2^n unless he knows both plaintext and one time pad.

No hardness assumptions.  Quantum algorithms don't seem to help. (Am I missing something obvious?  This is a quick proposal without any detailed analysis.)  Note that this assumes that doubling the size of the authenticated ciphertext is acceptable and that one-time-pad bits are cheap.  Neither of these would have been at all reasonable assumptions 10 years ago.  Today, tomorrow ... maybe.

There's a fundamental question of whether the *recipient* has to consider the one time pad bits "used."  If this message was created out of whole cloth by the attacker, then no.  If the attacker modified the message, then yes, because the sender is the one that actually consumes bits of randomness.  But ... how can the recipient reliably determine this?  If he asks the sender, that message could be damaged, or the response could be damaged.  The receiver can certainly skip ahead in its one time pad - but how can the the sender ever reliably determine that it needs to do so?  This is where the design gets tricky.

                                                        -- Jerry