We can do it! Efficient secret communications! (Another paper)

[Mark S. Miller <mark>]

Excuse the random order of explanation.  I'm excited.

Abstract: Once you have a cyptographically secure one-way hash (such
as Snefru), then you can you use it to generate a cryptographically
secure deterministic sequence of pseudo-random numbers (CSDSOPRN).
Once you have a CSDSOPRN, and both parties have the same random seed,
you can use the random sequence as a one-time pad.  The Stanford
"alpha-to-the-xy" scheme enables both parties to start with the same
random seed without allowing any eavesdropper to know the seed (i.e.,
it solves the "key distribution problem").  Michael's scheme (the one
he submitted to CACM ages ago) for using a one-time pad also prevents
a potential spoofing problem that you'd have if the enemy knows the
message (the known plaintext attack) and you were using the standard
XOR way of doing a one time pad.  Put this all together, and we have a
complete crypto solution except for digital signatures.  I.e., we've
got public & private keys (alpha-to-the-x & x), and both secret and
authenticated communication.

The punch line is that this is all fast enough to do on every packet.
It should run at about the full data rate of Snefru (8 megabits per
second on a sun-4).  In response to the question "is this fast enough
for voice", I responded "it's fast enough for slow video".  (Actually,
I know the above to be true given XOR style one-time pads.  I don't
know what the performance of Michael's scheme is.  Michael?)

The new insight is simply that we can use Snefru to generate a
CSDSOPRN.  (I don't know if the insight that you can use a CSDSOPRN as
the base of a one-time pad is well known or not.  I heard it first
from Drexler.)  We can do this as follows:

You and me use the Stanford scheme to start from the same 512 bit
random seed.  We each Snefru hash this random seed, generating 256
bits of output, which are the first 256 bits of the one-time pad.  We
then add one to our random seed, rehash, and voila, the next 256 bits
of our one time pad.  And so on, adding one each time.

Altogether, we have an interesting composite of techniques here:

1) the Stanford alpha-to-the-xy scheme for key distribution 

2) Snefru, our cryptographic hash of choice

3) The new insight, turning Snefru into a CSDSOPRN.  I know now that
this should work.

4) Drexler's insight, that a CSDSOPRN can be used as a one-time pad

5) Michael's alternative to XOR for using one-time pads, that enables
the communication to be authentic as well as secret.


The only missing piece for a full crypto foundation is digital
signatures, and Merkle has already published a scheme (in his thesis)
for using a cryptographic hash for digital signatures.  This technique
can be applied to Snefru.


Appendicies:


  The Stanford Scheme:

I generate a large number X which is my private key.  I publish Alpha
to the X mod M ((a^X)%M), where Alpha and M are two large globally
well known numbers that have appropriate number theoretic properties
(e.g., they're relatively prime or something.  I forget).  You
generate a large random Y as your private key, and publish (a^Y)%M as
your public key.  Now we want to communicate using a single key cipher
(such as the above scheme), so we need to somehow end up with the same
key without anyone else being able to know that key.  I calculate
(((a^Y)%M)^X)%M which happens to equal (a^(X*Y))%M.  You calculate
(((a^X)%M)^Y)%M which happens to equal (a^(X*Y))%M.  An eavesdropper
only knows (a^X)%M and (a^Y)%M, from which it is computationally
infeasible for him to calculate anything.  X and Y may also both have
to be prime or something, but it isn't a big deal.


   CSDSOPRN:

A sequence of random numbers is sufficient for use as a one time pad
if, given the entire history of numbers output so far, an eavesdropper
has no ability to predict any future output (not even a statistical
ability).


   One Time Pad:

Old technique that I believe was actually used in the military.  Let's
say that you and I are currently in secure communication (we're both
back at base), but we anticipate needing to communicate later during
battle when there may be eavesdroppers.  What we do now is generate a
mag-tape full of good true random numbers (e.g., gotten from a noisy
diode xored with radioactive decay).  I duplicate the mag tape and
give you a copy.  Later, I need to send you a 100 bit message.  I chop
the first 100 bits off the mag tape and xor it with my message, and
through that bit of mag tape away.  When you receive my 100 bit
seemingly random message, you take the first 100 bits off your mag
tape, xor it with my message, and recover the original (a xor b xor b
== a).  You also throw away the first 100 bits of your mag tape.  The
amount of shared random bits we need to generate beforehand is
precisely the same as the maximum amount of data that we can
communicate securely.  If we every reuse any of the tape, we're
screwed.  Drexler's insight is that a CSDSOPRN is equivalent to an
infinite tape.


   Snefru Properties We Are Counting On:

1) It is computationally infeasible to ever find any two inputs that
hash to the same output.  This is the certral claim being made for
Snefru.  This directly implies:

2) Given a Snefru output, it is computationally infeasible to generate
a corresponding input.

3) Given any two inputs that differ in at least one bit, the
corresponding outputs will be uncorrelated according to any
computationally feasible statistical test which doesn't know the
inputs (but does know the relationship between them).

4) The Snefru output is random to any feasible test which doesn't know
the input.  I don't know if one of 3 or 4 implies the other.


   Michael's method of one-time padding

I'll let Michael describe his alternative to XOR, and why we need it.


   The Hardest Unsolved Problem:

We need to name this scheme.  Did the Pharoh Snefru have any children?
Or perhaps we should call it the Lewis Cypher (Robert DeNiro's role in
Angel Heart)?