Problem class: 20261005-rotating-key-replay-window
The full verified solution is written to ~/rotating-key-replay-window/SOLUTION.md (1201 lines). Here it is in full:
Problem class: 20261005-rotating-key-replay-window
Environment: Node.js 20+
Deliverable: verifier.js (self-contained, no external dependencies) + test.js
The reported failures are not one bug but six interacting ones. A naive verifier that only checks a signature and a timestamp breaks in the following ways:
Replay is unbounded / never recorded. If the verifier only checks the timestamp, the same signed message can be submitted repeatedly inside the freshness window. Nothing ties a message to "already seen".
State is polluted by unauthenticated data. If the replay fingerprint is inserted before the signature is checked, an attacker can submit garbage envelopes that occupy the window and cause legitimate messages to be rejected. Signature verification must come before any replay-state mutation.
Asynchronous cross-region key rotation creates overlapping validity intervals. A key-per-keyId lookup that assumes a single "current" key (or assumes intervals are disjoint/ordered) rejects valid messages during rotation overlap. The registry must allow many simultaneously-valid keys and validate against each key's own [validFrom, validUntil) interval.
Delayed / out-of-order revocation notices. A key revoked at T may be learned about at T + delay, and notices may arrive out of order. Two errors are common: rejecting messages that were legitimately signed before T, and letting a late notice with a later effective time overwrite an earlier one. Revocation must merge with revokedAt = min(seen) and only reject envelopes whose issuedAt >= revokedAt.
Bounded clock skew vs. retransmission. Producers and verifiers have different clocks, and the network retransmits. The freshness rule must allow issuedAt up to now + maxSkewMs (future skew) while the per-key sliding window (sized >= 2 * maxSkewMs) allows legitimate late retransmissions. Anything older than the window is stale, anything further in the future is clock_skew_future.
Persisted state is not durable or not trustworthy. A JSON state file written with writeFile can be left half-written after a crash, and an attacker (or a stale disk) can restore an old copy to make previously-seen messages replayable. This requires: atomic writes (tmp → fsync → rename → directory fsync) so a snapshot is always either the old or the new complete file, never partial; an integrity MAC; a monotonic generation plus a separately persisted anchor; and a compact binary encoding.
Authenticate first, then apply a per-key sliding window whose entries are pruned by now - windowMs; validate keys against overlapping intervals and min()-merged revocations; and persist the whole state as a versioned, HMAC'd, fsync'd binary snapshot with a monotonic generation + anchor.
| Concern | Mechanism |
|---|---|
| Authentication | Ed25519 over a canonical signing string that commits to the payload hash |
| Message identity | fp = SHA-256(signingInput)[0..16) stored per key |
| Replay window | Map<fpHex, issuedAt> per keyId, pruned at < now - windowMs |
| Rotation overlap | Registry holds every key; each validated against its own interval |
| Delayed revocation | revokedAt = min(...), reject only issuedAt >= revokedAt |
| Clock skew | reject issuedAt > now + maxSkewMs; reject issuedAt < now - windowMs |
| Durability | temp file + fsync + atomic rename + dir fsync |
| Integrity | HMAC-SHA256 over the entire envelope |
| Anti-rollback | monotonic generation + .anchor file; load refuses generations below anchor |
| Partial write | .prev last-known-good snapshot fallback |
| Compactness | deterministic binary codec (fixed 16-byte fingerprints, fixed-width ints) |
Verify order (important): shape → key/interval/revocation → freshness → signature → replay-check → commit+persist. Persist failure rolls the in-memory entry back and returns persist_failed, so the verifier never reports success for state it could not durably record.
verifier.js'use strict';
/**
* rotating-key-replay-window/verifier.js
*
* Verifier for signed messages produced by asynchronously rotating keys.
*
* Guarantees implemented here:
* - Ed25519 signature verification (authentication before touching state).
* - Per-key sliding replay window: exact accepted-message fingerprints kept
* only for messages inside [now - windowMs, now + maxSkew].
* - Key validity intervals may overlap; a key is usable for its own interval.
* - Delayed / out-of-order revocation notices are merged with min(revokedAt);
* a message is only invalidated if issuedAt >= revokedAt.
* - Compact binary, integrity-protected persisted state.
* - Atomic + fsync'd writes, previous-good-generation fallback so a torn write
* can never be loaded.
* - Monotonic generation + independently persisted anchor so a rolled back
* snapshot is detected (see README note about the fundamental limit:
* full rollback of *all* local files can only be defeated by an external
* monotonic witness).
*/
const crypto = require('crypto');
const fs = require('fs');
const path = require('path');
const ENVELOPE_MAGIC = Buffer.from('RKRW', 'ascii');
const ENVELOPE_VERSION = 1;
const PAYLOAD_VERSION = 1;
const FP_LEN = 16; // truncated SHA-256 used as message fingerprint
const NONE_REVOKED = 0xffffffffffffffffn;
// ---------------------------------------------------------------------------
// Deterministic serialisation
// ---------------------------------------------------------------------------
function canonicalize(value) {
if (value === null || typeof value !== 'object') return JSON.stringify(value);
if (Array.isArray(value)) return '[' + value.map(canonicalize).join(',') + ']';
const keys = Object.keys(value).sort();
return '{' + keys.map((k) => JSON.stringify(k) + ':' + canonicalize(value[k])).join(',') + '}';
}
function sha256(...bufs) {
const h = crypto.createHash('sha256');
for (const b of bufs) h.update(b);
return h.digest();
}
function signingInput(env) {
// The payload is committed to via its canonical hash, so envelopes can carry
// arbitrary JSON without ambiguity.
const payloadHash = sha256(Buffer.from(canonicalize(env.payload), 'utf8')).toString('hex');
return ['v1', env.keyId, env.nonce, String(env.issuedAt), payloadHash].join('\n');
}
function fingerprint(env) {
return sha256(Buffer.from(signingInput(env), 'utf8')).subarray(0, FP_LEN);
}
// ---------------------------------------------------------------------------
// Tiny binary codec
// ---------------------------------------------------------------------------
class Writer {
constructor() {
this.chunks = [];
}
u8(v) {
this.chunks.push(Buffer.from([v & 0xff]));
return this;
}
u16(v) {
const b = Buffer.allocUnsafe(2);
b.writeUInt16BE(v);
this.chunks.push(b);
return this;
}
u32(v) {
const b = Buffer.allocUnsafe(4);
b.writeUInt32BE(v >>> 0);
this.chunks.push(b);
return this;
}
u64(v) {
const b = Buffer.allocUnsafe(8);
b.writeBigUInt64BE(BigInt(v));
this.chunks.push(b);
return this;
}
bytes(b) {
this.u32(b.length);
this.chunks.push(b);
return this;
}
str(s) {
return this.bytes(Buffer.from(s, 'utf8'));
}
concat() {
return Buffer.concat(this.chunks);
}
}
class Reader {
constructor(buf) {
this.buf = buf;
this.off = 0;
}
need(n) {
if (this.off + n > this.buf.length) throw new Error('truncated state');
}
u8() {
this.need(1);
return this.buf[this.off++];
}
u16() {
this.need(2);
const v = this.buf.readUInt16BE(this.off);
this.off += 2;
return v;
}
u32() {
this.need(4);
const v = this.buf.readUInt32BE(this.off);
this.off += 4;
return v;
}
u64() {
this.need(8);
const v = this.buf.readBigUInt64BE(this.off);
this.off += 8;
return v;
}
bytes() {
const n = this.u32();
this.need(n);
const b = this.buf.subarray(this.off, this.off + n);
this.off += n;
return b;
}
str() {
return this.bytes().toString('utf8');
}
fp() {
this.need(FP_LEN);
const b = this.buf.subarray(this.off, this.off + FP_LEN);
this.off += FP_LEN;
return b;
}
rest() {
return this.buf.subarray(this.off);
}
}
// ---------------------------------------------------------------------------
// Atomic file helpers
// ---------------------------------------------------------------------------
function fsyncDir(dir) {
try {
const fd = fs.openSync(dir, 'r');
try {
fs.fsyncSync(fd);
} finally {
fs.closeSync(fd);
}
} catch {
/* best effort; some platforms / filesystems do not allow dir fsync */
}
}
function atomicWrite(file, buf, mode = 0o600) {
const dir = path.dirname(file);
const tmp = path.join(
dir,
'.' + path.basename(file) + '.tmp-' + process.pid + '-' + crypto.randomBytes(4).toString('hex')
);
const fd = fs.openSync(tmp, 'w', mode);
try {
fs.writeSync(fd, buf);
fs.fsyncSync(fd);
} finally {
fs.closeSync(fd);
}
fs.renameSync(tmp, file);
fsyncDir(dir);
}
// ---------------------------------------------------------------------------
// Key registry
// ---------------------------------------------------------------------------
function normalizeKey(k) {
if (!k || typeof k.keyId !== 'string' || !k.keyId) throw new Error('keyId required');
if (!k.publicKey) throw new Error('publicKey required');
const validFrom = Number(k.validFrom ?? 0);
const validUntil = Number(k.validUntil ?? Number.MAX_SAFE_INTEGER);
if (!(validFrom < validUntil)) throw new Error('validFrom must be < validUntil');
return {
keyId: k.keyId,
publicKeyPem:
typeof k.publicKey === 'string'
? k.publicKey
: k.publicKey.export({ type: 'spki', format: 'pem' }),
validFrom,
validUntil,
revokedAt: k.revokedAt == null ? null : Number(k.revokedAt),
region: k.region == null ? null : String(k.region),
};
}
class KeyRegistry {
constructor() {
this.keys = new Map();
}
add(k) {
const norm = normalizeKey(k);
// Never silently resurrect a key that was already revoked.
const prev = this.keys.get(norm.keyId);
if (prev && prev.revokedAt != null) {
if (norm.revokedAt == null) norm.revokedAt = prev.revokedAt;
else norm.revokedAt = Math.min(norm.revokedAt, prev.revokedAt);
}
this.keys.set(norm.keyId, norm);
return norm;
}
get(keyId) {
return this.keys.get(keyId);
}
/**
* Merge a revocation notice. Delayed and out-of-order notices are safe:
* we keep the earliest effective revocation time ever seen for the key.
*/
revoke(keyId, revokedAt) {
const t = Number(revokedAt);
const key = this.keys.get(keyId);
if (!key) {
// Keep the notice even if the key descriptor has not arrived yet.
this.keys.set(keyId, {
keyId,
publicKeyPem: null,
validFrom: 0,
validUntil: Number.MAX_SAFE_INTEGER,
revokedAt: t,
region: null,
});
return t;
}
key.revokedAt = key.revokedAt == null ? t : Math.min(key.revokedAt, t);
return key.revokedAt;
}
list() {
return [...this.keys.values()];
}
}
// ---------------------------------------------------------------------------
// Verifier
// ---------------------------------------------------------------------------
class Verifier {
/**
* @param {object} opts
* @param {string} opts.statePath path of the snapshot file
* @param {Buffer|string} [opts.secret] integrity secret (HMAC key)
* @param {number} [opts.windowMs] per-key replay window
* @param {number} [opts.maxSkewMs] tolerated producer/verifier clock skew
* @param {number} [opts.maxEntriesPerKey] hard memory cap (fail closed)
* @param {function} [opts.clock] injectable clock for tests
* @param {boolean} [opts.persistOnVerify=true]
*/
constructor(opts) {
if (!opts || !opts.statePath) throw new Error('statePath required');
this.statePath = opts.statePath;
this.prevPath = opts.statePath + '.prev';
this.anchorPath = opts.statePath + '.anchor';
this.secretPath = opts.statePath + '.secret';
this.windowMs = opts.windowMs ?? 5 * 60 * 1000;
this.maxSkewMs = opts.maxSkewMs ?? 30 * 1000;
if (this.windowMs < 2 * this.maxSkewMs) {
throw new Error('windowMs must be >= 2 * maxSkewMs to allow legitimate retransmission');
}
this.maxEntriesPerKey = opts.maxEntriesPerKey ?? 100000;
this.clock = opts.clock ?? Date.now;
this.persistOnVerify = opts.persistOnVerify !== false;
this.registry = new KeyRegistry();
/** keyId -> Map<fpHex, issuedAt> */
this.windows = new Map();
this.generation = 0n;
this._lastSnapshot = null;
this._secret = this._resolveSecret(opts.secret);
this._loaded = false;
}
_resolveSecret(secret) {
if (secret != null) return Buffer.isBuffer(secret) ? secret : Buffer.from(secret);
if (process.env.RKRW_SECRET) return Buffer.from(process.env.RKRW_SECRET);
try {
return fs.readFileSync(this.secretPath);
} catch {
const s = crypto.randomBytes(32);
atomicWrite(this.secretPath, s, 0o600);
return s;
}
}
_mac(prefix) {
return crypto.createHmac('sha256', this._secret).update(prefix).digest();
}
_encodeEnvelope(payload, generation) {
const header = Buffer.alloc(4 + 1 + 8 + 4);
ENVELOPE_MAGIC.copy(header, 0);
header.writeUInt8(ENVELOPE_VERSION, 4);
header.writeBigUInt64BE(generation, 5);
header.writeUInt32BE(payload.length, 13);
const mac = this._mac(Buffer.concat([header, payload]));
return Buffer.concat([header, mac, payload]);
}
_decodeEnvelope(buf) {
if (buf.length < 4 + 1 + 8 + 4 + 32) throw new Error('state too short');
if (!buf.subarray(0, 4).equals(ENVELOPE_MAGIC)) throw new Error('bad magic');
const version = buf.readUInt8(4);
if (version !== ENVELOPE_VERSION) throw new Error('unsupported envelope version');
const generation = buf.readBigUInt64BE(5);
const payloadLen = buf.readUInt32BE(13);
const macOff = 17;
const payloadOff = macOff + 32;
if (buf.length !== payloadOff + payloadLen) throw new Error('bad length');
const header = buf.subarray(0, 17);
const payload = buf.subarray(payloadOff);
const expect = this._mac(Buffer.concat([header, payload]));
if (!crypto.timingSafeEqual(buf.subarray(macOff, payloadOff), expect)) {
throw new Error('integrity check failed');
}
return { generation, payload };
}
_encodeState() {
const w = new Writer();
w.u8(PAYLOAD_VERSION);
w.u64(this.generation);
const keys = this.registry.list();
w.u32(keys.length);
for (const k of keys) {
w.str(k.keyId);
w.u8(k.publicKeyPem ? 1 : 0);
if (k.publicKeyPem) w.str(k.publicKeyPem);
w.u64(k.validFrom);
w.u64(k.validUntil);
w.u64(k.revokedAt == null ? NONE_REVOKED : k.revokedAt);
w.u8(k.region ? 1 : 0);
if (k.region) w.str(k.region);
}
w.u32(this.windows.size);
for (const [keyId, map] of this.windows) {
w.str(keyId);
w.u32(map.size);
for (const [fp, t] of map) {
w.chunks.push(Buffer.from(fp, 'hex'));
w.u64(t);
}
}
return w.concat();
}
_decodeState(payload) {
const r = new Reader(payload);
const version = r.u8();
if (version !== PAYLOAD_VERSION) throw new Error('unsupported payload version');
this.generation = r.u64();
const keyCount = r.u32();
this.registry = new KeyRegistry();
for (let i = 0; i < keyCount; i++) {
const keyId = r.str();
const hasPub = r.u8();
const publicKeyPem = hasPub ? r.str() : null;
const validFrom = Number(r.u64());
const validUntil = Number(r.u64());
const revRaw = r.u64();
const hasRegion = r.u8();
const region = hasRegion ? r.str() : null;
this.registry.keys.set(keyId, {
keyId,
publicKeyPem,
validFrom,
validUntil,
revokedAt: revRaw === NONE_REVOKED ? null : Number(revRaw),
region,
});
}
const winCount = r.u32();
this.windows = new Map();
for (let i = 0; i < winCount; i++) {
const keyId = r.str();
const n = r.u32();
const map = new Map();
for (let j = 0; j < n; j++) {
const fp = r.fp().toString('hex');
map.set(fp, Number(r.u64()));
}
this.windows.set(keyId, map);
}
if (r.off !== r.buf.length) throw new Error('trailing bytes in state');
}
load() {
if (this._loaded) return this;
const candidates = [];
for (const [file, tag] of [
[this.statePath, 'main'],
[this.prevPath, 'prev'],
]) {
try {
const raw = fs.readFileSync(file);
const dec = this._decodeEnvelope(raw);
candidates.push({ tag, raw, ...dec });
} catch (e) {
if (e && e.code !== 'ENOENT') {
// Corrupt / torn file: recorded so we can fall through to .prev.
candidates.push({ tag, error: e.message });
}
}
}
let anchorGen = 0n;
let anchorOk = false;
try {
const raw = fs.readFileSync(this.anchorPath);
const dec = this._decodeEnvelope(raw);
const r = new Reader(dec.payload);
// anchor payload = u64 generation || 16-byte digest of main snapshot
const g = r.u64();
r.fp();
if (g > anchorGen) anchorGen = g;
anchorOk = true;
} catch {
/* anchor optional on first boot */
}
const usable = candidates.filter((c) => !c.error);
// Prefer main, but never accept a generation below a valid anchor.
let chosen = null;
const ordered = usable.sort((a, b) => {
const d = b.generation > a.generation ? 1 : b.generation < a.generation ? -1 : 0;
if (d !== 0) return d;
return a.tag === 'main' ? -1 : 1;
});
for (const c of ordered) {
if (anchorOk && c.generation < anchorGen) continue;
chosen = c;
break;
}
if (!chosen) {
if (anchorOk && anchorGen > 0n) {
throw new Error('rollback/tamper detected: no valid snapshot at or above anchor generation');
}
this._loaded = true;
return this;
}
this._decodeState(chosen.payload);
this._lastSnapshot = chosen.raw;
if (anchorOk && anchorGen > this.generation) this.generation = anchorGen;
this._loaded = true;
return this;
}
persist() {
this.generation += 1n;
const payload = this._encodeState();
const envelope = this._encodeEnvelope(payload, this.generation);
// Keep the last known-good snapshot as .prev before replacing main.
if (this._lastSnapshot) {
atomicWrite(this.prevPath, this._lastSnapshot, 0o600);
}
atomicWrite(this.statePath, envelope, 0o600);
this._lastSnapshot = envelope;
// Anchor records the generation and a digest of the snapshot we just wrote.
const aw = new Writer();
aw.u64(this.generation);
aw.chunks.push(sha256(envelope).subarray(0, FP_LEN));
atomicWrite(this.anchorPath, this._encodeEnvelope(aw.concat(), this.generation), 0o600);
return this;
}
addKey(k) {
if (!this._loaded) this.load();
this.registry.add(k);
if (this.persistOnVerify) this.persist();
return this;
}
revoke(keyId, revokedAt) {
if (!this._loaded) this.load();
const t = this.registry.revoke(keyId, revokedAt);
if (this.persistOnVerify) this.persist();
return t;
}
_prune(keyId, now) {
const map = this.windows.get(keyId);
if (!map) return;
const cutoff = now - this.windowMs;
for (const [fp, t] of map) {
if (t < cutoff) map.delete(fp);
}
}
/**
* Verify one envelope. Returns {ok:true} or {ok:false, reason}.
* State is only mutated after the signature has been authenticated, so an
* unauthenticated attacker can never poison the replay window.
*/
verify(env) {
if (!this._loaded) this.load();
const now = this.clock();
// --- structural validation -------------------------------------------------
if (!env || typeof env !== 'object') return { ok: false, reason: 'malformed' };
const { keyId, nonce, issuedAt, signature } = env;
if (typeof keyId !== 'string' || !keyId) return { ok: false, reason: 'malformed_key_id' };
if (typeof nonce !== 'string' || nonce.length < 8) return { ok: false, reason: 'malformed_nonce' };
if (!Number.isFinite(issuedAt)) return { ok: false, reason: 'malformed_issued_at' };
if (typeof signature !== 'string' || !signature) return { ok: false, reason: 'malformed_signature' };
// --- key metadata ----------------------------------------------------------
const key = this.registry.get(keyId);
if (!key || !key.publicKeyPem) return { ok: false, reason: 'unknown_key' };
// A revocation only invalidates messages issued at or after it. Messages
// signed before the effective revocation time stay valid (delayed notice).
if (key.revokedAt != null && issuedAt >= key.revokedAt) {
return { ok: false, reason: 'revoked_key' };
}
if (issuedAt < key.validFrom) return { ok: false, reason: 'key_not_yet_valid' };
if (issuedAt >= key.validUntil) return { ok: false, reason: 'key_expired' };
// --- freshness / bounded clock skew ---------------------------------------
if (issuedAt > now + this.maxSkewMs) return { ok: false, reason: 'clock_skew_future' };
if (issuedAt < now - this.windowMs) return { ok: false, reason: 'stale' };
// --- authentication BEFORE touching replay state --------------------------
const input = Buffer.from(signingInput(env), 'utf8');
let sig;
try {
sig = Buffer.from(signature, 'base64');
} catch {
return { ok: false, reason: 'malformed_signature' };
}
let pub;
try {
pub = crypto.createPublicKey(key.publicKeyPem);
} catch {
return { ok: false, reason: 'bad_public_key' };
}
let good = false;
try {
good = crypto.verify(null, input, pub, sig);
} catch {
good = false;
}
if (!good) return { ok: false, reason: 'bad_signature' };
// --- per-key sliding replay window ----------------------------------------
this._prune(keyId, now);
let map = this.windows.get(keyId);
if (!map) {
map = new Map();
this.windows.set(keyId, map);
}
const fp = fingerprint(env).toString('hex');
if (map.has(fp)) return { ok: false, reason: 'replay' };
if (map.size >= this.maxEntriesPerKey) return { ok: false, reason: 'replay_window_full' };
map.set(fp, issuedAt);
if (this.persistOnVerify) {
try {
this.persist();
} catch (e) {
// Never report success for state we could not durably record.
map.delete(fp);
return { ok: false, reason: 'persist_failed', error: e.message };
}
}
return { ok: true, keyId, fingerprint: fp, issuedAt };
}
/** Test helper: number of fingerprints currently in a key's window. */
windowSize(keyId) {
return this.windows.get(keyId)?.size ?? 0;
}
}
// ---------------------------------------------------------------------------
// Producer helper (used for tests / documentation)
// ---------------------------------------------------------------------------
function signEnvelope(env, privateKey) {
const input = Buffer.from(signingInput(env), 'utf8');
return { ...env, signature: crypto.sign(null, input, privateKey).toString('base64') };
}
module.exports = {
Verifier,
KeyRegistry,
signEnvelope,
signingInput,
fingerprint,
canonicalize,
_internal: { Writer, Reader, atomicWrite },
};
const crypto = require('crypto');
const { Verifier, signEnvelope } = require('./verifier');
const verifier = new Verifier({
statePath: '/var/lib/myapp/verify-state.bin',
// secret: process.env.RKRW_SECRET, // or a 0600 key file next to state
windowMs: 5 * 60 * 1000, // per-key replay window (>= 2*maxSkewMs)
maxSkewMs: 30 * 1000, // tolerated producer/verifier clock skew
}).load();
verifier.addKey({
keyId: 'eu-2026-10-a',
publicKey: publicKeyPem, // SPKI PEM (or a KeyObject)
validFrom: 1760000000000,
validUntil: 1760600000000,
region: 'eu',
});
// Delayed / out-of-order notices are safe; earliest effective time wins.
verifier.revoke('eu-2026-10-a', 1760300000000);
const result = verifier.verify(envelopeFromNetwork);
// { ok: true, ... } | { ok: false, reason: 'replay' | 'stale' | ... }
Producer side (for completeness):
const { publicKey, privateKey } = crypto.generateKeyPairSync('ed25519');
const signed = signEnvelope({
keyId: 'eu-2026-10-a',
nonce: crypto.randomBytes(16).toString('base64url'),
issuedAt: Date.now(),
payload: { amount: 42 },
}, privateKey);
test.js'use strict';
const test = require('node:test');
const assert = require('node:assert');
const crypto = require('crypto');
const fs = require('fs');
const os = require('os');
const path = require('path');
const { Verifier, signEnvelope } = require('./verifier');
// ---------------------------------------------------------------------------
// helpers
// ---------------------------------------------------------------------------
const T0 = 1_700_000_000_000;
function tmpDir() {
return fs.mkdtempSync(path.join(os.tmpdir(), 'rkrw-'));
}
function makeKey(keyId, opts = {}) {
const { publicKey, privateKey } = crypto.generateKeyPairSync('ed25519');
return {
descriptor: {
keyId,
publicKey: publicKey.export({ type: 'spki', format: 'pem' }),
validFrom: opts.validFrom ?? T0 - 3_600_000,
validUntil: opts.validUntil ?? T0 + 3_600_000,
region: opts.region ?? 'r1',
},
privateKey,
};
}
let nonceCounter = 0;
function envelope(keyId, issuedAt, payload = { n: 1 }, nonce) {
return {
keyId,
nonce: nonce ?? `nonce-${String(nonceCounter++).padStart(16, '0')}`,
issuedAt,
payload,
};
}
function newVerifier(dir, clock, extra = {}) {
return new Verifier({
statePath: path.join(dir, 'state.bin'),
secret: Buffer.from('test-secret-0123456789abcdef'),
windowMs: 300_000,
maxSkewMs: 30_000,
clock: () => clock.t,
...extra,
});
}
// ---------------------------------------------------------------------------
// tests
// ---------------------------------------------------------------------------
test('accepts a correctly signed fresh message', () => {
const dir = tmpDir();
const clock = { t: T0 };
const { descriptor, privateKey } = makeKey('k1');
const v = newVerifier(dir, clock).load().addKey(descriptor);
const env = signEnvelope(envelope('k1', T0), privateKey);
assert.deepStrictEqual(v.verify(env), {
ok: true,
keyId: 'k1',
fingerprint: require('./verifier').fingerprint(env).toString('hex'),
issuedAt: T0,
});
});
test('rejects a replayed message (per-key sliding window)', () => {
const dir = tmpDir();
const clock = { t: T0 };
const { descriptor, privateKey } = makeKey('k1');
const v = newVerifier(dir, clock).load().addKey(descriptor);
const env = signEnvelope(envelope('k1', T0), privateKey);
assert.strictEqual(v.verify(env).ok, true);
assert.deepStrictEqual(v.verify(env), { ok: false, reason: 'replay' });
assert.strictEqual(v.windowSize('k1'), 1);
});
test('replay is scoped per key (same nonce on another key is fine)', () => {
const dir = tmpDir();
const clock = { t: T0 };
const a = makeKey('a');
const b = makeKey('b');
const v = newVerifier(dir, clock).load().addKey(a.descriptor).addKey(b.descriptor);
const nonce = 'shared-nonce-0001';
assert.strictEqual(v.verify(signEnvelope(envelope('a', T0, {}, nonce), a.privateKey)).ok, true);
assert.strictEqual(v.verify(signEnvelope(envelope('b', T0, {}, nonce), b.privateKey)).ok, true);
});
test('rejects stale and far-future messages (bounded clock skew)', () => {
const dir = tmpDir();
const clock = { t: T0 };
const { descriptor, privateKey } = makeKey('k1');
const v = newVerifier(dir, clock).load().addKey(descriptor);
const stale = signEnvelope(envelope('k1', T0 - 300_001), privateKey);
assert.deepStrictEqual(v.verify(stale), { ok: false, reason: 'stale' });
const future = signEnvelope(envelope('k1', T0 + 30_001), privateKey);
assert.deepStrictEqual(v.verify(future), { ok: false, reason: 'clock_skew_future' });
// just inside the skew allowance is accepted
const skewed = signEnvelope(envelope('k1', T0 + 29_000), privateKey);
assert.strictEqual(v.verify(skewed).ok, true);
});
test('rejects unknown keys and bad signatures without poisoning state', () => {
const dir = tmpDir();
const clock = { t: T0 };
const { descriptor, privateKey } = makeKey('k1');
const other = makeKey('other');
const v = newVerifier(dir, clock).load().addKey(descriptor);
assert.deepStrictEqual(v.verify(signEnvelope(envelope('nope', T0), privateKey)), {
ok: false,
reason: 'unknown_key',
});
// forged signature must not create a replay entry
const forged = signEnvelope(envelope('k1', T0), other.privateKey);
assert.deepStrictEqual(v.verify(forged), { ok: false, reason: 'bad_signature' });
assert.strictEqual(v.windowSize('k1'), 0);
});
test('honours key validity intervals and overlapping rotation windows', () => {
const dir = tmpDir();
const clock = { t: T0 };
const oldK = makeKey('old', { validFrom: T0 - 100_000, validUntil: T0 + 100_000 });
const newK = makeKey('new', { validFrom: T0 - 50_000, validUntil: T0 + 200_000 });
const v = newVerifier(dir, clock).load().addKey(oldK.descriptor).addKey(newK.descriptor);
// overlap region: both keys accepted
assert.strictEqual(v.verify(signEnvelope(envelope('old', T0), oldK.privateKey)).ok, true);
assert.strictEqual(v.verify(signEnvelope(envelope('new', T0), newK.privateKey)).ok, true);
// new key not valid before its validFrom
const early = signEnvelope(envelope('new', T0 - 60_000), newK.privateKey);
assert.deepStrictEqual(v.verify(early), { ok: false, reason: 'key_not_yet_valid' });
// old key expired
const late = signEnvelope(envelope('old', T0 + 150_000), oldK.privateKey);
assert.deepStrictEqual(v.verify(late), { ok: false, reason: 'key_expired' });
});
test('delayed revocation: pre-revocation messages stay valid, later ones rejected', () => {
const dir = tmpDir();
const clock = { t: T0 };
const { descriptor, privateKey } = makeKey('k1');
const v = newVerifier(dir, clock).load().addKey(descriptor);
// We learn about a revocation effective at T0, but notices can arrive late.
const pre = signEnvelope(envelope('k1', T0 - 1_000), privateKey);
assert.strictEqual(v.verify(pre).ok, true);
v.revoke('k1', T0);
const post = signEnvelope(envelope('k1', T0 + 1_000), privateKey);
assert.deepStrictEqual(v.verify(post), { ok: false, reason: 'revoked_key' });
// A message issued before the effective revocation time is still valid.
const pre2 = signEnvelope(envelope('k1', T0 - 500), privateKey);
assert.strictEqual(v.verify(pre2).ok, true);
});
test('revocation notices merge out of order (keep earliest effective time)', () => {
const dir = tmpDir();
const clock = { t: T0 };
const { descriptor, privateKey } = makeKey('k1');
const v = newVerifier(dir, clock).load().addKey(descriptor);
v.revoke('k1', T0 - 10_000);
v.revoke('k1', T0 + 10_000); // late/conflicting notice must not move it later
assert.strictEqual(v.registry.get('k1').revokedAt, T0 - 10_000);
const between = signEnvelope(envelope('k1', T0), privateKey);
assert.deepStrictEqual(v.verify(between), { ok: false, reason: 'revoked_key' });
});
test('state survives restart: replay window and revocations persist', () => {
const dir = tmpDir();
const clock = { t: T0 };
const { descriptor, privateKey } = makeKey('k1');
const v1 = newVerifier(dir, clock).load().addKey(descriptor);
const env = signEnvelope(envelope('k1', T0), privateKey);
assert.strictEqual(v1.verify(env).ok, true);
v1.revoke('k1b', T0); // unknown-key revocation must persist too
const v2 = newVerifier(dir, clock).load();
assert.deepStrictEqual(v2.verify(env), { ok: false, reason: 'replay' });
assert.strictEqual(v2.registry.get('k1b').revokedAt, T0);
});
test('a crash during persist leaves the previous complete snapshot intact', () => {
const dir = tmpDir();
const clock = { t: T0 };
const { descriptor, privateKey } = makeKey('k1');
const v = newVerifier(dir, clock).load().addKey(descriptor);
const env = signEnvelope(envelope('k1', T0), privateKey);
const realRename = fs.renameSync;
let injected = false;
fs.renameSync = (...args) => {
if (!injected) {
injected = true;
throw new Error('simulated crash during rename');
}
return realRename(...args);
};
let result;
try {
result = v.verify(env);
} finally {
fs.renameSync = realRename;
}
assert.deepStrictEqual(result, {
ok: false,
reason: 'persist_failed',
error: 'simulated crash during rename',
});
// in-memory entry was rolled back so it matches durable state
assert.strictEqual(v.windowSize('k1'), 0);
const reloaded = newVerifier(dir, clock).load();
assert.strictEqual(reloaded.verify(env).ok, true);
});
test('tampering with the snapshot is detected (HMAC)', () => {
const dir = tmpDir();
const clock = { t: T0 };
const { descriptor } = makeKey('k1');
const v = newVerifier(dir, clock).load().addKey(descriptor);
const stateFile = path.join(dir, 'state.bin');
const raw = fs.readFileSync(stateFile);
raw[raw.length - 1] ^= 0xff; // flip a payload byte
fs.writeFileSync(stateFile, raw);
const fresh = newVerifier(dir, clock);
assert.throws(() => fresh.load(), /rollback\/tamper|integrity/i);
});
test('rollback of the snapshot below the anchor generation is rejected', () => {
const dir = tmpDir();
const clock = { t: T0 };
const { descriptor, privateKey } = makeKey('k1');
const v = newVerifier(dir, clock).load().addKey(descriptor);
const env = signEnvelope(envelope('k1', T0), privateKey);
assert.strictEqual(v.verify(env).ok, true);
const stateFile = path.join(dir, 'state.bin');
const prevFile = stateFile + '.prev';
fs.copyFileSync(prevFile, stateFile); // roll main back one generation
const fresh = newVerifier(dir, clock);
assert.throws(() => fresh.load(), /rollback\/tamper/i);
});
test('sliding window prunes old entries so memory stays bounded', () => {
const dir = tmpDir();
const clock = { t: T0 };
const { descriptor, privateKey } = makeKey('k1');
const v = newVerifier(dir, clock).load().addKey(descriptor);
const first = signEnvelope(envelope('k1', T0), privateKey);
assert.strictEqual(v.verify(first).ok, true);
assert.strictEqual(v.windowSize('k1'), 1);
// Jump past the window: the next accepted message evicts the old entry.
clock.t = T0 + 400_000;
const second = signEnvelope(envelope('k1', clock.t), privateKey);
assert.strictEqual(v.verify(second).ok, true);
assert.strictEqual(v.windowSize('k1'), 1);
});
test('asynchronous multi-region rotation with retransmission', () => {
const dir = tmpDir();
const clock = { t: T0 };
const keys = ['r1', 'r2', 'r3'].map((r) => makeKey('key-' + r, { region: r }));
const v = newVerifier(dir, clock).load();
for (const k of keys) v.addKey(k.descriptor);
// Interleave regions and retransmit each message once (a retransmit is a replay).
const sent = [];
for (let i = 0; i < 25; i++) {
const k = keys[i % keys.length];
const env = signEnvelope(envelope(k.descriptor.keyId, T0 + i, { i }), k.privateKey);
sent.push(env);
}
// deliver out of order
for (const env of [...sent].reverse()) assert.strictEqual(v.verify(env).ok, true);
// retransmissions are rejected
for (const env of sent) assert.deepStrictEqual(v.verify(env), { ok: false, reason: 'replay' });
});
test('persisted state is compact', () => {
const dir = tmpDir();
const clock = { t: T0 };
const { descriptor, privateKey } = makeKey('k1');
const v = newVerifier(dir, clock).load().addKey(descriptor);
for (let i = 0; i < 200; i++) {
const env = signEnvelope(envelope('k1', T0 + i, { i }), privateKey);
assert.strictEqual(v.verify(env).ok, true);
}
const size = fs.statSync(path.join(dir, 'state.bin')).size;
// ~200 fingerprints at 16 bytes + overhead; must be far below a JSON dump.
assert.ok(size < 200 * 32, `state too large: ${size} bytes`);
});
test('missing snapshot starts clean but a lone valid anchor still guards', () => {
const dir = tmpDir();
const clock = { t: T0 };
const { descriptor } = makeKey('k1');
const v = newVerifier(dir, clock).load().addKey(descriptor);
// delete state + prev but leave the anchor
fs.rmSync(path.join(dir, 'state.bin'));
fs.rmSync(path.join(dir, 'state.bin.prev'), { force: true });
const fresh = newVerifier(dir, clock);
assert.throws(() => fresh.load(), /rollback\/tamper/i);
});
node -e "require('./verifier'); console.log('module loads OK')"
node --test test.js
node demo.js
$ node -e "require('./verifier'); console.log('module loads OK')"
module loads OK
$ node --test test.js
ok 1 - accepts a correctly signed fresh message
ok 2 - rejects a replayed message (per-key sliding window)
ok 3 - replay is scoped per key (same nonce on another key is fine)
ok 4 - rejects stale and far-future messages (bounded clock skew)
ok 5 - rejects unknown keys and bad signatures without poisoning state
ok 6 - honours key validity intervals and overlapping rotation windows
ok 7 - delayed revocation: pre-revocation messages stay valid, later ones rejected
ok 8 - revocation notices merge out of order (keep earliest effective time)
ok 9 - state survives restart: replay window and revocations persist
ok 10 - a crash during persist leaves the previous complete snapshot intact
ok 11 - tampering with the snapshot is detected (HMAC)
ok 12 - rollback of the snapshot below the anchor generation is rejected
ok 13 - sliding window prunes old entries so memory stays bounded
ok 14 - asynchronous multi-region rotation with retransmission
ok 15 - persisted state is compact
ok 16 - missing snapshot starts clean but a lone valid anchor still guards
# tests 16
# pass 16
# fail 0
End-to-end demo (demo.js):
accept : {"ok":true,"keyId":"k1","fingerprint":"0cfd9db812b66b048f51a356b99d750c","issuedAt":1700000000000}
retransmit : {"ok":false,"reason":"replay"}
stale : {"ok":false,"reason":"stale"}
after reload: {"ok":false,"reason":"replay"}
snapshot : 255 bytes
The after reload line is the key restart guarantee: the replay window was recovered from disk, so the same envelope is rejected after a process restart. The 255-byte snapshot (a key descriptor + one window entry) demonstrates the compact binary format.
| # | Test | Requirement covered |
|---|---|---|
| 1 | accept fresh | signature + freshness happy path |
| 2 | replay rejected | per-key sliding window |
| 3 | per-key scoping | windows isolated by keyId |
| 4 | stale / future | bounded clock skew and window |
| 5 | forged sig no poisoning | authenticate before mutating state |
| 6 | overlapping intervals | async rotation across regions |
| 7 | delayed revocation | pre-revokedAt valid, post rejected |
| 8 | out-of-order notices | min() merge |
| 9 | restart | durable replay window + revocations |
| 10 | crash during persist | atomic write / rollback-on-failure |
| 11 | byte tamper | HMAC integrity |
| 12 | snapshot rollback | monotonic generation + anchor |
| 13 | pruning | bounded memory |
| 14 | multi-region retransmit | async regions + retransmission |
| 15 | size bound | compact state |
| 16 | anchor with missing snapshot | fail closed on rollback |
opts.secret, RKRW_SECRET, or is generated as a 0600 file next to the state. Protect it; if an attacker can read the secret and rewrite the state, they can forge a consistent snapshot.(generation, SHA-256(snapshot)) to an external monotonic witness (append-only log, notary, or another host) and compare on boot. The .anchor file is the local half of that protocol and is deliberately written after the snapshot so the common crash cases are safe.maxSkewMs should be kept small (seconds). windowMs must be at least 2 * maxSkewMs (enforced by the constructor) so a legitimate message delayed by the full future skew still falls inside the replay window.persist() calls or use a write-ahead log keyed on the same generation counter; correctness of the replay decision does not depend on the batching interval, only on the fact that a message is never reported ok before its window entry is durable.replay_window_full. Under a sustained flood faster than the window drains, the verifier fails closed rather than silently dropping old fingerprints (dropping them would reopen a replay hole). Raise maxEntriesPerKey or shorten windowMs if this is hit legitimately.rotating-key-replay-window/
├── verifier.js # the fix (self-contained, stdlib only)
├── test.js # 16 tests, all passing with `node --test`
├── demo.js # end-to-end smoke demo
└── SOLUTION.md # this document
Result: 16/16 tests pass. The files are at ~/rotating-key-replay-window/.
# Evidence - Problem class: 20261005-rotating-key-replay-window - Model: openrouter/deepseek/deepseek-v4.1-flash - Solved: 2026-10-05T10:16:02.221Z - Verification: solution produced by pi in sandbox; see signatures.json
{"description": "Implement a Node.js verifier for signed messages whose producers rotate keys asynchronously across regions while clients tolerate bounded clock skew and retransmission. The verifier must reject replay outside a per-key sliding window, safely handle overlapping key validity intervals and delayed revocation notices, and remain correct across process restarts using a compact persisted state format that resists rollback and partial writes.", "environment": "node20", "language": "js", "model": "openrouter/deepseek/deepseek-v4.1-flash", "problem_class": "20261005-rotating-key-replay-window", "provider": "openrouter", "solved_at": "2026-10-05T10:16:02.221Z", "version": "20"}