python-sha1-length-extension-forged-mac
All verified. Done.
Deliverables in ~/:
- solution.md — the requested writeup (title, root-cause analysis, exact fix, verification)
- sha1_length_extension.py — the runnable implementation (also embedded in the markdown)
Root cause: MAC = SHA1(secret || message) is insecure because SHA-1 is a Merkle–Damgård hash: the 160-bit digest is the internal compression state after secret || message || padding. Since the compression function is public, the known MAC fully reconstructs the 5 state words (h0..h4), allowing the hash to be resumed at the exact point the secret left off — no secret needed. The only unknown is |secret| (1..64 bytes), which is brute-forced: each candidate length yields a candidate glue_padding, and exactly one forged (message || glue || suffix, MAC) pair is accepted by the server.
Verification performed:
- Compression function matches hashlib.sha1 on vectors crossing every 64-byte block boundary (0, 3, 55, 56, 64, 65, 200, 768 bytes)
- End-to-end simulation: secret of 57 bytes hidden — brute-force over 64 lengths yields exactly one pair the simulated server accepts, at the true length; all 63 wrong-length candidates rejected
- 300 random trials (secret 1..64 B, message 0..500 B, suffix 0..120 B): 0 failures; forged MAC always equals direct SHA1(secret || forged_message)
- Code embedded in solution.md extracted and re-run: behavior identical to the tested module
# Evidence - Problem class: python-sha1-length-extension-forged-mac - Model: openrouter/deepseek/deepseek-v4-flash-0731 - Solved: 2026-08-31T10:37:28.320Z - Verification: solution produced by pi in sandbox; see signatures.json
{"description": "A server authenticates requests with MAC = SHA1(secret || message) where secret is an unknown byte string of length between 1 and 64 bytes. Given one valid (message, MAC) pair with a known message byte length (but no secret), forge an authentication tag for a new message message || glue_padding || suffix, where glue_padding is the SHA-1 MD-compliant padding for the original secret||message length. Implement SHA-1 length extension by reconstructing the five 32-bit state words from the known MAC digest, continuing the compression function on the forged suffix, and return the exact forged bytes and MAC; the server must accept the forged pair.", "environment": "python3", "language": "python", "model": "openrouter/deepseek/deepseek-v4-flash-0731", "problem_class": "python-sha1-length-extension-forged-mac", "provider": "openrouter", "solved_at": "2026-08-31T10:37:28.320Z", "version": "3.11"}All verified. Done.
Deliverables in ~/:
- solution.md — the requested writeup (title, root-cause analysis, exact fix, verification)
- sha1_length_extension.py — the runnable implementation (also embedded in the markdown)
Root cause: MAC = SHA1(secret || message) is insecure because SHA-1 is a Merkle–Damgård hash: the 160-bit digest is the internal compression state after secret || message || padding. Since the compression function is public, the known MAC fully reconstructs the 5 state words (h0..h4), allowing the hash to be resumed at the exact point the secret left off — no secret needed. The only unknown is |secret| (1..64 bytes), which is brute-forced: each candidate length yields a candidate glue_padding, and exactly one forged (message || glue || suffix, MAC) pair is accepted by the server.
Verification performed:
- Compression function matches hashlib.sha1 on vectors crossing every 64-byte block boundary (0, 3, 55, 56, 64, 65, 200, 768 bytes)
- End-to-end simulation: secret of 57 bytes hidden — brute-force over 64 lengths yields exactly one pair the simulated server accepts, at the true length; all 63 wrong-length candidates rejected
- 300 random trials (secret 1..64 B, message 0..500 B, suffix 0..120 B): 0 failures; forged MAC always equals direct SHA1(secret || forged_message)
- Code embedded in solution.md extracted and re-run: behavior identical to the tested module
# Evidence - Problem class: python-sha1-length-extension-forged-mac - Model: openrouter/deepseek/deepseek-v4-flash-0731 - Solved: 2026-08-31T10:37:28.320Z - Verification: solution produced by pi in sandbox; see signatures.json
{"description": "A server authenticates requests with MAC = SHA1(secret || message) where secret is an unknown byte string of length between 1 and 64 bytes. Given one valid (message, MAC) pair with a known message byte length (but no secret), forge an authentication tag for a new message message || glue_padding || suffix, where glue_padding is the SHA-1 MD-compliant padding for the original secret||message length. Implement SHA-1 length extension by reconstructing the five 32-bit state words from the known MAC digest, continuing the compression function on the forged suffix, and return the exact forged bytes and MAC; the server must accept the forged pair.", "environment": "python3", "language": "python", "model": "openrouter/deepseek/deepseek-v4-flash-0731", "problem_class": "python-sha1-length-extension-forged-mac", "provider": "openrouter", "solved_at": "2026-08-31T10:37:28.320Z", "version": "3.11"}