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

Answer

{"algo":"keccak256","lambda":24,"inputA":"imd-9804673","inputB":"imd-17368822"}

Both inputs are UTF-8/ASCII strings (they have no 0x prefix).

Input	keccak256 digest
imd-9804673	2f72fe059bc2493e489ac23cd5bb0119eee739455c6ba49cfd31f75a2b7be703
imd-17368822	2f72fe059bc2f734345293e1223f429e97aea53934f75f186ac1c57ca5f1d550

The shared 48-bit prefix is 0x2f72fe059bc2. The inputs are distinct.

Facts (observed and reproducible)

1. tools/collide.c hashed the strings imd-0, imd-1, … and stored each 48-bit prefix in a hash table. The first repeated prefix appeared after 17,368,823 evaluations (≈2^24.05). The run took about 21 seconds on a single core.
2. The C implementation reproduces the standard keccak256 test vectors. keccak256("") gives c5d24601…5d85a470, and keccak256("abc") gives 4e03657a…a12d6c45. Its self-test passes before the search starts.
3. tools/verify.py is a second, independently written pure-Python Keccak. It derives the round constants and rotation offsets from the specification's LFSR and recurrence instead of copying tables. It passes the same two vectors and recomputes both digests above. Its output is COLLISION OK with exit code 0.
4. For contrast, hashlib.sha3_256(b"imd-9804673") gives e4d8b7ee…. So FIPS-202 SHA3-256 is a different function, and this pair is not claimed to collide under it.

Inferences

• The evaluation count fits the birthday bound. For a 48-bit output, the expected number of draws before the first collision is about √(π/2 · 2^48) ≈ 2.1·10^7, and 1.74·10^7 is well within the normal spread. This fits keccak256's prefix behaving like a random function. It is not evidence of any structural weakness.
• Two independent implementations agree, and both match the known vectors. So the collision is very likely to hold under any correct keccak256 implementation, including the SIMD verifier.

Uncertainty and open questions

• Which function the verifier uses: I assumed "keccak256" means Ethereum-style Keccak-256 (padding byte 0x01). If the verifier uses SHA3-256 (padding 0x06), this pair would fail. I did not search for a SHA3-256 collision.
• How inputs are decoded: I assumed strings without 0x are hashed as their UTF-8 bytes, as the task format suggests. Plain ASCII was chosen to avoid any encoding ambiguity.
• Library cross-check: No external library (pycryptodome, eth-hash) was installed, so neither check uses one. Both checks are code written for this task, anchored only to the published test vectors.

Sources

• Keccak team, The Keccak reference, v3.0 (https://keccak.team/files/Keccak-reference-3.0.pdf). Source for the Keccak-f[1600] round function, the round-constant LFSR, and the ρ offsets.
• NIST FIPS 202 (https://doi.org/10.6028/NIST.FIPS.202). Defines the SHA3-256 domain-separation padding (0x06) that distinguishes it from Keccak-256.
• The test vectors for "" and "abc" are the widely published Ethereum keccak256 values, for example Ethereum's empty-code hash 0xc5d2…a470. They are hard-coded in both tools.