Bearer secrets: reset links, API keys and CSRF

// How many random bits does a bearer secret need? Three tables, all arithmetic: the same 128 bits written in four
// encodings, the time a guesser needs to hit one of many valid tokens, and what a six-digit code allows. No token is made.

const YEAR = 365.25 * 24 * 3600;
const sci = (x) => x.toExponential(1).replace('e+', 'e');
const guesses = (x) => (x < 1e6 ? Math.round(x).toLocaleString('en-US') : sci(x));
function duration(seconds) {
  if (seconds < 120) return `${seconds.toFixed(1)} seconds`;
  if (seconds < 7200) return `${(seconds / 60).toFixed(1)} minutes`;
  if (seconds < 2 * 86400) return `${(seconds / 3600).toFixed(1)} hours`;
  if (seconds < 2 * YEAR) return `${(seconds / 86400).toFixed(1)} days`;
  const years = seconds / YEAR;
  return years < 1e4 ? `${Math.round(years).toLocaleString('en-US')} years` : `${sci(years)} years`;
}

// Characters needed for 128 bits: each character carries log2(alphabet size) bits.
console.log('Characters needed for 128 bits');
for (const [name, size] of [['hex', 16], ['Base32', 32], ['Base64url', 64], ['decimal digits', 10]]) {
  const chars = Math.ceil(128 / Math.log2(size));
  console.log(`  ${name.padEnd(15)} ${String(chars).padStart(2)} characters = ${(chars * Math.log2(size)).toFixed(1)} bits`);
}

// A guess hits when it equals any one of the valid tokens, so v valid tokens cut the expected work by a factor v.
const expected = (bits, valid) => 2 ** bits / valid;

console.log('');
console.log('Time to the first hit with 100,000 valid tokens and 10,000 guesses a second');
console.log('  bits   guesses needed   time');
for (const bits of [32, 40, 64, 96, 128]) {
  const g = expected(bits, 100_000);
  console.log(`  ${String(bits).padStart(4)}   ${guesses(g).padStart(14)}   ${duration(g / 10_000)}`);
}

console.log('');
console.log('A faster guesser, and a longer token');
console.log(`  64 bits at 10 million guesses a second:    ${duration(expected(64, 100_000) / 1e7)}`);
console.log(`  128 bits at 10 trillion guesses a second:  ${duration(expected(128, 100_000) / 1e13)}`);

console.log('');
console.log('A six-digit emailed code carries 20 bits, so attempts must be limited');
for (const attempts of [1, 5, 100]) {
  console.log(`  ${String(attempts).padStart(3)} attempts allowed: chance of a hit ${((attempts / 1e6) * 100).toFixed(4)} %`);
}

Characters needed for 128 bits
  hex             32 characters = 128.0 bits
  Base32          26 characters = 130.0 bits
  Base64url       22 characters = 132.0 bits
  decimal digits  39 characters = 129.6 bits

Time to the first hit with 100,000 valid tokens and 10,000 guesses a second
  bits   guesses needed   time
    32           42,950   4.3 seconds
    40            1.1e7   18.3 minutes
    64           1.8e14   585 years
    96           7.9e23   2.5e12 years
   128           3.4e33   1.1e22 years

A faster guesser, and a longer token
  64 bits at 10 million guesses a second:    213.5 days
  128 bits at 10 trillion guesses a second:  1.1e13 years

A six-digit emailed code carries 20 bits, so attempts must be limited
    1 attempts allowed: chance of a hit 0.0001 %
    5 attempts allowed: chance of a hit 0.0005 %
  100 attempts allowed: chance of a hit 0.0100 %

// A reset link token in two parts. The selector finds the row; only a hash of the verifier is stored, and the
// verifier is compared with that hash in constant time. The byte source is injected so this run is repeatable;
// production code passes crypto.randomBytes.
import { createHash, timingSafeEqual } from 'node:crypto';

