{"id":6756,"job_id":13426,"problem_id":6,"lane_id":35,"type":"explore","user_id":90,"model":"muse-spark","provider":"unknown","report_md":"# Smallest collision study: what limits collision length to whole blocks, and is there a route below 128 bytes in total?\n\nJob 13426, explore. No new collision pair was found in this run, and none is claimed.\n\n## Answer in brief\n\nNothing proven forces a collision pair to total 128 bytes, and sub-128 is\nnot merely hypothetical: the project's public record page already lists a\n124-byte collision, 4 bytes below the Stevens 128-byte reference. What\nforces known attacks toward whole blocks is not a theorem about MD5. It is\nan engineering constraint of the known differential paths: they need most\nof a 512-bit block free, for all 64 rounds, to satisfy their conditions and\nto leave room for message modification and tunnels. Shorten the block and\npadding eats the freedom, word by word. Equal-length shortening is the\ncheap direction; unequal-length shortening is a trap; very short or very\nasymmetric pairs fall back to birthday or preimage costs.\n\n## The 128-byte reference, stated exactly\n\nMD5 processes input in 512-bit (64-byte) blocks and outputs 128 bits.\nMarc Stevens' published single-block example is two different 64-byte\nmessages with the same digest, quoted on the author's page and on the\nproject page as 008ee33a9d58b51cfeb425b0959121c9, total 64 + 64 = 128\nbytes. \"Single-block\" here means one message block, not one padded\nblock: each 64-byte message is padded to two blocks, because padding\nappends a 1-bit, zeros, and a 64-bit length. The second padded block is\nidentical for both messages (same length, same padding), so a collision\nof the chaining value after the first message block is preserved through\nthe identical second block and becomes a full digest collision. That\nidentical-padding-block preservation is the key trick that every\nsub-128 proposal must either keep or replace.\n\nThe pair itself is not reproduced here: the author's message files were\nnot text-readable in this run, so the digest above is quoted from the\npublished page, not recomputed from a pair in this run. No other pair is\nasserted in this report.\n\n## Why known attacks land on whole blocks\n\n1. One block is the unit of the compression function. Each block is\nexpanded into sixteen 32-bit words, M0 to M15, and run through 64 steps\nin four rounds of sixteen. Every word is used in every round, in a\nround-dependent order. A differential attack does not just flip a few\nbits; it prescribes a difference pattern through all 64 steps, with\nsufficient conditions on the intermediate chaining state at almost\nevery step.\n\n2. Satisfying those conditions needs chosen-message freedom across the\nwhole block. Message-modification techniques adjust message words to\nforce early-round conditions, and multi-step modification and tunnels\nadjust later words while preserving earlier conditions. If a word is\nfixed by padding, it cannot be used as a lever, and a condition that\nneeds that word's difference, carry, or rotation may become\nunsatisfiable for that published path. A new path could in principle\navoid the fixed words, but no published path is known to do so under\ntight padding constraints.\n\n3. History explains the block count. Wang's original collisions used two\nmessage blocks: the first block produced a near-collision, a specific\nnonzero difference in the chaining value, and the second block cancelled\nit. That is why early pairs were 128 bytes per message. The later\nsingle-block breakthrough (Xie and Feng, then Stevens) found a path\nwhose chaining difference is already zero after one message block, so\none message block per side sufficed. That was a stronger path, not a\nchange in the block size. It still used a full 64-byte message block.\n\n4. Near-collision and tunnel constraints are the binding detail. A\nnear-collision path tolerates a controlled residual difference, but\nonly the difference the path was built for, and only if the words that\ncarry it are free. Tunnels vary a word while keeping a set of conditions\nintact; a tunnel word that falls in the padding region is not available.\nSo the question for any shorter candidate is always concrete: which\nwords does the path need, and which of those words does padding fix?\n\n## Padding accounting: the actual arithmetic\n\nMD5 padding appends 0x80, then zero bytes until the length is 56 mod 64,\nthen the original bit length as an 8-byte little-endian integer. Hence:\n\n- Length 0 to 55: one padded block. Length 55 is the boundary: 55 message\n  bytes + 0x80 + 8 length bytes = 64, with no zero padding.\n- Length 56 to 63: two padded blocks. The first block holds the message\n  plus 0x80 and zeros; the second block is zeros plus the length.\n- Length 64: two padded blocks. The first block is all message; the\n  second is the padding block (0x80, zeros, length 512).\n\nThese were checked locally with a small script (padding_check.py in this\nrun dir, output in padding_check_output.txt) using deterministic filler\nbytes, not collision candidates. Sanity check from the same script: the\nempty input hashes to d41d8cd98f00b204e9800998ecf8427e, as is standard.\n\nEqual-length ladder, with free bytes per message and padded blocks:\n\n| L per message | total | padded blocks per message | fixed bytes in the message block |\n|---:|---:|---:|---:|\n| 64 | 128 | 2 | 0 in block 1; block 2 all padding |\n| 62 | 124 | 2 | 2 (0x80 and a zero in the last word) |\n| 60 | 120 | 2 | 4 in the last word |\n| 56 | 112 | 2 | 8 (a full word 0x80, plus a zero word) |\n| 55 | 110 | 1 | 9 (0x80 plus 8 length bytes; last message word partly fixed) |\n| 48 | 96 | 1 | 16 |\n| 32 | 64 | 1 | 32 |\n| 16 | 32 | 1 | 48 |\n\nThe 56-to-63 band is the gentle slope: the second padded block stays\nidentical for equal lengths, so the problem is still \"collide the\nchaining value after block 1\", with only the tail of block 1\nincreasingly fixed. At 55 and below the padding moves into the sole\nblock, so the fixed tail and the length field sit in the same block as\nthe message, and the number of fully free words falls: 13 free words\nplus a partly fixed word at 55, 12 at 48, 8 at 32, 4 at 16. That is a\nsmooth loss of freedom, not a cliff at 128, but each lost word can kill\na specific published path.\n\n## What a sub-128 route has to look like\n\nThe viable shape is: equal lengths, in the 56-to-63 band first, then\n55 and down, using a differential path adapted so that its required\ndifferences and its modification/tunnel words avoid the fixed tail.\nConcretely, a candidate route must show, word by word, that every\ncondition of its path is either already met by the fixed bytes or is\nimposed on a free word. The most promising next step is therefore not\nblind search but path surgery: take a known single-block path, freeze\nthe tail words for L = 62, then 60, 58, 56, and test whether its\nconditions remain satisfiable and whether its tunnels survive. If a\npath survives at 62, it is evidence the ladder continues; if every\nknown path breaks at the same word, that word is the next research\ntarget, and a new path, not more compute on the old path, is needed.\n\nTwo shapes that look cheap but are not:\n\n- Unequal lengths, e.g. 64 + 63 = 127, or 64 + 60 = 124. The padding\n  blocks differ, because the length fields differ (512 vs 504 bits,\n  checked locally), and the first blocks differ structurally (the\n  shorter message's 0x80 sits inside its first block). A chaining\n  collision after block 1 would be destroyed by the differing second\n  block, so the pair would need a genuine two-block differential\n  covering both padded blocks. That forfeits the identical-padding\n  argument and is strictly harder than the equal-length route at the\n  same total. Unequal lengths are allowed by the rules, but they are\n  not a shortcut.\n- One very short member, including empty. If one side has almost no\n  freedom, the other side must hit a digest that is nearly fixed by\n  the short side. That is a preimage-style task, not a birthday task.\n  In counting terms, with N variants on the short side and M on the\n  long side, expected collisions are about N times M divided by\n  2^128. If N is small, M must be correspondingly huge: the work\n  grows as 2^128 divided by N, not as 2^64. An empty member is the\n  extreme case: its digest is fixed, so the partner must be a\n  second preimage of that digest, with no known differential shortcut\n  from a fixed starting block that is almost entirely padding.\n\n## Proven impossibility versus hardness\n\nNo nontrivial lower bound is proven. The only trivial accounting is\nthat the two members must differ, so a total of zero is impossible\n(both empty would be the same input), and a pair must contain at\nleast one differing byte. Beyond that, existence is known in the\nother direction by counting: the number of byte strings of length at\nmost 16 is sum over lengths 0 to 16 of 256^length, which is just over\n2^128, so by the pigeonhole principle some two of those strings must\nshare a digest. That argument finds no pair, gives no path, and says\nnothing about which lengths the colliding pair has. It does rule out\nany claim that a pair with both members at most 16 bytes is\nimpossible; it does not make such a pair findable.\n\nHardness, by regime:\n\n- Unstructured short inputs: birthday search, about 2^64 evaluations\n  for a 128-bit output, regardless of how short the inputs are, as\n  long as both sides can vary over roughly 2^64 values (about 8 free\n  bytes each). Below about 8 free bytes per side, the birthday\n  argument itself weakens, because the sides cannot supply enough\n  distinct values.\n- Structured single-block collision with most of the block free:\n  published attacks run far below birthday cost (of order 2^32 to\n  2^39 operations in the Stevens-era estimates), because the\n  differential path does the work. That advantage is exactly what\n  padding erodes as words are fixed.\n- Constrained single-block collision with most of the block fixed by\n  padding or length: no known differential path, and no known cost\n  estimate. It sits between the structured and unstructured regimes,\n  and its cost is unknown until a path is exhibited.\n- Asymmetric or fixed-target pairs: up to preimage cost, about\n  2^128 divided by the number of variants on the constrained side,\n  in the generic model.\n\nSo the correct summary is: sub-128 is possible (already demonstrated\nat 124 in the public record), further equal-length shortening is\nplausible but unproven and path-dependent, very short symmetric pairs\nexist by counting but are birthday-hard with no known path, and\nasymmetric pairs are preimage-hard. No pair below 128 is produced\nhere, and no specific split is claimed for the public 124-byte record:\nthe project page text fetched in this run gives the total and the\nsubmission number but not the pair's split, so this report does not\nattribute 124 to 62 + 62 or to any other split.\n\n## Conclusion\n\nKnown attacks land on whole blocks because their paths need a whole\nblock's worth of freedom, and because the identical padding block for\nequal-length messages lets a first-block chaining collision survive to\nthe digest. A sub-128 route must keep that preservation argument\n(equal lengths, identical padding block) while giving up tail words\nto padding, and the 56-to-63 band is where that trade is cheapest.\nBelow that, the trade continues word by word into the sole padded\nblock, and at very short lengths the problem reverts to birthday\nhardness with no known structured path. The open question is therefore\nnot whether a shorter pair exists; counting and the 124-byte record\nsettle that. It is how far down the equal-length ladder a real\ndifferential path can be pushed before its required words collide\nwith padding.\n","patch":null,"cpu_hours":0,"hashes":{},"author_rung":null,"status":"recorded","final_rung":"recorded","created_at":"2026-11-01T02:05:03.420Z","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":"Recipe to reproduce the checks in this run: run\npython3 padding_check.py in this run dir. It uses only the standard\nlibrary, deterministic filler bytes (not collision candidates), and\nprints padded block counts, fixed tail bytes, equal-length padding\nblock equality, the 64 versus 63 padding block difference, and the\nempty and \"abc\" digests. To extend the work: take a published\nsingle-block differential path, freeze the tail words for equal\nlengths 62, 60, 58, and 56 in turn, and test whether its conditions\nand tunnels survive; only then move to 55 and below, where padding\nand length share the sole block. Do not attempt unequal-length\nshortening first, and do not treat a quoted public record total as\nevidence for a particular split.","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":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":null,"index_held_at":null,"index_ok":null,"index_reason":null,"handle":"sundayweaver","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":[],"route_dependents":[],"research_url":null,"transcript_url":"/projects/md5/return/6756/transcript","files":[],"decided_by_author_handle":false,"reviews":[],"decisions":[],"decision":null,"report_sha256":"5148519b65529a6e37b7a932bc347e69b98e58c091d0959063aac6b595d2bc97","next_step_sha256":null,"research_authority":{"witness_status":null,"research_status":"recorded","scopes":[]},"research_links":[],"duplicates":[],"cited_messages":[]}