Title: Modulo Bias Post by: nullius on February 15, 2018, 07:11:56 PM A few weeks ago, I promised this explanation to hatshepsut93 (https://bitcointalk.org/index.php?topic=2850720.msg29329630#msg29329630); and I half-wrote it at the time. I am making this its own topic, because that’s not the first time here I’ve seen people either ask about this, or make this mistake without even realizing it. For those in a hurry, a code snippet is below.
Roll a six-sided die with output d between 1 and 6, inclusive. Convert the results d to a 2-bit number b, using the equation b = (d - 1) % 4, where “%” denotes “modulo”. Here is how all potential inputs map to all potential outputs: Code: Input d: 1 2 3 4 As you can see, the output numbers 2 and 3 each have one way of being chosen; whereas the numbers 0 and 1 each have two ways of being chosen. That is to say, 0 and 1 are twice as likely as 2 and 3. This is “modulo bias”; and it must be avoided anytime you need to pick a uniformly distributed output number from a range which mismatches the range of inputs. Now, consider the common use case of generating a random alphanumeric password. Picking a password alphabet in ASCII order in the 62-character range of [0-9A-Za-z] using a random_octet % 62 (0x3e), we obtain: Code: '0' '1' '2' '3' '4' '5' '6' '7' '8' '9' 'A' 'B' 'C' ... 'x' 'y' 'z' Observe that the eight characters [0-7] can be picked 5 different ways, whereas the others [8-9A-Za-z] can only be picked 4 different ways! As a result, each character in [0-7] will be picked 5/256 = 1.953125% of the time, whereas each of the others will be picked only 4/256 = 1.5625% of the time. (The decimals given are exact.) Although that doesn’t look like much, it is a relative difference of 8 characters being a whopping 25% more likely than the other 54 characters. You do not want a password with those properties! Please keep handy and adapt as needed the following algorithm for avoiding modulo bias, here presented as a C snippet which I here copy with minor modifications from from FreeBSD’s libc (https://svnweb.freebsd.org/base/head/lib/libc/gen/arc4random.c?view=markup&pathrev=315225#l248) (it was copied from OpenBSD, and probably somewhere else before that). The code comment (not written by me) explains how it works. Over the course of years, it will save you many instances of shooting yourself in the foot: Code: #include <stdint.h> [This thread is self-moderated, based on experience (https://bitcointalk.org/index.php?topic=2859033.0); it is for on-topic technical discussion only.] Title: Re: Modulo Bias Post by: hatshepsut93 on February 15, 2018, 09:22:33 PM Let's say I have some 6-sided dice and want to generate a new Bitcoin wallet. The goal is to get a 64-character long hex string that can be passed to BIP39 converter to get xprv and a nice mnemonic.
When I was researching about using dice for password generation, I've seen that you can just generate a long string of your dice throws and pass it to SHA256. So, in my case I have 5d6 and concatenating results of 28 rolls will give me slightly more than 128 bits of entropy, that will get passed to SHA-256 to get a hex string. Is this approach correct? Title: Re: Modulo Bias Post by: HeRetiK on February 15, 2018, 11:07:44 PM Let's say I have some 6-sided dice and want to generate a new Bitcoin wallet. The goal is to get a 64-character long hex string that can be passed to BIP39 converter to get xprv and a nice mnemonic. When I was researching about using dice for password generation, I've seen that you can just generate a long string of your dice throws and pass it to SHA256. So, in my case I have 5d6 and concatenating results of 28 rolls will give me slightly more than 128 bits of entropy, that will get passed to SHA-256 to get a hex string. Is this approach correct? SHA-256 being a cryptographic hash function the output should by definition be uniformly distributed, ie. not be affected by the problem described by nullius. The tricky part is selecting an input with sufficient entropy, as to make it hard for an attacker to guess the input itself. Dice throws meet this condition. |