const sha256 = (bytes) => createHash('sha256').update(bytes).digest();
const b64url = (bytes) => Buffer.from(bytes).toString('base64url');

// 12 selector bytes (96 bits, public) and 32 verifier bytes (256 bits, secret): 16 and 43 characters.
function issue(db, userId, now, randomBytes) {
  const selector = b64url(randomBytes(12));
  const verifier = b64url(randomBytes(32));
  db.set(selector, { userId, verifierHash: sha256(verifier), expiresAt: now + 10 * 60, usedAt: null });
  return `${selector}.${verifier}`;
}

// Every refusal looks the same to the caller: wrong format, unknown selector and wrong verifier give one answer.
function redeem(db, token, now) {
  const [selector, verifier, ...rest] = String(token).split('.');
  if (!selector || !verifier || rest.length) return 'invalid';
  const row = db.get(selector);
  const expected = row ? row.verifierHash : Buffer.alloc(32); // hash and compare anyway: both paths do the same work
  const same = timingSafeEqual(sha256(verifier), expected);
  if (!row || !same || row.usedAt !== null || now >= row.expiresAt) return 'invalid';
  row.usedAt = now;
  return `ok: user ${row.userId}`;
}

// A repeatable stand-in for the CSPRNG: every call returns the next bytes of a SHA-256 stream, never the same twice.
function demoSource(label) {
  let n = 0;
  return (length) => {
    const out = [];
    while (out.length < length) out.push(...createHash('sha256').update(`${label}:${n++}`).digest());
    return Buffer.from(out.slice(0, length));
  };
}

const source = demoSource('demo bytes, not random');
const db = new Map();
const token = issue(db, 42, 1_000, source);
const [selector, verifier] = token.split('.');
const row = db.get(selector);

console.log(`token      ${token}`);
console.log(`selector   ${selector} (${selector.length} characters, public: safe to log)`);
console.log(`verifier   ${verifier} (${verifier.length} characters, secret)`);
console.log(`stored     selector ${selector}, SHA-256 of the verifier ${row.verifierHash.toString('hex').slice(0, 16)}…`);
console.log('');
console.log(`wrong verifier           ${redeem(db, `${selector}.${b64url(source(32))}`, 1_100)}`);
console.log(`unknown selector         ${redeem(db, `${b64url(source(12))}.${verifier}`, 1_100)}`);
console.log(`selector alone           ${redeem(db, selector, 1_100)}`);
console.log(`stored hash as verifier  ${redeem(db, `${selector}.${b64url(row.verifierHash)}`, 1_100)}`);
console.log(`the real link            ${redeem(db, token, 1_100)}`);
console.log(`the real link again      ${redeem(db, token, 1_101)}`);

const late = issue(db, 7, 2_000, source);
console.log(`a second link, 11 minutes later  ${redeem(db, late, 2_000 + 11 * 60)}`);

token      TgRfhjizfmCLMBbX.KlAIY8oyoxpfaWu41evjyLSLIi0IkShz40xJ4YhCBS4
selector   TgRfhjizfmCLMBbX (16 characters, public: safe to log)
verifier   KlAIY8oyoxpfaWu41evjyLSLIi0IkShz40xJ4YhCBS4 (43 characters, secret)
stored     selector TgRfhjizfmCLMBbX, SHA-256 of the verifier db22b437f0370c96…

wrong verifier           invalid
unknown selector         invalid
selector alone           invalid
stored hash as verifier  invalid
the real link            ok: user 42
the real link again      invalid
a second link, 11 minutes later  invalid

"""Two password-reset stores and the same eight checks. WeakResets is a toy made for this page; FixedResets is the design."""
import base64
import hashlib
import hmac
import random
import secrets

TTL = 10 * 60  # a reset link lives 10 minutes


def b64url(raw):
    return base64.urlsafe_b64encode(raw).rstrip(b"=").decode()


