Topic: A bitcoin client with no PRNG. Possible? (Read 4239 times)

Not really it is something I believe many people have considered simply because RFC6979 is "overkill" however the advantage of a widely adopted standard is it tends to become more widely adopted providing a defacto "universal solution".


It is better.  No doubt about it.  Pretty much anything is better than a random k.  Random k is fragile solution.  It is easy to implement but also very easy to get wrong.  

In general however HMACs are preferable over raw hashes because they have been proven to be cryptographically resilient to various attacks even when the underlying hash is weakened.  It also the more logical tool.  Someone who uses HMAC in other fields would immediately recognize how/why the HMAC is being used.  A HMAC is a keyed hash.  HMAC(message + secret) = keyed_digest.

Look familiar. A transaction is a message and a private key is a secret.  The system is being used exactly as it was intended, not some clever hack or workaround.  The right tool for the job means attack vectors are likely to be better researched.  You can bet that right not cryptographers are researching attacks and weaknesses which may lead to a HMAC "leaking" the secret.  That isn't necessarily the case of a H(secret + known_non_secret).


You could but like your humorous cartoon indicates it may not stop at that.  While RFC6979 may be "excessive" nobody has shown it is insecure.  In time it is very likely that it could end up in general purpose cryptographic libraries (much like pbkdf2 and HMAC-SHA256 are).

While k = sha256(privkey|mdigest) works so does k = sha256(magic|privkey|mdigest) or k = sha256(mdigest|privkey) or k = sha256(XOR(mdigest,privkey)), or k = sha256(privkey), or even k = sha256(message|nonce) or k = sha(message) XOR nonce or k = left32(message) XOR nonce.  The last three aren't deterministic but it would avoid a situaiton where a repeat nonce compromises the key

So if your choices are using algorithm above OR use random k well I would say use your algorithm.  If you can implement RFC6979 then I would say use that over another potentially good but incompatible solution.

As a side note even the simplest solution  k = XOR(privkey, known_constant) works. 

Thanks for the info, etotheipi.  I hadn't realized how simply HMAC could be implemented.  

But I still don't understand the value of HMAC when applied to our use case with bitcoin.  Setting k according to

   k = sha256(privkey | mdigest)

is equivalent to

   k = sha256(privkey | sha256(sha256(message)))

so I don't see how length-extension attacks are possible (which you alluded to as well).  How is

   k = sha256( (privKey XOR 0x5c5c5c5c...) | sha256( (privKey XOR 0x36363636...) | message))

any more secure?  It sure looks more secure because it's more complex, but I'm curious why that is so.    

If you're going for simple, I would still use HMAC, as it is very simple to implement on top of any hash function in only a couple lines of code.  HMAC is a primitive that should be in every developer's toolbox, and it is intended to be used create hashes based on secrets without leaking any information about the secret and also resistant to things like length-extension attacks (may not be so important here, just pointing out that it has nice properties).  So if you're looking for dead simple, I would use:

   k = HMAC_SHA256(privKey, msg)

Which is really just

   k = sha256( (privKey XOR 0x5c5c5c5c...) | sha256( (privKey XOR 0x36363636...) | msg))

I believe that gmaxwell can describe a couple super-longshot concerns about it that RFC 6979 would cover.  But those things should not be considered practical/feasible attacks on the system, but simply that RFC 6979 is more sound and robust.   

I'm going to tread into dangerous waters here….

The requirement for secure digital signatures is only that k is unique per message and that k remain secret.  In my opinion, one of the reasons we haven't seen deterministic signatures adopted more quickly is that RFC6979 is somewhat complex and requires a new cryptographic operation that developers might not already have in their library (HMAC).  Conservative developers probably want to do more due diligence implementing RFC6979 than if they could implement deterministic signatures with, for example, a single line of new code.  Because of this increased complexity, implementing deterministic signatures moves down on the developer's priority list.

As an experiment, what I've been doing is setting

   k = sha256(privkey|mdigest)

as this is trivial to implement (just hash over the 64-bytes found by concatenating the privkey with the message digest).  I'm not a cryptographer, but I don't understand how this could not be an improvement from using a pseudo-random k value from a potentially-flawed PRNG.  

Could bitcoin have its own standard for deterministic signatures that only uses the hash functions we already use anyways (sha256 + ripemd160)?  Another reason I don't particularly care for RFC6979 is because I'd like to see us work towards bitcoin signing ICs that can be built for less than $1.  To achieve max cost reduction, it is important to minimize FLASH and RAM requirements and any new code just increases cost.  To achieve max performance (e.g., speed), it is important that the calculations are not unnecessarily complicated so that they don't take an unreasonably long time to execute even on a uC running at (say) 8 MHz.  


