antirez/redis — pull request #718 by PeterScott (2012-10-22 22:06:08+00:00)
Title: Switch hash function to SipHash.

SipHash is a cryptographically strong MAC designed for use in hash tables. Previously
Redis switched to murmur2 to try to prevent hash flooding DoS attacks:

https://github.com/antirez/redis/commit/da920e75d4836897b9a7109b6d4743e201cd8a4f

Unfortunately, murmur2 and murmur3 are both easy to attack, as there are algorithms which
can quickly generate arbitrarily many keys that all hash to the same value regardless of
what the seed is:

https://www.131002.net/siphash/murmur2collisions-20120821.tar.gz

By switching to SipHash, we get strong resistance to this kind of attack, without any
noticeable slowdown on either redis-benchmark or "DEBUG POPULATE 1000000". According to
the SUPERCOP benchmarks, this good hash performance holds true for both large and small
keys across all CPU architectures and models tested:

http://bench.cr.yp.to/impl-auth/siphash24.html

This patch also switches to using /dev/urandom as a source of high-quality randomness for
key generation on server startup, unless it is unavailable, in which case time and pid
are used instead.