class WeakResets:
    """Seeds a generator with the clock, keeps the token as text, never expires it and never ends it."""

    def __init__(self):
        self.rows = {}  # token -> user

    def issue(self, user, now):
        token = f"{random.Random(int(now)).getrandbits(32):08x}"  # 32 bits, a function of the second
        self.rows[token] = user
        return token

    def redeem(self, token, now):
        return self.rows.get(token)

    def change_password(self, user):
        pass

    def stored_text(self):
        return " ".join(self.rows)

    def secret_part(self, token):
        return token


class FixedResets:
    """A selector finds the row, only a hash of the verifier is stored, links expire and work once."""

    def __init__(self):
        self.rows = {}  # selector -> row

    def issue(self, user, now):
        self.end_all(user)  # a newer request ends the older links
        selector = b64url(secrets.token_bytes(12))
        verifier = b64url(secrets.token_bytes(32))
        self.rows[selector] = {"user": user, "hash": hashlib.sha256(verifier.encode()).digest(), "expires": now + TTL}
        return f"{selector}.{verifier}"

    def redeem(self, token, now):
        selector, _, verifier = token.partition(".")
        row = self.rows.get(selector)
        if row is None or not verifier:
            return None
        same = hmac.compare_digest(hashlib.sha256(verifier.encode()).digest(), row["hash"])
        if not same or now >= row["expires"]:
            return None
        del self.rows[selector]  # single use: the row goes in the same step as the check
        return row["user"]

    def end_all(self, user):
        self.rows = {s: r for s, r in self.rows.items() if r["user"] != user}

    def change_password(self, user):
        self.end_all(user)

    def stored_text(self):
        return " ".join(f"{s} {r['hash'].hex()}" for s, r in self.rows.items())

    def secret_part(self, token):
        return token.partition(".")[2]


def clock_guess(now):
    """What someone who knows only the second of the request can compute."""
    return f"{random.Random(int(now)).getrandbits(32):08x}"


def not_from_the_clock(store):
    return store.issue("asha", 1_000) != clock_guess(1_000)


def nothing_usable_stored(store):
    token = store.issue("asha", 1_000)
    return store.secret_part(token) not in store.stored_text()


def works_once(store):
    return store.redeem(store.issue("asha", 1_000), 1_001) == "asha"


def second_use_refused(store):
    token = store.issue("asha", 1_000)
    store.redeem(token, 1_001)
    return store.redeem(token, 1_002) is None


def expires_at_ten_minutes(store):
    early = store.redeem(store.issue("asha", 1_000), 1_000 + TTL - 1)
    late = store.redeem(store.issue("ravi", 1_000), 1_000 + TTL)
    return early == "asha" and late is None


def changed_token_refused(store):
    return store.redeem(store.issue("asha", 1_000)[:-1] + "x", 1_001) is None


def newer_request_ends_older(store):
    older = store.issue("asha", 1_000)
    store.issue("asha", 1_001)
    return store.redeem(older, 1_002) is None


def password_change_ends_links(store):
    token = store.issue("asha", 1_000)
    store.change_password("asha")
    return store.redeem(token, 1_002) is None


CHECKS = [
    ("the token cannot be derived from the clock", not_from_the_clock),
    ("the store holds no usable token", nothing_usable_stored),
    ("a link works once", works_once),
    ("the second use is refused", second_use_refused),
    ("it works at 9:59 and not at 10:00", expires_at_ten_minutes),
    ("a changed token is refused", changed_token_refused),
    ("a newer request ends the older link", newer_request_ends_older),
    ("a password change ends open links", password_change_ends_links),
]

weak_passed = fixed_passed = 0
print(f"{'check':44} {'weak':>5} {'fixed':>6}")
for name, check in CHECKS:
    weak, fixed = check(WeakResets()), check(FixedResets())
    weak_passed, fixed_passed = weak_passed + weak, fixed_passed + fixed
    print(f"{name:44} {'ok' if weak else 'FAIL':>5} {'ok' if fixed else 'FAIL':>6}")
