# SIMD-COLLISION ripemd160, λ=24 — report ## Question Find two distinct inputs whose RIPEMD-160 digests agree on the first 48 bits (most significant bits first). ## Answer ```json {"algo":"ripemd160","lambda":24,"inputA":"simd-rmd160-8034104","inputB":"simd-rmd160-11290985"} ``` Both inputs are UTF-8 (plain ASCII) strings, hashed as their raw bytes with no trailing newline. The same JSON is in `collision.json` (repository root, committed) and `artifacts/collision.json`. | Input (UTF-8) | Input bytes (hex) | RIPEMD-160 digest | |---|---|---| | `simd-rmd160-8034104` | `0x73696d642d726d643136302d38303334313034` | `43a6458d33f3` `930d4541543a7034250a2073dfcb` | | `simd-rmd160-11290985` | `0x73696d642d726d643136302d3131323930393835` | `43a6458d33f3` `7c7af854f1d2d97be0242ad55be7` | Shared 48-bit prefix: `43a6458d33f3`. The digests differ from bit 49 onward (`93…` vs `7c…`), so this is a truncated collision only, not a full RIPEMD-160 collision. ## Evidence Facts — each was observed in this workspace: - **Search.** `python3 tools/find_collision.py` hashed the 2^25 = 33,554,432 messages `simd-rmd160-`, n = 0 … 2^25−1, and reported 3 colliding pairs: (8034104, 11290985), (12305291, 16044331), (14173627, 31849728). The first is the one delivered. Runtime was about 19 s on 4 cores, and a second run gave the same three pairs. - **Check 1, Python.** `python3 tools/verify_collision.py` re-reads `collision.json`, recomputes both digests with `hashlib` (Python 3.12.3), and printed `OK (48-bit prefix 43a6458d33f3)`. It also checks the key order and that the inputs are distinct. - **Check 2, OpenSSL CLI.** `printf %s | openssl dgst -provider legacy -provider default -ripemd160` (OpenSSL 3.0.13) printed the same two digests as in the table. - **Implementation sanity.** `hashlib.new('ripemd160', b'abc')` returned `8eb208f7e05d987a9b044a8e98c6b087f15a0bfc`, and OpenSSL returned `9c1185a5c5e9fc54612808977ee8f548b2258d31` for the empty input. Both match the published RIPEMD-160 test vectors as I recall them; I did not fetch the specification to confirm. Limit on the evidence: both checks go through the same underlying OpenSSL library on this machine, so they are not two independent implementations. ## Inferences - Finding 3 pairs is in line with the birthday estimate: with N = 2^25 samples and a 48-bit target, the expected number of colliding pairs is about N²/2^49 = 2. This is a consistency check, not a proof of anything. - Using 2^25 rather than the quoted 2^24 evaluations was deliberate: at 2^24 the expected number of pairs is only about 0.5. ## Uncertainty - **Input encoding.** The task allows "hex 0x... or utf8". I assumed a string without a `0x` prefix is hashed as its UTF-8 bytes. The inputs contain non-hex characters (`s`, `i`, `m`, `-`, `r`) and no `0x` prefix, so they cannot be read as hex. If the SIMD verifier requires hex, the equivalent values are in the "Input bytes (hex)" column. - **Truncation convention.** "48 bits MSB" was taken as the first 6 bytes of the digest in standard output order (the first 12 hex characters). - **File location.** The task did not say where `collision.json` should live; it is at the repository root with a copy under `artifacts/`. - **Whitespace.** The file is the exact JSON object, compact, followed by one newline. If byte-exact matching without a trailing newline is required, that byte would need to be removed. ## Unanswered - The SIMD verifier's actual parsing and acceptance behaviour was not available here, so acceptance by it is untested. ## Reproduce ``` python3 tools/find_collision.py # standard library only; rewrites collision.json python3 tools/verify_collision.py # prints both digests and OK/FAIL ``` Requires a Python whose `hashlib` exposes `ripemd160`; no network is needed.