# Report: RIPEMD-160 truncated-collision search (lambda = 24)

## Question

Find two distinct inputs `inputA`, `inputB` such that
`RIPEMD-160(inputA)` and `RIPEMD-160(inputB)` agree on their first 48 bits
(the 6 most significant bytes / 12 leading hex digits), for the task
`SIMD-COLLISION:ripemd160:24`.

## Answer

A collision was found and is delivered as `collision.json`:

```json
{"algo":"ripemd160","lambda":24,"inputA":"0x000000000162a52d","inputB":"0x0000000000de27bb"}
```

Independently recomputed digests (Python `hashlib` / OpenSSL 3.0.13):

| field | value |
|---|---|
| inputA | `0x000000000162a52d` (8 bytes) |
| inputB | `0x0000000000de27bb` (8 bytes) |
| digestA | `18573a938b62ac143bea6201e8a91fb007aa02ad` |
| digestB | `18573a938b62f83d5fd18457e6667947098926a1` |
| shared 48-bit MSB prefix | `18573a938b62` |

The inputs are distinct byte strings; the digests are identical in the
first 48 bits and differ afterwards. Full requirement satisfied.

## Method and evidence

**Method (fact).** Classical birthday search. Expected cost for a 48-bit
target is `sqrt(pi/2 * 2^48) ~= 2^24.3 ~= 17.8M` evaluations. The search
enumerates 8-byte big-endian counter inputs `0, 1, 2, ...` (distinct by
construction), computes RIPEMD-160, and inserts the top 48 digest bits
into an open-addressed table of 2^26 slots (512 MiB) indexed by the low 26
key bits. Tag collisions are confirmed by rehashing the stored candidate
before declaring a result.

**Observed cost (fact).** 23,242,030 hash evaluations, 7.6 s wall-clock
(~3.06 M hashes/s, single thread, `gcc -O3 -march=native`, 2-core VM).
This is within the expected ~1.3x range around the birthday median for a
single run.

**Correctness of the hash implementation (fact).** `src/ripemd160.c` is an
independent implementation written from the RIPEMD-160 specification. It
passes all 9 official Dobbertin/Bosselaers/Preneel test vectors (including
the 1,000,000 x 'a' streaming vector) and produced byte-identical output
to OpenSSL 3.0.13 (`hashlib.new('ripemd160')`) on 300 randomly generated
inputs spanning padding edge cases (lengths 0, 55, 56, 63, 64, 65, ...).

**Independent verification of the collision (fact).** Recomputed with a
different implementation than the search program: `hashlib` (OpenSSL) over
the hex-decoded inputs yields the two digests above; their first 12 hex
chars are equal (`18573a938b62`). Reproduce with:

```
python3 tools/verify_collision.py collision.json
# or: openssl dgst -r -ripemd160  over the raw input bytes
```

**Reproducibility.** `src/collide.c` is deterministic (fixed input
enumeration, no randomness): `bin/collide 26 collision.json` regenerates
the identical pair. Build via `make`; `make check` runs the test vectors
and the verifier.

## Facts vs. inferences vs. uncertainty

- **Fact:** the two digests above, recomputed by two independent
  implementations, share the 48-bit MSB prefix.
- **Fact:** `inputA != inputB` as byte strings.
- **Inference:** the run behaved per the birthday bound (23.2M evals vs.
  ~17.8M expected median ~16.7M); nothing anomalous observed.
- **Assumption (low risk):** "truncated to 48 bits MSB" is taken to mean
  the first 6 bytes of the canonical 20-byte digest encoding, i.e. the
  first 12 characters of the hex digest; "0x..." inputs are hex-decoded to
  raw bytes before hashing, matching the task's stated format.
- **Uncertainty:** none material. The result does not rely on any
  unpublished property of RIPEMD-160 — it is a brute-force birthday
  collision, and verification is a plain recomputation.
- **Unanswered:** whether the verifier also accepts utf-8 inputs — moot,
  since both inputs are delivered as `0x`-prefixed hex as specified.

## Scope limits

Only the truncated 48-bit prefix collides; no claim is made about the
remaining 112 bits (they differ). This is an offline, single-machine
result with no external dependencies beyond a C compiler and Python 3 for
verification.