A bitcoin client with no PRNG. Possible?

[CIYAM]

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

[jonald_fyookball]

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

A few seconds of recorded audio works also.

Or you could get two of these:

[DeathAndTaxes]

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.

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?
 

[jonald_fyookball]

Any other ideas?
 

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.

[DannyHamilton]

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.

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.

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.

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.

Although that complex sounds 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.  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 to generate a high entropy seed.

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.

[Cubic Earth]

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

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

[xenon481]

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

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

[cr1776]

... It is important to keep in mind that a perfect (or even very good shuffle) is probably not needed...

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.

[spin]

Any other ideas?

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. 

[cr1776]

cr1776,

It looks like you got your quote tags messed up there a bit.

I didn't say what the quote says I said.

D&T didn't say the things the quote says he said.

Your comments appear to be in D&T's quote block.

Sorry, I'll edit. :-)

[etotheipi]

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.

[Peter R]

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.

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:

[etotheipi]

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.  

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.   

[Peter R]

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.    

[DeathAndTaxes]

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

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

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.  

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

Could bitcoin have its own standard for deterministic signatures that only uses the hash functions we already use anyways (sha256 + ripemd160)?

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.