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.
Tags: algorithms, code, games, linux, prng, randomness, security, software, unix
