The rand() function in most C libraries is small and fast, but not particularly random. Below is a perl script that can take a few numbers from rand() and use them to predict the rest of the sequence, if rand() is a linear congruential generator of some sort. Actually, it isn't guaranteed to find the solution, but it usually does. It's based on the L3 lattice basis reduction algorithm. For more information, take a look at this introductory paper.
The script needs to know the parameters of your particular random number generator. I've included information for drand48() (which is the default in Linux) and the rand() function in ActiveState perl for Windows. It's generally not too hard to reverse engineer an unknown RNG by feeding chosen values into srand() and looking at the first couple of outputs.
$n is the number of random output bytes that are used to solve for the generator's internal state. With drand48(), it takes at least 7 bytes. That's just slightly inefficient in terms of information, since the internal state of the generator is 6 bytes long.
In order to run this, you'll need a recent version of Math::BigInt, Math::BigRat, and Math::BigInt::Pari or Math::BigInt::GMP. The running time increases as $n**6 (with a big multiplicative constant), so you'll need a reasonably fast BigInt library. On my machine, it takes 30-40 seconds with $n==7.
use strict;
use warnings;
use Math::BigInt lib => "Pari,GMP";
use Math::BigRat;
# Random number generator parameters
# $x = ($a*$x + $b) % $m
# These need to match the RNG your perl binary was compiled with.
# Run this one-liner and check to see if the output matches one
# of the signatures below.
# srand 1;@x=map int(256*rand),1..10;print "@x\n"
# drand48() -- the default on Linux
# Signature: 10 116 213 86 144 0 48 253 192 93
my $a = Math::BigInt->new("0x5DEECE66D");
my $b = Math::BigInt->new("0xB");
my $m = Math::BigInt->new(1) << 48;
my $n = 7; # number of input bytes needed
# ActiveState perl for windows
# Signature: 0 144 49 207 149 122 89 229 210 191
#my $a = Math::BigInt->new("0x343FD");
#my $b = Math::BigInt->new("0x269EC3");
#my $m = Math::BigInt->new(1) << 31;
#my $n = 4; # number of bytes needed
my $one_half = Math::BigRat->new("1/2");
my $three_fourths = Math::BigRat->new("3/4");
my @y = map int(256*rand), 1..$n;
print "rand = @y\n";
my @mat = map [(0) x ($n+1)], 0..$n;
my $k = $m >> 8;
$mat[0][0] = $k;
$mat[1][1] = 1;
foreach (2..$n) {
$mat[0][$_] = ($mat[0][$_-1] * $a + $b) % $m;
$mat[1][$_] = ($mat[1][$_-1] * $a) % $m;
$mat[$_][$_] = $m;
}
$mat[0][$_] -= $y[$_-1] * $k for 1..$n;
l3_reduce(\@mat);
CHECK: foreach my $row (@mat) {
if ($row->[0] < 0) { $_ = -$_ for @$row }
next CHECK unless $row->[0] == $k;
foreach (1..$n) {
next CHECK unless $row->[$_] >= 0 && $row->[$_] < $k;
}
my $x = $y[$n-1]*$k + $row->[$n];
my @p;
foreach (1..10) {
$x = ($a*$x + $b) % $m;
push @p, $x / $k;
}
print "prediction = @p\n";
}
my @z = map int(256*rand), 1..10;
print "rand = @z\n";
# l3 lattice basis reduction algorithm
# @$m is an array of lattice basis vectors
# $m is reduced in-place (the original is destroyed)
sub l3_reduce {
my ($m) = @_;
my $n = @$m;
my (@m2, @mag, @coeff);
foreach my $i (0..$n-1) {
my @v = map Math::BigRat->new($_), @{$m->[$i]};
foreach my $j (0..$i-1) {
my $w = $m2[$j];
my $c = dot_product(\@v, $w) / $mag[$j];
$coeff[$i][$j] = $c;
foreach my $k (0..$#v) {
$v[$k] -= $c * $w->[$k];
}
}
$m2[$i] = \@v;
$mag[$i] = dot_product(\@v, \@v);
}
undef @m2;
my $i = 1;
while ($i < $n) {
reduce_one($m, \@coeff, $i, $i-1);
my $u = $coeff[$i][$i-1];
my $u2 = $u*$u;
if (rcmp($mag[$i], ($three_fourths - $u2) * $mag[$i-1]) < 0) {
my $t = $mag[$i] + $u2*$mag[$i-1];
my $s = $mag[$i-1] / $t;
$mag[$i-1] = $t;
$mag[$i] *= $s;
$coeff[$i][$i-1] *= $s;
@$m[$i, $i-1] = @$m[$i-1, $i];
foreach my $j (0..$i-2) {
my $t = $coeff[$i][$j];
$coeff[$i][$j] = $coeff[$i-1][$j];
$coeff[$i-1][$j] = $t;
}
foreach my $j ($i+1..$n-1) {
my $t = $coeff[$j][$i];
$coeff[$j][$i] = $coeff[$j][$i-1] - $u*$t;
$coeff[$j][$i-1] = $t + $coeff[$i][$i-1]*$coeff[$j][$i];
}
$i-- if $i > 1;
}
else {
foreach my $j (reverse 0..$i-2) {
reduce_one($m, \@coeff, $i, $j);
}
$i++;
}
}
return $m;
} # l3_reduce
sub reduce_one {
my ($m, $coeff, $i, $j) = @_;
if (rcmp(abs($coeff->[$i][$j]), $one_half) > 0) {
my $c = $coeff->[$i][$j] + $one_half;
my $d = $c->numerator() / $c->denominator();
my $r = Math::BigRat->new($d);
if (rcmp($r, $c) > 0) {
--$d;
$r = Math::BigRat->new($d);
}
my ($u, $v) = @$m[$i, $j];
foreach my $k (0..$#$u) {
$u->[$k] -= $d * $v->[$k];
}
foreach my $k (0..$j-1) {
$coeff->[$i][$k] -= $r * $coeff->[$j][$k];
}
$coeff->[$i][$j] -= $r;
}
} # reduce_one
sub dot_product {
my ($x, $y) = @_;
my $sum = $x->[0] * $y->[0];
foreach my $i (1..$#$x) {
$sum += $x->[$i] * $y->[$i];
}
return $sum;
} # dot_product
# comparison not implemented in current Math::BigRat
sub rcmp {
my ($r, $s) = @_;
my $t = $r->numerator() * $s->denominator();
my $u = $s->numerator() * $r->denominator();
return $t->bcmp($u);
} # rcmp
|
Re: Predict Random Numbers
by johannz (Hermit) on Mar 14, 2002 at 13:36 UTC
|
<This did not run on my ActiveState Perl Install. I tried installing Math::BigInt and Math::BigRat via ppm, was only able to get Math::BigInt. And could not find the other modules, Math::BigInt::Pari or Math::BigInt::GMP.
Results for perl -v:
This is perl, v5.6.1 built for MSWin32-x86-multi-thread
(with 1 registered patch, see perl -V for more detail)
Copyright 1987-2001, Larry Wall
Binary build 626 provided by ActiveState Tool Corp. http://www.ActiveState.com
Built 01:31:15 May 2 2001
So, do you have ppd files for these modules or did you just build them yourself. I am assuming that these involve xs code?
Later...
So, it looks like Math::BigInt::Pari is a perl-only module, but requires Math::Pari, which is a c module and not available through PPM.
Math::BigInt::GMP is a c interface to another library and also is not available through PPM.
And Math::BigRat requires Math::BigFloat, which is in a later version of Math::BigInt than is on PPM.
So you have to get the latest Math::BigInt from CPAN, install it, install the latest Math::BigRat from CPAN, and then have a compiler so you can either install Math::BigInt::GMP, or the prerequisites for Math::BigInt::Pari.
Even more later...
So I installed Math::BigInt and Math::BigRat from CPAN. I did not install Math::BigInt::Pari or Math::BigInt::GMP but was able to run the code.
It hasn't finished, but it is running. :)
ps. I have a P3 500mhz, with 384M ram running Win2K. So we will see how it goes.
Update: He's right about needing a fast Math::BigInt library, the perl-only versions are too slow. It's been about 2 hrs and no results yet. | [reply] |
|
|
He's right about needing a fast Math::BigInt library, the perl-only versions are too slow. It's been about 2 hrs and no results yet.
If you want really fast code with which to manipulate large integers then I recommend getting Crandall's giants.c and giants.h C code from Perfectly Scientific. This code is used as a base library for the factorization of large composite numbers.
You will, of course, need a C compiler. If you want to actually hack the library you will need some patience as there is very little documentation and the code is very terse. Using the library functions though is relatively easy to do.
metadoktor
"The doktor is in."
| [reply] |
|
|
| [reply] |
|
|
|
|
quote:
Update: He's right about needing a fast Math::BigInt library, the perl-only versions are too slow. It's been about 2 hrs and no results yet.
You might also try and see if Math::BigInt::BitVect is available for Windows - although not as fast as GMP or Pari, they might speed it up ;)
Math::BigInt::Lite will make this hopefully a bit faster (since it is faster for small numbers), but it is not finished yet (see here)
Thanx for the fun, you guys rock ;)
If anybody wan't to chat to me about this, please drop me an email, I would love to ;)
Tels
| [reply] |
|
|
He's right about needing a fast Math::BigInt library, the perl-only versions are too slow. It's been about 2 hrs and no results yet.
Actually, it runs in about 10 minutes with the perl-only version on my machine. The problem is, there's a bug in some versions of the pure perl BigInt module, and the L3 algorithm isn't guaranteed to terminate in that situation. Try the latest version from
the author's web page.
| [reply] |
Re: Predict Random Numbers
by theorbtwo (Prior) on Mar 14, 2002 at 17:29 UTC
|
Looks very interesting; I'll probably play with it a little when I get home.
OTOH, it looked a lot more intersting before I read the code. I was wondering, how do you determinte the a, b, n, and m? Is it possible to write an algo to determinte them for an unknown RNG? Given only M (which seems to be 1<<number of bits of output)? Given nothing? Using srand()? Without changing the seed?
We are using here a powerful strategy of synthesis: wishful thinking. -- The Wizard Book
Update:Changed "N" to "M" in "given only N".
| [reply] |
|
|
For drand48(), the manpage tells you the constants a, b, and m. To get n (the number of outputs from int(rand*256) that are used), I used trial and error. There's a mathematical derivation of what values of n are likely to work in another paper, but that doesn't seem to be available online.
Determining a, b, and m using srand() can be automated in some cases, but it takes a bit of guesswork. If m is a power of 2 and b is small enough, you'll see an obvious pattern in the output of:
for (0..30) {
srand(1<<$_);
printf "%030b\n", rand()*(2**30);
}
You can work out a and take a guess at m and b from that -- a is the part that moves, b is the part that stays still, and m is whatever seems big enough to hold it all.
There are several papers (including the one I mentioned before) on determining those constants using only the output from rand(). Some of them use the L3 algorithm as well. | [reply]
[d/l] |
Re: Predict Random Numbers
by no_slogan (Deacon) on Oct 20, 2002 at 05:54 UTC
|
If you liked that, here's another way to discover the internal state of
a linear congruential pseudorandom number generator. It's only effective
when the internal state of the PRNG is small enough. As long as that's true,
it's fairly fast, since it doesn't need to use any BigInts.
This code is set up to use the same constants as the rand() function in
ActiveState Perl for Windows. It can be modified for other generators, but
there are some magic numbers that need to be tweaked. It takes four output
bytes from the PRNG, and comes up with a small number of possible seeds
(often just one). If that bothers you, give it a fifth byte to work with,
and that will narrow it down to one almost every time.
It works by looking at the first two output bytes from the PRNG, and
checking each of the roughly 2**15 seed values that would produce them.
This is one of the steps in the
cryptanalysis of the PKZIP cipher
by Biham and Kocher, which is implemented (though somewhat differently) in
pkcrack.
use strict;
use warnings;
use integer;
# PRNG parameters
my $m = 0x343fd;
my $b = 0x269ec3;
my $m1 = 0x39b33155; # multiplicative inverse of $m mod 2**31
# build the lookup tables
my (@diff_tbl, @prod_tbl);
for my $x (0 .. 0x2bc) { # 0x2bc is a magic number... see below
my $p = ($x * $m1) & 0x7fffffff;
my $e = ($p >> 22) & 0x1ff;
for ($e, ($e-1)&0x1ff, ($e-2)&0x1ff) {
push @{$diff_tbl[$_]}, $x;
push @{$prod_tbl[$_]}, $p;
}
}
# "Unknown" values: internal states of the PRNG
my $X0 = int(rand 2**31);
my $X1 = ($X0 * $m + $b) & 0x7fffffff;
my $X2 = ($X1 * $m + $b) & 0x7fffffff;
my $X3 = ($X2 * $m + $b) & 0x7fffffff;
# "Known" values: a few bytes of output from the PRNG
my $x0 = $X0 & 0x7f800000;
my $x1 = $X1 & 0x7f800000;
my $x2 = $X2 & 0x7f800000;
my $x3 = $X3 & 0x7f800000;
# find the lowest nonnegative $d such that
# $x0 == ((($x1 + $d - $b) * $m1) & 0x7f800000)
my $prev = (($x1 - $b) * $m1) & 0x7fffffff;
my $ent = (($x0 - $prev) >> 22) & 0x1ff;
my ($d, $p);
for (0 .. $#{$prod_tbl[$ent]}) {
$p = $prev + $prod_tbl[$ent][$_];
if (($p & 0x7f800000) == $x0) { $d = $diff_tbl[$ent][$_]; last }
}
die "can't happen\n" unless defined $d;
$p &= 0x7fffff;
my $q = ($x1 + $d) * $m + $b;
# modest (about 2**15 steps) brute-force search for the right $d
while ($d < 0x800000) {
# invariant: $p == ((($x1 + $d - $b) * $m1) & 0x7fffff)
# invariant: $q == ($x1 + $d) * $m + $b
# is this a solution?
if (($q & 0x7f800000) == $x2) {
my $r = $q * $m + $b;
if (($r & 0x7f800000) == $x3) {
printf "guessed x0 = %08x\n", (($x1 + $d - $b) * $m1) & 0x7fffff
+ff;
}
}
# find the next admissible value of $d
# there is much magic here... see below for a hint
if ($p < 0x67ceeb) { $d += 0x0c1; $p += 0x183115; $q += 0x27641b
+d }
elsif ($p >= 0x6a1b54) { $d += 0x1fc; $p -= 0x6a1b54; $q += 0x67aea0
+c }
else { $d += 0x2bd; $p -= 0x51ea3f; $q += 0x8f12bc
+9 }
}
printf "actual X0 = %08x\n", $X0;
# calculate the magic numbers
my $low = 0;
my $high = 0x800000;
my $x = 0;
while ($low < $high) {
$x++;
my $y = ($x * $m1) & 0x7fffffff;
my $yhi = ($y >> 23) & 0xff;
my $yneg = (-$y) & 0x7fffff;
if ($yhi == 0 && $yneg > $low) {
printf "if y < 0x%x then x += 0x%x, y += 0x%x\n", $yneg, $x, $y;
$low = $yneg;
}
elsif ($yhi == 0xff && $yneg < $high) {
printf "if y >= 0x%x then x += 0x%x, y -= 0x%x\n", $yneg, $x, $yne
+g;
$high = $yneg;
}
}
| [reply]
[d/l] |
|
|
