1
$\begingroup$

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
$\endgroup$
5
  • $\begingroup$ Is there any reason not to use simple rejection sampling? If (as it typical) you can spare some rejected pseudo entropy, it would have zero bias. $\endgroup$ – Paul Uszak Sep 1 '17 at 13:34
  • 1
    $\begingroup$ @Paul Uszak: can you expand on your idea to use rejection sampling? For a start, is it as a method of password-generation (and then I do not immediately see the method that you have in mind); or in order to test correctness of a method of password-generation (and then I do not get zero bias)? $\endgroup$ – fgrieu Sep 1 '17 at 16:27
  • 1
    $\begingroup$ @Paul Uszak crypto/rand.Int(reader io.Reader, max big.Int) reads enough bytes from reader to contain max, unsets any unused bits in the most significant byte, and throws out candidates >= max. I think this is what you mean. See src/crypto/rand/util.go, line 106. $\endgroup$ – Niko Carpenter Sep 1 '17 at 17:31
  • $\begingroup$ the best way to do without loosing entropy will be, Assuming your password has all printable characters which has ascii value from 32 to 127 in integer form, and a byte can hold a value from 0-255. Generate a random byte, if its value is from 32 to 127, use it to represent a password character otherwise ignore and generate another random byte, repeat the process until you get the desired length password $\endgroup$ – abraza Sep 1 '17 at 18:34
  • $\begingroup$ Yes, that...... $\endgroup$ – Paul Uszak Sep 1 '17 at 22:12
5
$\begingroup$

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 2B 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.

$\endgroup$
4
  • $\begingroup$ @Niko Carpenter: I added pseudocode. I suggest that you remove obsolete comments; I'll do the same with this one after you had opportunity to read it. $\endgroup$ – fgrieu Sep 1 '17 at 16:23
  • $\begingroup$ The reason I am hesitant to read in one character at a time is because I ran some tests using both methods, and the one-at-a-time method consumes more bytes, even if I very the length of the password. If I wanted to generate 64 hex digits, I could do it reading only 32 bytes by reading a bit int and using arbitrary-precision arithmetic, whereas it would take 64 bytes to read in one number at a time, from 0 to 15. Maybe I'm being overly concerned about how much entropy I'm consuming. This is just meant to be a personal password generator, like you'd find in LastPass. $\endgroup$ – Niko Carpenter Sep 1 '17 at 17:10
  • 1
    $\begingroup$ I am trying to figure out what your pseudocode does. Math doesn't work well with screen readers, and I'm horrible with LaTeX, so it might take me a bit. $\endgroup$ – Niko Carpenter Sep 1 '17 at 17:12
  • $\begingroup$ @Niko Carpenter: randomness is cheap, because it comes from fast CSPRNGs; I'm taking this as an exercise of style. I'll post or link to code (we seem to have Java in common), but that might be in a few days. $\endgroup$ – fgrieu Sep 1 '17 at 19:34
0
$\begingroup$

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à.

$\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.