Those interested in this should look at a paper from Vern Paxon and Nicholas Weaver:<p><a href="http://www.icir.org/vern/papers/witty-imc05.pdf" rel="nofollow">http://www.icir.org/vern/papers/witty-imc05.pdf</a><p>A summary of it: A worm used a linear congenital generator to generate its randomness. It used this generator to pick which IPs to try to infect, which hard drives to write data to, and what to write. These researchers used a /8, and were able to use that to count, exactly, the bandwith of all infected machines, how many hard drives machines each had, the time they started up, and locate the exact machine which initially spread the worm. It's really quite amazing that you can get all of this from just packet captures, before you think about it.
This is a pretty great post. We need lots more posts on practical exploit development for RNG flaws, because there are a lot of bad random number generators out there.<p>I want to respond to this headline, though. Use of MT as a CSPRNG is very, very common in PHP applications. And it's also true that MT is the algorithm used by Ruby for it's "rand". But this is not a very common Ruby flaw, at least not like it is in PHP, because virtually every Ruby build provides an explicit secure random number generator, either through OpenSSL or (more commonly) through Rails' SecureRandom.<p>You should know that unless your RNG calls itself "secure" or "cryptographic" --- like, <i>in the function name</i> --- you are using rand(), not a CSPRNG, and you can't count on it for security ever. You will have the exact same problem in most mainstream languages. Secure random number generators say they're secure. Nobody says Ruby's rand() is secure.<p>(I'm pretty sure the same is true of Python, but I'm less confident of the specifics. I think this is a very fair issue to raise with PHP in general, though.)
I remember someone inferring the Nethack RNG state to show off on online servers by dying three times in a row because of kicking a wand of wishing. Here:<p><a href="http://taeb-nethack.blogspot.com/2009/03/predicting-and-controlling-nethacks.html?m=1" rel="nofollow">http://taeb-nethack.blogspot.com/2009/03/predicting-and-cont...</a>
Indeed as the author rightfully mentioned in his article this method is not designed for crypto purpose. One can use the following Python method instead random.SystemRandom().randint(...)
Here's a hardware solution to the "pseudo" problem: <a href="http://gamesbyemail.com/News/DiceOMatic" rel="nofollow">http://gamesbyemail.com/News/DiceOMatic</a><p>It's a dice-rollingmachine "that can belch a continuous river of dice down a spiraling ramp, then elevate, photograph, process and upload almost a million and a half rolls to the server a day. I may not get nominated for a Nobel prize, but the deep rumbling vibration you feel more than hear when two rooms away is quite impressive."
Funny, that someone did this. I wanted to implement something similar to check that GCHQ weren't lying to me about this: <a href="http://blog.jgc.org/2011/12/back-channel-confirms-that-im-right.html" rel="nofollow">http://blog.jgc.org/2011/12/back-channel-confirms-that-im-ri...</a> Essentially, I thought that it was possible that this block of code was not what they actually used (partially because 0x7f did not appear in the output).<p>I didn't do it because I had only 326 bytes of random material with 7 bits per byte. Too little to recover the state.
Interesting read. Realistically, to "know all the cards in online poker games" wouldn't you also have to reverse engineer how they map the random number to a card?<p>You would get a jack of hearts, not an integer between 1 and 52, right? or does the exploit somehow work for arbitrary patterns as well?
A PRNG based on RC4 should be very fast but much more secure than a MT or a LCG.<p>EDIT: also it is very important to seed with care if you are interested in security. Even a strong PRNG seeded with seed_prng(time(NULL)) will be an easy target for brute force attacks.<p>At least /dev/urandom should be used for seeding purposes in applications where you need an unguessable PRNG.