Troncamento dell'output di hash per un ID univoco

5

Questa sembra una domanda comune, ma la mia conoscenza dell'hashing è molto limitata, quindi cerco una risposta di tipo ELI5. Sarei grato se qualcuno potesse aiutarmi con le mie domande

Alcuni contesto: sto lavorando su un requisito per generare un 12 caratteri lungo ID human-friendly (per le ricevute di pagamento del cliente), che utilizzerà il set di simboli AZ 0-9 senza O, I, Z, e U. Questo mi dà 32 simboli che significano 5 bit per simbolo e quindi l'ID sarebbe 60 bit. Il requisito è che questi ID dovrebbero essere unici, ma saranno archiviati in un database in modo da poter cercare nel database e rigenerarne un altro se esiste già. Sarebbe bello se gli ID fossero intrinsecamente univoci (quindi non si dovrebbe seguire la ricerca del database rigenerando un nuovo ID)

La mia domanda è

Se scelgo di creare ottenere uno SHA-256 sia di un UUID, o qualche valore ottenuto concatenando l'indirizzo IP privato del paese ospitante, il timestamp, e il filo la gestione di una richiesta di generazione di ID id, quindi ottenere la sua SHA 256 hash e usa i suoi 60 bit

  1. Avrò il massimo beneficio dall'utilizzare i primi 60, o gli ultimi 60 (o mezzo?) per preservare la massima unicità? Otterrei maggiori benefici se usassi i primi 12 caratteri del numero esadecimale del valore SHA?
  2. qui che per valori n-bit, il compleanno bound è 2 ^ (n / 2). Quindi, se faccio l'elaborazione di cui sopra, potrei aspettarmi collisioni dopo 2 ^ (30) generazioni con una probabilità del 50%?

I requisiti non sono flessibili (altrimenti andrei ovviamente con un UUID).

Grazie!

    
posta Shobit 11.02.2015 - 20:08
fonte

1 risposta

4

Non esiste alcuna proprietà nota del primo / ultimo / mezzo / whatev 60 bit di un output SHA-256 che li renderebbe più / meno "randomizzati" rispetto all'ultimo / whatev / medio / primi 60 bit. In altre parole, potresti prendere i primi 60 bit, e quello sarà il più bello possibile.

Con una generazione così casuale, puoi davvero aspettarti che le prime collisioni compaiano dopo che sono stati accumulati un miliardo circa di ID (2 30 ). Anche se a quel punto si verifica la prima collisione, le collisioni rimarranno comunque un evento raro. Con gli ID a 60 bit, quando hai, diciamo, 2 35 di loro (vale a dire più di trenta miliardi), allora solo uno su 2 25 di nuovi ID entrerà in collisione con uno esistente (quindi questo accadrebbe ancora meno di una volta in 30 milioni di casi). Se hai un database e puoi tollerare la collisione occasionale ma piuttosto rara, la generazione casuale dell'ID a 60 bit è la strada da percorrere.

(Oppure, detto altrimenti, se ottieni spesso collisioni, significa che hai già raccolto un numero enorme di ID e il tuo database centrale deve essere di proporzioni bibliche.)

Se vuoi più unicità di quella, allora hai bisogno di una sorta di generatore di ID centrale. Ad esempio, c'è un server centrale che può essere interrogato e restituisce il valore successivo di un contatore. Il server aumenta sempre il valore del contatore dopo essere stato interrogato, quindi non restituisce mai due volte lo stesso valore. Il server non esaurirà gli interi a 60 bit prima di molto, perché, ammettiamolo, 2 60 è ancora enorme.

Ora arriva la parte difficile, che è quella di cui non hai parlato: gli ID devono essere imprevedibili? Questa non è una domanda facile; dipende da cosa fai con loro e, fondamentalmente, da tutto ciò che è nel tuo sistema. Se hai bisogno di ID imprevedibili, un contatore centrale non funzionerà, perché tutti possono ottenere un valore ID e predire il prossimo con una precisione del 100%. La solita soluzione, in tal caso, sarebbe avere ancora un contatore, ma per crittografare i valori successivi con un codice a blocchi la cui dimensione del blocco è identica a quella dell'ID. Qui avresti bisogno di un codice a blocchi con blocchi a 60 bit - questo può essere costruito da un codice a blocchi con blocchi leggermente più grandi, ad es. 3DES (blocchi a 64 bit). Questo ha senso, però, solo nel contesto di un generatore di ID centrale.

Se è necessario consentire la generazione dell'ID da più macchine "client" senza doverle parlare insieme o con qualche sistema centrale, allora si dovrà fare affidamento sulla casualità e tollerare le poche collisioni occasionali (che saranno piuttosto rare per un lungo periodo di tempo) ). Se hai bisogno di imprevedibilità, utilizza un PRNG protetto da crittografia . A seconda del sistema operativo e del framework di programmazione, questo può essere chiamato /dev/urandom (sistemi Linux / Solaris / * BSD), CryptGenRandom() (Windows C / C ++), java.security.SecureRandom (Java), System.Security.Cryptography.RNGCryptoServiceProvider (.NET) ... È possibile che il sistema di generazione UUID intrinseco del tuo ambiente di programmazione locale si basa su un PRNG crittograficamente sicuro (quindi l'hashing di un UUID con SHA-256 andrebbe bene, anche per l'imprevedibilità), ma perché correre rischi? Basta usare direttamente un PRNG strong.

    
risposta data 11.02.2015 - 20:30
fonte

Leggi altre domande sui tag