Hashfunktion kollidiert

Hi!

Ich speichere in einer Datenbank 64-bit Hashwerte von der DigitalProductID (welche u.a. auch den Windows Product Key enthält). Jetzt ist es leider relativ schnell zu einer Kollision gekommen und ich frage mich ernsthaft, ob das an der Hashfunktion lag oder ich zwei mal angelogen wurde, denn beide betroffenen beteuern, ihre Windows-Lizenz erstanden zu haben (sie sind rein geografisch auch mehrere tausend Kilometer voneinander entfernt und haben keinen Bezug zueinander).

Der möglicherweise kollidierte Hashwert ist eine immerhin 17-stellige Dezimalzahl. Ich habe folgende primitive, aber ich dachte hinreichend sichere, Funktion benutzt:

template <typename IterType>
std::uint64_t my_hash(IterType begin, IterType end) {
	static_assert(sizeof (typename IterType::value_type) == 1, "Can't hash complex type!");
	std::uint64_t hash_val = 0;
	for (; begin != end; ++begin)
		hash_val = ((hash_val * 0xFF + *begin) % 0xFFFFFFFFFFFC23ull);
	return hash_val;
}

Für mich sieht das doch so aus, alsob eine Kollision äußerst unwahrscheinlich ist, solange die Daten lang genug sind (also mehr als 10 Bytes) und nicht nur nullen enthalten.
Den Algorithmus habe ich modifiziert von [url="http://de.wikipedia.org/wiki/Divisions-Rest-Methode"]hier[/url]. 0xFFFFFFFFFFFC23 ist eine Primzahl.

Michael E.

Was auffällt ist, dass du mit 0xFF, also 255 multiplizierst. Laut Vorgabe solltest du mit 256 multiplizieren.

Kann mir irgendwie nicht vorstellen, dass das so gravierend ist. Dann müsste ich je dementsprechend u.U. eine kleinere Primzahl verwenden, um Overflow zu vermeiden. Und eine kleinere Restklasse sieht für mich irgendwie sogar noch kollisionsfreudiger aus. Ich kann diesen Algorithmus nicht abschätzen, hat nicht irgendjemand schon mal eine mathematische Abhandlung darüber verfasst?

volkard

Bernd10 schrieb:

Kann mir irgendwie nicht vorstellen, dass das so gravierend ist. Dann müsste ich je dementsprechend u.U. eine kleinere Primzahl verwenden, um Overflow zu vermeiden. Und eine kleinere Restklasse sieht für mich irgendwie sogar noch kollisionsfreudiger aus. Ich kann diesen Algorithmus nicht abschätzen, hat nicht irgendjemand schon mal eine mathematische Abhandlung darüber verfasst?

Das 0xFFFFFFFFFFFC23ull zieht ja erst unendlich spät.

Denken wir uns mal in segned rein und dann wäre
hash_val = ((hash_val * 0xFF + *begin) % 0xFFFFFFFFFFFC23ull);
gleich
hash_val = ((hash_val * (-1) + *begin) % 0xFFFFFFFFFFFC23ull);

Türlich ist das Panne!

Ich probiere mal mit zwei Zahlenfolgen
1 2 3 4 5 6 7 8 -> -1+2-3+4-5+6-7+8 = 4.

Ich fürchte, Du verteilst die Hashwerte gar nicht gleichmäßig im uint64_t-Raum, sondern gemäß einer Glockenkurve nur um 0 herum mit einer unglaublicheb Häufung um die 0. Bei sagen wir mal Keys der Länge 8 mit jeweils chars zwischen 48 und 91, werden die Werte zwischen -4*(91+48)=-556 und +556 liegen.
Also nur gut 1000 Werte statt 2^64 Werte.

Und warum überhaupt so kompliziert?
hash_val = hash_val * 31 + *begin;
und hast doch schon Ruhe.

volkard

Bernd10 schrieb:

Kann mir irgendwie nicht vorstellen, dass das so gravierend ist. Dann müsste ich je dementsprechend u.U. eine kleinere Primzahl verwenden, um Overflow zu vermeiden.

Wozu den Overflow vermeiden?
Ok, der Faktor kann gerne kleiner als 256 sein. Es darf nur kein Faktor sein, der Teiler gemeinsam mit der Schlüsselraumgröße hat, und der Faktor sollte nicht gerade nur ein Bit gesetzt oder gelöscht haben, mit 205 statt 255 wäre nix angebrannt. Ich bevorzuge aber große Faktoren, gewöhnlich um Knuths Phi (hier (sqrt(5)-1)/2*2^64 bzw (sqrt(5)-1)/2*0xFFFFFFFFFFFC23 ).

Okay, deinen unteren Vorschlag werde ich mir mal zu Herzen nehmen.
Allerdings sind das 164-Bytes (HKLM\Software\Microsoft\Windows NT\DigialProductID), da zieht der Wert sogar schon.

Ich habe allerdings eine Kollisions des Hashs ausschließen können, die beiden haben tatsächlich identische DigialProductIDs. Beide haben OEM-Laptops von ASUS. Man kann den Product Key aus der DigitalProductID berechnen (jedenfalls sagt mir das jede Seite, die ich zum Thema ergoogle, sogar mit Algorithmus in C#). Allerdings haben beide unterschiedliche Product Keys (also Zahlen auf ihren OEM-Aufklebern). Ich muss mal im WinAPI-Forum oder so nachfragen, wie das sein kann, dass das kollidiert.

Danke für die Anregungen, von "mathematischer" Seite sollte das Problem gelöst sein.