{"id":2619,"job_id":5446,"problem_id":6,"lane_id":35,"type":"explore","user_id":1,"model":"claude-opus-5-5","provider":"anthropic","report_md":"# Where the single-block MD5 collision attack spends its work, and what 64 + 64 costs on a laptop (job #5446)\n\nQuestion 3 (shorter full collisions), track `md5-collision-totalbytes1024-v1`. Explore, no candidate submitted.\n\n## Claims (rung per claim)\n\n1. **Cited: the cost splits 2^15.96 × 2^33.85.** Stevens 2012 gives 2^49.81 compressions as two factors:\n   - 2^15.96 per message pair that meets every bitcondition through Q29. This covers first-round freedom plus tunnels T4, T9 and T14, measured on a Core2 Q9550.\n   - 2^33.85 for P(collision | conditions through Q29), also measured by Stevens.\n\n   So about 68% of the exponent is uncontrolled probability in steps 29–63, not message modification.\n2. **Measured: the published pair is verified and follows the path.** I recomputed the pair (MD5 `008ee33a9d58b51cfeb425b0959121c9`):\n   - δm8 = 2^25, δm13 = 2^31, as printed.\n   - Its δQ trail matches Table 2.\n   - It deviates from Table 3 only (a) at bits inside the tunnel masks in rows 3, 4, 9 and 14, which the tunnels flip, and (b) at bit-31 signs in rows 27–55, which the paper allows.\n3. **Measured: the tail decomposes by step (independent Monte Carlo, my own code).** Model: (Q, Q′) states that satisfy Table 3 rows 26–29, uniform random message words with Stevens' δm, and real MD5 steps 29–63 on both members. Sample sizes: 3 × 2^32 samples for steps 29→48 (6,893 survivors at step 48) and 4·10^6 samples for steps 48→64. Cost in bits per step range:\n\n   | steps | 29→30 | 30→31 | 31→32 | 32→33 | 33→34 | 34→35 | 35→38 | 38→48 (round 3) | 48→64 (round 4) |\n   |---|---|---|---|---|---|---|---|---|---|\n   | bits | 1.00 | 4.03 | 5.61 | 2.20 | 2.58 | 2.32 | 3.09 | **0** | **12.0** |\n\n   - The model total is 2^-32.84. Stevens measured 2^-33.85, so the uniform-state model is about 2× optimistic.\n   - The direct run saw 2 full-tail survivors in 2^33.58 samples, which is consistent.\n   - About 63% of the tail sits in steps 30–37: the round-2 to round-3 transition, where m8 (2^25) re-enters at step 33 and the differences collapse to bit 31.\n   - About 37% sits in round 4.\n   - Round 3 costs nothing, because H passes bit-31 differences with probability 1.\n4. **Measured, with an exact count: round-4 cost depends only on position, 2^-(p−44).** A pure bit-31 run entering round 4 must be cancelled by a word pair:\n   - m_j at round-4 step p with δm_j = 2^(31−RC_p);\n   - m_i at step p + 3 with δm_i = 2^31.\n\n   For all 13 members (p = 48…60) the Monte Carlo (start at step 48, N = 4·10^6 each) gives log2 P = −4.00, −4.99, −5.99, −6.99, −7.98, −9.01, −10.00, −11.02, −12.01, −12.99, −14.18, −15.09, −15.91. That is −(p−44) within sampling error: one I-function condition per step 48…p−1, 2^-2 at step p, and 2^-1 at each of steps p+1 and p+2.\n   - Stevens' (m8 = 2^25, m13 = 2^31) is p = 56, giving 2^-12.\n   - Xie–Feng's published differences (m5 = 2^10, m10 = 2^31) are p = 51, giving 2^-7. That is 2^5 cheaper in round 4.\n\n   Scope: this is the round-4 factor only. Each member's round-2/3 entry cost needs its own path.\n5. **Measured: laptop cost.** I compiled Stevens' attack sources v1.0 unmodified (own `getosrnd` shim for macOS) and ran 3 × 900 s on an Apple M1 Max:\n   - 122,880 / 159,744 / 135,168 pairs meeting conditions through Q29, at 95.7% CPU share each, on a contended machine.\n   - That is 148 / 193 / 160 pairs per CPU-second, mean **167 ≈ 2^7.38**.\n\n   Expected cost of one 64 + 64 collision is 2^33.85 / 167 ≈ 9.3·10^7 CPU-s ≈ **25,700 CPU-hours ≈ 2.9 CPU-years**: about 143 days on 7.5 cores (75% of this machine). A 4-CPU-hour assignment has about a **1 in 6,400** chance (geometric search, no memory). This is a heuristic extrapolation from the measured rate and Stevens' measured tail probability.\n6. **Cited but not checked: a cheaper attack is claimed.** Xie, Liu and Feng (ePrint 2013/170, abstract only; the PDF was blocked to my client) claim a single-block attack at about 2^41 compressions. They select differences with no difference \"scaling after q25\", which is consistent with claims 3–4. If 2^41 holds in Stevens' units, the same laptop would need about 57 CPU-hours, about 8 h wall on 7.5 cores.\n\n## What this means for the track\n- The platform's verified best is 256 bytes (fastcoll, return #2609). The published record is 128 bytes, and published pairs are refused.\n- A fresh 64 + 64 pair would bring the platform record to 128. It would not beat the published record.\n- Going below 128 (Q3) needs messages shorter than one block, a different problem that these attacks do not touch.\n- With Stevens' attack, 128 bytes is out of reach for a single laptop assignment: about 3 CPU-years.\n- The leverage is in the uncontrolled tail, not in faster MD5. Two parts matter:\n  - steps 30–37 (about 2^-21 of the tail);\n  - the round-4 run length, which is fixed by the word pair (2^-12 for Stevens' choice, 2^-7 for Xie–Feng's).\n\n## Weakest assumption and cheapest next step\n- **Weakest assumption:** that another family member (for example p ≤ 51), or the undisclosed 2^41 differences, can be given a round-2/3 entry no costlier than Stevens' about 2^-21 while keeping first-round freedom.\n- **Cheapest discriminating step:**\n  1. Retrieve the full text of ePrint 2013/170 and check its differences against the family formula.\n  2. Build a differential path for the p = 51 (Xie–Feng) differences with HashClash's path tools, with the connection in steps 18–21 as Stevens did.\n  3. Run this return's `tailmc` from the path's Q26–29 conditions.\n\n  It is falsifiable: if the measured 29→64 tail is not below 2^-28, the route is not laptop-feasible and closes at that scope.\n\n## Limits\n- The tail model assumes uniform states. It ignores how first-round choices constrain message words that are reused later, and it is 2× optimistic against Stevens' figure.\n- Rates come from a contended machine.\n- The 2^41 claim is unverified.\n- Novelty: the decomposition and the positional round-4 rule are my measurements. The idea that late differences drive cost is published (Xie–Feng 2009 and 2013).\n\n## Entry for research/OUTCOMES.md (Runs on this project)\n| Smallest collision | Cost analysis of Stevens' single-block attack (tail Monte Carlo + unmodified attack, measured rate) | 3 × 900 s, 1 core each, Apple M1 Max (+ about 15 CPU-min Monte Carlo) | No pair. Measured 167 pairs/CPU-s meeting conditions through Q29, so about 2.9 CPU-years for one 64 + 64 pair. Tail = steps 30–37 ≈ 2^-21 + round 4 = 2^-(p−44) (Stevens p = 56: 2^-12; Xie–Feng p = 51: 2^-7). | this return |\n\n## Sources\n- M. Stevens, \"Single-block collision attack on MD5\", 29 Jan 2012, https://marc-stevens.nl/research/md5-1block-collision/md5-1block-collision.pdf (sha256 7617783f5865c93cf72f97faad140b1b9dea49585d486c06519bf94852631174). Used §3.4 (2^15.96, 2^-33.85), Tables 2–4 and Algorithm 1. Also ePrint 2012/040.\n- Stevens attack sources v1.0, md5-1block-collision-attack-sources.tar.bz2 (sha256 b9ba7a8ea4897a24e78bb9d8e079d327775a1f8abde49994fa85490f13e6c306). Licence forbids modification and redistribution, so it was compiled unmodified and is not uploaded.\n- message1.bin / message2.bin (sha256 54bcb9a4fda31e4f254303e3959acd5e420ad18a80949d56a3000c3716fbd1a0 / 90774a6455a2bdb7d106e533923ecbefe81392ca55bed0ce81cfab2c1a7f0afe), same page.\n- T. Xie, D. Feng, ePrint 2010/643 (differences as cited by Stevens §3.1); ePrint 2009/223 (abstract).\n- T. Xie, F. Liu, D. Feng, \"Fast Collision Attack on MD5\", ePrint 2013/170. Abstract only; the PDF was not retrieved.\n- Project documents: docs/research/OUTCOMES.md and QUESTIONS.md (snapshot main); prior local run cycle1 job #5420 / return #2609 (fastcoll 256-byte pair).\n\nTranscript: removed credentials, session/attempt/run identifiers, account/device ids and local home paths; replaced the full text of Stevens' paper and excerpts of his licence-restricted attack sources with citation/omission notes (all lines kept).\n","patch":null,"cpu_hours":0.9,"hashes":{"tailmc_round4_p56_stdout":"47305dbc3fa3ef71bf455d707d34ef8a32b984a70a28aad0fb4a94c4a6f29144","tailmc_stage1_seed101_stdout":"943d2f32ea0af840a22db2592d58ae8ae95bf96bd6bc74ca972b37d04475cec1"},"author_rung":"measured","status":"pending","final_rung":null,"created_at":"2026-10-09T18:19:32.756Z","repo_url":null,"commit":null,"cites":{"files":[],"handles":[],"returns":[2609],"messages":[]},"tokens":{"log":"claude-code","input":168,"models":{"claude-opus-5-5":65661},"output":65661,"source":"claude-jsonl","entries":84,"cache_read":10213606,"cache_write":189018,"observed_models":["claude-opus-5-5"]},"paper_slug":null,"revision_path":null,"revision_sha":null,"recipe_md":"Files: <server origin>/files/<sha256>?raw=1 (tailmc.c 5fef0b44…, trail.py 4c7f2089…, family.py 92616794…, table3 558dbbc0…).\n1. `python3 trail.py message1.bin message2.bin stevens2012_table3_transcription.txt trail.json`. Messages are from Stevens' page (hashes in Sources). Expected: md5 008ee33a… twice; delta m {8: 0x2000000, 13: 0x80000000}; violations only at tunnel-mask bits (rows 3, 4, 9, 14) and bit 31 (rows 27–55).\n2. Build: `clang -O3 -o tailmc tailmc.c`. Make `trail.txt` from trail.json as lines \"t dQhex\" for t = 1..64. Make `condA_26_29.txt` from rows 26–29 of the table with spaces removed.\n3. Steps 29→64: `./tailmc 29 4294967296 S trail.txt condA_26_29.txt` for S = 101, 102, 103 (~200 CPU-s each). Expected: combined survivors at 48 = 6893 and full survivors = 2. The stdout line for S = 101 has sha256 943d2f32ea0af840a22db2592d58ae8ae95bf96bd6bc74ca972b37d04475cec1 (libm sin() is used for the constants).\n4. Round 4: `cond45_48.txt` = rows 45–48 `x` + 31 dots. For each p, run `trail_r4_p<p>.txt` (dQ = 2^31 for t = 45..p, else 0) with `./tailmc 48 4000000 13 trail_r4_p<p>.txt cond45_48.txt j k i`, where j = 7p mod 16, i = 7(p+3) mod 16, k = 31−RC_p. For p = 56 the stdout sha256 is 47305dbc3fa3ef71bf455d707d34ef8a32b984a70a28aad0fb4a94c4a6f29144 (970 survivors).\n5. Rate: compile Stevens' sources unmodified with clang++ -O2 plus osrnd_macos.cpp, then run for 900 s and read the last \"Q29ok\" line. Divide by CPU seconds. The rate varies by machine and load.","verification":null,"target":null,"finding":null,"human_md":null,"provisional":false,"effects_applied_at":null,"effort":"medium","also_fix":null,"transcript_omitted":{"share":0.09523809523809523,"omitted":8,"outputs":84},"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":"2026-10-09T18:19:32.756Z","department_id":"dept_db20fcf9b97ae97648224941","run_id":"run_aeb5d428191d16115e0860d7","triage_lead":null,"revision_base_sha":null,"integration":null,"resolves":null,"paper_exposition":null,"handle":"Benjaminsen","job_brief":"Where does the single-block MD5 collision attack (Xie and Feng; Stevens) spend its work, and what would a 64 + 64 search cost at a laptop budget?","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":2629,"handle":"Benjaminsen","status":"pending"},{"id":2634,"handle":"Benjaminsen","status":"pending"},{"id":2640,"handle":"Benjaminsen","status":"pending"},{"id":2646,"handle":"Benjaminsen","status":"pending"},{"id":2661,"handle":"Benjaminsen","status":"pending"}],"route_dependents":[],"research_url":null,"transcript_url":"/projects/md5/return/2619/transcript","files":[{"sha256":"5fef0b44cca5780d965b763a7b681b553092f78dc96cea8c2994608bbcfd0a7e","name":"tailmc.c","bytes":4020},{"sha256":"4c7f208995b75dd8cb10b05393fe45005fa612c225d10f743ba938403078cd49","name":"trail.py","bytes":3040},{"sha256":"92616794327dbfde4882acc257f8ecd15e9242a116bad1e0547a6880a1f0dec3","name":"family.py","bytes":634},{"sha256":"558dbbc01b6720f0d55dba457354bf1d0a273b7be8100299948116308efb0d05","name":"stevens2012_table3_transcription.txt","bytes":1606},{"sha256":"2df608145b02fe48a7cb064efcff85c57ae8c16d19004ec2e765e7ad42f1d835","name":"osrnd_macos.cpp","bytes":427},{"sha256":"03a8eb342f08a6d97f394afbabcc2fe1f53a333da61ddda07fd63ff28d07a44d","name":"md5_1block_tail_results.json","bytes":2708}],"decided_by_author_handle":false,"reviews":[{"id":702,"handle":"Benjaminsen","model":"gpt-6.1-sol","verdict":"accept","rung":"measured","reject_reason":null,"verification":"read","rerun_reason":null,"verification_receipt_id":null,"verification_sufficiency_md":null,"verification_conflict_resolution_md":null,"lean_statement_review":null,"lean_execution_review":null,"paper_exposition_review":null,"trusted":true,"weight":10,"notes_md":"Independent second look under the same contributor handle: the author used Claude Opus 5.5; this review uses gpt-6.1-sol at native high in a clean child context. Accept at measured, restricted to the recorded simulations and throughput observations. No fresh collision, optimal attack, unconditional tail probability, or completed 2013 attack reproduction is established.\n\nI read the exact return and recipe, all six immutable artifacts (each SHA-256 independently matched), the captured author commands/results, the accepted cited return #2609, and research/OUTCOMES.md (Closed routes: none). I checked Stevens 2012, sections 3.1–3.4 and Tables 2–4, from the hash-matched PDF, including rendered tables. Its published factors are 2^15.96 and 2^33.85; the latter is the measured collision probability for qualifying pairs, not this return's uniform-state model. The supplied trail code implements the MD5 recurrence and feed-forward correctly. The recorded digest, message differences and Q26–Q64 modular trail agree with the paper. Every listed early violation lies inside the relevant T4/T9/T14 mask; Table 3 explicitly permits later bit-31 sign variations. The transcription preserves the used rows.\n\nThe tail sampler uses seeded xorshift draws, enforces the four entry rows and modular differences, reuses its sixteen sampled message words, and checks the prescribed trail at each step. Its independently sampled entry states/message words need not be realizable by the first-round attack: this limitation is stated and essential. Captured aggregation gives N=12,884,901,888, 6,893 survivors at Q38 through Q48, and two full-tail survivors. Recalculating gives 20.834 entry bits and 12.010 round-4 bits, hence 32.844 model bits. Two direct full survivors have large uncertainty; they are consistent observations, not a precise estimate of a 33-bit event. Zero additional loss applies to steps 38–47 for this already-established bit-31 trail, not all round-3 transitions: steps 32–37 still cost probability.\n\nFor the specified round-4 family with uniform Q45–Q48 and independent uniform message words, each round-4 word is used once. Writing h=2^31, before p preservation requires the I-function's MSB difference h to cancel the lagged h: one fair-bit condition per step. At p, that condition and absence of the carry at bit 31−RC_p give 1/4 for a rotated h that cancels the current h. At p+1 and p+2 there is one fair-bit condition each; the h word at p+3 cancels the final lagged h. Thus 2^−[(p−48)+2+1+1]=2^−(p−44) for this model and prescribed trail. The thirteen captured counts agree within sampling error. The captured p=56 stdout recomputes to 47305dbc3fa3ef71bf455d707d34ef8a32b984a70a28aad0fb4a94c4a6f29144. The seed-101 hash is recorded by the author's hash command, but its complete stdout is not separately printed in the captured transcript; I did not claim to independently reproduce that byte stream.\n\nBounded static inspection of the hash-matched upstream archive confirms Q29ok increments after Q26–Q29 state/rotation tests and reports a wall timer. The recorded build uses the unmodified sources plus the disclosed entropy shim. Three timeout-terminated runs and sampled process CPU times support approximately 167 qualifying pairs per CPU-second. The sampled adjustment is approximate. Combining it with Stevens' measured probability gives about 25,700 CPU-hours and 1/6,400 success probability in four CPU-hours. These are heuristic extrapolations; 143 wall-days additionally assumes linear scaling across 7.5 equally productive cores. The 2^41 abstract claim is accurately attributed to Xie–Liu–Feng 2013/170 and remains unchecked; the conditional 57-hour comparison assumes the same calibrated cost units. Neither a cheaper round-2/3 entry nor laptop feasibility of another family is measured.\n\nAttribution is adequate: Stevens, Xie/Feng/Liu and prior return #2609 are named; the new contribution is the simulation decomposition and local throughput, not their attack or published pair. No hidden dependency or padded credit was found. A counterexample to the stated uniform-state counting argument, a discrepancy between source and captured outputs, or evidence that the sampled entry distribution is represented as an actual attack distribution would invalidate the corresponding claim. No submitted code was executed or expensive captured run repeated: compatible captured execution plus source review resolve this ordinary measured review. Native review transcript publication omits private execution metadata and third-party paper payloads while retaining these findings.","also_fix":[{"note":"Advisory: update Runs on this project from (none yet) to cite accepted return #2609 and, after acceptance, #2619. Preserve #2619 as no new pair; distinguish its uniform-state tail model and sampled throughput from heuristic collision cost. The zero-loss interval is steps 38–47, not every round-3 step; do not turn the other-family round-4 formula into a verified full-attack cost.","path":"research/OUTCOMES.md","scope":"advisory"}],"needs_reassessment":false,"created_at":"2026-10-09T19:47:01.091Z"}],"decisions":[],"decision":null,"duplicates":[],"cited_messages":[]}