Random tokens, UUIDs and unbiased sampling

A version 4 UUID has 122 random bits, enough that a trillion of them repeat with a chance of about 10⁻¹³, and yet RFC 9562 says UUIDs must not be used as security capabilities, the very job of a password-reset link. Being unique and being impossible to guess are different jobs, and an identifier can fail the second while passing the first.

This lesson sorts out the jobs. You decide when a UUID is acceptable and when a secret token is required, work out how many characters a token needs in hex, Base32, Base58 or Base64url, measure the modulo bias that byte % 10 creates and remove it with rejection sampling, and estimate two different risks for random identifiers: that two collide, and that someone guesses one. A two-step code lab at the end builds an unbiased number and an unbiased string.

A UUID names a record; a secret token proves something

RFC 9562 defines the UUID formats in use today. A version 4 UUID is 128 bits with 6 of them fixed: 4 bits say “version 4” and 2 say which variant of the format it is, which leaves 122 random bits. A version 7 UUID starts with the time in milliseconds, so that new ones sort after old ones and inserts stay close together in a database index: RFC 9562 reports that random keys such as version 4 have poor index locality, with differences of an order of magnitude or more. The program takes one of each apart:

"""Version 4 and version 7 UUIDs taken apart: which bits are fixed, which are random, and what a v7 tells about itself."""
import time
import uuid

v4 = uuid.uuid4()
print(f"uuid4: version {v4.version}, variant RFC 4122/9562: {v4.variant == uuid.RFC_4122}")
print(f"  the 13th hex digit is always 4: {str(v4)[14] == '4'}; the 17th is one of 8, 9, a, b: {str(v4)[19] in '89ab'}")
print(f"  random bits: {128 - 4 - 2} of 128")

before = time.time_ns() // 1_000_000
first, second = uuid.uuid7(), uuid.uuid7()
after = time.time_ns() // 1_000_000
stamp = int(first.hex[:12], 16)  # the first 48 bits: milliseconds since 1970
print(f"uuid7: version {first.version}, variant RFC 4122/9562: {first.variant == uuid.RFC_4122}")
print(f"  its first 48 bits are the clock in milliseconds: {before <= stamp <= after}")
print(f"  a later uuid7 sorts after it: {second > first}")
print(f"  bits that are neither clock nor fixed: {128 - 48 - 4 - 2} of 128")

uuid4: version 4, variant RFC 4122/9562: True
  the 13th hex digit is always 4: True; the 17th is one of 8, 9, a, b: True
  random bits: 122 of 128
uuid7: version 7, variant RFC 4122/9562: True
  its first 48 bits are the clock in milliseconds: True
  a later uuid7 sorts after it: True
  bits that are neither clock nor fixed: 74 of 128

The fixed digits are visible in every UUID: the 13th hex digit is the version, and the 17th is one of 8, 9, a or b. The version 7 UUID carried the clock reading of the moment it was made, and the second one sorted after the first.

A UUID is built to be unique, not secret. RFC 9562 warns implementations against assuming that UUIDs are hard to guess, and forbids using them as security capabilities, values that grant access to whoever holds them. ASVS 5.0 adds, in requirement 11.5.1, that UUIDs fall short of its rule for values nobody may guess, which asks for a CSPRNG and 128 bits or more. Version 7 also gives away when a record was created. Python’s uuid.uuid7() uses a 42-bit counter so that UUIDs made within one millisecond stay in order, and a counter is the opposite of a secret. Node added crypto.randomUUIDv7() in 24.16.0 and Python uuid.uuid7() in 3.14; crypto.randomUUID() and uuid.uuid4() give version 4.

Which value fits depends on what holding it allows. Answer the three questions in the table:

In short: a database counter or a version 7 UUID to name records, a version 4 UUID where the order should stay hidden, and a 128-bit random token whenever holding the value grants anything.

Token length: characters times the bits each one carries

When every character is picked uniformly and independently from an alphabet of size characters, a token of length characters carries length × log₂(size) bits of entropyentropy (of a token): The number of bits an attacker has to guess. A token of L characters, each drawn uniformly and independently from an alphabet of n, carries L × log2(n) bits; a fixed part such as a prefix carries none., the number of bits an attacker must guess. A hex character carries 4 bits, a Base64url character 6, a decimal digit only 3.32. The shortest token for a target of b bits is the smallest length L with size^L ≥ 2^b, which BigInt can check exactly instead of trusting a rounded logarithm:

