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

Question

Find two distinct inputs whose keccak256 digests are identical in their first 2λ = 48 bits, reading the digest most significant bit first. Return them as collision.json, in the form {"algo":"keccak256","lambda":24,"inputA":"<hex 0x... or utf8>","inputB":"<hex 0x... or utf8>"}. The task requires a genuine collision, because its verifier recomputes the digests.

Answer

collision.json sits at the repository root. An identical copy is in artifacts/collision.json.

{"algo":"keccak256","lambda":24,"inputA":"keccak256-lambda24-0016540872","inputB":"keccak256-lambda24-0061202354"}

	inputA	inputB
JSON value (UTF-8, no 0x prefix)	keccak256-lambda24-0016540872	keccak256-lambda24-0061202354
Bytes hashed (29 each), as hex	0x6b656363616b3235362d6c616d62646132342d30303136353430383732	0x6b656363616b3235362d6c616d62646132342d30303631323032333534
First 48 bits of keccak256	0x85d751916f30	0x85d751916f30

keccak256(inputA) = 0x85d751916f30 9a84a6322c3f72de0ff5f3197c2d0a2baf5715ba06e8de9ef8a3
keccak256(inputB) = 0x85d751916f30 19a0158c47b10fb21d3df6421801d8491d539f05d77aa2c885ec
                      '-48 bits-'  byte 7: 0x9a = 1001 1010 vs 0x19 = 0001 1001, so bit 49 differs

The two digests share exactly 48 leading bits. The same search run found two more valid pairs, listed in E1. Either one could replace this pair.

Evidence

Each item below was run on 4–5 October 2026. The environment is described at the end of the report.

E1. Search run. tools/keccak256_collide.c was built with cc -O3 -pthread and run with default arguments. Verbatim output:

# self-test ok; prefix "keccak256-lambda24-", candidates 2^26 = 67108864, threads 10
# collision 1: first 48 bits 0x85d751916f30
#   keccak256("keccak256-lambda24-0016540872") = 0x85d751916f309a84a6322c3f72de0ff5f3197c2d0a2baf5715ba06e8de9ef8a3
#   keccak256("keccak256-lambda24-0061202354") = 0x85d751916f3019a0158c47b10fb21d3df6421801d8491d539f05d77aa2c885ec
{"algo":"keccak256","lambda":24,"inputA":"keccak256-lambda24-0016540872","inputB":"keccak256-lambda24-0061202354"}
# collision 2: first 48 bits 0xa825d4be8e58
#   keccak256("keccak256-lambda24-0003371655") = 0xa825d4be8e583b410e6d32f26a5fb1a73d11cb0ae83404bc808646b2b02dc8e6
#   keccak256("keccak256-lambda24-0021623425") = 0xa825d4be8e5890f012a2bbc8da0ccfaa4ad7c8b27eff827263d1eff5e2607eff
{"algo":"keccak256","lambda":24,"inputA":"keccak256-lambda24-0003371655","inputB":"keccak256-lambda24-0021623425"}
# collision 3: first 48 bits 0xaa9368a309de
#   keccak256("keccak256-lambda24-0057733290") = 0xaa9368a309dea1548aae3467a978dd887ead99f4e6ec7ab1430cb2215eaf982c
#   keccak256("keccak256-lambda24-0060349179") = 0xaa9368a309dec6bea692e3d930cb36d7e1ea2597fd2d9e0fd32cacd0072fcb27
{"algo":"keccak256","lambda":24,"inputA":"keccak256-lambda24-0057733290","inputB":"keccak256-lambda24-0060349179"}
# hashing 2.06 s, sorting 0.89 s, scan 0.06 s
# collisions found 3, expected n(n-1)/2^49 = 8.00

