Report: keccak256 collision truncated to 48 bits (λ=24)

Answer

{"algo":"keccak256","lambda":24,"inputA":"0x00000000007004e7","inputB":"0x00000000016de6f6"}

Input (8 raw bytes, hex)	keccak256 digest
0x00000000007004e7	02649afb324c833597b7b240aee29067ae1ed85092e64569eeaaf3cadd56861f
0x00000000016de6f6	02649afb324c9eef48aff7d4de0563498952e8c85a9f706c8eb25a2c4661eff4

The first 48 bits (0x02649afb324c) are identical. The inputs are distinct, and the digests differ from byte 7 onward, so this is a real truncated collision and not the same input written twice.

Facts (observed directly in this run)

1. The implementation was checked against known vectors. tools/keccak_collide.c selftest produced keccak256("") = c5d24601…5d85a470 and keccak256("abc") = 4e03657a…a12d6c45. These are the standard Ethereum Keccak-256 vectors. With 0x06 padding, the same sponge reproduced Python hashlib.sha3_256 exactly for "" and "abc". That confirms the permutation and rate (136 bytes) are correct.
2. The search found 9 collisions. It hashed the 2^26 inputs 0x0000000000000000 through 0x0000000003ffffff (8-byte big-endian counters), sorted the 48-bit prefixes and found 9 colliding pairs. Wall time was 11.7 s on 32 cores. All 9 pairs are listed in the program output; the first one by prefix order was chosen.
3. A separate library confirmed the chosen pair. The npm package js-sha3 v0.9.3 (keccak256), written independently of this code, gave the same full digests for both inputs. It also gave the correct digest for keccak256("").

Inference

• The expected number of collisions among N = 2^26 random 48-bit values is about N²/2^49 = 8. Finding 9 is consistent with keccak256 behaving like a random function on this truncation. That fits the stated birthday cost of about 2^24 evaluations for a 48-bit output.

Uncertainty and open questions

• Which "keccak256" does the verifier use? I assume the Ethereum/original-Keccak padding (0x01). If the SIMD verifier uses FIPS-202 SHA3-256 instead, this pair is not a collision. I could not check this, because the verifier's source was not available to me.
• How does the verifier parse inputs? I assume 0x… strings are decoded as raw bytes, as the task format suggests ("hex 0x... or utf8"). If they were hashed as UTF-8 text instead, the pair would not collide.
• No external web sources were needed. Every claim above comes from computation that can be reproduced with tools/keccak_collide.c.

Reproduction

gcc -O3 -fopenmp -o kc tools/keccak_collide.c
./kc selftest
./kc search 26          # lists all 9 collisions
./kc hash 0x00000000007004e7
./kc hash 0x00000000016de6f6