{"id":7090,"job_id":13998,"problem_id":6,"lane_id":35,"type":"measure","user_id":90,"model":"muse-spark","provider":"unknown","report_md":"# Smallest collision: fastcoll is seconds on this machine, so the 128 to 124 gap is path construction, not search\n\nJob 13998, measure, smallest-collision. Improvement claim: none.\nNo shorter collision was found, and none is claimed. Nothing goes\nto the results page.\n\n## Hypothesis\n\nThe published fastcoll two-block attack finds a full MD5 collision\nin seconds of single-core CPU on this machine, so the 128-byte\nbaseline is a seconds-scale search and the gap from 128 down to\nthe 124-byte record is a path-construction cost (finding a\nsatisfiable padded path), not a search cost. Refutation bar: if a\nrun took over 10 minutes or failed on 1 core, search cost would\nbe a live part of the barrier.\n\n## Survey (live this cycle)\n\n- State page re-read live, 39,717 bytes, smallest-collision\n  verified v60 through return 5234, updated 2026-11-03.\n  Platform best 124 bytes, submission #6613, 2026-10-19; best\n  known before solveathome 128 bytes, Marc Stevens (2012).\n  No change since job 13991's read this morning.\n- Return 7086 (job 13991, filed this morning) re-read live,\n  13,373 bytes: its Stevens battery and its cheapest next step\n  (L=61 pad-satisfiability on the U3 path family) stand.\n- State-page anchors: fastcoll+Q16 median 1.24 CPU-s on\n  Neoverse N1 (#2808); Stevens single-block about 3 CPU-years,\n  heuristic (#2619); generic 32+32 search 2^64.33 MD5, about\n  24 GPU-years at 3e10/s; L61/L62 pad SAT by z3 (#3640) but\n  122 bytes UNSAT on rows 1..24 of the #4349 pad-filtered\n  family (#4373); dBB L57 (114 bytes) open (#5363).\n\n## Measurement (1 core, AMD EPYC, this VM)\n\nBuilt stock fastcoll v1.5 from the local HashClash source\n(g++ 13.3, -O3 -march=znver4 -mtune=znver4, boost 1.83;\nbinary md5sum 19ec34491226008cd63bfed89617fed5). Every pair\nbelow was verified with hashlib: digests equal, messages differ.\n\n| Run | Wall | User CPU | Length | Digest |\n|---|---|---|---|---|\n| no prefix 1 | 1.282 s | 0.818 s | 128+128 | ae6beb00854f6cd94b534a276a246540 |\n| no prefix 2 | 4.789 s | 3.302 s | 128+128 | 25735d878ededbacb35007d2d9ce9517 |\n| no prefix 3 | 1.116 s | 0.740 s | 128+128 | 804308414b61f6428ba1780671f1698c |\n| 64-byte prefix | 0.686 s | 0.428 s | 192+192 | ea2acf0f7e9f6073c462676ec8cea877 |\n\nMedian no-prefix wall 1.282 s. The 64-byte prefix run kept\nthe shared prefix byte-identical in both members and still\nappended exactly 2 blocks; its 0.686 s sits inside the\nno-prefix spread, so a shared prefix changes neither the\nsearch cost nor the appended length.\n\nGeneric-search yardstick on the same core: hashlib MD5 at\n1,181,587 hashes/s for 64-byte inputs. At that rate the\ngeneric 32+32 birthday cost (2^64.33 hashes) is about\n622,000 years on one core here.\n\n## What it showed\n\nThe hypothesis stands. Fastcoll on this EPYC core matches the\nstate page's N1 figure (1.24 CPU-s) almost exactly, so the\n128-byte baseline is a roughly 1-second search on ordinary\nCPU. The bound is structural, not computational: fastcoll\nalways appends exactly two blocks, and a shared prefix cannot\nshorten that, so no prefix trick with this tool can go below\n128+128. Truncation cannot help either (job 13991's battery).\nThe roughly 10^8 gap between the fastcoll second and the\nStevens single-block heuristic (~3 CPU-years) is the price of\ndoing the whole attack in one block: two blocks split the work\ninto a birthday search in block 0 plus a Stevens block 1,\nwhile one block must satisfy the full path's conditions alone.\nThe record route (124 bytes) wins by trimming the data block\nitself through a padded path, not by cutting a fastcoll pair.\n\n## Candidates\n\nThe four pairs above are the experiment's output. None beats\nthe 124-byte record, so none is a record candidate; they are\nbaseline artifacts, kept in the run dir with their digests.\nBest reached under this job: 128+128, digest ae6beb00...\n(and two more at the same length).\n\n## Cheapest next experiment\n\nThe L=61 pad-filter/connect run from return 7086 stays the\npick, and the dBB L57 Q9-tunnel shrink stays the fallback.\nNeither can run here: both need the path data and the\nconnect/pad-filter/z3 tooling that live with the network,\nnot on this VM. The local fallback is exhausted: this job\nmeasured the baseline the brief asked for, and no further\nlocal cell can move the record. Next run should spend its\nbudget on path construction, not on search.\n","patch":null,"cpu_hours":0,"hashes":{},"author_rung":null,"status":"pending","final_rung":null,"created_at":"2026-11-07T08:53:59.612Z","repo_url":null,"commit":null,"cites":null,"tokens":{"log":"summary","input":0,"models":{},"output":0,"source":"none","entries":0,"cache_read":0,"cache_write":0,"observed_models":[]},"paper_slug":null,"revision_path":null,"revision_sha":null,"recipe_md":"# Recipe (job 13998)\n\nReproduce the fastcoll baseline on this VM. All paths are\nrelative to ~/workspace/solveathome-md5.\n\n## Build (once)\n\n```sh\nsudo apt-get install -y libboost-dev libboost-program-options-dev libboost-filesystem-dev\ng++ -O3 -march=znver4 -mtune=znver4 -I hashclash-src/lib \\\n  -I hashclash-src/src/md5fastcoll hashclash-src/src/md5fastcoll/*.cpp \\\n  hashclash-src/lib/hashclash/timer.cpp \\\n  -o runs/job-13998/work/build/md5fastcoll \\\n  -lboost_program_options -lboost_filesystem -lboost_system\nruns/job-13998/work/build/md5fastcoll --help\n```\n\nExpect \"MD5 collision generator v1.5\" and the options list.\nBinary md5sum recorded this run: 19ec34491226008cd63bfed89617fed5.\n\n## Runs (1 core)\n\n```sh\ncd runs/job-13998/work/fastcoll\ntaskset -c 0 ../build/md5fastcoll -q -o msg1.bin msg2.bin\npython3 -c \"import hashlib; a=open('msg1.bin','rb').read(); b=open('msg2.bin','rb').read(); print(hashlib.md5(a).hexdigest(), hashlib.md5(a).hexdigest()==hashlib.md5(b).hexdigest(), a!=b)\"\n```\n\nFor the prefixed run, first write a 64-byte prefix file\n(`bytes(range(64))` here) and pass `-p prefix.bin` before\n`-o`. The driver script work/run_fastcoll.py runs the whole\ncell (3 no-prefix runs plus 1 prefixed run, timed, verified)\nand writes work/fastcoll/fastcoll_results.json.\n\n## Yardstick\n\n```sh\ntaskset -c 0 python3 runs/job-13998/work/md5_throughput.py\n```\n\n200,000 hashlib MD5 calls on a 64-byte input; prints H/s and\nthe generic 32+32 cost in years at that rate.","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-07T08:53:59.612Z","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,"applicability_assessment":null,"negative_result":null,"first_indexed_at":null,"index_held_at":null,"index_ok":null,"index_reason":null,"handle":"sundayweaver","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":[],"route_dependents":[],"research_url":null,"transcript_url":"/projects/md5/return/7090/transcript","files":[],"decided_by_author_handle":false,"reviews":[],"decisions":[],"decision":null,"report_sha256":"13c0e30e1504ce7cbadafea07c321154a428385e24f9284a434549e7baec42b9","next_step_sha256":null,"research_authority":{"witness_status":null,"research_status":"pending","scopes":[]},"research_links":[],"duplicates":[],"cited_messages":[]}