Before searching, the tool checks five known-answer values. Two are for Keccak-256: "" gives c5d24601…5d85a470 and "abc" gives 4e03657a…a12d6c45. Three are for SHA3-256, the same code with padding byte 0x06: "", "abc", and 200 bytes of 0xa3, which exercises more than one block. Third-party code reproduces all five, as shown in E3 and E4.

E2. Standard-library checker. Command: python3 tools/verify_collision.py collision.json. Exit status 0. Verbatim output:

self-test: ok (SHA3-256 matches hashlib at 10 lengths; Keccak-256 known answers)
inputA = "keccak256-lambda24-0016540872"
  bytes     (29) 0x6b656363616b3235362d6c616d62646132342d30303136353430383732
  keccak256      0x85d751916f309a84a6322c3f72de0ff5f3197c2d0a2baf5715ba06e8de9ef8a3
  sha3-256       0x679dfd1221ea69e085b857e7e758ac37573a5ef14d4f1a9ae3f029932592d5ee  (FIPS 202, for comparison only)
inputB = "keccak256-lambda24-0061202354"
  bytes     (29) 0x6b656363616b3235362d6c616d62646132342d30303631323032333534
  keccak256      0x85d751916f3019a0158c47b10fb21d3df6421801d8491d539f05d77aa2c885ec
  sha3-256       0x0f98ea030f9d52b6ef1211857b10a88bd0903fac0b6e159a91dc973ecbb8d6ba  (FIPS 202, for comparison only)
first 48 bits: A=0x85d751916f30 B=0x85d751916f30
identical leading bits: 48; inputs distinct as bytes: True
RESULT: OK, keccak256 digests agree on their first 48 bits

This checker shares no code with E1. It computes the round constants and rotation offsets from FIPS 202 Algorithms 2, 5 and 6 instead of copying a table, and it applies π in the FIPS 202 form instead of the Keccak team's combined ρπ form. It refuses to judge any claim until its SHA3-256 output matches Python's hashlib.sha3_256 at ten message lengths from 0 to 300 bytes.

E3. Third-party JavaScript (Node v24.21.0). The packages were installed from npm into a scratch directory that is not delivered. Verbatim output:

keccak256("") = 0xc5d2460186f7233c927e7db2dcc703c0e500b653ca82273b7bfad8045d85a470  [5 impls agree: true]
keccak256("abc") = 0x4e03657aea45a94fc7d47ba826c8d667c0d1e6e33a64a036ec44f58fa12d6c45  [5 impls agree: true]
keccak256("keccak256-lambda24-0016540872") = 0x85d751916f309a84a6322c3f72de0ff5f3197c2d0a2baf5715ba06e8de9ef8a3  [5 impls agree: true]
keccak256("keccak256-lambda24-0061202354") = 0x85d751916f3019a0158c47b10fb21d3df6421801d8491d539f05d77aa2c885ec  [5 impls agree: true]
0x-hex forms: inputA=0x6b656363616b3235362d6c616d62646132342d30303136353430383732 inputB=0x6b656363616b3235362d6c616d62646132342d30303631323032333534
first 48 bits: A=85d751916f30 ([email protected]) B=85d751916f30 (@noble/hashes) equal=true
node:crypto sha3-256("") = a7ffc6f8bf1ed76651c14756a061d662f580ff4de43b49fa82d80a4b80f8434a
node:crypto sha3-256("abc") = 3a985da74fe225b2045c172d6bd390bd855f086e3e9d525b46bfe24511431532
node:crypto sha3-256(0xa3*200) = 79f38adec5c20307a98ef76e8324afbfd46cfd81b22e3973c65fa1bd9de31787

The five implementations are:

1. js-sha3 0.13.0, keccak256.
2. js-sha3 0.9.3, keccak256.
3. @noble/hashes 2.4.0, keccak_256.
4. ethers 6.17.0, keccak256 over the UTF-8 bytes.
5. ethers 6.17.0, keccak256 over the 0x-hex string.

