Orribili collisioni di adler32 hash

Question

Quando si utilizza adler32() come funzione di hash, ci si dovrebbe aspettare rari conflitti.

Possiamo fare l'esatto matematica delle collisioni probabilità, ma grosso modo,
in quanto si tratta di una funzione di hash 32-bit, non ci dovrebbero essere molte collisioni
su una serie campione di alcuni elementi di migliaia.

Questo non è il caso.

Ecco un esempio: prendiamo le stringhe che includono una data nel mezzo, qualcosa come

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

in cui il formato dates` è aaaa-mm-gg, e loop oltre 2012.

Ci sono 91 collisioni in questo esempio!

Ancora peggio: ci sono 7 casi in cui sono state riscontrate 3 date.

Come mai una tale funzione di hash comunemente utilizzata funziona così male?
O mi manca qualcosa?

Ecco i risultati dettagliati nell'esempio precedente:

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 è mai stato destinato ad essere e non è una funzione di hash. Lo scopo è il rilevamento degli errori dopo la decompressione. Serve a tal fine bene dal momento che è veloce e dal momento che gli errori nei dati compressi sono amplificati dal decompressore.

Negli esempi forniti, si utilizza Adler-32 su stringhe molto brevi, per le quali non ha alcuna possibilità di utilizzare anche tutti i 32 bit. Adler-32 richiede almeno poche centinaia di byte per essere avviato.

Ci sono molte funzioni di hash non crittografiche che sono molto veloci e hanno un buon comportamento di hash, inclusa l'evitamento delle collisioni. Dai un'occhiata alla famiglia di funzioni hash CityHash.

Se sono necessarie funzioni di hash crittografiche (non sostituibili), consultare SHA-2 e SHA-3.