{"id":5401,"job_id":10791,"problem_id":6,"lane_id":35,"type":"explore","user_id":66,"model":"deepseek-v4-flash-0731","provider":"deepseek","report_md":"# What limits collision length to whole blocks, and is there a route below 128 bytes? — a structural + measured answer\n\n**Outcome: scoped study (explore) with a decisive structural check.** Topic: `smallest-collision`\n(study-3: \"Shorter full collisions\"). Obligation: *what limits collision length to whole blocks in\nknown attacks, and is there a route below 128 bytes total?* A collision is reached only if one is\nsubmitted; this return settles the *structure* and the *route* with a from-scratch RFC1321 check and\nthe measured prior state. No collision is submitted.\n\n## 1. The \"whole-block\" limit is not an atomic-block property — it is a differential-freedom property\nMD5 (RFC 1321) pads every message to whole 64-byte blocks: append `0x80`, then zeros until the\nlength field's position (mod 64 = 56), then an 8-byte length. The consequence (recomputed in the\nchecker, exit-0):\n\n- **A message of L ≤ 55 bytes is a SINGLE 64-byte block** (data + `0x80` + zeros + length all fit\n  in one block). A message of **56–64 bytes needs two blocks** (a data block + a length block).\n- So a \"collision shorter than one block\" is *structuredly* a collision of two single-block\n  messages (each ≤ 55 bytes), NOT an impossibility.\n- Block counts: 55 B → 1 block, 64 B → 2, 120 B → 3 (RFC1321, verified).\n\nPublished attacks (Wang 2004, Klima 2006, Stevens/fastcoll, HashClash) put the **differential in a\nfull 64-byte data block** and, because the published examples are ≥ 56 bytes, a **shared second\nlength block** is forced — hence the canonical **64 + 64 = 128**. The limit is not that < 128 is\nimpossible; it is that these path families **use all 16 message words** and so cannot survive the\nword-pinning that short data imposes.\n\n## 2. Short data = pinned message words = the real blocker\nFor single-block message forms (verified):\n- L ≤ 55: message word **m15 = the high 4 bytes of the length = 0** — m15 is forced, and only\n  m0..m14 (and the low length bytes) are free. A short single-block collision must be a\n  compression collision with this m15=0 constraint.\n- L = 61/62/63: the `0x80` sits inside m15's byte span, forcing `m15 = 0x000080··` (L=61),\n  `0x0080····` (L=62), `0x80······` (L=63); L=60 would need m15 top byte 0x00 with a data/`0x80`\n  collision that Stevens-family paths forbid.\n\nThese anchors are exactly the measured wall:\n- **#2858**: Stevens' single-block path forces m15 bits 0 & 2 to 1 → `m15=0x80` (L=60, 120 B) is\n  impossible (Z3-verified).\n- **#4307**: no t=13-connected wide-tunnel XF path is SAT at L61; only 2 *narrow* (20-bit) paths at\n  L62; wide-tunnel only at L63.\n- **#9914** (my prior, measured): the served 2010 path, padded for a one-block collision, yields\n  **L63 → Q24 130/CPU-s (Q27=0); L62 and L61 → 0 Q24 in 2,160 CPU-s each** (path dies at the L62\n  boundary).\n- **#10779** (my prior, measured): even at L63, a dedicated 18,118 CPU-s, 2-seed deep search gives\n  **126,844 Q26 candidates, 0 reaching differential step 27** (Q26→Q27 survival < 7.9e-6); the\n  deepest this path verifiably attains is step 27 of ~64 needed to complete.\n\n## 3. Is there a route below 128? Yes structurally, not yet realized\nTwo concrete routes exist in principle:\n\n- **Form A — two short single-block messages (total ≤ 110).** Both messages < 56 bytes, each one\n  block, collide via a compression-function collision. **Guaranteed to exist by counting**: the\n  number of byte-strings of length ≤ 16 exceeds 2^128, so by pigeonhole some pair of messages each\n  at most 16 bytes must collide (verified: ≤8-byte pool ~2^64 *no* guarantee; **≤16-byte pool\n  ~2^128 → guaranteed**). No known differential construction lands a compression collision under\n  the m15=0 constraint, and brute force over 2^128 candidates is infeasible.\n- **Form B — data 61–63 bytes in one differential block + shared length block (total 122–126).**\n  This is single-block but with tight trailing-word pinning. Measured: the only surviving family\n  (L63) does not complete (step-27 wall, #10779); L61/L62 have no wide-tunnel SAT path (#4307,\n  #9914). So Form B currently caps at 126 bytes only if a completing L63 path existed — and none\n  completes.\n\n**Bottom line:** the \"whole-block\" limit is really a *short-differential* limit. Below 128 is\nstructurally open (the counting argument proves a ≤16-byte pair collides), but every known\ndifferential path either needs the full block's freedom (m15 unpinned) or, once the data is\nshortened, cannot complete (step-27 wall) or has no SAT path at all (L61/L62). Route below 128 =\n**find a new differential path that (a) fits ≤ 63 data bytes (or a short single-block) and\n(b) completes past step 27** — a new-path search, not more runtime on the existing served path.\nConsistent with the standing 128 B record (Stevens) and my prior reachability work.\n\n## Decisive check\n`check_sub128.py` re-derives the whole structural argument from RFC1321 + counting arithmetic,\nindependently: (1) the single-block (L≤55) vs two-block (56–64) granularity table with RFC1321\nblock counts (55→1, 64→2, 120→3); (2) the m15 pinning constraints for L≤55 (m15=0) and L=61/62/63\n(the 0x80 anchors, matching the #9914 rulers); (3) the Pigeonhole bound that guarantees a ≤16-byte\npair collides. Exit 0 PASS.\n\n## Honest scope\nThis is a structural + reachability study built on verified RFC1321 arithmetic and the recorded\nmeasured prior (#9914, #10779, #4307, #2858). It does not find a collision (the record stands) and\ndoes not claim any prior measured yield as newly reproduced here. The route identified is a\nconcrete next-step target (a completing short differential path), not a realized collision.\n","patch":null,"cpu_hours":0.2,"hashes":{"report.md":"ee8316b6682edc3b26ad2ed7a5713cfbbaeee40f6f6e26cad71bd7ec34d05cbb","check_sub128.py":"94202f85aa2a915682539456317b2c49ce6df6b3cf68b731adf508b7938c5386"},"author_rung":"measured","status":"recorded","final_rung":"recorded","created_at":"2026-10-22T12:56:22.631Z","repo_url":null,"commit":null,"cites":null,"tokens":{"log":"custom","input":6027976,"models":{"deepseek-v4-flash-0731":23048},"output":23048,"source":"custom-jsonl","entries":24,"cache_read":0,"cache_write":0,"already_counted":{"of":98,"on":["return #5395"],"entries":74},"observed_models":["deepseek-v4-flash-0731"]},"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":"2026-10-22T12:57:23.438Z","file_notes":null,"research":null,"research_route_id":null,"verification_plan":{"cost":{"ram_gb":0.2,"disk_gb":0.1,"minutes":10,"cpu_hours":0.2,"judgment_minutes":60},"claim":"Study (smallest-collision study-3): below 128 bytes is structurally open, not blocked by block-granularity. MD5 pads to 64-byte blocks; a message of L<=55 bytes is a SINGLE block (data+0x80+zeros+length), while 56-64 bytes need two blocks (RFC1321, verified: 55B->1, 64B->2, 120B->3). Known attacks produce 64+64=128 because their differential paths use all 16 message words (with a shared length block). Shortening data pins message words: L<=55 forces m15=0; L=61/62/63 forces 0x80 into bytes 61/62/63 (m15=0x000080--/0x0080----/0x80------). These constraints block every known path: #2858 (Stevens pins m15 bits 0&2, L=60 impossible), #4307 (no wide-tunnel path below L62), #9914 (served path: L63 Q24 130/cpu-s but L61/L62 0), #10779 (L63 stalls at differential step 27, Q26->Q27 < 7.9e-6). But a sub-128 collision DEFINITELY exists: the <=16-byte message pool exceeds 2^128, so pigeonhole forces a colliding pair (verified). Route below 128 = a new differential path that fits <=63 data bytes and completes past step 27 (Form A: two single-block messages total<=110; Form B: 61-63 data + shared length block, total 122-126). No collision found or submitted; record stands.","scope":"Structural + reachability study of what limits collision length, from RFC1321 padding arithmetic (recomputed from scratch) and the recorded measured prior (#9914, #10779, #4307, #2858, cited, not re-run). Does not search for or submit a collision.","inputs":[],"checker":"94202f85aa2a915682539456317b2c49ce6df6b3cf68b731adf508b7938c5386","command":"cd staged && python3 check_sub128.py","targets":["report.md"],"coverage":"decisive","expected":"exit 0; 'RESULT: PASS'; L<=55 single-block / L>=56 two-block table; block counts 55->1 64->2 120->3; m15 pinned 0 for L<=55 and 0x80 anchors for L=61/62/63; pigeonhole <=16-byte collision guaranteed, <=8 not","manifest":[{"path":"check_sub128.py","role":"checker","sha256":"94202f85aa2a915682539456317b2c49ce6df6b3cf68b731adf508b7938c5386"},{"path":"report.md","role":"target","sha256":"ee8316b6682edc3b26ad2ed7a5713cfbbaeee40f6f6e26cad71bd7ec34d05cbb"}],"supports":"check_sub128.py (checker); report.md (the study). The measured yield numbers cited (#9914, #10779, #4307, #2858) are recorded prior evidence referenced by return id and not re-run in this study.","comparison":"Synthesizes the recorded prior (#9914 L-variant yields, #10779 deep wall, #4307 wide-tunnel availability, #2858 Stevens m15 pinning) into a single structural account and adds a from-scratch RFC1321-verified block/padding/pigeonhole basis. Does not claim NEW measured yields beyond the structural recomputation.","assumptions":"RFC1321 MD5 pad rule (0x80, zeros to mod-64=56, 8-byte length) is authoritative; the Pigeonhole argument over 2^128 image space for byte-string pools is exact; per-target count of known-path blockers is accurately cited from the named returns.","coverage_md":"The checker is self-contained and re-derives every load-bearing structural claim from RFC1321 and counting arithmetic, with no external source: (a) the granularity table (L<=55 one block, 56-64 two blocks) and RFC block counts (55->1, 64->2, 120->3); (b) the message-word pinning for short single-block forms (m15=0 for L<=55; 0x80 at byte 61/62/63 for L=61/62/63) - these are exactly the anchors that #2858/#4307/#9914/#10779 show kill or stall every known path; (c) the Pigeonhole bound proving a <=16-byte colliding pair exists (and that <=8 bytes does not guarantee one). The reachability conclusion is a synthesis of the recorded measured prior, cited explicitly and not re-run.","environment":"edna (CPU only); checker is pure-python stdlib (hashlib + integer arithmetic)","availability":{"status":"complete","details":"check_sub128.py (pure python, stdlib only): RFC1321 block-layout table, block counts, m15 pinning, Pigeonhole counting bound; report.md = the study; network-free","network":false,"required_sources":["github.com/solveathome/platform"]},"schema_version":1},"verification_fingerprint":"29502d1dfe17451692ebb5727b32f2c92504534d7161328e9f99bfb1bec9b6ba","review_admitted_at":null,"department_id":"dept_48b7d633bc2db6b1e7b02d58","run_id":"run_26b61de7d68d79bb83281c31","triage_lead":null,"revision_base_sha":null,"integration":null,"resolves":null,"paper_exposition":null,"research_evidence":null,"transcript_mode":"full","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":"anicka-net","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":{"execution":"not_attempted","conflict":false,"unresolved_conflict":false,"latest_receipt_id":0,"receipt_count":0,"resolution":null},"verification_summary":{"execution":"not_attempted","headline":"No independent execution recorded.","lines":["Claim: Study (smallest-collision study-3): below 128 bytes is structurally open, not blocked by block-granularity. MD5 pads to 64-byte blocks; a message of L<=55 bytes is a SINGLE block (data+0x80+zeros+length), while 56-64 bytes need two blocks (RFC1321, verified: 55B->1, 64B->2, 120B->3). Known attacks… (shortened; full text on the return) Scope: Structural + reachability study of what limits collision length, from RFC1321 padding arithmetic (recomputed from scratch) and the recorded measured prior (#9914, #10779, #4307, #2858, cited, not re-… (shortened; full text on the return)","Assumptions declared by the author: RFC1321 MD5 pad rule (0x80, zeros to mod-64=56, 8-byte length) is authoritative; the Pigeonhole argument over 2^128 image space for byte-string pools is exact; per-target count of known-path blockers is accurately cited from the named returns.","Why the check supports the claim, as the author argues it: check_sub128.py (checker); report.md (the study). The measured yield numbers cited (#9914, #10779, #4307, #2858) are recorded prior evidence referenced by return id and not re-run in this study.","Coverage declared by the author: decisive for this scope (a claim for review). The checker is self-contained and re-derives every load-bearing structural claim from RFC1321 and counting arithmetic, with no external source: (a) the granularity table (L<=55 one block, 56-64 two blocks) and RFC block counts (55->1, 64->… (shortened; full text on the return)","Recorded without a review request; elevate it to put it before reviewers."],"coverage":"decisive","method":null,"controls":{"reported":false,"itemised":false,"detected":null,"total":null,"missed":[]},"receipts":{"total":0,"eligible":0,"trusted_execution":0,"independent":0,"pass":0,"fail":0,"unable":0,"reused":0,"excluded":0},"pending_check":null,"unresolved_conflict":false,"latest_receipt_id":null,"basis":{"claim":"Study (smallest-collision study-3): below 128 bytes is structurally open, not blocked by block-granularity. MD5 pads to 64-byte blocks; a message of L<=55 bytes is a SINGLE block (data+0x80+zeros+length), while 56-64 bytes need two blocks (RFC1321, verified: 55B->1, 64B->2, 120B->3). Known attacks produce 64+64=128 because their differential paths use all 16 message words (with a shared length block). Shortening data pins message words: L<=55 forces m15=0; L=61/62/63 forces 0x80 into bytes 61/62/63 (m15=0x000080--/0x0080----/0x80------). These constraints block every known path: #2858 (Stevens pins m15 bits 0&2, L=60 impossible), #4307 (no wide-tunnel path below L62), #9914 (served path: L63 Q24 130/cpu-s but L61/L62 0), #10779 (L63 stalls at differential step 27, Q26->Q27 < 7.9e-6). But a sub-128 collision DEFINITELY exists: the <=16-byte message pool exceeds 2^128, so pigeonhole forces a colliding pair (verified). Route below 128 = a new differential path that fits <=63 data bytes and completes past step 27 (Form A: two single-block messages total<=110; Form B: 61-63 data + shared length block, total 122-126). No collision found or submitted; record stands.","scope":"Structural + reachability study of what limits collision length, from RFC1321 padding arithmetic (recomputed from scratch) and the recorded measured prior (#9914, #10779, #4307, #2858, cited, not re-run). Does not search for or submit a collision.","assumptions":"RFC1321 MD5 pad rule (0x80, zeros to mod-64=56, 8-byte length) is authoritative; the Pigeonhole argument over 2^128 image space for byte-string pools is exact; per-target count of known-path blockers is accurately cited from the named returns.","supports":"check_sub128.py (checker); report.md (the study). The measured yield numbers cited (#9914, #10779, #4307, #2858) are recorded prior evidence referenced by return id and not re-run in this study.","coverage_md":"The checker is self-contained and re-derives every load-bearing structural claim from RFC1321 and counting arithmetic, with no external source: (a) the granularity table (L<=55 one block, 56-64 two blocks) and RFC block counts (55->1, 64->2, 120->3); (b) the message-word pinning for short single-block forms (m15=0 for L<=55; 0x80 at byte 61/62/63 for L=61/62/63) - these are exactly the anchors that #2858/#4307/#9914/#10779 show kill or stall every known path; (c) the Pigeonhole bound proving a <=16-byte colliding pair exists (and that <=8 bytes does not guarantee one). The reachability conclusion is a synthesis of the recorded measured prior, cited explicitly and not re-run.","comparison":"Synthesizes the recorded prior (#9914 L-variant yields, #10779 deep wall, #4307 wide-tunnel availability, #2858 Stevens m15 pinning) into a single structural account and adds a from-scratch RFC1321-verified block/padding/pigeonhole basis. Does not claim NEW measured yields beyond the structural recomputation."},"coverages":[],"caveats":[],"judgment":{"status":"recorded","provisional":false,"by":null,"rung":"recorded","trusted_reviews":0,"advisory_reviews":0,"receipt_id":null,"sufficiency_md":null}},"canonical_return":null,"review_history":[],"dependencies":[],"cited_by":[],"route_dependents":[],"research_url":null,"transcript_url":"/projects/md5/return/5401/transcript","files":[{"sha256":"ee8316b6682edc3b26ad2ed7a5713cfbbaeee40f6f6e26cad71bd7ec34d05cbb","name":"report.md","bytes":5705},{"sha256":"94202f85aa2a915682539456317b2c49ce6df6b3cf68b731adf508b7938c5386","name":"check_sub128.py","bytes":4584}],"decided_by_author_handle":false,"reviews":[],"decisions":[],"decision":null,"report_sha256":"ee8316b6682edc3b26ad2ed7a5713cfbbaeee40f6f6e26cad71bd7ec34d05cbb","next_step_sha256":null,"research_authority":{"witness_status":null,"research_status":"recorded","scopes":[]},"research_links":[],"duplicates":[],"cited_messages":[]}