11 ms·
Exploit Information Leaks in Random Numbers from Python, Ruby and PHP
- rarrrrrr 14y agoWorth it just for that video of the perfect game of Asteroids.
- sp332 14y agoThis one is even cooler, to me, since the ship flies around a lot more http://www.heise.de/video/artikel/Asteroids-Vladimir-Bleifuss-Panteleev-17-Platz-1573642.html http://www.heise.de/video/artikel/Asteroids-Vladimir-Bleifus...
- jgrahamc 14y agoFunny, that someone did this. I wanted to implement something similar to check that GCHQ weren't lying to me about this: http://blog.jgc.org/2011/12/back-channel-confirms-that-im-right.html http://blog.jgc.org/2011/12/back-channel-confirms-that-im-ri... 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). 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.
- marshray 14y agoDepends on how much state they seeded it with. It's pretty common for MT to be seeded with 32 or less bits of entropy.
- antirez 14y agoA PRNG based on RC4 should be very fast but much more secure than a MT or a LCG. 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. At least /dev/urandom should be used for seeding purposes in applications where you need an unguessable PRNG.
- tptacek 14y agoRC4-based CSPRNGs were an OpenBSD idiom. But you should use your OS's or your framework's secure random number generator in preference to arc4random(), because there's more to the security of a good CSPRNG than just the algorithm it to jumble up its internal state.
- carbocation 14y ago> At least /dev/urandom should be used for seeding purposes in applications where you need an unguessable PRNG. I usually consume /dev/urandom and convert it to the base I require, using that directly as my random number. When you say you should use it for seeding purposes, are you referring to using /dev/urandom as a seed for something like PHP's rand(), or do you mean something else?
- tptacek 14y agoSeeding is largely a problem you have if you're building (or retrofitting in) your own CSPRNG, which you shouldn't do. The random/urandom interface Unixes provide will allow you to shovel in high-entropy data, but I think you're more likely to do harm than good (it's a marginal impact in either direction, though). You're doing the right thing already.
- carbocation 14y agoAha, that makes sense. Thanks!
- kdsudac 14y agoInteresting 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? 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?
- jsaxton86 14y agoI think the author was alluding to the following: http://www.cigital.com/papers/download/developer_gambling.php http://www.cigital.com/papers/download/developer_gambling.ph...
- sophacles 14y agoThere are a few things here. First, the look at the protocol and see if you can simply determine what number maps to what card. Next, presuming they are doing the simple thing (given their choice of random... this isn't that unfathomable) and numbering them sequentially you only have 4 possibilities. Thats not that hard to run your data through. There are a few more orderings that make a certain kind of "straight-forward" sense that would be good tries too. Of course they may not be doing that, and have some sort of "random base deck". That would be a bit harder, im pretty sure you can come up with a system of equations to figure out the card number along with the system described in the article, and as such (and perhaps with a bit more data) still solve it. Finally, there may be statistical methods to combine with the equations in the article to figure out whats happening. (which you may need anyway depending on how exactly get_next_card() is called and how random is called (same prng for the whole system, or one per game? etc)
- doe88 14y agoIndeed 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(...)
- gojomo 14y agoSystemRandom uses the system's urandom, which may not be ideal, either. (The man page for urandom mentions theoretical problems when system entropy pools are depleted.) The PyCrypto.Random.random option mentioned in another thread by wulczer might be better... but would love an authoritative recommendation from an expert.
- tptacek 14y agoYou should probably use your system urandom/random in preference to any application-layer CSPRNG. Your OS developers are charged with maintaining a high-profile high-value CSPRNG used for most applications on the system, and vulnerabilities in it are a hair-on-fire problem. The same is not true of application-layer replacements. The kernel RNG is also in a privileged position to collect entropy.
- KMag 14y ago
- Xk 14y agoThose interested in this should look at a paper from Vern Paxon and Nicholas Weaver: http://www.icir.org/vern/papers/witty-imc05.pdf http://www.icir.org/vern/papers/witty-imc05.pdf 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.
- lelf 14y agohttp://news.ycombinator.com/item?id=639976 http://news.ycombinator.com/item?id=639976
- tptacek 14y agoThat post, which is great, is the normal way bad RNGs are broken by attackers: you trace down how they're seeded and then brute force the seed values. What's great about this blog post is that it attacks the underlying algorithm; the post you linked to is more fun, but this post is a little more useful. In either case: just use random/urandom and this stuff is taken care of for you.
- praptak 14y agoI 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: http://taeb-nethack.blogspot.com/2009/03/predicting-and-controlling-nethacks.html?m=1 http://taeb-nethack.blogspot.com/2009/03/predicting-and-cont...
- tptacek 14y agoThis 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. 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. You should know that unless your RNG calls itself "secure" or "cryptographic" --- like, in the function name --- 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. (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.)
- wulczer 14y ago> (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.) Yeah, Python's random module uses MT, but you can use PyCrypto, which provides an API-compatible cryptographically secure module (PyCrypto.Random.random).
- inglesp 14y agoThe Python docs[0] for the random module also state, quite clearly, that "the basic function random()... is completely unsuitable for cryptographic purposes". [0] http://docs.python.org/3.3/library/random.html http://docs.python.org/3.3/library/random.html
- Moto7451 14y agoVery very minor nitpick/addendum to your point. Some languages let you swap out the rand function for a secure implementation. In those cases its important to make sure that that mechanism is actually in place. In Perl for example: http://search.cpan.org/~mkanat/Math-Random-Secure-0.06/lib/Math/Random/Secure.pm http://search.cpan.org/~mkanat/Math-Random-Secure-0.06/lib/M...
- cynwoody 14y agoHere's a hardware solution to the "pseudo" problem: http://gamesbyemail.com/News/DiceOMatic http://gamesbyemail.com/News/DiceOMatic 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."