Do imperfections in dice make them unsuitable to make really good bitcoin private keys?

Question

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.

Answer 1

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.

Answer 2

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!