Report: 48-bit truncated Keccak-256 collision (λ = 24)

Answer

collision.json (repository root):

{"algo":"keccak256","lambda":24,"inputA":"identitymd-7412922","inputB":"identitymd-49446283"}

Both inputs are plain UTF-8/ASCII strings with no 0x prefix, so they are read as UTF-8.

Input	Keccak-256 digest
identitymd-7412922	06f8602cde14eaa97a7264115761fc9eebb12fcd6cb8080f1dd6134b7de84bc4
identitymd-49446283	06f8602cde14d101876298776c73b65f60c20eb683748c28de306acd36858d84

The first 48 bits (6 bytes, MSB first) are 0x06f8602cde14 for both inputs. The inputs are different, and the full digests are different at byte 7 and after.

Facts (checked in this session)

1. Hash function. The hash is Keccak-256 with the original Keccak padding (domain byte 0x01, then 0x80 at the end of the 136-byte block). This is the variant Ethereum calls keccak256. Two implementations reproduce the known test vectors:
   • keccak256("") = c5d2460186f7233c927e7db2dcc703c0e500b653ca82273b7bfad8045d85a470
   • keccak256("abc") = 4e03657aea45a94fc7d47ba826c8d667c0d1e6e33a64a036ec44f58fa12d6c45
2. Search. tools/keccak256_birthday.c (C, gcc -O3) hashed the 2^26 strings identitymd-0 … identitymd-67108863. It stored each 48-bit prefix and sorted them to find duplicates. It finished in about 2 min 25 s on 4 cores (single-threaded) and found 5 colliding pairs. The first pair is the one submitted. The other four were:
   • identitymd-51640271 / identitymd-53212469 → 22d143cd1c0f
   • identitymd-32089584 / identitymd-46380380 → 4bbe9d21a877
   • identitymd-33320706 / identitymd-47021571 → 7a2e7927bfa1
   • identitymd-920291 / identitymd-13453043 → 82e59b2eea88
3. Independent check. tools/verify_collision.py is a separate pure-Python Keccak-f[1600] implementation. It computes the round constants with the FIPS 202 LFSR and the rotation offsets with the spec's recurrence, rather than using hard-coded tables. It checks the test vectors above, then loads collision.json, checks its keys and values, decodes both inputs, and confirms that the inputs differ and the 48-bit prefixes match. Output: 48-bit prefixes equal: True.

Inferences

• About 5 collisions is what the birthday bound predicts: with n = 2^26 samples in a space of 2^48, the expected number of pairs is n²/2^49 = 2^52/2^49 = 8. Five is a normal result. Only about 2^24 samples are needed for an even chance, so the run used more than it needed but stayed cheap.
• The C and Python code share no source, and they agree on both test vectors and on both full digests. That makes an implementation error unlikely to be the cause of the match.

Uncertainty / open questions

• Which "keccak256" the verifier uses. I assumed Ethereum-style Keccak-256 (0x01 padding), because that is what the name usually means. If the verifier actually uses NIST SHA3-256 (0x06 padding), this pair does not collide. SHA3-256 gives c4630a5e… and d7490bb6…. Re-running the search with that padding would take about 2 minutes.
• How "truncated to 48 bits MSB" is read. I took it as the first 6 bytes of the standard big-endian digest output. Other readings, such as the low bits or a little-endian word, were not tested.
• Input encoding. I assumed that a string without a 0x prefix is hashed as its UTF-8 bytes, with no trailing newline.

Sources

• FIPS 202, SHA-3 Standard (Keccak-f permutation, round-constant LFSR, rotation offsets): https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.202.pdf
• Keccak team reference / the original Keccak padding (pad10*1 with no SHA-3 domain bits): https://keccak.team/keccak_specs_summary.html
• The test vectors above are the widely published Ethereum keccak256 values. Both local implementations reproduced them, but I did not fetch them from the web in this session.

Reproduce

gcc -O3 -o kb tools/keccak256_birthday.c && ./kb test && ./kb   # ~2.5 min
python3 tools/verify_collision.py collision.json