// How many characters a token needs for 128 bits, alphabet by alphabet, worked out exactly with BigInt:
// the smallest length L with size ** L >= 2 ** 128.
const ALPHABETS = [
  ['digits 0-9', 10],
  ['hex', 16],
  ['lowercase a-z', 26],
  ['Crockford Base32', 32],
  ['lowercase and digits', 36],
  ['Base58 (no 0, O, I, l)', 58],
  ['letters and digits (Base62)', 62],
  ['Base64url', 64],
];

function lengthFor(bits, size) {
  const target = 2n ** BigInt(bits);
  let length = 0;
  let reach = 1n;
  while (reach < target) {
    reach *= BigInt(size);
    length++;
  }
  return length;
}

console.log('alphabet                       size  characters  bits carried');
for (const [name, size] of ALPHABETS) {
  const length = lengthFor(128, size);
  const carried = (length * Math.log2(size)).toFixed(1);
  console.log(`${name.padEnd(31)}${String(size).padStart(4)}${String(length).padStart(12)}${carried.padStart(14)}`);
}
console.log(`a UUIDv4 string: 36 characters, 122 random bits`);
console.log(`a 6-digit code: 6 characters, ${(6 * Math.log2(10)).toFixed(1)} bits`);

alphabet                       size  characters  bits carried
digits 0-9                       10          39         129.6
hex                              16          32         128.0
lowercase a-z                    26          28         131.6
Crockford Base32                 32          26         130.0
lowercase and digits             36          25         129.2
Base58 (no 0, O, I, l)           58          22         128.9
letters and digits (Base62)      62          22         131.0
Base64url                        64          22         132.0
a UUIDv4 string: 36 characters, 122 random bits
a 6-digit code: 6 characters, 19.9 bits

For 128 bits, hex needs 32 characters, Crockford Base32 26, and Base58, Base62 and Base64url 22 each, while decimal digits need 39. A larger alphabet shortens the token but never adds entropy by itself: 22 Base64url characters carry 132 bits because each one carries 6. The last two lines show why a UUID string and a 6-digit code are different objects: 36 characters for 122 bits, and 6 characters for about 20.

byte mod n favours the small values unless n divides 256

A random byte takes 256 values, and 256 = 25 × 10 + 6. Map bytes to digits with byte % 10 and the six bytes 250 to 255 land on 0 to 5, so those digits come from 26 bytes each and 6 to 9 from 25: each of 0 to 5 is 4 % more likely than each of 6 to 9. This uneven result is called modulo biasmodulo bias: The unevenness left by reducing random values with %: byte % 10 gives 0 to 5 from 26 of the 256 byte values each and 6 to 9 from 25. It disappears only when the size divides the range.. The program counts it on a million seeded bytes, next to the fix of the next section, and scores both with a chi-squared statisticchi-squared statistic: A measure of how far observed counts are from expected ones: the sum of (observed - expected)^2 / expected. Scored against English letter frequencies, the lowest value marks the most English-looking text. More in “The symmetric cipher model and the Caesar cipher”:

"""Modulo bias, counted: digits from byte % 10 against digits from rejection sampling, on seeded bytes."""
import random
from collections import Counter

rng = random.Random(2026)  # a seeded simulation generator, so the counts repeat on every run; never for secrets
N = 1_000_000


def chi_squared(counts, total):
    expected = total / 10
    return sum((counts[d] - expected) ** 2 / expected for d in range(10))


every_byte = Counter(b % 10 for b in range(256))
print("each byte value 0-255 once, byte % 10:", [every_byte[d] for d in range(10)])

modulo = Counter(b % 10 for b in rng.randbytes(N))

sampled, taken, rejected = Counter(), 0, 0
while taken < N:
    for b in rng.randbytes(4096):
        if taken == N:
            break
        if b >= 250:  # 250 to 255 would favour 0 to 5: draw again
            rejected += 1
            continue
        sampled[b % 10] += 1
        taken += 1

print(f"\n{'digit':<7}{'byte % 10':>11}{'rejection':>11}")
for d in range(10):
    print(f"{d:<7}{modulo[d]:>11,}{sampled[d]:>11,}")
