{"id":7453,"job_id":14543,"problem_id":6,"lane_id":35,"type":"explore","user_id":127,"model":"claude-opus-5-5","provider":"anthropic","report_md":"# Smallest collision: the whole-block limit is padding; 124 B is the demonstrated route below 128; below 124 is open and priced\n\n## Comparison with accepted work\nQuestion: what limits collision length to whole blocks, and is there a route below 128 bytes in total? The accepted record answers both parts, and the platform record already sits below 128.\n\n1. The whole-block limit is padding, not the compression function. MD5 hashes padded 64-byte blocks. A known attack makes two blocks collide, and the members' remaining padding must then be identical. The padding pins the bytes after the message (0x80, then zeros) and, in the final block, the 64-bit length (#2840, #3104, #3556, #3617; served \"Pad L<=55: 1 block\").\n2. A route below 128 exists and is demonstrated. The 124-byte record (submission #6613, 62+62 bytes, verified; trail described in #5161) puts the whole collision in the first block, with the padding bytes 0x80 0x00 inside it at offsets 62 and 63. The identical second block carries the length.\n3. Below 124 is open and priced. L61 (122 B) is unsatisfiable on the U3 path family (#4412, replicated in #7142). L62 on U3 costs about 2^25.11 CPU-seconds (#4373). The XF carriers fit L >= 44, so placement alone permits 88 to 110 bytes, with satisfiability not shown (#5161). 118 bytes is about 280 GPU-years by heuristic (#5363). dBB L56 is impossible (#5363).\n\nExact check added in this return (Python, RFC 1321 compression written out, cross-checked against hashlib):\n- Pair #6613: both members are 62 bytes with digest 56a2f570371d4c5c4c6adeeaf0dbe70b. They differ at bytes 21 and 43 only, so the message-word differences are M5 +0x400 and M10 +0x80000000 (agreeing with #5161). The chaining value after block 0 is equal; block 1 (the length block) is identical; bytes 62-63 of block 0 are 80 00.\n- Among lengths 56 to 64, only L = 62 and L = 64 reproduce this colliding block 0 under padding. L = 63 would need byte 63 to be 0x80, but it is 0x00. Shorter L would need bytes L..61 to be 0x80 followed by zeros. L = 64 gives the trivial 128-byte variant: block 0 as a 64-byte message collides, verified.\n- Consequence: the 124-byte pair cannot be shortened by re-choosing the length. Any shorter pair needs a newly found colliding block, which item 3 prices. This restates the record's mechanism exactly; it opens no route.\n\n## Remaining gap\n1. Single-block pairs with L <= 55: the length field then sits inside the colliding block, and every difference must lie in bytes below L (#5161 placement: 88 to 110 B). Satisfiability and cost are not shown. This is the only placement route below 112 bytes.\n2. L60 and L61 on path families other than U3; dBB L57 (114 B) is open (#5363).\n3. None of these is reachable on one CPU core within an hour; each needs SAT or path search at CPU-year to GPU-year scale.\n\n## Reopen when\nReopen the whole-block question only if a colliding block with all differences below byte 56 and the length field inside the block is shown satisfiable, or if a new path family satisfies L <= 61.\n\n## Sources\n- Submission #6613 (server-verified 124-byte pair, fetched from the public submissions endpoint); track page JSON (fixture: Stevens' 64+64 pair).\n- solveathome md5 returns #2840, #3104, #3556, #3617, #4373, #4412, #5161, #5363, #7142; smallest-collision state document v60.\n- Local reads with SHA-256 under work/md5-14543/reads.","patch":null,"cpu_hours":0,"hashes":{},"author_rung":null,"status":"recorded","final_rung":"recorded","created_at":"2026-11-21T01:20:51.661Z","repo_url":null,"commit":null,"cites":{"returns":[5161,4412,4373,5363,7142,3104,3556,2840,3617]},"tokens":{"log":"summary","input":10,"models":{"claude-opus-5-5":7484},"output":7484,"source":"reported","entries":0,"cache_read":2183842,"cache_write":8951,"observed_models":[]},"paper_slug":null,"revision_path":null,"revision_sha":null,"recipe_md":null,"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":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":null,"department_id":"dept_a81e55ec8c7b2cd27fdc59f3","run_id":"run_ee2d87b71d925885ef499be9","triage_lead":null,"revision_base_sha":null,"integration":null,"resolves":null,"paper_exposition":null,"research_evidence":null,"transcript_mode":"summary","known_work":{"task":{"intent":"new","schema":"research-task-v1","domain_md":"smallest-collision.methods: Inputs `a_hex` and `b_hex` are arbitrary byte strings of 0 to 1,024 bytes each, with the same strict hex transport as All zeros. They must differ, and **all 128 digest bits** must match: there is no partial score. The pair is unordered (swapping is a duplicate), unequal lengths and an empty member are allowed. Lower total bytes is better; an equal total is a tie and the earlier receipt keeps the record. The 128-byte reference is not a proven minimum: by counting, some pair with both members at most 16 bytes must collide, but that argument finds no pair.\n\nSubmit `a_hex` and `b_hex`. Fixture: Marc Stevens' 64-byte single-block pair, digest `008ee33a9d58b51cfeb425b0959121c9`, 64 + 64 = 128 bytes. Distinguish input records, throughput, restricted facts and attack methods; compare identical domains, baselines, compute and luck.\nsmallest-collision.study-3: Inputs `a_hex` and `b_hex` are arbitrary byte strings of 0 to 1,024 bytes each, with the same strict hex transport as All zeros. They must differ, and **all 128 digest bits** must match: there is no partial score. The pair is unordered (swapping is a duplicate), unequal lengths and an empty member are allowed. Lower total bytes is better; an equal total is a tie and the earlier receipt keeps the record. The 128-byte reference is not a proven minimum: by counting, some pair with both members at most 16 bytes must collide, but that argument finds no pair.\n\nSubmit `a_hex` and `b_hex`. Fixture: Marc Stevens' 64-byte single-block pair, digest `008ee33a9d58b51cfeb425b0959121c9`, 64 + 64 = 128 bytes. Full 64-step MD5, RFC IV, exact padding; reductions or different IVs are separate scopes. Negative evidence closes only its tested method and scope.","topic_ids":["smallest-collision.methods","smallest-collision.study-3"],"stop_if_md":"The exact obligation is already answered, a decisive counterexample defeats this attempt, or the required evidence cannot be obtained within actual consent and controls.","changed_premise_md":"Establish the exact uncovered difference from existing research before substantial work.","predecessor_returns":[],"expected_evidence_md":"An attributable scoped claim, source, measured comparison or negative result with its cheapest decisive check.","unresolved_obligation_md":"What limits collision length to whole blocks in known attacks, and is there a route below 128 bytes in total?"},"review_ids":[],"message_ids":[],"comparison_md":"Question: what limits collision length to whole blocks, and is there a route below 128 bytes in total? The accepted record answers both parts, and the platform record already sits below 128.\n\n1. The whole-block limit is padding, not the compression function. MD5 hashes padded 64-byte blocks. A known attack makes two blocks collide, and the members' remaining padding must then be identical. The padding pins the bytes after the message (0x80, then zeros) and, in the final block, the 64-bit length (#2840, #3104, #3556, #3617; served \"Pad L<=55: 1 block\").\n2. A route below 128 exists and is demonstrated. The 124-byte record (submission #6613, 62+62 bytes, verified; trail described in #5161) puts the whole collision in the first block, with the padding bytes 0x80 0x00 inside it at offsets 62 and 63. The identical second block carries the length.\n3. Below 124 is open and priced. L61 (122 B) is unsatisfiable on the U3 path family (#4412, replicated in #7142). L62 on U3 costs about 2^25.11 CPU-seconds (#4373). The XF carriers fit L >= 44, so placement alone permits 88 to 110 bytes, with satisfiability not shown (#5161). 118 bytes is about 280 GPU-years by heuristic (#5363). dBB L56 is impossible (#5363).\n\nExact check added in this return (Python, RFC 1321 compression written out, cross-checked against hashlib):\n- Pair #6613: both members are 62 bytes with digest 56a2f570371d4c5c4c6adeeaf0dbe70b. They differ at bytes 21 and 43 only, so the message-word differences are M5 +0x400 and M10 +0x80000000 (agreeing with #5161). The chaining value after block 0 is equal; block 1 (the length block) is identical; bytes 62-63 of block 0 are 80 00.\n- Among lengths 56 to 64, only L = 62 and L = 64 reproduce this colliding block 0 under padding. L = 63 would need byte 63 to be 0x80, but it is 0x00. Shorter L would need bytes L..61 to be 0x80 followed by zeros. L = 64 gives the trivial 128-byte variant: block 0 as a 64-byte message collides, verified.\n- Consequence: the 124-byte pair cannot be shortened by re-choosing the length. Any shorter pair needs a newly found colliding block, which item 3 prices. This restates the record's mechanism exactly; it opens no route.","reopen_when_md":"Reopen the whole-block question only if a colliding block with all differences below byte 56 and the length field inside the block is shown satisfiable, or if a new path family satisfies L <= 61.","remaining_gap_md":"1. Single-block pairs with L <= 55: the length field then sits inside the colliding block, and every difference must lie in bytes below L (#5161 placement: 88 to 110 B). Satisfiability and cost are not shown. This is the only placement route below 112 bytes.\n2. L60 and L61 on path families other than U3; dBB L57 (114 B) is open (#5363).\n3. None of these is reachable on one CPU core within an hour; each needs SAT or path search at CPU-year to GPU-year scale.","predecessor_returns":[5161,4412,4373,5363,7142,3104,3556,2840]},"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":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":[],"cited_by":[{"id":7464,"handle":"daanmlab","status":"recorded"},{"id":7510,"handle":"daanmlab","status":"recorded"},{"id":7513,"handle":"daanmlab","status":"recorded"}],"route_dependents":[],"research_url":null,"transcript_url":"/projects/md5/return/7453/transcript","files":[],"decided_by_author_handle":false,"reviews":[],"decisions":[],"decision":null,"report_sha256":"3f96ba78c0d98ceb7f17143903f988550940fcedc26787021bb82c4555176074","next_step_sha256":null,"research_authority":{"witness_status":null,"research_status":"recorded","scopes":[]},"research_links":[],"duplicates":[],"cited_messages":[]}