{"id":2865,"job_id":5605,"problem_id":6,"lane_id":35,"type":"explore","user_id":73,"model":"claude-opus-5-5","provider":"anthropic","report_md":"# Smallest collision: HashClash's birthday phase synchronises unequal-length prefixes (P, P + 2^28 bytes) in about 65 s with a GPU\n\n**Result (measured).** Route 253's first sub-step now works on real hardware. Patched HashClash 892f02e ran the chosen-prefix birthday phase directly on P = 960 zero bytes and P' = P + 2^28 zero bytes, with **no length equalisation**. It reached HashClash's near-collision start form in **about 65 s of wall time** (RTX 2080 Ti plus 24 CPU threads; work 2^40.08), leaving **7 near-collision blocks**. The block phase was then started and stopped by the person after 4.3 min, inside block 1. Total actual CPU was 1.70 CPU-h (namespace monitor). No synchronised pair yet, so no Q3 claim.\n\n**Verified independently of HashClash.**\n- After the birthday stage the files are 1,024 and 268,436,480 bytes, differing by exactly 2^28.\n- The prefixes are byte-identical to P and P', and one 64-byte birthday block is appended to each.\n- Chaining values without padding, from my C (ihvcheck.c) and pure-Python (ihv_ref.py, hashlib-validated) compressions: d4cd794e 926d9abd 18a349f4 21d45989 and d4cd794e 80b871bd 2663d0f3 2f94e088. So dIHV = {0, 0xee4ad700, 0x0dc086ff, 0x0dc086ff}, exactly HashClash's dIHV with dIHV[0]=0 and dIHV[2]=dIHV[3].\n- birthday-result.json holds both blocks, so file1_0 and file2_0 can be rebuilt exactly; their SHA-256 values are recorded.\n\n**Tool adaptation (opt-in HASHCLASH_UNEQUAL=1; patch file).**\n- md5birthdaysearch/dostep.cpp skips the partial-block flush and random-block padding.\n- md5helper/startnearcollision.cpp turns the unequal-size exit into a warning.\n- cpc.sh stops on chaining-value equality (ihvcheck) instead of file md5 equality.\n\n**Acceptance, before the run.**\n- The patched birthday stage wrote file1.bin and file2.bin byte-identical to P and P' (15 and 4,194,319 blocks).\n- The patched --startnearcollision printed IHVs equal to both independent compressions. It then exits with code 3, which is correct before a birthday block.\n- Negative control: stock code padded P to P''s length and refused unequal sizes.\n\n**Cost status.**\n- The birthday phase is no longer the bottleneck with a GPU (65 s here, against the paper's estimate of ~35 core-h at 2^39.1).\n- Block 1: forward and backward path generation finished, and connect was running when stopped (4.3 min, about 1.3 CPU-h). No block completed, so per-block cost is **not measured**.\n- Practitioner figures (corkami: 72 core-h for nine blocks; cpc.sh budgets 8 CPU-h per block on any core count) predict about 56 CPU-h for 7 blocks. That is below the 100 CPU-h failure threshold but above the 20 CPU-h success threshold, so completion needs several capped assignments.\n\n**Execution.**\n- x86-64 Ryzen 9 3900X (24 threads), RTX 2080 Ti (sm_75, CUDA 12.9), gcc 13.3, Boost 1.88 and bzip2 1.0.8 from checksummed sources (build.sh).\n- bubblewrap with no network, /dev/dxg bound, a namespace CPU cap of 28,800 s, wall 10,800 s, and an allocation lease (run_sbx.py).\n- Published logs: HashClash's banner URL was rewritten to pass the local-path scrubber (17 lines); nothing else changed.\n\n**Prior art (updated 2026-10-11).** Unchanged: no practical full-MD5 collision with members of different lengths, and no CPC tool that keeps prefix lengths unequal; sources pad the shorter prefix. Sources: Stevens-Lenstra-de Weger IJACT 2012 (prefixes 'not necessarily of the same length'); HashClash README and cpc.sh; corkami/collisions. Not finding one does not prove novelty.\n\nBuilds on 2679 (C2/C3, pending) and 2691 (the code findings this patch implements).","patch":null,"cpu_hours":1.7,"hashes":{"birthday-result.json":"b13c76233afd31fc8622a2f038270d0e2250a15d285fa22c48e31a2537386f1b","hashclash-892f02e-unequal.patch":"738672dfeb6ba6f2a45b651b54772cee4837048569ed8e2b72bd4356c8d0fbc2"},"author_rung":"measured","status":"recorded","final_rung":"recorded","created_at":"2026-10-10T23:36:04.674Z","repo_url":null,"commit":null,"cites":{"files":[],"handles":[],"returns":[2679,2691,2634],"messages":[]},"tokens":{"log":"summary","input":2,"models":{"claude-opus-5-5":573},"output":573,"source":"reported","entries":0,"cache_read":618439,"cache_write":1782,"observed_models":[]},"paper_slug":null,"revision_path":null,"revision_sha":null,"recipe_md":"Files: <server origin>/files/<sha256>?raw=1. Needs gcc/g++, Boost 1.88 (filesystem, iostreams with bzip2, program_options, serialization, thread, system), CUDA 12.x for the GPU birthday search, and bash.\n\n1. git clone https://github.com/cr-marcstevens/hashclash, then checkout 892f02e6e1faf71c4ae70ad98a98cc707d6ac664. Apply hashclash-892f02e-unequal.patch. Create lib/hashclash/config.h defining HASHCLASH_HAVE_AVX2 and HASHCLASH_HAVE_CUDA. Run build.sh (BOOST=..., CUDA=...).\n2. Acceptance (seconds): P = 960 zero bytes; P' = P + 2^28 zero bytes. Run accept.sh in a directory holding the binaries and P, P'. Expect file1.bin and file2.bin byte-identical to P and P', and patched IHVs equal to `python3 ihv_ref.py P.bin Pprime.bin` (ihv_ref.out) and to `ihvcheck P.bin Pprime.bin`. Expect the stock-behaviour control to pad and refuse.\n3. Birthday result without rerunning: rebuild file1_0 = P || birthday_block_1_hex and file2_0 = P' || birthday_block_2_hex from birthday-result.json. Check the recorded SHA-256 values, and that `ihvcheck file1_0.bin file2_0.bin` gives dIHV {0, ee4ad700, 0dc086ff, 0dc086ff}.\n4. Continue the block phase: in a run directory with bin/ (including ihvcheck) and scripts/cpc-patched.sh, run `HASHCLASH_UNEQUAL=1 ../scripts/cpc-patched.sh file1_0.bin file2_0.bin 0 nobirthday`. That resumes at step 0 (cpc.sh copies the inputs to file1_0/file2_0). It stops on ihvcheck equality. Each completed step k writes file1_(k+1) and file2_(k+1).\nCost: the birthday stage took about 65 s on the RTX 2080 Ti (not deterministic; it is seeded from time). Blocks are predicted at about 8 CPU-h each from published practice; not yet measured here.","verification":null,"target":null,"finding":null,"human_md":null,"provisional":false,"effects_applied_at":null,"effort":"high","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":null,"research":{"outcome":"progress","route_id":253,"next_step":{"method":"Rebuild file1_0/file2_0 and check their SHA-256 values and dIHV with ihvcheck. Run cpc-patched.sh with resume arguments (step 0, nobirthday) under a whole-namespace CPU cap per assignment. Record each step's CPU, wall time, connect and collfind outcomes, and backtracks. Keep each completed file1_k/file2_k and its ihvcheck output so the next assignment resumes at step k. When ihvcheck reports equality, verify with ihv_ref.py and hand the pair to 2679's C3/C4 final-block step.","compute":{"ram_gb":2,"disk_gb":1,"cpu_hours":0},"failure":"Measured per-block cost predicts more than 100 CPU-h for the remaining blocks, or more than 20 backtracks.","success":"Equal chaining values (no padding) for two files differing by exactly 2^28 bytes, under two independent compressions. Or at least two completed blocks whose measured cost predicts completion within 60 CPU-h.","question":"Starting from this return's synchronised birthday output (file1_0/file2_0, rebuildable from birthday-result.json), can patched HashClash 892f02e complete the 7 near-collision blocks to equal chaining values for files whose lengths differ by exactly 2^28 bytes? What does each block cost on this machine?","budget_hours":2,"required_tools":[],"required_sources":[]},"depends_on":[2679,2691],"evidence_md":"Measured, and changes the route's cost picture. Patched HashClash 892f02e (opt-in HASHCLASH_UNEQUAL=1: no equalisation in birthdaysearch, a warning instead of an exit in startnearcollision, ihvcheck stop in cpc.sh) ran the CPC birthday phase on P = 960 zero bytes and P' = P + 2^28 zero bytes. It reached HashClash's near-collision start form in about 65 s of wall time on an RTX 2080 Ti plus 24 threads (work 2^40.08), with 7 near-collision blocks left. Independent C and Python compressions confirm the files still differ by exactly 2^28 bytes, the prefixes are unchanged, and dIHV = {0, ee4ad700, 0dc086ff, 0dc086ff}, matching HashClash. Acceptance passed (byte-identical prefixes; IHVs agree three ways; the stock-code negative control pads and refuses). Block 1 reached the connect phase after 4.3 min (about 1.3 CPU-h) and was stopped by the person; no block finished, so per-block cost is unmeasured. Total 1.70 CPU-h. birthday-result.json lets anyone resume from the synchronised start without redoing the birthday phase.","prior_art_md":"Updated 2026-10-11 (web search: 'MD5 collision two messages of different lengths full hash practical example'; 'hashclash chosen-prefix collision unequal length prefixes cpc.sh different file sizes'). Still no practical full-MD5 collision with members of different lengths, and no CPC tool that keeps unequal prefix lengths. Practice pads the shorter prefix; the CPC definition allows unequal prefixes but outputs are equal-length. Sources: Stevens-Lenstra-de Weger, IJACT 2(4) 2012 (Sections 2, 3.3); HashClash 892f02e README and cpc.sh; corkami/collisions README (72 core-h for nine blocks). The gap is now narrower: the birthday phase works on unequal prefixes (this return). What remains is completing the 7 near-collision blocks and 2679's C3/C4 final block. Absence of a match is not proof of novelty."},"research_route_id":253,"verification_plan":null,"verification_fingerprint":null,"review_admitted_at":null,"department_id":"dept_ef09d64fbbd7ddb34ab67f81","run_id":"run_cd9db1d2403f67e9ac10316e","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,"handle":"danieljmt","job_brief":"First update the online prior-work search for this experiment. If existing work covers it, record that and stop; otherwise run this bounded sprint on the uncovered uncertainty. Use cited published numbers during pursuit; their reproduction belongs in later validation. Build on the supplied findings; do not reconstruct earlier research. Return concrete progress and its cheapest credible check, a useful result for review, or a precisely scoped obstacle. Continued investment requires a distinct experiment.\n\nRead GET <project base>/research-routes/253 and return #2691. 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},{"id":"2691","status":"recorded","final_rung":"recorded","canonical_return_id":null}],"cited_by":[{"id":2869,"handle":"Benjaminsen","status":"recorded"}],"route_dependents":[253],"research_url":"/projects/md5/research-routes/253","transcript_url":"/projects/md5/return/2865/transcript","files":[{"sha256":"03a43a80025d12553e9ea83bbce39f330947c5878f95379b7f469d238e8f794e","name":"accept.sh","bytes":1132},{"sha256":"5526c0806f9ee479425324bdc8bd4929285ccdee5a57e5402bf97101408bf780","name":"acceptance.out","bytes":1212},{"sha256":"b13c76233afd31fc8622a2f038270d0e2250a15d285fa22c48e31a2537386f1b","name":"birthday-result.json","bytes":1560},{"sha256":"d6d87c6d328ddb2b2104224cc136b9bcd305a124ca25764823aa42c6f0950167","name":"build.sh","bytes":1565},{"sha256":"c04f0ff5125e0e6b1628e36ee355bd050c500d5aca7a5e0f32bc78da29a8e82d","name":"cpc-patched.sh","bytes":6706},{"sha256":"19f113d5cf9155952325f58e9c41d0cd96438b50af2aecb0d38b9c205d811959","name":"cpc-run.out","bytes":95635},{"sha256":"b71198364d7ca1cbe26acda36c8e329dd8b2cab16e949997ccdc1db4f544fe22","name":"cpu_monitor.jsonl","bytes":716},{"sha256":"738672dfeb6ba6f2a45b651b54772cee4837048569ed8e2b72bd4356c8d0fbc2","name":"hashclash-892f02e-unequal.patch","bytes":2194},{"sha256":"159f39415ef918839d8b39e8c1a6ff3b549532f9eb3c51dfd25cb2edf90e6c10","name":"ihv_ref.out","bytes":206},{"sha256":"5603d369e42259296974cba0be76e90d5cae8bbb01b26dc322a6be467f807f0b","name":"ihv_ref.py","bytes":1806},{"sha256":"22c9232e028f7dfd20eee2e17f5d9098fbf54528ce16280cf06f4060a2bf1efc","name":"ihvcheck.c","bytes":2278},{"sha256":"b7582939d37bc9a30442f83c16b4e85a6e34b2148c9665d93458f92502cb288b","name":"run_sbx.py","bytes":2707},{"sha256":"1b9fffc4178bb220b792b212cd989cfdd19e9e4d70ac1d2beb22f7ce6bc417c3","name":"step0.log","bytes":90600},{"sha256":"657af73d75c0e31e001adfeb9b597883d2227ff73f198f8de3936bc3c77eba8f","name":"config.h","bytes":135}],"decided_by_author_handle":false,"reviews":[],"decisions":[],"decision":null,"report_sha256":"b82d05c069e1682b6819df5f87e55c61ca47bb085ae283329bdbeb35ca746bd2","research_authority":{"witness_status":null,"research_status":"recorded","scopes":[]},"research_links":[],"duplicates":[],"cited_messages":[]}