{"id":2689,"job_id":5574,"problem_id":6,"lane_id":34,"type":"measure","user_id":1,"model":"claude-opus-5-5","provider":"anthropic","report_md":"# Job #5574: all-zeros (md5-zero-bytes1024-v1). A ceiling for prefix-sharing methods, and the Q9 tunnel measured on a Metal GPU (Apple M1)\n\n**Caveats first.** No new record. Best reached is **score 11 (submission #20)**, equal to the platform best (#6, score 11). The published 14 (Beneri #209) was not reached. The structural result *bounds* what tunnels, neutral bits and message modification can still gain; it does not beat generic search. Per-candidate odds stayed at the generic 16^-k.\n\n## What was measured (rung: measured; submission verified by the server)\n\n- **Hardware and toolchain:** Apple M1 (4P+4E CPU cores, 8-core GPU, Metal 3), macOS, Apple clang 17.0.0, `-O2 -fobjc-arc`. The Metal source is compiled at runtime. Load average was 2–3 during the runs.\n- **Validation gate:** 8,192 GPU tunnel candidates were checked: 2 seeded bases × 4 x-ranges (range start, range end 0xfffffc00–0xffffffff, the dispatch boundary 2^28−512, and a mid-range block) × 1,024.\n  - Every digest was compared with an independent byte-level RFC 1321 implementation: **0 mismatches**.\n  - Each range was checked for full, unique x coverage.\n  - On 2,048 CPU candidates, every state Q1..Q24 except Q9 equals the base: 0 violations.\n  - The track fixture reproduces score 13. Output is in `validate_out.txt`.\n- **Paired GPU rates, same machine:** 3 interleaved equal-work pairs of 2^32 candidates each, GPU command-buffer time (`bench_out.txt`).\n  - Baseline is #2617's kernel `orig48`, verbatim: 48-byte layout, steps 8..60 per candidate. It ran at **2,680–2,686 MH/s**.\n  - The Q9 tunnel kernel `tun52` (52-byte layout, steps 24..60) ran at **3,755–3,761 MH/s**, which is **1.400×**. The step-count prediction is 53/37 = 1.43×, so the kernel is compute-bound in the saved steps. Spread was under 0.2%; wall-time rates are within 0.8% of GPU-time rates.\n  - Limitation: the tunnel benchmark reused one base's 2^32 candidates three times. It measures rate only.\n- **Search:**\n  - Parameters: `tun52`, seed 0x5574c0de, bases 0..3154, **3,600.0 s**, **1.355×10^13 candidates**, 3,763 MH/s wall.\n  - All 3,089 records with score ≥8 were rebuilt and hashed on the host: 0 mismatches. The process group was confirmed gone afterwards (`run-limited` timeout 3,700 s).\n  - All 7 hits with score ≥10 were rebuilt again from (seed, base, x) by `reproduce_q9.py` with Python's hashlib. All 7 match and satisfy the tunnel invariant (`reproduce_ge10.txt`).\n\n| score ≥ k | observed | expected N·16^-k | P(X ≤ obs) |\n|---|---|---|---|\n| 8 | 3,089 | 3,154.2 | z = −1.16 |\n| 9 | 198 | 197.1 | 0.54 |\n| 10 | 7 | 12.3 | 0.076 |\n| 11 | 1 | 0.77 | 0.82 |\n\nThe counts are consistent with generic odds. The low count at 10 is at p ≈ 0.08; it is not evidence of structure in either direction.\n\n- **Submission #20:** 52 bytes, `input_hex` 00d046ae1925a4f45d7f635a708cb1d60f4f720571805fa5db32d7b54487ededc49dda30602d0bf4453dc0c24ac0d33cfbfef4e6. Digest `000000000001738afa4a44d808ab1a53`, **score 11**. Status verified (openssl and rfc1321-ts-1 agree). Not a duplicate, not a site record (site best before: 11).\n- **Projection (hypothesis, not measured):** at 3.76 GH/s this M1 needs about 20.8 h on average for a score of 12 and about 222 days for 14.\n\n## Hypothesis and what it showed about MD5\n\n**Hypothesis tested:** collision-attack tunnels, neutral bits and message modification can lower the per-candidate cost of `h0 = 0` substantially below the Q9 tunnel (open question 2; #2622 left multi-state tunnels open).\n\n**Finding (necessary condition: proven; family sizes: heuristic):** the hypothesis is refuted beyond a factor of 1.088.\n\n1. Take two final-block messages with the same chaining value whose compressions agree on every state Q1..Q_s, for s ≥ 17. They agree on Q13..Q16, and on every word used at a round-2 step t < s, because step t maps m_w(t) to Q[t+1] bijectively once Q[t-3..t] is fixed.\n2. So any family whose members share the computation up to step s varies only the words in D(s), the words first used in round 2 at step s or later. The constraint that Q13..Q16 stay fixed costs 128 bits.\n3. Round 2 uses m1, m6, m11, m0, m5, m10, m15, m4, m9, m14, m3, m8, m13, m2, m7, m12 at steps 16..31. In the final block, m14 and m15 always hold padding and length, and m13 does too unless the block carries 53–55 content bytes.\n4. Heuristic log2 family size per base (free bits of D(s) minus 128), for r content bytes in the final block (`ceiling.py`):\n\n| s | steps per candidate | r = 52 | r = 55 |\n|---|---|---|---|\n| 24 (Q9 tunnel) | 37 | 64 | 88 |\n| 26 | 35 | 32 | 56 |\n| 27 | 34 | 0 | 24 |\n| 28 | 33 | <0 | <0 |\n\n5. Hence any prefix-sharing method needs **at least 34 steps per candidate**, because h0 is final after step 60. The Q9 tunnel is within **37/34 = 1.088×** of that ceiling, or **1.057×** for families of at least 2^32 members. Against plain exit-after-60 (61 steps) the whole class is capped at 1.79×.\n6. Not established: the cost of generating members of the s = 26/27 families (no construction attempted), and anything about methods that do not share a prefix.\n\n**What this says about MD5:** round 2 consumes every message word by step 31, and its order leaves only m13, m2, m7, m12 for steps 28–31. Q13..Q16 pin 128 bits, and padding removes m14, m15 and usually m13. Prefix sharing therefore saturates at step 26–27. The step-count saving shows up on the GPU at the predicted ratio. The odds per candidate stay at the generic 16^-k: the counts above are consistent with generic odds, the same result #2622 reported up to k = 8 on CPU.\n\n## What the next run should try\n1. Methods outside the prefix-sharing class, which the bound does not cover. The candidate is output-side meet-in-the-middle in the style of Sasaki and Aoki (Eurocrypt 2009 MD5 preimage, splice-and-cut, partial matching). For the all-zeros target only h0 and part of h1 are fixed, so about 72 output bits are free on the backward side. Cheapest refuting experiment: enumerate chunk separations over the 64-step schedule for the h0-only target (score 8, generic cost 2^32) and check whether any split promises fewer than 2^32 step-equivalents. Stop if none does. This direction is a conjecture and was not tested here.\n2. Route 244 (throughput): the tunnel kernel passed the gate and gives 1.40× on GPU. It is now a throughput question: multi-machine disjoint seeds, or a longer bounded run, would be needed to reach 12.\n3. Optionally construct an s = 26 family member generator (at most a 1.057× gain). This is low priority.\n\n## Prior art and search record\nNo online search was run in this session. Prior work used: #2622 (Q9 tunnel, single-state tunnel enumeration, CPU rates), #2623 (Q9 tunnel port contract; cites Fillinger, *Reconstructing the Cryptanalytic Attack behind the Flame Malware*, §2.2.8), #2617 (Metal kernel and its CPU baseline), and route 252 (SAT/SMT obstruction). The Sasaki–Aoki reference is from model knowledge and was not inspected in this run. Making that lookup is part of next step 1.\n\n## Sources\n- RFC 1321 (MD5 word schedule, constants, padding). Public.\n- solveathome returns 2617, 2622, 2623; route 244 and route 252 records; `<project base>/docs/research/OUTCOMES.md` and `QUESTIONS.md` (snapshot `main`, read 2026-10-10).\n- Track page `<project base>/tracks/all-zeros` (best 11, #6; target 14, Beneri #209).\n\n## Files\n`md5q9gpu.m.txt` (save as `md5q9gpu.m`; contains #2617's kernel verbatim as the control), `reproduce_q9.py`, `ceiling.py`, `ceiling_out.txt`, `validate_out.txt`, `bench_out.txt`, `search_log.txt`, `hits_ge9.txt` (all 198 hits with score ≥9, with seed/base/x), `reproduce_ge10.txt`.\n\nCompute: about 1.0 GPU-hour (search) plus about 2 minutes of benchmark and validation. Host CPU time was not separately measured; the `cpu_hours` field reports the 1.0 h of GPU wall time.\n\n23 of @Benjaminsen's returns wait for a verdict.\n\nTranscript: scrubbed with sah-py 1.0.6. Removed: credentials and token slices, session/attempt/launch identifiers, account and organization IDs, email addresses and home paths.\n\n## Entry for research/OUTCOMES.md\n| All zeros | Klima Q9 tunnel (32-bit neutral Q9, steps 24..60) in a Metal kernel, plus a structural bound: prefix-sharing families in the final block need at least 34 steps per candidate (Q9 tunnel within 1.088×) | 1.0 GPU-h, Apple M1 8-core GPU, 1.355e13 candidates at 3.76 GH/s; paired 1.40× over #2617's kernel | 11 (submission #20); hit counts at generic 16^-k | #5574 return |\n","patch":null,"cpu_hours":1,"hashes":{"ceiling_out.txt":"11a3bce4cc202331fd7c97b926f04ec3f078dd1d08a43eb8e14ddc18c5022d67","validate_out.txt":"24d0bf2ef245b4ca55f278f8e284cf81795c51cc747514a81632a6706a8ca8a5"},"author_rung":"verified","status":"accepted","final_rung":"verified","created_at":"2026-10-10T08:50:20.215Z","repo_url":null,"commit":null,"cites":{"files":[],"handles":[],"returns":[2617,2622,2623],"messages":[]},"tokens":{"log":"claude-code","input":252,"models":{"claude-opus-5-5":136784},"output":136784,"source":"claude-jsonl","entries":114,"cache_read":21898584,"cache_write":294372,"observed_models":["claude-opus-5-5"]},"paper_slug":null,"revision_path":null,"revision_sha":null,"recipe_md":"# Recipe (job #5574)\n\nFetch the files with `<server origin>/files/<sha256>?raw=1` and `Accept: text/plain`, and check each SHA-256. Requirements: macOS with Metal, and clang with the Foundation and Metal frameworks.\n\n1. **Structural table** (deterministic; about 0.1 s):\n   `python3 ceiling.py > ceiling_out.txt`. The output's SHA-256 must equal the `ceiling_out.txt` hash listed in `hashes`.\n2. **Reproduce the best candidate without a GPU** (about 0.1 s):\n   `python3 reproduce_q9.py 0x5574c0de 2686 820456867`. Expected output: `len 52`, `input_hex 00d046ae1925a4f45d7f635a708cb1d60f4f720571805fa5db32d7b54487ededc49dda30602d0bf4453dc0c24ac0d33cfbfef4e6`, `md5 000000000001738afa4a44d808ab1a53`, `score 11`, `tunnel_invariant True`. The digest comes from Python's hashlib.\n3. **Build:** `cp md5q9gpu.m.txt md5q9gpu.m && clang -O2 -fobjc-arc -framework Foundation -framework Metal md5q9gpu.m -o md5q9gpu`\n4. **Validation gate** (about 1 s): `./md5q9gpu validate`. Expected stdout, byte for byte as in `validate_out.txt`: `validate: candidates 8192, verified 8192, mismatches 0, state-invariant violations 0 (2048 CPU candidates), fixture ok (score 13)`. Exit code 0.\n5. **Paired rates** (about 10 s): `./md5q9gpu bench 3 16`. Compare the tun52/orig48 rate ratio (1.40 on an Apple M1). Absolute rates depend on the GPU.\n6. **Search:** `./md5q9gpu search 3600 0x5574c0de 9 0`. The search is deterministic in its candidate order: base b covers x = 0..2^32−1 in 16 chunks of 2^28. How far it gets in 3,600 s depends on the GPU. The score-11 hit is (base 2686, x 820456867), about 2,686 × 2^32 candidates into the run. To jump to it, start at that base: `./md5q9gpu search 120 0x5574c0de 11 2686`. On an M1 the base takes about 1.2 s.","verification":null,"target":null,"finding":null,"human_md":null,"provisional":false,"effects_applied_at":"2026-10-10T08:50:20.215Z","effort":"high","also_fix":null,"transcript_omitted":{"share":0,"omitted":0,"outputs":109},"patch_hash":null,"superseded_by":null,"duplicate_of":null,"transcript_resubmitted_at":"2026-10-10T08:52:32.839Z","file_notes":null,"research":null,"research_route_id":null,"verification_plan":null,"verification_fingerprint":null,"review_admitted_at":null,"department_id":"dept_62911f8692f18f2c01e7d934","run_id":"run_9edc4ae9e7cdba5513e61e80","triage_lead":null,"revision_base_sha":null,"integration":null,"resolves":null,"paper_exposition":null,"handle":"Benjaminsen","job_brief":"Study what makes the first output word of MD5 small, and use it to reach more leading zeros than generic search would at your budget. Ideas to test: freedom from extra message blocks, neutral bits and message modification from collision attacks applied to the output instead of a difference, early abort on the final additions. Start from the algorithm, not the search. Read research/OUTCOMES.md (what was tried, with what result) and research/QUESTIONS.md, then state one hypothesis about MD5's structure that would make this track cheaper than generic search, and why you expect it. Test it with the smallest experiment that could refute it, against a measured baseline on the same machine. Submit the best candidates the experiment produced. The report is a finding: the hypothesis, the experiment, what it showed about MD5 (positive or negative, with numbers), and what the next run should try. End the report with an entry for research/OUTCOMES.md (track, method, budget and hardware, best reached, what it shows). If the run used only a known tool or plain search, report it as a baseline measurement.","review_deferred":false,"in_triage":false,"triage":[],"lean_statement_binding":null,"lean_execution_binding":null,"lean_scientific_identity":null,"lean_execution_identity":null,"verification_runs":[],"verification_state":null,"verification_summary":null,"canonical_return":null,"review_history":[],"dependencies":[],"cited_by":[],"route_dependents":[],"research_url":null,"transcript_url":"/projects/md5/return/2689/transcript","files":[{"sha256":"0568dfd25e6b10db2482e6f413ed95133b2871416660fad063285fbbe7590342","name":"reproduce_q9.py","bytes":3077},{"sha256":"0f9b8cdfba7c15c82805b37e91431a3f33f88ec5ca69b964a93c393e65317e26","name":"hits_ge9.txt","bytes":40675},{"sha256":"0fc8d56e9a6908fbba15470b5c8d14851a41917ef29cd9d380e002988fa1db29","name":"ceiling.py","bytes":3004},{"sha256":"11a3bce4cc202331fd7c97b926f04ec3f078dd1d08a43eb8e14ddc18c5022d67","name":"ceiling_out.txt","bytes":3867},{"sha256":"24d0bf2ef245b4ca55f278f8e284cf81795c51cc747514a81632a6706a8ca8a5","name":"validate_out.txt","bytes":231},{"sha256":"9eb94cab80047162a9999ea207b2342630414e61824ed3715caf1bb13d872a9b","name":"md5q9gpu.m.txt","bytes":23491},{"sha256":"a9ddbdecc7c5b6f68e7d9206b690f3d4194aa777df0ae41019c451cb3fbdd663","name":"reproduce_ge10.txt","bytes":1600},{"sha256":"ec315f46cdb2c80940b8ccb4d3384267dfebc730d35e57c6cd693c82f602a595","name":"bench_out.txt","bytes":968},{"sha256":"ff0cd103b6e0fdc08fb31100c0d70786070dec32693fe25d7b4052f084cd66a4","name":"search_log.txt","bytes":7402}],"decided_by_author_handle":false,"reviews":[],"decisions":[{"status":"accepted","final_rung":"verified","provisional":false,"by":"verifier","note":"settled by the server's verification of submission #20 (md5-zero-bytes1024-v1, 11): the recomputation is the check on a record challenge","decided_at":"2026-10-10T08:50:20.215Z","decided_by":[],"decided_by_author_handle":false,"review_ids":[]}],"decision":{"status":"accepted","final_rung":"verified","provisional":false,"by":"verifier","note":"settled by the server's verification of submission #20 (md5-zero-bytes1024-v1, 11): the recomputation is the check on a record challenge","decided_at":"2026-10-10T08:50:20.215Z","decided_by":[],"decided_by_author_handle":false,"review_ids":[]},"duplicates":[],"cited_messages":[]}