ethers computes keccak256 through @noble/hashes, so it is not independent of item 3. The node:crypto lines come from OpenSSL 3.5.8. They confirm the SHA3-256 known answers used in E1.

E4. Third-party Python (pycryptodome 3.24.0). It uses Crypto.Hash.keccak.new(digest_bits=256). Verbatim output:

keccak256('') = 0xc5d2460186f7233c927e7db2dcc703c0e500b653ca82273b7bfad8045d85a470
keccak256('abc') = 0x4e03657aea45a94fc7d47ba826c8d667c0d1e6e33a64a036ec44f58fa12d6c45
keccak256('keccak256-lambda24-0016540872') = 0x85d751916f309a84a6322c3f72de0ff5f3197c2d0a2baf5715ba06e8de9ef8a3
keccak256('keccak256-lambda24-0061202354') = 0x85d751916f3019a0158c47b10fb21d3df6421801d8491d539f05d77aa2c885ec
first 48 bits equal: True 85d751916f30 | first 52 bits equal: False
hashlib sha3_256(0xa3*200) = 79f38adec5c20307a98ef76e8324afbfd46cfd81b22e3973c65fa1bd9de31787

E5. Independent recount of the search. A scratch script rehashed every candidate with pycryptodome and found duplicates with numpy sorting, sharing no code with E1:

• Default set, 2^26 candidates. It found the same 3 colliding values with the same index pairs as E1: 0x85d751916f30 at [16540872, 61202354], 0xa825d4be8e58 at [3371655, 21623425], and 0xaa9368a309de at [57733290, 60349179].
• Prefix big-a-, 2^28 candidates. It found 111 colliding values, and E1's tool also reported 111.

E6. The checker rejects false claims. Each case below was run through tools/verify_collision.py.

Case	Claim	Result
hex_ok	both inputs given in 0x-hex form	OK, exit 0
mixed_ok	inputA as UTF-8, inputB as 0x-hex	OK, exit 0
same	inputA = inputB	FAIL, exit 1
samebytes	0xABCD vs 0xabcd: different strings, same bytes	FAIL, exit 1
nocoll	inputA of this pair with inputA of pair 2	FAIL, exit 1
lambdastr	"lambda":"24" given as a string	FAIL, exit 1
algo	"algo":"sha3-256"	FAIL, exit 1
extra	an extra key "note"	FAIL, exit 1
lambda25	λ = 25, so 50 bits must match	FAIL, exit 1: only 48 bits agree

E7. Collision counts against the random-function expectation. Among n candidates there are n(n−1)/2 pairs. Each matches on 48 bits with probability 2^−48, so the expected count is n(n−1)/2^49. That is 8 at n = 2^26 and 128 at n = 2^28.

Runs	Collisions found	Expected	z
Exploratory, 9 runs at 2^26, including E1	3, 6, 9, 8, 6, 13, 6, 4, 9: total 64	72	−0.94
Exploratory, 7 runs at 2^28	108, 111, 113, 124, 122, 128, 129: total 835	896	−2.04
Fixed in advance: 20 runs at 2^28, prefixes fresh-00- to fresh-19-, total reported whatever it came out to	106, 133, 135, 124, 137, 133, 136, 145, 132, 104, 124, 115, 113, 128, 125, 111, 133, 137, 122, 145: total 2538	2560	−0.43

E8. Constants. A script compared three sources of the constants:

• the tables in tools/keccak256_collide.c;
• the tables on the Keccak team's specification summary [S2];
• the values tools/verify_collision.py derives from FIPS 202 Algorithms 2, 5 and 6 [S1].

All 24 round constants and all 25 rotation offsets agree across the three.

E9. Reproducibility. I rebuilt the tool from tools/keccak256_collide.c and ran it twice, once with 10 threads and once with 3. Apart from the header and timing lines, both outputs are identical to E1. The first JSON line of the 3-thread run matches collision.json byte for byte (cmp). The 2^26 table took 5.89 s to hash on 3 threads.

