From dawagner@tucson.princeton.edu Tue Jan 24 21:02:12 EST 1995
Article: 31926 of sci.crypt
Newsgroups: sci.crypt
Path: princeton!tucson.princeton.edu!dawagner
From: dawagner@tucson.princeton.edu (David A. Wagner)
Subject: Re: Name and Crack this scheme
Message-ID: <1995Jan25.013944.13052@Princeton.EDU>
Originator: news@hedgehog.Princeton.EDU
Sender: news@Princeton.EDU (USENET News System)
Nntp-Posting-Host: tucson.princeton.edu
Organization: Princeton University
References: <3g37ll$sdv@tuegate.tue.nl>
Date: Wed, 25 Jan 1995 01:39:44 GMT
Lines: 57
I tried to respond by email, but your news posting software
appears to be broken:
> From: Jacco Compier
In article <3g37ll$sdv@tuegate.tue.nl>, wrote:
> I stumbled upon the following decryption scheme:
>
> {$Q- Overflow checking off }
> MULX := $8CB785;
> MULY := $2D490D;
> ADDX := $3584B9;
> ADDY := $0CF639;
> for I:=0 to N do
> begin
> B := Data[I];
> Data[I] := B xor (KeyX shr 16) xor (KeyY shr 16);
> KeyX := ((KeyX+B)*MULX+ADDX) and $FFFFFF;
> KeyY := ((KeyY+B)*MULY+ADDY) and $FFFFFF;
> end;
>
> Where KeyX and KeyY are two 24 bit secret keys
> and Data[0..N] contains the encrypted bytes.
This scheme is a stream cipher based on a combination of two
linear congruential generators, and I believe it is very weak.
Here's a simple brute-force-ish attack which takes complexity
something on the order of 2^24 and requires n known plaintexts,
where n is (probably) on the order of a dozen or so:
1. Try each possible initial value of the 24-bit KeyX register.
2. Given any one initial value of KeyX, we can find the value
of the expression (KeyY shr 16) at each of the first n-3
character positions.
3. Given the values of (KeyY shr 16) at each of those n-3
positions, we can discover the initial value of KeyY, and
so we can check the last 3 known plaintext positions to
see if our guess at the initial values (KeyX, KeyY) is correct.
Step 2 is really easy. I think Step 3 is described in the
following paper (though I haven't read it myself):
Boyar, J. ``Inferring Sequences Produced by a Linear Congruential
Generator Missing Low-Order Bits.'' Journal of Cryptology.
vol. 1, num. 3, 1989, pp. 177--184.
There are probably more sophisticated and more efficient
attacks out there [for example, there's a meet-in-the-middle
attack which doesn't require you to use Boyar's technique,
but *does* require O(2^24) space].
Still, this one attack oughta be enough to convince you that
the cipher you described is hopelessly weak.
-------------------------------------------------------------------------------
David Wagner dawagner@princeton.edu