Quote from: DeathAndTaxes on July 09, 2014, 04:55:22 PM

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.

I agree that starting with a used deck eliminates nearly all of this risk. Biases only become important when the user starts with a brand new deck in a common starting order.

Finding the bias of a specific individual requires having access to their bias (watching them, getting them to shuffle a few decks for you, etc). Finding a common bias among a significant percentage of the population (example: right-handed people that play cards frequently) can significantly reduce the search space to find a collision with anyone that might have that bias. The more biased people that use the method, the more likely that an attacker will encounter a collision in the reduced search space.

There is probably an optimal method of eliminating bias. Your suggestions for alternating cutting and riffle shuffling are good ideas. Without experimentation or careful analysis, I'm not sure what the "best" answer is, but as you point out, given the size of the deck "best" may not be necessary.

Quote from: DeathAndTaxes on July 09, 2014, 04:55:22 PM

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.

My gut tells me that process would work fine. There may be faster and easier ways, and it's possible that intuition is wrong here, but if that processes isn't overly burdensome, there's a really good chance that it will be adequate.

Quote from: DeathAndTaxes on July 09, 2014, 04:55:22 PM

Although that complex sounds 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. 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 to generate a high entropy seed.

An interesting idea for data entry might be to sell a set of cards with QR codes printed on them (in which case the size of the deck wouldn't necessarily be limited to 52, 53, or 54 cards). The deck could even be pre-mixed in some form before sale to further protect against shuffle bias. Using QR-Codes would even allow each purchased deck to have its own unique set of codes. The user follows a recommended shuffle pattern. Then they deal the cards one at a time from top to bottom (or bottom to top) in front of a QR-code scanner (webcam, mobile cam, etc)built into the wallet. The user could then either store the cards somewhere in that exact order as a hard copy of the "seed", or they could create a backup of the wallet and re-use the cards to create additional wallets.

Not sure that there's an actual market for a few dozen shuffle-able unique QR codes, but the idea is kind of fun.