Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Exploit Information Leaks in Random Numbers from Python, Ruby and PHP

spideroak.com

Post reply on HN
Print view View original

31–40 of 40 posts

Re: Exploit Information Leaks in Random Numbers from Python, Ruby and PHP

#31

Post by KMag »

gojomo wrote: post #19
doe88 wrote: post #6

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(...)

SystemRandom 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.

PyCrypto.Random doesn't magically gather sources of entropy that aren't available to the O.S. Ideally, the O.S.'s non-blocking randomness source would be an implementation of Fortuna or some other CSPRNG that will eventually recover from compromised state.

Anyway, use OpenSSL's CSPRNG or the system's cryptographic random number source. The weak link in your system is almost certainly not going to be either of these, and they've received a lot more auditing and review than PyCrypto.

The theoretical weakness in /dev/urandom is that it generally hands out more entropy than it gathers, so if there are other exploitable flaws, eventually all of its state will leak. It's important to note that most implementations of /dev/random suffer from relying on estimates of the entropy present in several inputs. The nice thing about Fortuna is that it has the very nice theoretical property that it will eventually recover from leaked state, without relying on entropy estimates. Entropy estimates are a fiction to help some people sleep at night.

Re: Exploit Information Leaks in Random Numbers from Python, Ruby and PHP

#32

Post by tptacek »

Jabbles wrote: post #30
tptacek wrote: post #23

Earlier quoted context omitted.

You should pretty much just default to secure random. /dev/urandom is fine; in Ruby apps, I'd use OpenSSL::Random.random_bytes or ActiveSupport::SecureRandom.random_number.

What cases do you reserve /dev/random for? SSH keygen? Do those functions just read from /dev/urandom?

I don't. Just use urandom.

Re: Exploit Information Leaks in Random Numbers from Python, Ruby and PHP

#33

Post by carbocation »

tptacek wrote: post #27
carbocation wrote: post #25

Earlier quoted context omitted.

> 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?

Seeding 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.

Aha, that makes sense. Thanks!

Re: Exploit Information Leaks in Random Numbers from Python, Ruby and PHP

#34

Post by sophacles »

kdsudac wrote: post #5

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? 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?

There 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)

Re: Exploit Information Leaks in Random Numbers from Python, Ruby and PHP

#35

Post by wglb »

tptacek wrote: post #26
gojomo wrote: post #19

Earlier quoted context omitted.

SystemRandom 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.

You 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.

And what about them new-fangled Intel random number generating instructions?

Re: Exploit Information Leaks in Random Numbers from Python, Ruby and PHP

#36

Post by tptacek »

wglb wrote: post #35
tptacek wrote: post #26

Earlier quoted context omitted.

You 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.

And what about them new-fangled Intel random number generating instructions?

You should trust that your OS will use them when it makes sense to use them. :)

(I'm being glib.)

Re: Exploit Information Leaks in Random Numbers from Python, Ruby and PHP

#37

Post by seats »

tptacek wrote: post #18
Moto7451 wrote: post #15

Earlier quoted context omitted.

Very 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/M...

Which is evil, because you want assessors and code reviewers to be able to quickly spot which RNG you're using.

Not to mention wanting something to break if the secure implementation somehow were separated from the code using it (versus silently reverting to PRNG).

Re: Exploit Information Leaks in Random Numbers from Python, Ruby and PHP

#38

Post by wladimir »

Jabbles wrote: post #22
tptacek wrote: post #13

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. 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 PH…

Is there any advice you're able to give on how to distinguish situations where you need secure RNG from those that don't matter? For instance, you definitely need it in poker hand generation - would you need it for random loot generation in an MMO? Also by "secure" you mean /dev/random, and /dev/urandom is used as if it was rand()?

Using a secure RNG is always a good idea, unless you know you need lots of (predictable given the seed) random numbers for example in Monte Carlo sampling.

Even in randomized algorithms you may have to be careful what RNG you use, because of DDOS risk. For example see the problems with Python and Ruby hash tables that could be exploited to have worst-case behavior because their behavior was entirely predictable.

In a MMO you most certainly want to use a secure RNG, as cheating is rife in them. If a player can get an advantage by predicting the RNG, someone will.

Re: Exploit Information Leaks in Random Numbers from Python, Ruby and PHP

#39

Post by wglb »

tptacek wrote: post #36
wglb wrote: post #35

Earlier quoted context omitted.

And what about them new-fangled Intel random number generating instructions?

You should trust that your OS will use them when it makes sense to use them. :) (I'm being glib.)

And I was being a bit silly.

Re: Exploit Information Leaks in Random Numbers from Python, Ruby and PHP

#40

Post by emboss »

tptacek wrote: post #23
Jabbles wrote: post #22

Earlier quoted context omitted.

Is there any advice you're able to give on how to distinguish situations where you need secure RNG from those that don't matter? For instance, you definitely need it in poker hand generation - would you need it for random loot generation in an MMO? Also by "secure" you mean /dev/random, and /dev/urandom is used as if it was rand()?

You should pretty much just default to secure random. /dev/urandom is fine; in Ruby apps, I'd use OpenSSL::Random.random_bytes or ActiveSupport::SecureRandom.random_number.

If OpenSSL::Random isn't working (because OpenSSL is not installed for example) there is also SecureRandom in the stdlib. It tries to do the right thing in any situation: Use OpenSSL:Random if available, otherwise it will fall back to what's available in the OS you're on.
Post reply on HN