Gestione di collisioni praticamente impercettibili su valori imperdibili

Question

Esistono molti sistemi che dipendono dall'unicità di un determinato valore. Viene in mente qualsiasi cosa usi i GUID (ad esempio il registro di Windows o altri database), ma anche cose che creano un hash da un oggetto per identificarlo e quindi hanno bisogno che questo hash sia unico.

Una tabella hash di solito non interessa se due oggetti hanno lo stesso hash perché l'hashing è solo usato per suddividere gli oggetti in categorie, in modo che alla ricerca, non tutti gli oggetti nella tabella, ma solo quegli oggetti in la stessa categoria (bucket) deve essere confrontata per l'identità dell'oggetto ricercato.

Tuttavia, altre implementazioni (sembrano) dipendono dall'unicità. Il mio esempio (questo è quello che mi ha spinto a chiedermelo) sono gli ID di revisione di Mercurial. Un entry sulla mailing list Mercurial giustamente

Le probabilità di changeset hash collisione per caso nei vostri primi miliardi di commit è praticamente pari a zero. Ma noteremo se succede. E diventerai famoso come il ragazzo che ha rotto SHA1 per sbaglio.

Ma anche la più piccola probabilità non significa impossibile. Ora, non voglio una spiegazione del perché sia ​​del tutto corretto fare affidamento sull'unicità (questo è stato discusso here per esempio). Questo è molto chiaro per me.

Piuttosto, mi piacerebbe sapere (forse per mezzo di esempi il proprio lavoro):

• Ci sono delle migliori pratiche per coprire questi casi improbabili comunque?

• Devono essere ignorati, perché è più probabile che i venti solari particolarmente forti portino a letture del disco rigido difettose?

• dovrebbero almeno essere testati per, se non altro per non riuscire con un "Mi arrendo, avete fatto l'impossibile" messaggio per l'utente?

• O anche questi casi devono essere gestiti con garbo?

Per me, in particolare i seguenti sono interessanti, anche se sono un po 'permaloso-feely:

• Se non si gestisce questi casi, che cosa fare contro sentimenti viscerali che don' t ascoltare le probabilità?

• Se li gestisci, come giustifichi questo lavoro (a te stesso e agli altri), considerando che ci sono casi più probabili che non gestisci, come una supernonva?

Answer 1

• Se non li gestisce, come si giustifica questo lavoro (per se stessi e gli altri), considerando che ci sono casi più probabili non si gestisce, come una supernova?

La risposta a questa è che non stanno testando da individuare una collisione GUID che si verificano per caso.Stai provando ad individuare una collisione GUID che si verifica a causa di un bug nel codice GUID, o una precondizione che il codice GUID si basa su quello che hai violato (o ingannato in violazione da parte di un utente malintenzionato), come in V1 che MAC gli indirizzi sono unici e il tempo va avanti. O è molto più probabile dei bug basati su supernova.

Tuttavia, non tutti i client del codice GUID devono testarne la correttezza, in particolare nel codice di produzione. Questo è ciò che i test unitari dovrebbero fare, quindi compensare il costo di perdere un bug che il tuo uso effettivo potrebbe catturare, ma i test unitari non lo hanno fatto, contro il costo di indovinare le tue librerie per tutto il tempo.

Nota anche che i GUID funzionano solo se tutti quelli che li generano cooperano. Se la tua app genera gli ID sulle macchine che controlli, allora potresti non aver bisogno di GUID in ogni caso - un ID localmente unico come un contatore incrementale potrebbe farti bene. Ovviamente Mercurial non può usarlo, quindi usa gli hash, ma alla fine lo SHA-1 cadrà su un attacco che genera collisioni (o, peggio ancora, pre-immagini), e dovranno cambiare.

Se l'app genera "GUID" non hash su macchine che non si controllano, come i client, quindi dimenticare le collisioni accidentali, si è preoccupati per le collisioni deliberate da parte di client dannosi che tentano di eseguire il DOS sul server. Proteggersi contro questo probabilmente ti proteggerà dagli incidenti comunque.

• O dovrebbe anche ottenere questi casi trattati con grazia?

La risposta a questo è probabilmente "no". Se si riescono a gestire i GUID in collisione con garbo, come fa un hashtable, allora perché preoccuparsi di GUID? L'intero punto di un "identificatore" è che se due cose hanno lo stesso ID, allora sono uguali. Se non vuoi trattarli allo stesso modo, dirigili inizialmente in bucket come fa un hashtable, quindi usa uno schema diverso (come un hash).

Answer 2

Dato un buon hash 128 bit, il probabilmente di collisione con un valore hash specifico dato un ingresso casuale è:

1/2 ** 128 che è approssimativamente uguale a 3 * 10 ** -39.

La probabilità di non vedere collisioni (p) dati n campioni può essere calcolata utilizzando la logica utilizzata per spiegare lo birthday problem.

p = (2 ** 128)!/(2 ** (128 * n) * (2 ** 128 - n)!) 

dove ! indica la funzione fattoriale. Possiamo quindi tracciare la probabilità di collisioni, come il numero di campioni aumenta:

Probability of a random SHA-1 collision as the number of samples increases. http://img21.imageshack.us/img21/9186/sha1collision.png

Tra 10**17 e 10**18 hash cominciamo a vedere le possibilità non banali della collisione dal 0,001% al 0,14% e, infine, il 13% con gli scarti 10**19. Quindi in un sistema con un milione di miliardi di dischi che contano sull'unicità è probabilmente poco saggio (e tali sistemi sono concepibili), ma nella stragrande maggioranza dei sistemi la probabilità di una collisione è così piccola che puoi contare sull'unicità dei tuoi hash per tutti gli scopi pratici.

Ora, a parte la teoria, è molto più probabile che le collisioni possano essere introdotte nel sistema sia da bug che da qualcuno che attacca il sistema e quindi la risposta di onebyone fornisce buoni motivi per controllare le collisioni anche se la probabilità di una collisione accidentale è incredibilmente piccolo (vale a dire la probabilità che bug o malizia siano molto più alti di una collisione accidentale).