print(f"{'passed':44} {weak_passed:>3}/8 {fixed_passed:>4}/8")

check                                         weak  fixed
the token cannot be derived from the clock    FAIL     ok
the store holds no usable token               FAIL     ok
a link works once                               ok     ok
the second use is refused                     FAIL     ok
it works at 9:59 and not at 10:00             FAIL     ok
a changed token is refused                      ok     ok
a newer request ends the older link           FAIL     ok
a password change ends open links             FAIL     ok
passed                                         2/8    8/8

"""An API key with a prefix, 256 random bits and a CRC-32 checksum; what the server keeps; and a log scanner."""
import hashlib
import re
import zlib

ALPHABET = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz"
PREFIX = "demo_live_"
BODY, CHECK = 43, 6  # 62**43 is more than 2**256, and 62**6 is more than 2**32


def base62(number, width):
    digits = []
    for _ in range(width):
        number, digit = divmod(number, 62)
        digits.append(ALPHABET[digit])
    return "".join(reversed(digits))


def checksum(text):
    return base62(zlib.crc32(text.encode()), CHECK)


def mint(random_bytes):
    body = base62(int.from_bytes(random_bytes(32), "big"), BODY)
    return PREFIX + body + checksum(PREFIX + body)


def has_valid_checksum(key):
    return key[-CHECK:] == checksum(key[:-CHECK])


def record_for(key):
    """What the server stores: never the key, only a digest to look it up by and enough to show it in a list."""
    return {"prefix": PREFIX, "last4": key[-4:], "sha256": hashlib.sha256(key.encode()).hexdigest()}


# A repeatable stand-in for the CSPRNG: the bytes of a SHA-256 chain, never the same twice.
chain = hashlib.sha256(b"demo bytes, not random").digest()


def demo_bytes(length):
    global chain
    chain = hashlib.sha256(chain).digest()
    return chain[:length]


key = mint(demo_bytes)
print(f"key      {key}  ({len(key)} characters)")
print(f"parts    prefix {PREFIX}, {BODY} random characters (256 bits from 32 bytes), checksum {key[-CHECK:]}")
print(f"stored   {record_for(key)}")

# A scanner finds anything shaped like a key, then keeps only the strings whose checksum is right.
SCANNER = re.compile(rf"demo_(?:live|test)_[0-9A-Za-z]{{{BODY + CHECK}}}(?![0-9A-Za-z])")
look_alike = key[:-1] + ("0" if key[-1] != "0" else "1")  # the same key with its last character changed
lines = [
    f"GET /v1/items 200 api_key={key}",
    f"retrying with {look_alike}",
    "GET /v1/items 200 request_id=7f3a",
]
print()
for line in lines:
    found = SCANNER.findall(line)
    if not found:
        print("scanner  no key in this line")
    for candidate in found:
        verdict = "valid checksum: report it and revoke the key" if has_valid_checksum(candidate) else "checksum fails: drop it, no call to the issuer"
        print(f"scanner  {candidate[:14]}…{candidate[-4:]}  {verdict}")

key      demo_live_KjaSPwuBQ09WXl2VxjaLrJvVCJq2oT8vu4ryIpKL6it1EuvH2  (59 characters)
parts    prefix demo_live_, 43 random characters (256 bits from 32 bytes), checksum 1EuvH2
stored   {'prefix': 'demo_live_', 'last4': 'uvH2', 'sha256': '6793af7c81428b22604a2f54071d653c2869912e5611a1100a630cbf55beedc0'}

scanner  demo_live_KjaS…uvH2  valid checksum: report it and revoke the key
scanner  demo_live_KjaS…uvH0  checksum fails: drop it, no call to the issuer
scanner  no key in this line

