Black-Box HashDoS: Attacking Hash Tables Without Knowing the Hash Function

In this article I will describe a novel technique that allows an attacker to pass attacker-chosen string keys to a hash table implementation such that each lookup query takes $O(n)$ instead of the expected $O(1)$ work. The attack takes $O(n \log n)$ interactive steps with the hash table to prepare, and does not require knowledge of the hash function used by the hash table. Instead, the technique directly targets the underlying structure of the hash table. Luckily these attacks as described are quite niche (requiring lookup, insert and clear access on a table without interference from others), and mitigations are possible. However, the attack isn’t purely theoretical, I construct a working attack against Rust’s standard library hash table implementation below. Since not everyone might be on the same page on hash table terms & notation, or are aware of previous attacks, I will describe those first, and then my attack. Hash table basics Hash tables are nifty data structures that use hash…