SipHash: A Classic Tale of a Fix For A Problem
… and still one of the best hashing methods around
Around 2011/2012, JP Aumasson and Daniel J Bernstein (djb) outlined some major risks around many existing hashing methods [here]:
For this, YP outlined that a DoS could be created on a hashtable by sending the same hash (a multicollision) to a server. This results in a worst-case insert time, and can result in a DoS against the hashing method. The example given is to send 2MB of POST data consisting of 200,000 of the same 10 byte string and which results in 40,000,000,000 string comparisons — having an impact of a computation time of around 10 seconds on a 2 GHz machine. They found MurmurHash2/3 and Google’s CityHash as being vulnerable to these attacks. Google has since released FarmHash in order to address the weakness.
But for YP and jdb it was not all about outlining a weakness, but where they fixed the problem with SipHash [1]. This addressed some of the issues caused by DoS attacks against hashing methods [here]:
