Modulo bias: the bug in most password generators

Modulo bias is the bug hiding in a great many password and token generators. You take a random number, compute random % n to pick one of n things, and some of the things come up more often than others, or never. It's easy to write, it looks correct, the output passes a glance, and it does real if usually small damage. cipher.ink's own passphrase generator had it until the day this page was written. Here's the bug in our code, the exact numbers it cost, and the fix.

The bug, in our own code

The compose page's dice button builds a passphrase from five words out of a list of 288, plus a number from 10 to 99. This is what it ran until October 23, 2026:

function gen() {
  var b = Cipher.rand(6), out = [];
  for (var i = 0; i < 5; i++) out.push(WORDS[b[i] % WORDS.length]);
  return out.join('-') + '-' + (10 + b[5] % 90);
}

Cipher.rand(6) returns six random bytes, each from 0 to 255 with every value equally likely. b[i] % 288 maps a byte to a word, and that's where it goes wrong. A byte only reaches 256 values and the list has 288 words, so words 256 to 287 could never be chosen. Thirty-two of the 288 words were impossible. The trailing number, 10 + b[5] % 90, was uneven for a subtler reason, covered next. And the identifier of every message, a 12-character code from a 57-letter alphabet, used byte % 57 in the PHP.

Why a remainder isn't uniform

Say you want a fair number from 0 to 89 and you have fair bytes (0 to 255). Compute byte % 90. Byte values 0 to 89 give 0 to 89. Values 90 to 179 give 0 to 89 again. Values 180 to 255, only 76 of them, give 0 to 75. So the numbers 0 to 75 each have three bytes mapping to them, and 76 to 89 have two. The first 76 outcomes are each 50% more likely than the last 14. Nothing was wrong with the byte. The unfairness comes from pouring 256 equal slices into 90 equal buckets, which doesn't divide evenly, and the leftover slices all land in the low buckets.

For 288 outcomes the arithmetic is blunter. 256 values can't even cover 288 buckets, so 32 buckets stay empty and the rest get one slice each. The general rule: random % n is exactly fair only when n divides the size of the random range.

What it cost

Entropy, counted in bits, is the right measure of the damage, because it says how much easier an attacker's job got compared with the ideal. scripts/examples/modulo-bias.mjs computes the exact entropy of each biased choice and simulates ten million draws of the old and new methods:

Over a whole passphrase (five words and a number) the loss was 0.86 bits out of 47.34. An attacker who knew about the bias would need about 55% as many guesses on average as one who didn't, an edge of less than one bit. Over a 12-character message id the loss was 0.11 bits of 69.99. That's small, which is why nothing looked wrong. But a small flaw in something meant to be uniform is still a flaw, and the missing words turn up as soon as anyone counts. In ten million simulated draws of the old method, words 256 to 287 were drawn zero times, while every other word came up about 39,000 times. The fixed method gave every word between 34,136 and 35,354 draws, around the expected 34,722.

You can watch the same effect live. The randomness tool has a histogram, and ticking naive method makes the first values twice as likely as the rest.

The fix: rejection sampling

To pick fairly from n outcomes, draw from a range much bigger than n, find the largest multiple of n that fits in it, and throw away any draw at or above that, drawing again. What remains divides evenly, so every outcome gets exactly the same number of chances. That's rejection sampling, and the redraws are rare. Every generator on this site now runs this code:

function randInt(n) {
  var lim = Math.floor(4294967296 / n) * n, x = new Uint32Array(1);
  do C.getRandomValues(x); while (x[0] >= lim);
  return x[0] % n;
}

function gen() {
  var out = [];
  for (var i = 0; i < 5; i++) out.push(WORDS[Cipher.randInt(WORDS.length)]);
  return out.join('-') + '-' + (10 + Cipher.randInt(90));
}

It draws a 32-bit number from crypto.getRandomValues. lim is the largest multiple of n not above 2³², and a draw at or above it loops and goes again. For 288 words, 2³² holds 14,913,080 whole groups of 288, so only the top 256 draws out of 4.29 billion, about one in 16.8 million, get rejected. Using 32 bits instead of 8 makes the draw fast and the rejection rare, and the answer is exact either way. The PHP that makes message ids does the same with a byte: it skips any byte of 228 or more (228 is the largest multiple of 57 below 256), as the comment in ci_new_id() says.

Other ways to get it wrong

• Scaling a float. Math.floor(Math.random() * n) has a similar, much smaller bias, and Math.random() isn't a secure source in the first place (see random numbers in the browser).
• Shuffling with a biased pick. A Fisher-Yates shuffle needs a fair integer at every step. Feed it a biased one and some permutations get likelier than others.
• Requiring one of every kind. The easy way to satisfy "at least one digit and one symbol" is to place one of each and fill in the rest, which skews the distribution. The password generator draws a whole password and redraws if a kind is missing, so every valid password is equally likely, and it counts the exact cost.

What it taught us

The old test never asked the question that finds this bug: can every outcome happen? The suite now draws 288,000 values from randInt(288) and requires that every word turns up and that none sits more than about 30% off its expected count. Test a generator on its distribution, since "looks random" proves little. And publish the fix. The history is in the history of cipher.ink, and the code is in the annotated source.

The generated passphrase is now 5 words from a list of 288, plus a number from 10 to 99, which is 47.3 bits, computed from the list the page really uses.