Se si eseguono dati simili con hashing delle dimensioni (numeri di previdenza sociale, ad esempio) utilizzando un algoritmo hash con una dimensione byte maggiore dei dati (ad esempio sha-256), l'hash garantirà lo stesso livello di univocità come i dati originali?Ci sono circostanze in cui un algoritmo hash può essere garantito univoco?
Se si utilizza un hash crittografico come SHA, la risposta breve è sì.
È sempre possibile creare un hash personalizzato che garantisce univocità. Per i dati in un dominio conosciuto (come gli SSN), l'esercizio è relativamente semplice.
Se il valore di hash di destinazione ha effettivamente più bit disponibili rispetto a ciò che si sta facendo, l'hash mappa semplicemente i valori di input su uno dei valori di output disponibili. Questa sarà una semplice mappatura lineare dal valore di input come un intero multi-byte all'output come un intero multi-byte.
Quando il valore di hash di destinazione ha meno bit di quello che viene sottoposto a hash, l'univocità non può mai essere garantita.
Grazie. Sto considerando l'hashing ssn e un identificativo "account" che può variare a seconda dell'implementazione. Quindi, se posso usare una funzione di hash invece di una pre-generata, sarebbe preferibile. – matt
Se l'obiettivo è la mascheratura dei numeri di previdenza sociale, implementare una funzione di mappatura lineare uno a uno non sarebbe sufficiente, in quanto sarebbe piuttosto facile calcolare l'input originale da alcuni campioni dell'output. Inoltre, la lunghezza della stringa di input non influisce sicuramente sull'efficacia di una funzione di hash crittograficamente sicura, quindi l'utilizzo di un algoritmo di hash noto è la strada da percorrere –
Una caratteristica chiave di un cryptographically secure hash function è che si è al sicuro da collisioni oltre ogni ragionevole dubbio, indipendentemente dall'input. Ciò vale anche per l'input più corto della dimensione dell'output, che è lo stesso di un messaggio più lungo con poca entropia. Quindi puoi usare SHA-2 senza preoccuparti delle collisioni.
La probabilità di una collisione hash non ha nulla a che fare con la dimensione della stringa di input (tranne nella misura in cui indica quanti ingressi è necessario mantenere l'unicità tra). È possibile avere una collisione hash quando hash 0 e 1 utilizzando un algoritmo di hash perfetto, sebbene la possibilità sia 1/(2^bit di lunghezza). Che nel caso di SHA-256 è effettivamente zero.
Le collisioni di hash sono un problema di compleanno paradossale. Nel caso di un hash 256 bit, la probabilità di una collisione tra due ingressi è puramente dipende dal conteggio di ingressi ed è:
True. Non sto interrogando le implicazioni sulla sicurezza, però. Sto chiedendo la probabilità di unicità da un hash quando la dimensione dei dati è inferiore alla dimensione dell'hash. (Ho bisogno che il valore risultante sia deterministico/ripetibile, quindi l'esecuzione di un salt random di x byte non funziona per me. Potrei "salt" aggiungendo caratteri costanti per implementazione - ad esempio, potrei aggiungere caratteri come "593jra" al ssn prima dell'hashing). – matt
Il paradosso del compleanno non è basato sul principio del pigeonhole? Se è così, in teoria non ho uno scenario da incasellare. – matt
Il principio del "pigeonhole" è la semplice nozione che quando si hanno più oggetti che piccioni, si ha una collisione garantita. Il paradosso del compleanno dice solo che sei davvero in grado di ottenere una collisione se il tuo rapporto tra gli oggetti e le porcellane è "alto". Dove "alto" è definito dalla formula sopra. –
Altri hanno sottolineato che le collisioni non dovrebbero costituire un problema; questo è l'intero punto delle funzioni di hash crittograficamente sicure. Vorrei solo aggiungere le seguenti:
Grazie. Stavo pensando così, ma non sono riuscito a trovare un riferimento per il backup e non sono abbastanza intelligente da scavare nella matematica e concludere in un modo o nell'altro! – matt
Come notato sopra, un hash crittografico dice semplicemente che le collisioni sono straordinariamente improbabili, non impossibili. – Novelocrat
@Novelcrat, La * risposta breve * alla domanda originale è sì. Mentre in teoria è possibile una collisione, il tempo medio per trovare una collisione è considerevolmente più lungo del tempo che impiegherà il sole per evolvere in un gigante rosso e distruggere la terra. –