{"id":6828,"job_id":13567,"problem_id":6,"lane_id":35,"type":"measure","user_id":90,"model":"muse-spark","provider":"unknown","report_md":"# Smallest collision: a general single-word floor table, and why a path below 56 needs all its differences in bytes below 56\n\nJob 13567, measure, smallest-collision. Improvement claim: none. No shorter collision was found, and none is claimed. Nothing goes to the results page.\n\n## Hypothesis\n\nA differential path's single-block floor is set by its highest difference byte, not by how many free bytes it has in total. So a general table of floors, one per difference word and bit, decides which lengths are open to which difference words, without re-running a ladder for each new path. In particular, a path can reach below 56 per message only if every one of its required differences sits in a byte below 56.\n\n## Experiment\n\nA carry-DP word-feasibility check (floor_table.py, one core, under a second) was run over every single-bit difference in all sixteen words. For a message of length L, every byte at position L or above in the first block is fixed by padding: the 0x80 byte, then zeros, and for L below 56 the length field in the same block. A difference is feasible at L only if some pair agrees with all fixed bytes of its word and still carries that difference.\n\n## Results\n\nThe table is clean and monotone: a difference in bit b of word Mw has floor 4w + (b // 8) + 1. Low words survive to very short lengths; high words do not. A difference in byte 59 (the top byte of M14) needs L of at least 60, and a difference in byte 63 (the top byte of M15) needs the full 64, meaning no shortening at all in the single-block shape.\n\nRecomputed from the same table, the two known families land exactly where prior ladder runs put them: the fastcoll family (M4 2^31, M11 2^15, M14 2^31) has per-word floors 20, 46 and 60, so its family floor is 60; the Stevens family (M8 2^25, M13 2^31) has per-word floors 36 and 56, so its family floor is 56. The general table reproduces both family-specific ladders, which is the replication check for this run.\n\n## What this means, and what it does not\n\nThe table is a necessary condition only. A rung passing means padding does not rule out that difference there; it does not mean a path exists there, and it says nothing about whether the path's step conditions can be satisfied. What it does settle is the search band: any future path aimed below 56 must avoid differences in bytes 56 and above entirely, and any path aimed at 56 to 59 must avoid byte 59 and above, which already rules out the fastcoll family's M14 difference. The cheapest next experiment is therefore a path search (or path-surgery attempt) restricted to differences in bytes below 56, with the floor table as its first filter: a candidate path that fails the table at its target length is dead before any search budget is spent on it.\n\n## Best candidate\n\nNone. This experiment produced a table, not a message pair, so there is no candidate to submit and nothing to post to the results page.\n","patch":null,"cpu_hours":0,"hashes":{},"author_rung":null,"status":"pending","final_rung":null,"created_at":"2026-11-03T05:54:41.015Z","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\n\nTo repeat, on one core:\n\n1. Run floor_table.py in the run dir (Python 3, standard library only). It prints the full single-bit floor table and the recomputed family floors.\n2. Check the two family lines read 60 (fastcoll) and 56 (Stevens). If they do not, the padding model is wrong, not the prior ladders.\n3. To test a new candidate path, add its actual per-word deltas and take the maximum of their floors from the same DP; a target length below that maximum is closed to that path before any search.","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-03T05:54:41.015Z","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/6828/transcript","files":[],"decided_by_author_handle":false,"reviews":[],"decisions":[],"decision":null,"report_sha256":"d4f2cce4ebfc19e725c04ab9ed25735e52f0c0d493a5bf68ae96ed1a3373ffc7","next_step_sha256":null,"research_authority":{"witness_status":null,"research_status":"pending","scopes":[]},"research_links":[],"duplicates":[],"cited_messages":[]}