Method and cost

1. Candidates. Candidate i is keccak256-lambda24- followed by i as a 10-digit zero-padded decimal, for 0 ≤ i < 2^26. Every candidate is 29 bytes, which fits in one 136-byte rate block, so each costs one Keccak-f[1600] call.
2. Packing. Each candidate's first 48 digest bits go into a 64-bit word, above the low 16 bits of i. The 2^26 words take 512 MiB, plus the same again as sort buffer.
3. Sort and scan. An LSD radix sort on the digest bits puts equal prefixes next to each other, and a linear scan reports them. This is Yuval's store-and-match birthday attack [S7, Algorithm 9.92], with a sort in place of a hash table.
4. Index recovery. For each colliding word, the full index is found by rehashing the 2^10 candidates that share its stored low 16 bits.
5. Cost. The table took 2^26 hash evaluations. Recovery added 6 × 1024 more. Wall time was about 3 s on 10 threads (E1).
6. Why 2^26. n = 2^24 is the order-of-magnitude birthday figure from HAC Fact 9.33 [S7] and the task, but it expects only about 0.5 collisions, so one or more appears with probability only about 39%. At n = 2^26 the expected count is 8, and the chance of finding none is e^−8 ≈ 0.03%.

Facts

These are directly observed or quoted, and each can be reproduced from the evidence and sources cited.

• F1. Under Keccak-256, both inputs' digests begin with the same 48 bits, 0x85d751916f30, and first differ at bit 49 [E1–E4]. Keccak-256 here means rate 1088 bits, capacity 512, first padding byte 0x01.
• F2. The two inputs are distinct, both as JSON strings and as byte sequences [E2, E6].
• F3. Five separate code bases computed the same two digests [E1–E4]:
  • two written for this task, in C and in Python;
  • three third-party: pycryptodome, js-sha3 (in two releases two and a half years apart), and @noble/hashes. ethers delegates to @noble/hashes.
• F4. Under FIPS 202 SHA3-256, the same inputs do not collide. 0x679dfd12… and 0x0f98ea03… differ from the first byte [E2].
• F5. The 0x-hex encodings of the two inputs give the same digests as the UTF-8 strings [E3, E6].
• F6. The search tool's collision counts were exact on both candidate sets that were recounted independently [E5]. On the batch fixed in advance, the count matched the random-function expectation, 2538 against 2560 [E7].
• F7. What the sources say:
  • FIPS 202 defines SHA3-256(M) = KECCAK[512] (M || 01, 256). It states that the SHA-3 hash functions "differ slightly from the instances of KECCAK that were proposed for the SHA-3 competition", namely that "a two-bit suffix is appended to the messages" [S1, Sec. 1 and 6.1]. Its byte-level padding for the hash functions is M || 0x06 || 0x00 … || 0x80 [S1, App. B.2, Table 6].
  • The Ethereum Yellow Paper uses "the Keccak-256 hash function (as per version 3 of the winning entry to the SHA-3 contest by Bertoni et al. [2011], rather than the final SHA-3 specification)" [S3, Sec. 3].
  • Solidity's keccak256 "compute[s] the Keccak-256 hash of the input" [S4].
  • PyCryptodome describes FIPS 202 SHA-3 as "incompatible to Keccak" [S5].

Inferences

These are reasoned from the facts and sources. None was checked against the task's own verifier.

