Un hash "sicuro" è un hash che si crede sia difficile "falsificare" in modo formulaico, riproducibile senza una precedente conoscenza del messaggio usato per creare l'hash. Poiché tali informazioni sono generalmente segrete, quindi la necessità di un hash, questa è una buona proprietà di una funzione di hashing intesa per l'uso nell'autenticazione.
Un hash è generalmente considerato "sicuro" se, dato un messaggio M, una funzione hash hash () e un valore hash H prodotto da hash (M) con una lunghezza in bit L, nessuno dei seguenti può essere eseguito in meno di O (2 L ) tempo:
- Dato hash () e H, produce M. (pre-resistenza)
- Dato hash () e M, produce un diverso M 2 tale che hash (M 2 ) == H. (resistenza a collisione debole)
- Dato hash (), produce qualsiasi M 1 e M 2 tale che hash (M 1 ) == hash (M 2 ). (strong resistenza di collisione)
Inoltre, un hash "sicuro" deve avere una lunghezza hash L tale che 2 L non sia un numero ammissibile di passaggi per un computer da eseguire dato l'hardware corrente. Un hash intero a 32 bit può avere solo 2,1 miliardi di valori; mentre un attacco preimage (trovare un messaggio che produce un hash H specifico) richiederebbe un po 'di tempo, non è impossibile per molti computer, specialmente quelli nelle mani di agenzie governative noleggiate con il codice. Inoltre, un algoritmo che crea e memorizza i messaggi casuali e i loro hash farebbe, secondo la probabilità, un colpo del 50% nel trovare un hash duplicato con ogni nuovo messaggio dopo aver provato solo 77.000 messaggi, e avrebbe una probabilità del 75% di colpire un duplicare dopo solo 110.000. Anche gli hash a 64 bit hanno ancora il 50% di possibilità di scontrarsi dopo aver provato solo circa 5 miliardi di valori. Tale è il potere dell'attacco di compleanno su piccoli hash. Al contrario, un computer in cerca di collisioni in un hash a 256 bit (SHA-256) non avrebbe nemmeno una possibilità in un miliardo per il prossimo messaggio che ha cercato di scontrarsi fino a quando non ha provato 15 decillion numeri (1.5 * 10 34 ).
Gli attacchi più dimostrati sugli hash crittografici sono stati attacchi di collisione e hanno dimostrato la capacità di generare messaggi in collisione in meno di 2 L (la maggior parte sono ancora stati esponenziali, ma riducendo l'esponente di la metà è una significativa riduzione della complessità poiché rende un hash a 256 bit facile da risolvere quanto un 128 bit, un 128 bit facile da risolvere come un 64 bit, ecc.)
Oltre alle piccole dimensioni dell'hash, altri fattori che possono rendere un hash dimostrabilmente insicuro sono:
Lavoro scarso - un hash progettato per essere utilizzato da un hashtable o per altri scopi di tipo "checksum" sono solitamente progettati per essere computazionalmente economici. Ciò rende molto più facile un attacco a forza bruta.
"Sticky State" (Stato appiccicoso) - La funzione di hashing è soggetta a schemi di input in cui il valore hash corrente di tutti gli input fino a quel momento non cambia quando viene fornito un particolare byte di input aggiuntivo. Avere "sticky state" rende le collisioni facili da trovare, perché una volta identificato un messaggio che produce un hash "sticky state" è banale generare altri messaggi che hanno lo stesso hash aggiungendo byte di input che mantengono l'hash nel suo "stato appiccicoso" ".
Diffusione - Ogni byte di input del messaggio dovrebbe essere distribuito tra i byte del valore hash in un modo altrettanto complesso. Alcune funzioni di hash creano modifiche prevedibili a determinati bit dell'hash. Ciò rende nuovamente banale la creazione di collisioni; dato un messaggio che produce un hash, le collisioni possono essere facilmente create introducendo nuovi valori nel messaggio che riguardano solo i bit che cambiano in modo prevedibile.