# Report: RIPEMD-160 collision truncated to 48 bits (λ=24)

## Answer

| | input (UTF-8) | RIPEMD-160 digest |
|---|---|---|
| A | `idmd-13458001` | `9ff5cb7e7844`b4e20774f357c3ce88d721e7832f |
| B | `idmd-21777228` | `9ff5cb7e7844`b94fb8896a518dd50687714b3a45 |

The inputs are different, and their first 48 bits (`9ff5cb7e7844`) are the same. The 7th
byte is where they first differ (`b4` vs `b9`), so this is a 48-bit collision and not a
longer one.

`collision.json`:
```json
{"algo":"ripemd160","lambda":24,"inputA":"idmd-13458001","inputB":"idmd-21777228"}
```

## Evidence (facts: commands run and what they printed)

1. **Search.** `tools/search.c` (built with `gcc -O2`) hashed `idmd-<n>` for n = 0, 1, 2, …
   and stored the 48-bit prefixes in a hash table. It stopped at the first repeated prefix:
   `idmd-13458001 idmd-21777228 9ff5cb7e7844` after about 21.8M evaluations, in 26 s on a
   single core. Before searching, the program checks its own RIPEMD-160 against the
   published vector RIPEMD-160("abc") = `8eb208f7…0bfc`.
2. **Independent implementation (OpenSSL 3, legacy provider):**
   `printf %s idmd-13458001 | openssl dgst -rmd160 -provider legacy -provider default` gave
   `9ff5cb7e7844b4e20774f357c3ce88d721e7832f`. The same command for `idmd-21777228` gave
   `9ff5cb7e7844b94fb8896a518dd50687714b3a45`.
3. **Pure-Python verifier** (`tools/verify.py`, separate code): it checks the reference
   vectors for `""`, `"abc"` and `"message digest"`. It also produced the same digest as
   OpenSSL for a 1000-byte multi-block input (`aa69deee…e9cf`). Then it reads
   `collision.json`, checks the exact key set, `algo`, `lambda`, and that the inputs are
   distinct, and printed `collision on first 48 bits: True` (exit code 0).

Three implementations agree: the C search code, OpenSSL, and the Python verifier.

Sources for the algorithm and test vectors: the RIPEMD-160 reference page by A. Bosselaers,
https://homes.esat.kuleuven.be/~bosselae/ripemd160.html, and Dobbertin, Bosselaers and
Preneel, "RIPEMD-160: A Strengthened Version of RIPEMD" (FSE 1996). The constants were
written from the specification. Checking against the published vectors and against
OpenSSL is the evidence that they were transcribed correctly.

## Inferences

- The work done (about 2^24.4 hashes) fits the birthday bound. With 48-bit outputs, the
  expected number of hashes before the first collision is √(π/2 · 2^48) ≈ 2^24.3. The
  result therefore needed no cryptanalytic shortcut, which matches the task's cost
  estimate of "about 2^24".
- I assume the verifier interprets "truncated to 48 bits MSB" as the first 6 bytes of the
  standard digest byte string, which is how RIPEMD-160 digests are normally displayed in
  hex. Under that reading the collision holds.

## Uncertainty / unanswered questions

- I could not run the actual "SIMD" verifier, so I cannot confirm how it decodes
  inputs. The inputs are plain ASCII with no `0x` prefix, so a utf8-vs-hex mix-up should
  not be possible.
- If the verifier truncated in a different order (for example, the most significant bits
  of the little-endian word `h0`), the prefixes would differ, and this result is not
  claimed to hold under that convention.
- This result says nothing about the collision resistance of full 160-bit RIPEMD-160.