print("\nchi-squared (9 degrees of freedom, 5 % critical value 16.92):")
print(f"  byte % 10: {chi_squared(modulo, N):,.1f}")
print(f"  rejection: {chi_squared(sampled, N):,.1f}")
print(f"bytes rejected: {rejected:,} ({rejected / (N + rejected):.2%} of those drawn; 6 of 256 is {6 / 256:.2%})")

each byte value 0-255 once, byte % 10: [26, 26, 26, 26, 26, 26, 25, 25, 25, 25]

digit    byte % 10  rejection
0          101,706     99,325
1          101,189    100,098
2          101,865    100,032
3          101,421    100,297
4          101,452     99,908
5          101,052     99,513
6           97,837     99,929
7           97,674    100,672
8           97,725    100,330
9           98,079     99,896

chi-squared (9 degrees of freedom, 5 % critical value 16.92):
  byte % 10: 319.9
  rejection: 13.8
bytes rejected: 23,724 (2.32% of those drawn; 6 of 256 is 2.34%)

The digits 0 to 5 came up about 101,500 times each and 6 to 9 about 97,800. Against a uniform result the chi-squared score is 319.9, far above 16.92, the value a fair generator exceeds only 5 % of the time with 9 degrees of freedom (NIST’s e-Handbook table). Rejection sampling scored 13.8 on the same seeded bytes and threw away 2.32 % of them, close to the 6 in 256 the arithmetic predicts. The generator here is seeded on purpose, so the counts repeat; the bias comes from the %, whatever generator feeds it.

How much the bias matters depends on the size, and some standards accept a small one knowingly:

"""How much byte % n favours some values, for common alphabet sizes, and the bias that HOTP accepts (RFC 4226)."""
from fractions import Fraction

print(f"{'n':>4}  {'values favoured':>15}  {'how much more likely':>20}")
for n in [2, 10, 16, 26, 36, 58, 62, 64, 100]:
    low, extra = divmod(256, n)  # each value gets `low` bytes, and `extra` values get one more
    if extra == 0:
        print(f"{n:>4}  {'none':>15}  {'unbiased':>20}")
    else:
        print(f"{n:>4}  {f'{extra} of {n}':>15}  {f'{(low + 1) / low - 1:.1%}':>20}")

# HOTP (RFC 4226) turns a 31-bit number into a 6-digit code with "mod 10**6".
space, codes = 2**31, 10**6
per_code, favoured = divmod(space, codes)
best_guess = Fraction(per_code + 1, space)
print(f"\nHOTP: 2**31 = {space:,} numbers onto {codes:,} codes")
print(f"  codes below {favoured:,} come from {per_code + 1:,} numbers, the rest from {per_code:,}")
print(f"  best single guess succeeds with {float(best_guess * codes):.8f} / 10**6")

   n  values favoured  how much more likely
   2             none              unbiased
  10          6 of 10                  4.0%
  16             none              unbiased
  26         22 of 26                 11.1%
  36          4 of 36                 14.3%
  58         24 of 58                 25.0%
  62          8 of 62                 25.0%
  64             none              unbiased
 100        56 of 100                 50.0%

HOTP: 2**31 = 2,147,483,648 numbers onto 1,000,000 codes
  codes below 483,648 come from 2,148 numbers, the rest from 2,147
  best single guess succeeds with 1.00024045 / 10**6

For 62 characters, the letters and digits of Base62, byte % 62 makes 8 of the characters 25 % more likely, and for 100 values 56 of them become 50 % more likely. Sizes that divide 256, such as 16 and 64, have no bias at all. HOTP, the one-time-password standard of RFC 4226, reduces a 31-bit number modulo 10⁶, so some codes are a little more likely than others; its Appendix A puts the best guess at 1.00024045 in a million, which the program reproduces, and the standard accepts that because it limits guesses anyway.

Rejection sampling: throw away the values that break the tie

The fix is to use only values that split evenly, which is called rejection samplingrejection sampling: Drawing again whenever a random value falls at or above the largest multiple of the size you need, so that every result comes from the same number of values and is exactly uniform.. The Handbook of Applied Cryptography describes it for random bits turned into numbers: if the result is too large, discard it and draw again. For digits, keep a byte only if it is below 250, the largest multiple of 10 that fits in a byte; then every digit comes from exactly 25 bytes. Step through one draw in which the first byte is thrown away:

