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

*To*: <amix>, <drexler>, <dspitzer>, <mark>, <terry>, <us>*Subject*: Re: We can do it! Efficient secret communications! (Another paper)*From*: Michael McClary <michael>*Date*: Fri, 9 Feb 90 23:53:27 PST

> I'll let Michael describe his alternative to XOR, and why we need it. Looks GREAT so far! (One caveat: Compromising the private key at EITHER end makes recorded traffic readable, as with the other non-transitive-authentication systems, such as DES. With RSA it only compromises traffic bound toward the compromised side.) I agree we should research Snefru's children. Especially if he had a recognized child with someone outside the pharonic line. B-) (I'm always itchy about pseudo-random generators, because if they ever figure out where you are in the sequence, you're screwed. On the other hand, if that ever becomes a concern, we could use some function of (a^(X*Y))%M, rather than 1, for the increment, and even if they achieve sync they're back to figuring out (a^(X*Y))%M on the next block.) (Yes, they used one-time-pad in wars. Real pads of paper. Shannon invented information theory for the military crypto effort in WWII, and proved one-time-pad is really unbreakable, so the pads are as strong as the random generator and the key distribution path, and perfect if true random noise used once and destroyed.) Why straight XOR one-time-pad isn't enough: If the bad guy can intercept and modify your transmission, and he knows what your are about to send, he can solve for your chunk of one-time-pad, and use that to replace the message with his bogus message. The GLOPS variant of one-time-pad: (I don't have the paper handy, so I'll just sketch it... and undobutedly use different letters than I used on the paper.) GLOPS is a small-block cypher. In this description, I'll use bytes (8-bit blocks), but the blocks can be any size, with the probabilities scaling accordingly. Rather than using one byte of one-time-pad to encrypt one byte of plaintext (via add or XOR), you use two bytes, and combine them with the plaintext using a system of arithmetic called a "gallois field". (Pronounced gah-WAH) A gallois field is any of a set of finite fields constructed from polynomial arithmetic as follows: - Numbers are sets of integer coefficients for a polynomial of degree N-1. - The coefficients range from zero to one less than some prime P. - Addition is polynomial addition, with the coefficients taken modulus P. - Multiplication is polynomial multiplication, with the coefficients taken modulus P and the entire polynomial taken modulus an irreducable polynomial I, which is of order N. It can be shown that, for any combination of P and N>0, there exists at least one irreducable polynomial I on which a gallois field can be constructed. Since the numbers in a gallois field are ordered N-tuples of integers from zero to P-1, and 2 is prime, at least one gallois field exists which exactly represents a binary word of any given number of bits. In a gallois field with P=2, addition and subtraction are XOR. Polynomial multiplication and division with coefficients modulus 2 are accomplished by XOR-and-shift operations analogous to the add/subtract-and-shift operations used for integer multiply and divide (think of it as binary arithmetic with the carry bits lost), and the two can be combined in a single loop. Thus the gallois P=2 multiply is roughly: MASK = 1<<N; /* In this case, N=8 */ k = multiplier; m = multiplicand; a = 0; for (j = N; --j > 0; { if ((a <<= 1) & MASK) { a ^= I; } }) { if ((m <<= 1) & MASK) { a ^= k; } } /* Result in a */ This is quite fast. (For 8 bits, though, you might just want to use a table, which would only be 64K long.) Divide is most easily accomplished by multiplying by an entry from a pre-computed table of multiplicative inverses. Similarly, since you only need one I for all time, you can find it in a few sec of brute-force search. Because gallois fields are FIELDS, all the interesting field properties (additive inverses, a zero, multiplicative inverses {except for the zero}, a one, commutativity, distributivity) apply. (Note that boolean logic is just the gallois field with P=2, N=1.) Now, to encrypt: + = gallois(P=2,N=8) addition (i.e. bitwise XOR) - = gallois(P=2,N=8) subtraction (i.e. bitwise XOR) * = gallois(P=2,N=8) multiplication (see above) / = gallois(P=2,N=8) division (from precomputed inverse table) Let T0 = First byte of your plaintext. Let K0 = the first byte from your one-time pad. (If it is zero, discard it and take the next byte, etc., until you get a byte that is not zero). Let K1 = the next byte from your one-time pad. (Zero is OK.) Calculate C0 = (T0 * K0) + K1. This is your cyphertext. Discard the "used" one-time-pad bytes and repeat as necessary. To decrypt: Calculate T0 = (C0 - K1) * inverse(K0). Because gallois arithmetic is a field, for any Tb != T0 Cb != C0, there exists exactly one combination of K0 { = (C0 - Cb) / (T0 - Tb)} and K1 { = (Cb*T0 - C0*Tb) / (T0 - Tb)} such that: C0 = (T0 * K0) + K1 and Cb = (Tb * K0) + K1. This means that the bad guy has the following choice: He can leave the byte unmodified, or he can substitute a bogus cyphertext byte (Cb) that corresponds to a random selection (Mb) among the other possible values for the message byte. He is thus reduced to a malicious noise generator. (The best he can do is chose the worst spot to inject his noise.) His knowlege that K0 != 0 corresponds exactly to his knowlege that he can leave the message unmodified. Using 8-bit blocks, you can encrypt single keystrokes. The bad guy's chance of making a desired change in one of them is 1/255, in two of them is 1/(255**2), and so on. michael s

- Prev by Date:
**Re: merged image.** - Next by Date:
**Re: merged image.** - Previous by thread:
**We can do it! Efficient secret communications! (Another paper)** - Next by thread:
**Weekly planning meeting, 2/6** - Index(es):