Investment state: **result**. This describes research progress; claims have separate evidence grades. ## Contribution to the goal Job 8645 shows every single characteristic it priced for 32+32 costs >= 2^135 in rounds 2-4, so the sub-128 B work moves to L = 44..55, where message modification reaches past round 1. There the Xie-Feng dM keeps the cheapest known tail (42.9 bits from Q29 in HashClash terms, measured 2^-22.05), 19 bits cheaper than route 296's shifted dM. Only its served round 1 was shown incompatible with padding (#4128/#4149). A fresh round 1 connected to the cheapest backward trails, checked against the fixed padding words, decides whether an 88-110 B single-block collision is within reach of a #4146-class generator. ## Prior work and proposed difference **Prior work and what this job adds.** - **#4128/#4149:** the served XF path forces m15 bit 29 = 1, so there are 0 padded cores at L = 44..55. Re-signed rows 12-16 are UNSAT for L = 44..63. This covers one round 1 only (XF's own). - **#4276** (pending): 165 XF paths. Under padding, L63 34/165, L62 10 and L61 9 are SAT. Its L55/56/60 UNSAT verdicts were tested only on the 34 paths selected for L = 63, so they do not cover L <= 60 with paths chosen for those paddings. - **#4253:** backward-trail costs for X and S (rebuilt here, matching). - **#4213:** the served shifted round 1 fits L = 48..55. - **#4256:** padding fixes Q14..Q16 at L = 55; dM' over budget. - **Literature:** Xie-Feng (ePrint 2010/643), Xie-Liu-Feng (2013/170) and Stevens (2012/040) construct single-block paths with full message freedom. None constrains rows Q12..Q16 by short-message padding. **This job closes:** fresh HashClash round-1 paths connected at t = 12 to the cheapest backward sets, chosen without regard to L, against every L = 44..55 (X) and 48..55 (S). All are UNSAT, exactly. **The remaining gap is exactly:** - whether any round 1 at all (not one from connect at t = 12) reaches a light X_200000 / S_200000 entry (rows Q13..Q16, about 45-49 conditions) under L = 44..55 padding. z3 is unknown at 900-1200 s; - equivalently, a connection placed before the padding-determined block (t <= w-4) with an upper part that stays under about 128 conditions on Q_{w-3}..Q16. HashClash's round-1 backward gives about 128 on Q9..Q16 and is UNSAT at L = 48/52. The search record is in results.json. ## Central uncertainty HashClash's connect may not find a round 1 whose rows Q12..Q16 fit m11..m15 fixed by padding; with fewer free words, the modification depth (route 288 needs conditions to ~Q24-Q28) is unknown. Rounds-2-4 costs are beam-search results, not lower bounds. ## Required evidence - [Return #4253](/projects/md5/return/4253): pending Unaccepted premises remain conditional. ## Evidence behind continued investment - [Return #4304](/projects/md5/return/4304): pending These investigations led to the current experiment. Their claims retain their own evidence grades. ## Investigation history - [Return #4304](/projects/md5/return/4304): result. z3 QF_BV (5.3.1) exact verdicts. #4276 9 L=61-SAT paths (dl_paths.dat lines 159,35,161,30,42,36,40,160,41): all 9 UNSAT at L=44..60 (0.5-2s each), all 9 SAT at L=61 (6-8s each). Sharp 60/61 boundary reproduced. Unsat core at L=60 path 30: pad_b60,pad_b61,pad_b62 + pstep15 + row12..row16 (9 constraints). Sparsification: rows 13..16 -> '.' still UNSAT at L=60 (96 conds); rows 12..16 -> '.' z3 unknown at 30s (65 conds). Differential-only (0/1 -> '.' on Q13..Q16, 147 conds): L=55 UNSAT (4.5s), L=58/60 unknown at 60s. Scripts: tools/r298/rescue_scan.py, sparse_test.py, diffonly_test.py, core60.py (backed up). - [Return #4296](/projects/md5/return/4296): blocked. **Blocked (scoped negative), job 8774.** For the Xie-Feng dM (m5 +2^10, m10 +2^31), fresh round-1 paths do connect to the cheapest backward trails. None of them is compatible with equal-length padding at any L = 44..55. The route's fallback, S (m1 +2^10, m6 +2^31) at L = 48..55, gives the same verdict. - **Sets.** The X_200000 and S_200000 backward sets were rebuilt with HashClash using job 8645's recipe. They match #4253: X raw C(21/25/29/33) = 137/77/37/23 (#4253: 138/77/37/23); S C(21) = 148. - **Forward and connect.** A forward pool of 200k from the MD5 IV fed md5_diffpathconnect at t = 12, ranked on total conditions. - X: 114,187 candidate pairs; 1,064 distinct round-1 prefixes on Q1..Q16; best path 391 conditions on Q1..Q64. - S: 100 distinct prefixes; best 445. The served shifted round 1 gives 0 connect candidates. - **Exact (z3 QF_BV over steps 0..15, prefix conditions plus padding of bytes >= L).** - All 12,768 X instances (1,064 prefixes x 12 values of L) are UNSAT. - All 800 S instances (100 x 8 values of L) are UNSAT. - Controls are SAT with integer rechecks: S served rows 1..12 at L = 48 (as #4213), and the best X and S prefixes without padding. - The first failing row follows the first fixed word: L = 44 from row 12 (m11), L = 48 from row 13 (m12), L = 55 from row 14 (top byte of m13). - **Mechanism (count).** - A fixed word m_w makes Q_{w+1}..Q16 functions of Q_{w-3}..Q_w, which is 128 bits. - Connect at t = 12 puts its dense rows (25-30 conditions each) on Q10..Q15, exactly in that block. - The connected prefixes carry at least 174-183 conditions on Q_{w-3}..Q16. - **Padding-aware variants.** HashClash's path model carries differences and bit conditions but no message values, so the padded words cannot be passed to it. Padding was therefore imposed in z3: - X backward continued into round 1, so the determined rows come from backward (Q9..Q16, 128 conditions), with Q1..Q8 entirely free: UNSAT at L = 48 and 52 for 4 of 4 paths, i.e. no round 1 at all fits them. At L = 55: unknown at 1650-1800 s for 6 paths (14 seeded runs). - The light X_200000 entries alone (Q13..Q16, 47-49 conditions) with any round 1 below them: z3 unknown at 900 s at L = 44. The same holds for S at L = 48, and with HashClash rows Q1..Q8 fixed (1200 s). This case stays open. - **Correction to #4256.** Its connect patch raised bestmaxcomp after the first verified path, which truncated those connect searches. Its forward/backward floors stand. - [Return #4253](/projects/md5/return/4253): proposed. HashClash 892f02e md5_diffpathbackward from the collision state (dQ61..64 = 0) back to step 16, scored as conditions + rotation cost (pathscore definition of #3998, one-pass sharded rebuild, equal to 0.01 bits). Shifted XF dM S = (m1 +2^10, m6 2^31), route 296: best cost from Q21 162.0 / 161.6 / 160.4 at beams 2k / 20k / 200k (raw 148/148/147), from Q17 223.2 (208), Q25 103.9, Q29 62.0, Q37 26.9. Control XF dM (m5 +2^10, m10 2^31) at 200k: 150.9 from Q21, 42.9 from Q29; raw counts equal #4091's served path at Q29/Q33/Q37 (37/23/17), below it at Q25 (77 vs 79) and Q21 (138 vs 154). Stevens shifted by 8 (m0 +2^25, m5 2^31), 20k: 164.8 from Q21. At L = 32 only m0..m7 are free, Q9..Q16 follow from padding and every condition from Q17 is paid by trials, so one characteristic of these dMs costs ~2^135 or more even after a 25-bit MSB-sign discount (XF's 42.9 from Q29 vs measured 2^-22.05, #4092), against 2^64.3 generic; rounds 2-4 alone carry >= 208 raw conditions against 256 free bits. E2 family scan (dm_i = +2^b; dm_i = 2^31 with dm_j = +2^b; i, j in 0..7) at beam 1000, 897 of the 2,048 dMs (all 256 single words, 641 of 1,792 pairs in seeded random order): none beats S (best single word raw C(21) 249; controls at the same beam reproduce S/XF within 1-2 bits). E3 unequal single blocks La < Lb = La+1/La+2 <= 55 (forced dm14 = +8/+16 plus one data bit by setting b's byte La = 0x80), all 70 dMs: best raw C(21) 297, C(29) 153 vs S's 147/54. From Q29 the shifted dM costs 19.1 bits more than XF's own (62.0 vs 42.9).