js-ff1-format-preserving-encryption-radix-nist-sp800-38g-exactness

Answer

Done. The full self-contained solution is at ~/SOLUTION.md, with runnable code at ~/ff1.js, ~/verify.js, and the extended suite at ~/test.js.

Root cause

FF1 implementations round-trip but fail the published vectors because of a small set of spec deviations. The decisive one hit while building this: Step 6.iii of SP 800-38G builds S as R || CIPH_K(R ⊕ [1]^16) || CIPH_K(R ⊕ [2]^16) || …, and R itself is emitted unencrypted. The original code ran the entire R || … buffer through AES, so S was wrong on every round. Other exactness traps addressed:

• PRF is CBC-MAC with a zero IV, returning only the final block.
• b = ceil(ceil(v·log2(radix))/8), d = 4·ceil(b/4)+4 (exact integer math for power-of-two radices).
• Correct 16-byte P layout ([1][2][1][radix]₃[10][u mod 256][n]₄[t]₄).
• Correct Q padding (−t−b−1) mod 16, then [i]¹, then big-endian STR^b_256(NUM_radix(B)).
• BigInt for y, radix^m, and modular add/subtract (values exceed 2^53).
• Validation for radix [2,65536], digit range, min length 2, AES key length, and alphabets (duplicates/unknown chars).

The fix replaces generateS with:

function generateS(key, R, d) {
  const blocks = Math.ceil(d / 16);
  if (blocks === 1) return R.subarray(0, d);
  // Block 0 is R itself; blocks j = 1..blocks-1 are CIPH_K(R xor [j]).
  const input = Buffer.alloc((blocks - 1) * 16);
  const ctr = Buffer.alloc(16);
  for (let j = 1; j < blocks; j++) {
    ctr.fill(0); ctr.writeBigUInt64BE(BigInt(j), 8);
    for (let k = 0; k < 16; k++) input[(j - 1) * 16 + k] = R[k] ^ ctr[k];
  }
  return Buffer.concat([R, aesEcb(key, input)]).subarray(0, d);
}

Verification

All nine official SP 800-38G samples reproduce byte-for-byte (exact digits):

node test.js → 38 checks passed, additionally covering official radix-2 vectors, a 128-digit radix-36 vector with d = 48 > 16 (multi-block S expansion), 198 round-trip cases across radices {2…65536}, and all rejection cases.