# SIMD-COLLISION: keccak256, λ=24 (48-bit truncation)

## Question
Find two distinct inputs `inputA` and `inputB` such that `keccak256(inputA)` and
`keccak256(inputB)`, each truncated to the first 48 bits (6 bytes, MSB-first), are
identical.

## Answer (fact)
A collision was found:

- `inputA` = `collision-input-26889896` (UTF-8)
- `inputB` = `collision-input-27496353` (UTF-8)
- Truncated-48-bit digest (both): `243bb7fb00b8`

Full (untruncated) Keccak-256 digests, for reference:

```
keccak256("collision-input-26889896") = 243bb7fb00b8be896a8c53f462e1231b112b6b58e6d79dabbc010efcf09e9e00
keccak256("collision-input-27496353") = 243bb7fb00b82a0e30071d0386232cd1be965333eb9980d59763867c9a952e22
```

The first 6 bytes (`243bb7fb00b8`) match; the remaining 26 bytes differ, and the two
inputs are byte-for-byte distinct. This satisfies the task's exact requirement: match
on the 48-bit MSB truncation, distinct inputs, no shortcuts (e.g. reusing one hash as
the other's preimage, or a zero-length/empty-string trick).

Result file: `collision.json` at the repository root (also reproduced in this report).

## Method (fact)
A birthday-attack search was run: candidate inputs `"collision-input-" + i` for
increasing integer `i` were hashed with Keccak-256 (Ethereum's variant, 0x01 padding —
not NIST SHA3's 0x06 padding, which is a different, incompatible function). Each
48-bit truncated digest was inserted into an open-addressing hash table (a
`Float64Array`/`Int32Array` pair, 2^26 slots, linear probing) keyed on the 48-bit
value, so a collision is detected as soon as a second input maps to an
already-occupied slot with a matching key.

- Implementation: Node.js (`v24.21.0`) + the `js-sha3` npm package (pure-JS Keccak,
  not SHA3) for the search; the result was independently cross-checked against the
  `keccak` npm package (native C bindings, the implementation used by `ethereumjs`/
  web3 tooling).
- Sanity check before trusting either library: both reproduce the well-known Ethereum
  test vector `keccak256("abc") = 4e03657aea45a94fc7d47ba826c8d667c0d1e6e33a64a036ec44f58fa12d6c45`.
- Search cost: the collision was found after **27,496,354 evaluations**, in about
  145 seconds on this machine. The task's stated expected cost is ~2^24 ≈ 16.8M
  evaluations; the birthday paradox's expected number of draws before a first
  collision in a 48-bit space is actually ≈1.2533·sqrt(2^48) ≈ 21.0M, with substantial
  run-to-run variance, so 27.5M is a plausible draw from that distribution, not an
  anomaly.
- Scripts used for the search and cross-verification live under `test/scratch/`
  (`find_collision.js` — an initial attempt that hit V8's `Map` size ceiling around
  16.7M entries and was abandoned; `find_collision2.js` — the typed-array version
  that succeeded). Per the task's own rules, `test/scratch/` is not part of the
  submitted deliverable and is excluded before verification.

## Verification performed (fact)
Independently, outside the search loop, both `js-sha3` and `keccak` (native bindings)
were asked to hash `inputA` and `inputB` fresh and were confirmed to agree with each
other and to produce matching 48-bit prefixes:

```
js-sha3  trunc48(inputA) = 243bb7fb00b8
js-sha3  trunc48(inputB) = 243bb7fb00b8
keccak   trunc48(inputA) = 243bb7fb00b8
keccak   trunc48(inputB) = 243bb7fb00b8
inputA !== inputB        = true
```

## Inference
Because two independently-maintained Keccak-256 implementations (one pure JS, one
native-code bindings commonly used in Ethereum tooling) agree on both digests and both
pass the standard `"abc"` test vector, the collision is very unlikely to be an artifact
of a library bug rather than a genuine property of Keccak-256 truncated to 48 bits.

## Uncertainty / unanswered questions
- This report's own verification used the same two JavaScript-ecosystem libraries for
  cross-checking; it was not re-verified against a third, differently-sourced
  implementation (e.g. a C or Rust reference). The task states the authoritative check
  is performed by a separate SIMD verifier, which is the stronger, independent
  confirmation this report cannot itself provide.
- No cryptographic significance is claimed beyond the stated task: finding a 48-bit
  truncated collision is expected and easy (2^24-ish work) precisely because 48 bits is
  far short of Keccak-256's full 256-bit security; this says nothing about the
  collision resistance of un-truncated Keccak-256.