Dice do have imperfections (depending on how expensive ones you get), but would they not still have enough entropy such that a private key generated by them could be considered really safe? I am thinking of paper wallets storing lots of coins, potentially.

It would short circuit the problems with the implementations of random number generators on computers (the recent Android bug, and the Debian bug between 2006 and 2008)

http://www.debian.org/security/2008/dsa-1571

If a die is missing a side one would notice, so they are a lot easier to inspect for big errors than computer code.

So, how much would imperfections in dice lower the entropy? Could you just calculate with a lower base, e.g. 5.765*N rather than 6*N with a perfect die (5.765 then being a measurement of imperfection of a specific die).

Edit: maybe rather 6**(N-x), where x are the extra occurrences of one number.

  • 2
    I'm sorry, but I don't really see how this is specially related to Bitcoin? – Jori Nov 21 '13 at 15:15
  • It is the generation of the Bitcoin private key, I will clarify that in the text. As you know there have been problems with the RNGs on some platforms – jeorgen Nov 21 '13 at 16:21
  • So let me get this clear: you propose using dices from a board-games like Monopoly instead of using Pseudo-Random Number generators? Wouldn't that be really time consuming (although fun lol). If you are really worried about implementation/security errors, you should look into True Random Number generators. These are external devices that can be plugged in your computer and make use of atmospheric noise or atom decay. See for example random.org. – Jori Nov 21 '13 at 16:45
  • Hardware random generators may still suffer from implementation errors, just like the RNGs on computers. RNGs on computers may also be driven with real randomness from the microphone (see randomsound package on Linux). If dice are good enough, entropy-wise, they are a really simple solution. And I mean using it for a cold storage wallet, so you only need to do it once (or a couple of times if you need to move bitcoins). – jeorgen Nov 21 '13 at 17:05
  • see world.std.com/~reinhold/diceware.html – RentFree Nov 21 '13 at 17:31

You can certainly use any randomness source you like to generate a private key; however, any bias or correlation in your random inputs will make your key easier to guess and reduce its security.

I wasn't able to find a comprehensive analysis of dice randomness in the scientific literature, but this paper could be a start:

Labby, Z. Weldon's dice, automated. Chance 22(4): 6-13, 2009. http://statistics.uchicago.edu/about/docs/labby09dice.pdf

Based on a total of 315672 die rolls, the author found a statistically significant bias toward the numbers 1 and 6. The other references in that paper could be useful. I also found remarks elsewhere that casino dice, which have flat faces rather than hollowed-out pips, may be less likely to be biased. Of course, your dice could be different; if you wanted, you could roll them a large number of times and perform various statistical tests on the outcomes.

Even if your dice are biased, there are various ways to extract randomness from your data to obtain unbiased random numbers. One of the simplest approaches (though not the most efficient) was described by von Neumann in 1951:

Von Neumann, J. Various techniques used in connection with random digits. NIST journal, Applied Math Series, 12:36-38, 1951.

There's a description of the technique here. Note that it depends on the die rolls being independent and identically distributed, so you would need to roll the same die in exactly the same way each time to get a truly unbiased result.

  • Thanks for digging up stats on alctual dice! Whitening wouldn't increase the entropy as far as I understand. It is useful for a smoother distribution, which is applicable for other applications of RNGs. – jeorgen Nov 22 '13 at 12:42
  • @jeorgen: You're right, whitening isn't the right thing here. The word for what I had in mind turns out to be randomness extraction. I edited. – Nate Eldredge Nov 22 '13 at 16:01
  • I read through the linked page, and it does not seem that a randomness extractor increases the entropy either. – jeorgen Nov 22 '13 at 17:29
  • @jeorgen: It doesn't increase the entropy, but it effectively lets you condense the entropy of a larger sample into a smaller one. For example, when extracting randomness from biased coin flips, the input is some number of biased bits n, and the output is k < n unbiased bits (the same k bits of entropy that were in the original sample, or perhaps fewer). You're right, though, we can't really increase entropy per se; there's no free lunch. – Nate Eldredge Nov 22 '13 at 20:11
  • OK, I get it. Yeah that would increase the quality I suppose, if you know that your source is severely biased. However if you don't know that, then it will decrease entropy in that you get fewer bits of entropy for a given number of die rolls or coin throws. Which is a given of course if your source is biased, then that is the whole point. But if your source is non-biased then the extraction will just make you throw the coin or dice more times. So there is trade-off between fixing the bias and wearing out your arm :-) – jeorgen Nov 22 '13 at 20:57
up vote 0 down vote accepted

I didn't think I would figure this one out but here is a stab at a solution to my own question:

The number of keys possible in bitcoin in roughly 2^256, some values are not allowed at the end, so in decimal it goes from 1 to 115792089237316195423570985008687907852837564279074904382605163141518161494337.

That is 78 digits. What would that number be in base 6? It would be 100 digits:

1021410542201502023034020312354303525141003020114142003134301540433233134222423333133255354344331041

So about 100 or 99 dice throws and we have reached the upper number limit, or close to it. Let's go with 99 so we don't overflow the key space.

Now imagine a die that is loaded. Very loaded. It actually shows five 50% of the time. that means that the most probable number, of all numbers, is all fives, with a probability of 0.5^99. That is around 1.6*10^-30. All other number combinations have lower probability. So is 1.6*10^-30 a problem?

According to this answer on bitcoin.stackoverflow, this video "Exhaustive search attacks" from Dan Boneh has him saying "anything that's bigger than 2^90 is considered sufficiently secure" (although that is for a different application). In inverted decimal that is around 8*10^-28.

According to this paper "1 The Birthday Paradox" by Andy Toshi, which is specifically about Bitcoin, it also seems to be safe as far as I can understand.

So we seem to be on the safe side!

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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