// The same session in three cookies: an opaque ID, a signed value and an encrypted value. For each: how big the cookie
// is, whether the person holding it can read it, what a changed cookie does, and what a logout on the server does.
import { createCipheriv, createDecipheriv, createHash, createHmac, timingSafeEqual } from 'node:crypto';

const b64url = (bytes) => Buffer.from(bytes).toString('base64url');
const fromB64url = (text) => Buffer.from(text, 'base64url');
const data = JSON.stringify({ sub: 'u_1042', role: 'editor', exp: 1_800 });

// A repeatable stand-in for the CSPRNG (SHA-256 of a counter); production code uses crypto.randomBytes.
let n = 0;
const demoBytes = (length) => createHash('sha256').update(`demo ${n++}`).digest().subarray(0, length);
const signingKey = demoBytes(32);
const encryptionKey = demoBytes(32); // a second key: one key is never used for two jobs

// 1. Opaque: the cookie is only a name; the data stays in the server's table.
const table = new Map();
const opaqueId = b64url(demoBytes(24));
table.set(opaqueId, data);
const opaqueOpen = (cookie) => table.get(cookie) ?? null;

// 2. Signed: the data travels in the cookie, readable, and an HMAC says nobody changed it.
const mac = (payload) => createHmac('sha256', signingKey).update(payload).digest();
const signedCookie = `${b64url(data)}.${b64url(mac(b64url(data)))}`;
function signedOpen(cookie) {
  const [payload, tag, ...rest] = cookie.split('.');
  if (!payload || !tag || rest.length) return null;
  const given = fromB64url(tag);
  const want = mac(payload);
  return given.length === want.length && timingSafeEqual(given, want) ? fromB64url(payload).toString() : null;
}

// 3. Encrypted: AES-256-GCM hides the data and detects changes. The 12-byte nonce is new for every cookie.
function seal(text) {
  const nonce = demoBytes(12);
  const cipher = createCipheriv('aes-256-gcm', encryptionKey, nonce);
  const body = Buffer.concat([cipher.update(text, 'utf8'), cipher.final()]);
  return b64url(Buffer.concat([nonce, body, cipher.getAuthTag()]));
}
function encryptedOpen(cookie) {
  const raw = fromB64url(cookie);
  if (raw.length < 12 + 16) return null;
  try {
    const decipher = createDecipheriv('aes-256-gcm', encryptionKey, raw.subarray(0, 12));
    decipher.setAuthTag(raw.subarray(raw.length - 16));
    return Buffer.concat([decipher.update(raw.subarray(12, raw.length - 16)), decipher.final()]).toString();
  } catch {
    return null;
  }
}
const encryptedCookie = seal(data);

const flip = (cookie) => cookie.slice(0, 10) + (cookie[10] === 'A' ? 'B' : 'A') + cookie.slice(11);
const readable = (cookie) => (fromB64url(cookie.split('.')[0]).toString().startsWith('{') ? 'yes' : 'no');
const designs = [
  ['opaque', opaqueId, opaqueOpen],
  ['signed', signedCookie, signedOpen],
  ['encrypted', encryptedCookie, encryptedOpen],
];
const verdict = (open, cookie, accepted) => (open(cookie) === null ? 'refused' : accepted);

console.log(`the data: ${data} (${data.length} characters)`);
console.log('');
console.log('design     cookie size   holder can read it   one changed character   after logout on the server');
const changed = designs.map(([, cookie, open]) => verdict(open, flip(cookie), 'ACCEPTED'));
table.delete(opaqueId); // the logout, on the server: for the opaque design this one line is the whole revocation
designs.forEach(([name, cookie, open], i) => {
  const size = `${String(cookie.length).padStart(4)} chars`;
  console.log(`${name.padEnd(10)} ${size}     ${readable(cookie).padEnd(20)} ${changed[i].padEnd(23)} ${verdict(open, cookie, 'still accepted')}`);
});

the data: {"sub":"u_1042","role":"editor","exp":1800} (43 characters)

