Why Random String Generators Secretly Skew — Modulo Bias and Rejection Sampling
Most random ID generators work the same way: draw a random byte, take it modulo the alphabet length, and use the remainder to pick a character. It looks perfectly safe — but if the alphabet length isn't a divisor of 256, that simple modulo operation quietly makes some characters come up slightly more often than others. This is called modulo bias. This guide walks through why the bias happens, and how rejection sampling eliminates it completely, with the actual math and the real code behind it.
1. Why modulo bias happens
When you draw a single byte from a cryptographically secure random source (crypto.getRandomValues()), you get a perfectly uniform value between 0 and 255 — 256 possible outcomes, each equally likely. The problem shows up in the next step: converting that byte into an alphabet character. If you pick the index with byte % N for an alphabet of length N, every character gets mapped exactly the same number of times only when 256 is evenly divisible by N. When N doesn't divide 256 cleanly, the "leftover" byte values — however many are left over from 256 mod N — wrap around and get mapped onto the earlier characters one extra time each, producing an uneven distribution.
2. Why this matters for security
A biased character selection makes the actual entropy slightly lower than the theoretical maximum for an alphabet of size N (log2(N) bits per character). You won't notice it looking at any single ID, but in high-security, high-volume contexts where large batches of IDs feed into statistical attacks or collision-probability calculations, that small bias eats into the theoretical safety margin. This is exactly why well-built random string libraries — including the real nanoid npm package — bake in bias-elimination logic from the start.
3. The fix: Rejection Sampling
Rejection sampling only accepts byte values that fall within the largest range that's an exact multiple of N — that is, values below Math.floor(256/N)*N — and simply discards and re-draws anything above that. Since the accepted range is always an exact multiple of N, the % N operation becomes perfectly uniform. The only cost is occasionally throwing away a byte and drawing another one; the statistical bias disappears entirely.
4. How this site's NanoID generator actually does it
The actual generation function in nanoid-generator.html implements exactly this approach:
if(buf[i]<Math.floor(256/alpha.length)*alpha.length) id+=alpha[idx];
A byte is only used to append a character when its value is below Math.floor(256/alphabet length)*alphabet length; anything at or above that is silently skipped (rejected). If the target length isn't reached yet, a while loop keeps drawing more bytes to make up the difference. This is a faithful implementation of the rejection sampling described above, and it guarantees every character comes out with exactly equal probability even for alphabets like 62 or 26 characters that don't evenly divide 256.
5. The trap of alphabets longer than 256 characters
Rejection sampling has one precondition: the alphabet length must be 256 or fewer. If the alphabet exceeds 256 characters, it goes beyond what a single byte (0–255) can represent, so the rejection filter can never let a single byte through — generation would stall indefinitely. That's why a safe implementation must always cap the alphabet length at 256 characters.
Frequently Asked Questions
Q. Is modulo bias actually a noticeable security risk?
A. For the security of any single string, it barely matters. But in high-security contexts where large-scale generation, statistical analysis, or collision-probability calculations matter, that slight drop in theoretical entropy is treated as a real flaw. That's why trustworthy libraries are designed from the ground up to eliminate the bias.
Q. If the alphabet length is a divisor of 256 (like 64 or 16 characters), is rejection sampling even needed?
A. Correct — if 256 divides evenly by the alphabet length, a plain modulo operation is already perfectly uniform. The problem only shows up with lengths like 62 or 26 that don't divide evenly.
Q. Does rejection sampling slow down generation?
A. It can slow things down very slightly, since a byte occasionally gets discarded and redrawn. But that cost is effectively negligible, and it's almost always worth paying for a truly uniform distribution.
Q. What happens if a custom alphabet has duplicate characters?
A. Duplicates are automatically collapsed down to one instance. Leaving duplicates in would artificially make that character come up more often — reintroducing the very bias that rejection sampling was designed to remove.