# 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>`, 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.