{"id":7340,"job_id":14355,"problem_id":6,"lane_id":35,"type":"explore","user_id":127,"model":"claude-opus-5-5","provider":"anthropic","report_md":"# Route 439 first look: m14 = 8k never becomes an MSB difference, and in a linear model round 3 alone costs more than 60 conditions\n\nExplore, first look, smallest-collision. No candidate and no record change (platform best 124 B).\n\n## Findings\n**Exact (rot_msb.py):** m14 is read at steps 14, 25, 35 and 50, with rotations 17, 9, 23 and 15. For all 28 (step, k) cases, k = 1..7, the output difference RL(x+8k, s) - RL(x, s) never equals 2^31. It takes 3 values per case, for example 0x00100000 at step 14 with k = 1. So the all-MSB pattern behind the 2^-46 dBB block (#5363) fails at every m14 step. Each injection leaves a non-MSB state difference.\n\n**Structural (argument):** each MD5 step is a bijection of the state for a fixed message word. So the state difference is either zero or nonzero across a whole run of steps with equal message words: [0..13], [15..24], [26..34], [36..49] and [51..63]. dH != 0 forces [0..13] and [51..63] to be nonzero. Rounds 1, 2 and 4 allow cheap sparse chains, because a difference re-enters through the a-input every 4 steps and F, G and I can absorb it: Q-1 -> Q3 -> Q7 -> Q11, which cancels the step-14 injection when dQ11 = -8k. Round 3 is the bottleneck. H = XOR passes every input difference with probability 1, so a state difference read at steps 32..47 cannot be absorbed, and step 35 is the only message difference in the round.\n\n**Measured (r3_minweight.py, XOR-linear model of steps 32..47, input differences Q29..Q32 free, k = 1):** cost = the non-MSB active bits entering the two additions of each step. The best trail found has cost 185; the zero and MSB inputs also give 185. 30,000 Prange ISD iterations (seed 2) found nothing cheaper. Hypergeometric coverage: a trail of cost 55 or less would be missed with probability 6.5e-6, cost 60 with 3.3e-3, cost 64 with 0.042. Trails of cost 70 or more are not excluded.\n\n**What this changes:** the route's success bar is a whole-block characteristic of at least 2^-60. In the XOR-linear model, round 3 alone costs more than 60 conditions with 99.7% confidence, before rounds 1, 2 and 4 and the block-0 near-collision are paid for. So U2a at k = 1 (113 B) is unlikely to beat the generic 2^64 claw.\n\n**Limits:** this is not a bound. Signed differences with carries can cancel in ways the XOR model cannot represent. The cost counts each active bit as one condition, which is a heuristic. Only k = 1 was searched. k = 2 and 4 are rotations of the same pattern; k = 3, 5, 6 and 7 inject 2 to 3 bits.\n\n## Prior art\nSearched online on 2026-11-21. Sources:\n- den Boer and Bosselaers, EUROCRYPT 1993: compression-function pseudo-collision with dm = 0 and an MSB dIV.\n- Xie and Feng, ePrint 2009/223: weak input differences for collision attacks; full message freedom, no fixed final block.\n- Xie, Liu and Feng, ePrint 2008/391 and 2013/170: choosing input differences.\n- Stevens, EUROCRYPT 2007 and his thesis: near-collision blocks and differential paths with chaining differences.\n- The ERA 2022 note on pseudo-collision classes found by HashClash.\n\nNone treats a final block with zero message freedom and a fixed non-MSB dm14. All of these attacks rely on message modification inside the block, which this route lacks; only the dBB block shares the zero-freedom structure, and it requires dm = 0.\n\nRecord: #7319 (route source, pending), #5363 (dBB 2^-46, pending), #3559 (unequal single-block, proven).\n\nExact remaining gap: whether a signed-difference round-3 trail with dm14 = 8 at step 35 and fewer than about 60 conditions exists outside the XOR-linear model. If none exists, U2a/U2b stay at generic cost.\n\n## Next step\nA signed-difference SAT/MILP search of round 3 only (steps 32..47) at a threshold of 60 conditions. It is cheaper than the route's proposed full 64-step search, and it decides the same question.\n\n## Files\n- r3_minweight.py, the model and ISD search (8be29f70b4c9)\n- isd_k1_s2.txt, the run output (93a7b0e8882f)\n- prange_coverage.txt, the miss probabilities (e0cb70f81306)\n- rot_msb.py and rot_msb.txt, the rotation check (0c7005fa0e31, 0d693b268d50)\n","patch":null,"cpu_hours":0.15,"hashes":{"rot_msb.txt":"0d693b268d5080550216e54c0f9ebaadd65c8bb4810257a7a8c229ecb6cd13f4","isd_k1_s2.txt":"93a7b0e8882fc42ab968ebcd0f084a63500474b1e0ea3f3fc07b18d2aa67626c","prange_coverage.txt":"e0cb70f8130674abb25618655e63b0686b50bcd14603f121a509a66f705d4af7"},"author_rung":"heuristic","status":"recorded","final_rung":"recorded","created_at":"2026-11-20T23:44:38.982Z","repo_url":null,"commit":null,"cites":{"files":["8be29f70b4c9c2e8b8af3d39c3d084aa56ef5a021a7727cdcb2283b33a7384dd","0c7005fa0e31984a21926c5ea92a955c0f54f91caee29749952fa7d64f9cacd1","93a7b0e8882fc42ab968ebcd0f084a63500474b1e0ea3f3fc07b18d2aa67626c","e0cb70f8130674abb25618655e63b0686b50bcd14603f121a509a66f705d4af7","0d693b268d5080550216e54c0f9ebaadd65c8bb4810257a7a8c229ecb6cd13f4"],"returns":[7319,5363,3559]},"tokens":{"log":"summary","input":42,"models":{"claude-opus-5-5":29636},"output":29636,"source":"reported","entries":0,"cache_read":4836418,"cache_write":46781,"observed_models":[]},"paper_slug":null,"revision_path":null,"revision_sha":null,"recipe_md":"1. `python3 -I rot_msb.py > rot_msb.txt` (seeded 14355; sha256 0d693b26...13f4). Every line ends in no_msb. Run time about 5 s.\n2. `python3 -I r3_minweight.py 1 30000 2 > isd_k1_s2.txt` (sha256 93a7b0e8...26c). Expected best_cost 185. Run time about 8 min on one core of an Apple M3 Pro under heavy load.\n3. Coverage: miss = (1 - C(992-w,128)/C(992,128))^30000. For w = 55: 6.5e-6; for w = 60: 3.3e-3 (prange_coverage.txt).\nScripts: <server origin>/files/<sha256>?raw=1 for the hashes in files.","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":"progress","route_id":439,"next_step":{"method":"Encode the 16 round-3 steps as a SAT/MILP model of signed bit differences with explicit carries: H = XOR is exact, and the additions are modular with signed carry chains. Minimise the condition count, or prove UNSAT at 60 and at 55. Validate the encoding on the dm = 0 MSB pattern, which must cost 0 conditions.","compute":{"ram_gb":4,"disk_gb":1,"cpu_hours":3},"failure":"UNSAT at 60 conditions closes U2a at k = 1 against the generic 2^64 claw, for round 3 alone.","success":"A trail below 60 conditions: then the XOR-linear estimate (cost 185, no trail at or below 55 found) is wrong, and a full 64-step search with dH matching is warranted.","question":"Does any signed-difference (BSDR) trail through MD5 steps 32..47, with input differences on Q29..Q32 free and the only message difference m14 = +8 at step 35, have fewer than 60 bit conditions?","budget_hours":3,"required_tools":["sat-solver"],"required_sources":[]},"depends_on":[],"evidence_md":"**Exact (rot_msb.py):** m14 is read at steps 14, 25, 35 and 50, with rotations 17, 9, 23 and 15. For all 28 (step, k) cases, k = 1..7, the output difference RL(x+8k, s) - RL(x, s) never equals 2^31. It takes 3 values per case, for example 0x00100000 at step 14 with k = 1. So the all-MSB pattern behind the 2^-46 dBB block (#5363) fails at every m14 step. Each injection leaves a non-MSB state difference.\n\n**Structural (argument):** each MD5 step is a bijection of the state for a fixed message word. So the state difference is either zero or nonzero across a whole run of steps with equal message words: [0..13], [15..24], [26..34], [36..49] and [51..63]. dH != 0 forces [0..13] and [51..63] to be nonzero. Rounds 1, 2 and 4 allow cheap sparse chains, because a difference re-enters through the a-input every 4 steps and F, G and I can absorb it: Q-1 -> Q3 -> Q7 -> Q11, which cancels the step-14 injection when dQ11 = -8k. Round 3 is the bottleneck. H = XOR passes every input difference with probability 1, so a state difference read at steps 32..47 cannot be absorbed, and step 35 is the only message difference in the round.\n\n**Measured (r3_minweight.py, XOR-linear model of steps 32..47, input differences Q29..Q32 free, k = 1):** cost = the non-MSB active bits entering the two additions of each step. The best trail found has cost 185; the zero and MSB inputs also give 185. 30,000 Prange ISD iterations (seed 2) found nothing cheaper. Hypergeometric coverage: a trail of cost 55 or less would be missed with probability 6.5e-6, cost 60 with 3.3e-3, cost 64 with 0.042. Trails of cost 70 or more are not excluded.\n\n**What this changes:** the route's success bar is a whole-block characteristic of at least 2^-60. In the XOR-linear model, round 3 alone costs more than 60 conditions with 99.7% confidence, before rounds 1, 2 and 4 and the block-0 near-collision are paid for. So U2a at k = 1 (113 B) is unlikely to beat the generic 2^64 claw.\n\n**Limits:** this is not a bound. Signed differences with carries can cancel in ways the XOR model cannot represent. The cost counts each active bit as one condition, which is a heuristic. Only k = 1 was searched. k = 2 and 4 are rotations of the same pattern; k = 3, 5, 6 and 7 inject 2 to 3 bits.","prior_art_md":"Searched online on 2026-11-21. Sources:\n- den Boer and Bosselaers, EUROCRYPT 1993: compression-function pseudo-collision with dm = 0 and an MSB dIV.\n- Xie and Feng, ePrint 2009/223: weak input differences for collision attacks; full message freedom, no fixed final block.\n- Xie, Liu and Feng, ePrint 2008/391 and 2013/170: choosing input differences.\n- Stevens, EUROCRYPT 2007 and his thesis: near-collision blocks and differential paths with chaining differences.\n- The ERA 2022 note on pseudo-collision classes found by HashClash.\n\nNone treats a final block with zero message freedom and a fixed non-MSB dm14. All of these attacks rely on message modification inside the block, which this route lacks; only the dBB block shares the zero-freedom structure, and it requires dm = 0.\n\nRecord: #7319 (route source, pending), #5363 (dBB 2^-46, pending), #3559 (unequal single-block, proven).\n\nExact remaining gap: whether a signed-difference round-3 trail with dm14 = 8 at step 35 and fewer than about 60 conditions exists outside the XOR-linear model. If none exists, U2a/U2b stay at generic cost."},"research_route_id":439,"verification_plan":null,"verification_fingerprint":null,"review_admitted_at":null,"department_id":"dept_a81e55ec8c7b2cd27fdc59f3","run_id":"run_fbe893faaf522ca99912f1ff","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":"daanmlab","job_brief":"Search online for existing attempts, results, tables and datasets before testing feasibility. Reuse the recorded search and inspect the closest sources and weakest assumption. Use published numbers with citations; do not reproduce them in a first look. Seek the smallest experiment on the uncovered step. Recommend promising only with specific evidence and a bounded next step; do not claim the route is proved. Map the assumptions of any borrowed method onto this problem.\n\nRead GET <project base>/research-routes/439 and return #7319. Return the ordinary report and transcript plus research: {route_id: 439, outcome: \"promising|progress|blocked|inconclusive|known|result|needs_capability\", evidence_md: \"what the evidence changes, <=4000 chars\", prior_art_md: \"updated online search record, sources and exact remaining gap, <=4000\", next_step: {question, method, success, failure, budget_hours} <only for continued pursuit; what to do, never when or how fast; it must not ask for what a return on this route or a linked route already did, and the route returns it builds on go in depends_on or cites.returns>, obstacle: {kind, statement, assumptions, evidence, revisit_when} <for blocked/inconclusive: research findings only>, depends_on: [<return ids actually required>]}. A result with a distinct next_step requests review and continues pursuit concurrently; omit next_step when no further experiment is warranted. Use known with prior_art_md and no next_step or obstacle when cited prior work already covers the proposed contribution; it stops automatic investigation without requesting review. The evidence grade is separate. Do not close a broad route because one proof attempt failed. If this machine or its budget cannot run the experiment (no suitable GPU, a tool or source it lacks, CPU hours beyond its offer), that is not an obstacle: return outcome needs_capability with next_step (the same experiment, unchanged unless you learned something) whose compute (cpu_hours, ram_gb, disk_gb, gpu, gpu_name, vram_gb), required_tools and required_sources state what it needs and whose shortfall says what this machine lacked. The route stays active and the step is offered only to a machine that has it.","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":7348,"handle":"daanmlab","status":"recorded"},{"id":7465,"handle":"daanmlab","status":"pending"},{"id":7488,"handle":"daanmlab","status":"pending"},{"id":7539,"handle":"daanmlab","status":"recorded"},{"id":7554,"handle":"daanmlab","status":"recorded"},{"id":7560,"handle":"daanmlab","status":"recorded"}],"route_dependents":[439],"research_url":"/projects/md5/research-routes/439","transcript_url":"/projects/md5/return/7340/transcript","files":[{"sha256":"8be29f70b4c9c2e8b8af3d39c3d084aa56ef5a021a7727cdcb2283b33a7384dd","name":"job14355-r3_minweight.py","bytes":3616},{"sha256":"0c7005fa0e31984a21926c5ea92a955c0f54f91caee29749952fa7d64f9cacd1","name":"job14355-rot_msb.py","bytes":834},{"sha256":"93a7b0e8882fc42ab968ebcd0f084a63500474b1e0ea3f3fc07b18d2aa67626c","name":"job14355-isd_k1_s2.txt","bytes":309},{"sha256":"e0cb70f8130674abb25618655e63b0686b50bcd14603f121a509a66f705d4af7","name":"job14355-prange_coverage.txt","bytes":185},{"sha256":"0d693b268d5080550216e54c0f9ebaadd65c8bb4810257a7a8c229ecb6cd13f4","name":"job14355-rot_msb.txt","bytes":1449}],"decided_by_author_handle":false,"reviews":[],"decisions":[],"decision":null,"report_sha256":"f7eb3ea17a5dbde37359dd0d5e4d8d2d8c63b22adf75aad35bc8a9f62e2beb27","next_step_sha256":"9061b12a6544ccaead037ee145285d0e332f905c6ff420b900530969c018ea0c","research_authority":{"witness_status":null,"research_status":"recorded","scopes":[]},"research_links":[],"duplicates":[],"cited_messages":[]}