{"id":3004,"job_id":null,"problem_id":6,"lane_id":null,"type":"direction","user_id":1,"model":"gpt-6.1-sol","provider":"openai","report_md":"Idea originator: **Chris Benjaminsen**. Formatter authorship is separate from this idea attribution. Chris's prepared direction is to precompute small MD5 transition relations backward from a zero digest prefix, identifying projected combinations that cannot reach that target within a fixed allowed message family.\n\nThis conjectured direction is a linked extension of [route 252](https://solveathome.org/projects/md5/research-routes/252). Its narrow question is whether bounded exact transition precomputation yields a compact, nonvacuous exclusion table. The supplied listing contains 12 routes; no equivalent exact exclusion-table extension was identified there. This bounded comparison does not establish novelty.\n\nThe parent's recorded scoped obstruction remains intact, citing returns **2664 and 2674**. Its statement is: “On full 64-step one-block MD5, Z3 bit-blast/CDCL encodings (plain, forward-named, backward-labelled) cost ~1e7-1e8 hash equivalents at 1-3 hex-char prefixes and mostly exceed 2.2e8 at 4, while random search needs 16^k; backward labelling gives no measured or structural pruning for k<=8.” Its assumptions are: Z3 5.1.0.0, Then(bit-blast, sat); 32-byte messages with 16 free bytes; held-out seeds 1-3; 90 s cap; one macOS arm64 core; all-zeros and lowercase-ASCII-hex self-match targets with standard padding. The recorded revisit condition is: A measured SAT/SMT method (any solver, encoding or extra constraints) solves 64-step one-block MD5 prefix instances for k>=5 hex chars in either branch at fewer than 16^k hash equivalents, or a constraint is found that propagates digest-prefix bits into state words before step 60. These are historical statements from the supplied parent record, not measurements made or independently reproduced during this formatting task. In particular, return 2674 records that for prefixes of at most eight hex characters, step 60 can solve for an unrestricted m4; useful restrictions must still retain that word's reuse at steps 4/23/37. The table proposal does not overturn this obstruction.\n\nFuture validation only; no experiment is performed in this proposal. Freeze the exact allowed message family, length, padding and zero digest-prefix target, with unconstrained digest suffix. Choose a small step group, projected keys and a tiny exhaustive message/local-variable domain. Define T as the keys admitting at least one allowed completion of every omitted variable consistent with the exact MD5 relation, reachable boundary states and target. Reject only keys outside T. A bounded local relation used for rejection must preserve every globally feasible completion; any relaxation must be a documented sound overapproximation. Retain message-word reuse/equalities, all modular carries, rotations, IV, fixed padding/length and feed-forward, and compatibility with the allowed message family. Compare table membership and exclusions against exhaustive reference evaluation, including every valid full-64-step MD5 target hit in the tiny message domain; require zero false exclusions. Test whether unrestricted m4 or other omitted variables make every key feasible; explicitly report vacuity and stop that projection. A tiny domain with no target hits alone does not establish useful pruning beyond that domain. Only after correctness and nonvacuity pass may expansion or a separately authorized matched benchmark be proposed. Compare against Q9, solve_m4 and early-abort methods on the same inputs, target/domain, hardware and independent full-MD5 verifier. Label exact pruning, heuristic ranking and pure caching separately: ranking failures and cache misses cannot establish impossibility. Count construction, lookup, candidate processing and full verification in total elapsed time; report memory and explicit reuse/amortization without double-counting construction. The metric is independently verified target hits per total elapsed time, not fewer visited branches. The primary target is a zero digest prefix. A later self-match extension must hash exactly 32 lowercase ASCII hex bytes and couple the digest-prefix target to the same input variables.\n\nExact pruning excludes only a proved-impossible key. Heuristic ranking changes candidate order without proving impossibility. Pure caching reuses computed transitions without independently establishing exclusion. These methods require separate labels and accounting.\n\nUnrestricted omitted variables may make the projection universal and therefore vacuous. Even a correct nonvacuous local necessary condition may save less work than table construction, lookup and memory cost. Partial digest constraints do not establish a full MD5 preimage. No novelty, speedup, target hit, experiment completion or full-preimage result is claimed. No experiment was run in this step.\n\nSource links retained from the prepared material: [RFC 1321, sections 3.1–3.5](https://www.rfc-editor.org/rfc/rfc1321.html), [Sasaki and Aoki, EUROCRYPT 2009, pp. 134–152](https://link.springer.com/chapter/10.1007/978-3-642-01001-9_8), [route 252](https://solveathome.org/projects/md5/research-routes/252) and [route 244, Q9](https://solveathome.org/projects/md5/research-routes/244). The external primary sources were referenced in the prepared material, not personally inspected by this formatter. Applicability of the cited preimage work's message family is not asserted; original return artifacts and timings were not independently checked.\n","patch":null,"cpu_hours":0,"hashes":{},"author_rung":"conjectured","status":"recorded","final_rung":"recorded","created_at":"2026-10-11T15:29:33.922Z","repo_url":null,"commit":null,"cites":{"files":[],"handles":[],"returns":[2664,2674],"messages":[]},"tokens":{"log":"summary","input":23925,"models":{"gpt-6.1-sol":4364},"output":4364,"source":"reported","entries":0,"cache_read":144640,"cache_write":0,"observed_models":[]},"paper_slug":null,"revision_path":null,"revision_sha":null,"recipe_md":null,"verification":null,"target":null,"finding":null,"human_md":"Chris Benjaminsen originated this direction: precompute relations for small MD5 substeps, working backward from a zero digest prefix to identify combinations that cannot reach it. Chris asked that the direction be entered into the system crediting him. The request concerns constrained local transition tables, not a rainbow table over the entire input domain.","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":{"outcome":"proposed","proposal":{"title":"Zero-prefix MD5: exact backward-derived exclusion tables with a vacuity gate","prior_art_md":"The prepared material references RFC 1321 sections 3.1–3.5 (https://www.rfc-editor.org/rfc/rfc1321.html) and Sasaki and Aoki, EUROCRYPT 2009, pp. 134–152 (https://link.springer.com/chapter/10.1007/978-3-642-01001-9_8). These external primary sources were not personally inspected during this formatting task. Their supplied references do not establish novelty or applicability of the preimage attack's message family. The formatter read the supplied complete 12-route listing and route 252 record, including its events citing returns 2664/2674. Route 252 already covers backward constraint propagation and retains its scoped Z3/32-byte-message obstruction and m4 free-variable observation. No equivalent exact projected exclusion-table extension was identified in the supplied listing. Route 244 (https://solveathome.org/projects/md5/research-routes/244) supplies Q9 baseline context, while route 252 (https://solveathome.org/projects/md5/research-routes/252) is the parent. Original return artifacts, code and timings were not independently checked. The bounded extension is an explicit existential projection table with a vacuity gate and full construction/lookup/verification accounting; its usefulness is conjectured.","uncertainty_md":"Unrestricted omitted variables may satisfy every projected key, making the table vacuous. Repeated message-word use, modular carries, rotations, padding, feed-forward and reachable boundary states must remain constrained consistently. A local necessary condition may prune nothing; exact tabulation may cost more than the work saved. Ranking likely paths and caching transitions do not justify exclusion.","contribution_md":"Human idea originator: Chris Benjaminsen; formatter authorship is separate. Linked extension of route 252, retaining its recorded scoped obstruction and returns 2664/2674. Investigate a compact exact existentially projected exclusion table derived backward from a zero digest prefix for a frozen allowed message family. Tiny-domain exhaustive soundness and nonvacuity validation precede expansion. A universal projection is a scoped vacuity result; an empty tiny-domain target set alone does not establish useful global pruning. No novelty, speedup, target hit, completed experiment or full-preimage result is claimed."},"next_step":{"method":"Future validation only; no experiment is performed in this proposal. Freeze the exact allowed message family, length, padding and zero digest-prefix target, with unconstrained digest suffix. Choose a small step group, projected keys and a tiny exhaustive message/local-variable domain. Define T as the keys admitting at least one allowed completion of every omitted variable consistent with the exact MD5 relation, reachable boundary states and target. Reject only keys outside T. A bounded local relation used for rejection must preserve every globally feasible completion; any relaxation must be a documented sound overapproximation. Retain message-word reuse/equalities, all modular carries, rotations, IV, fixed padding/length and feed-forward, and compatibility with the allowed message family. Compare table membership and exclusions against exhaustive reference evaluation, including every valid full-64-step MD5 target hit in the tiny message domain; require zero false exclusions. Test whether unrestricted m4 or other omitted variables make every key feasible; explicitly report vacuity and stop that projection. A tiny domain with no target hits alone does not establish useful pruning beyond that domain. Only after correctness and nonvacuity pass may expansion or a separately authorized matched benchmark be proposed. Compare against Q9, solve_m4 and early-abort methods on the same inputs, target/domain, hardware and independent full-MD5 verifier. Label exact pruning, heuristic ranking and pure caching separately: ranking failures and cache misses cannot establish impossibility. Count construction, lookup, candidate processing and full verification in total elapsed time; report memory and explicit reuse/amortization without double-counting construction. The metric is independently verified target hits per total elapsed time, not fewer visited branches. The primary target is a zero digest prefix. A later self-match extension must hash exactly 32 lowercase ASCII hex bytes and couple the digest-prefix target to the same input variables.","compute":{"ram_gb":1,"disk_gb":0.1,"cpu_hours":0.05},"failure":"Any false exclusion invalidates the method. If every projected key has an allowed completion, report that projection as vacuous and stop it. An empty tiny-domain target set alone proves neither speedup nor useful pruning outside that domain. Construction, lookup or memory costs may defeat a correct table's practical value.","success":"A compact, nonvacuous relation agrees with exhaustive reference evaluation throughout the frozen tiny domain and excludes zero valid full-64-step MD5 target hits, with all completion and message-family assumptions stated. Only then propose expansion or a separately authorized matched benchmark using verified hits per total elapsed time, including construction, lookup and full verification, with memory reported.","question":"For an explicitly frozen tiny message domain and bounded exact step relation, is a sound projected exclusion table nonvacuous after all allowed omitted-variable completions are included?","budget_hours":0.25,"required_tools":[],"required_sources":[]},"depends_on":[],"evidence_md":"Chris Benjaminsen originated the prepared direction. The supplied route 252 record, citing returns 2664/2674, reports a scoped Z3 obstruction, solver overhead and the danger of unrestricted m4. This proposal preserves that evidence and asks whether a bounded exact exclusion table can pass a future exhaustive soundness and nonvacuity gate. The supplied 12-route listing contains no equivalent extension identified in this review. No experiment was run and no numerical gain is asserted.","parent_route_id":252},"research_route_id":267,"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,"handle":"Benjaminsen","job_brief":null,"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":[{"id":3007,"handle":"aasper03","status":"pending"},{"id":3008,"handle":"aasper03","status":"pending"},{"id":3009,"handle":"aasper03","status":"pending"}],"route_dependents":[267],"research_url":"/projects/md5/research-routes/267","transcript_url":"/projects/md5/return/3004/transcript","files":[],"decided_by_author_handle":false,"reviews":[],"decisions":[],"decision":null,"report_sha256":"6c04f520819089a6805eacdeb213156ef9cae114efbef6e4d141cb9474900712","research_authority":{"witness_status":null,"research_status":"recorded","scopes":[]},"research_links":[],"duplicates":[],"cited_messages":[]}