A bitcoin client with no PRNG. Possible?

[DeathAndTaxes]

Someone mentioned using the random ordering of a deck of cards as the entropy for an HD wallet seed (I can't recall if it was electrum developer or armory developer but great idea).  It had never occured to me but there are 52! possible permutations (52 * 51 * 50 * 49 .... *1) to the ordering of a shuffled deck of cards.  That is ~80,658,175,170,943,900,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000 or ~225 bits of entropy.  It is faster, and easier than rolling a number of dice.  Unlike dice there is no issue of bias (a dice which favors higher numbers).  I wouldn't recommend it but you could even leave a backup of the seed in plain sight by keeping the deck in the proper order in the box.

So it got me thinking could you design a wallet which made absolutely no PRNG calls.  CSPRNG are potential weak link in any cryptographic system and as most rely on deep OS level calls flaws or intentional backdoors can be difficult to detect (or at least provable state that they don't exist).  The only client operations that I can think that require the use of cryptographically secure random numbers are key generation, transaction signing, and wallet encryption (salt in key derivation function).

HMAC(card sequence) -> seed
BIP38(seed) -> master pubkey and master key (and indirectly all derived keys and pubkeys)
RFC6979(key, message_hash) -> k value
LEFT16BYTES(HMAC(seed)) -> salt  (on password change LEFT16BYTES(HMAC(old_salt)) -> new_salt)

So one deck of cards, a lifetime of secure transactions, and no additional sources of entropy required.  Anything I am missing?

[DannyHamilton]

Anything I am missing?

My only concern would be that the deck be truly and well shuffled.

Cards sticking together, shuffling habits, and other human factors could influence the realistic number of permutations available, and might reduce the total entropy of the seed.

The question (perhaps one that can only be answered by running hundreds of thousands, or millions, of tests with actual humans shuffling actual decks of cards) is: How much entropy is lost to the various biases that might be involved?

[hashman]

Someone mentioned using the random ordering of a deck of cards as the entropy for an HD wallet seed (I can't recall if it was electrum developer or armory developer but great idea).  It had never occured to me but there are 52! possible permutations (52 * 51 * 50 * 49 .... *1) to the ordering of a shuffled deck of cards.  That is ~80,658,175,170,943,900,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000 or ~225 bits of entropy.  It is faster, and easier than rolling a number of dice.  Unlike dice there is no issue of bias (a dice which favors higher numbers).  I wouldn't recommend it but you could even leave a backup of the seed in plain sight by keeping the deck in the proper order in the box.

So it got me thinking could you design a wallet which made absolutely no PRNG calls.  CSPRNG are potential weak link in any cryptographic system and as most rely on deep OS level calls flaws or intentional backdoors can be difficult to detect (or at least provable state that they don't exist).  The only client operations that I can think that require the use of cryptographically secure random numbers are key generation, transaction signing, and wallet encryption (salt in key derivation function).

HMAC(card sequence) -> seed
BIP38(seed) -> master pubkey and master key (and indirectly all derived keys and pubkeys)
RFC6979(key, message_hash) -> k value
LEFT16BYTES(HMAC(seed)) -> salt  (on password change LEFT16BYTES(HMAC(old_salt)) -> new_salt)

So one deck of cards, a lifetime of secure transactions, and no additional sources of entropy required.  Anything I am missing?

+1   

Entropy should always at least be visible in an editable field, though it could be initially filled with PSRNG output.

Cards, dice, free association, it doesn't matter.  Let the user decide.  That way as a wallet dev you will never be the one that blew it.   

 

[DeathAndTaxes]

My only concern would be that the deck be truly and well shuffled.

Good point.  However a Bitcoin address only has 128 bit security and properly shuffled a deck is 225 bits of entropy.  One would have to lose a lot of entropy to have any effect on security.   It takes about 9 riffle shuffles to properly shuffle a deck.  Not sure if human behavior can be modeled but I imagine a system of a wash, riffle shuffle, and cutting the deck could be devised to ensure adequate shuffle even by those with bad biases.  There are proven methods used by casinos to ensure decks have sufficient entropy however they are designed with efficiency of a professional in mind.  I am not sure if they would be optimal

I played a lot of poker in the past so I might not be the typical user.  I took a deck arranged it by suit (diamonds, clubs, hearts, spades) and in increasing rank (with Ace being high) such that the starting deck was from 2d to As.   I did 8 riffle shuffles trying to be casual and imprecise and cut the deck once at the end.  It took less than 3 minutes (and another 5 minutes to record the sequence).

I ended up with the following:
TdKh6sAc5s8hJcJs5c6h3s9s7cQsQh4s9h3c4h4c2hTs3hJh9c5hKc2cTc7s4dAh9d2dJdQdAd7hTh5d2s8c7dAsQcKd3d6d6cKs8s8d

Not too bad although there is a big clump of diamonds near the end.  Adding a wash at the beginning and mid sequence cut and additional ripples would probably improve things but I would be pretty confident using this sequence as an entropy seed (well not now that it has been shared).  One thing that occured to me is if the client asked the user for the actual card sequence it could run a statistical analysis and warn the user of a sequence which may show signs of insufficient shuffling.

If you take HMAC-512(card-sequence, "Bitcoin-Deckware) for the sequence above you get d017aa48483abd407348df1f7075faeb87e689f35735e0f2ffed551ef26b84bd6eaf8d56b328985 83c48aae1a60df9ad8929f69049122952b74a39c4c0bff909

This could be broken up as, first 256 bits is hd_seed, next 128 bits is initial kdf salt, last 128 bits is symmetric cipher salt.

hd_seed: d017aa48483abd407348df1f7075faeb87e689f35735e0f2ffed551ef26b84bd
kdf_salt:  6eaf8d56b32898583c48aae1a60df9ad
aes_salt: 8929f69049122952b74a39c4c0bff909

[jonald_fyookball]

Very interesting and cool low tech steganography method although slightly less effective now that you shared it.  Seems there are many possible homegrown entropy methods. You could even use magic the gathering cards if it weren't so blasphemous. lol.  just kidding.

By the way, as a poker player I wonder if you've ever read the poker book by Frank Wallace.

[DannyHamilton]

I ended up with the following:
TdKh6sAc5s8hJcJs5c6h3s9s7cQsQh4s9h3c4h4c2hTs3hJh9c5hKc2cTc7s4dAh9d2dJdQdAd7hTh5d2s8c7dAsQcKd3d6d6cKs8s8d

Not too bad although there is a big clump of diamonds near the end.

A clump of identical suit or a few cards in a row are to be expected in a truly random shuffle (just like hot streaks and cold streaks are expected in a truly random game).

Exceptionally large clumps might be a concern, but I'd also be a bit concerned about predictable patterns or general movements of cards throughout the deck.

As an example.  Imagine an Ace of Diamonds on the bottom of the deck.  Now you split the deck in half.  The Ace of Diamonds is on the bottom of one of those two halves.  You riffle shuffle the deck. Assuming a perfect riffle, there's a 50% chance that Ace is still the bottom card, and a 50% chance it is second from the bottom, right?

Split the deck and shuffle again.  There's now a 25% chance that the Ace is still the bottom card, a 25% chance that it is second from the bottom, a 25% chance that it has now moved up to 3rd from bottom, and a 25% chance that it is 4th from bottom.

A third riffle, and we are looking at particularly good chances of it being in the bottom 8 cards.

A fourth riffle, and the chances are that it is in the bottom 16 cards

A fifth riffle, and the chances are that it is in the bottom 32 cards.

And with the sixth riffle, it could be anywhere in the deck.

This all assumes a perfect riffle where the cards exactly alternate right and left sides, and the only random factor is whether the shuffler drops a card from the right side first or the left side. This is probably why it is frequently said that 9 riffle shuffles result in a well shuffled deck.

But if we introduce a human bias and say that the shuffler always holds the bottom half of the deck in their right hand and nearly always drops a card from their right hand first...  You could riffle shuffle that deck 100 times, and there'd still be a really good chance that the Ace of Diamonds is the bottom card (or at least very close to the bottom) of the deck.  There'd also be a really good chance that the top card hadn't moved very far at all.

It would be interesting to run the test a few hundred times and plot the end position of the cards that start at the bottom and top of the deck.  I wonder if you'd see a tendency for those 2 cards to end up in particular areas (or to avoid particular areas) of the deck.

Adding a wash at the beginning and mid sequence cut and additional ripples would probably improve things but I would be pretty confident using this sequence as an entropy seed (well not now that it has been shared).

A wash would probably make a very big difference.  Starting with an already used deck would help a lot as well.

One thing that occured to me is if the client asked the user for the actual card sequence it could run a statistical analysis and warn the user of a sequence which may show signs of insufficient shuffling.

Perhaps.  On the other hand, identifying a particular person's bias might be difficult.  A larger risk would be if a person used this process many times to generate many seeds for various purposes.  It might be possible to significantly reduce the search space on all their other seeds if you can get your hands on any one of their sequences.

[jonald_fyookball]

You would already have tons of entropy from an old deck sitting around your house.
So you could shuffle it several times and any shuffling biases would be inconsequential
since no one new the original state.

[DannyHamilton]

Note.  I also played quite a bit of poker in the past (both home games and casino).  I knew a guy who would take advantage of shuffle bias in home games to win Texas Hold'em tournaments.  I talked to him a bit about his strategies quite a bit.

When it was his turn to shuffle, he would intentionally use shuffle bias to move high value cards towards the bottom of the deck.  Then he'd watch where the cards were cut before they were dealt.  This would allow him to know if there was a really good chance that several people were holding very high cards in the pocket (if the cut moved the "clump" to the top of the deck), or a really good chance that high cards wouldn't be coming into the community cards (since they were buried deep in the deck.  If he knew the habits of the person that would be cutting the deck, he'd try to use the shuffle bias to get as many high cards into people's hands as possible.  This would encourage a lot of high betting and would knock people out of the tournament faster.

When it wasn't his turn to shuffle, he'd pay attention to how the cards were gathered up.  He'd watch to see if he could tell what the top or bottom few cards were before the shuffle began based on how the just played cards were assembled into the deck.  Then he'd watch to see if the shuffler had a bias that would keep top cards near the top, or bottom cards near the bottom.  This would allow him information about whether particular cards were likely to show up during the next round of play.

[DannyHamilton]

You would already have tons of entropy from an old deck sitting around your house.
So you could shuffle it several times and any shuffling biases would be inconsequential
since no one new the original state.

Correct.  But if this were to become a standard part of some wallet, there'd be a significant risk that people would purchase brand new decks solely for this purpose.  These decks would come in a pre-set order.  Therefore the process of introducing the entropy into the system would become very important.  Given enough people using the system, it is highly likely that certain bad habits would occur on a very frequent basis unless significant steps were forced upon the users to prevent the habits.

[jonald_fyookball]

You would already have tons of entropy from an old deck sitting around your house.
So you could shuffle it several times and any shuffling biases would be inconsequential
since no one new the original state.

Correct.  But if this were to become a standard part of some wallet, there'd be a significant risk that people would purchase brand new decks solely for this purpose.  These decks would come in a pre-set order.  Therefore the process of introducing the entropy into the system would become very important.  Given enough people using the system, it is highly likely that certain bad habits would occur on a very frequent basis unless significant steps were forced upon the users to prevent the habits.

Dice seem more idiot proof in that regard, although subject to tampering.

[DeathAndTaxes]

Exceptionally large clumps might be a concern, but I'd also be a bit concerned about predictable patterns or general movements of cards throughout the deck.

I think that can be largely eleminated by using cutting and stripping (sometimes called side shuffling).

The new wallet wizard could walk the user (possibly with diagrams and/or video) through this process (even if starting from a pre-determined new deck of cards).

Cut the deck randomly.
Riffle shuffle 1 time.
Strip shuffle.
Riffle shuffle 2 times.
Strip shuffle.
Riffle shuffle 3 times.
Strip shuffle.
Riffle shuffle 4 times.
Cut the deck randomly.
Flip the deck over and record the cards in order into the new wallet wizard.

[Aleksei Richards]

Exceptionally large clumps might be a concern, but I'd also be a bit concerned about predictable patterns or general movements of cards throughout the deck.

I think that can be largely eleminated by using cutting and stripping (sometimes called side shuffling).

The new wallet wizard could walk the user (possibly with diagrams and/or video) through this process (even if starting from a pre-determined new deck of cards).

Cut the deck randomly.
Riffle shuffle 1 time.
Strip shuffle.
Riffle shuffle 2 times.
Strip shuffle.
Riffle shuffle 3 times.
Strip shuffle.
Riffle shuffle 4 times.
Cut the deck randomly.
Flip the deck over and record the cards in order into the new wallet wizard.

Would it not be simpler to throw the cards on the floor, take a picture and then get the SHA256 of the raw photo bytes ?

[dserrano5]

Would it not be simpler to throw the cards on the floor, take a picture and then get the SHA256 of the raw photo bytes ?

You don't need a deck for that. A black picture (e.g. without removing the cap from the lens) at maximum ISO setting will yield a decent amount of random noise.

[cr1776]

Anything I am missing?

My only concern would be that the deck be truly and well shuffled.

Cards sticking together, shuffling habits, and other human factors could influence the realistic number of permutations available, and might reduce the total entropy of the seed.

The question (perhaps one that can only be answered by running hundreds of thousands, or millions, of tests with actual humans shuffling actual decks of cards) is: How much entropy is lost to the various biases that might be involved?

Randomness is a good point. If you use a perfect shuffle, it isn't random of course.  But if you model a random riffle shuffle mathematically seven shuffles should be sufficient (cut binomially, drop cards from either side with a probability proportional to the current size of each side). I remember seeing the proof that at that point any combination is equally possible. Of course no one would be that good so another couple of shuffles should be done when doing it by hand.

[DannyHamilton]

Exceptionally large clumps might be a concern, but I'd also be a bit concerned about predictable patterns or general movements of cards throughout the deck.

I think that can be largely eliminated by using cutting and stripping (sometimes called side shuffling).
- snip -

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.  Any time you put a human being in charge of creating randomness, I become very skeptical.  We are very bad at it, and yet in most cases we believe we are very good at it.  It's probably possible to find a system of shuffling that would eliminate any bias, but I'm not sure what that system would be or what percentage of people would realize the importance of using the recommended system.

[DeathAndTaxes]

Would it not be simpler to throw the cards on the floor, take a picture and then get the SHA256 of the raw photo bytes ?

I timed it and despite it sounding like a lot it took about 1 minute.

[jonald_fyookball]

I'm not sure what that system would be or what percentage of people would realize the importance of using the recommended system.

I find myself constantly overestimating the collective intelligence/ethics/competence of humanity.
There's many great people but many more morons. 

[gmaxwell]

I've generally found it to be pretty easy to shuffle poorly... I'd rather throw hex dice 128 times and compress 2:1 with sha256. Even a little excess entropy plus a cryptographically hard compression function should overcome all small biases, and the order dependence in a shuffle much harder to notice or test for. The excess input also gives you enough data to perform some tests that thwart user misuse (you rolled 0 100 times in a row? really?) without compromising security.

[btchris]

Maybe this is already obvious, but there's no reason to avoid using a potentially compromised entropy source assuming that you're also using a source that is likely to be good, is there?

In other words, why not use a shuffled deck + CryptGenRandom() (even though it's closed source) + RDSEED/RDRAND (even though it can't be inspected) + whatever else you can come up with? Even if one or more of those methods is insecure, the result is secure as long as at least one of those methods produced enough real entropy, correct?

[gmaxwell]

There is a reason— just that it can hide the faults when your other things failed.  Sort of if you assume everything is right, then no— it's no harm. But of course, if you could really get away with assuming that everything is right you would have not worried with additional entropy sources to begin with.  Another reason is that it makes audit and review harder, e.g. if you can test it and confirm that it always gives the same keys for the same deck then thats a useful property to facilitate testing.

Not a reason to not do it, but it's just something to keep in mind.