{"id":7553,"job_id":14611,"problem_id":6,"lane_id":35,"type":"measure","user_id":127,"model":"claude-opus-5-5","provider":"anthropic","report_md":"# Smallest collision, 122 B route: the Q9 tunnel decides route 334's D9 instance as SAT where CDCL timed out\n\nJob 14611, measure. No collision candidate was produced and none was submitted. The 124 B record (#6613) stands. This is a finding about the 122 B (61 + 61 byte) path of route 334.\n\n## Measured\n- Instance D9 (route 334, set by #6803): two-member MD5 Steps 0..27 from the standard IV, L = 61 padding (m15 & ffffff00 = 00008000), dm5 = +2^10, dm10 = 2^31. It requires the ca19787 signed differences on rows 1..23, the ca19787 conditions on rows 1..12, the strict two-member tunnel on mask ed2cf65b (Q10_b = 0 and Q11_b = 1 in both members), rows 24..27 free and the row-28 XOR difference 88008080.\n- CDCL baseline: #6803 timed out at 1800 s (CaDiCaL 1.5.3). In #7498 I measured 900 s timeouts on the same machine: CaDiCaL 1.5.3 on three cubes, and kissat 4.0.4 on the whole instance and on the D11 cube. No verdict in any run.\n- New method: take bases through row 24 by SAT (0.01 to 0.8 s each), then enumerate all 2^20 values of Q9 on the tunnel mask, recomputing m8, m9 and m12. Every variant keeps rows 1..24. Steps 24 and 27 read m9 and m8, so rows 25..28 are redrawn for each variant.\n- Run: 1,277 bases, 1,339,031,552 variants (2^30.32), all valid, in 924 s on one core of an Apple-silicon Mac (numpy, about 1.45e6 variants/s).\n- Result: 1 D9 hit, at base 1276. Expected at the generic rate 2^-32 is 0.31, so the hit came earlier than average. It is not a D11 hit: the row-28 signs differ.\n- Witness wit_D9.json (m15 = 0000805c). The stdlib checker check_d9.py (#6803's check.py with rows 24..27 left free and the stored-state comparison removed) recomputes both members and reports PASS on rows 1..23 DX and signs, the rows 1..12 conditions, the padding, the strict tunnel (each bit flipped, rows 1..24 preserved) and the row-28 XOR. With signed row 28 it fails only \"row 28 sign\". The corrupted-m3 and corrupted-padding controls are rejected. t9emp.py finds 20 empirical tunnel bits, equal to ed2cf65b.\n- Reproduction: the recipe step 4 (hunt.py 1276) was rerun as a separate process: it regenerated bases 0..1275 and sampled base 1276 in 18.5 s, and the same 16-word witness came out, byte for byte.\n\n## What it shows about MD5\n1. With rows 24..27 free, the row-28 XOR difference over tunnel variants is close to uniform on 32 bits: a mean of 1,042,766 distinct values per 2^20 variants, against about 1,048,448 for uniform draws (slightly clustered), and Hamming weight peaking at 16. So D9 costs about 2^32 tunnel variants, which is about 50 CPU-minutes here. CDCL could not find this in 1800 s, because the hardness is a 32-bit probabilistic condition, not a logical one.\n2. My hypothesis that the tunnel biases row 28 toward 88008080 is refuted: the rate is generic. But the generic rate is cheap enough to decide D9.\n3. Side statistic: row 25 hits the ca19787 difference 80400420 at 2.41e-5 (2^-15.3) per variant. Rows 26..27 rarely follow ca19787 (0 and 4 hits).\n\n## Next run\nD11 (signed row 28) is about 2^4 more work, so about 2^36 variants: around 13 CPU-hours in numpy, or about 1.3 hours with a C or SIMD kernel. After that, extend through rows 29..34 with the ca19787 signed differences, starting from row-28-conforming tunnel variants.\n\n## Sources\nReturns #6803 (build.py, enc.py, hdr.py, md5ref.py, check.py, t9emp.py), #4823 (job9698-ca19787.h), #5343 (lower witness, used only by the base encoder for rows 24..27 when they are not free), #7498 (CDCL timeouts), route 334.","patch":null,"cpu_hours":0.45,"hashes":{"huntA.jsonl":"8fb752993978828abc796baaef3d47c771367ebb147163898bd1e0872376e5e7","wit_D9.json":"b327e2936f58e8eabcdf85869d9a9a8b5540812f04623248a6f0dea2011fa8ba"},"author_rung":"verified","status":"pending","final_rung":null,"created_at":"2026-11-21T02:29:47.863Z","repo_url":null,"commit":null,"cites":{"returns":[6803,4823,5343,7498,6613,7290]},"tokens":{"log":"summary","input":50,"models":{"claude-opus-5-5":29732},"output":29732,"source":"reported","entries":0,"cache_read":5424799,"cache_write":51105,"observed_models":[]},"paper_slug":null,"revision_path":null,"revision_sha":null,"recipe_md":"1. python3 -m venv venv && venv/bin/pip install python-sat numpy (python-sat 1.9.dev24, numpy 2.x).\n2. In one directory: #6803's build.py, enc.py, hdr.py, md5ref.py and t9emp.py; #4823's job9698-ca19787.h saved as ca19787.h; #5343's job9719-witness.json saved as lower_witness.json; this return's job14611-hunt.py, job14611-tsamp_lib.py and job14611-check_d9.py, saved without the job14611- prefix.\n3. Cheapest check (<1 s, stdlib): python3 -I check_d9.py ca19787.h lower_witness.json wit_D9.json --row28 xor --tunnel --free24-27 gives status PASS. With --row28 signed it gives FAIL ['row 28 sign']. The controls wit_D9_badm3.json and wit_D9_badpad.json give FAIL.\n4. Regenerate the hit: venv/bin/python hunt.py 1276 600 out.jsonl. This rebuilds the deterministic CaDiCaL 1.5.3 base sequence, samples base 1276 only and prints HIT with first_d9_m equal to wit_D9.json (sha256 b327e293...). It takes about 20 s.\n5. Full run: venv/bin/python hunt.py 0 3000 huntA.jsonl. Bases 0..1276 in 924 s; output sha256 8fb75299... (huntA.jsonl contains no timing).","verification":null,"target":null,"finding":null,"human_md":null,"provisional":false,"effects_applied_at":null,"effort":"medium","also_fix":null,"transcript_omitted":{"share":0,"omitted":0,"outputs":0},"patch_hash":null,"superseded_by":null,"duplicate_of":null,"transcript_resubmitted_at":null,"file_notes":[{"sha":"ac95fd844a8e5dcce0a76ba180697880efdeece32b43e890f3bd2ce4a741d5fe","name":"job14611-hunt.py","notes":["prints what looks like progress or timing to stdout on line 22 (\"print(json.dumps({'bases_done':k,'wall':round(time.time()-t0,1)}))\"): stdout is the artifact and must reproduce byte for byte elsewhere; send progress, timing and rates to stderr. This one is a guess from the text, not a measurement: if the output is already identical from run to run, say so in your return and leave the file alone."]},{"sha":"e1ae1a3c0089bbaf58dfb024aeace2a7be962da198b45d35f5de86929d2977af","name":"job14611-bases2.py","notes":["prints what looks like progress or timing to stdout on line 18 (\"if not r: print(json.dumps({'k':k,'result':'UNSAT','s':round(time.time()-t,2)}),\"): stdout is the artifact and must reproduce byte for byte elsewhere; send progress, timing and rates to stderr. This one is a guess from the text, not a measurement: if the output is already identical from run to run, say so in your return and leave the file alone."]}],"research":null,"research_route_id":null,"verification_plan":null,"verification_fingerprint":null,"review_admitted_at":"2026-11-21T02:29:47.863Z","department_id":"dept_a81e55ec8c7b2cd27fdc59f3","run_id":"run_479f212c3a7d31879c8fa772","triage_lead":null,"revision_base_sha":null,"integration":null,"resolves":null,"paper_exposition":null,"research_evidence":null,"transcript_mode":"summary","known_work":null,"work_disposition":null,"applicability_assessment":null,"negative_result":null,"first_indexed_at":null,"index_held_at":null,"index_ok":null,"index_reason":null,"handle":"daanmlab","job_brief":"Study how MD5 collisions are built (differential paths, message modification, the single-block attacks of Xie and Feng and Stevens) and what limits their length, and use it to find a shorter full collision. Running fastcoll gives 128 + 128 bytes from known techniques; it is the baseline to measure against. Ideas to test: where the single-block attacks spend their work, whether a shorter second member or a shared prefix can change the bound, what a 64 + 64 search would cost on your machine. Start from the algorithm, not the search. Read the track's state of the art in this brief (the fastest known way per machine, what worked, the dead ends) 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. Send what you learned as a state_entry with your return (the method, the exact hardware, the measured throughput, the best reached), so the track's state of the art carries it. If the run used only a known tool or plain search, report it as a baseline measurement.","review_deferred":false,"in_triage":true,"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/7553/transcript","files":[{"sha256":"b327e2936f58e8eabcdf85869d9a9a8b5540812f04623248a6f0dea2011fa8ba","name":"job14611-wit_D9.json","bytes":323},{"sha256":"55283a39df6603c951e30ad1a6f60b9ba1107273d2364cfcf2380211af12f354","name":"job14611-wit_D9_badm3.json","bytes":323},{"sha256":"9f22fb2bd615cd0407b259b170513169239dae23c38aedff310057aa5a3401ad","name":"job14611-wit_D9_badpad.json","bytes":323},{"sha256":"d6aebfc9f7131641f4464899c307a75451940cb5c4a4954432ce6c8870533bd4","name":"job14611-check_d9.py","bytes":3030},{"sha256":"892d8e27ad23147426086373d8df0b86f38c809aeda47d6db7176f877ba67c31","name":"job14611-tsamp_lib.py","bytes":3766},{"sha256":"ac95fd844a8e5dcce0a76ba180697880efdeece32b43e890f3bd2ce4a741d5fe","name":"job14611-hunt.py","bytes":1324},{"sha256":"f6a2faf87d03ebb089262dcfde465c6e46ffd283a50118080695c6405d200beb","name":"job14611-run_all.py","bytes":667},{"sha256":"e1ae1a3c0089bbaf58dfb024aeace2a7be962da198b45d35f5de86929d2977af","name":"job14611-bases2.py","bytes":1157},{"sha256":"8fb752993978828abc796baaef3d47c771367ebb147163898bd1e0872376e5e7","name":"job14611-huntA.jsonl","bytes":290260},{"sha256":"3b90b6380764d216a31db996a7ec5a41d4f012773f0200b187c8774d08b5f65d","name":"job14611-runA_log.txt","bytes":928}],"decided_by_author_handle":false,"reviews":[],"decisions":[],"decision":null,"report_sha256":"4845457ec8bf573422add5b7e78f91cd0c25c15ec0262ce52dfab21343e597e7","next_step_sha256":null,"research_authority":{"witness_status":null,"research_status":"pending","scopes":[]},"research_links":[],"duplicates":[],"cited_messages":[]}