Quote from: DannyHamilton on July 09, 2014, 12:27:45 PM

I agree, intuitively it feels like alternating riffle and strip shuffling should solve the problem of any human induced shuffle bias.

On the other hand, there are a lot of things that seem intuitive but which turn out to be counter-intuitive in real life.

Agreed and thanks for the good points to consider. This was the kind of discussion I was hoping to get with the thread. It is important to keep in mind that a perfect (or even very good shuffle) is probably not needed. Shuffle biases usually require the person to watch the shuffle and know the starting order of the deck (more commonly the concentration of card types not specific card sequences). For a remote attacker to exploit a bias it would need to be a relatively consistent bias shared by a large portion of the population. As an example lets say you routinely interleave cards 2:2 instead of 1:1. That might be useful to know in a card game if I can see the bottom two cards but if you were to shuffle like that unseen bias or not it wouldn't do me much good.

Although it is unusual in any other scenario there would be value to having the user cut first and perform more strips (essentially multiway cuts) in the shuffling. For existing well played decks it won't hurt but for new decks it makes exploiting any potential bias even more difficult.

I would point out however if you used a shuffled deck as entropy and some stranger asks you to individually shuffle 100 decks and then put the cards back into their boxes and he will pay you $5 for each shuffled deck well you should probably be suspicious.

So users may shuffle poorly. This is less of a concern with a well played deck but more of a concern with a brand new deck. We don't necessarily need a high quality shuffle just one that is good enough that it can't be exploited remotely. What countermeasures are possible?

1) Use a larger set than needed. To get ~128 bits of potential entropy you only need to deal out 26 of 52 cards. We will have the user deal out the entire deck (~224 bits). If the user's deck has jokers well that is just a bonus. A 53 card deck is ~230 bits and 54 card deck is ~236 bits.

2) Use macro methods to move cards out of the top and bottom of the deck. In a ripple shuffle the "problem areas" are the top and bottom. This can be done by having the user cut the deck multiple times (strip shuffle is an option but simply "cut the deck" may be easier for novices).

3) Use more iterations than necessary (there are some math models showing 7 ripple shuffles are sufficient to de-pattern a deck sufficient for cardplay). We will prompt the user to perform 10 ripples interleaved with cuts. Cut deck, Shuffle Once, Cut Deck, Shuffle Twice, Cut Deck, Shuffle Three times, Cut Deck, Shuffle Four Times, Cut Deck. Deal out and record.

4) Use PBKDF2 with a high number of rounds. Since this will be infrequently done performing a million rounds (few seconds on average compute) is a good way to add 20 bits of key strength.

Although that sequence sounds complex and long it only took about 1-2 minutes to shuffle. Data entry was three minutes by text and four minutes by clicking on a crude card matrix (probably could be improved). I wasn't particularly rushing either. I imagine with a step by step on screen wizard it shouldn't take even a novice more than 5-6 minutes (including key stretching) to generate a high entropy seed.

Any other ideas?