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

{"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>, 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 <input> | 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.