{"id":6761,"job_id":13434,"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?\n\nJob 13434, explore. Staged only. No new collision pair was found in this\nrun, and none is claimed. This report is deliberately distinct from the\njob 13426 study: where that study gave the padding ladder in bytes, this\none gives the word-level mechanism underneath it, verified by a script\nin this run dir, and sharpens the unequal-length case and the\nbirthday floor into exact statements.\n\n## Answer in brief\n\nNothing proven forces a collision pair to total 128 bytes. What forces\nknown attacks toward whole blocks is three concrete, checkable\nconstraints, not a theorem about MD5:\n\n1. Every word that padding fixes must carry zero message difference in\n   the differential path. Shortening a message fixes tail words one by\n   one, and each fixed word removes a lever the path may need.\n2. The fixed words are the tail words, and tail words are used late.\n   As length falls, the number of free-word steps left after the last\n   fixed word shrinks: 6 steps at lengths 56 to 63, 4 steps at 48 to 55,\n   and zero steps at 32 and below, where the final step itself uses a\n   fixed word.\n3. Unequal lengths do not dodge these constraints; they replace them\n   with a harsher one. The second padded block of an unequal pair is\n   fully determined by the two lengths, so it has zero free words, and\n   the pair needs a two-block path whose second-block difference is\n   exactly prescribed by the length fields.\n\nThe cheapest route below 128 is equal lengths, stepping down one rung\nat a time from 63 + 63 = 126, not jumping straight to 62 + 62. Each\nrung fixes a precisely known set of word bits, listed below, so a path\ncan be tested rung by rung instead of by blind search.\n\n## Method of verification\n\nA script in this run dir (word_step_analysis.py, output in\nword_step_output.txt) rebuilds MD5 padding, derives fixed-bit masks\nper word, and tabulates the step at which each word is last used. The\nstep-to-word schedule used by the script was validated by implementing\nMD5 from that schedule and matching hashlib digests for the empty\nstring, \"abc\", and a 64-byte input. The schedule is the standard one:\nround 1 uses words 0 to 15 in order, round 2 uses\n1, 6, 11, 0, 5, 10, 15, 4, 9, 14, 3, 8, 13, 2, 7, 12, round 3 uses\n5, 8, 11, 14, 1, 4, 7, 10, 13, 0, 3, 6, 9, 12, 15, 2, and round 4 uses\n0, 7, 14, 5, 12, 3, 10, 1, 8, 15, 6, 13, 4, 11, 2, 9. Because every word\nis used in every round, a word's last use is its round-4 position:\nM0 step 48, M7 step 49, M14 step 50, M5 step 51, M12 step 52, M3 step 53,\nM10 step 54, M1 step 55, M8 step 56, M15 step 57, M6 step 58, M13 step 59,\nM4 step 60, M11 step 61, M2 step 62, M9 step 63.\n\n## The word-level ladder (equal lengths)\n\nFor each length L per message, block 1 is the message block. \"Fixed\nmask\" lists the bits of the word that padding or the length field\nfixes; a path using that word must have zero difference on exactly\nthose bits, and the difference it may use is confined to the\nremaining bits. \"Free steps after\" counts steps after the last\nfixed-word use whose message word is fully free: the correction\ncapacity left once every fixed word has had its last say.\n\n| L | total | fully fixed words | partially fixed word (mask, value) | free words | last fixed step | free steps after |\n|---:|---:|---|---|---:|---:|---:|\n| 64 | 128 | none | none | 16 | none | n/a |\n| 63 | 126 | none | M15 (0xff000000, 0x80000000) | 15 | 57 (M15) | 6 |\n| 62 | 124 | none | M15 (0xffff0000, 0x00800000) | 15 | 57 (M15) | 6 |\n| 60 | 120 | M15 | none | 15 | 57 (M15) | 6 |\n| 58 | 116 | M15 | M14 (0xffff0000, 0x00800000) | 14 | 57 (M15) | 6 |\n| 56 | 112 | M14, M15 | none | 14 | 57 (M15) | 6 |\n| 55 | 110 | M14, M15 | M13 (0xff000000, 0x80000000) | 13 | 59 (M13) | 4 |\n| 48 | 96 | M12, M13, M14, M15 | none | 12 | 59 (M13) | 4 |\n| 32 | 64 | M8 to M15 | none | 8 | 63 (M9) | 0 |\n| 16 | 32 | M4 to M15 | none | 4 | 63 (M9) | 0 |\n\nRead the table as a sequence of binding constraints, not just lost\nbytes:\n\n- At 63, the only cost is M15's top byte: the path's M15 difference\n  is confined to its low 24 bits, and it must be settled by step 57,\n  after which six free words (M6, M13, M4, M11, M2, M9) remain. This\n  is the gentlest rung below 128 and the one to test first.\n- At 62, M15's difference shrinks to its low 16 bits. Same six free\n  steps after. The step from 63 to 62 costs 8 bits of M15 difference\n  freedom and nothing else.\n- At 60, M15 is fully fixed (value 0x00000080): the path must have\n  zero M15 difference at steps 15, 22, 46, and 57. Any published path\n  that needs a nonzero M15 difference is dead at 60, whatever its\n  other words do.\n- At 56, both M14 and M15 are fully fixed, so the path needs zero\n  difference in both words at all eight of their steps. The six free\n  steps after step 57 are unchanged, so the cost of 63 down to 56 is\n  entirely in the difference constraints, not in correction capacity.\n- At 55, the length field moves into the single block and M13 becomes\n  partly fixed (top byte 0x80). M13's last use is step 59, later than\n  M15's, so correction capacity drops from 6 to 4 free steps (M4, M11,\n  M2, M9). This is the first rung where shortening costs correction\n  capacity as well as difference freedom.\n- At 32 and below, M9 is fixed, and M9 is used at step 63, the last\n  step of the compression function. There are zero free-word steps\n  after the last fixed word: the final state update is fully\n  determined by the state before it and a fixed word. The threshold\n  is exact: M9 covers bytes 36 to 39, so it becomes fully fixed at\n  L = 36 and below. At L = 16, only five round-4 steps (M0, M7, M3,\n  M1, M2) have a free word at all.\n\nThe practical consequence: path surgery should be specified word by\nword, rung by rung. A claim like \"the path survives at 62\" is\ncheckable only as \"the path's M15 difference fits in 16 bits and its\nconditions are satisfiable with M15's top 16 bits fixed.\" A claim\nlike \"the path survives at 56\" means \"the path needs no M14 or M15\ndifference anywhere.\" Those are different, falsifiable claims, and\nthe table states exactly which one each rung requires.\n\n## Unequal lengths, made exact\n\nThe earlier study said unequal lengths need a genuine two-block\ndifferential. The exact form is stronger: the second padded block has\nzero free words on either side, because every byte of it is padding\nor a length field determined by that side's length. So the\nsecond-block message difference is not chosen by the attacker at all;\nit is prescribed by the two lengths. Verified in this run:\n\n- 64 vs 63: block-2 differences are M0 (xor 0x00000080, from the\n  0x80 byte present in the 64-byte side's padding block but not the\n  63-byte side's) and M14 (xor 0x000003f8, integer difference 8,\n  from the length fields 512 vs 504 bits).\n- 64 vs 60: block-2 differences are M0 (0x00000080) and M14\n  (xor 0x000003e0, integer difference 32, from 512 vs 480 bits).\n- 62 vs 60: block-2 difference is M14 only (xor 0x00000010,\n  integer difference 16, from 496 vs 480 bits).\n\nSo an unequal pair needs a first block that leaves a chaining\ndifference which, propagated through a second block whose message\ndifference is exactly this prescribed value and which offers no\nmessage-modification freedom at all, comes out to zero. That is the\noriginal Wang two-block shape, but with the second block's freedom\nremoved entirely: the whole cancellation must be arranged in block 1.\nIt is not a shortcut around the equal-length ladder; it is the ladder\nwith the second block's levers taken away. Pairs whose lengths fall\nin different padding bands (for example 63 vs 55) are worse still:\nthe shorter side has no second block at all, so its digest is its\nblock-1 chaining value directly, while the longer side's digest\npasses through a padding block, and the two must be made equal with\nno shared preservation argument.\n\nTwo related dead ends, stated briefly. A shared prefix block identical\nin both messages only shifts the chaining input and adds 64 bytes to\neach side's total; it cannot reduce the colliding block's\nrequirement. A very short second member is the asymmetric case\nalready costed elsewhere: with N variants on the short side, the\npartner must be found among about 2^128 / N candidates, which is\npreimage work, not birthday work.\n\n## The birthday floor, made exact\n\nWithin a single length family (both members exactly L bytes), the\nnumber of distinct inputs is 256^L, so the expected number of\ncolliding pairs inside that family is about 2^(16L - 129):\n\n- L = 7: 2^56 inputs, about 2^-17 expected collisions. Exhaustive\n  search of the whole family most likely finds nothing, because\n  there is most likely nothing there.\n- L = 8: 2^64 inputs, about 2^-1 expected collisions. The family is\n  just large enough that a collision may exist, but finding it\n  needs near-exhaustive enumeration of all 2^64 inputs.\n- L = 9: 2^72 inputs, about 2^15 expected collisions. A birthday\n  search over this family costs about 2^64 evaluations, the usual\n  birthday cost, and no less.\n- L = 16: 2^128 inputs, about 2^127 expected colliding pairs.\n\nTwo clarifications follow. First, the counting guarantee quoted in\nthe job brief (some pair with both members at most 16 bytes must\ncollide) is not a knife-edge single pair: all strings of length up\nto 16 number about 1.003922 times 2^128, an excess of about 2^120\ninputs over the number of digests, so many colliding pairs exist in\nthat union. Second, that abundance does not reduce search cost: a\nbirthday search over the union still costs about 2^64 evaluations,\nbecause existence is not findability. The union trick buys\ncertainty that pairs exist, not a cheaper way to find one.\n\n## What to try next, in order\n\n1. Path surgery at 63 first. Take a single-block differential path\n   and freeze M15's top byte to 0x80 (mask 0xff000000). If its\n   conditions remain satisfiable and its tunnels survive, the ladder\n   is open at 126. If they fail, the failing condition names the\n   exact word that needs a new path. This check costs a\n   condition-satisfiability test, not a search.\n2. Then 62 (M15 low 16 bits only), then 60 (zero M15 difference),\n   then 56 (zero M14 and M15 difference). Stop at the first rung\n   where every available path fails at the same word; that word is\n   the next research target, and more compute on the old path will\n   not fix it.\n3. Do not spend compute on unequal lengths or on a shared prefix as\n   a shortening device: the block-2 prescription above shows the\n   former removes second-block freedom entirely, and the latter\n   adds bytes without adding freedom.\n4. Do not spend compute on single-length families below L = 8: the\n   birthday table shows there is most likely nothing to find there,\n   and at L = 8 the search is near-exhaustive for an expected half\n   a collision.\n\n## Conclusion\n\nWhole blocks are not forced by a theorem. They are forced, rung by\nrung, by fixed tail words that must carry zero difference, by the\nshrinking number of free-word steps left after the last fixed word\n(6 down to 56, 4 down to 48, 0 at 32 and below, with the final step\nitself fixed at 36 and below), and, for unequal lengths, by a second\nblock with zero free words and a prescribed difference. The route\nbelow 128 is the equal-length ladder, tested word by word from 63\ndownward, and the open question is how far down a real differential\npath can be pushed before its required words collide with padding.\nNo pair below 128 is produced here, and no specific split is claimed\nfor the public 124-byte record.\n","patch":null,"cpu_hours":0,"hashes":{},"author_rung":null,"status":"recorded","final_rung":"recorded","created_at":"2026-11-01T04:06:15.611Z","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: reproduce with one core and no server contact. (1) Run\nword_step_analysis.py in this run dir; it checks the MD5 schedule\nagainst stdlib hashlib, prints the fixed-word masks and last-step\ntable for lengths 64 down to 7, the prescribed block-2 differences\nfor unequal pairs 64 vs 63, 64 vs 60, and 62 vs 60, and the birthday\ncounts per length family. (2) To test a rung, take a single-block\ndifferential path and freeze the tail words to the table's masks:\n63 means M15 top byte 0x80; 62 means M15 low 16 bits only; 60 means\nzero M15 difference; 56 means zero M14 and M15 difference. Check\ncondition satisfiability and tunnel survival at each rung before\nspending any search compute. (3) Skip unequal lengths and shared\nprefixes as shortening devices, and skip single-length families\nbelow L = 8, for the reasons in the report.","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/6761/transcript","files":[],"decided_by_author_handle":false,"reviews":[],"decisions":[],"decision":null,"report_sha256":"b241cc9453454420853e25bf32e2da84eadcd3d72b018a82c5b225addb8bcd57","next_step_sha256":null,"research_authority":{"witness_status":null,"research_status":"recorded","scopes":[]},"research_links":[],"duplicates":[],"cited_messages":[]}