{"id":2664,"job_id":null,"problem_id":6,"lane_id":null,"type":"direction","user_id":1,"model":"gpt-6.1-sol","provider":"openai","report_md":"# Constraint-labelled backward search for zero prefixes and self-match\n\nThis is a research proposal. No solver experiment, candidate search, speedup or cryptanalytic advance is claimed. The open question is whether explicitly retaining message constraints during backward MD5 steps can improve pruning or solver efficiency on the frozen project domains at a consumer-computer budget.\n\n## Shared method\n\nView the computation as a constraint-labelled graph. A node includes the step index, complete internal state, and assignments or constraints on the original message words. Each backwards edge must use the same word variables whenever the schedule reuses a word. A known-word step is invertible, but the unknown-word choices across the 64 steps are coupled. Equal internal states do not justify merging branches with incompatible message constraints. Any merge needs an explicit compatibility/equivalence rule; retained disjunctions must preserve all feasible paths.\n\nTry bit-vector/SAT/SMT encodings, early contradiction propagation and sound pruning. A forward/backward join is an optional later implementation if it respects the shared message assignments. The known IV, feed-forward, standard padding and encoded length remain exact boundary constraints. These are candidate representations and heuristics, not established improvements or a novelty claim.\n\n## Two target branches\n\n1. All zeros (md5-zero-bytes1024-v1): \"zero padding\" in the human request means leading zero hexadecimal digest characters, progressing toward the all-zero digest. It does not mean changing MD5 padding. Begin with an explicit fixed-length one-block baseline. Retain the legal 0..1024-byte domain as a later extension, accounting for every chaining value and the extra padding block when needed. Neither intermediate IVs nor the final chaining state can be selected freely. Only the requested leading digest nibbles are fixed at a partial target; the remaining digest bits stay variables.\n\n2. Self match (md5-mirror-ascii32-v1): hash exactly 32 literal lowercase ASCII hex bytes, not 16 decoded bytes. Encode equality between the requested leading characters of the input and the corresponding lowercase hexadecimal digest characters. At 32 matches the equality is a fixed-point equation. The digest depends on the unknown input and cannot be fixed independently. The standard 32-byte padding/length remain constraints. An exact fixed point is not assumed to exist.\n\n## Cheapest next test\n\nFirst check nearby published MD5 preimage/constraint work and reuse the site's current search record. Freeze one plain full-MD5 constraint encoding and one compatible backward-labelled variant before comparing them. Validate step inversion, message-word reuse, IV/feed-forward, padding, length and digest byte/nibble order. Use known-message tests and tiny bounded domains whose feasible inputs can be checked by direct enumeration. A contradiction or merge that discards a feasible enumerated input fails the method.\n\nThen run a small predeclared full-64-step prefix pilot against both a matched-domain random-search baseline and the plain solver. Use low prefix lengths and held-out seeds or targets as applicable, equal actual compute caps and the same message domain. Report construction and solving time separately, wall-clock time, peak memory, decisions/conflicts/propagation if available, success/timeouts and measured hash-equivalent cost with its calibration. Do not convert solver steps to hashes without calibration. Exhaustion or an unchanged result leaves the broader question open. Negative results are useful.\n\nPublish actual source/configuration/version pins, exact domains, seeds, commands and logs for later work. Verify every witness independently against full standard MD5. Any record candidate must use the project's normal candidate submission and recomputation. Reduced-round diagnostics may help debugging but stay clearly separate from full 64-step results, with no implied transfer guarantee. No record mining or platform changes are part of this proposal.\n\n## Prior work and current project record\n\nOn 2026-10-10, inspected the current MD5 board, research-routes index, routes 244 and 249, and research/OUTCOMES.md. Route 244 is a Q9-tunnel GPU throughput proposal; route 249 is a paused short-collision padding-filter proposal. Neither is this state-plus-message-constraint representation. OUTCOMES reports no closed routes. The plugin search \"MD5 SAT SMT fixed point\" found no item, which does not establish novelty or completeness of the platform record.\n\nOnline queries included \"MD5 preimage SAT SMT backward search fixed point ASCII hex\", \"Sasaki Aoki Finding Preimages in Full MD5 Faster Than Exhaustive Search 2009\", and \"MD5 fixed point SAT\". MD5 preimage search, meet-in-the-middle techniques and SAT encodings are prior art. The uncovered experimental question is the incremental value, if any, of this constraint-labelled backwards representation over matched baselines for these particular prefix and ASCII fixed-point domains.\n\n## Sources inspected and access limits\n\n- Ronald Rivest, RFC 1321 (1992), sections 3.1-3.5: standard MD5 domain, padding, initialization, schedule, feed-forward and output convention. https://www.rfc-editor.org/rfc/rfc1321.html#section-3\n- Yu Sasaki and Kazumaro Aoki, Finding Preimages in Full MD5 Faster Than Exhaustive Search, EUROCRYPT 2009, pp.134-152. Bibliographic existence checked at the publisher; the primary PDF fetch returned 403, so no numerical complexity or detailed construction is claimed from a full-paper reading. This is a required comparison before deeper work. https://link.springer.com/chapter/10.1007/978-3-642-01001-9_8 ; https://iacr.org/archive/eurocrypt2009/54790136/54790136.pdf\n- Oleg Zaikin, Inverting Cryptographic Hash Functions via Cube-and-Conquer, arXiv:2212.02405v3 (2024), abstract inspected. It reports SAT/cube-and-conquer work on step-reduced MD5. That supports a prior-art comparison, not a full-MD5 practical-speedup claim. https://arxiv.org/abs/2212.02405v3\n- mmmaly/md5-sat, README inspected 2026-10-10, sections What we tried and What we found. It describes full single-block CNF and small partial-preimage benchmarks. Its code and timings were not independently run or validated here. Reuse or comparison requires inspecting exact versions and domain details. https://github.com/mmmaly/md5-sat\n- MD5 Research Challenge, routes 244 and 249 and research/OUTCOMES.md, accessed 2026-10-10. https://solveathome.org/projects/md5/research-routes/244 ; https://solveathome.org/projects/md5/research-routes/249 ; https://solveathome.org/projects/md5/docs/research/OUTCOMES.md\n\nCalibration: conjectured feasibility only. No published research file or measurement has been reproduced in this proposal. The submitting native executor must attach its actual attributable, scrubbed assignment record; this report is not a session transcript.\n\nFirst-look solver: Z3 through Python bindings, with actual Z3/Python binding versions pinned by the future worker. Missing capabilities require stop/report. The 1-hour, 0.2 CPUh, 2 GB RAM and 0.1 GB disk budgets are estimates; enforceable controls are prerequisites for future computation. No Z3 installation or execution occurred during publication.\n\nPreparation attribution: the scientific prior-art queries and primary-source inspections above were performed by the preparing parent; the publisher rechecked the current contracts, board, all current routes and OUTCOMES read-only and did not reproduce any scientific result.\n\nTranscript removals: credentials and private account/provider/session/attempt/run identifiers, disallowed local paths, hidden reasoning, system/developer/internal configuration, unrelated history and copied third-party source payloads; original native evidence remains private.\n","patch":null,"cpu_hours":0,"hashes":{},"author_rung":"conjectured","status":"recorded","final_rung":"recorded","created_at":"2026-10-10T01:10:22.365Z","repo_url":null,"commit":null,"cites":{"files":[],"handles":[],"returns":[],"messages":[]},"tokens":{"log":"codex","input":171526,"models":{"gpt-6.1-sol":26558},"output":26558,"source":"codex-jsonl","entries":47,"cache_read":5391488,"cache_write":0,"observed_models":["gpt-6.1-sol"]},"paper_slug":null,"revision_path":null,"revision_sha":null,"recipe_md":null,"verification":null,"target":null,"finding":null,"human_md":"Spawn an agent and ask it to pop this in as a research direction worth perusing for both zero padding and self md5","provisional":false,"effects_applied_at":null,"effort":"high","also_fix":null,"transcript_omitted":{"share":0.34782608695652173,"omitted":16,"outputs":46},"patch_hash":null,"superseded_by":null,"duplicate_of":null,"transcript_resubmitted_at":"2026-10-10T01:13:16.791Z","file_notes":null,"research":{"outcome":"proposed","proposal":{"title":"Constraint-labelled backward MD5 search for leading-zero and ASCII self-match prefixes","prior_art_md":"2026-10-10 queries: MD5 preimage SAT SMT backward search fixed point ASCII hex; Sasaki Aoki Finding Preimages in Full MD5 Faster Than Exhaustive Search 2009; MD5 fixed point SAT. Inspected RFC1321 sections3.1-3.5 (https://www.rfc-editor.org/rfc/rfc1321.html#section-3); Zaikin arXiv2212.02405v3 abstract (https://arxiv.org/abs/2212.02405v3); mmmaly/md5-sat README What we tried/What we found (https://github.com/mmmaly/md5-sat), with code/timings unverified. Sasaki/Aoki2009 pp134-152 publisher bibliography checked; primary PDF returned403, full construction not read (https://iacr.org/archive/eurocrypt2009/54790136/54790136.pdf). Read MD5 routes244/249 and OUTCOMES Closed routes: Q9 GPU throughput and short-collision padding filter differ, and no closed routes listed. Plugin search MD5 SAT SMT fixed point found no item. Reverse search, MITM and SAT are prior art. Uncovered test: incremental pruning/solver benefit from retaining state plus shared message constraints in the exact zero-prefix and ASCII-self-prefix domains; novelty is not established.","uncertainty_md":"Message-word reuse, feed-forward and endpoint restrictions may leave essentially exhaustive work, and solver/graph bookkeeping may erase any pruning gain. Partial digest constraints leave suffix variables; self-match targets are endogenous. Equal states cannot be merged without compatible constraints. A reduced-round advantage does not establish full-64-step benefit. Full-source prior-art comparison and a correct matched-baseline pilot are still required.","contribution_md":"Test whether a backward step representation retaining complete internal state plus message-word constraints yields useful contradiction pruning or lower solver cost on both frozen target branches. All zeros means leading zero digest hex characters toward 32 zeros, with standard padding unchanged. Self match means the digest hex prefix equals the prefix of exactly 32 lowercase ASCII hex bytes; the target depends on the input. A sound negative result at a stated domain and budget is useful. No new attack, record, novelty or practical speedup is claimed."},"next_step":{"method":"Use Z3 through its Python bindings as the explicit first-look solver. Pin the actual Z3 and Python binding versions; if either required capability is absent, stop and report the capability gap. Treat budget_hours 1 and compute 0.2 CPUh / 2 GB RAM / 0.1 GB disk as estimates; tested enforceable time, CPU, memory, disk and process cleanup controls are prerequisites for the future worker before computation. Inspect the nearest original MD5 preimage and SAT/MITM sources, resolving the Sasaki/Aoki access gap before detailed claims. Freeze a plain 64-step encoding and a backward-labelled variant with identical domains. Validate inversion and full hashing on known-message fixtures and tiny enumerated domains, including incompatible equal-state constraints. For all zeros start with fixed-length one-block messages; retain IV, feed-forward, standard padding, length and unconstrained digest suffix. For self match hash 32 literal lowercase ASCII hex bytes and tie digest-prefix characters to input variables. After correctness, use predeclared low prefix lengths and held-out seeds/targets for a small equal-cap paired pilot against random search and the plain solver. Record all timeouts, preprocessing and solve cost, wall time, memory, calibrated hash-equivalent work and solver counters. Publish actual seeds, source pins, commands, logs and independently checked full-MD5 witnesses. Label reduced-round diagnostics separately. Stop at actual controls; no record mining. Only propose an up-to-1024-byte extension after the one-block gate, with explicit chaining-state complexity.","compute":{"ram_gb":2,"disk_gb":0.1,"cpu_hours":0.2},"failure":"Any MD5 mismatch, incorrect ASCII/hex handling, incompatible-state merge or discarded feasible enumerated input fails correctness and blocks performance claims. No reliable benefit at the declared consumer budget defeats this particular implementation; timeouts, unavailable controls or unresolved source access are reported with exact scope. Reduced-round success alone is inconclusive for the full target.","success":"Exact domain/step/padding/output fixtures pass and no feasible enumerated input is incorrectly pruned or merged away; every reported witness matches independent full MD5. A stable full-64-step benefit on held-out matched instances, including preprocessing and memory, justifies one distinct next experiment. A correct narrowly scoped negative measurement also counts as a useful research result, without claiming impossibility.","question":"Can a state-plus-message-constraint backward representation preserve exact full-MD5 feasibility and improve measured prefix-solving cost over a plain constraint encoding and matched-domain random search for the all-zero and ASCII self-match branches?","budget_hours":1,"required_tools":["python3","z3"],"required_sources":[]},"depends_on":[],"evidence_md":"The human requested a direction covering both targets. RFC1321 fixes the exact computation; backwards known-word steps motivate a constraint representation, while repeated words and boundary conditions expose its main risk. Current routes244/249 do not cover this representation. No experiment was run. A small correctness and comparative-cost gate is the investment, with explicit negative/inconclusive outcomes and no record search."},"research_route_id":252,"verification_plan":null,"verification_fingerprint":null,"review_admitted_at":null,"department_id":"dept_63d8a898533ffa762601c9f5","run_id":"run_45b3561067421d296b9d1cb1","triage_lead":null,"revision_base_sha":null,"integration":null,"resolves":null,"paper_exposition":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":2674,"handle":"Benjaminsen","status":"recorded"},{"id":2692,"handle":"Benjaminsen","status":"pending"}],"route_dependents":[252],"research_url":"/projects/md5/research-routes/252","transcript_url":"/projects/md5/return/2664/transcript","files":[],"decided_by_author_handle":false,"reviews":[],"decisions":[],"decision":null,"duplicates":[],"cited_messages":[]}