11 ms·

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

185 points by lauradhamilton 13y ago

DerpDerpDerp 13y ago
This is one of those times you'd really want to use an actual random number generator, rather than a pseudo-random number generator.
- joshka 13y ago
  PRNG would be fine if you could ensure that there's no leakage or reversible information.
  - TillE 13y ago
    A CSPRNG is fine (just use any decent stream cipher), but as the article suggests, properly seeding it is crucial.
  - DerpDerpDerp 13y ago
    My exact point was that this is non-trivial to ensure.
- krexit 13y ago
  Many regulatory licensing authorities of online gambling companies mandate the use of certified Hardware RNGs. Example: Alderney Gaming Commission. Certification includes Monte Carlo testing of the output, amongst other things.
TempleOSV2 13y ago
C:\TAD\Text\BIBLE.TXT bundance without weight; 22:4 Also cedar trees in abundance: for the Zidonians and they of Tyre brought much cedar wood to David. 22:5 And David said, Solomon my son is young and tender, and the house that is to be builded for the LORD must be exceeding magnifical, of fame and of glory throughout all countries: I will therefore now make preparation for it. So David prepared abundantly before his death. 22:6 Then he called for Solomon his son, and charged him to build an house for the LORD God of Israel.
DanBC 13y ago
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.
- notduncansmith 13y ago
  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.
  - nitrogen 13y ago
    I think you got downvoted because your comment reads like it was written by a marketing plant.
    - notduncansmith 13y ago
      My b, I just get really enthusiastic about products that improve my life.
betterunix 13y ago
I like to use this as an example of a problem that secure multiparty computation can solve i.e. that you can remove a buggy / malicious central dealer from a system.
jonbarker 13y ago
true random based on atmospheric noise: random.org
- Ellipsis753 13y ago
  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 numbers. I mean, if you're doing this as a business the small cost of this is well worth not having to deal with your random source having issues.
  - wtallis 13y ago
    > "...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.
    - Ellipsis753 13y ago
      I do however think that I am correct in thinking that provided that any one of your sources is "true" and independent then the xor'd string of binary will be completely random. You cannot xor an unkown random binary string and make it less random.
gedrap 13y ago
I'm curious how actually random are current generators in online poker? I mean, some rather subtle patterns, situations would generate larger pots, therefore more rake. Or being on the new players side in 50/50 situations would 'help' to get him addicted. I am not talking about 100% of the time dealing someone pocket kings, and someone else pocket aces and king on the flop. Something subtle and very rare would be enough to count for large amounts of money at the end of the year, given the volume of major poker sites. On other hand, if someone would leak it, that might ruin the business for good.
- foobarqux 13y ago
  Professionals monitor the play of other players and identify statistically abnormalities. You would have to be clever and conservative enough to evade those types of checks which, while I am sure is possible, is not trivial.
- sanswork 13y ago
  Since the odds of getting certain hands is known and there are a lot of professionals with very large databases of hands any manipulation like that would stand out pretty quickly as a statistical anomaly.
- letstryagain 13y ago
  The major sites don't do this. We know because many people out there collect literally millions of poker hands observed on these sites and mine the data for every kind of statistic you can think of. If anything significant was out of whack they would have picked it up. Look at the 'online poker' section of the twoplustwo forums for example. 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.
  - sillysaurus2 13y ago
    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 if this adds any extra security: probably not. There's no reason not to use the extremely well-tested and well-understood /dev/urandom.