A second form needs no division at all: keep only as many low bits as the bound needs, 4 bits for a bound of 10, and draw again whenever the value is the bound or more. It throws away more draws for some bounds, but it works the same way for a bound of 1,000 or of 2³², and the first step of the code lab uses it. Either way the result is exactly uniform, and the expected number of draws stays below 2.

You rarely need to write it yourself. Node’s crypto.randomInt(min, max) returns an integer in the range and its documentation says it avoids modulo bias, for ranges below 2⁴⁸; Python’s secrets.randbelow(n) and secrets.choice(seq) give uniform results from the system generator. Write your own only where no such call exists, as in a format that picks characters from its own alphabet, and test it on every byte value, as the code lab does.

Collisions and guesses are two different questions

A random identifier can fail in two ways, and they need different sums. A collision is two identifiers that come out the same, which matters for uniqueness; by the birthday boundbirthday bound: The rule that random values of b bits start to repeat after about 2^(b/2) of them. It is why a 256-bit hash gives about 128 bits of collision resistance and why random nonces have usage limits. More in “Security levels, key sizes and attack cost” its chance grows with the square of the number made. A guess is someone hitting any identifier that is live, which matters for security; its chance grows with the number of live values times the number of guesses. The program works out both for typical cases:

"""Two questions about random identifiers: will two of them collide, and can someone guess a valid one?"""
import math


def any_duplicate(n, bits):
    """Birthday bound: the chance that n random values of `bits` bits are not all different."""
    return -math.expm1(-n * (n - 1) / 2 ** (bits + 1))


def guess_one(valid, guesses, bits):
    """The chance that `guesses` random tries hit any of `valid` live values out of 2**bits."""
    return -math.expm1(guesses * math.log1p(-valid / 2**bits))


print("Will two collide?                         chance of any duplicate")
for label, n, bits in [
    ("10**5 codes of 6 Base32 characters", 10**5, 30),
    ("10**9 IDs of 64 random bits", 10**9, 64),
    ("10**12 version 4 UUIDs", 10**12, 122),
    ("10**12 tokens of 128 bits", 10**12, 128),
]:
    print(f"  {label:<38}{any_duplicate(n, bits):.2e}")

print("\nCan someone guess one?                    chance of a hit")
year_of_guesses = 10**6 * 365  # a million tries a day for a year
for label, valid, guesses, bits in [
    ("6-digit code, 100 tries, then locked", 1, 100, math.log2(10**6)),
    ("6-digit code, a year with no limit", 1, year_of_guesses, math.log2(10**6)),
    ("10**9 live 64-bit tokens, a year", 10**9, year_of_guesses, 64),
    ("10**9 live 128-bit tokens, a year", 10**9, year_of_guesses, 128),
]:
    print(f"  {label:<38}{guess_one(valid, guesses, bits):.2e}")

Will two collide?                         chance of any duplicate
  10**5 codes of 6 Base32 characters    9.91e-01
  10**9 IDs of 64 random bits           2.67e-02
  10**12 version 4 UUIDs                9.40e-14
  10**12 tokens of 128 bits             1.47e-15

Can someone guess one?                    chance of a hit
  6-digit code, 100 tries, then locked  1.00e-04
  6-digit code, a year with no limit    1.00e+00
  10**9 live 64-bit tokens, a year      1.96e-02
  10**9 live 128-bit tokens, a year     1.07e-21

A hundred thousand gift codes of 6 Base32 characters, 30 bits, almost surely repeat: the chance is 0.99. A billion 64-bit identifiers repeat with a chance of 2.67 %, and a trillion version 4 UUIDs with 9.4 × 10⁻¹⁴, which is why UUIDs work well as names. Guessing is the second half of the output. With a billion live 64-bit tokens and a million guesses a day, a year of guessing hits one with a chance of about 2 %; with 128-bit tokens it is 10⁻²¹, which is why secrets get 128 bits even where 64 would be unique enough.

Short codes that people type, such as the six digits of a one-time password, carry about 20 bits by design, and they stay safe only because the verifier limits the guesses and the code expires. RFC 4226 asks the server to throttle failed attempts, and NIST SP 800-63B-4 caps consecutive failures at 100 before the authenticator is disabled, requires rate limiting for any such secret under 64 bits, and gives an out-of-band code at most 10 minutes. With 100 tries the chance of hitting a 6-digit code is 1 in 10,000; with a year of unlimited tries it is certain.

