| 1 | // The printed credentials: Crockford Base32, the checksum, and the repair |
| 2 | // that makes a mistyped character survivable. |
| 3 | // |
| 4 | // This is what a person reads off aged paper at the worst moment they will |
| 5 | // ever use this product. Pinned by vectors/contra-v1.json. |
| 6 | |
| 7 | import { sha256 } from "./kdf.js"; |
| 8 | |
| 9 | // Crockford's alphabet: no I, L, O or U. Decoding maps O to 0 and I and L to |
| 10 | // 1 — the exact confusions humans and OCR make reading print. |
| 11 | export const ALPHABET = "0123456789ABCDEFGHJKMNPQRSTVWXYZ"; |
| 12 | |
| 13 | export const TAG_ACCOUNT_KEY = "A1"; |
| 14 | export const TAG_RECOVERY = "C1"; |
| 15 | |
| 16 | const DATA_SYMBOLS = 26; |
| 17 | const CHECK_SYMBOLS = 4; |
| 18 | const CODE_SYMBOLS = 2 + DATA_SYMBOLS + CHECK_SYMBOLS; |
| 19 | |
| 20 | function symbolValue(ch) { |
| 21 | let c = ch.toUpperCase(); |
| 22 | if (c === "O") c = "0"; |
| 23 | if (c === "I" || c === "L") c = "1"; |
| 24 | const i = ALPHABET.indexOf(c); |
| 25 | return c === "" ? -1 : i; |
| 26 | } |
| 27 | |
| 28 | // normalize strips hyphens and whitespace, uppercases, and applies the |
| 29 | // O/I/L mappings. The two-character tag survives it unchanged, so callers |
| 30 | // normalise first and match the tag afterwards. |
| 31 | export function normalize(s) { |
| 32 | let out = ""; |
| 33 | for (const ch of s) { |
| 34 | if (ch === "-" || /\s/.test(ch)) continue; |
| 35 | const v = symbolValue(ch); |
| 36 | if (v < 0) throw new Error("contra: character outside the Crockford alphabet"); |
| 37 | out += ALPHABET[v]; |
| 38 | } |
| 39 | return out; |
| 40 | } |
| 41 | |
| 42 | // base32Encode packs bytes MSB-first and left-aligned, so 16 bytes become 26 |
| 43 | // symbols whose last one carries two zero pad bits. |
| 44 | // |
| 45 | // Byte packing rather than Crockford's big-integer form: no language should |
| 46 | // need a bignum to read a recovery code, and this module is capped at 300 |
| 47 | // lines by test. |
| 48 | export function base32Encode(b) { |
| 49 | const n = Math.ceil((b.length * 8) / 5); |
| 50 | let out = ""; |
| 51 | for (let i = 0; i < n; i++) { |
| 52 | const bit = i * 5; |
| 53 | const by = bit >> 3; |
| 54 | const off = bit & 7; |
| 55 | let v = b[by] << 8; |
| 56 | if (by + 1 < b.length) v |= b[by + 1]; |
| 57 | out += ALPHABET[(v >> (11 - off)) & 0x1f]; |
| 58 | } |
| 59 | return out; |
| 60 | } |
| 61 | |
| 62 | // base32Decode is strict: it rejects a non-zero pad in the final symbol, so |
| 63 | // every value has exactly one encoding. Without that, two different strings |
| 64 | // decode to one key and the checksum stops meaning what it says. |
| 65 | export function base32Decode(sym, nbytes) { |
| 66 | if (sym.length !== Math.ceil((nbytes * 8) / 5)) { |
| 67 | throw new Error("contra: wrong number of symbols"); |
| 68 | } |
| 69 | const out = new Uint8Array(nbytes); |
| 70 | let acc = 0; |
| 71 | let bits = 0; |
| 72 | let o = 0; |
| 73 | for (const ch of sym) { |
| 74 | const v = symbolValue(ch); |
| 75 | if (v < 0) throw new Error("contra: character outside the Crockford alphabet"); |
| 76 | acc = (acc << 5) | v; |
| 77 | bits += 5; |
| 78 | if (bits >= 8) { |
| 79 | bits -= 8; |
| 80 | out[o++] = (acc >> bits) & 0xff; |
| 81 | } |
| 82 | } |
| 83 | if ((acc & ((1 << bits) - 1)) !== 0) { |
| 84 | throw new Error("contra: non-zero pad bits in the final symbol"); |
| 85 | } |
| 86 | return out; |
| 87 | } |
| 88 | |
| 89 | // checksum20 is the first 20 bits, MSB-first, of SHA-256 over the raw |
| 90 | // payload bytes — not over the string. Twenty bits is enough to catch a |
| 91 | // mistyped character and small enough to fit four symbols on a printed line. |
| 92 | export async function checksum20(payload) { |
| 93 | const d = await sha256(payload); |
| 94 | return (d[0] << 12) | (d[1] << 4) | (d[2] >> 4); |
| 95 | } |
| 96 | |
| 97 | function checksumSymbols(c) { |
| 98 | let out = ""; |
| 99 | for (let i = 0; i < CHECK_SYMBOLS; i++) out += ALPHABET[(c >> (15 - 5 * i)) & 0x1f]; |
| 100 | return out; |
| 101 | } |
| 102 | |
| 103 | export async function normalizedCode(tag, payload) { |
| 104 | return tag + base32Encode(payload) + checksumSymbols(await checksum20(payload)); |
| 105 | } |
| 106 | |
| 107 | // formatCode renders what goes on the paper: |
| 108 | // TAG-XXXXX-XXXXX-XXXXX-XXXXX-XXXXX-XXXXX. |
| 109 | export async function formatCode(tag, payload) { |
| 110 | const norm = await normalizedCode(tag, payload); |
| 111 | let out = tag; |
| 112 | for (let i = 2; i < norm.length; i++) { |
| 113 | if ((i - 2) % 5 === 0) out += "-"; |
| 114 | out += norm[i]; |
| 115 | } |
| 116 | return out; |
| 117 | } |
| 118 | |
| 119 | async function parseNormalized(tag, norm) { |
| 120 | if (norm.length !== CODE_SYMBOLS) throw new Error("contra: wrong number of symbols"); |
| 121 | if (norm.slice(0, 2) !== tag) throw new Error("contra: wrong tag"); |
| 122 | const payload = base32Decode(norm.slice(2, 2 + DATA_SYMBOLS), 16); |
| 123 | if (checksumSymbols(await checksum20(payload)) !== norm.slice(2 + DATA_SYMBOLS)) { |
| 124 | throw new Error("contra: checksum does not match"); |
| 125 | } |
| 126 | return payload; |
| 127 | } |
| 128 | |
| 129 | // parseCode normalises, checks the tag and the checksum, and returns the |
| 130 | // payload. A checksum failure is where the caller reaches for repairCode. |
| 131 | export async function parseCode(tag, s) { |
| 132 | return parseNormalized(tag, normalize(s)); |
| 133 | } |
| 134 | |
| 135 | // repairCode brute-forces every single-character substitution over the 30 |
| 136 | // payload positions — about a thousand candidates — and returns every one |
| 137 | // whose checksum passes, in position-then-alphabet order. |
| 138 | // |
| 139 | // It deliberately does not pick a winner. Twenty bits collides roughly once |
| 140 | // in eleven hundred attempts, so the caller tries each candidate against the |
| 141 | // KCV, which does not collide. Choosing here would sometimes choose wrong |
| 142 | // and hand back the wrong key without saying so. |
| 143 | export async function repairCode(tag, s) { |
| 144 | const norm = normalize(s); |
| 145 | if (norm.length !== CODE_SYMBOLS) throw new Error("contra: wrong number of symbols"); |
| 146 | const out = []; |
| 147 | const buf = norm.split(""); |
| 148 | for (let pos = 2; pos < CODE_SYMBOLS; pos++) { |
| 149 | const orig = buf[pos]; |
| 150 | for (const ch of ALPHABET) { |
| 151 | if (ch === orig) continue; |
| 152 | buf[pos] = ch; |
| 153 | const candidate = buf.join(""); |
| 154 | try { |
| 155 | await parseNormalized(tag, candidate); |
| 156 | out.push(candidate); |
| 157 | } catch { |
| 158 | // Not a repair. The overwhelming majority of the ~930 candidates |
| 159 | // land here; a throw is the expected outcome, not an error path. |
| 160 | } |
| 161 | } |
| 162 | buf[pos] = orig; |
| 163 | } |
| 164 | return out; |
| 165 | } |
| 166 | |
amadan