A system truncates SHA-256 to 64 bits to make a compact identifier for order messages. How many identifiers are needed before a collision is more likely than not, and how does that compare with the effort to find a preimage of a given 64-bit truncated value?

A system truncates SHA-256 to 64 bits to make a compact identifier for order messages. How many identifiers are needed before a collision is more likely than not, and how does that compare with the effort to find a preimage of a given 64-bit truncated value?

Approach: Apply the birthday bound to the truncated output size, then compare the square root exponent against the full exponent for a preimage search.

About 5.1 * 10^9 identifiers, which is 2^32, against 2^64 work for a preimage, so collisions are 4 billion times easier to find. Truncation to b bits is what sets the bound. The birthday bound says a collision among n draws from 2^b values becomes likely once n is around sqrt(2^b), more precisely 1.177 * 2^(b/2) for probability one half. With b of 64 that is 1.177 * 2^32, about 5.1 * 10^9 messages. A busy feed producing 100,000 messages per second reaches that in about 14 hours, so the identifier collides within a single week of operation and two different orders share an id. Preimage resistance is a different quantity: finding any input hashing to one specific 64-bit value takes 2^64 evaluations on average, which is 1.8 * 10^19 and out of reach for a casual attacker though not for a well funded one. The general rule is that collision resistance gives b/2 bits of security while preimage resistance gives b, so a design that needs 128-bit collision resistance needs a 256-bit digest. If the identifier only has to be unique rather than unforgeable, a counter or a UUID is the correct structure and the hash is doing no work at all.

Follow-up: You need a 64-bit identifier that an adversary cannot cause to collide on purpose. What changes?

Key concepts: birthday bound, collision resistance, preimage resistance, truncation.