Can a deck of cards be used as a practical source of cryptographic randomness?

Question

This is not a duplicate of Entropy measurement from shuffled cards, as this concerns use of cards as a cryptographic entropy source, rather than calculating entropy from some number of cards.

The Solitaire cipher from Cryptonomicon makes use of a deck of cards to encipher messages. However, it is considered insecure, and is likely impractical for actual cryptographic uses.

However, a deck of cards does have a large amount of entropy, and unlike electronically generated randomness, the randomness of a properly shuffled deck is nearly infalliable*. The entropy of a deck of cards is $\log_2(52!)$, or 225.58 bits, which approaches the Landauer limit and is well beyond anything we will ever be able to brute force. On the other hand, the order of a deck of cards is not a stream of bits, and is not easy to quickly process with a computer (a specialized deck reader and shuffler machine will be needed.)

My question is: How can random bits be extracted from a shuffled deck of cards? Does this have any practical value at all?

So far, I've come up with the following procedure:

-OCR the deck, producing a string like JH3CAS0D... to represent "Jack of Hearts, 3 of Clubs, Ace of Spades, 10 of Diamonds... and so on".

-Take the SHA-512 hash of this string. For the sake of the example, I came up with: bfda311f6e9f6ad06825c9dc07fbbffb98ff86556a8e6fd7ac835b58f0c5eee04155db4e63f748a6c2b0b7c15e558b0e6c7e8222760283869904a2e485ef2d04

-Take the SHA-512 hash of the last 256 bits of the first hash, and append that to the first hash.

-Repeat step 3 as many times as needed to create an infinite stream.

*Barring cases such as improper shuffling or shuffling a default/stacked/known deck only once.

Answer 1

You're asking about a composition of two things:

1. Choosing a key—or perhaps passphrase—uniformly among $52!$ possibilities by shuffling a deck. Although the key is not a uniform random bit string, it is uniform random in another space.

2. Expanding the key $k$ into a large effectively uniform random pad by computing $x_0 = \operatorname{SHA512}(k)$, $x_1 = \operatorname{SHA512}(\operatorname{trunc}(x_0))$, $x_2 = \operatorname{SHA512}(\operatorname{trunc}(x_1))$, etc., and returning $x_0 \mathbin\| x_1 \mathbin\| x_2 \mathbin\| \cdots$.

In the random process of part (1), if you do a good job shuffling then it's a reasonable way to choose a key from a weird space.

But in the deterministic procedure of part (2), it's trivially breakable—i.e., the procedure is not a good pseudorandom generator—because given $x_0$, or any $x_i$, I can perfectly predict the entire remainder of the output.

However, there's other possibilities:

• $\operatorname{SHA512}(k \mathbin\| 0) \mathbin\| \operatorname{SHA512}(k \mathbin\| 1) \mathbin\| \operatorname{SHA512}(k \mathbin\| 2) \mathbin\| \cdots$, where the numbers $0, 1, 2, \dots$ are uniquely encoded in fixed width.
• $\operatorname{AES}_{k'}(0) \mathbin\| \operatorname{AES}_{k'}(1) \mathbin\| \operatorname{AES}_{k'}(2) \mathbin\| \cdots$, where $k' = \operatorname{SHA512}(k)$.
• In general, you could feed a hash $H(k)$ of $k$ to any pseudorandom generator $G$ to get an arbitrarily long effectively uniform random pad, where $H$ is a random oracle or reasonable to model as such like SHA512. $G$ can be AES in CTR mode, or can be a Keccak duplex, or anything else that has PRG security.

---

For practical use, the standard way to do things is:

1. Use a random process—like shuffling a deck of cards and transcribing the order—to arrive at a secret string; the process need not have uniform distribution as long as it has high min-entropy.
2. Use a standard key derivation function—like HKDF-SHA256—to convert the maybe-nonuniform but high-min-entropy secret string input, together with an optional salt that is unique per user, into a family of effectively uniform keys, labeled by their purpose so that you can use the same secret string input for multiple cryptosystems.
3. Use standard cryptosystems—like X25519, AES-GCM, HMAC-SHA256—with the resulting keys confident that they are effectively uniformly distributed, in accordance with the security contracts of the cryptosystems.

Answer 2

In general, if you can trust the shuffle process to be random enough you can extract a number of bits from a shuffled deck, just like any other physical process.

You do need to trust that the shuffle process generates nearly uniform distribution on the set of permutations of $52$ elements. Otherwise, measures such as unbiasing need to be used.

However, the main problem is the suggestion

-Take the SHA-512 hash of the last 256 bits of the first hash, and append that to the first hash.

You have started with some finite probably flawed randomness, everything else you do is deterministic. No amount of taking halves of SHA outputs, mixing, re-hashing suffices to give you an infinite stream of randomness.

Answer 3

Kodlu makes the fundamental first observation. Extending a finite supply of good randomness into a usable stream is a hard, and more importantly different, problem.

However, I think it is still interesting looking for ways to extract the entropy of the card order specifically. I am going to suggest reversing a shuffle process to extract all the randomness. A standard shuffle algorithm is Fisher-Yates. It works by picking a random card out of the 52 to come first, then a random card out of the 51 to come second, then a random card out of the 50 to come third, and so on.

To reverse the process and extract the entropy, you need to know what random value would have to be picked at each stage to get to your order. So if your shuffled deck has card 19 on the top, write it down as a 19. If it has card 0 next, write that down. And if it has card 36 next, you will write down 34. That is because two earlier cards have already been taken out, so card 36 would actually be in position 34.

Now once you have all the numbers written down, you will read them as a mixed base number. For the example I will assume a deck of 5 cards and that you wrote down 2, 3, 1, 0, 0. (the last digit is always 0) Those were out of 5, 4, 3, 2, 1 respectively. So you have a zero which is forced and can be discarded. Then you have a zero in the units place, so add that to tally 0x(1). Next is a one in the twos place, so add 1x(2x1). Then a three, so add 3x(3x2x1), and a two so add 2x(4x3x2x1). This adds up to 44. If done right, each total value less than five factorial should be reachable by exactly one initial shuffle. You can use that number for your random bits as easily as if you had thrown one 120 sided die.

Of course this still leaves open the problem of fair shuffling, the problem of reading the order, and the problem that the whole thing is really rather slow.