Re: random numbers reverse-engineering

[Bill Stewart <stewarts@ix.netcom.com>]

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!