Note: I haven't read Diaconis's work; just some reports of it in the news section of SCIENCE more than ten years ago, so people should take what I say with more than a grain of salt. In article <v02140b00aeb6e056bb78@[192.0.2.1]>, ph@netcom.com (Peter Hendrickson) wrote:
A few days ago I suggested that playing cards are a good source of entropy. This was based on claim by Persi Diaconis which was quoted in The Economist.
I've researched the claim and I now believe it would be wise not to use playing cards as a source of entropy for cryptographic applications.
A fully random deck of 52 cards has about 225 bits of entropy. That means that each riffle shuffle introduces about 32 bits of entropy. Intuitively, that seems like a lot of entropy for one riffle shuffle. I've tried a few riffle shuffles with a sorted deck. While hardly scientific, the level of randomness does not look like 32 bits. Most of the time the cards alternate.
Thirty-two bits of randomness in a space that is 225 bits wide leave room for an awful lot of order. Here is a (surely oversimplified) model of a less-than-perfect riffle shuffle: the deck is divided into two equal stacks, and the shuffler typically introduces some number k of "errors" that result in a pair of adjacent cards in the shuffled deck being exchanged (compared to a perfectly-shuffled deck). In a fifty-two-card deck there are fifty-one possible pairs to exchange. log2(51) = 5.67, so we get 5.67 bits of entropy for each exchange, if the exchanges are distributed uniformly through the deck. How many exchanges are needed to get 32 bits of entropy? That would be 32/5.67 , or 5.64 . In other words, to inject that much entropy into the deck, only about six shuffling errors need to occur in the shuffle. The vast remnant of the deck is going to be ordered, in the order that comes from a perfect shuffle. We would expect to see, as you observe, most of the cards in the deck alternating suit after one riffle shuffle.
The claim that 7 riffle shuffles of a deck of 52 cards will bring the deck to a state of near randomness appears in this book:
Diaconis, Persi "Group Representations in Probability and Statistics" Hayward, California: Institute of Mathematical Statistics, 1988. ISBN 0-940600-14-5
The section "An Analysis of Real Riffle Shuffles" begins on page 77.
A model is presented which Diaconis believes is similar to how people shuffle in real life. What is troubling from a cryptographic point of view is that there is little empirical evidence to back this up. What is more, Diaconis mentions that there is some variation in shufflers. A neat shuffler will be less random. (Side note: The Economist claims Diaconis can execute 8 perfect shuffles in less than a minute. This means the deck is returned to its original order!)
Mathematics does not rely on empirical evidence. ;-) But bear in mind that Diaconis is a stage magician as well as a statistician, and surely has a lot of direct personal experience with shuffling cards.
The study of randomness in cards looks much harder to me now. Also, flaws which may be exploitable for financial reasons when real money is on the table may have to be substantially more dramatic than the flaws required to exploit, for instance, an alleged one-time pad.
Do bear in mind that, unless you distill its entropy through hashing, a randomly-ordered deck of cards is going to show a lot of seemingly non-random properties if you try to use it as a one-time pad. Most obviously, because each card in the deck is dealt once and only once, there must of necessity be correlations between cards dealt early in the deck and cards dealt later. (Card-counters at blackjack tables make their money by exploiting these correlations.)
Here's why I now prefer dice: Dice are simple. Each die throw can be made to be quite independent of all other die throws. Even loaded dice may be used by throwing them repeatedly and adding the results mod the number of sides to the die. Dice which are suspect may be studied by repeated throwing. Non-independence can be more easily studied as it can be assumed that a throw of the die is, at most, related only to the previous throw and none before.
The randomness of rolling dice is much more easy to interpret than that of dealt cards. Alan "Roll me and call me your tumbling dice" Bostick -- Alan Bostick | You know those chemicals women have in them, | when they've got PMS? Well, men have those very mailto:abostick@netcom.com | same chemicals in them *all the time*. news:alt.grelb | Margaret Atwood, THE ROBBER BRIDE http://www.alumni.caltech.edu/~abostick