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:

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