Practise: an unbiased number and an unbiased string

Two exercises with sample tests on this page build what every token generator needs. The first returns a uniform number below any bound up to 2³² from an injected byte source, keeping only the bits the bound needs and drawing again when the value is too large. The second makes a string from any alphabet of up to 256 characters with the cut-off of this lesson, held to an exhaustive test over every byte value:

def uniform_int(max_exclusive, source):
    """A whole number from 0 to max_exclusive - 1, every one equally likely. source(n) returns n random bytes."""
    return source(1)[0] % max_exclusive  # modulo bias, and never above 255

from collections import Counter

from uniform_int import uniform_int


class Bytes:
    """A test source that hands out the given bytes in order and counts how many it gave."""

    def __init__(self, data):
        self.data = bytes(data)
        self.given = 0

    def __call__(self, n):
        chunk = self.data[self.given : self.given + n]
        assert len(chunk) == n, "the source ran out: too many bytes were asked for"
        self.given += n
        return chunk


def raises_value_error(call):
    try:
        call()
    except ValueError:
        return True
    return False


def test_every_byte_once_gives_a_flat_count():
    """bound 10 over the bytes 0-249: each digit 16 times, and the 90 bytes with low bits 10-15 skipped"""
    source = Bytes(range(256))
    counts = Counter(uniform_int(10, source) for _ in range(160))
    assert [counts[d] for d in range(10)] == [16] * 10
    assert source.given == 250


def test_high_bytes_are_never_used_as_they_are():
    """bound 10: the bytes 250-255 are all refused, then 7 is kept"""
    source = Bytes([250, 251, 252, 253, 254, 255, 7])
    assert uniform_int(10, source) == 7
    assert source.given == 7


def test_rejection_branch():
    """bound 10: byte 12 has low bits 12, too big, so a second byte is drawn"""
    source = Bytes([12, 3])
    assert uniform_int(10, source) == 3
    assert source.given == 2


def test_two_bytes_big_endian():
    """bound 1000 needs 10 bits in 2 bytes: 0x03E8 (1000) is rejected, 0x03E7 (999) kept"""
    source = Bytes([0x03, 0xE8, 0x03, 0xE7])
    assert uniform_int(1000, source) == 999
    assert source.given == 4


def test_ends_of_the_range():
    """bound 1 needs no byte; bound 2**32 keeps all 32 bits"""
    source = Bytes([])
    assert uniform_int(1, source) == 0
    assert source.given == 0
    assert uniform_int(2**32, Bytes([0xFF, 0xFF, 0xFF, 0xFF])) == 2**32 - 1
    assert uniform_int(2**32, Bytes([0x12, 0x34, 0x56, 0x78])) == 0x12345678


def test_bad_bounds():
    """0, -5, 2**32 + 1 and 2.5 are refused"""
    for bad in [0, -5, 2**32 + 1, 2.5]:
        assert raises_value_error(lambda: uniform_int(bad, Bytes([1, 2, 3, 4]))), f"{bad} should raise ValueError"

/** A whole number from 0 to maxExclusive - 1, every one equally likely. source(bytes) fills a Uint8Array. */
export function uniformInt(maxExclusive, source) {
  const byte = source(new Uint8Array(1))[0];
  return byte % maxExclusive; // modulo bias, and never above 255
}

import { test, assert } from 'mysmartcopilot:test';
import { uniformInt } from './uniform_int.mjs';

// A test source that hands out the given bytes in order and counts how many it gave.
function bytesSource(list) {
  const state = { given: 0 };
  state.fill = (bytes) => {
    if (state.given + bytes.length > list.length) throw new Error('the source ran out: too many bytes were asked for');
    for (let i = 0; i < bytes.length; i++) bytes[i] = list[state.given + i];
    state.given += bytes.length;
    return bytes;
  };
  return state;
}

test('bound 10 over the bytes 0-249: each digit 16 times, and the 90 bytes with low bits 10-15 skipped', () => {
  const source = bytesSource(Array.from({ length: 256 }, (_, i) => i));
  const counts = Array(10).fill(0);
  for (let i = 0; i < 160; i++) counts[uniformInt(10, source.fill)]++;
  assert.deepEqual(counts, Array(10).fill(16));
  assert.equal(source.given, 250);
});