I'll end by pre-emptively making fun of my own proposal:

Generating the keys is half the battle.  And a critical half of the battle.  I believe the other half is using a deterministic signing algorithm RFC 6979.  In Armory we have been talking about doing it, because it's actually much simpler to implement than it would seem from reading the document, and it would totally eliminate the need to call the PRNG after the keys have been created.  And as gmaxwell said, doing so adds the ability to audit the signing device -- when you use the same private key and message to sign, you should get a deterministic signature that can be verified against another trusted device doing the same calculation.  This would certainly increase confidence in devices like the Trezor for which the pre-installed firmware would be difficult to audit otherwise.

Of course, there's still some shenanigans available for malicious manufacturers/handlers of the devices, but I think this would go a long way towards improving the situation.  We had actually planned to do RFC 6979 for the next release of Armory but it fell between the cracks of all the other activities.  And if we do, we'd have a way to toggle whether you prefer to use the PRNG or the deterministic signing (with deterministic signing being default).

Also, although I'd like to take credit for the card shuffling idea, it was actually maaku who originally mentioned it to me.  225 bits is overkill, and I'd have a tough time believe that you could end up below 128 bits of entropy after a two wash-riffle-riffle sequences, no matter how "bad" you are at it.  That doesn't mean you should lessen your shuffling efforts -- I see no reason not to do 5 such sequences and remove 100% of doubt, since it only adds 2 minutes to the key generation sequence that should be required only a couple times per year.

Sorry, I'll edit. :-)

Keep the jokers and other odd cards in?  I haven't bought a pack recently but they often have few extra odd cards.  Couple of bits more?
edit: missed your joker comment. 

Just wanted to point out that a "perfect shuffle" is different from a perfect riffle or a perfectly implemented random shuffle.  It may be obvious, but just in case it isn't for people who weren't exposed to it in a CS class or math class (or probably Vegas ;-)  ), a perfect shuffle is also known as a faro shuffle and will the deck back in order in 8 shuffles if all are done with a "perfect shuffle".  It splits the deck exactly evenly, then exactly alternates the cards from each side.

This compares with the random riffle shuffle like I mentioned above.  I had said "If you use a perfect shuffle, it isn't random of course" but then realized it might not have been clear.

I can't stop watching that machine. I'm mesmerized.

Of course that should work just fine, but I don't think there is really a good way to audit it.  You have have to trust the camera.

That's the beauty of the card method, or dice, or something physical.  You personally can control the influences on the physical item, and keep a record of the state.  Then you can verify using different hardware and software setups that the resultant public keys and hashes come out the same.  With the camera method, you have to trust the manufacturer of the camera to not backdoor the chips.

And on the card method, perhaps just adding a second deck would increase the bitspace enough so even really terrible shuffling bias would still yield computationally secure results.

Or we could all build dice-o-matics -->   http://www.youtube.com/watch?v=7n8LNxGbZbs

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.


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.


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.

In between the traditional shuffles, you could have them fan the cards
and choose a few at random to bury at the bottom.

You could also have them "deal a round" and then
recollect them.  

These would be alternative forms of shuffling.

Here's another idea, not sure how much merit it
has but it is a thought:  After they shuffle several times,
then you have them manually divide the deck into red cards
and black cards and keep shuffling. 

Since most new decks are already arranged by suit, this
separation into red and black wouldn't add any value if
done as the first step...  However, after SOME entropy
is added, you would then be creating a different "starting point",
so you would lock in the entropy generated up to that point
before going on to create additional entropy.

If there was a bad shuffler who failed to create much
changes to , say, the top of the deck, then at least
once you would get a totally new order with this method.

Agreed and thanks for the good points to consider.  This was the kind of discussion I was hoping to get with the thread.  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.

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.

Although that sequence sounds complex and 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 (probably could be improved).  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 (including key stretching) to generate a high entropy seed.

Any other ideas?
 

A few seconds of recorded audio works also.

Or you could get two of these:

I like the idea of taking a random photo (with a camera that has no internet capabilities) and then downloading the photo to an offline computer and taking a SHA256 of the photo file.

Easy to do - and hard to screw up IMO (you could attach a simple web cam to the offline computer to make this even easier).

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.

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?

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.

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

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

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.

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.

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.

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 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.

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

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.

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.

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.

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.


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


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.

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.

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

+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.   

 

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?

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?