From: Nickey MacDonald <i6t4@jupiter.sun.csd.unb.ca>
Date: Thu, 29 Apr 93 05:22:23 PDT
To: cypherpunks list <cypherpunks@toad.com>
Subject: A link encryption protocol to crytique ;-)
Message-ID: <Pine.3.05.9304290914.A8389-d100000@jupiter>
MIME-Version: 1.0
Content-Type: text/plain


Okay folx, tear this apart...  I running on little sleep, but after
thinking about this for a couple of hours (mostly while trying to document
it...) I can't see any obvious holes...

If no one points out any significant deterrants, I will code this up in C
and release the code to the public domain (I'll get it put on soda...)

I should comment, that this is not meant to be the best link encryption
protocol available...  the NSA (or others of their TLA friends) can
monitor my sessions if they really want to...  but this should at least
provide a minor stumbling block...

Also, I'm not a math major, so my version of a "technical" description of
how to do this may upset the mathematicians among us... I did it the way
it is cause it seem straight forward that way...  I hope it actually makes
sense to someone besides me...  I hope it is general enuff (while writing
this I had fixed values in mind, like 256 byte packets, so I may have let
some of the constants creep in without noticing...   I hope not, please
point out these things)...

Anyway, here it is, for whatever its worth...  Oh, for irony's sake, I
must admit that it was all the "clipper" discussion that got me thinking,
and the use of I1 & I2 reflect this...  hehehehe!


--- Cut here ---

Protocol proposal for a peer to peer encrypted link
---------------------------------------------------


The goal of this algorithm was to be fast and not easily subject to a known
plaintext attack, as the data bytes in B[] will be highly structured.

x^y=the result of x exclusive ORed with y
v[x..y]=a vector with positions indexed from x up to y (inclusive)
v[i]=index into an an vector v for position i
v[]=the list of all values in vector v
CRC(v[])=caculate a CRC checksum on the data bytes in vector v

N=number of user data bytes per packet
D=N+sizeof(CRC(B[]))  (for ease in generating I, should be a power of 2)
S=D+sizeof(I)*2
B[0..N-1]=the N user data bytes
C[0..D-1]=a work buffer filled from B[], CRC(B[])
P[0..S-1]=the outgoing packet

K1 & K2=two random "session" keys of length P

I=packet rearrange index (range of 0 up to D-1)
I1 & I2=the two generators of I (range of 0 up to D-1)
T[0..(2^sizeof(I))-1]=array of vectors of size D
L=number of times to iterate the shuffle function

total size of data        D=N              +
                            sizeof(CRC(B[]))

total size of each packet S=sizeof(I)*2    +
                            N              +
                            sizeof(CRC(B[]))

Exchanged in advance of any packets being sent (by a public key mechanism
for example) are N, sizeof(I), sizeof(CRC(B[])), K1, K2, T.

K1 and K2 are generated randomly, but checked to insure that K1[i] does not
equal K2[i].

T[i] is generated by a pseudo random process, similar to shuffling a deck of
cards.  For each i, fill the vector with the values 0 to D-1.  Then two random
indexes (j & k) are chosen (to be different) and the two values at
T[i,j] and T[i,k] are swapped.  This can be iterated an arbitraty number of
times (L) to ensure a good "shuffle" of the values.


To encrypt each packet P:
   - Generate a random index (I) by generating two random values for
     I1 and I2 and exclusive OR'ing them together.  I is not transmitted
     as part of the packet
   - Copy the values in B[i] to C[T[I,i]] for all values of i=0 up to N-1.
   - Copy the individual bytes from CRC(B[]) into C by indexing T[I,x]
     for x=N up to D-1.
   - Form the packet:  P[0..D-1]=C[], P[D..D+sizeof(I)-1]=I1,
     P[D+sizeof(I)..S-1]=I2
   - Replace each value of P[i] with P[i]^K1[i]^K2[i] for all values of
     i=0..S-1.
   - Transmit P[i] for all values i=S-1 down to 0.

Explanatory comments:
   - Exclusive OR was chosen beacuse it executes so quickly on most machines.
   - The asumption was that just using a single key K1 would not be strong
     enough, so thus there are two.
   - Sending I as I1 and I2 gives more appranent choices of values, without
     requiring T to be extremely large.  This is in hopes of further
     hindering any known plaintext attacks.
   - P is transmitted backwards merely so that I1 & I2 arrive first, to aide
     the decryption process.  (Quite honestly this was done to make the
     above description of the assemblage of P a little easier to write,
     as putting I1 & I2 in first would have meant more calculation to yield
     the offsets of the sub parts of P  eg. "P[0..D-1]=C[] would have become
     "P[sizeof(I)..sizeof(I)+D-1]=C[]" which is not as easily understood.)


To decrypt each packet P:
   - As each byte comes in, it is stored into P[i] for values of
     i=S-1 down to 0.
   - Replace each value of P[i] with P[i]^K1[i]^K2[i] for all values of
     i=0..S-1.
   - I1=P[D..D+sizeof(I)-1]=I1, I2=P[D+sizeof(I)..S-1].
   - I=I1^I2.
   - C[]=P[0..D-1]=C[].
   - Copy the values in C[T[I,i]] to B[i] for all values of i=0 up to N-1.
   - Verify that CRC(B[]) equals C indexed T[I,x] for x=N up to D-1.
   - If the CRC verifies, the the data values have been transmitted and
     reside in B[] to be used.

--- Cut here ---

{ God I hope I don't look like too much of a fool...  ;-) }

---
Nick MacDonald               | NMD on IRC
i6t4@jupiter.sun.csd.unb.ca  | PGP 2.1 Public key available via finger