himal 13y ago
Related post https://news.ycombinator.com/item?id=7196820 https://news.ycombinator.com/item?id=7196820
bloodmoney 13y ago
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'.
- lutusp 13y ago
  In engineering terms, it's easier to use a reversed-biased diode as a noise source. An input circuit would transfer the diode's random waveform into a shift register as zeros and ones, until the desired word size has been assembled. It's really quite simple, and it could produce a very high degree of randomness. It would differ from typical PRNGs in that the binary sequence could not be reproduced, no matter how much you knew about the circuit. > I have often wondered about this but lack the 'propriate schoolin'. That's an easily remedied problem. Remember what Mark Twain said: "I have never let my schooling interfere with my education".
  - bloodmoney 13y ago
    Yeah, but AI is taking most of my free cycles at the moment. Still learning, but not much formal computer science. Thank you for responding.
    - lutusp 13y ago
      > Yeah, but AI is taking most of my free cycles at the moment. Given the present state of technology, that's probably a better use of your time. Someone else can produce a white noise source and mass-market it.
  - ye 13y ago
    In engineering terms it would be easier to cover a shitty webcam with a bag, take a photo, and then use the lower bit of each pixel as the source of entropy. You can use other things, like microphone input, or CPU temperature. No need to buy expensive hardware generators. Then you can use something like Fortuna to generate more random numbers from that seed: http://en.wikipedia.org/wiki/Fortuna_(PRNG) http://en.wikipedia.org/wiki/Fortuna_(PRNG)
aelaguiz 13y ago
As recent as 2010 we were finding major flaws in online poker security, here are a couple of videos I did of us sniffing hole cards out of the air because sites were lying about their use of SSL. They were using xOR encryption. Insane. http://www.youtube.com/watch?v=4HBUe8Fb73Q http://www.youtube.com/watch?v=4HBUe8Fb73Q http://www.youtube.com/watch?v=AAQDEXJdbQc http://www.youtube.com/watch?v=AAQDEXJdbQc
- SeanDav 13y ago
  Ouch, I suppose the moral of the story is don't play poker for money using a wireless connection.
  - kawsper 13y ago
    The moral of the story is don't play poker for money where you suspect MITM to be in effect, because the connection is not secure.
    - aelaguiz 13y ago
      It wasn't a MITM. Although I've done that too, ARP flood the router and redirect the traffic through myself. Only works on sites where they didn't peer validate the SSL cert. These were just packet dumps, wasn't associated with the WAP. It's hard to remember the exact details but I believe I was dumping the packets and decrypting them with the WEP key then piping them into a C program which just applied the decryption key to the packets.
      - redthrowaway 13y ago
        Why would they even send that information to the client before it was needed anyway? Keep it on the server and push it when, and only when, the client needs to see it.
        qbrass 13y ago
        It's catching packets heading to other clients to grab the information they don't send to you. Or it would be if it were put to use for evil.
comex 13y ago
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 discontinuity that makes it much more likely for a card to end up a short distance after its starting position: http://en.wikipedia.org/wiki/File:Orderbias.png http://en.wikipedia.org/wiki/File:Orderbias.png Anyone have a good explanation?
- malisper 13y ago
  I'm not entirely sure, but I have been able to figure a few things out. By running some simulations by shuffling the range from 1 to n (with n going from 3 to 7), I found that at least one of the most common permutations had always started with 2. I'm unable to come up with a reason to explain this, but I was able to figure out something else interesting. Imagining that the deck is vertical and going through each card and swapping it with a random card in the deck, the random card that has been swapped will never move further up the deck while the other card can still possibly move further up the deck. This implies that cards at the top of the deck should stay near the top and the cards at the bottom should stay near the bottom. I tested this by taking the sum of the sums of the first half of all the permutations and the sum of the sums of the second half of all the permutations and found that the total sum of the first halves was slightly smaller than the total sum of the second halves. n first halves | second halves 3 53 | 54 4 1265 | 1295 5 18322 | 18976 6 461683 | 498093 7 9638931 10051128 So it seems that cards starting near the top are more likely to end up near the top and cards starting near the bottom are more likely to end up near the bottom. Note: for odd numbers I threw out the middle number.
- sxyuan 13y ago
  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.
chops 13y ago
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.
- deleted 13y ago
  [deleted]
- hueving 13y ago
  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)
  - brazzy 13y ago
    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"??
    - chops 13y ago
      Yes, it was indeed a joke. And one which has apparentlly fallen flat.
      - dublinclontarf 13y ago
        No no, I got it, much enjoyed.
      - blumkvist 13y ago
        No, it worked perfectly. If you have to explain a joke to someone, that means the joke is making fun of them!
  - MertsA 13y ago