test('bound 10: the bytes 250-255 are all refused, then 7 is kept', () => {
  const source = bytesSource([250, 251, 252, 253, 254, 255, 7]);
  assert.equal(uniformInt(10, source.fill), 7);
  assert.equal(source.given, 7);
});

test('bound 10: byte 12 has low bits 12, too big, so a second byte is drawn', () => {
  const source = bytesSource([12, 3]);
  assert.equal(uniformInt(10, source.fill), 3);
  assert.equal(source.given, 2);
});

test('bound 1000 needs 10 bits in 2 bytes: 0x03E8 (1000) is rejected, 0x03E7 (999) kept', () => {
  const source = bytesSource([0x03, 0xe8, 0x03, 0xe7]);
  assert.equal(uniformInt(1000, source.fill), 999);
  assert.equal(source.given, 4);
});

test('bound 1 needs no byte; bound 2**32 keeps all 32 bits', () => {
  const empty = bytesSource([]);
  assert.equal(uniformInt(1, empty.fill), 0);
  assert.equal(empty.given, 0);
  assert.equal(uniformInt(2 ** 32, bytesSource([0xff, 0xff, 0xff, 0xff]).fill), 2 ** 32 - 1);
  assert.equal(uniformInt(2 ** 32, bytesSource([0x12, 0x34, 0x56, 0x78]).fill), 0x12345678);
});

test('0, -5, 2**32 + 1 and 2.5 are refused', () => {
  for (const bad of [0, -5, 2 ** 32 + 1, 2.5]) assert.throws(() => uniformInt(bad, bytesSource([1, 2, 3, 4]).fill), `${bad} should throw`);
});

def random_string(length, alphabet, source):
    """length characters from alphabet, each equally likely. source(1) returns one random byte."""
    return "".join(alphabet[source(1)[0] % len(alphabet)] for _ in range(length))  # modulo bias

from collections import Counter

from random_string import random_string

BASE62 = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz"


class Bytes:
    """A test source that hands out the given bytes, one per call, and counts them."""

    def __init__(self, data):
        self.data = list(data)
        self.given = 0

    def __call__(self, n):
        assert n == 1, "ask for one byte at a time"
        assert self.given < len(self.data), "the source ran out: too many bytes were asked for"
        self.given += 1
        return bytes([self.data[self.given - 1]])


def raises_value_error(call):
    try:
        call()
    except ValueError:
        return True
    return False


def test_every_byte_once_gives_a_flat_count():
    """the 256 byte values, shuffled: 248 Base62 characters, each exactly 4 times, and all 256 bytes used"""
    source = Bytes((3 * b + 7) % 256 for b in range(256))
    counts = Counter(random_string(248, BASE62, source))
    assert sorted(set(counts.values())) == [4]
    assert len(counts) == 62
    assert source.given == 256


def test_bytes_above_the_cut_off_are_drawn_again():
    """Base62: the bytes 248-255 are refused, then 5 gives the character 5"""
    source = Bytes([248, 249, 250, 251, 252, 253, 254, 255, 5])
    assert random_string(1, BASE62, source) == "5"
    assert source.given == 9


def test_digits():
    """10 digits: the cut-off is 250, so 250 is refused and 249 gives 9"""
    source = Bytes([250, 249, 12])
    assert random_string(2, "0123456789", source) == "92"


def test_no_rejection_for_powers_of_two():
    """16 hex digits: every byte is kept"""
    source = Bytes([255, 16, 1])
    assert random_string(3, "0123456789abcdef", source) == "f01"
    assert source.given == 3


def test_empty_and_bad_input():
    """length 0 is empty; 1 or 257 characters, a repeated one, and lengths -1 and 2.5 are refused"""
    assert random_string(0, BASE62, Bytes([])) == ""
    wide = "".join(chr(0x100 + i) for i in range(257))
    for length, alphabet in [(4, "a"), (4, wide), (4, "aab"), (-1, BASE62), (2.5, BASE62)]:
        assert raises_value_error(lambda: random_string(length, alphabet, Bytes([1] * 8))), f"{length}, {alphabet[:8]!r}"

