hashing crittografico senza collisioni?

2

Desidero hash qualcosa che emetta un hash privo di collisioni e usare quell'hash come id in un database. L'utilizzo dell'hash crittografico convenzionale (lunghezza fissa) significa che esiste una possibilità di collisione e che l'ID potrebbe non diventare univoco.

Esiste un hash crittografico simile?

Credo che potrei sempre usare la crittografia asimmetrica deterministica e criptare qualcosa con la chiave pubblica, buttare via la chiave privata e usare l'output come una sorta di hash, ma comunque - mi chiedevo se ci sono altre possibilità.

Fondamentalmente il mio problema è questo: voglio che ogni nome utente abbia un record nel mio database, ma se qualcuno ottiene una sospensione del mio database, non voglio che nessuno possa leggere il nome utente da un record. Nessun utente potrà mai conoscere il nome utente di qualcun altro, eliminando così la possibilità di eseguire semplicemente l'hashing e testare se qualcuno esiste nel database.

    
posta HelloWorld 07.05.2018 - 01:14
fonte

1 risposta

4

Quello che stai chiedendo è un oracolo casuale , un ipotetico hash ideale che non può creare collisioni a meno che l'input sia più grande dell'output. Un tale hash non esiste in realtà e il meglio che si può ottenere è l'hash crittografico corrente che rende più difficile trovare collisioni intenzionalmente. Maggiore è l'output dell'hash, minore è la possibilità di una collisione involontaria. È improbabile che un hash strong come lo SHA-256 possa scontrarsi mai , anche se stavi generando intenzionalmente miliardi di ID al secondo.

La possibilità di una collisione è 1 - e -b (b - 1) / 2n , dove n è il numero di distinti Gli ID nel set e b sono il numero di bit nel digest hash. Questo sito web spiega di più sui rischi di collisione dell'hash.

Se tutto ciò che si vuole fare è generare un ID pseudorandom unico dato un input di dimensioni fisse, si potrebbe usare un codice a blocchi. L'input è l'ID di input e l'output è l'unico ID pseudocasuale. Questo può essere descritto come H = E k (ID) ed è simile a un codice a blocchi in modalità contatore. Finché l'input e l'output devono essere grandi solo quanto le dimensioni del blocco, non ci saranno collisioni. Nota che, a differenza di un hash, questo è reversibile e la conoscenza della chiave può essere utilizzata per calcolare l'ID originale.

La dimensione del blocco del codice è ciò che determina le dimensioni di input e output. Ad esempio, un codice a 64 bit a blocchi richiede un ID a 64 bit come input e genererà un valore a 64 bit che può essere utilizzato al posto dell'hash. Ogni distinto ingresso a 64 bit verrà mappato su un'uscita a 64 bit distinta e pseudocasuale. L'input può essere più piccolo della dimensione del blocco se è riempito con un valore costante, ma l'output deve essere usato così com'è. Se l'input o l'output sono troncati, ci sarà il rischio di incorrere in collisioni.

L'uso di un codice a blocchi potrebbe non essere pratico se si convertono nomi utente in ID, poiché una dimensione di blocco di 64 bit (ad esempio) può accettare al massimo un nome utente di 8 caratteri, assunzione ASCII . Se l'input deve essere di dimensioni variabili, ti esorto a utilizzare una funzione di hash. La possibilità di collisioni per un hash strong ≥160-bit è fuggevolmente piccola. Questo è ciò per cui sono stati progettati gli hash.

    
risposta data 07.05.2018 - 01:15
fonte

Leggi altre domande sui tag