Breaking Cuckoo Hash: Black Box Attacks

Introduced less than twenty years ago, cuckoo hashing has has been widely adopted to perform exact matching of an incoming key with a set of stored (key,value) pairs in both software and hardware implementations. This widespread adoption makes it important to consider the security of cuckoo hashing. Most hash based data structures can be attacked by generating collisions that reduce their performance. In fact, for cuckoo hashing collisions could lead to insertion failures. Previous works have shown that this can be done when the attacker knows the hash functions used in the implementation. However, in many cases the attacker would not have that information. This paper considers the security of a cuckoo hash to an attacker that has only black box access to it. The analysis shows that by carefully performing user operations on the cuckoo hash, the attacker can force insertion failures with a small set of elements. The proposed attack has been implemented and tested for different configurations to demonstrate its feasibility. The fact that cuckoo hash can be broken with only access to its user functions should be taken into account when implementing it on critical systems. The paper also discusses potential approaches to mitigate this vulnerability.