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

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

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

<p>1021410542201502023034020312354303525141003020114142003134301540433233134222423333133255354344331041</p>

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

<p>Now imagine a die that is loaded. Very loaded. It actually shows <em>five</em> 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?</p>

<p>According to <a href="https://bitcoin.stackexchange.com/questions/7724/what-happens-if-your-bitcoin-client-generates-an-address-identical-to-another-pe">this answer</a> on bitcoin.stackoverflow, this <a href="https://www.coursera.org/course/crypto" rel="nofollow noreferrer">video</a> "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.</p>

<p>According to this paper "<a href="http://download.wpsoftware.net/bitcoin-birthday.pdf" rel="nofollow noreferrer">1 The Birthday Paradox</a>" by Andy Toshi, which is specifically about Bitcoin, it also seems to be safe as far as I can understand.</p>

<p>So we seem to be on the safe side!</p>

CC BY-SA 3.0
2013-11-22T00:39:30.083Z
2013-11-22T00:39:30.083Z
2017-04-13T12:47:32.940Z
jeorgen
<p>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.</p>

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

<blockquote>
  <p>Labby, Z. Weldon's dice, automated.  <em>Chance</em> <strong>22</strong>(4): 6-13, 2009.  <a href="http://statistics.uchicago.edu/about/docs/labby09dice.pdf" rel="nofollow">http://statistics.uchicago.edu/about/docs/labby09dice.pdf</a>‎</p>
</blockquote>

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

<p>Even if your dice are biased, there are various ways to <a href="http://en.wikipedia.org/wiki/Randomness_extractor" rel="nofollow">extract randomness</a> 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:</p>

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

<p>There's a description of the technique <a href="http://pit-claudel.fr/clement/blog/generating-uniformly-random-data-from-skewed-input-biased-coins-loaded-dice-skew-correction-and-the-von-neumann-extractor/" rel="nofollow">here</a>.  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.</p>

CC BY-SA 3.0
2013-11-22T12:42:54.017Z
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
CC BY-SA 3.0
2013-11-22T16:01:49.683Z
@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
CC BY-SA 3.0
2013-11-22T17:29:08.850Z
I read through the linked page, and it does not seem that a randomness extractor increases the entropy either.
jeorgen
CC BY-SA 3.0
2013-11-22T20:11:01.033Z
@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
CC BY-SA 3.0
2013-11-22T20:57:25.370Z
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
CC BY-SA 3.0
2013-11-22T01:12:53.700Z
2013-11-22T16:00:04.410Z
2013-11-22T16:00:04.410Z
Nate Eldredge
<p>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.</p>

<p>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)</p>

<p><a href="http://www.debian.org/security/2008/dsa-1571" rel="nofollow">http://www.debian.org/security/2008/dsa-1571</a></p>

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

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

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

CC BY-SA 3.0
2013-11-21T15:15:22.680Z
I'm sorry, but I don't really see how this is specially related to Bitcoin?
Jori
CC BY-SA 3.0
2013-11-21T16:21:03.960Z
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
CC BY-SA 3.0
2013-11-21T16:45:02.007Z
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 http://www.random.org/.
Jori
CC BY-SA 3.0
2013-11-21T17:05:43.263Z
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
CC BY-SA 3.0
2013-11-21T17:31:06.053Z
see http://world.std.com/~reinhold/diceware.html
RentFree
CC BY-SA 3.0
2013-11-21T17:31:34.167Z
You may want to get casino-grade / tested dice
RentFree
CC BY-SA 3.0
2013-11-21T18:28:54.710Z
A question like this might get a better response on a math or general cryptography StackExchange. There's nothing in the question specific to bitcoin (other than they happen to want to make a cryptographically good random number for use in bitcoin).
dchapes
CC BY-SA 3.0
2013-11-21T19:09:48.560Z
Well, most things are not specific to bitcoin, since all technologies and solutions it is made up of, are also in used in other things. However you may have a point in that there are not that many people in this part of stackexchange who can answer something like off the top of their heads. I do believe that the key generation handling is crucial to bitcoin's future.
jeorgen
CC BY-SA 3.0
2013-11-21T19:12:08.747Z
...and the specifics of the key space and availability of the blockchain with all the addresses and many of the public keys, frames the problem in a certain context, when it comes to crackability and incitament to do so.
jeorgen
<private-key>
Do imperfections in dice make them unsuitable to make really good bitcoin private keys?
jeorgen
# Do imperfections in dice make them unsuitable to make really good bitcoin private keys?

(Asked by: username_0 on 2013-11-21)

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.

**Tags:** private-key

> **Comments:**
> **username_1**: I'm sorry, but I don't really see how this is specially related to Bitcoin?  
> **username_0**: 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  
> **username_1**: 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 http://www.random.org/.  
> **username_0**: 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).  
> **username_2**: see http://world.std.com/~reinhold/diceware.html  
> **username_2**: You may want to get casino-grade / tested dice  
> **username_3**: A question like this might get a better response on a math or general cryptography StackExchange. There's nothing in the question specific to bitcoin (other than they happen to want to make a cryptographically good random number for use in bitcoin).  
> **username_0**: Well, most things are not specific to bitcoin, since all technologies and solutions it is made up of, are also in used in other things. However you may have a point in that there are not that many people in this part of stackexchange who can answer something like off the top of their heads. I do believe that the key generation handling is crucial to bitcoin's future.  
> **username_0**: ...and the specifics of the key space and availability of the blockchain with all the addresses and many of the public keys, frames the problem in a certain context, when it comes to crackability and incitament to do so.  

---

## 2 answers

### Answer by username_0 on 2013-11-22. Score: 0 | Accepted answer

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](https://bitcoin.stackexchange.com/questions/7724/what-happens-if-your-bitcoin-client-generates-an-address-identical-to-another-pe) on bitcoin.stackoverflow, this [video](https://www.coursera.org/course/crypto) "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](http://download.wpsoftware.net/bitcoin-birthday.pdf)" 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!


---

### Answer by username_4 on 2013-11-22. Score: 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](http://en.wikipedia.org/wiki/Randomness_extractor) 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](http://pit-claudel.fr/clement/blog/generating-uniformly-random-data-from-skewed-input-biased-coins-loaded-dice-skew-correction-and-the-von-neumann-extractor/). 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.

> **Comments:**
> **username_0**: 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.  
> **username_4**: @username_0: 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.  
> **username_0**: I read through the linked page, and it does not seem that a randomness extractor increases the entropy either.  
> **username_4**: @username_0: 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.  
> **username_0**: 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 :-)  

---

