Capisco che, in base al principio del pigeonhole, se il numero di elementi è maggiore del numero di contenitori, allora almeno un contenitore avrà più di un elemento. Importa quale contenitore sarà? Come si applica agli hash MD5, SHA1, SHA2?Quando si scontrano gli hash?
No, non importa quale contenitore sia, e in effetti non è così importante per gli hash crittografici; molto più più importante è il birthday paradox, che dice che è necessario solo hash sqrt(numberNeededByPigeonHolePrincipal) valori, in media, prima di trovare una collisione.
Pertanto, l'hash deve essere abbastanza grande che la radice quadrata dello spazio di ricerca sia troppo grande per la forza bruta. Lo spazio di ricerca della radice quadrata per SHA1 è 2 e, a marzo 2012, non sono mai stati trovati due valori con lo stesso SHA1-hash (sebbene prevedo che accadrà entro l'anno prossimo o due ..); lo stesso con SHA2, una famiglia di hash che hanno tutti uno spazio di ricerca ancora più grande. MD5 è stato broken for a while però.
Il punto di una funzione di hash è distribuire casualmente gli oggetti in contenitori. Per qualsiasi buona funzione di hash, non deve/non deve "importare" quale contenitore è quale, in quanto devono essere indistinguibili.
Questo non si applica alle implementazioni di "hash perfetto" che tentano di fare meglio della distribuzione casuale, a differenza degli algoritmi che hai citato.
Come ha detto Michael, le collisioni si verificano LUNGO prima che ci siano tanti oggetti come slot. Per gestire lo birthday paradox, è necessario avere un trattamento di collisione aggraziato (o un hash perfetto).
Se si dispone di più elementi per l'hash di quanti sono gli slot, si avranno conflitti di hash. Ma se hai un algoritmo di hashing scadente, vedrai le collisioni anche quando il rapporto elementi/slot è molto piccolo. Un buon algoritmo di hashing (che include la maggior parte di quelli che vedrete in natura) tenterà di distribuire gli hash risultanti sull'intero spazio di output nel modo più uniforme possibile, e quindi minimizzare le collisioni.
Si noti che una collisione di hash non è la fine del mondo. Ad esempio, se utilizzato in una tabella hash, significa che più di un elemento è memorizzato in uno slot e il codice della tabella dovrà attraversare un po 'di più per trovare o aggiungere l'elemento di destinazione, aumentando leggermente il tempo di ricerca.
Vedrete le persone fare riferimento a MD5 come un algoritmo di hash "rotto", quando in realtà, è solo uno scarso da utilizzare come hash crittografico. Sarà meglio di uno che costruisci da solo.
MD5 è danneggiato, perché non è crittograficamente sicuro; i vari algoritmi SHA dovrebbero essere utilizzati al posto di MD5. Detto questo, MD5 è abbastanza buono se tutto quello che stai usando è come checksum di un file scaricato. –
la maggior parte delle volte md5 non è usato per essere crittograficamente sicuro. È un hash molto veloce che è più che buono nella maggior parte dei casi. Non è come se suggerisse di usarlo per le password ... o stai suggerendo di implementare un algoritmo di blowfish veramente sicuro e deliberatamente lento da usare in un algoritmo di hash per velocizzare le ricerche in una situazione in cui i dati cambiano rapidamente? Almeno sarà crittograficamente sicuro. MD5 ha ancora uno scopo valido ed è molto bravo a farlo. –
@MrTortoise: sì, è esatto. MD5 va bene per l'utilizzo non crittografico. Nel caso in cui non sia chiaro agli altri, ** non usare ** MD5 per situazioni sensibili alla sicurezza (crittografiche). –
Penso che l'applicazione utilizzata per la funzione di hash rappresenti un'importante distinzione. Le frequenti collisioni nei contenitori di hashing, ad esempio, possono peggiorare le prestazioni. La frequente collisione nella crittografia avrà conseguenze molto più devastanti (vedi: cryptographic hash function on Wikipedia).
La collisione avviene in modo relativamente semplice anche con algoritmo di hash "decente". Ad esempio, in Java,
String s = new String(new char[size]);
hash sempre a 0. Cioè, tutte le stringhe che contengono solo \0 hash a 0 in Java.
Per quanto riguarda il "cosa importa quale contenitore sarà?", Ancora una volta dipende l'applicazione. È possibile progettare funzioni hash che annullerebbero oggetti "simili" ai valori vicini. Questo è utile quando si desidera cercare oggetti simili, ad esempio. Basta eliminarli tutti e vedere dove cadono. In questo caso, sono desiderabili collisioni o quasi collisioni perché raggruppa oggetti simili.
In altre applicazioni, si desidera anche il minimo cambiamento nell'oggetto per ottenere un valore hash completamente diverso. Questo è il caso della crittografia, ad esempio, in cui si vuole essere il più possibile certi che qualcosa non sia stato modificato. In questo caso è molto più difficile trovare oggetti diversi con l'hash allo stesso valore.
A seconda dell'applicazione, gli hash crittografici come MDA, SHA1/2, ecc. Potrebbero non essere la scelta ideale, proprio perché sembrano del tutto casuali, dando così luogo a scontri come previsto dal paradosso del compleanno. Tradizionalmente, uno dei motivi per l'utilizzo di semplici hash basati sull'operazione rimanente è che ci si aspettava che le chiavi fossero numeri seriali o simili, in modo che un'operazione residua avrebbe sopportato meno collisioni del previsto a caso. Per esempio. se le chiavi sono numeri interi 1..1000 potresti non avere collisioni in un contenitore di dimensioni 1009 se la tua funzione di hash è la chiave mod 1009. Le persone a volte regolano manualmente i sistemi selezionando con attenzione le dimensioni del contenitore e la funzione hash per raggiungere una divisione uniforme.
Ovviamente, se ci si deve preoccupare che le persone scelgano maliziosamente le chiavi che causano difficoltà o che un sistema a monte invii chiavi molto marcate (perché ad es. Ha una propria tabella hash e decide di elaborare tutte le chiavi che l'hash ha X alla volta). potresti voler usare un hash basato su una funzione hash crittografica con chiave per difendersi da questo.
Vorrei poter revocare questa risposta due volte. – Cuga
Vale la pena notare che SHA1 è stato rotto in pratica nel 2017 https://shattered.io/ –