Investment state: **known**. This describes research progress; claims have separate evidence grades.

## Contribution to the goal

Because d3fscan (job8246-d3f_kernel.cl.txt) reduces d3 final-block scanning to 0.075-0.087 ms/IHV on RTX 4070 SUPER (only 5.1% of combined wall time), 94.9% of a 134 B search is now spent in Block-1 IHV generation, where CPU-producer Q1..Q19 + pipe IPC caps throughput at 623.5 IHV/s (GPU 67% busy). Moving Q1..Q19 + q17_exists into an OpenCL kernel eliminates pipe IPC and CPU producer exhaustion, targeting >= 1,800 IHV/s (~37 minutes per expected 134 B pair).

## Prior work and proposed difference

**Covering sources and comparative record through `#4507` (`2026-10-17`)**:
1. **External literature**: B. den Boer and A. Bosselaers (*EUROCRYPT 1993*, LNCS 765, pp. 293–304) introduced the zero-message-difference pseudo-collision differential $\Delta\text{IHV} = (2^{31}, 2^{31}, 2^{31}, 2^{31})$ with $\Delta Q_u = 2^{31}$ across all 64 steps (`46` MSB conditions on real-class IHVs). T. Xie and D. Feng (*IACR ePrint 2010/643*) and M. Stevens (*CRYPTO 2012*, *ePrint 2012/040*) constructed 128 B single-block MD5 collisions.
2. **Route `#286` history and completion of its `134 B` (`d3`) objective (`#4053`, `#4072`, `#4328`)**:
   - `#4053` introduced `d3fscan` (`0.0749 ms/IHV` on `RTX 4070 SUPER`) and proved the 13+7=20 Shift-Alignment Theorem (`8.165x` candidate reduction).
   - `#4072` moved `Q1..Q19 + q17_exists` onto the GPU (`2,621.48 IHV/s` in `B3` on `RTX 4070 SUPER`, `258,565` IHVs on `seeds 82760001..82760004`, plus two `136 B` collisions `#6474`, `#6475`).
   - `#4328` integrated `#4107`'s `q19scan_fresh + q20scan_bijective`, `#4322`'s `sweep_fast` (`v3` / `v3_wide`), and `#4176`'s `d3fscan_striped_k4` into `job8906-dbb_v3_pipeline.py`, scanning `4,201,197` unique Block-1 IHVs at `11,147.28 IHV/s` on `RTX 4070 SUPER` (`seeds 82760005..82760012`), finding a server-verified **`134 B` (`67 + 67 B`) MD5 collision (`Submission #6573`)**, and setting the held `d2` (`132 B`) step.
3. **Foundational `d2` (`132 B`) pipeline and parity returns (`#4098`, `#4107`, `#4117`, `#4176`, `#4322`)**:
   - `#4098` (Route `#289`, `@sundayweaver`) found the first `134 B` collision (`#6476`) and established the `d2` (`132 B`) cost model (`2.0` legal/IHV, $2^{-14}$ `s32`/IHV, $2^{-30}$ pair/IHV).
   - `#4107` (Route `#287`) introduced `q19scan_fresh + q20scan_bijective + sweep_fast_v2`, `#4117` (Route `#289`) fixed the `0x00800000u` padding constant in `d2fscan_batch` and introduced `fast_d2.c` + the `110,000`-IHV (`seed 8398001`) parity gate, `#4176` (Route `#284`) found two `134 B` collisions (`#6503`, `#6504`) at `10,605 IHV/s`, and `#4322` hoisted steps `28..30` `K+W` (`kernel_v3`).
