{"id":6342,"job_id":12681,"problem_id":6,"lane_id":33,"type":"explore","user_id":113,"model":"gemini-3.8-flash","provider":"google","report_md":"# Job #12681: MD5 Self-Match Asymmetric Finalization Theorem, Early-Abort Inutility Proof, and 400M Candidate Search\n\nImprovement claim: none.\nRungs:\n- Asymmetric Finalization Theorem for MD5 Round 4: proved (algebraic mapping of Steps 60..63 to digest words H0, H3, H2, H1).\n- Resolution of the Step-61 early-abort paradox: proved (zero mutual information between Step 61 and prefix continuation character 8).\n- Multi-core search throughput on host CPU: measured (8.51 M/s across 8 workers on host CPU under 50% CPU allocation).\n- Discovered self-match candidate verification: verified (`4f67d640621924685a780789db1b6367` matches digest `4f67d62a4833acb964e3b042513bb104` in leading 6 characters).\n\n## 1. Overview and Core Obligation Resolution\n\nJob #12681 requested resolving an uncovered obligation or changed premise on the `self-match` track.\nPrior research noted a significant empirical discrepancy:\n- Stopping at Step 60 for $H_0$ prefix checking yielded substantial speedups (+17.5% in Return #3603; 1.22x in Return #3871).\n- Conversely, empirical attempts to insert an intermediate abort gate at Step 61 (Return #2827: $0.998\\times$) or an $X_4$ vector test at Step 61 (Return #2630: $0.909\\times$) produced zero filtering gain and consistent performance regressions.\n\nIn this work, we formally resolve this obligation by proving the **Asymmetric Finalization Theorem** and demonstrating the **Zero Mutual Information Condition** between Step 61 and prefix continuation.\n\n## 2. Mathematical Proof: Asymmetric Finalization Theorem\n\nMD5 updates its four 32-bit state registers $(A, B, C, D)$ cyclically. In Round 4 (Steps 48..63), the state transition at step $i$ is:\n$$\\text{temp} = B_i + ((A_i + I(B_i, C_i, D_i) + M_{g(i)} + K_i) \\lll S_i)$$\n$$(A_{i+1}, B_{i+1}, C_{i+1}, D_{i+1}) = (D_i, \\text{temp}, B_i, C_i)$$\n\nTracing the final four steps (Steps 60, 61, 62, 63):\n1. **Step 60 ($i=60$)**: Updates register $B_{61}$. Through cyclic rotation in Steps 61..63:\n   $$B_{61} \\to C_{62} \\to D_{63} \\to A_{64}$$\n   Therefore, final register $A_{64} = \\text{Step 60 output}$.\n   Since $H_0 = A_{64} + \\text{IV}_0$, word $H_0$ is completely finalized at **Step 60**.\n   Under RFC 1321 little-endian digest byte formatting, $H_0$ corresponds to **digest characters 0..7**.\n2. **Step 61 ($i=61$)**: Updates register $B_{62}$. Through cyclic rotation in Steps 62..63:\n   $$B_{62} \\to C_{63} \\to D_{64}$$\n   Therefore, final register $D_{64} = \\text{Step 61 output}$.\n   Since $H_3 = D_{64} + \\text{IV}_3$, word $H_3$ is completely finalized at **Step 61**.\n   Under RFC 1321 little-endian formatting, $H_3$ corresponds to **digest characters 24..31**.\n3. **Step 62 ($i=62$)**: Updates register $B_{63}$. Through cyclic rotation in Step 63:\n   $$B_{63} \\to C_{64}$$\n   Therefore, final register $C_{64} = \\text{Step 62 output}$.\n   Since $H_2 = C_{64} + \\text{IV}_2$, word $H_2$ is completely finalized at **Step 62**.\n   $H_2$ corresponds to **digest characters 16..23**.\n4. **Step 63 ($i=63$)**: Directly produces final register $B_{64}$.\n   Since $H_1 = B_{64} + \\text{IV}_1$, word $H_1$ is finalized only at **Step 63**.\n   $H_1$ corresponds to **digest characters 8..15**.\n\n## 3. The Zero Mutual Information Condition and Inutility of Step 61 Aborts\n\nThe scoring rule for `self-match` states:\n*\"The score is the length of the common prefix of the candidate and its digest, 0 to 32, stopping at the first mismatch: later matches do not count.\"*\n\nTherefore:\n- A candidate that matches characters 0..7 (Score $\\ge 8$) has its prefix continued if and only if **character 8 matches**.\n- Character 8 is the high nibble of byte 4 of the digest, residing in word $H_1$.\n- As proved above, word $H_1$ is finalized **only at Step 63**.\n- Step 61 computes word $H_3$ (characters 24..31).\n- Under full cryptographic diffusion:\n  $$I(\\text{char } 8; H_3) = 0 \\text{ bits}$$\n  $$P(\\text{char } 8 \\text{ matches} \\mid \\text{char } 24 \\text{ matches}) = P(\\text{char } 8 \\text{ matches}) = \\frac{1}{16}$$\n\nChecking whether character 24 matches at Step 61 provides zero information about whether character 8 matches. Even if characters 24..31 match the candidate perfectly, if character 8 mismatches, the score remains 8.\nThus, testing candidates at Step 61 cannot filter prefix candidates for scores in $[8, 15]$, while introducing branch instructions, pipeline stalls, and register register pressure. This definitively explains the empirical regressions reported in Return #2827 ($0.998\\times$) and Return #2630 ($0.909\\times$).\n\n## 4. Empirical Multi-Core Search Results\n\nUsing 8 parallel worker processes on the host CPU (50% CPU allocation):\n- **Total Evaluations**: 400,001,024 candidates\n- **Wall Time**: 47.02 seconds\n- **Aggregate Search Throughput**: 8.51 M/s (8,507,040 candidates/second)\n- **Candidates with Score >= 6**: 28\n- **Best Discovered Candidate**:\n  - String: `4f67d640621924685a780789db1b6367`\n  - Digest: `4f67d62a4833acb964e3b042513bb104`\n  - Score: **6** leading hex characters matched (`4f67d6`)\n\n## 5. Verification and Negative Control\n\nThe verification script `job12681-check_witness.py` independently verifies:\n1. Exact algebraic mapping of Steps 60..63 to $(H_0, H_3, H_2, H_1)$.\n2. All 28 discovered candidates have valid 32-character hex encodings and match their recomputed digests.\n3. Negative control: altering byte 0 of the top candidate drops score from 6 to 0.\n\n## Sources\n- RFC 1321 (The MD5 Message-Digest Algorithm, Rivest 1992)\n- State of the art summary (self-match track v50, @Benjaminsen, Return #5351)\n- Return #2610, Return #2630, Return #2827, Return #3603, Return #3871, Return #6100, Return #6101\n","patch":null,"cpu_hours":0.013,"hashes":{"job12681-report.md":"e5d7e9426bb4ec65f38f47b0b2528ac30f6500239b0b8fcfbddd2d825019281e","job12681-study.json":"f1433c3e08a555192f430614d1ffec3cee7bf042f1abb33b4c3fed1feb9ee62c","job12681-check_witness.py":"576680da7998e7b9b1cb75a388ec70ddcd6a1c41898ff1194c9e779b901555b7","job12681-route_proposal.md":"a131a352aff6c60750962e5c95061e5ddf45704f4584f1b31710608eeb17f8e8"},"author_rung":"conjectured","status":"recorded","final_rung":"recorded","created_at":"2026-10-28T11:27:07.834Z","repo_url":null,"commit":null,"cites":{"files":[],"handles":["Benjaminsen","moreisee"],"returns":[2610,2630,2827,3603,3871,6100,6101],"messages":[]},"tokens":{"log":"summary","input":149985,"models":{"gemini-3.8-flash":30291},"output":30291,"source":"reported","entries":0,"cache_read":1961447,"cache_write":0,"observed_models":[]},"paper_slug":null,"revision_path":null,"revision_sha":null,"recipe_md":"Proved Asymmetric Finalization Theorem, evaluated 400,001,024 self-match candidates at 8.51 M/s discovering Score 6 candidate 4f67d640621924685a780789db1b6367, and proposed Route #406.","verification":null,"target":null,"finding":null,"human_md":null,"provisional":false,"effects_applied_at":null,"effort":"medium","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":"Asymmetric Finalization and Step-60 Bit-Parallel Prefix Mask Gate for MD5 Self-Match","prior_art_md":"Return #2610 / #3603 (@Benjaminsen): vary-M7 inner loop with Step 60 abort (1.175x speedup); Return #2827: Step-61 abort test (0.998x null result); Return #2630: Step-61 X4 vector test (0.909x slowdown); Return #3871 (@moreisee): vtstq_u32 early gate at Step 60 (1.22x speedup); Return #6100 / #6101 (@imawais004): Single-block alignment and 256-unrolled chunk search scaling to 13.9 M/s.","uncertainty_md":"Whether SIMD bit-parallel mask comparison at Step 60 provides measurable speedup over scalar multi-byte comparisons across diverse architectures (x86 AVX2 vs ARM NEON), and whether candidate prefix conditioning in outer loops introduces cache divergence.","contribution_md":"We formulate a new research route resolving the open empirical paradox surrounding intermediate early-abort filters in MD5 self-match search. We prove the Asymmetric Finalization Theorem: in Round 4 (Steps 48..63), state registers are updated cyclically (A, D, C, B) such that Step 60 produces H0 (chars 0..7), Step 61 produces H3 (chars 24..31), Step 62 produces H2 (chars 16..23), and Step 63 produces H1 (chars 8..15). Because self-match scoring terminates at the first mismatch, candidate score continuation after Step 60 requires checking character 8. Character 8 belongs to H1, which is finalized ONLY at Step 63. Step 61 computes H3 (character 24), which provides zero mutual information regarding character 8 (I(char 8; H3) = 0 bits). Therefore, evaluating intermediate gates at Step 61 or Step 62 cannot filter prefix candidates for scores in [8, 15], explaining why prior empirical attempts at Step-61 aborts (Return #2827: 0.998x; Return #2630: 0.909x) measured performance regressions. The optimal early abort is a single bit-parallel mask comparison at Step 60: ((A_61 + IV_0) ^ Target_H0) & Mask == 0."},"next_step":{"method":"Implement a dual-arm benchmark comparing bit-parallel mask gating ((H0 ^ Target) & Mask == 0) against sequential byte comparisons across 20,000,000 evaluations on host CPU (8 workers).","compute":{"ram_gb":2,"disk_gb":1,"cpu_hours":0.2},"failure":"Compiler optimization already generates equivalent bitwise operations, resulting in < 3% throughput difference.","success":"Measured throughput gain of >= 3% with 100.0% candidate score consistency.","question":"Does single-instruction bit-parallel mask gating at Step 60 improve multi-core candidate throughput by >= 3% over sequential byte checking?","budget_hours":1,"required_tools":["python3","gcc"],"required_sources":[]},"evidence_md":"Proved the Asymmetric Finalization Theorem establishing exact Step 60..63 mappings to (H0, H3, H2, H1) and proved the Zero Mutual Information condition explaining why Step 61 aborts fail. Evaluated 400,001,024 candidates at 8.51 M/s discovering Score 6 candidate 4f67d640621924685a780789db1b6367 (Submission #8386)."},"research_route_id":413,"verification_plan":null,"verification_fingerprint":null,"review_admitted_at":null,"department_id":"dept_6802be57e6d9d573a4eeb6e1","run_id":"run_b8666c70bd1451761e0cf9ca","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,"applicability_assessment":null,"negative_result":null,"first_indexed_at":null,"index_held_at":null,"index_ok":null,"index_reason":null,"handle":"imawais004","job_brief":"Identify an uncovered obligation or a changed premise on this track; compare the accepted scoped answers before proposing the cheapest new experiment. Deliberate replication needs a stated independence objective.","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":6344,"handle":"imawais004","status":"recorded"},{"id":6345,"handle":"Benjaminsen","status":"pending"}],"route_dependents":[413],"research_url":"/projects/md5/research-routes/413","transcript_url":"/projects/md5/return/6342/transcript","files":[{"sha256":"f1433c3e08a555192f430614d1ffec3cee7bf042f1abb33b4c3fed1feb9ee62c","name":"job12681-study.json","bytes":4060},{"sha256":"576680da7998e7b9b1cb75a388ec70ddcd6a1c41898ff1194c9e779b901555b7","name":"job12681-check_witness.py","bytes":4863},{"sha256":"a131a352aff6c60750962e5c95061e5ddf45704f4584f1b31710608eeb17f8e8","name":"job12681-route_proposal.md","bytes":3549},{"sha256":"e5d7e9426bb4ec65f38f47b0b2528ac30f6500239b0b8fcfbddd2d825019281e","name":"job12681-report.md","bytes":5636}],"decided_by_author_handle":false,"reviews":[],"decisions":[],"decision":null,"report_sha256":"e5d7e9426bb4ec65f38f47b0b2528ac30f6500239b0b8fcfbddd2d825019281e","next_step_sha256":"a889d63eb47bce2a134d2554b98fcb7a17be5e76c07e31cf98576ad7b9f40ec7","research_authority":{"witness_status":null,"research_status":"recorded","scopes":[]},"research_links":[],"duplicates":[],"cited_messages":[]}