Schreckliche Kollisionen von adler32 Hash

Question

Wenn Sie adler32() als eine Hash-Funktion verwenden, sollte man seltene Kollisionen erwarten.

Wir können die genaue mathematische Kollisionswahrscheinlichkeit, aber grob gesagt,
da es sich um eine 32-Bit-Hash-Funktion ist, sollte es nicht viele Kollisionen
auf einem Probensatz von ein paar tausend Einzelteilen.

Dies ist kaum der Fall. Hier

ein Beispiel: Lassen Sie uns Saiten nehmen, die ein Datum in der Mitte sind, so etwas wie

"Some prefix text " + date + " some postfix text." 

wo das dates` Format yyyy-mm-dd ist, und Schleifen über 2012

In diesem Beispiel gibt es 91 Kollisionen!

Noch schlimmer: Es gibt 7 Fälle, wo 3 Daten kollidierten.

Wie kommt so eine häufig verwendete Hash-Funktion so schlecht?
Oder fehlt mir etwas?

Hier sind die detaillierten Ergebnisse des obigen Beispiels:

0x592a0f1f: 2012-01-30, 2012-02-02, 2012-10-21 
0x592b0f1f: 2012-02-11, 2012-10-30, 2012-11-02 
0x593d0f20: 2012-01-31, 2012-02-03, 2012-10-22 
0x593e0f20: 2012-02-12, 2012-10-31, 2012-11-03 
0x59410f20: 2012-03-11, 2012-11-30, 2012-12-02 
0x59560f21: 2012-03-30, 2012-04-02, 2012-12-21 
0x59690f22: 2012-03-31, 2012-04-03, 2012-12-22 

0x59020f1d: 2012-01-10, 2012-10-01 
0x59150f1e: 2012-01-11, 2012-10-02 
0x59160f1e: 2012-01-20, 2012-10-11 
0x59170f1e: 2012-02-01, 2012-10-20 
0x59180f1e: 2012-02-10, 2012-11-01 
0x59280f1f: 2012-01-12, 2012-10-03 
0x59290f1f: 2012-01-21, 2012-10-12 
0x592c0f1f: 2012-02-20, 2012-11-11 
0x592d0f1f: 2012-03-01, 2012-11-20 
0x592e0f1f: 2012-03-10, 2012-12-01 
0x593b0f20: 2012-01-13, 2012-10-04 
0x593c0f20: 2012-01-22, 2012-10-13 
0x593f0f20: 2012-02-21, 2012-11-12 
0x59400f20: 2012-03-02, 2012-11-21 
0x59420f20: 2012-03-20, 2012-12-11 
0x59430f20: 2012-04-01, 2012-12-20 
0x594e0f21: 2012-01-14, 2012-10-05 
0x594f0f21: 2012-01-23, 2012-10-14 
0x59500f21: 2012-02-04, 2012-10-23 
0x59510f21: 2012-02-13, 2012-11-04 
0x59520f21: 2012-02-22, 2012-11-13 
0x59530f21: 2012-03-03, 2012-11-22 
0x59540f21: 2012-03-12, 2012-12-03 
0x59550f21: 2012-03-21, 2012-12-12 
0x59570f21: 2012-04-11, 2012-12-30 
0x59610f22: 2012-01-15, 2012-10-06 
0x59620f22: 2012-01-24, 2012-10-15 
0x59630f22: 2012-02-05, 2012-10-24 
0x59640f22: 2012-02-14, 2012-11-05 
0x59650f22: 2012-02-23, 2012-11-14 
0x59660f22: 2012-03-04, 2012-11-23 
0x59670f22: 2012-03-13, 2012-12-04 
0x59680f22: 2012-03-22, 2012-12-13 
0x596a0f22: 2012-04-12, 2012-12-31 
0x596c0f22: 2012-04-30, 2012-05-02 
0x59740f23: 2012-01-16, 2012-10-07 
0x59750f23: 2012-01-25, 2012-10-16 
0x59760f23: 2012-02-06, 2012-10-25 
0x59770f23: 2012-02-15, 2012-11-06 
0x59780f23: 2012-02-24, 2012-11-15 
0x59790f23: 2012-03-05, 2012-11-24 
0x597a0f23: 2012-03-14, 2012-12-05 
0x597b0f23: 2012-03-23, 2012-12-14 
0x597c0f23: 2012-04-04, 2012-12-23 
0x59820f23: 2012-05-30, 2012-06-02 
0x59870f24: 2012-01-17, 2012-10-08 
0x59880f24: 2012-01-26, 2012-10-17 
0x59890f24: 2012-02-07, 2012-10-26 
0x598a0f24: 2012-02-16, 2012-11-07 
0x598b0f24: 2012-02-25, 2012-11-16 
0x598c0f24: 2012-03-06, 2012-11-25 
0x598d0f24: 2012-03-15, 2012-12-06 
0x598e0f24: 2012-03-24, 2012-12-15 
0x598f0f24: 2012-04-05, 2012-12-24 
0x59950f24: 2012-05-31, 2012-06-03 
0x59980f24: 2012-06-30, 2012-07-02 
0x599a0f25: 2012-01-18, 2012-10-09 
0x599b0f25: 2012-01-27, 2012-10-18 
0x599c0f25: 2012-02-08, 2012-10-27 
0x599d0f25: 2012-02-17, 2012-11-08 
0x599e0f25: 2012-02-26, 2012-11-17 
0x599f0f25: 2012-03-07, 2012-11-26 
0x59a00f25: 2012-03-16, 2012-12-07 
0x59a10f25: 2012-03-25, 2012-12-16 
0x59a20f25: 2012-04-06, 2012-12-25 
0x59ae0f25: 2012-07-30, 2012-08-02 
0x59ae0f26: 2012-01-28, 2012-10-19 
0x59af0f26: 2012-02-09, 2012-10-28 
0x59b00f26: 2012-02-18, 2012-11-09 
0x59b10f26: 2012-02-27, 2012-11-18 
0x59b20f26: 2012-03-08, 2012-11-27 
0x59b30f26: 2012-03-17, 2012-12-08 
0x59b40f26: 2012-03-26, 2012-12-17 
0x59b50f26: 2012-04-07, 2012-12-26 
0x59c10f26: 2012-07-31, 2012-08-03 
0x59c40f26: 2012-08-30, 2012-09-02 
0x59c40f27: 2012-02-28, 2012-11-19 
0x59c50f27: 2012-03-09, 2012-11-28 
0x59c60f27: 2012-03-18, 2012-12-09 
0x59c70f27: 2012-03-27, 2012-12-18 
0x59c80f27: 2012-04-08, 2012-12-27 
0x59d70f27: 2012-08-31, 2012-09-03 
0x59da0f28: 2012-03-28, 2012-12-19 
0x59db0f28: 2012-04-09, 2012-12-28 

Answer 1

Adler-32 wurde nie nicht eine Hash-Funktion zu sein und ist vorgesehen. Sein Zweck ist die Fehlererkennung nach der Dekomprimierung. Es erfüllt diesen Zweck gut, da es schnell ist und Fehler in den komprimierten Daten durch den Dekomprimierer verstärkt werden.

In den Beispielen, die Sie angeben, verwenden Sie Adler-32 für sehr kurze Strings, für die es keine Möglichkeit gibt, alle 32 Bits zu verwenden. Adler-32 benötigt mindestens einige hundert Bytes, um ins Rollen zu kommen.

Es gibt viele nicht-kryptografische Hash-Funktionen, die sehr schnell sind und ein gutes Hash-Verhalten haben, einschließlich der Vermeidung von Kollisionen. Werfen Sie einen Blick auf die CityHash Familie von Hash-Funktionen.

Wenn Sie kryptografische (nicht spoofable) Hash-Funktionen benötigen, dann sehen Sie sich SHA-2 und SHA-3 an.