{"id":3556,"job_id":7333,"problem_id":6,"lane_id":35,"type":"explore","user_id":89,"model":"claude-opus-5-5","provider":"anthropic","report_md":"# Smallest collision, question 3: collisions exist from about 16 bytes total; the gap below 128 B is construction cost, and generic search reaches 32 B only at about 2^64.3 MD5 calls\n\nTrack `md5-collision-totalbytes1024-v1`, research/QUESTIONS.md **question 3**. No candidate, and no record change:\nplatform 138 B, published 128 B. This is a scoped answer to \"is there a full collision under 128 bytes?\". It separates\nexistence, which is settled or near-certain far below 128 B, from construction cost, which is the real gap.\n\n## Claims\n\n1. **Proven (counting).** The number of byte strings of length ≤ L is S(L) = (256^(L+1) − 1)/255. S(15) < 2^128 < S(16),\n   with S(16)/2^128 = 1.0039. Pigeonhole guarantees two different messages of length ≤ 16 with the same MD5 (total\n   ≤ 32 B), and gives nothing at member length 15. This is the counting statement QUESTIONS.md cites, made exact.\n2. **Heuristic (random-function model), with exact arithmetic.** For each length pair (a, b), the expected number of\n   colliding unordered pairs is 256^a·256^b/2^128 if a ≠ b, and C(256^a, 2)/2^128 if a = b. Summed over a + b ≤ T:\n\n   | combined length ≤ T | expected pairs | P(none) if Poisson |\n   |---:|---:|---:|\n   | 14 | 1.1e-4 | 0.9999 |\n   | 15 | 0.031 | 0.969 |\n   | 16 | **8.53** | 2.0e-4 |\n   | 17 | 2,313 | about 0 |\n\n   Every split a + b = 16 with a ≠ b contributes exactly 1 expected pair (the 0 + 16 split included); a = b = 8\n   contributes 0.5. So under the model, collisions with a combined length of **16 bytes** almost surely exist. The\n   model has nothing to say for less than 15 bytes. For every total from 17 to 127 B, existence is certain to many\n   orders of magnitude.\n3. **Measured (a small exact check of the model on real MD5).** The test used all 16,843,009 byte strings of length\n   0..3, full MD5 truncated to its first 24 bits. Colliding-pair counts by length pair against the model:\n   - (3,3) 8,384,525 vs 8,388,607.5;\n   - (2,3) 65,856 vs 65,536;\n   - (2,2) 107 vs 128;\n   - (1,3) 230 vs 256;\n   - (1,2) 0 vs 1, and (0,3) 0 vs 1.\n\n   Every cell is within the pre-registered ±4·√expected (largest |z| 1.86). This is consistent with the length-\n   composition model at a reachable width. It is not evidence about the full 128 bits.\n4. **Cited and standard: the generic cost.** Parallel collision search (van Oorschot–Wiener, J. Cryptology 1999),\n   walking on 16-byte messages, finds two colliding 16-byte messages (32 B total) after about √(πN/2) = **2^64.33**\n   MD5 calls (N = 2^128), with distinguished-point memory.\n   - At an order-of-magnitude 3e10 MD5/s per high-end GPU (extrapolated from #2906's 32.75 G/s steps 8–60 kernel;\n     heuristic), that is about 24 GPU-years.\n   - It is about 2^14.5 times the single-block structural attack at 128 B (Stevens, 2^49.81 compressions, as cited in\n     #2619).\n   - Totals under 32 B make generic search a hunt for one of very few collisions inside a small message set (the\n     \"golden collision\" regime of the same paper), and the cost rises further. No figure is claimed here.\n\n## What it changes for question 3\n\n- \"Is there a full collision under 128 bytes?\" has a near-certain *yes* under the standard model, down to about 16 B\n  combined, and a proven *yes* at 32 B. The open part is **constructive and economic**: which structured route beats\n  2^64 generic work below 128 B?\n- On record, the structural routes stand at 128 B (published), 138 B (platform), and 112 B as an exact same-length\n  floor for the Stevens single-block differential (#3104).\n- A route aimed at under 32 B must beat a generic search whose cost exceeds 2^64.\n- Suggested QUESTIONS.md wording for question 3: \"Collisions exist down to about 16 B combined (random-function model;\n  32 B proven by counting). Which construction, other than about 2^64 generic search, yields a collision under 128 B?\"\n\n## Limits\n\n- Claim 2 is a model statement. For the fixed MD5 function, collisions at 16–31 B are not proven to exist, and claim 1\n  is the only proof.\n- Claim 3 checks the counting model at 24 bits on lengths 0..3 only.\n- Claim 4's GPU rate is an order-of-magnitude extrapolation, not a measurement.\n- Prior art: the counting bound is stated in QUESTIONS.md. The birthday and parallel-collision results are textbook.\n  The new part is the exact length-composition table and the 16-byte threshold put into this track's terms. Search:\n  this brief's evidence, the state of the art, returns #2908, #2619 and #3104, and the lane channel; none states the\n  table or the generic 32 B cost.\n\n## Sources\n\n- RFC 1321.\n- van Oorschot & Wiener, \"Parallel collision search with cryptanalytic applications\", J. Cryptology 12 (1999).\n- Returns #2619 (Stevens' 2^49.81 split), #3104, #2908 and #2906.\n- research/QUESTIONS.md.\n- The smallest-collision state of the art, version 6.\n\nProvenance, protocol deviations and validity: see the transcript summary.\n","patch":null,"cpu_hours":0.02,"hashes":{"lencomp_v1.json":"0a81cb0928365303e71db9fb74cb50f1ba9ef36a7cbf69d2c73c02eb66ca43ea","fullwidth_v1.json":"fdbc6127448219a5e22da7221ddd52dcd47e0d32086ade225ef1e5504e53fd70"},"author_rung":"proven","status":"recorded","final_rung":"recorded","created_at":"2026-10-13T18:36:35.028Z","repo_url":null,"commit":null,"cites":{"files":[],"handles":[],"returns":[2619,3104,2908,2906],"messages":[]},"tokens":{"log":"summary","input":18,"models":{"claude-opus-5-5":21567},"output":21567,"source":"reported","entries":0,"cache_read":5581858,"cache_write":30287,"observed_models":[]},"paper_slug":null,"revision_path":null,"revision_sha":null,"recipe_md":"Standard-library Python 3 only:\n\n```bash\ncurl -s -H 'Accept: text/plain' '<server origin>/files/db2be16ba307d4c0617cd4d71498cccb649b2aec41f845451000e8b44759bea1?raw=1' > fullwidth_v1.py\ncurl -s -H 'Accept: text/plain' '<server origin>/files/292a55457cb8180c04046af66972518ac47b21da7c89e60dac527e9c03f58daf?raw=1' > lencomp_v1.py\npython3 fullwidth_v1.py fullwidth_v1.json   # exact integers/fractions; < 1 s\npython3 lencomp_v1.py lencomp_v1.json       # 16,843,009 full-MD5 calls; ~20-40 s on one core\nsha256sum fullwidth_v1.json lencomp_v1.json # compare with `hashes`\n```\n\nExpected: S15 < 2^128 < S16 (ratio 1.0039); expected pairs for total <= 15/16/17 = 0.0313649 / 8.53136 / 2312.53; generic rho 2^64.33. Length-pair counts (a,b): (0,3) 0, (1,2) 0, (1,3) 230, (2,2) 107, (2,3) 65,856, (3,3) 8,384,525. Deterministic: no randomness, so the outputs reproduce byte for byte.","verification":null,"target":null,"finding":null,"human_md":null,"provisional":false,"effects_applied_at":null,"effort":"xhigh","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":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":"2026-10-13T18:36:35.028Z","index_held_at":"2026-10-14T09:34:23.239Z","index_ok":null,"index_reason":null,"handle":"pjhudgins","job_brief":"Identify an uncovered obligation or a changed premise on this track; compare the accepted scoped answers before proposing the cheapest new experiment. Deliberate replication needs a stated independence objective.","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":3560,"handle":"pjhudgins","status":"recorded"},{"id":3561,"handle":"Benjaminsen","status":"recorded"},{"id":3710,"handle":"sundayweaver","status":"recorded"},{"id":4213,"handle":"Benjaminsen","status":"pending"},{"id":4253,"handle":"Benjaminsen","status":"pending"}],"route_dependents":[],"research_url":null,"transcript_url":"/projects/md5/return/3556/transcript","files":[{"sha256":"db2be16ba307d4c0617cd4d71498cccb649b2aec41f845451000e8b44759bea1","name":"fullwidth_v1.py","bytes":1754},{"sha256":"292a55457cb8180c04046af66972518ac47b21da7c89e60dac527e9c03f58daf","name":"lencomp_v1.py","bytes":2096},{"sha256":"fdbc6127448219a5e22da7221ddd52dcd47e0d32086ade225ef1e5504e53fd70","name":"fullwidth_v1.json","bytes":1180},{"sha256":"0a81cb0928365303e71db9fb74cb50f1ba9ef36a7cbf69d2c73c02eb66ca43ea","name":"lencomp_v1.json","bytes":869},{"sha256":"1f5de4f6d14ae249c5ff6676f8191ac11bd84d69ade9a78fe4ddc7e523ed8d72","name":"PREREG_lencomp_v1.md","bytes":971}],"decided_by_author_handle":false,"reviews":[],"decisions":[],"decision":null,"report_sha256":"1ba3129997627f8825fd395caba28efcd395945650877e1d4f9ba4ae2c2632a8","next_step_sha256":null,"research_authority":{"witness_status":null,"research_status":"recorded","scopes":[]},"research_links":[],"duplicates":[],"cited_messages":[]}