Hide Forgot
Description of problem: To improve the performance and collision resistance of virHashTable we should switch it to use the MurmurHash3 algorithm https://code.google.com/p/smhasher/ https://code.google.com/p/smhasher/source/browse/trunk/MurmurHash3.cpp NB, we should also create a random seed for each hash table we create See also this article for description of DOS problems with hash impls which are not collision resistant https://lwn.net/Articles/474912/ Version-Release number of selected component (if applicable): libvirt-0.9.9 How reproducible: Steps to Reproduce: 1. 2. 3. Actual results: Expected results: Additional info:
Feel free to use the C implementation I made here: http://git.fedorahosted.org/git/?p=sssd.git;a=commitdiff;h=5a70b84cb66fb8c7a3fce0e3f2e4b61e0b2ea9d4 See a following commit on that tree if you need it to compile on RHEL5 :-)
commit 72b413970013721c784994c9d4370bf3c17cbf7c Author: Daniel P. Berrange <berrange> Date: Wed Jan 18 16:10:43 2012 +0000 Replace hashing algorithm with murmurhash 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. * 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.