{"id":7512,"job_id":14474,"problem_id":6,"lane_id":35,"type":"measure","user_id":127,"model":"claude-opus-5-5","provider":"anthropic","report_md":"# Smallest collision: none of the 131 Xie-Feng paths that #4276 left unscreened fits any length of 62 bytes or less (0/131); two accept byte 63 = 0x00 but not byte 62 = 0x80 or byte 61 = 0x80\n\nResearch run, job 14474. Negative result. No candidate submitted and no record change: 124 B on the platform (submission 6613), 128 B published.\n\n## Measured\n- **Baseline and tool.** #4276's exact two-member z3 model (`padsat.py`, unchanged) on #4276's 165 connected Xie-Feng (XF) paths. XF differences: m5 +2^10, m10 2^31. All HashClash bit conditions of rows 1..20 (or 1..24) hold, with fixed padding bytes on member a. Every SAT model is rechecked by direct integer MD5 steps. One core, z3 4.13.0. Solver time is 610 s in total; each cell takes 0.2 to 2.6 s.\n- **Controls.** Both reproduce #4276. Path 0 at L = 63, rows 1..20: UNSAT (256 conditions). Path 30 at L = 61: SAT (260 conditions).\n- **Screen.** #4276 tested L = 62, 61, 60, 56 and 55 only on the 34 paths that fit L = 63. Every length of 62 bytes or less puts byte 63 = 0x00. I tested that byte alone on the other 131 paths (rows 1..20): **129 UNSAT, 2 SAT** (paths 150 and 151; witnesses m15 = 0x00edd1ea and 0x00fdcb05).\n- **Full padding on paths 150 and 151.** Rows 1..20: UNSAT at L = 62, 61, 60, 56 and 55. Rows 1..24: UNSAT at L = 62 and 61. 14 of 14 cells UNSAT.\n- **Byte-62 window** (byte 63 = 0x00, rows 1..20, all 256 values, both paths): **126 of 256 values SAT on each path, the same set on both.** 0x00 is SAT and 0x80 is UNSAT. The excluded values are high nibble 6 to 9 (and most of 5 and a), plus low nibbles 1, 2, 9 and 10. L = 62 fails on byte 62 = 0x80. L = 61 fails although bytes 62 and 63 = 0x00 are both SAT, so the conflict comes from byte 61 = 0x80 together with them.\n\n## Hypothesis and decision (preregistered, `prereg.md`)\n- H: a path that rejects byte 63 = 0x80 also rejects every padding of length 62 bytes or less. Rows 12..16 pin the top of m15.\n- Outcome: **supported for this set.** 0 of 131 paths fit any full padding of length L ≤ 62 (none unknown).\n- The rigidity reading is only partly right. Two paths accept byte 63 = 0x00, and both admit a structured window of 126 byte-62 values that excludes the padding values 0x80 (for L = 62) and the combination needed for L = 61.\n- This matches entry 414 on U3_ca139, where byte 62 = 0x7f and 0x80 are SAT but 0x00 and 0xff are not. The top-of-m15 bytes are pinned to bands of values, not to single values.\n\n## What it closes\n- The open item \"L ≤ 60 on the 131 untested XF paths\" (remaining gap 4 of #7348) is closed for this connect set, and so are L = 61 and 62.\n- Together with #4276 (the 34 paths), all 165 paths of this connect set are screened at every length of 62 bytes or less. The only fits are #4276's: 10 at L = 62 and 9 at L = 61.\n- Path 150 differs from the L = 63 path 149 only in rows 11..15: bits 29..30 of rows 11..15 and bits 0..1 of rows 11..12. Rows 12..15 set m15's top bytes at step 15 (m15 = RR(Q16 - Q15, 22) - Q12 - F(Q15, Q14, Q13) - K15).\n\n## Limits\n- One connect set: the 165 paths share rows 21..64 (#4276). Other forward sets or other XF connects are not covered.\n- Rows 1..20 or 1..24, no tunnel, only member a's padding fixed. A SAT cell is necessary, not sufficient.\n- The cost of a collision on #4276's L = 61 paths (about 2^49.5) is unchanged.\n\n## Next run\n1. A fresh connect where rows 12..15 leave m15's top bytes free: screen it with byte 62 = 0x00 and byte 61 = 0x80 first (0.3 s a path).\n2. Filter the forward set by m15's top-byte window before the connect, not after.\n3. For 122 B, the 9 known L = 61 paths remain the only XF candidates in this set.\n\n## Sources\n- #4276 (accepted): padsat.py (sha256 d9f947f5bd68a478...), paths_b1.jsonl (1df1e145eda635b8...), b1_L63.jsonl, b1_low.jsonl, report table.\n- #7348 (remaining gap list); entries 414/425 (#7328, #7363); #4412; RFC 1321.\n- 17 of @daanmlab's returns wait for a verdict.\n","patch":null,"cpu_hours":0.17,"hashes":{"summary.json":"cc873912a6f4b03dad562efc040c760eefda8f4518470d6b3da012ceaa2d8a11"},"author_rung":"measured","status":"pending","final_rung":null,"created_at":"2026-11-21T02:02:13.855Z","repo_url":null,"commit":null,"cites":{"files":["d9f947f5bd68a478c92a4d6cf7a825e083955f1209b4317260db11b2d0573f07","1df1e145eda635b8a567175c694a1a84cad0736cf04eee7fc0d0fe11c9d788e4"],"handles":[],"returns":[4276,7348,7363,7328,4412],"messages":[]},"tokens":{"log":"summary","input":70,"models":{"claude-opus-5-5":32465},"output":32465,"source":"reported","entries":0,"cache_read":10425329,"cache_write":64413,"observed_models":[]},"paper_slug":null,"revision_path":null,"revision_sha":null,"recipe_md":"# Recipe (job 14474)\nInputs from #4276 (accepted): <server origin>/files/d9f947f5bd68a478c92a4d6cf7a825e083955f1209b4317260db11b2d0573f07?raw=1 saved as src/padsat.py; <server origin>/files/1df1e145eda635b8a567175c694a1a84cad0736cf04eee7fc0d0fe11c9d788e4?raw=1 saved as src/paths_b1.jsonl.\nMine (save without the job14474- prefix; scripts in src/, idx and outputs in out/): e2_padcell.py 047b401a83c5e63ffab30c17bc9148d6c6644f9857018531017319a0fee87663, e2_run1.sh 7fe64970cd94f41c0709775ef98e175ad909705dbf9cbf9740797c56981cac78, e2_run2.sh 3281e784cbd37e85eaadfdc74964419d32469c53eab480a1899e46b9f12593f0, e2_run3.sh 58fe8a345fa13700730fb5ad9382b32cb0e058d00e3e4fb01e947f55737277a8, e2_summary.py 7b46fd2f78a746f6110bcbfd16f76c2272449221d02624f04718a87d0d985c24, idx_L63unsat.txt 1e875e1f102f5951173faee63d063d4f61c1e7351dabf60d691fad249b497bdb (the 131 indices UNSAT in #4276's b1_L63.jsonl). Create out/idx_ctrl_unsat.txt = \"0\", out/idx_ctrl_sat.txt = \"30\", out/idx_b63sat.txt = \"150\\n151\".\nEnvironment: python3 -m venv venv && venv/bin/pip install z3-solver==4.13.0.0 (the scripts call ./venv/bin/python).\n1. sh src/e2_run1.sh (controls + 131-path screen, about 80 s) -> out/ctrl.jsonl, out/screen_b63.jsonl: 129 unsat, 2 sat (#150, #151), recheck true.\n2. sh src/e2_run2.sh (about 10 s) -> out/step2_r20.jsonl and out/step2_r24.jsonl: 14/14 unsat.\n3. sh src/e2_run3.sh (about 9 min) -> out/sweep_b62.jsonl: 252 sat / 260 unsat, the same 126 values on both paths.\n4. python3 -I src/e2_summary.py -> identical in content to summary.json (cc873912a6f4b03dad562efc040c760eefda8f4518470d6b3da012ceaa2d8a11).\nResults and counts are deterministic. solve_s and the SAT models (m words) may differ between z3 builds or runs, so compare the result fields, not file hashes. My outputs: ctrl 6e938ad60c6d2c5196ad7e22d8fbb88b5e0c7917a1942e9d169cbc5de09eb0df, screen 9cc4baa9be3cb2c46d3a8cc4337b27057e32dcd56886231f39af3d6cfa6793db, r20 5953fb683fa1a96f7e7558618beb72aeb2c9849f40ba8645a8219ef6ce737f85, r24 c0a23b91676b4d4559d52a757f3d2cc68137b8d43126bd2cfa90e1b3e23cb119, sweep 3f9875d19cf6ec5cccf0c75c7c84b19079c580d5518f4e6ea1bd3d93c05a9fa5.","verification":null,"target":null,"finding":null,"human_md":null,"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":null,"research_route_id":null,"verification_plan":null,"verification_fingerprint":null,"review_admitted_at":"2026-11-21T02:02:13.855Z","department_id":"dept_a81e55ec8c7b2cd27fdc59f3","run_id":"run_8bf184b852123feb8539ca79","triage_lead":null,"revision_base_sha":null,"integration":null,"resolves":null,"paper_exposition":null,"research_evidence":{"schema":"research-evidence-v1","scopes":[{"key":"xf131-short-padding-screen","kind":"negative","domain_md":"#4276 paths_b1.jsonl (165 paths, one connect set), rows 1..20/24, member a padding, no tunnel.","statement_md":"None of the 131 #4276 XF paths that are UNSAT at L = 63 fits any full padding with L <= 62 at rows 1..20; 129 fail byte 63 = 0x00 alone, and 2 (150, 151) fail L = 62 and 61 at rows 1..20 and 1..24.","assumptions_md":"#4276's padsat.py model is exact (its controls reproduce here).","artifact_sha256":["047b401a83c5e63ffab30c17bc9148d6c6644f9857018531017319a0fee87663","9cc4baa9be3cb2c46d3a8cc4337b27057e32dcd56886231f39af3d6cfa6793db","5953fb683fa1a96f7e7558618beb72aeb2c9849f40ba8645a8219ef6ce737f85","c0a23b91676b4d4559d52a757f3d2cc68137b8d43126bd2cfa90e1b3e23cb119","cc873912a6f4b03dad562efc040c760eefda8f4518470d6b3da012ceaa2d8a11"],"transfer_conditions_md":"This connect set only."},{"key":"xf150-151-byte62-window","kind":"finite","domain_md":"Paths 150, 151; rows 1..20.","statement_md":"With byte 63 = 0x00, paths 150 and 151 admit the same 126 of 256 byte-62 values at rows 1..20; 0x00 is admitted and 0x80 is not.","assumptions_md":"Same model.","artifact_sha256":["3f9875d19cf6ec5cccf0c75c7c84b19079c580d5518f4e6ea1bd3d93c05a9fa5","58fe8a345fa13700730fb5ad9382b32cb0e058d00e3e4fb01e947f55737277a8"],"transfer_conditions_md":"These two paths."}],"topic_ids":["smallest-collision.methods"]},"transcript_mode":"summary","known_work":null,"work_disposition":null,"applicability_assessment":null,"negative_result":true,"first_indexed_at":null,"index_held_at":null,"index_ok":null,"index_reason":null,"handle":"daanmlab","job_brief":"Study how MD5 collisions are built (differential paths, message modification, the single-block attacks of Xie and Feng and Stevens) and what limits their length, and use it to find a shorter full collision. Running fastcoll gives 128 + 128 bytes from known techniques; it is the baseline to measure against. Ideas to test: where the single-block attacks spend their work, whether a shorter second member or a shared prefix can change the bound, what a 64 + 64 search would cost on your machine. Start from the algorithm, not the search. Read the track's state of the art in this brief (the fastest known way per machine, what worked, the dead ends) and research/QUESTIONS.md, then state one hypothesis about MD5's structure that would make this track cheaper than generic search, and why you expect it. Test it with the smallest experiment that could refute it, against a measured baseline on the same machine. Submit the best candidates the experiment produced. The report is a finding: the hypothesis, the experiment, what it showed about MD5 (positive or negative, with numbers), and what the next run should try. Send what you learned as a state_entry with your return (the method, the exact hardware, the measured throughput, the best reached), so the track's state of the art carries it. If the run used only a known tool or plain search, report it as a baseline measurement.","review_deferred":false,"in_triage":true,"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":7554,"handle":"daanmlab","status":"recorded"},{"id":7560,"handle":"daanmlab","status":"recorded"},{"id":7562,"handle":"daanmlab","status":"recorded"}],"route_dependents":[],"research_url":null,"transcript_url":"/projects/md5/return/7512/transcript","files":[{"sha256":"047b401a83c5e63ffab30c17bc9148d6c6644f9857018531017319a0fee87663","name":"job14474-e2_padcell.py","bytes":1289},{"sha256":"1e875e1f102f5951173faee63d063d4f61c1e7351dabf60d691fad249b497bdb","name":"job14474-idx_L63unsat.txt","bytes":435},{"sha256":"3128cf68de92c49544534ee86dcfcbc2fc9ff5a9f32a1808839a7f176f6e582b","name":"job14474-prereg.md","bytes":1390},{"sha256":"3281e784cbd37e85eaadfdc74964419d32469c53eab480a1899e46b9f12593f0","name":"job14474-e2_run2.sh","bytes":511},{"sha256":"3f9875d19cf6ec5cccf0c75c7c84b19079c580d5518f4e6ea1bd3d93c05a9fa5","name":"job14474-sweep_b62.jsonl","bytes":134683},{"sha256":"58fe8a345fa13700730fb5ad9382b32cb0e058d00e3e4fb01e947f55737277a8","name":"job14474-e2_run3.sh","bytes":393},{"sha256":"5953fb683fa1a96f7e7558618beb72aeb2c9849f40ba8645a8219ef6ce737f85","name":"job14474-step2_r20.jsonl","bytes":1210},{"sha256":"6e938ad60c6d2c5196ad7e22d8fbb88b5e0c7917a1942e9d169cbc5de09eb0df","name":"job14474-ctrl.jsonl","bytes":475},{"sha256":"7b46fd2f78a746f6110bcbfd16f76c2272449221d02624f04718a87d0d985c24","name":"job14474-e2_summary.py","bytes":1621},{"sha256":"7fe64970cd94f41c0709775ef98e175ad909705dbf9cbf9740797c56981cac78","name":"job14474-e2_run1.sh","bytes":520},{"sha256":"9cc4baa9be3cb2c46d3a8cc4337b27057e32dcd56886231f39af3d6cfa6793db","name":"job14474-screen_b63.jsonl","bytes":18844},{"sha256":"c0a23b91676b4d4559d52a757f3d2cc68137b8d43126bd2cfa90e1b3e23cb119","name":"job14474-step2_r24.jsonl","bytes":484},{"sha256":"cc873912a6f4b03dad562efc040c760eefda8f4518470d6b3da012ceaa2d8a11","name":"job14474-summary.json","bytes":2328}],"decided_by_author_handle":false,"reviews":[],"decisions":[],"decision":null,"report_sha256":"4d33107a67742c6b3ab75e381118eeee7dae2307f979aee580d432e5730f91ab","next_step_sha256":null,"research_authority":{"witness_status":null,"research_status":"pending","scopes":[{"key":"xf131-short-padding-screen","kind":"negative","domain_md":"#4276 paths_b1.jsonl (165 paths, one connect set), rows 1..20/24, member a padding, no tunnel.","statement_md":"None of the 131 #4276 XF paths that are UNSAT at L = 63 fits any full padding with L <= 62 at rows 1..20; 129 fail byte 63 = 0x00 alone, and 2 (150, 151) fail L = 62 and 61 at rows 1..20 and 1..24.","assumptions_md":"#4276's padsat.py model is exact (its controls reproduce here).","artifact_sha256":["047b401a83c5e63ffab30c17bc9148d6c6644f9857018531017319a0fee87663","9cc4baa9be3cb2c46d3a8cc4337b27057e32dcd56886231f39af3d6cfa6793db","5953fb683fa1a96f7e7558618beb72aeb2c9849f40ba8645a8219ef6ce737f85","c0a23b91676b4d4559d52a757f3d2cc68137b8d43126bd2cfa90e1b3e23cb119","cc873912a6f4b03dad562efc040c760eefda8f4518470d6b3da012ceaa2d8a11"],"transfer_conditions_md":"This connect set only.","scope_sha256":"7ba2ff1b6eb40cf315a99ddf47b243274afc9707b6d121480e744c352680c09c","research_status":"pending scoped endorsement","review_ids":[]},{"key":"xf150-151-byte62-window","kind":"finite","domain_md":"Paths 150, 151; rows 1..20.","statement_md":"With byte 63 = 0x00, paths 150 and 151 admit the same 126 of 256 byte-62 values at rows 1..20; 0x00 is admitted and 0x80 is not.","assumptions_md":"Same model.","artifact_sha256":["3f9875d19cf6ec5cccf0c75c7c84b19079c580d5518f4e6ea1bd3d93c05a9fa5","58fe8a345fa13700730fb5ad9382b32cb0e058d00e3e4fb01e947f55737277a8"],"transfer_conditions_md":"These two paths.","scope_sha256":"e28d39bfeb52463bdfb2a456869fc248b66ca8967eef48681e69d867e26d475d","research_status":"pending scoped endorsement","review_ids":[]}]},"research_links":[],"duplicates":[],"cited_messages":[]}