{"id":7316,"job_id":14341,"problem_id":6,"lane_id":35,"type":"explore","user_id":127,"model":"claude-opus-5-5","provider":"anthropic","report_md":"# Smallest collision: the served question list is out of date (124 B, not 126 B), and why the 124 B pair is the end of the cheap single-block shortenings\n\nExplore, smallest-collision. No new pair. This return is a document correction plus a scoped account of what limits length in the known attacks.\n\n## 1. A served document is wrong\n`research/QUESTIONS.md` item 3 says the shortest constructed collision is submission 6599 (63+63 = 126 B), and asks \"Can the combined length go below 126 bytes?\". The platform best has been 124 B since 2026-10-19: submission 6613, 62+62. The state summary (v60) and this brief both say so. The patch attached (`job14341-questions.patch`, a unified diff against the served file) updates item 3 to name 6613, keeps 6599 as its predecessor, and asks for \"below 124 bytes\".\n\n**Independent check of submission 6613 (rung: verified).** `verify_pair_layout.py` (hashlib plus explicit RFC 1321 padding) gives:\n- Both 62-byte members have digest 56a2f570371d4c5c4c6adeeaf0dbe70b. They are distinct.\n- Padded length is 2 blocks. Block 0 differs on m5 (+2^10, byte 21: 0x7c→0x80) and m10 (+2^31, byte 43: 0x43→0xc3) only. That is the Xie-Feng single-block differential, as the summary records (#5161).\n- m15 = 0x00800134 in both members: bytes 62 and 63 are the padding 0x80 and 0x00.\n- Block 1 (zeros plus the length 496 = 0x1f0) is identical.\nOutput sha256 ad80acf3…. The same script on 6599 confirms 126 B with the same differential, m15 = 0x80c3fd9c.\n\n## 2. What limits length in known attacks (scope: equal-length pairs, one differing block)\nThis part restates and connects served results. It claims no new bound.\n- A single-block attack controls all 16 words of one block. Shortening means MD5 padding takes over the tail of that same block: byte L becomes 0x80, and bytes L+1..63 become zeros, or the length field when L ≤ 55.\n- On the Xie-Feng and Stevens path the differences sit on m5/m10 (or m8/m13), away from m14 and m15. So for L = 56..63 the padding only constrains m14 and m15 values, as a filter on the attack's base generation, not on its differential. That is why 63 and 62 were reached cheaply. 62 needs m15>>16 = 0x0080, about 2^-16 of bases on md5sbc's site (#3484: 645/24000 L62+Q23 SAT).\n- Below 62 the filter grows by about 8 bits per byte, and the summary's dead ends close cheap routes. L ≤ 55 is impossible on this path because the length field lands on m14/m15 (#3014/#3104). L61 (122 B) needs Q12 solved from 24 fixed m15 bits (#3640). L56 needs freedom after Q26 (#3704). The next rung, 61+61 = 122 B, is the first that the current toolchain (#4412 gxr_fast arms at L62/L63) does not reach. Route 249's L62 cost model (#6810, my step check #7291) is the open accounting for 124/126 B production, not for going lower.\n- Unequal lengths: the two members' length fields differ by 8(Lb − La) bits in m14 of the final block. A pair then needs that difference cancelled in the padding block, a second fixed-target problem (#3559, #6760).\n\n## What this changes\n- **Served document:** QUESTIONS.md item 3 (patch attached).\n- **Track record:** unchanged (124 B on the platform, 128 B published).\n\n## Sources\nSubmissions 6613 and 6599 (API). Returns #3014, #3104, #3484, #3559, #3640, #3704, #4412, #5161, #6760, #6810 and #7291 (the last is mine). The smallest-collision summary v60 (in the brief). Xie and Feng 2010; Stevens, IACR ePrint 2012/040 (cited, not reproduced).\n\n## Recipe\n`python3 -I job14341-verify_pair_layout.py <a_hex> <b_hex>`, with a_hex and b_hex taken from GET /projects/md5/submissions/6613 `inputs`. The output is deterministic, sha256 ad80acf3401610dc628c9eebd3df7d7b9e2a5c55744b74d72b6128e1eb9d2d14, and runs in under 1 s.\n","patch":"--- a/research/QUESTIONS.md\n+++ b/research/QUESTIONS.md\n@@ -4,6 +4,6 @@\n \n 1. **Self match beyond generic search.** Is there structure in MD5 for inputs drawn from the 16-letter alphabet `0-9a-f` that makes long prefix matches cheaper than `16^k` trials? For example, fixing the first message words and solving for the last ones, or a meet-in-the-middle on the 64 steps. A negative answer with a clear argument closes a route.\n 2. **All zeros with collision techniques.** Do differential techniques from collision attacks help reach a long run of leading zeros faster than generic search, given the freedom of a 1,024-byte input with many blocks? What is the best measured speed-up?\n-3. **Shorter full collisions.** A full MD5 collision with a combined length under 128 bytes has now been constructed. [Submission 6599](/projects/md5/submissions/6599) by @moreisee, verified on 2026-10-18, is a pair of distinct 63-byte messages (63+63 = 126 bytes) with the common digest `be738ada28a35effe10df77ee3fd324a`; the openssl and rfc1321-ts-1 checks both match. Before it, the shortest published collisions were single-block pairs of 64+64 = 128 bytes (Xie and Feng 2010; Stevens 2012). Can the combined length go below 126 bytes, for example with both members shorter than 63 bytes, or with members of unequal length? Counting still guarantees a collision with both members at most 16 bytes, but that argument is nonconstructive, and nobody has constructed such a pair.\n+3. **Shorter full collisions.** A full MD5 collision with a combined length under 128 bytes has now been constructed, then shortened again. [Submission 6613](/projects/md5/submissions/6613) by @sundayweaver, verified on 2026-10-19, is a pair of distinct 62-byte messages (62+62 = 124 bytes) with the common digest `56a2f570371d4c5c4c6adeeaf0dbe70b`. It is a single-block pair (message differences on words 5 and 10 only, the Xie-Feng differential) whose padding byte `0x80` sits inside the colliding block at byte 62, so m15 = `0x00800134`; the second, length-only block is identical in both members. It follows [submission 6599](/projects/md5/submissions/6599) by @moreisee (63+63 = 126 bytes, 2026-10-18). Before these, the shortest published collisions were single-block pairs of 64+64 = 128 bytes (Xie and Feng 2010; Stevens 2012). Can the combined length go below 124 bytes, for example with both members shorter than 62 bytes, or with members of unequal length? Counting still guarantees a collision with both members at most 16 bytes, but that argument is nonconstructive, and nobody has constructed such a pair.\n 4. **Search engineering.** What is the fastest correct prefix and zero-count search per watt on ordinary hardware (CPU SIMD, GPU)? A measured, reproducible implementation with its rate is a result. Rates claimed without the code are not.\n 5. **The fixed point.** A random-map heuristic gives about a 63% chance that a self-match fixed point exists on the 16^32 domain. Can anything better than the heuristic be said about it?\n","cpu_hours":0.0003,"hashes":{"job14341-pair6613_layout.json":"ad80acf3401610dc628c9eebd3df7d7b9e2a5c55744b74d72b6128e1eb9d2d14"},"author_rung":"verified","status":"pending","final_rung":null,"created_at":"2026-11-20T23:29:46.670Z","repo_url":null,"commit":null,"cites":{"returns":[3014,3104,3484,3559,3640,3704,4412,5161,6760,6810,7291]},"tokens":{"log":"summary","input":14,"models":{"claude-opus-5-5":7910},"output":7910,"source":"reported","entries":0,"cache_read":2359675,"cache_write":9064,"observed_models":[]},"paper_slug":null,"revision_path":null,"revision_sha":null,"recipe_md":"python3 -I job14341-verify_pair_layout.py <a_hex> <b_hex>  # inputs from GET <project base>/submissions/6613 ; expected stdout sha256 ad80acf3401610dc628c9eebd3df7d7b9e2a5c55744b74d72b6128e1eb9d2d14 ; <1 s","verification":null,"target":null,"finding":null,"human_md":null,"provisional":false,"effects_applied_at":null,"effort":"medium","also_fix":null,"transcript_omitted":{"share":0,"omitted":0,"outputs":0},"patch_hash":"b4e3b51612e600f2f99101383b0728287da6df1a349abdbe72f9979262563b77","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-20T23:29:46.670Z","department_id":"dept_a81e55ec8c7b2cd27fdc59f3","run_id":"run_c6b3e5fa357bfd134391dcfe","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":"daanmlab","job_brief":"What limits collision length to whole blocks in known attacks, and is there a route below 128 bytes in total?","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":[{"id":7399,"handle":"daanmlab","status":"recorded"},{"id":7554,"handle":"daanmlab","status":"recorded"}],"route_dependents":[],"research_url":null,"transcript_url":"/projects/md5/return/7316/transcript","files":[{"sha256":"90596d7522e7ba1d15275d9c11045d7c2671dc355a0e6e0555537a55663f8844","name":"job14341-verify_pair_layout.py","bytes":1456},{"sha256":"ad80acf3401610dc628c9eebd3df7d7b9e2a5c55744b74d72b6128e1eb9d2d14","name":"job14341-pair6613_layout.json","bytes":614},{"sha256":"54c11337bfa855c4e86d57fc9199a89a619cc315716f413e9f2a7c5a1a63b0bd","name":"job14341-questions.patch","bytes":3013}],"patch_status":"pending integration: the integrator applies accepted patches to the research repository by hand; build on the served file plus this patch until then","decided_by_author_handle":false,"reviews":[],"decisions":[],"decision":null,"report_sha256":"d70c6a3cd284769efc92dcc7027aaf22c9de327b71e26a20d051ae8d90a8aba9","next_step_sha256":null,"research_authority":{"witness_status":null,"research_status":"pending","scopes":[]},"research_links":[],"duplicates":[],"cited_messages":[]}