2
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 256-bit bitcoin private key. D6 because that is what is used (as an alternative to Hex dice) on swansontec.com/bitcoin-dice.html $\endgroup$ – bulletgirl22 Jan 25 at 18:50
  • 1
    $\begingroup$ Expecting a chain of 4 zeros or ones with 0 probability is not random. Is has a probability greater than 0. $\endgroup$ – kelalaka Jan 25 at 18:57
  • $\begingroup$ Toss a coin 1024 times and see that you will see 10T or 10F series $\endgroup$ – kelalaka Jan 25 at 19:25
  • 2
    $\begingroup$ Indeed, this RNG method is not properly cryptographically secure because obviously you can't see the values the die can't generate. A proper method would be to only generate 2 bits per throw (0-00, 1-01, 2-10, 3-11) and re-roll on 5 or 6. However this method should still generate private keys with about 220 bits of entropy which should be enough to not be brute-forceable which makes this question much more interesting to see if this kind of bias is actually exploitable (though I wouldn't bet on it not being exploitable). $\endgroup$ – SEJPM Jan 25 at 19:36
  • $\begingroup$ Thanks SEJPM, that's what I was wondering. So this would be less secure than true random numbers but probably still strong enough to be considered cryptographically safe for the purposes of public-private key encryption. $\endgroup$ – bulletgirl22 Jan 25 at 22:06
5
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ Addition: the part "a key with 220 bits of entropy (is) perfectly adequate" applies to a key, as stated. That does not generalize to the random value used in ECDSA signing! That random value is very sensitive to a variety fo biases, when that repeats. $\endgroup$ – fgrieu Jan 26 at 9:49
  • $\begingroup$ Hashing with more than 100 rolls also helps combat the non-uniformity in real-world die rolling. $\endgroup$ – Future Security Jan 26 at 19:23
1
$\begingroup$

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!

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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