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

When Random Isn't Random Enough: Lessons from an Online Poker Exploit

lauradhamilton.com

Post reply on HN
Print view View original

81–90 of 90 posts

Re: When Random Isn't Random Enough: Lessons from an Online Poker Exploit

#81

Post by hueving »

MertsA wrote: post #49
hueving wrote: post #46

Earlier quoted context omitted.

No! You call a blocking rand function bound by available entropy. If your random source is compromised, adding two numbers from the same broken source does nothing. What you can do though, is XOR numbers from independent random sources to improve the entropy of the final output. (not sure if that's what you meant by adding random numbers together)

Doing nothing but an XOR is usually fine but one thing to keep in mind is that an attacker that can see one stream and control the other could completely eliminate any entropy yet make the data look completely random. This sounds like some unlikely scenario but for instance the Linux kernel uses a method like this for /dev/random. Entropy is collected and mixed in an entropy pool from many sources but at the end it i…

That's not really right. The other requirement for that scheme to work is to leak the entropy_pool as well. That's why the linux kernel random source IS safe from bad hardware. Even if the hardware source is completely known by a third party, they can't discern the output from random data because it has been XORed with random data.

If it helps to think about, imagine that the evil hardware always output 00000000 for a byte of randomness. The kernel then XORs that with a byte from the entropy_pool, which is unknown to the adversary. The output byte is still completely unknown to the adversary even though it knows one of the inputs.

Re: When Random Isn't Random Enough: Lessons from an Online Poker Exploit

#82

Post by tptacek »

hueving wrote: post #80
tptacek wrote: post #65

Earlier quoted context omitted.

Oh, I get it. These are both joke comments that are commenting on the weird number of urban legends surrounding randomness.

Really? I would have expected better from you for your reputation. :-) Read carefully what I said. Explained more clearly, XORing is at worst a ceiling function of the entropy of two random sources. If it weren't, that would imply one-time pad is insecure.

I was reacting to "blocking function bound by available entropy".

Re: When Random Isn't Random Enough: Lessons from an Online Poker Exploit

#83

Post by akater »

I'm not a pro (not even an amateur, actually), but the very premise of “shuffling the deck” bewilders me. Shuffling the whole deck is so obviously bug-prone. Why not just pick random elements from decks instead? If I ever wrote a deck simulator I'd never shuffle anything, just picked 1 out of n < 52 when needed. Is this approach too naive and well-known to be somehow flawed as well?

Re: When Random Isn't Random Enough: Lessons from an Online Poker Exploit

#84

Post by strangestchild »

akater wrote: post #83

I'm not a pro (not even an amateur, actually), but the very premise of “shuffling the deck” bewilders me. Shuffling the whole deck is so obviously bug-prone. Why not just pick random elements from decks instead? If I ever wrote a deck simulator I'd never shuffle anything, just picked 1 out of n < 52 when needed. Is this approach too naive and well-known to be somehow flawed as well?

You're simulating a full game of poker. Once a player has been given card 'i', you have to ensure that card 'i' isn't drawn again during the game. You could maintain a set containing all cards that have already been drawn, and re-select your random number if you draw a duplicate, but that's going to get awfully laggy once large numbers of cards have been drawn.

Re: When Random Isn't Random Enough: Lessons from an Online Poker Exploit

#85

Post by akater »

strangestchild wrote: post #84
akater wrote: post #83

I'm not a pro (not even an amateur, actually), but the very premise of “shuffling the deck” bewilders me. Shuffling the whole deck is so obviously bug-prone. Why not just pick random elements from decks instead? If I ever wrote a deck simulator I'd never shuffle anything, just picked 1 out of n < 52 when needed. Is this approach too naive and well-known to be somehow flawed as well?

You're simulating a full game of poker. Once a player has been given card 'i', you have to ensure that card 'i' isn't drawn again during the game. You could maintain a set containing all cards that have already been drawn, and re-select your random number if you draw a duplicate, but that's going to get awfully laggy once large numbers of cards have been drawn.

I keep track on which cards have been drawn this round. Every time I need a new card drawn I use, say, one of 52 predefined generators picking 1 out of n (I could even publish these: an attacker would still need to know which millisecond every single card in this round had been drawn to exploit it.)

