From dawagner@tucson.princeton.edu Sat Dec 3 00:45:40 EST 1994 Article: 30781 of sci.crypt Newsgroups: sci.crypt Path: princeton!tucson.princeton.edu!dawagner From: dawagner@tucson.princeton.edu (David A. Wagner) Subject: Cryptanalyzing Colston's stream cipher Message-ID: <1994Dec3.053023.14542@Princeton.EDU> Summary: There's a good reason why crypto experts use tried-and-true ciphers. Originator: news@hedgehog.Princeton.EDU Sender: news@Princeton.EDU (USENET News System) Nntp-Posting-Host: tucson.princeton.edu Organization: Princeton University Date: Sat, 3 Dec 1994 05:30:23 GMT Lines: 92 Recently David Colston posted assembly code source to a single-key stream cipher he designed. I don't know if anyone looked at it (I know the assembly code was almost enough to frighten me away), but I'll try to summarize his algorithm, and then try to cryptanalyze it. I hope if I misunderstood the algorithm he'll correct me. The internal state is a 98-byte lookup table T[1..98] and four counters R1, ..., R4 stepping through the table. The original value of T[] is the secret key, and the original values of R1, ..., R4 is publicly known. To obtain a pseudo random byte, he uses the following algorithm: 1. T[R2--] += T[R1--]. 2. If R1 == 0, R1 = 98. If R2 == 0, R2 = 98. 3. X = T[R3--] + T[R4--]. 4. If R3 == 0, R3 = 97. If R4 == 0, R4 = 97. 5. Return X. The pseudo random byte gets used as you would expect: it is XORed with the plaintext to obtain the ciphertext. Let's let K_1, ..., K_98 be the original value of the T[] array -- i.e., the key. Note that we can express the output of the algorithm very simply in terms of (K_i). [for the sake of illustration, I'll assume initially R1=98, R2=11, R3=97, R4=34, as recommended in the source] X_1 = K_97 + K_34 X_2 = K_96 + K_33 X_3 = K_95 + K_32 ... X_23 = K_75 + K_12 X_24 = K_74 + K_11 + K_98 X_25 = K_73 + K_10 + K_97 ... and so on. If we let P_i and C_i be the i-th plaintext and ciphertext bytes, then C_i = P_i XOR X_i. Using a known plaintext attack, we can find the values of X_i. Now the key observation is that we can form a column vector (X_i) and a column vector (K_i); moreover we can easily write down the matrix (M_ij) which relates those two vectors according to (X_i) = (M_ij) (K_i). The matrix (M_ij) would look something like 0 ... 0 0 0 0 ... 0 0 0 1 0 ... 0 0 0 0 ... 0 0 0 1 0 0 ... 0 0 0 0 ... 0 0 1 0 0 ... 0 0 0 0 ... 0 0 1 0 0 0 ... 0 0 0 0 ... 0 1 0 0 0 ... 0 0 0 0 ... 0 1 0 0 0 : : : : : : : : : : : : : : : : : : : 0 ... 0 0 0 1 ... 0 0 0 0 0 ... 0 0 1 0 ... 0 0 0 0 0 0 ... 0 0 1 0 ... 0 0 0 0 0 ... 0 1 0 0 ... 0 0 0 0 1 0 ... 0 1 0 0 ... 0 0 0 0 0 ... 1 0 0 0 ... 0 0 0 1 0 : : : : : : : : : : : : : : : : : : : [i.e., M_{1}{97} = M_{1}{34} = 1, etc.] I know that's an ugly ascii picture, but I hope you can see the two diagonals, and then a third one forming. If we take a 98x98 matrix, there should be at most four diagonals formed. This matrix should be of very nearly full rank (though I haven't proved it yet). By taking a slightly bigger (say 105x105) matrix and by using a bit of known plaintext (say 105 bytes) to determine the (X_i) value, one should be able to compute the (K_i) vector through standard linear algebra techniques. Thus, I think this private-key stream cipher is very weak because it's too linear. Anyone comments or criticisms of my attempted cryptanalysis? Oh, one more thing I forgot to mention: David Colston suggests perturbing the T[] table after every 128 bytes (or so) of output -- he wrote a small routine that does some little diddling based on one byte, and this small routine would be called with one byte of input after every 128 bytes of pseudo random ouput. [God only knows how this one byte is calculated or sent to the receiver.] This shouldn't affect any attacks: every 128 bytes, the attacker can exhaustively search through all possible values of the diddling-byte (there are only 256 possible values, after all! :-) and quickly find the correct value. ------------------------------------------------------------------------------- David Wagner dawagner@princeton.edu