• I1. The task's "keccak256" means the original Keccak-256, with first padding byte 0x01. That is the name Ethereum and Solidity use for it [S3, S4], and every library tested under the name keccak256 or keccak_256 computes it [E3, E4]. The 0x01 byte follows from the Keccak team's padding formula d = 2^|Mbits| + … [S2]: the competition version appends no suffix, so |Mbits| = 0 and d = 0x01. The tested libraries agree with this.
• I2. The verifier will read both inputs as UTF-8. The task's format is "hex 0x... or utf8", and neither input starts with 0x. Both inputs also contain characters outside [0-9a-f] (k, l, m, -), so they could not be read as hex even by a parser that guesses hex without a prefix.
• I3. "Truncated to 48 bits MSB" means the first 6 bytes of the 32-byte digest, in the byte order every tested library prints.
• I4. This is a generic birthday result for a 48-bit truncation [S7, Fact 9.33], and it shows nothing about full-length Keccak-256. FIPS 202 lists 128-bit collision strength for SHA3-256 [S1, App. A.1, Table 4]. Keccak-256 uses the same permutation and capacity, and PyCryptodome says "the security principles and margins remain the same" [S5].
• I5. The exploratory runs came out 2σ low (E7), and that was chance. The tool's counts were exact where recounted (E5), and the batch fixed in advance matched expectation (z = −0.43).
• I6. In index order, the earliest collision is pair 2, which completes at candidate 21,623,425, about 2^24.37. So a sequential search that stopped at its first collision would have used about 1.29 × 2^24 hashes. That is close to the textbook expectation of √(πN/2) ≈ 1.25 × 2^24 for N = 2^48. I derived that estimate myself; it is not taken from the sources below.

Uncertainty

• U1. Keccak variant. The task's verifier might compute FIPS 202 SHA3-256 under the name "keccak256". Python's hashlib documentation, for instance, calls its sha3_256 constructor "SHA3 (Keccak)" [S6], yet hashlib.sha3_256(b"") returns a7ffc6f8…, the FIPS 202 value. If so, this pair fails (F4). A pair valid under both functions would need to satisfy a 96-bit condition, about 2^48 work. I did not attempt it.
• U2. Input decoding. The verifier might hex-decode every input regardless of prefix. If so, these UTF-8 inputs would be rejected. Their hex forms are in the Answer table, but collision.json can carry only one form.
• U3. Self-run checks. The agent that produced the answer also ran every check, so under the task's rules they carry no independent authority. The third-party packages came from npm and PyPI without signature verification. js-sha3 resumed releases in July–August 2026 after a gap of more than two years. Two things reduce this risk: no installed package has install-time scripts, and the result was also checked against js-sha3 0.9.3 from December 2023 and against code bases unrelated to js-sha3.
• U4. PDF quotations. Quotations from FIPS 202, the Yellow Paper and HAC are taken from text extracted locally with pypdf from the retrieved files. Spacing artefacts introduced by extraction, such as "SHA -3", were normalised.

Unanswered questions

• Q1. The task does not say which implementation its verifier ("SIMD") uses. Its Keccak variant, input decoding, and any limits on input length are unknown, and none of this could be observed from this workspace. Both inputs are 29 bytes, equal in length and within one block, in case that matters.
• Q2. The task does not say whether the verifier prefers hex or UTF-8 when both are allowed.
• Q3. It is unclear whether a pair valid under both Keccak-256 and SHA3-256 is expected. It was not attempted at roughly 2^48 work.

Sources

All sources were retrieved 4–5 October 2026. SHA-256 fingerprints are given for the files as retrieved.

• [S1] NIST, FIPS 202: SHA-3 Standard: Permutation-Based Hash and Extendable-Output Functions, August 2015.
  • URL: https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.202.pdf (doi:10.6028/NIST.FIPS.202). PDF sha256 1592607831ff0908cc590632ce371c6c95e94025bb1a0c8ae90a4d0ec1ed025e.
  • Used: Sec. 1; Sec. 3.2.2 (Algorithm 2); Sec. 3.2.3 (π); Sec. 3.2.5 (Algorithms 5–6); Sec. 5.2 (KECCAK[c] = SPONGE[KECCAK-p[1600, 24], pad10*1, 1600 – c]); Sec. 6.1; App. A.1, Table 4; App. B.2, Table 6.
  • Status at https://csrc.nist.gov/pubs/fips/202/final: still the August 2015 final. A planning note dated 03/13/2025 says NIST "has decided to update this publication", and it records a typo in non-normative Appendix B, Algorithm 10, which none of the sections above relies on.
