# SHA-256 (λ=24, 48-bit truncation) Collision — Report

## Task

Find two distinct inputs `inputA` and `inputB` such that `SHA-256(inputA)` and
`SHA-256(inputB)`, each truncated to the first 48 bits (most-significant bits
of the digest), are identical. Birthday-bound cost for a 48-bit output space
is on the order of 2^24 (~16.8M) hash evaluations.

## Method (facts — directly observed from this run)

- Implementation: `test/scratch/find_collision.js`, run under Node.js v24.21.0
  (`node --max-old-space-size=2048 test/scratch/find_collision.js`).
- Search strategy: classic birthday attack. Inputs were generated as UTF-8
  strings `"collision-" + counter` for `counter = 0, 1, 2, …`. Each input was
  hashed with Node's built-in `crypto.createHash('sha256')`, and the first 6
  bytes (48 bits) of the 32-byte digest, interpreted MSB-first, were used as
  the truncated digest.
- Deduplication structure: an open-addressing hash table (`Float64Array` keys
  sized to exactly hold a 48-bit value without precision loss, `Int32Array`
  values holding the counter) with 2^26 (67,108,864) slots, linear-probed.
  Each new truncated digest was looked up; an exact match against an existing
  stored 48-bit value (with a different counter) was treated as a collision.
- Result: a collision was found after **40,900,436** total trials (counters
  0 through 40,900,435 inclusive), in **82.88 seconds** of wall-clock time on
  this machine (~493,000 hashes/sec sustained). This trial count is within
  the expected order of magnitude for a 2^24-cost birthday search (the
  expected trial count for a 50% success probability is ≈1.25·sqrt(2^48) ≈
  20.97M; 40.9M is roughly 2x that, i.e., well within normal variance for a
  probabilistic search — no attempt was artificially inflated or retried
  with a different seed).

## Result (facts)

```
inputA = "collision-31148703"   (UTF-8, 19 bytes)
inputB = "collision-40900435"   (UTF-8, 19 bytes)

SHA-256(inputA) = 07afc2c97a1364f16ac87a1246b74e13c7d5bc72ebb724606e3b9770e3e4c686
SHA-256(inputB) = 07afc2c97a1354db22932ced05fe0302aeffb802924c5241cdf84dbcc8acc7dc

First 48 bits (6 bytes, MSB) of both digests = 07afc2c97a13
```

`inputA != inputB` (distinct strings/byte sequences), and the two full
SHA-256 digests differ after the 48-bit prefix (as expected — only the
truncated prefix is required to match).

## Independent verification (facts)

The Node.js computation was cross-checked with a second, independent tool
chain to rule out a bug in the search script itself:

- The two input strings were written to raw files (`test/scratch/inputA.bin`,
  `test/scratch/inputB.bin`) via `printf '%s'`, with no trailing newline.
  `wc -c` confirmed both files are exactly 18 bytes, matching the 18-character
  length of each UTF-8 string (`"collision-" ` = 10 chars + 8 digits), so the
  on-disk bytes are exactly the bytes that were hashed in-memory by Node — no
  encoding or truncation discrepancy.
- `Get-FileHash -Algorithm SHA256` (PowerShell, backed by .NET's
  `System.Security.Cryptography.SHA256`, an independent SHA-256
  implementation from Node's OpenSSL-backed `crypto` module) was run against
  both files:

  ```
  inputA.bin -> 07AFC2C97A1364F16AC87A1246B74E13C7D5BC72EBB724606E3B9770E3E4C686
  inputB.bin -> 07AFC2C97A1354DB22932CED05FE0302AEFFB802924C5241CDF84DBCC8ACC7DC
  ```

  These match the Node-computed digests exactly (case-insensitive hex), and
  the first 12 hex characters (48 bits) are identical between the two
  (`07AFC2C97A13` == `07AFC2C97A13`). This is a genuine, reproducible 48-bit
  truncated SHA-256 collision, confirmed by two independent SHA-256
  implementations (OpenSSL via Node vs. .NET via PowerShell).

## Deliverable

`collision.json` (repository root):

```json
{"algo":"sha256","lambda":24,"inputA":"collision-31148703","inputB":"collision-40900435"}
```

## Inferences

- The ~40.9M trial count (vs. the ~16.8–21M "textbook" birthday expectation)
  is consistent with normal statistical variance in a probabilistic birthday
  search, not evidence of an implementation flaw — the independent
  cross-check (different hash implementation, different tool) found the same
  digests, which would not happen if the Node-side truncation/comparison
  logic were buggy.
- Because inputs were drawn from a simple counter-based namespace
  (`"collision-" + n`), this collision is specific to that generation
  scheme; it is not a general-purpose SHA-256 weakness and says nothing
  about full (untruncated) SHA-256, which remains collision-resistant at its
  full 256-bit output length.

## Uncertainty / unanswered questions

- No formal proof is offered (nor possible) that this is the *lowest-cost*
  collision findable; it is simply the first one encountered by this
  particular search order. A different counter-generation order or seed
  would very likely find a different, equally valid collision at a
  different trial count.
- The runtime (~83s, ~493K hashes/sec) is specific to the machine this was
  executed on; it is reported as a fact about this run, not a general
  performance claim about Node.js SHA-256 throughput on other hardware.

## Reproduction

```
node --max-old-space-size=2048 test/scratch/find_collision.js
```

(Script and raw intermediate output are preserved under `test/scratch/` for
this session; per task instructions, `test/scratch/` is not part of the
delivered scope and is discarded before submission — the facts above are
self-contained and independently reproducible by re-running the same
counter-based search.)