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

41–50 of 90 posts

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

#41

Post by nitrogen »

notduncansmith wrote: post #27
DanBC wrote: post #6

This was an interesting article. (Font size is tiny using Chrome on iOS). > If your business or technology depends on using random numbers, your best bet is to use a hardware random number generator. Some hardware RNGs would be hopeless for this task. It'd be scary to have to buy one of these things and trust the output.

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.

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

#42

Post by nitrogen »

TwoBit wrote: post #35
sillysaurus2 wrote: post #25

Earlier quoted context omitted.

The random number generators used by these sites are hardware systems that use micro fluctuations in ambient temperature (for example) as a source of entropy and they are very careful to use enough bits of entropy for every card shuffled. It's amusing to realize that they could just read from dev/urandom with zero risk. They're probably not running Linux, but still. So, for anyone who's wondering if you need this, or…

FWIW, Windows has an equivalent of /dev/urandom. http://msdn.microsoft.com/en-us/library/windows/desktop/aa37...

Is CryptGenRandom equally secure as /dev/urandom, or are there ways to use it wrong?

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

#43

Post by wtallis »

Ellipsis753 wrote: post #13
jonbarker wrote: post #8

true random based on atmospheric noise: random.org

That's a bad idea. You shouldn't be trusting random.org with your random data (what if they get hacked or something). Also if it's send over http then an attacker could listen in to the random data you were being sent (either at your end or at random.org). Ultimately I think you'd do best to use several software methods and 2 hardware methods and just xor them all together into a single secure source of random number…

> "...use several software methods and 2 hardware methods and just xor them all together..."

An xor is only okay if you ensure that all of your RNGs are completely independent - unable to affect or observe each other, and do not draw any of their input from any shared or correlated sources. If you've got two machines seeding their entropy pools with packet timings from the same network, then XORing their PRNG output is as likely to decrease entropy as increase it.

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

#44

Post by sxyuan »

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…

Here's my attempt at an intuitive explanation:

After the first swap, the distribution of numbers at the first position is uniform. What happens in the second swap? Well, the second position contains 1 with probability 1/n, and 2 with probability (n-1)/n. With probability 1/n, this position that is highly biased towards 2 (for n > 2) will get swapped with the first position. So 2 is more likely to be found in the first position.

Of course, it gets messy to carry this out for the n swaps and I still haven't really answered your question yet. To do that let's make the following assumption: after the ith swap, the distribution of numbers at position i is uniform. (I think you can prove this inductively but I haven't tried working it out - I was studying for a midterm before I got nerd-sniped.)

Before the ith swap, position i is biased towards number i. By our assumption, position i-1 is uniform. By making position i uniform we are essentially "smoothing out" the bias at position i to the other positions. Hence, as in the example I started with, it is more likely after swap i that position i-1 will contain number i, at the expense of the other numbers. This then reduces the likelihood of finding number k in positions 1, 2, etc. as opposed to position k-1: 2 is more likely in 1, 3 is more likely in 2, and so on.

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

#45

Post by zaius »

bloodmoney wrote: post #12

I admit I am a total noob here, but couldn't you make something with a TV turned to a station with just static? I have often wondered about this but lack the 'propriate schoolin'.

A similar idea was done by silicon graphics using a lava lamp - http://en.wikipedia.org/wiki/Lavarand

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

#46

Post by hueving »

chops wrote: post #31

The solution here, which the article fails to mention, and which every security expert will undoubtedly tell you, is to make sure you use super random numbers (that's the technical term, for the layperson) by adding two random numbers together.

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)

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

#47

Post by [deleted] »

just2n wrote: post #38

It seems to me that the only major issue here is using a seed which can be trivially brute forced. Even if you don't look around the expected server time in order to guess the seed more quickly, 32 bits is really not hard at all to brute force these days. I don't believe the number of bits the PRNG can generate is an issue here since we only need to uniformly get a number between 1 and 52, though what may be question…

[deleted]

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

#48

Post by brazzy »

hueving wrote: post #46
chops wrote: post #31

The solution here, which the article fails to mention, and which every security expert will undoubtedly tell you, is to make sure you use super random numbers (that's the technical term, for the layperson) by adding two random numbers together.

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)

I believe that chops was being sarcastic in ascribing a typical naive and useless attempt at "improving" randomness to "experts". Come on, "super random numbers"??

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

#49

Post by MertsA »

hueving wrote: post #46
chops wrote: post #31

The solution here, which the article fails to mention, and which every security expert will undoubtedly tell you, is to make sure you use super random numbers (that's the technical term, for the layperson) by adding two random numbers together.

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 is XORed with the output of Rdrand on processors that support it. The NSA could force Intel to sign a malicious microcode update that changes Rdrand to AES_encrypt(i++, NSA_KEY) ^ entropy_pool and then any random data coming from the kernel is completely predictable and without NSA_KEY it wouldn't be discernible from truly random data.

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

#50

Post by rlwolfcastle »

Ignoring that some of the variables don't match up properly (the arrays: card and Card), it seems like the explanation of the first flaw may also be flawed.

Flaw #1: An Off-by-One Error

The algorithm above tries to iterate over each card in the deck, swapping each card with another randomly chosen card in the deck. However—every programmer has made this mistake before—there's an off-by-one error. The function random(n) returns a number between 0 and (n-1), not between 1 and n as the programmer intends. As a result, the algorithm will never swap the 52nd card with itself; the 52nd card can never end up in the 52nd place. So that is the first reason the "random" card shuffling isn't really random.

The comment refers to the Pascal code:

  random_number := random(51)+1;
If the programmer really thought that random was between 1 and n then the random_number variable would be a number between 2 and 52 (1+1 to 51+1). It seems like, instead, a better explanation is that they may have thought random(n) produced a random number between 0 and n, hence the need to increment by one. Another explanation is they just messed up the slicing using 51 instead of 52.

The point being that in the writer's explanation of the flaw they actually make the same mistake.

Funnily enough googling "pascal random" points to a stackoverflow article where the best answer makes the same error.

https://stackoverflow.com/questions/4965863/how-to-get-a-ran...

Post reply on HN