[Date Prev][Date Next][Thread Prev][Thread Next][Author Index][Date Index][Thread Index]

*To*: <us>, <amix>, <dspitzer>, <drexler>, <terry>*Subject*: We can do it! Efficient secret communications! (Another paper)*From*: Mark S. Miller <mark>*Date*: Fri, 9 Feb 90 15:42:16 PST

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

- Prev by Date:
**Re: "BackFollow", May it RIP.** - Next by Date:
**Weekly planning meeting, 2/6** - Previous by thread:
**Re: FromNess, ToNess, Weirdness** - Next by thread:
**Re: We can do it! Efficient secret communications! (Another paper)** - Index(es):