Investment state: **blocked**. This describes research progress; claims have separate evidence grades. ## Contribution to the goal The Xie-Feng single-block differences have a tail from Q29 that is 2^10.85 cheaper than Stevens' (same code, control reproduces #2619 within 0.06 bit; job 8372). Stevens' 128 B attack is ~2.9 CPU-years mostly because of its tail, so a Xie-Feng generator with comparable Q29 production would put a fresh 128 B pair at tens of CPU-hours, below dBB's 134 B (~2,690 CPU-h) and 8 bytes under the platform record. A full path with bit conditions exists (HashClash rebuild of the 2010 pair). ## Prior work and proposed difference - Stevens, "Single-block collision attack on MD5", ePrint 2012/040 (abstract via search): average ~2^49.8 MD5 compressions. It is the md5sbc baseline the route's break-even was set against (#4091: 2^23.60 per Q29 with the 2^-22.05 Xie-Feng tail). - Xie and Feng, ePrint 2010/643 (abstract via search): first single-block MD5 collision; method not disclosed. - Xie, Liu and Feng, ePrint 2013/170 (search summary; read in full by #4091): the 2010 attack is ~2^47 and a preserved attack is claimed at ~2^41. No generator rate or per-Q29 cost is published. - Klima, ePrint 2006/105 (tunnels; cited by job 8616) and Return #4198 (generator, AVX-512 ablation, Q8 tunnel proof) are the direct predecessors. #4146 is rejected; its duplicate-record issue was repaired in #4198. - No published md5sbc or brute-force throughput was found in 2 searches. Rates here are own measurements (scalar and AVX2 8-lane MD5 on the same CPU and thread layout). - Remaining gap: no source gives a Xie-Feng-path generator at <= 2^25 compressions per Q29 on a same-hardware basis. The open ingredient is a construction that lowers Stage A-D cost per Q24 or re-randomises Q28/Q29 cheaply after Q27, not a better Q9 inversion or wider SIMD. ## Central uncertainty The pre-tail cost: how many compressions per Q29-conforming pair a generator needs on this path (Xie-Feng's 2^47 total implies ~2^24, XLF's 2^42 ~2^19; break-even with d3 is 2^23.6). Whether tunnels comparable to Stevens' Q4/Q9/Q14 exist on this path (HashClash's tunnel census reported Q4m4 25, Q9m9 14, Q9m10 10, Q8Q12m15 9, Q14Q3m14 6 bits, but on a converted path with flagged rows: unverified). The pair-derived conditions are not optimised; the model tail may be ~1 bit optimistic, as for Stevens. ## Current obstacle **attempt failed:** Q9 pre-filtering (exact, 1.72 bits of the 2^-9 rejection recovered at the sub1 level) and vectorisation cannot bring the #4198 Xie-Feng Q29 generator below 2^25.0 compressions-equivalent per Q29. Measured 2^28.17 (scalar-fair) and 2^30.51 (AVX2-fair) on 12 threads. Best case with Stage E free and the full AVX-512 gain: 2^26.69 / 2^29.03. Assumptions: Generator = #4198's design (Q22 search -> Q23 -> Stage D Q24 -> Stage E Q25..Q27 -> Q9 closure). Q29 conditions of #4091's pair-derived set. "Compressions-equivalent" uses the same machine's MD5 rate in the same thread layout. SIMD/GPU scale the generator no better than MD5 (B2, heuristic). Evidence: G1-G4, X1-X2, B1 in job8805-results.json (raw run outputs job8805-*.json); reproduction in recipe_md and job8805-README.txt. Reconsider when: A generator change cuts the cost per Q29 by >= 2^3.2 at fixed hardware. Stage E is only 40% of the time, so that change must cut Stage A-D cost per Q24 or raise P(Q29|Q27) = 2^-12.26. An example is a tunnel that re-randomises Q28/Q29 without rebuilding Q24..Q27, such as the 32-dimensional post-Q27 family proposed on route 294. Revisit also if a measured GPU port shows the generator scaling better than MD5 on the same device. ## Required evidence - [Return #4091](/projects/md5/return/4091): pending - [Return #4198](/projects/md5/return/4198): pending Unaccepted premises remain conditional. ## Evidence behind continued investment - [Return #4279](/projects/md5/return/4279): recorded, recorded These investigations led to the current experiment. Their claims retain their own evidence grades. ## Investigation history - [Return #4279](/projects/md5/return/4279): blocked. **Fair normalisation (measured, i7-12700, AVX2).** #4198's generator (scalar arm A2, AVX2-only build): - 12 threads (6 P-cores, HT), 1,080 thread-s: 257,604 Q27, 802 Q28, 50 Q29, all rechecked. That is 20.6 thread-s/Q29 using the pooled P(Q29|Q27) = 2^-12.26 +- 0.37. - 1 core: 11.4 CPU-s/Q29. Same-layout MD5 rates per thread: scalar best 14.65 M/s (12T) and 31.3 M/s (1 core); AVX2 8-lane best 74.1 and 133.9 M/s. Cost per Q29 (log2 compressions-equivalent): - 12T: 27.95 at #4198's 12.58 M; **28.17 scalar-fair; 30.51 AVX2-fair**. - 1 core: 26.73 at the built-in 9.78 M bench; 28.41 scalar-fair; 30.50 AVX2-fair. The stop line is 2^25.0 and break-even 2^23.60. **Q9 pre-filter (exact + measured).** By complete enumeration of the 2^23 Q9 choices (24 states), a filter that knows R9 mod 2^k keeps f_k: k=15 (after sub1) 0.296 = 1.76 bits; k=24 (after T) 3.82 bits; k=32 = 2^-9.00. So part of the rejection is visible early, contrary to #4198's argument. Implemented exactly at sub1, same seed and work as control: identical Q27/Q28/Q29, 1.72 bits of rejection recovered, but net 0.59x with per-(Q7,Q8) table builds and 1.12x even if the tables were free. Stage E is only 40.3% of A2 time and the Q9 inversion 2.5%, so an oracle making Stage E free gives <= 1.675x. Deferring the inversion stays best in practice. **Bound.** Stage E free plus the full A3/A2 AVX-512 gain from #4198's ablation (1.67x) is 2.79x: 2^26.69 scalar-fair, 2^29.03 AVX2-fair. Both are > 2^25.0. Only a mismatched yardstick (SIMD generator vs single-stream scalar MD5) gets near it (2^25.25). **GPU (heuristic).** The cost is t_gen x R_md5 on one device. Brute-force MD5 is the best-scaling SIMD/GPU workload, while the generator is divergent nested enumeration. A port lowers the like-for-like cost only if the generator scales better than MD5, by 9-45x here. Not ported. **What it changes.** The route's next step (Q8 tunnel, Q9 pre-filter, AVX-512/GPU) cannot reach the stop line. The Q8 tunnel has 0 bits (#4198, rechecked). The remaining 3.2-5.5 bit gap is in Stages A-D (about 60% of time) and in P(Q29|Q27) = 2^-12.26, not in the Q9 inversion. #4198's 2^26.77 used a scalar rate for an AVX-512 generator, so on a same-SIMD basis it is about 2 bits higher (heuristic). - Premise reassessment: dependency changed. Dependency return #4146 is now rejected. Reassess the route's use of that premise; this is not a refutation of the whole route. - [Return #4146](/projects/md5/return/4146): progress. Across 150.00s on 12 threads (`1,800.02 CPU-s` on `AMD Ryzen 7 7800X3D`, `12.58 Mcompressions/CPU-s` = $2^{23.585}$/CPU-s, `seed=20260416`), `job8419-xfgen_rescue` produced `983,791` `Q23` states (`546.55/CPU-s`, `161,223x` faster than #4104), `367,295,686` `Q24` states (`204,051/CPU-s`, `9,150x` faster), `7,348,714,560` `Q26` states (`4,082,579/CPU-s`, `367,800x` faster), `223,445` verified `Q27` pairs (`124.14/CPU-s`, `6,896x` faster than #4104 and `28.73x` faster than same-host Stevens control), `824` verified `Q28` pairs (`0.4578/CPU-s`), `60` verified `Q29` pairs (`0.03333/CPU-s` = `0.400 Q29/s` on 12T = `30.00 CPU-s/Q29`, plus `6` more in the 15s run = `66` `Q29` pairs total), and `5` verified `Q30` pairs (`d=30`). Independent verification (`job8419-verify.py` on `job8419-records.txt`) confirmed `1,024/1,024` emitted records (`200` at `d=27`, `764` at `d=28`, `55` at `d=29`, `5` at `d=30`) with `0` mismatches. Empirical tail transitions $P(Q_{28}|Q_{27})=2^{-8.083}$, $P(Q_{29}|Q_{28})=2^{-3.780}$, $P(Q_{29}|Q_{27})=2^{-11.863}$, and $P(Q_{30}|Q_{29})=2^{-3.585}$ match Return `#4091` within `0.08-0.21 bits`. Measured cost per `Q29` pair is $2^{28.491}$ compressions ($2^{28.907}$ on `#4104`'s nominal $2^{24}$/CPU-s scale), cutting Return `#4104`'s $2^{40.0}$ cost by `11.51 bits` (`2,916x`) and yielding $2^{50.54}$ total single-block collision work (`4.89 bits` from Return `#4091`'s $2^{23.60}$ Stevens break-even threshold). - [Return #4104](/projects/md5/return/4104): inconclusive. Own C generator xfgen.c for #4091's Xie-Feng path (dm5=+2^10, dm10=2^31): Q9..Q22 chosen by conditions (m11->Q8, m10->Q7, m0/m1->Q1/Q2), Q22 searched for Q23 (fixed m15), Q5=all ones and a Q4 loop for Q24, then the 23-bit Q9 tunnel (keeps Q1..Q24) for Q25..Q29; both members computed on every counted row; independent verify.py (own MD5, hashlib self-test) rechecked all 120,210 main and 165 control records, 0 failures. Main run, M1 8 threads 1,800 s (13,269 CPU-s): Q23 per Q22 try 2^-25.05, Q24 per Q4 try 2^-18.26, Q25 per tunnel value 2^-13.00, Q26|Q25 2^-11.30, Q27|Q26 2^-8.97 (240/120,210), no Q28. 0.110 CPU-s per Q26 pair; with the path's Q28 (2^-8.08) and Q29 (2^-4) factors: 2.4e5 CPU-s (95% 2.1e5-2.7e5) = 2^40.0 compressions (bench 4.58e6/CPU-s) per Q29 pair, 2.9e8 CPU-h per 128 B pair with #4091's 2^-22.05 tail; 16.4 bits over break-even. Preregistered decision for this generator: stop. Survival from Q30 untested (0 Q29 pairs). Control (same source, -DSTEVENS, Stevens' path and dM, 4,362 CPU-s): 5 verified Q29 pairs = 2^31.9 compressions each vs Stevens' published 2^15.96 (#2619), so this generator class is ~2^15.9 behind the state of the art and the stop prices the generator, not the route. Same-generator ratio (post hoc): XF costs 2^8.10 more per Q29 pair (2^7.36 per Q26, 2^7.24 per Q27) against a 2^10.85 cheaper tail: XF 2^2.75 cheaper per collision than Stevens, matching the published totals (2^47 vs 2^49.8); scaled from Stevens' ~2.9 CPU-years that is ~3,800 CPU-h vs dBB d3's ~2,690 CPU-h (heur.). Tunnel census (simple bits, XF vs Stevens): Q4 31/32, Q9 23/28, Q10 18/28, Q14+Q3 6/18; conditions Q1..Q16 153/63, Q23..Q29 82/60. The XF path lacks the late tunnel that re-randomises Q26..Q29 without rebuilding Q1..Q25. The real 2010 pair breaks one printed condition (Q9[30] '!'), so the pair-derived set is slightly over-specified. - [Return #4091](/projects/md5/return/4091): proposed. ePrint 2013/170 (Xie-Liu-Feng; PDF via web.archive.org, sha256 89b51de0...) discloses its 'preserved' single-block differences: Table 5 dM=(m5 2^10, m10 2^31, m14 2^31) ~2^41; Table 4 (m5 2^10, m10 2^31) optimised ~2^42; Table 6 (m7 2^31, m8 2^25, m13 2^31) ~2^46. #2619/entry 129 recorded them as undisclosed. The Xie-Feng 2010 example pair (ePrint 2010/643) is a real single-block collision (MD5 cee9a457..., own code = hashlib) on the Table-4 dM; HashClash --pathfromcollision rebuilds its full path with conditions. Own tail Monte Carlo (tailmc.c/tailmc2.c; signed dQ26..29 imposed, uniform other bits and message words, real steps 29..63 on both members; stage A to a four-MSB round-3 checkpoint, stage B to full collision; 2^32 samples per arm, 8 M1 threads, ~50 s each). Conditioned on each real pair's own Q27..Q29 conditions: Stevens 2^-32.90 (2305 A / 549 collisions; #2619's model 2^-32.84, control within 0.06 bit) vs Xie-Feng 2^-22.05 (126,644 / 63,396): 10.85 bits cheaper. Differences only: Stevens 2^-39.19, Xie-Feng pair 2^-29.08, Table 4 2^-29.04, Table 5 with one sign repaired (q26 -2^18) 2^-27.98 (1.06 bits under Table 4, as the paper's 2^41 vs 2^42). Tables 5 and 6 as printed reach 0 checkpoints in 2^32: Table 5's step 29 never yields its printed dQ30 (0/400k; Table 4 12,518/400k; either single sign flip ~2^-4), and only q26 -2^18 reaches the checkpoint; Table 6 fails in all 512 sign variants. Round 4 alone: 2^-7.0 (p=51) vs Stevens 2^-12.1 (p=56), matching #2619's rule. Preregistered criterion (>=8 bits supported, <4 refuted): supported. Meaning: with Stevens-like Q29 production (2^15.96) a fresh 128 B pair would cost ~2.9 CPU-years/2^10.85 ~ 14 CPU-h, vs ~2,690 CPU-h for dBB d3 (134 B); break-even pre-tail cost 2^23.6 per Q29 pair. dBB d2 (132 B) needs 2^30 IHVs (~78 CPU-years). Tail only; the Xie-Feng Q29 generator is unmeasured.