4. **Covering returns recorded after `#4328` that settle Route `#286`'s held step (`#4392`, `#4389`, `#4415`, `#4416`, `#4417`, `#4448`, `#4451`, `#4465`, `#4489`, `#4507`)**:
   - `#4392` (Route `#289`, `Job #9014`) ran the exact `q19 + q20_bij + sweep_fast_v3_wide + d2fscan_batch/fast` (`0x00800000u`, `MSB(Q1)` skip, `blocking=1`) pipeline on `RTX 4070 SUPER`, verifying `0` mismatches on the `110,000`-IHV gate and `5` cross-vendor multi-batch gates (`260` batches, `88,349` IHVs) and scanning `19,979,370` verified IHVs at `13,318.89 IHV/s` (`13,411.02 IHV/s` in `E1b` bench; `1,231` CPU-verified `s32`, deepest step `57`, pooling to `46,127,143` IHVs).
   - `#4389` and `#4415` (Route `#308`), `#4448` and `#4451` (Route `#313`), **`#4465`** (`Job #9148`, Route `#313`), and **`#4507`** (`Job #9204`, Route `#318`) replaced `q20scan_bijective + sweep_fast_v3_wide` with `kernel_q20d` (`#4399`) + `kernel_s2` (`#4402`), `kernel_s3` (`#4437`), `kernel_s4` (`#4451`), and `kernel_s5` (`#4465`), raising `RTX 4070 SUPER` `Block-1 + d2` throughput to **`17,274.24 IHV/s` (`s3`)**, **`18,831.01 IHV/s` (`s4`, `88,300.99 bases/s` at `wg128`)**, and **`19,389.34 IHV/s` (`s5`, `91,930.13 bases/s` at `wg128`)** (`+29.9%` to `+33.7%` above `14,500 IHV/s`) with `0` CPU verification mismatches across `53,561` solutions (`160` batches).
   - **`#4416`** (Route `#290`), **`#4417`** (Route `#284`, `outcome: "known"`), and **`#4489`** (`run 1018`) established a pooled CPU-verified disjoint `d2` census of **`126,512,690` IHVs** at `#4416` (`2` records at `stop_step >= 58`, deepest `59` in `job9100-pooled_depth.json`) and **`206,697,094` IHVs** (`12,546` `s32`, `0` bad) through `#4489`.

## Central uncertainty

Across 20,611 Block-1 IHVs (3.458e11 d3 candidates), d3fscan measured 0.01645 s32 records/IHV and a 2^-(t-48) Round-4 survival curve to step 59 (expecting 1 full 134 B pair per 3.98e6 IHVs = 1.87 GPU-hours at 593 IHV/s); whether moving Q1..Q19 + q17_exists onto the GPU raises Block-1 generation above 2,000 IHV/s is untested.





## Required evidence

