Does my code have modulo bias

Question

I am writing a password generator in Go, but I want to make sure I am avoiding modulo bias.

My solution is to get a random number from crypto/rand in the range [0, len(alphabet) ** passwordLength), and then encode that into the alphabet by dividing by len(alphabet), and using the remainder as an index into the alphabet.

if length == 0 {
    return "", nil
}
if len(alphabet) == 0 {
    return "", errors.New("Alphabet has length 0")
}

// Reading from rand.Reader once for each character would read more bits than necessary.
base := big.NewInt(int64(len(alphabet)))
max := big.NewInt(0).Exp(base, big.NewInt(int64(length)), nil)
num, err := rand.Int(rand.Reader, max)
if err != nil {
    return "", errors.Wrap(err, "Cannot get random data")
}

m := big.NewInt(0)
password := make([]rune, length)
// Add characters in reverse, so that the encoded characters
// follow the same order as the bytes read from rand.Reader.
for i := length-1; i >= 0; i-- {
    // Divmod sets num = num / base,
    // and m = num % base.
    num.DivMod(num, base, m)
    password[i] = alphabet[int(m.Int64())]
}

return string(password), nil

Answer 1

The goal is to generate string password of length characters among alphabet, with uniform distribution (assuming alphabet does not contain duplicate characters), while minimizing consumption of octets drawn from a source assumed uniformly random (hereafter just octets).

A bug in the original code suppressed the first character of alphabet on the left of the generated password, creating a bias for any remaining left character.

The current code seems correct: it generates a uniform arbitrarily large integer that can be thought as index of the generated password in a lexicography sorted vector of all possible passwords, then deduce the password by expressing that integer in a base corresponding to alphabet. This is conceptually clean, but:

• Contrary to the objective, it frequently over-consumes octets. The underlying cause is that Go's implementation of rand.Int(rand.Reader, max) (by crypto/rand#Int or math/big/nat#random, I can't tell) repeatedly generates a uniformly random integer less than max rounded up to the next power of two, until that integer is less than max. For a password of 2 characters among 17, 2 octets are consumed at each iteration; the average is over 3.5 octets per password; 16 octets or more are consumed over once in 336, with no upper limit.
• Average execution time is quadratic with the length of the password, rather than linear for simpler algorithms. That's because cost of modular division grows linearly with the length of the number divided.
• While the language Go comes with an arbitrary precision integer library, not all languages do; and languages that do (like Java) sometime are used in an environment where that library is unavailable (e.g. most Java Cards).

  ---

Unless the length of alphabet is a power of two, whatever method introducing no bias can consume unbounded octets. Proof:

• Assume a method always consume at most B octets and has no bias.
• There's also no bias for a method always consuming exactly B octets, obtained by throwing away octets in the end as necessary.
• That method has 2^B possible inputs and length(alphabet)length possible outputs. It has no bias, hence the later must divide the former.
• Hence length(alphabet) must be a power of two.

It is hard to tell if the use of big makes it more or less difficult to exhibit a timing dependency or other side-channel leaking some info about the generated password.

I can't tell what RNG is actually used, much less if it is cryptographically sound and properly seeded.

---

A fixed-precision algorithm

Note: this is work in progress, missing an implementation (more readable to the OP), and optimizations to reduce octet consumption when len(alphabet) is large.

Here is pseudocode for a method without arbitrary precision arithmetic. It is simple, fast, yields no bias, and is competitive with the question's method on consumption of random bytes when len(alphabet)<80 (in particular, on likelihood of large over-consumption for some parameters). All variables are non-negative integers less than 256*len(alphabet) and conveniently fit integer variables.

• Set $n\gets 256$
  ^{[ $n$ is the number of possible input symbols (here, bytes) ]}
• Set $k\gets$ len(alphabet)
  ^{[ $k$ is the number of possible output symbols]}
• Set $r\gets0$
  Set $s\gets1$
  ^{[ $s$ is the number of possible values for randomness buffer $r$ ]}
• Set the password to empty
• For each character to be generated
  ^{[ $r$ is uniformly random with $0\le r<s<n$ ]}
  1. While $r\ge\lfloor s/k\rfloor\cdot k$
     • set $r\gets r-\lfloor s/k\rfloor\cdot k$
       set $s\gets s-\lfloor s/k\rfloor\cdot k$
       ^{[ $r$ is uniformly random with $0\le r<s<k$ ]}
     • Get one new uniformly random symbol $x$
       ^{[ $x$ is uniformly random with $0\le x<n$ ]}
     • Set $r\gets r\cdot n+x$
       Set $s←s\cdot n$
       ^{[ $r$ is uniformly random with $0\le r<s<k\cdot n$ ]}
  2. Let $y\gets r\bmod k$.
     ^{[ $y$ is uniformly random with $0\le y<k$ ]}
  3. Let $r\gets \lfloor r/k\rfloor$
     Let $s\gets \lfloor s/k\rfloor$
     ^{[ $r$ is uniformly random with $0\le r<s<n$ ]}
  4. Append to the password the character at index $y$ in alphabet

Proof of correctness follows from the comments and arithmetic facts. More there, including why this is economical on randomness consumed (no claim of optimality). Despite the simplicity, I fail to find a reference in the literature.

Notation: to the Go programmer, $\lfloor r/k\rfloor$ is r/k and $r\bmod k$ is r%k.

Extension: One can modify $n$ at the second bullet of step 1 (e.g. to adapt to input symbols variably chosen by dice or coin throw). One can can modify $k$ after step 4 (e.g. to generate passwords always starting with a letter then also allowing digits), but that also requires re-initializing $r$ and $s$ (which looses some randomness), or careful adjustment of these variables.

Caution: I often get my answers correct only after many revisions, and we are only at the second version of the pseudocode itself.

Answer 2

Statistical testing is big part of cryptography. It's an alternative to inspection, and if you amend the code you can have the confidence of proving no bias to yourself on demand. It can also be integrated into a unit test.

Passwords are usually printable characters, so say n characters. Simply histogram the output from a long run of say n*n characters. Go might have some sort of histogramming facility in a library. You then perform a Chi Squared test that ultimately returns a probability value. That might be available in a library too (but I'm unfamiliar with Go). If you have to calculate p yourself directly from the Chi square value, you can use a table for a normal distribution. If p repetitively seems to vary uniformly between 0 and 1, you have no bias and voilà.