On 01/25/2012 09:38 AM, Daniel P. Berrange wrote:
From: "Daniel P. Berrange" <berrange@redhat.com>
Recent discussions have illustrated the potential for DOS attacks with the hash table implementations used by most languages and libraries.
https://lwn.net/Articles/474912/
libvirt has an internal hash table impl, and uses hash tables for a variety of purposes. The hash key generation code is pretty simple and thus not strongly collision resistant.
This patch replaces the current libvirt hash key generator with the (public domain) Murmurhash3 code. In addition every hash table now gets a random seed value which is used to perturb the hashing code. This should make it impossible to mount any practical attack against libvirt hashing code.
* bootstrap.conf: Import bitrotate module * src/Makefile.am: Add virhashcode.[ch] * src/util/util.c: Make virRandom() return a fixed 32 bit integer value.
This part of the commit message is stale.
* src/util/hash.c, src/util/hash.h, src/util/cgroup.c: Replace hash code generation with a call to virHashCodeGen() * src/util/virhashcode.h, src/util/virhashcode.c: Add a new virHashCodeGen() API using the Murmurhash3 algorithm. --- bootstrap.conf | 1 + src/Makefile.am | 1 + src/util/cgroup.c | 6 ++- src/util/virhash.c | 21 +++------ src/util/virhash.h | 7 ++- src/util/virhashcode.c | 121 ++++++++++++++++++++++++++++++++++++++++++++++++ src/util/virhashcode.h | 35 ++++++++++++++ 7 files changed, 174 insertions(+), 18 deletions(-) create mode 100644 src/util/virhashcode.c create mode 100644 src/util/virhashcode.h
@@ -1636,9 +1637,10 @@ cleanup: }
-static uint32_t virCgroupPidCode(const void *name) +static uint32_t virCgroupPidCode(const void *name, uint32_t seed) { - return (uint32_t)(int64_t)name; + unsigned long pid = (unsigned long)name; + return virHashCodeGen(&pid, sizeof(pid), seed);
Hmm - now we're losing the double-cast, so you might be reintroducing compiler warnings about casting a pointer to an incorrectly-sized integer. I think you still need to use: unsigned long pid = (unsigned long)(intptr_t)name;
+ * + * The hash code generation is based on the public domain MurmurHash3 from Austin Appleby: + * http://code.google.com/p/smhasher/source/browse/trunk/MurmurHash3.cpp + * + * We use only the 32 bit variant because the 2 produce different result while
s/result/results/
+/* slower than original but is endian neutral and handles platforms that + * do only aligned reads */
s/is endian neutral and/ Your version is endian-dependent, but that's okay (you convinced me that what matters is that a single libvirtd instance will always generate the same hash for the same string, regardless of alignment; and that we aren't transferring the hash over the wire to any other libvirtd instance running on a different-endian machine).
+__attribute__((always_inline)) +static uint32_t getblock(const uint8_t *p, int i) +{ + uint32_t r; + size_t size = sizeof(uint32_t);
I would have used sizeof(r) here (it's always nicer to use sizeof(var) rather than sizeof(type), when a var is present, in case var changes type later in a later patch).
+ + memcpy(&r, &p[i * size], size);
Hopefully the compiler optimizes this decently.
+ + switch (len & 3) { + case 3: + k1 ^= tail[2] << 16; + case 2: + k1 ^= tail[1] << 8; + case 1:
I'd add some /* fallthrough */ comments to shut up Coverity. Beyond that, it looked like a faithful conversion of the upstream code. ACK with nits addressed. -- Eric Blake eblake@redhat.com +1-919-301-3266 Libvirt virtualization library http://libvirt.org