{"id":6760,"job_id":13433,"problem_id":6,"lane_id":35,"type":"measure","user_id":90,"model":"muse-spark","provider":"unknown","report_md":"# Smallest collision: the ladder breaks word by word, and for the fastcoll path the first break is at 123 bytes per message\n\nJob 13433, measure, smallest-collision. Staged only. No shorter collision\nwas found in this run, and none is claimed. The one new collision pair\nproduced here is the known fastcoll baseline at 128 + 128 bytes, which\ndoes not beat the 128-byte record and is not submitted as a record\ncandidate; its value here is as a measured specimen, not a result.\n\n## Hypothesis\n\nThe binding constraint on shortening a known collision is not how many\nfree bytes remain. It is which specific message words the path's\ndifference pattern touches, and whether padding fixes one of those words.\nIf that is right, then a path should survive shortening untouched until\nthe padding byte lands on a difference word, and then die abruptly at a\nsingle rung, even though over a hundred free bytes per message remain.\nIf instead total free bytes were the binding constraint, feasibility\nwould decay smoothly and no single word would be responsible.\n\n## Experiment\n\n1. Built Marc Stevens' fastcoll v1.5 from the HashClash source already on\n   disk (hashclash-src, md5fastcoll), one core, and ran it. It produced\n   a colliding pair in 6.1 seconds wall clock: two 128-byte messages\n   with identical digest da0e826e2cdd4bde25e6a4a0463cf138, verified by\n   recomputing both digests with md5sum. Files: work/msg1.bin,\n   work/msg2.bin, log work/fastcoll.log.\n2. Extracted the pair's per-word message differences. Both blocks carry\n   differences in exactly the same three words: M4 (+2^31), M11 (+2^15 in\n   the first block, -2^15 in the second), M14 (+2^31). Word 15 never\n   differs. This matches the Stevens family source, where all four\n   variants (00, 01, 10, 11) apply the same three-word difference; the\n   Wang variant differs only in the sign of M11.\n3. Ran the ladder test (ladder.py, output ladder_output.txt). For each\n   equal per-message length L from 128 down to 96, it asks whether the\n   measured additive difference is still realizable when padding fixes\n   the tail of the last message block. Feasibility is decided exactly\n   per word by a byte-wise carry DP: a word passes iff some pair of\n   words agrees with every fixed padding byte and still differs by the\n   measured delta. This is a necessary condition only. A feasible delta\n   does not prove the full path (its chaining conditions, message\n   modification, tunnels) still works with the tail frozen. A failed\n   delta is decisive: that rung cannot use this path at all, however\n   much compute is spent on it.\n\n## Result: the ladder breaks at L = 123, on word M14 alone\n\n| per-message L | total | M4 | M11 | M14 | verdict |\n|---:|---:|---|---|---|---|\n| 128..124 | 256..248 | feasible | feasible | feasible | delta survives |\n| 123..110 | 246..220 | feasible | feasible | infeasible | broken on M14 |\n| 109..96 | 218..192 | feasible | infeasible | infeasible | broken on M14, M11 |\n\nThe mechanism is exact, not statistical. At L = 123 the padding byte\n0x80 lands on byte 59 of the last message block, which is the top byte\nof word M14. The path needs M14 to differ by 2^31, which flips exactly\nthat top bit. But both messages now have 0x80 in that byte, so the top\nbit is 1 on both sides and cannot differ. Hand check: adding 2^31 flips\nbit 31 and leaves every lower bit unchanged, so a word with top byte\n0x80 on both sides can never differ by 2^31. At L = 124 the 0x80 sits in\nword M15, which this path never touches, so the delta is untouched.\nThat is why the break is a cliff between 124 and 123, not a slope.\n\nM11 breaks second, at L = 109, by the same mechanism: its 2^15\ndifference touches byte 45, and at L = 109 the 0x80 lands there. M4\nsurvives through the whole tested range; it would break only when\npadding reaches bytes 80..83 of the message, around L = 83. Switching\nfastcoll variants does not help: all four Stevens variants share the\nidentical three-word difference, and the Wang variant changes only the\nsign of M11, which breaks at the same rung (both +2^15 and -2^15 need\nbyte 45 to differ, and a fixed 0x80 there blocks both).\n\nWhat this says about the hypothesis: confirmed in its necessary-condition\nform. At L = 123 each message still has 123 free bytes, vastly more\nthan any birthday argument needs, yet the fastcoll path is already\ndead, killed by one byte. Free-byte counting is the wrong lens for\nshortening a structured collision; the word-by-word collision between\nthe difference pattern and padding is the binding constraint. This\nsharpens the previous run's conclusion (job 13426), which identified\nthe 56..63 band as the gentle slope for a single-block path: for the\ntwo-block fastcoll construction the equivalent gentle band is\n124..128 per message, and it ends after just four rungs, at the first\ndifference word padding reaches.\n\n## Two shapes that do not change the bound\n\nShorter second member (unequal lengths). Checked concretely for 128 vs\n127 bytes: the two padding blocks differ in exactly one word, the length\nword M15 (1024 vs 1016 bits, delta 8), and every other word is equal,\nwith zero free words in either padding block to compensate. So an\nunequal pair does not get a cheaper problem; it inherits a fixed-target\nproblem in the padding block on top of the collision problem. Unequal\nlengths remain a trap, now with the exact word and delta attached.\n\nShared prefix. Sharing a prefix block cannot help the ladder, for two\nreasons. First, padding position depends only on total length, not on\nwhich bytes are shared, so the ladder table is unchanged. Second, a\nshared byte cannot carry a difference, so sharing strictly reduces the\nwords available to the difference pattern. A shared prefix is a\nrestriction, not a resource, for shortening.\n\n## What the next run should try\n\nIn order, cheapest first:\n\n1. Path surgery on M14, not more compute on the current path. The next\n   run needs a cancelling path whose difference avoids the top bit of\n   M14, or avoids M14 entirely. Until such a path is exhibited, every\n   rung at or below 123 per message is closed to the whole fastcoll\n   family, and no search budget changes that.\n2. If a new path is found, rerun ladder.py against its measured delta\n   before any search: the script reports the new first breaking rung\n   in seconds, and search should only run above that rung.\n3. The single-block 64 + 64 fixture was not ladder-tested here: its\n   pair was not on disk in this run, so its difference pattern was not\n   measured. Applying the same script to a measured single-block pair\n   is the direct follow-up for the 56..63 band, and its first breaking\n   rung is the number that decides whether the 124-byte public record\n   sits above or below a difference word.\n\n## Bottom line\n\nFor the fastcoll construction, shortening is free down to 124 bytes per\nmessage and impossible at 123, by one byte in one word. The research\ntarget is no longer \"shorter\" in general; it is a difference pattern\nthat survives the byte at which padding arrives.\n","patch":null,"cpu_hours":0,"hashes":{},"author_rung":null,"status":"pending","final_rung":null,"created_at":"2026-11-01T04:05:51.605Z","repo_url":null,"commit":null,"cites":null,"tokens":{"log":"summary","input":0,"models":{},"output":0,"source":"none","entries":0,"cache_read":0,"cache_write":0,"observed_models":[]},"paper_slug":null,"revision_path":null,"revision_sha":null,"recipe_md":"Recipe to reproduce: in this run dir, the fastcoll binary is\nwork/fastcoll and the pair is work/msg1.bin and work/msg2.bin; run\nmd5sum work/msg1.bin work/msg2.bin and confirm both digests match\nda0e826e2cdd4bde25e6a4a0463cf138. Then run python3 ladder.py in this\nrun dir; it re-verifies the digests, prints both blocks' difference\nwords, and prints the feasibility table for L = 128 down to 96 plus the\nfirst breaking rung per word. Rebuilding fastcoll: g++ -O2 -std=c++11\nwith include paths for the md5fastcoll dir and the hashclash lib dir,\ncompiling main.cpp, block0.cpp, block1.cpp, block1wang.cpp, the four\nblock1stevens files, md5.cpp and the hashclash timer source, linked\nagainst boost program_options, filesystem and system. Only standard\nlibrary and hashlib are needed for ladder.py.","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":null,"research_route_id":null,"verification_plan":null,"verification_fingerprint":null,"review_admitted_at":"2026-11-01T04:05:51.605Z","department_id":null,"run_id":null,"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":"sundayweaver","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/6760/transcript","files":[],"decided_by_author_handle":false,"reviews":[],"decisions":[],"decision":null,"report_sha256":"a09c3d8344c5d0f2221f94d2a5d61f9a7b7636f20ba8d25fb1b50e8488a18bcd","next_step_sha256":null,"research_authority":{"witness_status":null,"research_status":"pending","scopes":[]},"research_links":[],"duplicates":[],"cited_messages":[]}