I don't reselect random numbers; every time it is used, DrawCard function excludes cards currently in-game from the deck and then applies one of those 52 predefined generators to the result of that ComplementarySet call (OK, only 51 of them are nontrivial, doesn't matter). The buffer of drawn cards in current round is about 15 cards or so. It becomes useless once the round is over and is collected by GC, or cleared in some other way. Nothing gets accumulated.

Re: When Random Isn't Random Enough: Lessons from an Online Poker Exploit

#86

Post by akater »

strangestchild wrote: post #84
akater wrote: post #83

I'm not a pro (not even an amateur, actually), but the very premise of “shuffling the deck” bewilders me. Shuffling the whole deck is so obviously bug-prone. Why not just pick random elements from decks instead? If I ever wrote a deck simulator I'd never shuffle anything, just picked 1 out of n < 52 when needed. Is this approach too naive and well-known to be somehow flawed as well?

You're simulating a full game of poker. Once a player has been given card 'i', you have to ensure that card 'i' isn't drawn again during the game. You could maintain a set containing all cards that have already been drawn, and re-select your random number if you draw a duplicate, but that's going to get awfully laggy once large numbers of cards have been drawn.

(52 predefined generators is probably an overkill but when you run an online casino then maybe it's not. :-)

Re: When Random Isn't Random Enough: Lessons from an Online Poker Exploit

#87

Post by ye »

lutusp wrote: post #76
ye wrote: post #75

Earlier quoted context omitted.

> There's now been reported a way to hack a computer by way of its microphone, so that particular method is out. No, it's not. It's in some server in a datacenter. If you can get to the server, you can just change the Poker code, no need to do any crazy microphone hacking. Plus you'd need to know exactly when and how the microphone was sampled. > CPU temperature doesn't change enough to serve as a secure source of en…

> > There's now been reported a way to hack a computer by way of its microphone, so that particular method is out. > No, it's not. Excuse me? Here's the source: http://www.scientificamerican.com/article/computers-can-be-h... Here's a quote: "Computers Can Be Hacked Using High-Frequency Sound -- A computer's microphone and speakers can covertly send and receive data" Which word didn't you understand? >> CPU temperatur…

"by distances of up to about 65 feet (20 meters)"

Good luck getting that close to a server in a data center.

Re: When Random Isn't Random Enough: Lessons from an Online Poker Exploit

#88

Post by rfugger »

comex wrote: post #29

I understand that "swap with entire deck" can't possibly be uniform because it has 52^n input possibilities, which is not divisible by 52! (and that the correct Fisher-Yates having 52! input possibilities and being able to generate every possible outcome is one way to prove that it is uniform). However, I'm not sure I can come up with an intuition for why any particular bias should exist, or why there is a discontinu…

There's a decent explanation here:

http://www.codinghorror.com/blog/2007/12/the-danger-of-naive...

There's also a more complete story about the online poker exploit here:

http://www.cigital.com/papers/download/developer_gambling.ph...

Re: When Random Isn't Random Enough: Lessons from an Online Poker Exploit

#89

Post by hueving »

tptacek wrote: post #82
hueving wrote: post #80

Earlier quoted context omitted.

Really? I would have expected better from you for your reputation. :-) Read carefully what I said. Explained more clearly, XORing is at worst a ceiling function of the entropy of two random sources. If it weren't, that would imply one-time pad is insecure.

I was reacting to "blocking function bound by available entropy".

If you care about having good random bytes, you should call a blocking random function (i.e it doesn't return random data until enough entropy is collected)(e.g./dev/urandom).

If you don't care about security, you can certainly call one that always returns using a PRNG (/dev/random). However, with it being based on a much smaller random seed, using it to generate keys is massively reducing the key space an attacker would need to search for discovery.

In summary, reading from /dev/random is a blocking function bound by available entropy and it's more secure than it's /dev/urandom counterpart that is not bound by entropy.

I'm not sure what your problem is there. Care to elaborate?

Re: When Random Isn't Random Enough: Lessons from an Online Poker Exploit

#90

Post by notduncansmith »

nitrogen wrote: post #41
notduncansmith wrote: post #27

Earlier quoted context omitted.

News/YC is my favorite iOS HackerNews client, it's free and beautiful, and comes with Readability so I never run into this problem. So many sites are either not responsive or do it badly, so it's a lifesaver.

I think you got downvoted because your comment reads like it was written by a marketing plant.

My b, I just get really enthusiastic about products that improve my life.
Post reply on HN