Sto creando un'applicazione che memorizza i documenti e fornisce a ciascuno un UID basato su un digest SHA1 di alcune cose, incluso il timestamp. Il digest ha molti caratteri e voglio consentire agli utenti di identificare i documenti usando i primi x caratteri del digest completo. Qual è un buon valore per x se il numero di documenti è forse intorno a 10 K - 100 K?Quanto si può troncare un hash SHA1 ed essere ragionevolmente sicuri di avere un ID univoco?
Adattare le formule sul sul wikipedia for the Birthday problem, si può approssimare la probabilità di collisione come e^(-n^2/(2^(b+1))), dove n è il conteggio dei documenti e b è il numero di bit. Graphing this formula with n=100,000, sembra che vorrai b> 45 almeno. Sarei più incline ad andare con 64 per renderlo un numero bello e rotondo. Detto questo, avere un piano per affrontare le collisioni se si verificano (forse modificare leggermente il timestamp o aggiungere un nonce?)
Se è per questo, se lo sha1 si basa su più del solo contenuto del documento, perché non renderlo semplicemente un ID casuale? In questo caso le collisioni sono meno problematiche, dato che puoi sempre generare un nuovo numero casuale e riprovare (la probabilità di una collisione con una singola prova è la stessa, comunque).
Non c'è davvero un valore per questo; parte di ciò che rende SHA un buon algoritmo di hashing di tipo generale è che i dati simili non producono necessariamente valori hash simili. La tua migliore scommessa (senza sapere altro sul tuo sistema) sarebbe semplicemente quella di cercare nell'elenco dei documenti i cui hash iniziano con il valore fornito dall'utente, quindi presentarli con un elenco di documenti da selezionare o andare direttamente al documento se ce n'è solo uno.
è che cosa fa git con revs? – dan
@ Dan Si, ed è generalmente un approccio abbastanza buono. –
Bene, ecco una forse troppo semplicistica di una risposta ..
Se con piena SHA1 si ottiene circa 1 a 2^160 possibilità di collisione, quindi troncando un carattere si aumenta la probabilità di collisione del 16 (tutti i possibili valori del carattere troncato) ... che è 2^4 .. Quindi, se tronchi i caratteri x ottieni 1 in 2^(160 - 4 * x) possibilità di collisione .. giusto?
Per un singolo documento questo è vero, ma la probabilità di qualsiasi collisione che si verifica per qualsiasi coppia di documenti aumenta molto più rapidamente – bdonlan
Biham/Chen offrono esempi di Collisioni vicine; e Knudsen dimostra i differenziali troncati. Entrambi sono problemi per gli hash troncati; nessuno dei due casi è il paradosso del compleanno. – jww
È un generalization di the birthday problem. Nel tuo caso n è il numero di documenti, e invece di 365 costante avresti il numero di possibilità che il cutoff ti dà (quindi per k bit è 2 k).
Ovviamente il calcolo esatto è fuori questione, ma è possibile utilizzare approximation.
Biham/Chen offrono esempi di Collisioni vicine; e Knudsen dimostra i differenziali troncati.Entrambi sono problemi per gli hash troncati; nessuno dei due casi è il paradosso del compleanno. – jww
Prestare attenzione al troncamento poiché non vi è alcuna riduzione della prova che l'hash più piccolo è sicuro. Vedi Kelsey's http://csrc.nist.gov/groups/ST/hash/documents/Kelsey_Truncation.pdf. Kelsey dà argomenti euristici affermando lo stesso ("Output Hash correlati" e "Collisioni vicine"). Biham/Chen offrono esempi di Collisioni vicine; e Knudsen dimostra i differenziali troncati.
Alla fine, probabilmente di caricamento dei dati in un HMAC con la dimensione troncato (la dimensione è digerito dal HMAC, troppo) e quindi utilizzare il tronco HMAC.
Ciao JWW, sul NIST-PDF, come lo interpretate? La formula di @ bdonlan, 'e^(- n^2/(2^(b + 1))', è una buona approssimazione per stimare le troncature o no? In caso contrario, quale formula o algoritmo controllare * numero minimo di bit * (_bmin_) per un troncamento SHA1? –
Piccolo nit - Non è il formuala e^(- n^2/(2^(b + 1)))? Cambia leggermente la risposta in b> 40. – Fakrudeen
@Fakrudeen, infatti - Ho fatto un errore quando lo trascrivo nella risposta. Il grafico era corretto però ..... anche se ora mi rendo conto che StackOverflow non ha creato un collegamento per questo: | – bdonlan
Ho aggiornato la risposta per avere la formula corretta come concordato nei commenti. –