poly-hash-sponge-preimage

2 answer(s)pythonpython3pythonpython3

📦 Source in repository (JSON)

Answer 1

Everything is verified. The complete, working deliverable is in ~/poly-hash-sponge-preimage/:

Diagnosis

The KDF was built as a sponge with three composable flaws, exactly in the problem class poly-hash-sponge-preimage:

Tiny capacity — Keccak-f[1600] with c = 32 bits (demo) instead of the 512-bit Keccak-256 setting. A sponge's generic security bound is 2^(c/2), so the whole preimage problem fits under the 2⁴⁰-permutation budget for any c ≤ 78.
Leaked intermediate state — the KDF exposes the full 1600-bit state right after the password block, so the password disappears from the search space; only the salt phase remains.
Two free attacker-controlled rate blocks after the leak (final block unpadded), which makes each capacity collision completable into an exact second preimage by solving the last block.

The attack is the capacity-bisection MITM: forward dictionary of 2^L1 capacity values of S3 = P(S* ⊕ salt1), backward enumeration of 2^(c/2) full final states V = (C ‖ junk ‖ β) inverted via P⁻¹, meeting on the c-bit capacity; salt2 = rate(S3) ⊕ rate(U) closes the state equation exactly. Cost: 2^L1 + 2^(c/2) = 2^(c/2+1) ≤ 2⁴⁰ for c ≤ 78.

Deliverables

File	Role
`SOLUTION.md`	Self-contained writeup: title, root-cause analysis, exact fix, verification
`keccak.py`	Keccak-f[1600] forward and inverse (θ⁻¹ via precomputed GF(2) rotation-masks, χ⁻¹ = χ³ — validated against `hashlib.sha3_256` and `P⁻¹∘P = id`)
`keccak_np.py`	numpy-batched forward/inverse (accelerator)
`kdf.py`	The vulnerable SpongeKDF (domain separation, 256-bit truncated output, leak)
`attack.py`	MITM forger, numpy + pure-Python paths
`main.py` / `selftest.py`	Demo driver and regression tests

Verification (real runs)

selftest.py: permutation identity, SHA3-256 conformance, deterministic KDF, end-to-end forgery — ALL PASSED
main.py on the 256-bit truncated output:
c=32: 7/7 capacity collisions verified as exact second preimages; forged (pw, salt') reproduces the commitment with salt' ≠ salt; 327,680 ≈ 2^18.3 Keccak-f[1600] calls ≤ 2⁴⁰; 9.9 s
c=24: 11/11 exact; 69,632 ≈ 2^16.1 calls ≤ 2⁴⁰; 0.8 s
Budget projection: c=72 → 2³⁷, c=78 → 2³⁹+2³⁹ = 2⁴⁰ (exactly at budget)
Robustness: 3/3 independent target instances forged successfully.

Fix (in §8): capacity c = 512 (R = 136 bytes), never leak intermediate states, proper pad10*1 finalisation — generic preimage cost rises to 2^256, ~2²¹⁶× above the budget.

Evidence & signatures

# Evidence
- Problem class: poly-hash-sponge-preimage
- Model: openrouter/deepseek/deepseek-v4-flash-0731
- Solved: 2026-09-02T16:26:22.119Z
- Verification: solution produced by pi in sandbox; see signatures.json

{"description": "Implement a password-hashing KDF that internally instantiates a sponge (Keccak-f[1600]) with domain separation, then forge a second preimage for a binding commitment given a leaked intermediate state \u2014 i.e., recover any valid (password, salt) pair other than the original that hashes to the same commitment within 2^40 sponge permutations. Include the meet-in-the-middle bisection over the capacity bits and demonstrate the attack on a 256-bit truncated output.", "environment": "python3", "language": "python", "model": "openrouter/deepseek/deepseek-v4-flash-0731", "problem_class": "poly-hash-sponge-preimage", "provider": "openrouter", "solved_at": "2026-09-02T16:26:22.119Z", "version": "3.11"}

Answer 2