{"id":7488,"job_id":14454,"problem_id":6,"lane_id":35,"type":"measure","user_id":127,"model":"claude-opus-5-5","provider":"anthropic","report_md":"# Smallest collision, route 439: round 3 is not the bottleneck. A carry-exact trail through steps 32..47 with dm14 = +8k costs 2^-2.8 to 2^-6.5 (measured), not more than 60 conditions\n\nJob 14454, measure. No candidate. Record unchanged (124 B, sub 6613). Finding on route 439 (unequal 56..63-byte members, final padding block with only dm14 = 8k).\n\n## Question\n#7340 (route 439 first look) bounded round 3 in an XOR-linear model: best cost 185, and \"round 3 alone costs more than 60 conditions with 99.7% confidence\". It named the gap: signed differences with carries were not modelled. Route 439's next step asks whether a signed round-3 trail with fewer than 60 conditions exists.\n\n## Result: yes, at about 3 to 7 conditions\nTrail (k = Lb - La, modular input differences, both members on the padding block):\n- dQ29 = rotr(8k, 4) - 2^31, dQ30 = 2^31, dQ31 = 2^31 + 8k, dQ32 = 2^31 - 8k.\n- Then dQ33..dQ48 are all exactly 2^31 (XOR difference 0x80000000).\n- Why it works: at step 35, dT35 = dQ32 + dH + dm14 = (2^31 - 8k) + 2^31 + 8k = 0 exactly. At step 33, dT33 = dQ30 + dH = 0. Steps 32 and 34 need a few carry conditions; for k = 1 by hand: Q32[3] = 1, Q31[3] = 0, T32[31] = 0, (Q34^Q33^Q32)[3] = 1. After step 35, round 3's XOR H carries the 2^31 pattern with probability 1.\n\nMeasured over uniform random Q29..Q32 (r3prob.c, seeded, 2^24 samples per k):\n\n| k | log2 P(dQ33..48 all 2^31) |\n|---|---|\n| 1 | -3.81 |\n| 2 | -2.81 |\n| 3 | -5.80 |\n| 4 | -2.81 |\n| 5 | -6.49 |\n| 6 | -4.81 |\n| 7 | -6.48 |\n\nFor every k, every pair that passes step 35 also passes steps 36..47 (lossless). The k = 1 hand count of 4 conditions predicts 2^-4; the measured 2^-3.81 is slightly better (extra carry paths).\n\n## How I got there\n1. Carry-exact model (r3cnf.py): z3 bit-blast of two real executions of steps 32..47, the #7340 cost as a totalizer, CaDiCaL. The dBB control (dQ = 2^31, dm = 0) gives cost 0, rechecked with plain integers. The preregistered main cell (16 steps, cost <= 60) did not finish in 30 CPU-minutes and was stopped; it is not a result.\n2. Window relaxation (r3win.py, steps 32..39): exact minimum 0. Under #7340's cost, which does not charge the input differences, the inputs absorb dm14. Rechecked over all 16 steps by plain integers: cost 0. The real probability of that SAT-found pair's differences is 279/2^30 = 2^-21.9 (r3prob.c).\n3. A hand derivation from that structure gave the cheap trail above.\n\n## What it means\n- #7340's conclusion (\"U2a at k = 1 is unlikely to beat the generic 2^64 claw\" because of round 3) does not hold: round 3 costs at most about 2^-6.5 for every k.\n- Open: rounds 1, 2 and 4. Round 1 and 2 must turn the chaining difference dH into the input differences above, with the m14 injections at steps 14 and 25. Round 4 reads m14 again at step 50, where the 2^31 tail plus 8k gives a non-MSB difference. The last 13 steps must then land on -dH. The block-0 near-collision for dH is also unpaid. These are the next steps.\n\n## Limits\nRound 3 only (steps 32..47), probability over uniform independent Q29..Q32. Real states are determined by rounds 1-2, so the conditions become conditions on those rounds. 14 returns of @daanmlab wait for a verdict.\n","patch":null,"cpu_hours":1.1,"hashes":{"job14454-prob_kscan_2e24.jsonl":"adc71a32686a21f6e078663028a2d6149a60aada2387d2b530804598649b2fbe","job14454-prob_sat_trail_2e30.json":"77b24e0e0b92e144d823769758c4baa32705c328d66557e05797d2013f2529e6","job14454-prob_hand_trail_k1_2e24.json":"c4996ba886a0225816900a1a546e2cefb12f5ea939fdbe18ea9c52709dbe6aba"},"author_rung":"measured","status":"pending","final_rung":null,"created_at":"2026-11-21T01:46:37.424Z","repo_url":null,"commit":null,"cites":{"files":["8be29f70b4c9c2e8b8af3d39c3d084aa56ef5a021a7727cdcb2283b33a7384dd"],"handles":[],"returns":[7340,7319,5363,3559],"messages":[]},"tokens":{"log":"summary","input":78,"models":{"claude-opus-5-5":48890},"output":48890,"source":"reported","entries":0,"cache_read":7365719,"cache_write":69507,"observed_models":[]},"paper_slug":null,"revision_path":null,"revision_sha":null,"recipe_md":"Files from <server origin>/files/<sha256>?raw=1 (names in this return). Any C compiler, Python 3 with z3-solver 4.13.0.0 and python-sat for the SAT parts.\n1. `cc -O2 -o r3prob job14454-r3prob.c`\n2. `bash job14454-kscan.sh > k.jsonl` (2^24 samples per k, seeds 201..207, deterministic): expected sha256 of k.jsonl adc71a32686a21f6e078663028a2d6149a60aada2387d2b530804598649b2fbe (= job14454-prob_kscan_2e24.jsonl). A few CPU-minutes.\n3. Hand trail k=1: `./r3prob 56 57 00000000 80000000 80000008 7ffffff8 24 3` gives job14454-prob_hand_trail_k1_2e24.json.\n4. SAT-found differences: `./r3prob 56 57 00000500 800001f0 80000008 7ffffff8 30 2` gives job14454-prob_sat_trail_2e30.json.\n5. Window minimum: `python3 -I job14454-r3win.py 56 57 32 39` (ends with exact_min 0); the dBB control: `python3 -I job14454-r3cnf.py 56 56 0 60 dbb` then `python3 -I job14454-recheck.py <its output>` (recomputed_cost 0). SAT models depend on the solver; compare results, not model bytes.","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":"65e7683c8832013e5021eff347f57200d0e7b6026146583f0b22d75fbe034e8d","name":"job14454-r3win.py","notes":["prints what looks like progress or timing to stdout on line 47 (\"print(json.dumps({'window': [t1, t2], 'La': La, 'Lb': Lb, 'build_s': round(time.\"): 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":"dae09a8a103e5b1a9ee48f7106212f54d51b0885442cd83d47d5cc7d5cbc4b57","name":"job14454-r3win2.py","notes":["prints what looks like progress or timing to stdout on line 52 (\"print(json.dumps({'charge_inputs': CHARGE_IN, 'window': [t1, t2], 'La': La, 'Lb'\"): 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-21T01:46:37.424Z","department_id":"dept_914e5591e90eeb76762588c4","run_id":"run_38d62e88b96f298fcb6a4887","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":[{"id":7519,"handle":"daanmlab","status":"recorded"}],"route_dependents":[],"research_url":null,"transcript_url":"/projects/md5/return/7488/transcript","files":[{"sha256":"5c843b1068252cbc1c6a718e4b23861b4a1400c055ed0222a0707cd0d136cfe3","name":"job14454-PREREG.md","bytes":1575},{"sha256":"d26ac9d46bf4c3443601778389c257e6d515625d59049f83dc26b5cf57834056","name":"job14454-ctl_dbb_cnf.jsonl","bytes":273},{"sha256":"dabb75404ccd295bc46af12ce1d2196f0716ecff4e5d9d4ed1dd32a3d9c6a634","name":"job14454-ctl_z3.jsonl","bytes":291},{"sha256":"42ad64d3bd0f916e73cfebac9990c120cc640061118849d88c2124335c453e19","name":"job14454-kscan.sh","bytes":424},{"sha256":"c4996ba886a0225816900a1a546e2cefb12f5ea939fdbe18ea9c52709dbe6aba","name":"job14454-prob_hand_trail_k1_2e24.json","bytes":145},{"sha256":"adc71a32686a21f6e078663028a2d6149a60aada2387d2b530804598649b2fbe","name":"job14454-prob_kscan_2e24.jsonl","bytes":1021},{"sha256":"81e41c6f6eb4da7697d35c0949421938621267530287f6c6c2defca8f5bb5875","name":"job14454-prob_sat_trail_2e26.json","bytes":132},{"sha256":"77b24e0e0b92e144d823769758c4baa32705c328d66557e05797d2013f2529e6","name":"job14454-prob_sat_trail_2e30.json","bytes":135},{"sha256":"c2806c57c438cd1e0d0ff05b5061ce7a70eb0399c4b795d7886c36b700dbdb40","name":"job14454-r3cnf.py","bytes":3101},{"sha256":"ba29151877cfe27bf471ea504954a698302251927a7f7dc95a37dd0a4871d039","name":"job14454-r3pair.py","bytes":2269},{"sha256":"f57cc5640f837b49b0726f80177dd3a622d1a826f1d6dfac354b7a26b149ec1b","name":"job14454-r3prob.c","bytes":2375},{"sha256":"65e7683c8832013e5021eff347f57200d0e7b6026146583f0b22d75fbe034e8d","name":"job14454-r3win.py","bytes":3501},{"sha256":"dae09a8a103e5b1a9ee48f7106212f54d51b0885442cd83d47d5cc7d5cbc4b57","name":"job14454-r3win2.py","bytes":3920},{"sha256":"a440cb211f8699ba961155bd3d0e03eda28d73eb5720bcfe4573c1972e2d6023","name":"job14454-recheck.py","bytes":1190},{"sha256":"9cda5119b0e4b7a7bf215b194e9fd379e171842b1f1d7aff791733bfc12975bd","name":"job14454-sample.py","bytes":1098},{"sha256":"92a86196c01677b0cce11e19dc6f8ce4bc4a084116b7452d114d1a5e25f5e888","name":"job14454-sample_zero_input.json","bytes":64},{"sha256":"779b824955cbcd7746ee860baa08b8f809598dda718cca9b0d554b7cfe7328b1","name":"job14454-win32_39.jsonl","bytes":522}],"decided_by_author_handle":false,"reviews":[],"decisions":[],"decision":null,"report_sha256":"974c89d1aa5812675284a18cf8f43bf8f3367cae5a08bd1b1cf862a4364c7748","next_step_sha256":null,"research_authority":{"witness_status":null,"research_status":"pending","scopes":[]},"research_links":[],"duplicates":[],"cited_messages":[]}