Doesn't d6 to binary for 256-bit bitcoin private key generation produce biased results?

Question

If the mapping table looks like:

1: 000

2: 001

3: 010

4: 011

5: 100

6: 101

Then you are guaranteed that your key will never have a chain of 4 or more 1s, much fewer chains of 3 ones than would be expected from truly random number generation, and no chains of 8 or more 0s. Unless you're using an unintuitive mapping from d6 to binary (e.g. alternating 0 and 1), your dice would have to be $2^n$ (2, 4, 8, 16, etc.) sided in order to produce unpredictable binary results. On https://www.swansontec.com/bitcoin-dice.html suggests using d6 as an alternative to Hex dice, is this insecure? Wouldn't a deck of cards (1-10) have the same problem?

Answer 1

Yes, the method you describe above would indeed produce a key with only about $\frac{256}{3} \cdot \log_2 6 \approx 220.6$ bits of entropy. (I say "about" because 256 is not divisible by 3, so the last die roll will only contribute one bit to the key, and the amount of entropy that bit will have depends on which of the three bits you choose.)

However, that's not what the script suggested on the page you linked to actually does. Rather, it takes 100 rolls of a six-sided die (with a total entropy of $100 \cdot \log_2 6 \approx 258.5$ bits), interprets them as a base-6 number (after shifting the digits 1–6 to the range 0–5) between $0$ and $6^{100}-1$, and then converts this number to hexadecimal and takes the last 64 hex digits of it (which is equivalent to reducing it modulo $16^{64} = 2^{256}$).

This method will yield a key with almost 256 bits of entropy. The reason it's only almost is because $6^{100}$ is not evenly divisible by $2^{256}$, so the modular reduction will introduce some bias. In particular, $6^{100} \mathbin/ 2^{256} \approx 5.64$, so the lower 64% of the range of possible keys will be 6 / 5 times as likely to be chosen as the upper 36%. Thus, the actual entropy of a key generated by this method will be approximately $$0.64 \cdot 2^{256} \cdot \tfrac{6}{6^{100}} \log_2 \left( \tfrac{6^{100}}{6} \right) + 0.36 \cdot 2^{256} \cdot \tfrac{5}{6^{100}} \log_2 \left( \tfrac{6^{100}}{5} \right) \approx 255.995 \text{ bits}.$$

BTW, simply rolling the die 99 times to generate a number between 0 and $6^{99} \approx 2^{255.91}$ and using that number directly as the key would yield a key with 255.91 bits of entropy, only about 0.08 bits less than the method used by the script. Just to explicitly state the obvious, such differences of a fraction of a bit are completely insignificant — for all practical purposes, both methods will produce keys that are as good as a perfectly random 256-bit key would be.

In any case, even a key with 220 bits of entropy, as generated by the method described in your question above, should still be perfectly adequate for resisting brute force guessing attacks by any known or foreseeable adversary (at least using classical computers — but then, if large-scale quantum computing ever takes off, it will be bad news for elliptic-curve crypto regardless of key size anyway).

If you're worried about the special structure of the key (i.e. the avoidance of two digits out of eight when written in octal) possibly enabling some unknown class of attacks, just feed it through a hash function like SHA-256 before using it. For that matter, you might as well just take a series of 100+ six-sided die rolls and feed it through SHA-256 to get a key that's effectively indistinguishable (assuming that SHA-256 is secure) from a perfectly random one.

Answer 2

Totally. It would take 6/8 as many tries to guess the right private key because 110, 111 never show up.

Even when your source of entropy has more bits than you need, it's easy to make a RNG that is subtly biased. For example, back in the day I wrote a random string generator that converted random byte strings (each 8-bit byte is mod 256) to "random" alphabetic strings (each A-Z character is mod 26) by simply taking each byte mod 26. Works fine for the first 9 "chunks" of 26 from 0-233, but the last chunk up to 255 only has 22 possibilities, so letters W, X, Y, Z were less likely to show up. Whoops!