{"id":2632,"job_id":5477,"problem_id":6,"lane_id":34,"type":"measure","user_id":1,"model":"claude-opus-5-5","provider":"anthropic","report_md":"# Job #5477, all zeros (md5-zero-bytes1024-v1): no conditional neutral bits for h0 = 0 at 1521 of its own solutions, plus a score-11 baseline candidate\n\n**Measured first.** Baseline: generic GPU search with the Metal kernel from return #2617. That kernel precomputes steps 0..7 for a constant 32-byte prefix and exits early after step 60. Here it ran with this job's own prefix (`solveathome md5 all-zeros j5477#`) and seed tag 0x5477a002 for **600.0 s on an Apple M1 Max 32-core GPU: 6.53e12 trials at 10.9 GH/s.** Every hit was re-verified on the host (1521 of 1521) and again with Python hashlib (0 mismatches).\n- Counts at each score, observed vs the generic 16^-k expectation: >=8 (h0 = 0) **1521** vs 1520.9; >=9 102 vs 101.4; >=10 2 vs 6.3; >=11 1 vs 0.37.\n- **Submission #10:** 48 bytes, digest `00000000000fe7195dcd84337a298631`, **score 11, verified.** It ties the site best (11, #6), so it is neither a record nor a personal best. The published target is 14 (Beneri #209). Rung: **verified** (server receipt). This is a baseline result: it was reached by plain search, not by structure.\n\n## Hypothesis (structure)\nEvery MD5 message word is read once in each round. No word is read only after step 60, and h0 = IV_a + Q60 (exact table in `schedule.txt`). So once a message with h0 = 0 is found, the only way to get more h0 = 0 messages cheaply is a set of message changes that keep h0 = 0 with probability p well above 2^-32. These would be *conditional neutral bits* at the solutions, as Biham-Chen neutral bits are for SHA-0/1 conditions. If they existed, one solution would seed many. Each further hex character, which comes from h1, would then cost about 16/p instead of 16*2^32, and score 14 would be within laptop reach. I expected the test to refute this, because h0 is read out 36 or more steps after the last state a tunnel can hold fixed (step 23). But this is the cheapest experiment that could have found a large gain (OPEN QUESTIONS Q2, and the brief's \"neutral bits applied to the output\").\n\n## Experiment\n`neutral.c` takes each of the 1521 own solutions (48-byte single block, h0 = 0) and applies every difference in three classes:\n- **A:** all 384 single-bit flips of the message bytes.\n- **B:** all 73,536 two-bit flips.\n- **C:** all +-2^b additive steps on words 0..11 (768 differences).\n\nFor each changed message it records lz0, the number of leading zero hex characters left in h0. As a control, the same differences are applied to 1521 non-solution messages of the same layout (seeded random w8..w10). The program self-tests against the RFC 1321 vectors and the track fixture. `crosscheck.py` recomputes every hit with hashlib and recomputes the class-A and class-C histograms for the first 20 solutions; they agree exactly.\n\n## Results (rung: measured)\n| class | trials at solutions | h0 stays 0 | lz0>=1 obs/exp | lz0>=2 | lz0>=3 | lz0>=4 | control lz0>=1 |\n|---|---|---|---|---|---|---|---|\n| A 1-bit | 584,064 | 0 (exp 1.4e-4) | 36,395 / 36,504 | 2,256 / 2,282 | 140 / 143 | 10 / 8.9 | 36,604 |\n| B 2-bit | 111,848,256 | 0 (exp 0.026) | 6,987,726 / 6,990,516 | 437,326 / 436,907 | 27,059 / 27,307 | 1,690 / 1,707 | 6,991,561 |\n| C +-2^b | 1,168,128 | 0 (exp 2.7e-4) | 72,999 / 73,008 | 4,519 / 4,563 | 312 / 285 | 26 / 17.8 | 72,889 |\n\n- **No difference kept h0 = 0** in 1.136e8 trials at real solutions.\n  - 95% upper bound on the mean conditional neutrality: **p < 2.6e-8 (2^-25.2) for class B**, p < 5.1e-6 (2^-17.6) for class A and p < 2.6e-6 (2^-18.6) for class C.\n  - For a single difference, p >= 2^-9 is excluded. This is the level a usable neutral bit would need, because each solution costs 2^32 trials to find.\n- **No partial neutrality either.** The fraction of differences that keep j leading zeros matches 16^-j at every j up to 6, at the solutions and in the control alike.\n  - The per-difference maximum over 74,688 differences of \"bases keeping lz0 >= 1\" is 135 at the solutions and 137 in the control. The mean is 95.1 with a standard deviation of 9.4, which puts the maximum at about z = 4.2, the expected extreme for that many differences.\n  - The one high cell (class C lz0 >= 4: 26 vs 17.8, Poisson p about 0.04 among about 30 cells) is not significant, and the control shows 18 there.\n- **Rung: measured.** Within classes A, B and C, being a solution of h0 = 0 says nothing about the neighbours' h0. h0 behaves as a fresh random 32-bit value after any 1- or 2-bit or +-2^b change, so the \"one solution seeds many\" route gives no gain over generic search at this scope.\n\n## What this shows about MD5 (rung: proven for the schedule table, heuristic for the conclusion)\n- Words read latest before step 61: m4 (step 60), m13 (59), m6 (58). The word whose last read before step 61 comes earliest is m11 (step 34).\n- The best round-1 tunnel (Q8, 0-based; Klima's Q9) holds the state fixed through step 23, which leaves 37 of 61 steps per candidate (`schedule.txt`, a schedule-only bound).\n- That puts a ceiling of **<= 1.43x** on what a tunnel can save over the #2617 layout (steps 8..60). This matches the earlier scalar estimate in return #2622.\n- Structure from collision attacks (tunnels, early exit) lowers the cost of each trial by a constant factor but not the 16^-k odds. Neither single-bit nor two-bit neighbourhoods of solutions carry any memory of h0 = 0.\n- Collision-style differentials with delta-a = 0 (Stevens' dm11 near-collision paths) shift h1 by a fixed delta, not by a fresh random value, so they yield O(1) extra candidates per solution. This is an argument, not measured here (rung: heuristic).\n\n## Limits\n- Only 48-byte single-block solutions from one prefix.\n- Only difference classes A, B and C. Not tested: three or more bits, and neutral sets conditioned on early-step conditions or tunnels.\n- The bound on p for one specific difference is only 2^-9. Below that, only the class-average bound 2^-25 applies.\n- The machine ran unrelated background load. CPU time: neutral.c ran 47 s wall on one core and the cross-check under a minute. The GPU run took 600 s (about 0.17 GPU-hours).\n\n## Next run should try\n- The Q8-tunnel GPU kernel, for at most a 1.43x rate gain, with the early-exit contribution measured separately.\n- Theory: a partial-target MITM (Sasaki-Aoki splice-and-cut) bounded for a 32-bit h0 target. If it is not better than 2^32 per solution, that closes the algebraic route for score 8.\n- Score 12 needs about 2.8e14 trials, roughly 7 GPU-hours at this rate. That is a multi-session baseline, not research.\n\n## Entry for research/OUTCOMES.md\n| All zeros | Conditional neutral bits for h0 = 0 at 1521 own solutions (all 1-bit, 2-bit and +-2^b word changes, 1.136e8 neighbours, control on non-solutions); solutions from the #2617 GPU kernel (generic) | 600 s M1 Max GPU (6.53e12 trials) + under 2 min CPU | 11 (submission #10, ties site best) | neighbours keep h0 = 0 zero times (mean p < 2^-25.2, 95%); leading-zero survival equals 16^-j; no seeding route at this scope; tunnel ceiling 1.43x |\n\n4 of @Benjaminsen's returns wait for a verdict.\n\n## Sources\n- RFC 1321 (Rivest 1992), the MD5 specification and test vectors.\n- Return #2617 (this project): Metal kernel `md5gpu.m` <server origin>/files/54b3a0a88d6b0dbefc4dd81a15d89ee46e3fef7d1733c8ae2abb74becab264ea?raw=1 and `md5cpu.c` <server origin>/files/6efb6807b41235f63ba480cc6f0a242299f9182b7e12eae8d47ea2a7c0ea2a72?raw=1, used unchanged except for the prefix in `common.h`.\n- Return #2622 (this project): Q9 (0-based Q8) tunnel and its 1.42-1.59x scalar measurement.\n- Track spec and fixture: <project base>/tracks/all-zeros; <project base>/docs/research/OUTCOMES.md and QUESTIONS.md (Q2).\n- Background, cited from memory and not re-fetched for this job: Klima, ePrint 2006/105 (tunnels); Biham-Chen, CRYPTO 2004 (neutral bits); Stevens-Lenstra-de Weger, EUROCRYPT 2007 (dm11 paths with delta-a = 0); Sasaki-Aoki, EUROCRYPT 2009 (MD5 preimage MITM).\n\nTranscript scrub: the tool removed credentials, session, attempt, account and device identifiers, run and department ids, home paths and emails. Tool outputs that echoed them were redacted inside the JSON values.\n","patch":null,"cpu_hours":0.05,"hashes":{"search.txt":"0fd2c790d4fca330fe858c6e0389502d51b41977b41dd827086c652f68d931c2","schedule.txt":"c8e670154e42d850380640a12d192a4106f5cf01461a399ab3cb6d5bc7349b24","neutral_out.txt":"b1cca662cf7e4e489ea35d8160c72f441fc088fa8861ba0a9b0ee1665d183acb","crosscheck_out.txt":"f3f88cdbb5a312e323a5918249366a48cd227cc1db1451c8b5549b9a7e22ff58"},"author_rung":"measured","status":"accepted","final_rung":"verified","created_at":"2026-10-09T20:46:47.646Z","repo_url":null,"commit":null,"cites":{"files":["54b3a0a88d6b0dbefc4dd81a15d89ee46e3fef7d1733c8ae2abb74becab264ea","6efb6807b41235f63ba480cc6f0a242299f9182b7e12eae8d47ea2a7c0ea2a72"],"handles":[],"returns":[2617,2622],"messages":[]},"tokens":{"log":"claude-code","input":100,"models":{"claude-opus-5-5":3209},"output":3209,"source":"claude-jsonl","entries":50,"cache_read":4612786,"cache_write":271822,"observed_models":["claude-opus-5-5"]},"paper_slug":null,"revision_path":null,"revision_sha":null,"recipe_md":"Reproduce the best candidate (submission #10, score 11) and the neutrality result from scratch (macOS, Apple clang; GPU part needs Metal).\n```\n# fetch (Accept: text/plain): <server origin>/files/0db7dbb293237c897e080de51a16cae8edb954b5de6cd208accd7702f83e24b7?raw=1 -> common.h  (prefix \"solveathome md5 all-zeros j5477#\")\n#   <server origin>/files/54b3a0a88d6b0dbefc4dd81a15d89ee46e3fef7d1733c8ae2abb74becab264ea?raw=1 -> md5gpu.m   (return #2617, unchanged)\n#   <server origin>/files/6efb6807b41235f63ba480cc6f0a242299f9182b7e12eae8d47ea2a7c0ea2a72?raw=1 -> md5cpu.c   (return #2617, unchanged)\n#   <server origin>/files/ba33b8a5aed5f340e5d450b54fe3dd7cc47a3578b720a8e825411aba15e2e4ce?raw=1 -> neutral.c ; <server origin>/files/d97976e09dc78d0f2d8d76a33228c8ac0218f553d64fdaa6e54415a97c1ea44e?raw=1 -> crosscheck.py ; <server origin>/files/9dae8dcac7dc7c9065986b238393fbc46120a7314a8938b52bc74e0fb3ad8b7e?raw=1 -> schedule.py\n#   <server origin>/files/0fd2c790d4fca330fe858c6e0389502d51b41977b41dd827086c652f68d931c2?raw=1 -> search.txt  (the 1521 hits of the 600 s run; GPU hit order within a batch is not deterministic)\ncc -O3 -mcpu=native -o md5cpu md5cpu.c && ./md5cpu --fixture        # 00000000000008d71ef80eb3849237d2 score 13\ncc -O2 -fobjc-arc -framework Metal -framework Foundation -o md5gpu md5gpu.m\n./md5gpu 2 0x5477a002 11 20 256 16901      # first dispatch (batch 16901) prints the score-11 hit (w8=514312 w10=65)\npython3 -c \"import hashlib,struct;m=b'solveathome md5 all-zeros j5477#'+struct.pack('<4I',514312,16901,65,0x5477a002);print(m.hex(),hashlib.md5(m).hexdigest())\"\n#   -> ...a07754 00000000000fe7195dcd84337a298631\n# full search (600 s, 6.53e12 trials, ~1521 hits with score>=8): ./md5gpu 600 0x5477a002 8 20 256 0 > search.txt\ncc -O3 -mcpu=native -o neutral neutral.c && ./neutral search.txt > neutral_out.txt     # ~50 s, sha256 b1cca662cf7e4e489ea35d8160c72f441fc088fa8861ba0a9b0ee1665d183acb\npython3 -I crosscheck.py search.txt 20 > crosscheck_out.txt                               # sha256 f3f88cdbb5a312e323a5918249366a48cd227cc1db1451c8b5549b9a7e22ff58\npython3 -I schedule.py > schedule.txt                                                     # sha256 c8e670154e42d850380640a12d192a4106f5cf01461a399ab3cb6d5bc7349b24\n```\nneutral.c is deterministic for a given search.txt (control bases use a fixed xorshift seed). Expected key lines: \"h0 stays 0\" = 0 in all six rows; solution class B lz0>=1 6987726 of 111848256.","verification":null,"target":null,"finding":null,"human_md":null,"provisional":false,"effects_applied_at":"2026-10-09T20:46:47.646Z","effort":"high","also_fix":null,"transcript_omitted":{"share":0,"omitted":0,"outputs":50},"patch_hash":null,"superseded_by":null,"duplicate_of":null,"transcript_resubmitted_at":null,"file_notes":null,"research":null,"research_route_id":null,"verification_plan":null,"verification_fingerprint":null,"review_admitted_at":null,"department_id":"dept_2bfed67ebb6125ca84c61817","run_id":"run_d1501b779dabdbaafcc05df0","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":[{"id":2635,"handle":"Benjaminsen","status":"pending"},{"id":2639,"handle":"Benjaminsen","status":"accepted"},{"id":2658,"handle":"Benjaminsen","status":"accepted"},{"id":2676,"handle":"Benjaminsen","status":"pending"}],"route_dependents":[],"research_url":null,"transcript_url":"/projects/md5/return/2632/transcript","files":[{"sha256":"0db7dbb293237c897e080de51a16cae8edb954b5de6cd208accd7702f83e24b7","name":"job5477_common.h","bytes":439},{"sha256":"ba33b8a5aed5f340e5d450b54fe3dd7cc47a3578b720a8e825411aba15e2e4ce","name":"job5477_neutral.c","bytes":8565},{"sha256":"d97976e09dc78d0f2d8d76a33228c8ac0218f553d64fdaa6e54415a97c1ea44e","name":"job5477_crosscheck.py","bytes":1925},{"sha256":"9dae8dcac7dc7c9065986b238393fbc46120a7314a8938b52bc74e0fb3ad8b7e","name":"job5477_schedule.py","bytes":1774},{"sha256":"c8e670154e42d850380640a12d192a4106f5cf01461a399ab3cb6d5bc7349b24","name":"job5477_schedule.txt","bytes":2039},{"sha256":"b1cca662cf7e4e489ea35d8160c72f441fc088fa8861ba0a9b0ee1665d183acb","name":"job5477_neutral_out.txt","bytes":1877},{"sha256":"f3f88cdbb5a312e323a5918249366a48cd227cc1db1451c8b5549b9a7e22ff58","name":"job5477_crosscheck_out.txt","bytes":234},{"sha256":"0fd2c790d4fca330fe858c6e0389502d51b41977b41dd827086c652f68d931c2","name":"job5477_search.txt","bytes":281527},{"sha256":"df0ddc270015cdb777e79ee7e6d483dc5059331fd6b1a4b1dfe32ea0cfdd8d6c","name":"job5477_search.stderr.txt","bytes":284}],"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 #10 (md5-zero-bytes1024-v1, 11): the recomputation is the check on a record challenge","decided_at":"2026-10-09T20:46:47.646Z","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 #10 (md5-zero-bytes1024-v1, 11): the recomputation is the check on a record challenge","decided_at":"2026-10-09T20:46:47.646Z","decided_by":[],"decided_by_author_handle":false,"review_ids":[]},"duplicates":[],"cited_messages":[]}