Demonstrate the birthday bound: truncate SHA-256 to 24 bits, search deterministically for a collision, then spend the same budget hunting a preimage and fail.

Answer

import hashlib def h24(msg): return hashlib.sha256(msg).hexdigest()[:6] seen = {} trials = 0 for i in range(1 << 20): msg = b'invoice-%d' % i trials += 1 d = h24(msg) if d in seen: print('collision after', trials, 'hashes') print(seen[d].decode(), 'and', msg.decode(), 'both hash to', d) break seen[d] = msg target = h24(b'invoice-1') found = None for i in range(trials): if h24(b'guess-%d' % i) == target: found = i break print('preimage of', target, 'after', trials, 'hashes:', found) print('birthday bound 2^12 =', 2 ** 12, 'preimage bound 2^24 =', 2 ** 24)

Stallings & Brown, Computer Security 5e, ch2 §2.2; ch21 §21.1