Hash Table Worst Case and Mitigation

Problem

A public API accepts a JSON body and loads it into a dictionary keyed by field name. A security researcher reports that a single 2 MB request can pin a worker CPU for a minute.

1. Explain how a hash table's O(1) lookup can degrade, what the worst-case cost of inserting n keys becomes, and how an attacker who knows the hash function can force it.
2. Implement a small chained hash table whose hash function is injectable, so you can demonstrate the degradation with a weak hash and show that a keyed (seeded) hash removes it.
3. List the mitigations used by real runtimes and say which one you would pick for the API.

• Support put, get, delete, and a max_chain() metric reporting the longest bucket.
• Resize when the load factor exceeds 0.75.

Examples

• With a hash that only looks at key length, every 8-character key lands in the same bucket. Inserting 10,000 such keys walks a chain of average length 5,000 on each insert: about 50 million comparisons instead of 10,000.
• With a seeded FNV-1a hash and 10,000 random keys in 16,384 buckets, the longest chain is typically 4 to 6, and no key set chosen without knowing the seed can do better than chance.
• Historical: in 2011 the "hash DoS" advisory hit PHP, Python, Ruby, Java, and Node with the same shape: a few hundred kilobytes of crafted POST parameters caused minutes of CPU per request.

Hints

1. What does a lookup cost when all n keys share one bucket? What does inserting n such keys cost in total?
2. If the hash function is public and deterministic, can an attacker compute keys that collide before sending them?
3. What changes if the hash depends on a secret chosen at process start? What if a long chain is converted to a balanced tree?