search

armon / bloomd

C network daemon for bloom filters
http://armon.github.io/bloomd
Other
1.24k stars 111 forks source link

bloomd hashmap vulnerable to DOS via predictable hash collisions #6

Closed cemeyer closed 11 years ago

cemeyer commented 11 years ago

This is a pretty well-known issue with hashmap implementations; it made the rounds of major programming languages over the past few years, here's Python for an example:

http://bugs.python.org/issue13703

Anywhere untrusted user input is used for a key, collisions can be generated so that all keys land in the same bucket, yielding O(N) lookups (instead of expected O(1)). This can DOS hashmap-implementation consumers (in the case of Python, web apps; for bloomd, unwary users of bloomd).

cemeyer commented 11 years ago

Related: bloomd uses MurmurHash3_x64_128, not MurmurHash3_x32_32, so it isn't an issue for bloomd, but generating "universal" collisions for the 32 variant is apparently easy. So bloomd should stick with the 128-bit variant =). http://131002.net/siphash/murmur3collisions-20120731.tar.gz