SHA-256 48-bit Truncated Collision (λ=24)

Question

Find two distinct inputs inputA and inputB such that SHA-256(inputA) and SHA-256(inputB), each truncated to the first 48 bits (6 bytes, MSB-first), are identical. The birthday bound for a 48-bit output space is about sqrt(2^48) = 2^24 ≈ 16.7M evaluations in expectation.

Method (facts, attributable to this run)

• Implementation: test/scratch/collision_search.py (Python 3.12.3, stdlib hashlib).
• Approach: classic birthday/meet-in-the-middle search. Candidate messages are built from a random 8-byte session prefix (from secrets.token_bytes(8)) concatenated with an 8-byte big-endian counter. For each candidate, compute SHA-256(message) and keep only the first 6 bytes (48 bits, MSB-first) as a lookup key in an in-memory hash table. The first key collision between two distinct messages is reported.
• This directly matches the task's definition of the target: "sha256 truncated to the first 48 bits."

Result

• Collision found after 4,667,153 candidate evaluations, in 6.72 s wall-clock on this machine — consistent with (same order of magnitude as) the expected ~2^24 ≈ 16.7M birthday bound; exact counts vary run to run since this is a probabilistic search.
• inputA = 0x0af4d22dc07cc3210000000000005b11
• inputB = 0x0af4d22dc07cc3210000000000473711
• SHA-256(inputA) = 45039b5bef1e42c86170b7ae5d03de6598eb7e22727adc41ef6fa12171825ca0
• SHA-256(inputB) = 45039b5bef1e03c049536447dcf166dbd44aca8a78a04654994a251f9053daae
• Both digests share the same first 6 bytes (48 bits): 45039b5bef1e.
• inputA != inputB (verified: they differ in the trailing 8-byte counter portion, byte-for-byte distinct).

Independent verification performed

In addition to the search script's own in-process check, the result was recomputed in a separate Python process/invocation, decoding the hex strings fresh with binascii.unhexlify and recomputing hashlib.sha256(...).hexdigest() for both inputs, then comparing the first 12 hex characters (48 bits) of each digest. Output:

A input bytes: 0af4d22dc07cc3210000000000005b11
B input bytes: 0af4d22dc07cc3210000000000473711
A != B: True
digest A: 45039b5bef1e42c86170b7ae5d03de6598eb7e22727adc41ef6fa12171825ca0
digest B: 45039b5bef1e03c049536447dcf166dbd44aca8a78a04654994a251f9053daae
trunc48 A: 45039b5bef1e
trunc48 B: 45039b5bef1e
MATCH: True

This confirms the collision is not an artifact of the search script's own bookkeeping.

Deliverable

collision.json at the repository root contains exactly the required shape:

{"algo":"sha256","lambda":24,"inputA":"0x0af4d22dc07cc3210000000000005b11","inputB":"0x0af4d22dc07cc3210000000000473711"}

Inference and uncertainty

• The number of evaluations to find a collision (4.67M) is a single sample from a random process; it is lower than the mean birthday-bound estimate (~16.7M) but well within the expected statistical spread for this kind of search (the distribution of first-collision time is heavy-tailed, and getting a hit well before the mean is unsurprising — not evidence of a weakness in SHA-256 or an error in the search).
• No claim is made about collisions in full (untruncated) SHA-256 — only the 48-bit MSB truncation specified by the task, which is a much weaker target by construction.
• "λ=24" in the task statement is a search-cost exponent (≈2^24 expected evaluations), not the truncation length itself; the truncation length is 48 bits (6 bytes). This distinction mattered during implementation: an initial draft of the search script conflated the two and truncated to 24 bits instead of 48, which produced a cheap but invalid "collision" (only a 24-bit prefix match, not a 48-bit one). That bug was caught by the independent verification step above before producing the final collision.json, and the search was re-run with the corrected 48-bit (6-byte) truncation to produce the result reported here.

Unanswered / out of scope

• No attempt was made to find a collision faster than brute-force birthday search (e.g. via parallelism or SIMD), since the plain search completed in under 7 seconds on standard hardware — well within the task's assumed cost budget.