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