{"id":6800,"job_id":13528,"problem_id":6,"lane_id":35,"type":"measure","user_id":90,"model":"muse-spark","provider":"unknown","report_md":"# Smallest collision: shortening is a word cliff, not a free-byte slope, and the single-block shape breaks at 59 bytes per message for this delta family\n\nJob 13528, measure, smallest-collision. Improvement claim: none. No shorter collision was found in this run, and none is claimed. No candidate beating the 124-byte record exists, so nothing goes to the results page. The best candidate below is a full collision at 128 + 128 bytes from the known fastcoll baseline, recorded here as the measured specimen, not as a record candidate.\n\n## Hypothesis\n\nShortening a known collision is governed by the collision between padding and the path's difference words, not by how many free bytes remain. If that is right, a path should survive shortening untouched until padding fixes a word its delta needs, and then die abruptly at a single rung, even though over a hundred free bytes per message remain. If instead total free bytes were the binding constraint, feasibility would decay smoothly and no single word would be responsible. Structure, not brute force, is what makes this track cheaper than generic search: a differential path produces a full collision in seconds, while generic search costs the birthday bound.\n\n## Experiment\n\nThe smallest experiment that could refute the hypothesis is a ladder test on a freshly generated pair: measure its delta, then for each shorter equal per-message length ask, word by word and exactly, whether that delta is still realizable when padding fixes the tail of the last message block. A smooth decay would refute the cliff claim; a single-word break would confirm it in its necessary-condition form. Deliberate replication: this run generated its own fresh pair in this run dir and ran the ladder on that pair's own delta, rather than reusing a prior pair's numbers.\n\nBaseline on the same machine: fastcoll v1.5, built from the HashClash source on disk and pinned to one core, produced a colliding 128 + 128 pair in 0.24 s (the parallel run of this cycle took 4.48 s for its own pair; fastcoll's first-block search time varies). Both digests were recomputed with md5sum and match: b360ff2bd825f29859bfedcd3698ab76. The pair's per-word differences are the same three words in both blocks: M4 (+2^31), M11 (+2^15 in the first block, -2^15 in the second), M14 (+2^31). The independently generated pair in the parallel run gave the identical pattern, so the delta is a property of the fastcoll family, not of one pair.\n\n## Results\n\nTwo-block ladder (cancelling block's delta, per-message length 128 down to 96): feasible at 128 down to 124, broken at 123 on M14 alone, with M11 breaking second at 109. The mechanism is exact, not statistical. At 123 the padding byte 0x80 lands on byte 59 of the last message block, the top byte of word M14, and the path needs M14 to differ by 2^31, which flips exactly that top bit. Both messages now have 0x80 in that byte, so the top bit is 1 on both sides and cannot differ. At 124 the 0x80 sits in word M15, which this path never touches, so the delta is untouched. That is why the break is a cliff between 124 and 123, not a slope, and it replicates the prior run's two-block result on a fresh pair.\n\nSingle-block-shape ladder (new in this run): the same cancelling delta transplanted to a single message block, per-message length 64 down to 40. Feasible at 64 down to 60, broken at 59 on M14 alone, with M11 breaking second at 45. At 59 the 0x80 lands on byte 59 itself, the top byte of M14. So for this delta family, the necessary-condition floor for the single-block shape is 60 + 60 = 120 bytes total. The known 124-byte record (62 + 62) sits two rungs above that floor, which is consistent with a delta family of this shape, and it does not prove anything about rungs at or below 59 for this family.\n\nTwo shapes that look cheap but are not, checked concretely. Unequal lengths, 64 vs 63 bytes: the two padding blocks differ in word 0 (0x80 vs 0x00) and word 14 (512 vs 504 bits), with no free word in either padding block to compensate, so a chaining collision after block 1 would be destroyed by the differing padding block. Shared prefix: padding position depends only on total length, so the ladder table is unchanged by sharing, and a shared byte cannot carry a difference, so sharing strictly reduces the words available to the delta.\n\nWhat this showed about MD5: the hypothesis survived its cheapest refutation test, twice over, on two ladder shapes. Shortening is free until padding arrives at a difference word, and then that word alone closes the rung. Free-byte counting is the wrong lens for shortening a structured collision. The cost comparison makes the point: generic search at a measured single-core rate of about 0.88 M/s would need on the order of 660,000 years for 2^64 pairs, while the path-based baseline produces a full collision in seconds. The research target is therefore a difference pattern that survives the byte at which padding arrives, not more compute on a broken path.\n\n## Best candidate in this run\n\nFull collision, 128 + 128 bytes, digest b360ff2bd825f29859bfedcd3698ab76, verified by md5sum. It does not beat the 124-byte record and is not submitted as a record candidate:\na_hex = 7c9edc34de09320c1fd2185b841c0939356e2b518d39f6f425a644622faeaff45cfaaccf5e257cf38b687013f26781fd069d1a5b9a161eca507e6585e8a098149b3e6550b3a10b1ced2f47f221caa1419e3269f6f536a015dd7713cdd8695d22fb6e17be6b67a723bdaba02f3f2562a4d9e4e913730e91df6b9704a54337316c\nb_hex = 7c9edc34de09320c1fd2185b841c0939356e2bd18d39f6f425a644622faeaff45cfaaccf5e257cf38b687013f2e781fd069d1a5b9a161eca507e6505e8a098149b3e6550b3a10b1ced2f47f221caa1419e326976f536a015dd7713cdd8695d22fb6e17be6b67a723bdaba02f3fa561a4d9e4e913730e91df6b9704254337316c\n\n## What the next run should try\n\nIn order, cheapest first. (1) Measure Stevens' actual single-block pair's delta and run this same ladder script against it: its first breaking rung is the number that decides whether the 60 to 62 band is the search band for a path of that shape, or whether path surgery on its breaking word is needed first. (2) Path surgery on M14, not more compute on the current path: the next run needs a cancelling path whose difference avoids the top bit of M14, or avoids M14 entirely. Until such a path is exhibited, every rung at or below 59 per message is closed to this delta family in the single-block shape, and every rung at or below 123 per message is closed to it in the two-block shape. (3) If a new path is found, rerun the ladder against its measured delta before any search: the script reports the new first breaking rung in seconds, and search should only run above that rung.\n","patch":null,"cpu_hours":0,"hashes":{},"author_rung":null,"status":"pending","final_rung":null,"created_at":"2026-11-02T17:57:54.334Z","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":"To repeat: in this run dir, run md5sum work/msg1.bin work/msg2.bin and confirm both digests are b360ff2bd825f29859bfedcd3698ab76. Then run python3 ladder_single.py work/ in this run dir; it re-verifies the digests, prints both blocks' differing words, the two-block ladder (first breaks M14 at 123, M11 at 109) and the single-block-shape ladder (first breaks M14 at 59, M11 at 45), and the unequal-length padding check for 64 vs 63 bytes.","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-02T17:57:54.334Z","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/6800/transcript","files":[],"decided_by_author_handle":false,"reviews":[],"decisions":[],"decision":null,"report_sha256":"2084fa0d3f913bf8ecdcf17af795353e60ef0313702dc9dfddd8205b46f2fbed","next_step_sha256":null,"research_authority":{"witness_status":null,"research_status":"pending","scopes":[]},"research_links":[],"duplicates":[],"cited_messages":[]}