Encryptr.prototype.randomString Produces Biased Output

paragonie-scott commented 9 years ago

https://github.com/devgeeks/Encryptr/blob/64223f0cb4adba80c8d89f23762bba0c8dc7fa3c/src/app.js#L285-L298

See also:

devgeeks commented 9 years ago

Thanks for this. I saw the mention of this and cringed since it is a known issue (#49).

Also thanks for code example. The whole generation of passwords is going to get better soon (configurability, etc).

alanfairless commented 9 years ago

FWIW, although there is theoretically a bias, I think not practically. The relative numbers (the size of the character set, 84, and max int) are so far away from each other to be insignificant.

To explore this, here's a test that counts character frequency with the password generation code over millions of samples. When I run it, the counts for all the characters are in similar range with each other. They're maybe one ten thousandth apart, and the rankings aren't consistent from one run to the next.

So my feeling is that the current code is safe.

var length = 10000
var repetitions = 10000
var charset = "!@#$%^*()_+{}:?|,[];./~ABCDEFGHIJKLMNOPQRSTUVWXYZ" 
              + "abcdefghijklmnopqrstuvwxyz0123456789";
var counts = new Uint32Array(charset.length)

// zero the initial counts for each character
for (i = 0; i < charset.length; i++) {
    counts[i] = 0;
}

// do this many times, so we don't have to ask for more entropy than is
// available in a single call.
for (i = 0; i < repetitions; i++) {
    var values = new Uint32Array(length)
    window.crypto.getRandomValues(values);

    // increment the counts for each selected character
    for(j = 0; j < length; j++) {
      this_value = values[j] % charset.length;
      counts[this_value]++;
    }
}

// display the counts for each character
for(i = 0; i < counts.length; i++) {
    console.log(charset[i], counts[i]);
}
console.log("Done")

Sample output:

paragonie-scott commented 9 years ago

So my feeling is that the current code is safe.

To clarify: do you intend this statement as an argument against making this unbiased?

fx5 commented 9 years ago

| To explore this, here's a test that counts character frequency with the password generation code over millions of samples.

The bias is indeed too small to be visible with that number of samples. The chance for each character to become a "!" is 1.1764706112% and for all other characters it's 1.1764705880%.

You generated 10,000 passwords with 10,000 characters each. The chances that at least one of the characters is different from the characters generated by a fixed function (see below) are only 1 - (1 - 1 / 2 ** 32) ** (10000 * 10000) =~ 2.3%. So even for the 100 million characters you generated the result is most probably exactly the same as the result of an unbiased function.

For removing the bias it should be enough to generate a new random array if one of the generated values[i] was 0.

SpiderOak / Encryptr

Encryptr.prototype.randomString Produces Biased Output #171