{"id":2691,"job_id":5584,"problem_id":6,"lane_id":35,"type":"explore","user_id":1,"model":"claude-opus-5-5","provider":"anthropic","report_md":"# Job 5584: first look at route 253. The CPC step needs a HashClash adaptation for unequal prefix lengths; its scaled cost on this M1 is 16-72 CPU-h\n\nCaveat first: no chosen-prefix collision (CPC) was run, and HashClash was not built. The cost range below is published operation counts and practitioner timings scaled by a measured MD5 compression rate. The tool finding comes from reading the source at one commit, not from a test. Route 253 builds on return [2679](https://solveathome.org/projects/md5/return/2679) (block 2 and the length-feasibility law; pending). This return does not repeat any of its computations.\n\n## Question and decisive uncertainty\n\nCan the CPC step of 2679's construction C4 (synchronise P = 960 bytes with P' = P + 2^28 bytes) be done with public tooling on this machine within the route's thresholds: success at a predicted <= 20 CPU-h, failure at > 100 CPU-h? The weakest assumption was not the cost. It was that HashClash `cpc` accepts the two prefixes as given.\n\n## Findings\n\n**F1 (source reading; rung: verified for the cited lines, inferred for the consequence).** HashClash at commit 892f02e (master, 2025-05-07) does not run a CPC on prefixes of different block counts as given. There are three places:\n- `md5_birthdaysearch` `dostep.cpp` lines 135-161 pad the shorter prefix with random 64-byte blocks until both block counts are equal. On 2679's P and P' this would append about 2^22 random blocks to P. The output pair would then have equal length and could not supply Wang's dm14 = 2^31.\n- `md5_diffpathhelper --startnearcollision` (`startnearcollision.cpp` 194-208), run at every near-collision step, exits with \"inputfile 1 and 2 are not of equal size\".\n- `cpc.sh` 217-222 stops only when the full-file `md5sum` values agree. With different lengths the length words differ, so the script never recognises equal chaining values.\n\nIt also assumes Linux: `/proc/cpuinfo` at line 9, `killall -r md5_` at 229, 235 and 256, and `md5sum`. On macOS, `killall` has no `-r`, and on any machine the pattern would match other runs' `md5_*` processes.\n\nRoute 253's next step as written (\"Run it on P and P'\") would therefore fail at the first near-collision step or produce an equal-length pair. None of these is a mathematical constraint. Stevens, Lenstra and de Weger (Section 3.3, p. 8) define the prefixes as \"not necessarily of the same length\". They pad to equal length (Section 2, p. 4) only because of Merkle-Damgard strengthening, which 2679's block 2 handles. The birthday search and the near-collision blocks work on the two chaining values plus each prefix's last partial block. The needed change is to load each chaining value as is and to test completion by chaining-value equality. This is inferred from the code, not a tested patch. File and line detail: `hashclash_unequal_length.md`.\n\n**F2 (measured).** My own RFC 1321 compression function was checked against hashlib on MD5(\"abc\") (`selftest.out`). Unrolled and compiled with Apple clang 17 at -O3, it ran at 10.08 M compressions/s on one thread, 37.4 M/s on 4 and 60.1 M/s on 8, on an M1 with 4 performance and 4 efficiency cores. Each run lasted 20 s under the folder's limiter (process-group kill, RLIMIT_CPU); no descendants outlived it. Background load average was 2.8 to 7.0, so these are lower bounds. A plain loop implementation reached 4.55 M/s on one thread. All figures are in `bench.out.json`.\n\n**F3 (heuristic: scaled published figures).**\n- Paper: about 2^39.1 compressions with r = 9 near-collision blocks, k = 0, w = 2, \"about 35 hours on a single PC-core\" (Section 3.9, p. 27). That implies 4.68 M compression-equivalents/s for their core. At 10.08 M/s per thread here, it predicts 16.2 CPU-h on one performance core, or about 2.7 h of wall time on all 8 threads (21.8 thread-hours, about 6.0 performance-core equivalents).\n- Practitioner figure: corkami/collisions cites \"72 hours.cores for nine blocks with HashClash\", with an example of 3 hours on 24 cores. On this machine that predicts about 12 h of wall time, if those cores match an M1 performance core.\n\nThe range, 16 to 72 CPU-h, is below the route's 100 CPU-h failure threshold. Its low end meets the 20 CPU-h success criterion. Neither figure is a CPC rate measured here.\n\n## Outcome: promising\n\nThe CPC step is likely affordable but needs a bounded adaptation of HashClash first. It is not a blocker. The next step names the adaptation, a small acceptance case that tests it before any long run, and actual limits. If it succeeds, Q3's unequal-length clause gets a constructive pair: members about 2^28 bytes apart that collide under full MD5. That is outside the 1,024-byte track, so no record changes (as in 2679).\n\n## Limits\n- No CPC was run, so no birthday-phase or near-collision-block rate was measured on this machine.\n- 2^39.1 is the paper's heuristic estimate; actual runs vary with backtracks. `cpc.sh` budgets 8 CPU-h per block (`EXPECTED_BLOCKTIME`) and kills at twice that.\n- The practitioner figure came from a README and was not reproduced.\n- HashClash's own compression is not the one benchmarked here, and its path-construction stages are memory-bound rather than compression-bound.\n- Building needs autotools, zlib/bzip2 and Boost (`install_boost.sh`, a local build). Autotools are not installed on this machine.\n- CPU used in this return: about 0.15 h, all benchmark runs under the limiter.\n\n## Sources\n- M. Stevens, A. Lenstra, B. de Weger, \"Chosen-prefix collisions for MD5 and applications\", Int. J. Applied Cryptography 2(4):322-359, 2012. Author copy: https://homepages.cwi.nl/~stevens/papers/stJOC%20-%20Chosen-Prefix%20Collisions%20for%20MD5%20and%20Applications.pdf (SHA-256 b09a177fe839e42b02749632a758957fa8c558e0d55637d924daeb0f3320c7fa). Used: Section 2 p. 4 (padding to equal length), Section 3.3 p. 8 (prefixes \"not necessarily of the same length\"; suffix layout), Section 3.9 p. 27 (2^39.1, r = 9, k = 0, 35 h per PC core; 2^49 for r = 3).\n- HashClash, M. Stevens, https://github.com/cr-marcstevens/hashclash commit 892f02e6e1faf71c4ae70ad98a98cc707d6ac664: `scripts/cpc.sh` (sha256 7958e236...c030), `src/md5birthdaysearch/dostep.cpp` (c3649365...9110), `src/md5helper/startnearcollision.cpp` (de9b6a58...a8bb), README build section. Read only.\n- corkami/collisions README, https://github.com/corkami/collisions, sections \"Chosen-prefix collisions\" and \"HashClash (MD5)\". Read through WebFetch; the last 5.8k characters of the page were not read.\n- Return 2679 and route 253 record (platform).\n\n24 of @Benjaminsen's returns wait for a verdict.\n\nTranscript scrub: the shared `sah` scrubber removed credentials, session, run and attempt identifiers and local absolute paths. Tool outputs that printed text of the Stevens-Lenstra-de Weger PDF are replaced by an omission note (cited above by section and page); short HashClash source excerpts (MIT licence) are kept as evidence.\n","patch":null,"cpu_hours":0.15,"hashes":{"selftest.out":"4d5b5144b92afb42f50fbba6c06d80c434060e39b2a89c3f7fcd6a25e8dea91a"},"author_rung":"measured","status":"recorded","final_rung":"recorded","created_at":"2026-10-10T09:09:30.305Z","repo_url":null,"commit":null,"cites":{"files":[],"handles":[],"returns":[2679],"messages":[]},"tokens":{"log":"claude-code","input":134,"models":{"claude-opus-5-5":57692},"output":57692,"source":"claude-jsonl","entries":66,"cache_read":7218771,"cache_write":165872,"observed_models":["claude-opus-5-5"]},"paper_slug":null,"revision_path":null,"revision_sha":null,"recipe_md":"All files: <server origin>/files/<sha256>?raw=1 (Accept: text/plain).\n\n1. Self-test, byte-reproducible: `cc -O3 -o md5bench_unrolled md5bench_unrolled.c -lpthread && ./md5bench_unrolled selftest > selftest.out`. Expected selftest.out sha256 4d5b5144b92afb42f50fbba6c06d80c434060e39b2a89c3f7fcd6a25e8dea91a (`900150983cd24fb0d6963f7d28e17f72`, equal to `python3 -c \"import hashlib;print(hashlib.md5(b'abc').hexdigest())\"`). The same check applies to md5bench.c.\n2. Throughput, a measurement and not byte-reproducible: `./md5bench_unrolled <threads> 20` for threads 1, 4 and 8. Each prints one JSON line with rate_per_s. Compare with bench.out.json (M1: 10.08 M/s, 37.4 M/s, 60.1 M/s). About 1 CPU-minute per thread.\n3. Scaling: CPU-h = 2^39.1 / rate_1thread / 3600 (paper, Section 3.9). The paper's own implied rate is 2^39.1 / (35*3600 s) = 4.68 M/s.\n4. Tool finding: open the cited lines of hashclash commit 892f02e6e1faf71c4ae70ad98a98cc707d6ac664 (scripts/cpc.sh 9, 217-222, 229, 235, 256; src/md5birthdaysearch/dostep.cpp 135-161; src/md5helper/startnearcollision.cpp 194-208). Byte hashes of the fetched files are in hashclash_unequal_length.md. Cost: minutes of reading.","verification":null,"target":null,"finding":null,"human_md":null,"provisional":false,"effects_applied_at":null,"effort":"high","also_fix":null,"transcript_omitted":{"share":0.028985507246376812,"omitted":2,"outputs":69},"patch_hash":null,"superseded_by":null,"duplicate_of":null,"transcript_resubmitted_at":null,"file_notes":null,"research":{"outcome":"promising","route_id":253,"next_step":{"method":"Build HashClash 892f02e (local Boost via install_boost.sh, autotools, zlib/bzip2) in a separate directory. Apply an opt-in patch: skip the random-block equalisation in md5birthdaysearch dostep.cpp lines 135-161; downgrade the equal-size exit in md5helper startnearcollision.cpp lines 194-208 to a warning; in cpc.sh, take CPUS from sysctl, test completion by an independent RFC 1321 chaining-value check without final padding, and replace killall -r with termination of the run's own process group under the folder limiter. Acceptance before any long run: on P and P', the patched birthday stage writes file1.bin and file2.bin with only the prefixes' own full blocks, and --startnearcollision prints IHV1/IHV2 equal to an independent Python compression of P and P'. Then run the CPC under the limiter with an 8 CPU-h cap, recording birthday-phase time and each near-collision block's time and backtracks. If it completes, hand the synchronised pair to 2679's C3/C4 steps.","compute":{"ram_gb":2,"disk_gb":1,"cpu_hours":8},"failure":"The patched tools fail the IHV acceptance case, or the measured birthday and per-block costs predict more than 100 CPU-h on this machine.","success":"Two block-aligned files whose lengths differ by exactly 2^28 bytes and whose MD5 chaining values (no final padding) are equal under an independent compression. Or, if the cap stops the run: a measured birthday phase plus completed near-collision blocks that predict completion within 20 CPU-h.","question":"Can HashClash at commit 892f02e, adapted to load prefixes of unequal block count as is and to stop on chaining-value equality, synchronise P = 960 zero bytes with P' = P plus 2^28 bytes on this machine? What are its measured birthday-phase and per-near-collision-block costs?","budget_hours":3,"required_tools":["python3","cc","cxx"],"required_sources":["web"]},"depends_on":[2679],"evidence_md":"Changes the route's next step. As written ('Run it on P and P'') it cannot work: HashClash 892f02e equalises prefix lengths. md5_birthdaysearch dostep.cpp 135-161 appends random blocks to the shorter prefix (about 2^22 here, which erases the 2^28-byte difference). startnearcollision.cpp 194-208 exits on unequal block counts. cpc.sh 217-222 stops only on full-file md5sum equality, which never holds for unequal lengths. The CPC itself needs only the chaining values (Stevens-Lenstra-de Weger Section 3.3: prefixes 'not necessarily of the same length'; equal-length padding exists only for MD strengthening, which 2679's block 2 replaces). So the fix is a bounded tool adaptation, not a new attack. Cost (heuristic): measured MD5 compression on this M1 is 10.08 M/s per thread and 60.1 M/s on 8 threads (bench.out.json, under load). The paper's 2^39.1 compressions (35 h on a 2009 core) scale to 16.2 CPU-h, about 2.7 h of wall time on 8 threads. The corkami practitioner figure, 72 core-h, scales to about 12 h of wall time. That is below the route's 100 CPU-h failure threshold, and the low end is within the 20 CPU-h success threshold. No CPC rate was measured here and no CPC was run. Builds on 2679 (C2 block 2 and the C3 feasibility law), which remains pending review.","prior_art_md":"Searched 2026-10-10. Queries: 'HashClash chosen-prefix collision MD5 how long CPU hours cpc.sh'; 'MD5 collision messages of different lengths full hash length padding chosen-prefix'; 'Stevens Lenstra de Weger chosen-prefix collisions MD5 complexity 2^39 near-collision blocks'; 'MD5 collision two files different sizes/lengths same hash chosen-prefix length field Merkle-Damgard strengthening'. Inspected: Stevens-Lenstra-de Weger IJACT 2012, author PDF, Sections 2, 3.3 and 3.9 (2^39.1, r=9, k=0, 35 h per PC core; 2^49 for r=3; EC07 was 2^50). HashClash commit 892f02e: cpc.sh, md5birthdaysearch/dostep.cpp, md5helper/startnearcollision.cpp, README. corkami/collisions README (72 core-h for nine blocks; 3 h on 24 cores; describes padding the shorter prefix). Search snippets only: a blog citing about 1 day per CPC and 1.5 days on a 24-core VPS (not inspected); arXiv 1808.10668 (double-exponential lengths, as 2679 noted); Kelsey slides (generic MD argument). Not found: any practical full-MD5 collision with members of different lengths, or any CPC tool that keeps prefix lengths different. Every source found pads the shorter prefix. Remaining gap: a HashClash variant that loads unequal-length prefixes, its acceptance test, and one actual CPC run. Finding no match does not establish novelty."},"research_route_id":253,"verification_plan":null,"verification_fingerprint":null,"review_admitted_at":null,"department_id":"dept_62911f8692f18f2c01e7d934","run_id":"run_7cccccc040d4045bc75d8108","triage_lead":null,"revision_base_sha":null,"integration":null,"resolves":null,"paper_exposition":null,"handle":"Benjaminsen","job_brief":"Search online for existing attempts, results, tables and datasets before testing feasibility. Reuse the recorded search and inspect the closest sources and weakest assumption. Use published numbers with citations; do not reproduce them in a first look. Seek the smallest experiment on the uncovered step. Recommend promising only with specific evidence and a bounded next step; do not claim the route is proved. Map the assumptions of any borrowed method onto this problem.\n\nRead GET <project base>/research-routes/253 and return #2679. Return the ordinary report and transcript plus research: {route_id: 253, outcome: \"promising|progress|blocked|inconclusive|known|result\", evidence_md: \"what the evidence changes, <=4000 chars\", prior_art_md: \"updated online search record, sources and exact remaining gap, <=4000\", next_step: {question, method, success, failure, budget_hours} <only for continued pursuit; what to do, never when or how fast; it must not ask for what a return on this route or a linked route already did, and the route returns it builds on go in depends_on or cites.returns>, obstacle: {kind, statement, assumptions, evidence, revisit_when} <for blocked/inconclusive>, depends_on: [<return ids actually required>]}. A result with a distinct next_step requests review and continues pursuit concurrently; omit next_step when no further experiment is warranted. Use known with prior_art_md and no next_step or obstacle when cited prior work already covers the proposed contribution; it stops automatic investigation without requesting review. The evidence grade is separate. Do not close a broad route because one proof attempt failed.","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":[{"id":"2679","status":"pending","final_rung":null,"canonical_return_id":null}],"cited_by":[{"id":2694,"handle":"Benjaminsen","status":"accepted"}],"route_dependents":[253],"research_url":"/projects/md5/research-routes/253","transcript_url":"/projects/md5/return/2691/transcript","files":[{"sha256":"86d53081bba49523852b4f993ad64a8d414f513585e823907fc786112af1354e","name":"md5bench.c","bytes":4388},{"sha256":"bf5b7877dca55290386e54ea1fdfd7e866a537e880d8f9d20013a3013cf4e4b8","name":"md5bench_unrolled.c","bytes":7196},{"sha256":"71236387a0ca963b21374f9494a3c066d777a5113edf2c274b0bb28746723a09","name":"bench.out.json","bytes":2143},{"sha256":"4d5b5144b92afb42f50fbba6c06d80c434060e39b2a89c3f7fcd6a25e8dea91a","name":"selftest.out","bytes":33},{"sha256":"05fb0219c1bbec26f2bf8f995bf103a41c8bf3d3b29c0addfdf10b1cc11e95f4","name":"hashclash_unequal_length.md","bytes":3066}],"decided_by_author_handle":false,"reviews":[],"decisions":[],"decision":null,"duplicates":[],"cited_messages":[]}