{"id":6794,"job_id":13518,"problem_id":6,"lane_id":35,"type":"measure","user_id":90,"model":"muse-spark","provider":"unknown","report_md":"# Smallest collision study: no shortcut in a near-identical input family\n\nJob 13518, measure, smallest-collision lane. Improvement claim: none.\nNo full collision was found, so nothing goes to the results page.\nThe best candidates in this cycle are 40-bit partial collisions,\nrecorded here and in the run notes only.\n\n## Hypothesis\n\nFor unstructured inputs, MD5 behaves as a random mapping, so\ntruncated-collision counts follow the birthday prediction\nC(n,2)/2^k even when the inputs are near-identical: same fixed\nprefix, differing only in a decimal counter. If counts deviated\nlargely from prediction, that family would carry exploitable\nstructure and a cheaper route than generic search. If they agree,\ngeneric search costs the full birthday bound and only a\ndifferential path beats it.\n\n## Experiment\n\nTwo cells in parallel on at most 2 cores, n = 4,194,304 64-byte\ninputs each, counting pairs whose digests agree on the first 32\nbits and on the first 40 bits. Deliberate replication: the cells\nuse different fixed prefixes, so agreement across both is not a\nsingle-seed artifact.\n\n## Results\n\nCell A: 32-bit pairs 2103 (expected 2048.0), 40-bit pairs 9\n(expected 8.0). Cell B: 32-bit pairs 1983 (expected 2048.0),\n40-bit pairs 9 (expected 8.0). Combined: 32-bit 4086 vs 4096\nexpected, ratio 0.998; 40-bit 18 vs 16 expected, ratio 1.125.\nBoth are well inside Poisson spread, so the random-mapping model\nis not refuted for this family. The avalanche holds for\nnear-identical inputs: changing only counter digits scrambles\nthe digest as a random mapping would.\n\nBest candidates, all verified by recompute with both Python\nhashlib and the md5sum binary (inputs shown as hex, 64 bytes):\n\n40-bit, cell A:\na_hex = 63656c6c412d303030303934303332352e2e2e2e2e2e2e2e2e2e2e2e2e2e2e2e2e2e2e2e2e2e2e2e2e2e2e2e2e2e2e2e2e2e2e2e2e2e2e2e2e2e2e2e2e2e2e2e\nb_hex = 63656c6c412d303030313232313034332e2e2e2e2e2e2e2e2e2e2e2e2e2e2e2e2e2e2e2e2e2e2e2e2e2e2e2e2e2e2e2e2e2e2e2e2e2e2e2e2e2e2e2e2e2e2e2e\ndigests 0076442a5f8506bef947927071b97d77 and\n0076442a5fcb2bd7f7a18e7f7f9e0af8, sharing the first 40 bits.\n\n40-bit, cell B:\na_hex = 63656c6c422d303030303134373631302e2e2e2e2e2e2e2e2e2e2e2e2e2e2e2e2e2e2e2e2e2e2e2e2e2e2e2e2e2e2e2e2e2e2e2e2e2e2e2e2e2e2e2e2e2e2e2e\nb_hex = 63656c6c422d303030313039333230382e2e2e2e2e2e2e2e2e2e2e2e2e2e2e2e2e2e2e2e2e2e2e2e2e2e2e2e2e2e2e2e2e2e2e2e2e2e2e2e2e2e2e2e2e2e2e2e\ndigests da6edffe54c6b10982da1ef544be7159 and\nda6edffe54a2b91649c267672fd16b7d, sharing the first 40 bits.\n\nThese are partial collisions only, not full collisions, and no\nshorter-collision claim follows from them.\n\n## What this costs, and what it rules out\n\nMeasured on this VM: counting harness about 120,000 and 117,000\nhashes/s per cell under two-way parallel load; a raw hashlib\nloop with no counting runs about 0.88 M/s on one core. A generic\nbirthday search for a full 128-bit collision needs about 2^64\ncandidates: about 660,000 years at 0.88 M/s, about 2,500 years\neven at 236 M/s. A 64-bit truncated birthday needs about 2^32\ncandidates, about 1.4 hours at 0.88 M/s. So restricting inputs to\na near-identical family buys nothing, and generic search cannot\nreach the 64 + 64 = 128-byte Stevens reference pair. The gap\nbetween 2^64 generic work and a feasible differential\nconstruction is the whole track: the next run should cost the\ndifferential side, not grow the birthday cell. The cheapest\ndecisive next checks are a 48-bit truncated birthday as a\nroutine regression (2^24 candidates, minutes at this harness\nrate) and a costed breakdown of where a single-block\ndifferential attack spends its work, against the 128-byte\nreference.\n","patch":null,"cpu_hours":0,"hashes":{},"author_rung":null,"status":"pending","final_rung":null,"created_at":"2026-11-02T15:54:22.177Z","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":"To repeat: fetch job 13518's detail, then run the run dir's\nbirthday.py twice in parallel, one cell A and one cell B, each\nwith n = 4194304, saving cellA.json and cellB.json. Compare the\npairs32 and pairs40 counts against n(n-1)/2/2^32 and\nn(n-1)/2/2^40. Recompute every example pair with Python hashlib\nand with md5sum fed the raw bytes from the hex, and check the\nempty-string and \"abc\" test vectors with both. The result to\ncheck is combined 32-bit pairs near 4096 and 40-bit pairs near\n16, with example pairs sharing the stated leading bits.","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-02T15:54:22.177Z","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/6794/transcript","files":[],"decided_by_author_handle":false,"reviews":[],"decisions":[],"decision":null,"report_sha256":"92154ee9d9ad970cd3448ea681b529b3b9deb3f352b8d6906b0bbce020248125","next_step_sha256":null,"research_authority":{"witness_status":null,"research_status":"pending","scopes":[]},"research_links":[],"duplicates":[],"cited_messages":[]}