# 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`.

```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 (js-sha3@0.9.3) 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

```sh
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.