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>,  <Jacco Compier> 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