/** length characters from alphabet, each equally likely. source(bytes) fills a Uint8Array. */
export function randomString(length, alphabet, source) {
  let out = '';
  for (let i = 0; i < length; i++) {
    const bytes = new Uint8Array(1);
    source(bytes);
    out += alphabet[bytes[0] % alphabet.length]; // modulo bias
  }
  return out;
}

import { test, assert } from 'mysmartcopilot:test';
import { randomString } from './random_string.mjs';

const BASE62 = '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz';

// A test source that hands out the given bytes, one per call, and counts them.
function bytesSource(list) {
  const state = { given: 0 };
  state.fill = (bytes) => {
    if (bytes.length !== 1) throw new Error('ask for one byte at a time');
    if (state.given >= list.length) throw new Error('the source ran out: too many bytes were asked for');
    bytes[0] = list[state.given++];
    return bytes;
  };
  return state;
}

test('the 256 byte values, shuffled: 248 Base62 characters, each exactly 4 times, and all 256 bytes used', () => {
  const source = bytesSource(Array.from({ length: 256 }, (_, b) => (3 * b + 7) % 256));
  const counts = new Map();
  for (const c of randomString(248, BASE62, source.fill)) counts.set(c, (counts.get(c) ?? 0) + 1);
  assert.equal(counts.size, 62);
  assert.deepEqual([...new Set(counts.values())], [4]);
  assert.equal(source.given, 256);
});

test('Base62: the bytes 248-255 are refused, then 5 gives the character 5', () => {
  const source = bytesSource([248, 249, 250, 251, 252, 253, 254, 255, 5]);
  assert.equal(randomString(1, BASE62, source.fill), '5');
  assert.equal(source.given, 9);
});

test('10 digits: the cut-off is 250, so 250 is refused and 249 gives 9', () => {
  assert.equal(randomString(2, '0123456789', bytesSource([250, 249, 12]).fill), '92');
});

test('16 hex digits: every byte is kept', () => {
  const source = bytesSource([255, 16, 1]);
  assert.equal(randomString(3, '0123456789abcdef', source.fill), 'f01');
  assert.equal(source.given, 3);
});

test('length 0 is empty; 1 or 257 characters, a repeated one, and lengths -1 and 2.5 are refused', () => {
  assert.equal(randomString(0, BASE62, bytesSource([]).fill), '');
  const wide = Array.from({ length: 257 }, (_, i) => String.fromCharCode(0x100 + i)).join('');
  for (const [length, alphabet] of [[4, 'a'], [4, wide], [4, 'aab'], [-1, BASE62], [2.5, BASE62]]) {
    assert.throws(() => randomString(length, alphabet, bytesSource(Array(8).fill(1)).fill), `${length}, ${alphabet.slice(0, 8)}`);
  }
});

Then practise across the five ideas: the first questions go to your weakest one, right answers earn harder ones, and anything you miss comes back before the end:

Interview questions

Warm-up (fresher to mid level): is a version 4 UUID a good password-reset token?

It is a poor choice, even though its 122 random bits are hard to guess when a secure generator made them. RFC 9562 says UUIDs must not be used as security capabilities, identifiers whose possession grants access, and that implementations should not assume they are hard to guess: the standard only recommends a secure generator for them, and version 7 puts the time inside. ASVS 5.0 requirement 11.5.1 asks for a CSPRNG and at least 128 bits for values that must not be guessed, and says UUIDs do not meet it. Use 16 or more bytes from crypto.getRandomValues or secrets.token_urlsafe(16), store only a hash of the token, make it single-use and give it a short expiry. Keep UUIDs for naming records.

Key takeaways

• A UUID is for uniqueness: version 4 has 122 random bits, version 7 starts with the time in milliseconds, and RFC 9562 forbids using either as a value whose possession grants access.
• A token of length characters from an alphabet of size carries length × log₂(size) bits: 128 bits take 32 hex, 26 Base32 or 22 Base64url characters.
• byte % n is biased unless n divides 256: byte % 10 made 0 to 5 4 % more likely, and byte % 62 makes 8 characters 25 % more likely.
• Rejection sampling removes the bias exactly by drawing again for values above the largest multiple of n, and crypto.randomInt, secrets.randbelow and secrets.choice already do it.
• Collisions grow with the square of the number of identifiers and guesses with the number of live values times the tries, so secrets get 128 bits and short codes get rate limits and a short life.