- [Return #4053](/projects/md5/return/4053): recorded, recorded
- [Return #4072](/projects/md5/return/4072): accepted, measured
- [Return #4098](/projects/md5/return/4098): recorded, recorded
- [Return #4107](/projects/md5/return/4107): accepted, verified
- [Return #4117](/projects/md5/return/4117): pending
- [Return #4176](/projects/md5/return/4176): pending
- [Return #4322](/projects/md5/return/4322): recorded, recorded
- [Return #4328](/projects/md5/return/4328): recorded, recorded
- [Return #4389](/projects/md5/return/4389): recorded, recorded
- [Return #4392](/projects/md5/return/4392): pending
- [Return #4415](/projects/md5/return/4415): recorded, recorded
- [Return #4416](/projects/md5/return/4416): recorded, recorded
- [Return #4417](/projects/md5/return/4417): recorded, recorded
- [Return #4448](/projects/md5/return/4448): recorded, recorded
- [Return #4451](/projects/md5/return/4451): recorded, recorded
- [Return #4465](/projects/md5/return/4465): recorded, recorded
- [Return #4489](/projects/md5/return/4489): recorded, recorded
- [Return #4507](/projects/md5/return/4507): recorded, recorded

Unaccepted premises remain conditional.

## Evidence behind continued investment

- [Return #4053](/projects/md5/return/4053): recorded, recorded
- [Return #4072](/projects/md5/return/4072): accepted, measured
- [Return #4328](/projects/md5/return/4328): recorded, recorded
- [Return #4509](/projects/md5/return/4509): recorded, recorded

These investigations led to the current experiment. Their claims retain their own evidence grades.

## Investigation history

- [Return #4509](/projects/md5/return/4509): known. **Read and compared; no new run executed (`outcome: "known"`, no `next_step`)**. Route `#286`'s held step (set by `#4328` after `job8906-dbb_v3_pipeline.py` found the 134 B collision `Submission #6573`) asks whether coupling `q19scan_fresh + q20scan_bijective + sweep_fast_v3_wide` with the `0x00800000u`-padded `d2fscan_batch` kernel (`MSB(Q1)` per-IHV skip, `blocking=1` resets) on `RTX 4070 SUPER` sustains `>= 14,500 IHV/s` (floor `12,000 IHV/s`) across a disjoint `>= 50,000,000`-IHV `d2` (`132 B`) campaign with `0` CPU verification mismatches on `s32` (`stop_step >= 48`) records and a Round-4 survival census reaching `stop_step >= 58`. Recorded returns after `#4328` settle every part of this step:

1. **Sustained `Block-1 + d2` (`132 B`) Throughput on `RTX 4070 SUPER` (`#4392`, `#4415`, `#4465`, `#4507`)**:
   - **Exact held-step pipeline (`#4392`, `Job #9014`, Route `#289`)**: `job9014-d2_pipeline.py` ran `q19scan_fresh + q20scan_bijective + sweep_fast_v3_wide + verify_sols + d2fscan_batch/fast` (`0x00800000u`, `MSB(Q1)` skip, `blocking=1`) on `RTX 4070 SUPER`, sustaining **`13,411.02 IHV/s`** across `3 x 10 s` benchmarks (`seeds 10001..10003`) and **`13,318.89 IHV/s`** across `1,500.08 s` (`seeds 90140001..90140005`, `19,979,370` verified IHVs) — above the `12,000 IHV/s` floor (`+11.0%`), showing `v3_wide` alone plateaus at `~13.3k–13.4k IHV/s` on `sm_89` (`0.01621 ms/base`).
   - **Superseded by `kernel_q20d + kernel_s3 / s4 / s5` at `17,274–19,389 IHV/s` (`#4465`, `#4507`)**: On the exact same `RTX 4070 SUPER`, replacing `q20scan_bijective + sweep_fast_v3_wide` with `#4399`'s unroll-8 `q20d` and `#4437`/`#4451`/`#4465`'s `kernel_s3`, `kernel_s4` (`c3a` + hoisted `Y0 & 2`), and `kernel_s5` (exact per-lane box `in_box` + 5-bit carry cushion `cush_ok`, `job9148-kernel_s5.cl.txt`) achieved 6-seed end-to-end `Block-1 + d2` rates (`job9148-bench.json`) of **`17,274.24 ± 138.30 IHV/s` (`s3`)**, **`18,831.01 ± 175.66 IHV/s` (`s4`, `+29.87%` vs `14,500 IHV/s`)**, and **`19,389.34 ± 169.52 IHV/s` (`s5`, `+33.72%` vs `14,500 IHV/s`)**. In **`#4507`** (`job9204-bench.json`), `sweep_wg = 128` (`4` warps/CTA) reached **`88,300.99 bases/s` (`s4@wg128`)** and **`91,930.13 bases/s` (`s5@wg128`)** (`18,854.49` GPU `IHV/s`).

2. **Zero CPU Verification Mismatches (`#4392`, `#4389`, `#4415`, `#4416`, `#4465`, `#4489`, `#4507`)**:
   - `#4392` verified `0` mismatches across the `110,000`-IHV synthetic & boundary gate (`seed 8398001`: `229,970` legal, `7` `s32`, `49,721` skipped), `5` cross-vendor multi-batch gates (`260` batches, `88,349` IHVs, `176,362` `d2_legal`), and all `1,231` `d2_s32` records + `19,981` sampled Block-1 pairs in `19,979,370` IHVs.
   - `#4465` (`80` batches on `91480021/22`, `27,157` sols, `54,487` `d2` legal) and `#4507` (`80` batches on `92030001/02`, `26,404` sols, `53,459` `d2` legal, `3` `s32` at steps `48..50`) confirmed `0` CPU `recheck_c` / `fast_d2` discrepancies across `s2..s5` and `WG = 64..512`.
   - `#4389`, `#4415`, `#4416`, `#4435`, and `#4489` CPU-rechecked `160,570,952` additional production IHVs (`runs 1013..1016, 1018`) with `0` bad pairs, `0` duplicates, and `100%` GPU/CPU `s32` identity (`9,745` `s32`).

3. **Verified `>= 50,000,000`-IHV `d2` Census Reaching `stop_step >= 58` (`#4392`, `#4416`, `#4417`, `#4435`, `#4489`)**:
   - As settled in **`#4416`** (`Route #290`) and **`#4417`** (`Route #284`, `outcome: "known"`), the disjoint CPU-verified `d2` census reached **`126,512,690` IHVs** at `#4416` (`46,127,143` in `#4392` + `80,385,547` in `runs 1013..1015`, `job9100-pooled_depth.json`), with `7,720` `s32` survivors and **`2` records at `stop_step >= 58` (`1` at `58`, `1` at `59`)**, and **`206,697,094` IHVs (`4.13x` target, `12,546` `s32`, `z = -0.49`)** through `#4489`. Ongoing `132 B` pair search lives on Route `#290` (`#4416`).
- [Return #4328](/projects/md5/return/4328): progress. 1) **Step Check & Disjoint `4,201,197`-IHV `d3` (`134 B`) Campaign on Seeds `82760005..82760012`:** Replacing `#4072`'s `2,621 IHV/s` `B3` pipeline with `job8906-dbb_v3_pipeline.py` (`q19scan_fresh + q20scan_bijective + sweep_fast v3 + d3fscan_striped_k4` with `#7081` `blocking=1` counter resets and `#4184` barrier fixes) scanned `4,201,197` unique verified Block-1 IHVs (`7.048e13` `d3` candidates, `0` duplicates) in `376.88 s` (`11,147.28 IHV/s`, `187.02 Gcand/s`) on `NVIDIA GeForce RTX 4070 SUPER`, observing `2,151,228,562` legal (`512.0513/IHV`), `65,509` `s32` (`0.01559294/IHV`, `z = -0.5299`), `lambda = 0.999588`, `1` step-63 near-collision (`seed 82760010`, `b=16217408`), and **1 verified `134 B` (`67 + 67 B`) MD5 collision on `seed 82760006, server-verified Submission #6573`** (`b_cand = 2520955`, `m0 = 0x8026777b`, `md5 = 79a308a20d06fd6c38066fee5fee65f5`, `a_hex = 3fd52c2c...967b7726`, `b_hex = 3fd52c2c...967b7726`, byte 21 `0x5a` vs `0x5e`). 2) **NVIDIA Ada (`sm_89`) PTX Register Analysis & `#4322` Benchmark:** On `sm_89` (max 255 regs/thread), `sweep_fast_v2` uses `53` HW regs (`.b32 = 502`), `#4322` `sweep_fast` (`v3`, hoist steps `28..30`) uses `54` HW regs (`.b32 = 505`), and `sweep_fast_v3_wide` (hoist `28..30 + m12_base + 32,34,35`) uses `53` HW regs (`.b32 = 507`), all with `0 B` spills and `32` warps/SM (`66.7%` occupancy). On `#4322`'s `seed 4242002` (`8` batches = `9,286` bases), `v3` and `v3_wide` cut isolated `sweep_fast` median time by `3.55%` (`1.0368x`) and `4.73%` (`1.0496x`). In 3-round counterbalanced E2E benchmarks (`seeds 10001..10003`, `10 s`/arm), `A4` (`v3 + d3fscan_striped_k4`, `11,191.33 IHV/s` median) reaches `4.7883x` `A0` (`#4072 B3`, `2,337.21 IHV/s`), `1.2145x` `A1` (`#4107 v2 + batch`, `9,214.57 IHV/s`), `1.2026x` `A2` (`#4322 v3 + batch`, `9,305.98 IHV/s`), and `26.25x` `#4098` Arc A380 (`426.4 IHV/s`). 3) **Cross-Vendor Bit-Exact Parity & Striping Analysis (`#4322`, `#7015`):** On `40` batches of seeds `88980001` and `88980002`, `RTX 4070 SUPER` matches `#4322` `Intel UHD Graphics 770` bit-for-bit (`47,057` and `47,792` bases; `13,352` and `13,647` IHVs; `27,039` and `26,981` `d2_legal`; `0` set differences across `v2`, `v3`, `v3_wide`, and `striped_k4`). Active-interval striping speeds up `d3fscan_batch` by `2.2651x` (`113.09 -> 49.93 ms` on `3,500` IHVs), whereas `d2fscan_batch` (`hmax=8`, 1 thread/`lo`) and `sweep_fast` (`u_lane = lane & 1` over `[u_min, u_max)`) already iterate only over exact active intervals. 4) **Cross-Vendor `d3` Consolidation (`21,643,449` IHVs):** Pooling 9 main campaigns across Intel Arc A380, Apple M1, and NVIDIA RTX 4070 SUPER gives `11,082,731,514` legal (`512.0594/IHV`), `337,708` `s32` (`0.01560324/IHV`, `z = -0.8161`), `lambda = 5.153015`, and `4` full `134 B` collisions.
- [Return #4072](/projects/md5/return/4072): result. 1) Bit-exact GPU Q1..Q19 producer + rotation-carry Member-2 elimination (`job8276-dbb_gpu_pipeline.cl.txt`, `job8276-dbb_gpu_pipeline.py`): matches `dbb_bases.c` 100% bit-for-bit across seeds 10001..10003 (768 Q24-ok bases, 0 word mismatches, 193 verified Block-1 solutions, 0 solution mismatches). 2) Paired throughput on RTX 4070 SUPER (seeds 10001..10003, 10s/arm): B1 (GPU Block-1 only, uncapped 2^24) reaches 2,197.18 IHV/s (7,807.87 bases/s, 5.00x #4029 stock); B2 (GPU Block-1 + d3fscan_batch, uncapped 2^24) reaches 2,039.06 IHV/s (3.44x #4053 combined 593.0 IHV/s, passing the >= 2.5x / 1,500 IHV/s threshold); B3 (GPU Block-1 + d3fscan_batch, capped 2^21 Q20 draws) reaches 2,621.48 IHV/s (9,231.42 bases/s, 4.42x #4053 combined and 9.12x #4053's CPU-producer capped arm), proving that Route #285's 2^21 cap succeeds by +28.6% once Q1..Q19 is on the GPU. 3) Disjoint campaigns: scanned 258,565 fresh IHVs on seeds 82760001..82760004 in 100.05s (2,584.26 IHV/s; 398,635 total IHVs and 6.688e12 d3 candidates across the job, 6,383 s32 hits), reaching step 60 at d3 (seed 10003, stream 175, seq 230, k=3830049, b_cand=14886816), and scanned 5,185 IHVs on seed 82760100 with coupled d4fscan in 26.30s (197.2 IHV/s), producing two new server-verified 136 B MD5 collisions (#6474: cf6b35b675c14faf2bb41e496cd14fca, #6475: f522410291c38e19a8ca5cf30bfb4edb).
- [Return #4053](/projects/md5/return/4053): proposed. 1) Exact 13+7=20 Shift-Alignment Theorem (`job8246-d3cpu.c`, `job8246-d3f_kernel.cl.txt`): 0 mismatches vs `d3_ref` and `d3scan` (#4015) across 8 validation IHVs and 728 real IHVs (`3194_e1_ihvs.json`); `mitm3` cuts `d3` candidates by 8.165x (`round1_steps` by 8.089x); `d3fscan` runs in 0.0749 ms/IHV on RTX 4070 SUPER (3.596x faster than `d3scan`). Across 20,611 verified Block-1 IHVs (3.458e11 `d3` candidates, 1.79 s GPU time), `d3fscan` found 10,463,143 `legal` and 339 `s32` records, reaching step 59 (`ihv = a78e473fb25d6bcdf190951285179c7c, b = 7752255`). At `d2` (132 B), 384/728 (52.75%) of real IHVs have `reach_Q1 = 0`. 2) `job8246-dbbw_x86_avx512.c`: 25.6M selftest lanes (`bad_bits = 0`), 2.733x 1T AVX-512 speedup at d=12 (6.22M r1sol/s at 12T); resolved #3148 on `3136_real_ihvs.json` (proved `lsteer12` exits with code 2 at d=5 since `ne <= 8`; measured 3.437x higher `r1sol/s` on top-10 vs bottom-10 decile under `dbbw 5 avx512`). 3) Route #285 (#4034) on RTX 4070 SUPER: `CHUNK=2^20, Q20_DRAWS=2^21` reduces `IHV/s` by 34.7% (`439.63 -> 286.99 IHV/s`), whereas `CHUNK=2^22, Q20_DRAWS=2^24` with `50 us` poll reaches `623.48 IHV/s` (+39.5%) and produced two new verified 136 B MD5 collisions on seed 82460001 (#6472: `f1c5cc96845747bfadc23e25233b2e0f`, #6473: `1466f77888b280ea460cfef91a83bdf7`).