PRNGs and Groove Theory

Urban Dead is a new browser-based MMORPG that’s become popular recently. I’m not planning to talk about the game itself, at least not until I’ve played it a bit!, but there’s something worth noting here — a cheat called Groove Theory:

Groove Theory was a cheat for Urban Dead that claimed to exploit an apparent lack [sic] of a random number generator in the game, [so] that performing an action exactly eight seconds after a successful action would also be successful.

Kevan, the Urban Dead developer, confirmed that Groove Theory did indeed work, and made this comment after fixing the bug:

There is some pattern to the random numbers, playing around with them; “srand(time())” actually brings back some pretty terrible patterns, and an eight-second wait will catch some of these.

So — here’s my guess as to how this happened.

It appears that Urban Dead is implemented as a CGI script. I’ll speculate that somewhere near the top of the script, there’s a line of code along the lines of srand(time()), as Kevan mentioned. With a sufficiently fast network connection, and a sufficiently unloaded server, you can be reasonably sure that hitting “Refresh” will cause that srand call to be executed on the server within a fraction of a second of your button-press. In other words, through careful timing, the remote user can force the pseudo-random-number generator used to implement rand() into a desired set of states!

As this perl script demonstrates, the output from perl’s rand() is perfectly periodic in its low bits on a modern Linux machine, if constantly reseeded using srand()the demo script’s output decrements from 3 to 0 by 1 every 2 seconds, then repeats the cycle, indefinitely.

I don’t know if Urban Dead is a perl script, PHP, or whatever; but whatever language it’s written in, I’d guess that language uses the same PRNG implementation as perl is using on my Linux box.

As it turns out, this PRNG failing is pretty well-documented in the manual page for rand(3):

on older rand() implementations, and on current implementations on different systems, the lower-order bits are much less random than the higher-order bits. Do not use this function in applications intended to be portable when good randomness is needed.

That manual page also quotes Numerical Recipes in C: The Art of Scientific Computing (William H. Press, Brian P. Flannery, Saul A. Teukolsky, William T. Vetterling; New York: Cambridge University Press, 1992 (2nd ed., p. 277)) as noting:

“If you want to generate a random integer between 1 and 10, you should always do it by using high-order bits, as in

j=1+(int) (10.0*rand()/(RAND_MAX+1.0));

and never by anything resembling

j=1+(rand() % 10);

(which uses lower-order bits).”

I think Groove Theory demonstrates this nicely!

Update: I need to be clearer here.

Most of the Groove Theory issue is caused by the repeated use of srand(). If the script could be seeded once, instead of at every request, or if the seed data came from a secure, non-predictable source like /dev/random, things would be a lot safer.

However, the behaviour of rand() is still an issue though, due to how it’s implemented. The classic UNIX rand() uses the srand() seed directly, to entirely replace the linear congruential PRNG’s state; on top of that, the arithmentic used means that the low-order bits have an extremely obvious, repeating, simple pattern, mapping directly to that seed’s value. This is what gives Groove Theory its practicability by a human, without computer aid; with a more complex algorithm, it’d still be guessable with the aid of a computer, but with the simple PRNG, it’s guessable, unaided.

Update 2: as noted in a comment, Linux glibc’s rand(3) is apparently quite good at producing decent numbers. However, perl’s rand() function doesn’t use that; it uses drand48(), which in glibc is still a linear congruential PRNG and displays the ‘low randomness in low-order bits’ behaviour.