design     cookie size   holder can read it   one changed character   after logout on the server
opaque       32 chars     no                   refused                 refused
signed      102 chars     yes                  refused                 still accepted
encrypted    95 chars     no                   refused                 still accepted

// A CSRF token the server can recompute: HMAC-SHA-256 over the session ID and a random value, with the length of
// each field written in front of it (the construction of the OWASP CSRF Prevention Cheat Sheet).
import { createHash, createHmac, timingSafeEqual } from 'node:crypto';

// A repeatable stand-in for the CSPRNG (SHA-256 blocks of a counter); production code uses crypto.randomBytes.
let n = 0;
function demoBytes(length) {
  const out = [];
  for (let block = 0; out.length < length; block++) out.push(...createHash('sha256').update(`demo ${n}:${block}`).digest());
  n++;
  return Buffer.from(out.slice(0, length));
}
const secret = demoBytes(32); // the server's CSRF key, never sent anywhere

const framed = (sessionId, random) => `${sessionId.length}!${sessionId}!${random.length}!${random}`;
const unframed = (sessionId, random) => `${sessionId}!${random}`;
const hmacHex = (message) => createHmac('sha256', secret).update(message).digest('hex');

function issue(sessionId) {
  const random = demoBytes(64).toString('hex'); // 64 random bytes as 128 hex characters
  return `${hmacHex(framed(sessionId, random))}.${random}`; // the session ID itself is not in the token
}

function accepts(sessionId, token) {
  if (typeof token !== 'string' || !/^[0-9a-f]{64}\.[0-9a-f]{128}$/.test(token)) return false;
  const [given, random] = token.split('.');
  return timingSafeEqual(Buffer.from(given, 'hex'), Buffer.from(hmacHex(framed(sessionId, random)), 'hex'));
}

const mine = 'sess_Zm9vYmFy';
const theirs = 'sess_YmF6cXV4';
const token = issue(mine);
const [mac, random] = token.split('.');
const word = (ok) => (ok ? 'accepted' : 'refused');

console.log(`token   ${mac.slice(0, 16)}….${random.slice(0, 16)}…  (${token.length} characters: 64 for the HMAC, a dot, 128 for the random value)`);
console.log('');
console.log(`own session, own token     ${word(accepts(mine, token))}`);
console.log(`another session's token    ${word(accepts(mine, issue(theirs)))}`);
console.log(`random value changed       ${word(accepts(mine, `${mac}.${'0'.repeat(128)}`))}`);
console.log(`HMAC changed               ${word(accepts(mine, `${'0'.repeat(64)}.${random}`))}`);
console.log(`upper-case hex             ${word(accepts(mine, token.toUpperCase()))}`);
console.log(`no token                   ${word(accepts(mine, undefined))}`);

console.log('');
console.log('Why each length goes into the message: two different pairs of (session, random value), one string.');
const [s1, r1, s2, r2] = ['a!b', 'c', 'a', 'b!c'];
console.log(`  without lengths  "${unframed(s1, r1)}" and "${unframed(s2, r2)}"  same HMAC: ${hmacHex(unframed(s1, r1)) === hmacHex(unframed(s2, r2))}`);
console.log(`  with lengths     "${framed(s1, r1)}" and "${framed(s2, r2)}"  same HMAC: ${hmacHex(framed(s1, r1)) === hmacHex(framed(s2, r2))}`);

token   53650eb61002d256….6c98a07a4d3ec236…  (193 characters: 64 for the HMAC, a dot, 128 for the random value)

own session, own token     accepted
another session's token    refused
random value changed       refused
HMAC changed               refused
upper-case hex             refused
no token                   refused

Why each length goes into the message: two different pairs of (session, random value), one string.
  without lengths  "a!b!c" and "a!b!c"  same HMAC: true
  with lengths     "3!a!b!1!c" and "1!a!3!b!c"  same HMAC: false