From: Bill Stewart <stewarts@ix.netcom.com>
Date: Thu, 18 Jul 1996 17:04:43 +0800
To: Jüri Kaljundi <jk@stallion.ee>
Subject: Re: random numbers reverse-engineering
Message-ID: <199607170739.AAA29679@cygnus.com>
MIME-Version: 1.0
Content-Type: text/plain


At 08:28 PM 7/15/96 +0300, Juri wrote:
>Is there somewhere where I could find more information on finding out RNG
>algorithms or reverse-engineering RNG's, once you have some quantity of
>random numbers generated by some RNG?
>
>For example a local bank is giving each customer a list with 600 one-time
>passwords (6-digit decimal numbers), and I believe they use the account
>number as (one of the) seeds for the RNG. Is there some program that I
>could use, together with the numbers and possible seed, to try to break
>the RNG?

If you have some guess about the algorithm being used, you can try it,
and if they've chosen a weak algorithm, you may be successful.

For instance, if they use a simple Linear Congruential Multiplicative PRNG,
        X[n+1] = ( a * X[n] + c ) mod m 
and if you've got a list of 600 one-time passwords, you can get a good
approximation to m by taking the largest password and looking for
prime numbers slightly higher than it.  You can then try solving
for a and c.

On the other hand, if the account number is large, and each X[n+1] is
the low-order 6 digits of Y'[n+1] = MD5(Y[n]) and Y[0] = account number,
then it'll be much harder to reverse-engineer.

#				Thanks;  Bill
# Bill Stewart +1-415-442-2215 stewarts@ix.netcom.com
# http://www.idiom.com/~wcs
#				Confuse Authority!