This entry was posted in Uncategorized and tagged , , , , , , , , . Bookmark the permalink. Both comments and trackbacks are currently closed.


  1. Paul Jakma
    Posted September 23, 2005 at 08:08 | Permalink

    Ye gods, your script calls srand() repeatedly. No wonder the output is non-random. You’re only supposed to seed a PRNG once. This is not a demonstration of differing entropy between higher and lower order bits in rand(), but completely broken usage of srand/rand in your example! :)

    Move the srand() outside of the while loop:

    $ perl -e ‘srand(time()); while (1) {print time, ” “, int(rand(4)), “\n”; sleep 1;}’ 1127456349 3 1127456350 0 1127456351 3 1127456352 3 1127456353 3 1127456354 3 1127456355 2 1127456356 2 1127456357 3 1127456358 0 1127456359 1 1127456360 0 1127456361 1 1127456362 0 1127456363 1 1127456364 3 1127456365 0 1127456366 0 1127456367 3 1127456368 3 1127456369 0 1127456370 3 1127456371 1 1127456372 3 1127456373 1 1127456374 2 1127456375 0 1127456376 1 1127456377 1 1127456378 3 1127456379 2 1127456380 1 1127456381 1 1127456382 3 1127456383 3 1127456384 1 1127456385 1 1127456386 3 1127456387 3 1127456388 2 1127456389 3 1127456390 1 1127456391 2 1127456392 3 1127456393 1 1127456394 0 1127456395 3 1127456396 0

    Note that the glibc rand() function claims there is no difference in entropy between different order bits obtained from it. However, rand/random() are not really very random:

    $ ./rand | rngtest -t 30 rngtest 2 Copyright (c) 2004 by Henrique de Moraes Holschuh This is free software; see the source for copying conditions. There is NO warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

    rngtest: starting FIPS tests… rngtest: bits received from input: 59300032 rngtest: FIPS 140-2 successes: 1 rngtest: FIPS 140-2 failures: 2964 rngtest: FIPS 140-2(2001-10-10) Monobit: 2121 rngtest: FIPS 140-2(2001-10-10) Poker: 2964 rngtest: FIPS 140-2(2001-10-10) Runs: 123 rngtest: FIPS 140-2(2001-10-10) Long run: 1 rngtest: FIPS 140-2(2001-10-10) Continuous run: 0 rngtest: input channel speed: (min=129.696; avg=2050.266; max=3255208.333)Kibits/s rngtest: FIPS tests speed: (min=917.908; avg=33086.243; max=38072.612)Kibits/s rngtest: Program run time: 30012710 microseconds $ ./random | rngtest -t 30 rngtest 2 Copyright (c) 2004 by Henrique de Moraes Holschuh This is free software; see the source for copying conditions. There is NO warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

    rngtest: starting FIPS tests… rngtest: bits received from input: 61280032 rngtest: FIPS 140-2 successes: 3 rngtest: FIPS 140-2 failures: 3061 rngtest: FIPS 140-2(2001-10-10) Monobit: 2167 rngtest: FIPS 140-2(2001-10-10) Poker: 3061 rngtest: FIPS 140-2(2001-10-10) Runs: 110 rngtest: FIPS 140-2(2001-10-10) Long run: 2 rngtest: FIPS 140-2(2001-10-10) Continuous run: 0 rngtest: input channel speed: (min=167.075; avg=2122.813; max=3255208.333)Kibits/s rngtest: FIPS tests speed: (min=1.078; avg=32.445; max=37.180)Mibits/s rngtest: Program run time: 30011652 microseconds $ cat rand.c





    void main (int argc, char **argv) { srand(time(NULL));

    while (1) { int r = rand(); write (STDOUT_FILENO, &r, sizeof(int)); } }

    The random version is similar, but using srandom, random and a long int. I suspect the reason random /slightly/ faster, and does ever so slightly better on the tests is due to it using long int and the above having been run on a 64bit platform. But I can’t be arsed running it long enough to see if there’s a statistically significant difference :).

    The PRNG provided by the Linux kernel, /dev/random, does pass the FIPS 140-2 tests as implemented by rngtest, but is many orders of magnitude slower:

    $ dd if=/dev/random bs=4096 | rngtest -t 30 rngtest 2 Copyright (c) 2004 by Henrique de Moraes Holschuh This is free software; see the source for copying conditions. There is NO warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

    rngtest: starting FIPS tests… rngtest: bits received from input: 40032 rngtest: FIPS 140-2 successes: 2 rngtest: FIPS 140-2 failures: 0 rngtest: FIPS 140-2(2001-10-10) Monobit: 0 rngtest: FIPS 140-2(2001-10-10) Poker: 0 rngtest: FIPS 140-2(2001-10-10) Runs: 0 rngtest: FIPS 140-2(2001-10-10) Long run: 0 rngtest: FIPS 140-2(2001-10-10) Continuous run: 0 rngtest: input channel speed: (min=1.117; avg=1.145; max=1.174)Kibits/s rngtest: FIPS tests speed: (min=34.869; avg=35.718; max=36.609)Mibits/s rngtest: Program run time: 34145326 microseconds

  2. Posted September 23, 2005 at 09:44 | Permalink

    Paul, that srand is called repeatedly better emulates the situation with a CGI, where the entire program only lasts as long as it takes to serve the request. It can be called again a second later, when it’ll initialise the PRNG again, because the program is starting again.

  3. Paul Jakma
    Posted September 23, 2005 at 09:55 | Permalink

    Bah, to be perfectly clear:

    • the problem is not with the order of bits used
    • the problem lies in fact that the seed to the PRNG is pretty much controlled by the attacker

    A language designed for CGI use probably should provide an PRNG which is pre-seeded from an external RNG, whose state can not be influenced. (eg /dev/random). This appears to be the case with PHP’s rand() function, since 4.2.0:

  4. David Malone
    Posted September 23, 2005 at 19:06 | Permalink

    I wrote a section on random numbers for the FreeBSD /dev/random web page, as arguments about random numbers seem to break out fairly regurally. Naturally, I take the time to slag off rand() – it seems like srandomdev() and random() are pretty good choices in C these days, for simulation/games. (The man page is at – scroll down and look for the section “Randomness”).

    To some extent, the numerical recipies comment applies even if the high order and low order bits are equally random, unless the range of rand() is a multiple of 10 – 1.

    In Paul’s program it is worth noting that the range of rand() is RAND_MAX and the range of random() is 2^31 – 1 (which is usually RAND_MAX). I guess neither of these fill an int on any Linux platform. That may explain why the FIPS tests failed so badly. I think almost everyone uses the same implementation of random(), which contains a comment explaining its design:

  5. David Malone
    Posted September 23, 2005 at 19:08 | Permalink

    Hmmm – the underscores in my comments got chewed and turned into italics…

  6. Posted September 23, 2005 at 20:51 | Permalink

    Paul: as Aidan notes, the repeated srand() calling is deliberate, to emulate the situation with the CGI. However, my further discussion of the rand() manual page doesn’t help. If Urban Dead used a secure seed source like /dev/random, this wouldn’t be a problem, alright. I’ve updated the posting to be clearer.

    David: yes, the underscore thing is an annoying glitch in the Markdown text-markup language I’m using here. Sorry about that!

  7. Paul Jakma
    Posted September 24, 2005 at 01:12 | Permalink


    Yeah, my initial reply missed the point a bit wrt the srand() for each rand() ;). However, it was the discussion of which order bits to use which I took exception to mostly (or which confused me). Some further tests here with Glibc’s PRNG show that high and low order bits seem to have same randomness (at least, as determined by the rough and basic FIPS statistical tests) – regardless of whether it’s reseeded or not. (Course, it might look random – but if the seed can be influenced by the attacker, it most definitely is trivially deterministic ;) ).


    Aha, of course. That explains it. I was scratching my head wondering why the full int didn’t pass. The upper or lower two bytes of rand() /do/ pass FIPS 140-2 sort of equally well, which led me to try find some other reason, but couldnt (I figured that if it was a range problem, the high order two bytes streamed through rngtest would fail far more of the statistical tests, particularly monobit – but it didnt strangely).

    Finally, perl must have some rather cruddy PRNG that the 1st iteration PRNG output is so periodically coupled to the seed.

  8. Posted September 24, 2005 at 01:29 | Permalink

    Paul —

    yeah, I was wondering why the rand() results are so cruddy myself. I looked into it, and it simply calls through to glibc’s drand48(), which is documented to use the crappy old linear congruential algorithm on Linux glibc!