chops 13y ago
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.
just2n 13y ago
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 questionable is the cycle length of the PRNG if it weren't using an easily brute forced seed. I'm not entirely convinced the off-by-1 is substantial, nor the fact that the shuffle produces duplicate shuffles (I can't intuit a significant bias, so I may well be wrong here). So to summarize: never seed a PRNG with a small and easily brute forced value.
- deleted 13y ago
  [deleted]
- Nilzor 13y ago
  "I'm not entirely convinced the off-by-1 is substantial". What? You don't think always putting ace of spades at the bottom of the deck is substantial? (given that's what "52" represents)
  - just2n 13y ago
    That wouldn't be the result. The result is that the final card is swapped only once, and can never be swapped with itself, meaning it is always somewhere else in the deck. If the final card is the ace of spades, then the ace of spades can never be the last card in the shuffled deck. In most casino card games, shuffles happen before this knowledge becomes particularly useful, which is why I don't think it's necessarily the major cause for concern here. Being able to easily guess the seed is, however, a pretty massive issue.
    - IanCal 13y ago
      > Being able to easily guess the seed is, however, a pretty massive issue. Particularly since they initialise the deck each time (it'd be a massive issue anyway, but this just makes it worse). Starting with 2^32 states, and knowing their algorithm, you have ~4 billion possible shuffles. However, each card you see drastically reduces the search space. My reasoning is that each card you know reduces the possible number by about how many cards it could have been (so no knowledge is 2^32, one card is 2^32 / 52 ...) Knowing just one card brings you to one of 83 million possible decks. One more card and you're down to just 1.6 million. Once the flop is down, you know 5 cards and that means there are only about 15 possible decks. I think this reasoning is right, but it does seem rather dramatic. I'll have to write a simulation, I've been looking for a good blog post to work through & to work on my visualisations.
rlwolfcastle 13y ago
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-random-number-in-pascal https://stackoverflow.com/questions/4965863/how-to-get-a-ran...
- atul_wired 13y ago
  I think programmer tried to be defensive by ignoring an edge case. He either was lazy in searching for its documentation (<= 1999 you know) and tried to be over-smart to avoid "Out of Range" exception in test/production. Or he didn't consider looking at documentation like some of us do. He may have given it a shot by running it several times to see if it actually generates the number provided as an argument.
PhantomGremlin 13y ago
I haven't seen this link posted yet http://www.idquantique.com/random-number-generators/products.html http://www.idquantique.com/random-number-generators/products... Note they claim: "QUANTIS has also been approved by national authorities and can be used for gaming applications." If I were implementing this for a casino, I'd do what other posters have already suggested and use at least two independent hardware sources for my random numbers and XOR them together. IMO Intel's on-chip RNG would probably be a good source to use, but only in conjunction with others.
- alextingle 13y ago
  > IMO Intel's on-chip RNG would probably be a good source to use Only if NSA contractors don't play online poker in their spare time.
Kartificial 13y ago
Did this exploit actually got exploited? Or did they notify the site and gave them an opportunity to fix it before they released their findings?
stephan10h 13y ago
Flaw #3 seems flawed to me. There are 52! possible ways to shuffle a deck of cards but a game is only played using a small subset. Suppose there are 4 players, then you need 2 times 4 plus 5 is 13 cards. The remaining deck of 39 cards can be shuffled in 39! ways without affecting the game. These possibilities are still included in those 52! of total possibilities. In case of 4 players there are only 52!/39! possible games that can be played. This is still a larger number then the 4 billion mentioned in the article but it doesn't dwarf the 4 billion as the 8*10^67 does.
MikeTV 13y ago
Direct link to the full article with a detailed explanation of the exploit: http://www.cigital.com/papers/download/developer_gambling.php http://www.cigital.com/papers/download/developer_gambling.ph...
o_nate 13y ago
Another lesson to be learned here is it's generally not a good idea to publish the code to a vulnerable, in-production system unless you are very, very sure there are no bugs.
akater 13y ago
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?
- strangestchild 13y ago
  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.
  - akater 13y ago
    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 <= 52 depending on a millisecond number. (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.
  - akater 13y ago
    (52 predefined generators is probably an overkill but when you run an online casino then maybe it's not. :-)

185 points by lauradhamilton 13y ago

This is one of those times you'd really want to use an actual random number generator, rather than a pseudo-random number generator.

joshka 13y ago
PRNG would be fine if you could ensure that there's no leakage or reversible information.
- TillE 13y ago
  A CSPRNG is fine (just use any decent stream cipher), but as the article suggests, properly seeding it is crucial.
- DerpDerpDerp 13y ago
  My exact point was that this is non-trivial to ensure.
krexit 13y ago
Many regulatory licensing authorities of online gambling companies mandate the use of certified Hardware RNGs. Example: Alderney Gaming Commission. Certification includes Monte Carlo testing of the output, amongst other things.

TempleOSV2 13y ago

C:\TAD\Text\BIBLE.TXT bundance without weight; 22:4 Also cedar trees in abundance: for the Zidonians and they of Tyre brought much cedar wood to David. 22:5 And David said, Solomon my son is young and tender, and the house that is to be builded for the LORD must be exceeding magnifical, of fame and of glory throughout all countries: I will therefore now make preparation for it. So David prepared abundantly before his death. 22:6 Then he called for Solomon his son, and charged him to build an house for the LORD God of Israel.

DanBC 13y ago

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.

notduncansmith 13y ago
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.
- nitrogen 13y ago
  I think you got downvoted because your comment reads like it was written by a marketing plant.
  - notduncansmith 13y ago
    My b, I just get really enthusiastic about products that improve my life.

betterunix 13y ago

I like to use this as an example of a problem that secure multiparty computation can solve i.e. that you can remove a buggy / malicious central dealer from a system.

jonbarker 13y ago

true random based on atmospheric noise: random.org

Ellipsis753 13y ago
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 numbers. I mean, if you're doing this as a business the small cost of this is well worth not having to deal with your random source having issues.
- wtallis 13y ago
  > "...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.
  - Ellipsis753 13y ago
    I do however think that I am correct in thinking that provided that any one of your sources is "true" and independent then the xor'd string of binary will be completely random. You cannot xor an unkown random binary string and make it less random.

gedrap 13y ago

I'm curious how actually random are current generators in online poker? I mean, some rather subtle patterns, situations would generate larger pots, therefore more rake. Or being on the new players side in 50/50 situations would 'help' to get him addicted. I am not talking about 100% of the time dealing someone pocket kings, and someone else pocket aces and king on the flop. Something subtle and very rare would be enough to count for large amounts of money at the end of the year, given the volume of major poker sites. On other hand, if someone would leak it, that might ruin the business for good.

foobarqux 13y ago
Professionals monitor the play of other players and identify statistically abnormalities. You would have to be clever and conservative enough to evade those types of checks which, while I am sure is possible, is not trivial.
sanswork 13y ago
Since the odds of getting certain hands is known and there are a lot of professionals with very large databases of hands any manipulation like that would stand out pretty quickly as a statistical anomaly.
letstryagain 13y ago
The major sites don't do this. We know because many people out there collect literally millions of poker hands observed on these sites and mine the data for every kind of statistic you can think of. If anything significant was out of whack they would have picked it up. Look at the 'online poker' section of the twoplustwo forums for example. 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.
- sillysaurus2 13y ago
  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 if this adds any extra security: probably not. There's no reason not to use the extremely well-tested and well-understood /dev/urandom.

himal 13y ago

Related post https://news.ycombinator.com/item?id=7196820 https://news.ycombinator.com/item?id=7196820

bloodmoney 13y ago

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

lutusp 13y ago
In engineering terms, it's easier to use a reversed-biased diode as a noise source. An input circuit would transfer the diode's random waveform into a shift register as zeros and ones, until the desired word size has been assembled. It's really quite simple, and it could produce a very high degree of randomness. It would differ from typical PRNGs in that the binary sequence could not be reproduced, no matter how much you knew about the circuit. > I have often wondered about this but lack the 'propriate schoolin'. That's an easily remedied problem. Remember what Mark Twain said: "I have never let my schooling interfere with my education".
- bloodmoney 13y ago
  Yeah, but AI is taking most of my free cycles at the moment. Still learning, but not much formal computer science. Thank you for responding.
  - lutusp 13y ago
    > Yeah, but AI is taking most of my free cycles at the moment. Given the present state of technology, that's probably a better use of your time. Someone else can produce a white noise source and mass-market it.
- ye 13y ago
  In engineering terms it would be easier to cover a shitty webcam with a bag, take a photo, and then use the lower bit of each pixel as the source of entropy. You can use other things, like microphone input, or CPU temperature. No need to buy expensive hardware generators. Then you can use something like Fortuna to generate more random numbers from that seed: http://en.wikipedia.org/wiki/Fortuna_(PRNG) http://en.wikipedia.org/wiki/Fortuna_(PRNG)

aelaguiz 13y ago

As recent as 2010 we were finding major flaws in online poker security, here are a couple of videos I did of us sniffing hole cards out of the air because sites were lying about their use of SSL. They were using xOR encryption. Insane. http://www.youtube.com/watch?v=4HBUe8Fb73Q http://www.youtube.com/watch?v=4HBUe8Fb73Q http://www.youtube.com/watch?v=AAQDEXJdbQc http://www.youtube.com/watch?v=AAQDEXJdbQc

SeanDav 13y ago
Ouch, I suppose the moral of the story is don't play poker for money using a wireless connection.
- kawsper 13y ago
  The moral of the story is don't play poker for money where you suspect MITM to be in effect, because the connection is not secure.
  - aelaguiz 13y ago
    It wasn't a MITM. Although I've done that too, ARP flood the router and redirect the traffic through myself. Only works on sites where they didn't peer validate the SSL cert. These were just packet dumps, wasn't associated with the WAP. It's hard to remember the exact details but I believe I was dumping the packets and decrypting them with the WEP key then piping them into a C program which just applied the decryption key to the packets.
    - redthrowaway 13y ago
      Why would they even send that information to the client before it was needed anyway? Keep it on the server and push it when, and only when, the client needs to see it.
      - qbrass 13y ago
        It's catching packets heading to other clients to grab the information they don't send to you. Or it would be if it were put to use for evil.

comex 13y ago

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 discontinuity that makes it much more likely for a card to end up a short distance after its starting position: http://en.wikipedia.org/wiki/File:Orderbias.png http://en.wikipedia.org/wiki/File:Orderbias.png Anyone have a good explanation?

malisper 13y ago
I'm not entirely sure, but I have been able to figure a few things out. By running some simulations by shuffling the range from 1 to n (with n going from 3 to 7), I found that at least one of the most common permutations had always started with 2. I'm unable to come up with a reason to explain this, but I was able to figure out something else interesting. Imagining that the deck is vertical and going through each card and swapping it with a random card in the deck, the random card that has been swapped will never move further up the deck while the other card can still possibly move further up the deck. This implies that cards at the top of the deck should stay near the top and the cards at the bottom should stay near the bottom. I tested this by taking the sum of the sums of the first half of all the permutations and the sum of the sums of the second half of all the permutations and found that the total sum of the first halves was slightly smaller than the total sum of the second halves. n first halves | second halves 3 53 | 54 4 1265 | 1295 5 18322 | 18976 6 461683 | 498093 7 9638931 10051128 So it seems that cards starting near the top are more likely to end up near the top and cards starting near the bottom are more likely to end up near the bottom. Note: for odd numbers I threw out the middle number.
sxyuan 13y ago
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.

chops 13y ago

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.

deleted 13y ago
[deleted]
hueving 13y ago
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)
- brazzy 13y ago
  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"??
  - chops 13y ago
    Yes, it was indeed a joke. And one which has apparentlly fallen flat.
    - dublinclontarf 13y ago
      No no, I got it, much enjoyed.
    - blumkvist 13y ago
      No, it worked perfectly. If you have to explain a joke to someone, that means the joke is making fun of them!
- MertsA 13y ago

chops 13y ago

just2n 13y ago

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 questionable is the cycle length of the PRNG if it weren't using an easily brute forced seed. I'm not entirely convinced the off-by-1 is substantial, nor the fact that the shuffle produces duplicate shuffles (I can't intuit a significant bias, so I may well be wrong here). So to summarize: never seed a PRNG with a small and easily brute forced value.

deleted 13y ago
[deleted]
Nilzor 13y ago
"I'm not entirely convinced the off-by-1 is substantial". What? You don't think always putting ace of spades at the bottom of the deck is substantial? (given that's what "52" represents)
- just2n 13y ago
  That wouldn't be the result. The result is that the final card is swapped only once, and can never be swapped with itself, meaning it is always somewhere else in the deck. If the final card is the ace of spades, then the ace of spades can never be the last card in the shuffled deck. In most casino card games, shuffles happen before this knowledge becomes particularly useful, which is why I don't think it's necessarily the major cause for concern here. Being able to easily guess the seed is, however, a pretty massive issue.
  - IanCal 13y ago
    > Being able to easily guess the seed is, however, a pretty massive issue. Particularly since they initialise the deck each time (it'd be a massive issue anyway, but this just makes it worse). Starting with 2^32 states, and knowing their algorithm, you have ~4 billion possible shuffles. However, each card you see drastically reduces the search space. My reasoning is that each card you know reduces the possible number by about how many cards it could have been (so no knowledge is 2^32, one card is 2^32 / 52 ...) Knowing just one card brings you to one of 83 million possible decks. One more card and you're down to just 1.6 million. Once the flop is down, you know 5 cards and that means there are only about 15 possible decks. I think this reasoning is right, but it does seem rather dramatic. I'll have to write a simulation, I've been looking for a good blog post to work through & to work on my visualisations.

rlwolfcastle 13y ago

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-random-number-in-pascal https://stackoverflow.com/questions/4965863/how-to-get-a-ran...

atul_wired 13y ago
I think programmer tried to be defensive by ignoring an edge case. He either was lazy in searching for its documentation (<= 1999 you know) and tried to be over-smart to avoid "Out of Range" exception in test/production. Or he didn't consider looking at documentation like some of us do. He may have given it a shot by running it several times to see if it actually generates the number provided as an argument.

PhantomGremlin 13y ago

I haven't seen this link posted yet http://www.idquantique.com/random-number-generators/products.html http://www.idquantique.com/random-number-generators/products... Note they claim: "QUANTIS has also been approved by national authorities and can be used for gaming applications." If I were implementing this for a casino, I'd do what other posters have already suggested and use at least two independent hardware sources for my random numbers and XOR them together. IMO Intel's on-chip RNG would probably be a good source to use, but only in conjunction with others.

alextingle 13y ago
> IMO Intel's on-chip RNG would probably be a good source to use Only if NSA contractors don't play online poker in their spare time.

Kartificial 13y ago

Did this exploit actually got exploited? Or did they notify the site and gave them an opportunity to fix it before they released their findings?

stephan10h 13y ago

Flaw #3 seems flawed to me. There are 52! possible ways to shuffle a deck of cards but a game is only played using a small subset. Suppose there are 4 players, then you need 2 times 4 plus 5 is 13 cards. The remaining deck of 39 cards can be shuffled in 39! ways without affecting the game. These possibilities are still included in those 52! of total possibilities. In case of 4 players there are only 52!/39! possible games that can be played. This is still a larger number then the 4 billion mentioned in the article but it doesn't dwarf the 4 billion as the 8*10^67 does.

MikeTV 13y ago

Direct link to the full article with a detailed explanation of the exploit: http://www.cigital.com/papers/download/developer_gambling.php http://www.cigital.com/papers/download/developer_gambling.ph...

o_nate 13y ago

Another lesson to be learned here is it's generally not a good idea to publish the code to a vulnerable, in-production system unless you are very, very sure there are no bugs.

akater 13y ago

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?

strangestchild 13y ago
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.
- akater 13y ago
  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 <= 52 depending on a millisecond number. (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.
- akater 13y ago
  (52 predefined generators is probably an overkill but when you run an online casino then maybe it's not. :-)