Bug 773692

Summary: Convert virHash over to use Murmurhash3 algorithm
Product: [Community] Virtualization Tools Reporter: Daniel BerrangĂ© <berrange>
Component: libvirtAssignee: Libvirt Maintainers <libvirt-maint>
Status: CLOSED UPSTREAM QA Contact:
Severity: unspecified Docs Contact:
Priority: unspecified    
Version: unspecifiedCC: crobinso, ssorce, xen-maint
Target Milestone: ---   
Target Release: ---   
Hardware: Unspecified   
OS: Unspecified   
Whiteboard:
Fixed In Version: Doc Type: Bug Fix
Doc Text:
Story Points: ---
Clone Of: Environment:
Last Closed: 2015-01-15 12:23:49 UTC Type: ---
Regression: --- Mount Type: ---
Documentation: --- CRM:
Verified Versions: Category: ---
oVirt Team: --- RHEL 7.3 requirements from Atomic Host:
Cloudforms Team: --- Target Upstream Version:

Description Daniel Berrangé 2012-01-12 15:53:59 UTC 
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:
Comment 1 Simo Sorce 2012-01-12 16:01:09 UTC 
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 :-)
Comment 2 Daniel Berrangé 2015-01-15 12:23:49 UTC 
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.