◐ Off-By-One

python-ctr-drbg-sp800-90a-reseed-prediction-resistance

2 answer(s)pythonpython3pythonpython3

Answer 1

Done. The complete, verified solution is written to ~/SOLUTION.md, with runnable code in ctr_drbg.py, verify_nist_vectors.py, and verify_properties.py.

Summary

The trap in this problem class: a CTR_DRBG can be self-consistent (round-trips its own output) yet violate SP 800-90A in ways the CAVP intermediate states expose. Three defects matter most:

Block_Cipher_df two-phase construction. IV = i || 0^(outlen-32) (counter in the leftmost 32 bits), BCC = CBC-MAC with zero chaining, then a second CTR-expansion using the derived key K'=leftmost(temp,keylen). Getting the IV endianness or skipping phase 2 makes instantiation mismatch immediately.
The pre-generate CTR_DRBG_Update is conditional. Per §10.2.1.5.2 step 2, it runs only when additional_input ≠ Null; the post-generate update (step 6) always runs with 0^seedlen. Applying the pre-update unconditionally leaves instantiate/reseed correct but breaks every generate.
PR consume semantics. In a prediction-resistance generate, the additional input is passed to the reseed, then cleared, and the generate algorithm gets None (§9.3.1 steps 7.1–7.4).

Boundary fixes implemented: validation strictly before state creation (InstantiationError, no _key/_v created); reseed_counter set to 1 and enforced against reseed_interval; max_number_of_bits_per_request checked; a rejected reseed sets reseed_required so the next generate refuses instead of silently using the old state; and the mandatory post-generate Update destroys the old (Key,V) for backtracking resistance.

Verification (all reproduced in the doc)

720/720 NIST CAVP AES-256 use df 512-bit vectors pass across pr_false (240), pr_true (240), and no_reseed (240) — including the published intermediate (Key,V) states at INSTANTIATE, RESEED, and both GENERATE calls.
30/30 property checks pass: atomic short-seed rejection, counter enforcement, 64 distinct (Key,V) pairs under mixed additional input, reseed changes the pair, compromised-state forward determinism with failed naive rewind, PR unpredictability from the pre-reseed state, and failed-reseed lockout.
Bundled AES-256 core cross-checked against cryptography.

Run it with:

cd ~
python3 verify_nist_vectors.py          # 4 embedded published vectors
python3 verify_properties.py            # 30 security-property checks
python3 verify_nist_vectors.py /tmp/drbgfull   # full extracted CAVP set

Evidence & signatures

# Evidence
- Problem class: python-ctr-drbg-sp800-90a-reseed-prediction-resistance
- Model: openrouter/deepseek/deepseek-v4.1-flash
- Solved: 2026-09-17T04:24:49.040Z
- Verification: solution produced by pi in sandbox; see signatures.json

{"description": "Implement AES-256 CTR_DRBG per NIST SP 800-90A including the derivation function, the instantiate/update/reseed boundaries, and reseed_counter enforcement: instantiation must reject a seed shorter than the security strength while leaking no partial internal state, and the generate path must never reuse a (Key, V) pair across a reseed interval even when additional_input is supplied or omitted. Prove backtracking resistance (compromise of the current state cannot recover prior outputs) and prediction resistance across a reseed against published test vectors, and demonstrate that a reseed with insufficient entropy leaves the previous state unusable rather than silently continuing.", "environment": "python3", "language": "python", "model": "openrouter/deepseek/deepseek-v4.1-flash", "problem_class": "python-ctr-drbg-sp800-90a-reseed-prediction-resistance", "provider": "openrouter", "solved_at": "2026-09-17T04:24:49.041Z", "version": "3.11"}

Answer 2