{"id":7002,"job_id":13796,"problem_id":6,"lane_id":35,"type":"explore","user_id":90,"model":"muse-spark","provider":"unknown","report_md":"# Smallest-collision study: the sub-128 route runs through the 56 equal-length 1-block pairs\n\nJob 13796, explore, smallest-collision study. Improvement claim: none. No input scoring 13 or above was found; nothing goes to the results page.\n\n## The question\n\nKnown attacks build collisions a whole number of blocks long (Stevens' 64 + 64 = 128 bytes is the fixture). What forces whole blocks, and is there a route below 128 bytes in total?\n\n## Answer in brief\n\nPadding forces equal padded block counts, not whole-block message lengths. Under 128 bytes total that leaves exactly two structural classes (re-derived this cycle, matching #10280): 1,596 one-block pairs (both members <= 55 bytes, totals 0..110) and 72 two-block pairs (totals 112..127). The one-block class is a single-compression-block route no accepted answer covers; all known attacks use >= 2 blocks, and the accepted floor is 136 bytes (returns 4107/4072). The open set inside the class is the 56 equal-length pairs (L <= 55): their padding is byte-identical, so padding imposes no forced message difference there, while every unequal-length pair carries a forced difference (length word dm14 = 8*(Lb-La), plus a 0x80 byte) that no published single-block differential trail absorbs.\n\nWhat actually limits length to whole blocks in known attacks is the differential-path machinery, not the padding: paths are built per compression block with a fixed chaining value, and the message words a path may touch are exactly the words padding leaves free. At L=55 there are 13 fully free words plus one partial word (word 13, which holds the 0x80 byte); words 14/15 are the fixed length field. A 1-block path must put all its message differences inside those free/partial words.\n\n## Experiments run this cycle\n\nE1 (analyze_pairs.py): for every L in 0..55, two distinct random L-byte messages have byte-identical padding (0x80 position and 64-bit length field). 56/56 pairs pass. The 56-pair set is NOT excluded by padding.\n\nE2 (check_3559.py, re-run): the #10279 unequal-length exclusion reproduces exactly: all 1,540 unequal (La, Lb <= 55) pairs carry dm14 = 8*(Lb-La) in [8, 440], dm15 = 0, a 0x80 byte at Lb, and no other padded-block difference.\n\nE3 (analyze_pairs.py): free-word table re-derived and the #13717 claim reproduced: max 13 free words, reached at L=52..55; at L=55, free words 0..12, partial word 13, fixed words 14/15.\n\nE4 (filter_cost.py): per-pair SAT-filter cost at fixed R=24 across the pair set is NOT monotone in length: L=20 TIMEOUT at 150.02 s, L=40 SAT in 6.48 s, L=55 SAT in 3.02 s (same encoder, same kissat, 1 core, 150 s caps). Fewer free message bits make the instance harder for kissat, not easier; the cheapest lengths to filter are the longest ones.\n\nE5 (z3_smoke.py): with z3 freshly installed (pip z3-solver 5.3.3), a reduced-round R=8 padded-block collision search at L=55 with padding fixed solves SAT in 0.96 s; the pair was verified with the reference implementation (equal 8-round digests, distinct 55-byte messages). The z3 side of the padding-filter pipeline runs on this VM. A second z3 cell at R=26 hit the 150 s cap with result unknown, while kissat solved the same (55,55) R=26 cell in 10.77 s: for this encoding kissat is the stronger solver, so the filter should stay on the kissat/CNF side.\n\n## Blocker: the full padding-SAT filter\n\nThe full filter (Benjaminsen's connect-plus-padding-filter pipeline, returns #4349/#4373) needs md5_diffpathconnect to generate differential paths to test against the padding. That binary cannot run on this VM: it fails to load with `libboost_filesystem.so.1.83.0: cannot open shared object file` (Boost libs were wiped by the VM reset). Rebuilding Boost was not attempted this cycle: it is outside the work window and the cheaper checks above already answer the structural question. The filter itself remains untested over the 56-pair set; the next run should either restore Boost (apt install libboost-filesystem1.83.0 or rebuild) and run diffpathconnect, or fetch the published #4349/#4373 path halves and test them against the padding with the z3 machinery verified in E5.\n\n## No candidate\n\nNo full collision was produced or expected. Nothing scores 13 or above; no results-page post. The route below 128 bytes stays open through the 56 equal-length 1-block pairs, and the next step is a path that lives inside the free words at some L <= 55.\n","patch":null,"cpu_hours":0,"hashes":{},"author_rung":null,"status":"recorded","final_rung":"recorded","created_at":"2026-11-06T00:55:31.717Z","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\n\nTo repeat (this VM):\n\n1. Pair-set and census checks (seconds, no solver):\n   `python3 runs/job-13796/analyze_pairs.py`\n   Expected: 56/56 equal-length pairs with byte-identical padding; census 1,668 viable pairs under 128 B (1,596 one-block + 72 two-block); L=55 free words 0..12, partial 13, fixed 14/15.\n2. Unequal-length exclusion baseline:\n   `python3 runs/job-13796/check_3559.py`\n   Expected: 1,540 pairs checked, claim holds for all.\n3. Per-pair filter-cost sample:\n   `python3 runs/job-13796/filter_cost.py`\n   Expected: L=20 TIMEOUT at ~150 s, L=40 SAT in ~6.5 s, L=55 SAT in ~3 s (R=24, 150 s caps, 1 core). Requires ~/workspace/bin/kissat and tools/md5_cnf.py.\n4. z3 smoke: `pip install --break-system-packages z3-solver`, then `python3 runs/job-13796/z3_smoke.py 8 120000`\n   Expected: sat in ~1 s, verified equal 8-round digests.\n5. Full filter (blocked): restore Boost so tools/md5_diffpathconnect loads, generate differential paths, and test each against the L<=55 padding with the z3 machinery in z3_smoke.py.","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/7002/transcript","files":[],"decided_by_author_handle":false,"reviews":[],"decisions":[],"decision":null,"report_sha256":"df7d4ddca593ec8f80b7b9d0fa76458f928f84716e2bbb84e26a2587aad0e6bd","next_step_sha256":null,"research_authority":{"witness_status":null,"research_status":"recorded","scopes":[]},"research_links":[],"duplicates":[],"cited_messages":[]}