• [S2] Keccak team, "Keccak specifications summary".
  • URL: https://keccak.team/keccak_specs_summary.html.
  • Used: the round pseudo-code (B[y,2*x+3*y] = rot(A[x,y], r[x,y])), the padding pseudo-code, Table 1 (round constants), Table 2 (rotation offsets), and Table 3 (SHA3-256: r = 1088, c = 512, Mbits = 01, d = 0x06).
• [S3] G. Wood, Ethereum: A Secure Decentralised Generalised Transaction Ledger, Shanghai version efc5f9a, 2025-02-04, Sec. 3 "Conventions".
  • URL: https://ethereum.github.io/yellowpaper/paper.pdf. PDF sha256 d67c009c5d5a0542c8288aee3c4d470b3e2dbe6e664f72f00011543608477fa9.
• [S4] Solidity documentation (0.8.38-develop), "Units and Globally Available Variables", Mathematical and Cryptographic Functions.
  • URL: https://docs.soliditylang.org/en/latest/units-and-global-variables.html.
  • Also states: "There used to be an alias for keccak256 called sha3, which was removed in version 0.5.0."
• [S5] PyCryptodome documentation, "Keccak".
  • URL: https://pycryptodome.readthedocs.io/en/latest/src/hash/keccak.html.
  • The page header reads "PyCryptodome 3.23.0 documentation"; the installed package was 3.24.0.
• [S6] Python 3.14.8 documentation, hashlib.
  • URL: https://docs.python.org/3/library/hashlib.html.
  • The note reads: "Added in version 3.6: SHA3 (Keccak) and SHAKE constructors sha3_224(), sha3_256(), …"
• [S7] A. Menezes, P. van Oorschot, S. Vanstone, Handbook of Applied Cryptography, CRC Press, 1996, Chapter 9.
  • URL: https://cacr.uwaterloo.ca/hac/about/chap9.pdf. PDF sha256 f203be51f8ddd0c2272c4a57130ea80f53e5fb8c7610ca879d20f9fe0c4a5c7e.
  • Fact 9.33: a birthday attack "allows colliding pairs of messages x, x′ with h(x) = h(x′) to be found in about 2^{n/2} operations".
  • §9.7.1 and Algorithm 9.92 (Yuval's birthday attack).

Reproduce

cc -O3 -pthread -o keccak256_collide tools/keccak256_collide.c
./keccak256_collide                              # prints E1; ./keccak256_collide PREFIX LOG2N THREADS for other runs
./keccak256_collide | grep -m1 '^{' > collision.json
python3 tools/verify_collision.py collision.json # prints E2, exit status 0

# third-party spot checks
pip install pycryptodome
python3 -c 'from Crypto.Hash import keccak; [print(keccak.new(digest_bits=256, data=s.encode()).hexdigest()) for s in ("keccak256-lambda24-0016540872", "keccak256-lambda24-0061202354")]'
npm install js-sha3
node -e 'const {keccak256}=require("js-sha3"); for (const s of ["keccak256-lambda24-0016540872","keccak256-lambda24-0061202354"]) console.log(keccak256(s))'

Environment

• Machine. Apple M1 Max, 10 cores, 32 GiB RAM, macOS (Darwin 27.0.0, arm64).
• Compilers and runtimes. Apple clang 21.0.0 (clang-2100.3.34.2), Python 3.9.6, Node v24.21.0 with OpenSSL 3.5.8.
• Scratch-only packages. pycryptodome 3.24.0, numpy 2.0.2, pypdf, js-sha3 0.13.0 and 0.9.3, @noble/hashes 2.4.0, ethers 6.17.0. None of them is needed to build or run anything in the repository.