SIMD-COLLISION:keccak256:24 — 48-bit truncated Keccak-256 collision

Answer

A collision on Keccak-256 truncated to its first 48 bits (MSB) was found:

	input (hex)	keccak256 digest	first 48 bits
inputA	0x8375360100000000	prefix 8851a59bbb9d (full 256-bit digest not printed by the search)	8851a59bbb9d
inputB	0x7131040200000000	prefix 8851a59bbb9d (full 256-bit digest not printed by the search)	8851a59bbb9d

Both inputs are 8-byte messages, distinct, and their digests agree on the first 6 bytes.

Deliverable: collision.json at the repository root:

{"algo":"keccak256","lambda":24,"inputA":"0x8375360100000000","inputB":"0x7131040200000000"}

Method (facts)

• Hash: Keccak-256 with original Keccak padding (0x01), rate 136 bytes, as used by Ethereum. Not NIST SHA3-256 (which uses 0x06).
• Search: birthday attack. Inputs were the 8-byte little-endian encoding of a counter i = 0, 1, 2, …. Each digest's 48-bit prefix was stored in an open-addressing hash table (2^26 slots). The first prefix repeat between two different counters was taken as the collision.
• Implementation: test/scratch/keccak_birthday.c, compiled with gcc -O3 -march=native. Single thread.
• Result: collision after 33,829,234 evaluations (counters 0 through 33,829,233), 1 min 4 s wall time.
• The program recomputed both digests from the inputs and checked that the inputs differ and that their 48-bit prefixes match before reporting.

Verification

• Implementation check (fact): the Keccak-256 routine reproduces the published test vectors:
  • keccak256("") = c5d2460186f7233c927e7db2dcc703c0e500b653ca82273b7bfad8045d85a470 (matches)
  • keccak256("abc") = 4e03657aea45a94fc7d47ba826c8d667c0d1e6e33a64a036ec44f58fa12d6c45 (matches)
• Pair check (fact): the program's output shows both digests with prefix 8851a59bbb9d; the inputs are distinct.
• Not done: an independent second Keccak implementation. pycryptodome could not be installed (no pip), and OpenSSL 3.0.13 here has no Keccak digest. The pair was therefore checked only by the same code that found it, plus the published vectors. The SIMD verifier that recomputes the digests is the independent check the task names; I have not seen its result.

Inferences and uncertainty

• The 2^24 birthday estimate matched the observed cost: a collision is expected after about √(π/2 · 2^48) ≈ 2.1·10^7 evaluations, and 3.4·10^7 is within the usual variance for a single run.
• Whether the SIMD verifier uses the same padding and byte order (8-byte little-endian input, MSB-first truncation) is an assumption. If it hashes the hex as ASCII, or uses NIST SHA3-256, this pair will not verify. The task specifies keccak256 and a hex 0x… input, which I read as raw bytes.
• The collision is a 48-bit truncation collision only. It says nothing about full 256-bit collision resistance, which is untouched.

Unanswered

• Whether the external verifier accepts this pair under its exact input-decoding rule (raw bytes vs. ASCII of the hex string). I did not test that rule against the verifier.

Sources

• Keccak test vectors above are the standard published Keccak-256 values, checked here against the implementation. No web sources were consulted; the padding and rate choices are from the Keccak specification and the Ethereum Keccak-256 convention.