Hacker News Reader

Comment by just2n | Hacker News Reader

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.

View on HN

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

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.

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

> I can't intuit a significant bias, so I may well be wrong here

Assume you have a deck of 3 cards. If you switch any 2 cards 3 times, you end up with 27 possibilities. But there are 3! (= 6) permutations. Obviously 27 isn't evenly divisible by 6, so some permutations are represented more than others.

It's not as big an issue, but it is an issue, and it's a mistake many people are likely to make.

Reply on news.ycombinator.com