On (not) using "cryptographic hashes" for hash table keys

Hash tables form the backbone of countless data structures and algorithms across software systems, providing efficient key-value storage and retrieval. At their core, these data structures rely on a hash function ℎ that maps keys to buckets or more complex addressing schemes. The conventional wisdom suggests that cryptographic hashes like SHA-256 would make excellent choices for these hash functions due to their desirable properties. However, this assumption contains a subtle yet critical flaw that can lead to severe vulnerabilities in adversarial environments.

The fundamental purpose of a hash function in a hash table context differs significantly from its cryptographic applications. For typical non-adversarial workloads with naturally distributed inputs, a hash function needs to spread keys evenly across the available buckets. Properties like distribution uniformity and avalanche effect—where a single-bit change in input flips approximately half the output bits—suffice for these scenarios. Cryptographic hashes excel in these aspects, making them seem like natural candidates for hash table implementations.

However, when adversaries can control the input to the hash table, the requirements shift dramatically. Different hash table schemes exhibit specific vulnerabilities that malicious actors can exploit:

• Chained tables degrade when multiple keys hash to the same bucket, creating chains of length Θ(n)
• Open-addressed tables suffer when keys' probe sequences repeatedly collide on the same slots
• Extendible hash tables collapse when many keys share long prefixes, causing exponential directory growth

In each case, the adversary's objective is to construct a set of inputs S such that ℎ(x) for x ∈ S exhibits specific non-uniformity that triggers the hash table's degenerate behavior. The defender's challenge is to make constructing such an S computationally infeasible.

This is where cryptographic hashes like SHA-256 fall short. Their strength lies in properties like collision resistance, preimage resistance, and second-preimage resistance—characteristics that prevent finding different inputs with identical hashes or deriving inputs from given hashes. However, these properties do not guarantee the unpredictability required for adversarial-resistant hash tables.

Consider a service that receives Git objects, computes their SHA-256 hashes, and uses these hashes directly to index an extendible hash table. If an adversary wants to submit 10^6 inputs whose SHA-256 hashes share a 20-bit prefix, they can sample approximately 10^9 public Git objects, filter them for the desired prefix property, and then submit these crafted inputs to the service. This would cause the extendible hash directory to expand with a global depth of at least 20 and a size of at least 2^20, consuming substantial memory and potentially causing denial-of-service.

The solution lies in incorporating unpredictability through secret keys. Hash functions like SipHash, when keyed with a secret unknown to the adversary, provide the necessary unpredictability while maintaining computational efficiency. The approach would involve computing SipHash_k(SHA-256(x)) where k is a secret key. Hashing the digest rather than the original object is acceptable since SHA-256 is injective in practice over typical inputs, and it preserves content-addressing functionality.

Interestingly, SipHash's lack of collision resistance—its 64-bit output makes finding collisions feasible in roughly 2^32 work via the birthday bound—is irrelevant for hash table purposes. Collisions, prefix collisions, and similar events are expected in any hash table implementation and are handled at some cost. What matters is that an adversary cannot deliberately target such collisions without possessing the secret key.

This analysis reveals a fundamental principle in security engineering: cryptographic properties that make a function suitable for one purpose do not automatically transfer to other applications. The "more cryptographic implies more secure" assumption is particularly dangerous in hash table design, where unpredictability through secrecy trumps traditional cryptographic strength.

As software systems increasingly operate in environments where adversaries can manipulate inputs, understanding these distinctions becomes critical. The next time you reach for SHA-256 to implement a hash function, consider whether you're protecting against cryptographic attacks or adversarial manipulation of your hash table's performance characteristics. The appropriate solution may involve a simpler, keyed hash function rather than a complex cryptographic primitive.