4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ It's really great that you're exploring entropy. What I don't understand is the need for hand card shuffling to feed SHA512 which must be done by machine. If you don't want to get the good stuff from /dev/random, you can simply SHA(dark OCR camera image) and don't bother with the cards at all. You'll get waaay more than 256 bits for AES. $\endgroup$ – Paul Uszak May 8 at 0:01
  • $\begingroup$ @PaulUszak So what you're saying is... card shuffling is a "good" source of entropy, but by no means a "practical" source for machine use. $\endgroup$ – nCoder May 8 at 0:03
  • $\begingroup$ I was just trying to understand your motivation for using cards to feed a computer :-) If you're getting some sort of deck reading camera, useful context would be to know that I easily get 20,000 bits of entropy from 1 VGA frame. The cards become superfluous. $\endgroup$ – Paul Uszak May 8 at 0:27
  • 3
    $\begingroup$ Once upon a time most computers had a reader for punched cards and all too many decks of such cards were randomized by people dropping them or knocking them over/down, or wind gusts, and people complained about the effort needed to remove that entropy. $\endgroup$ – dave_thompson_085 May 8 at 3:37
3
$\begingroup$

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.
$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks for the answer; I knew that my self-rolled CSPRNG was probably terrible, but do you know a way to efficiently extract entropy from the deck? $\endgroup$ – nCoder May 7 at 22:50
  • $\begingroup$ Since the maximum entropy in the shuffled deck is 225 bits, use SHA as you suggest and take no more than a 128 to 196 bit substring of the output. Then discard the shuffle output. If you are concerned about collisions, go for a shorter output bitlength. $\endgroup$ – kodlu May 7 at 23:03
  • $\begingroup$ Okay, which means that in theory, I could produce enough entropy to make an AES key by using a deck of cards, thus making the Solitaire cipher a bit pointless... $\endgroup$ – nCoder May 7 at 23:06
  • $\begingroup$ About whether "you can trust the shuffle process to be random enough", see the second half of the Wikipedia page on shuffling for basic info and references. $\endgroup$ – Mars May 10 at 3:22
0
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Aren't uniformly distributed bits/bytes the expected output of a randomness extraction procedure? Yet an F-Yesque shuffle requires random numbers ranging 0 - 50. So wouldn't that be the range that pops out when it's run in reverse? $\endgroup$ – Paul Uszak May 8 at 12:17
  • $\begingroup$ @Josiah this statement is false: “Extending a finite supply of good randomness into a usable stream is a hard, and more importantly different, problem.” Any stream cipher (or block cipher in counter mode) does exactly this. $\endgroup$ – rmalayter Jun 21 at 10:43
  • 1
    $\begingroup$ Yes, and designing an effective stream cipher is hard, and is a different problem from harvesting entropy. $\endgroup$ – Josiah Jun 21 at 17:43
  • $\begingroup$ I don't understand the downvotes on this answer. It accomplishes the goal of extracting the entropy in a card shuffle into a source of uniform random numbers in the range 0-n!, without requiring the use of a CSPRNG. Especially in the context of generating random numbers by hand, this is useful since most people will have some difficulty computing e.g. HKDF-SHA256 off the top of their head. (Of course, actually combining the factors of n! together into one huge number is impractical, so some modification is needed.) $\endgroup$ – Lily Chung Oct 13 at 21:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.