Quando è sicuro da usare una funzione di hash rotto?

StackOverflow https://stackoverflow.com/questions/2889473

Domanda

E 'banale di utilizzare una funzione hash sicuro come SHA-256, e continuando a utilizzare MD5 per la sicurezza è un comportamento sconsiderato. Tuttavia, ci sono alcune complessità di vulnerabilità funzione di hash che vorrei capire meglio.

Le collisioni sono stati generato per MD4 e MD5 . Secondo il NIST, MD5 non è una funzione hash sicuro. Si richiede solo 2 39 operazioni per generare una collisione non dovrebbe mai essere utilizzato per le password . Tuttavia SHA-1 è vulnerabile a un simile attacco di collisione in cui una collisione può essere trovato in 2 69 operazioni, mentre la forza bruta è 2 80 . Nessuno ha generato uno SHA-1 di collisione e NIST elenca ancora SHA-1 come messaggio sicuro digerire funzione .

Così, quando è sicuro da usare una funzione di hash rotto? Anche se una funzione è rotto può ancora essere "abbastanza grande". Secondo Schneier una funzione hash vulnerabile ad un attacco di collisione lattina ancora essere utilizzato come HMAC . Credo che questo sia perché la sicurezza di un HMAC dipende dalla sua chiave segreta e una collisione non può essere trovato fino ad ottenere questa chiave. Una volta che avete la chiave utilizzata in un HMAC è già rotto, quindi è un punto controverso. Quali vulnerabilità funzione hash minerebbe la sicurezza di un HMAC?

Diamo un po 'più questa proprietà. Ha poi diventare sicuro da usare un messaggio molto debole digerire come MD4 per le password, se un sale viene anteposto alla password? Tenete a mente gli attacchi MD4 e MD5 sono prefisso attacchi, e se un sale viene anteposta quindi un attaccante non può controllare il prefisso del messaggio. Se il sale è davvero un segreto, e non è noto per l'attaccante, allora cosa importa se è aggiunto alla password? E 'lecito ritenere che un attaccante non può generare una collisione fino a quando è stato ottenuto l'intero messaggio?

Sei a conoscenza di altri casi in cui una funzione di hash rotto può essere utilizzato in un contesto di sicurezza senza introdurre una vulnerabilità?

(Si prega di inviare prove a sostegno, perché è impressionante!)

È stato utile?

Soluzione

In realtà le collisioni sono più facili di quello che vi elenco sia MD5 e SHA-1. collisioni MD5 possono essere trovati in tempo equivalente a 2 26,5 di funzionamento (dove un "operazione" è il calcolo di MD5 in un breve messaggio). Vedere questa pagina per alcuni dettagli e un'implementazione dell'attacco (ho scritto che il codice, ma trova una collisione all'interno di una media di 14 secondi su un 2,4 GHz Core2 x86 in modalità a 64 bit)

.

Analogamente, il miglior attacco noti su SHA-1 è circa 2 61 operazioni, non 2 69 . E 'ancora teorica (collisione reale è stato ancora prodotto), ma è all'interno del regno del fattibile.

Per quanto riguarda le implicazioni in materia di sicurezza: le funzioni di hash sono di solito ha detto di avere tre caratteristiche:

  • Nessun preimage: dato y , non dovrebbe essere possibile trovare x in modo tale che h (x) = y
  • Nessun secondo preimage: dato x 1 , non dovrebbe essere possibile trovare x 2 (distinta da x 1 ) tale che h (x 1 ) = h (x 2 ) .
  • Nessun collisione: non dovrebbe essere possibile trovare qualsiasi x 1 e x 2 (distinto da reciprocamente) tale che h (x 1 ) = h (x 2 ) .

Per una funzione hash con un n di uscita bit, ci sono gli attacchi generici (che opera indipendentemente dai dettagli della funzione di hash) in 2 n operazioni per le due prime proprietà, e 2 n / 2 operazioni per il terzo. Se, per una data funzione hash, un attacco è trovato che, sfruttando i dettagli particolari di come la funzione hash opera, trova un preimage, un secondo preimage o collisione veloce rispetto al corrispondente attacco generico, la funzione hash è detta essere "rotto".

Tuttavia, non tutti gli utilizzi di funzioni hash si basano su tutte e tre le proprietà. Per esempio, le firme digitali cominciano hashing dei dati, che deve essere firmato, e quindi il valore di hash viene utilizzato nel resto dell'algoritmo. Questo si basa sulla resistenza di preimages e seconde preimages, ma firme digitali non sono, di per sé, influenzato dalle collisioni. Le collisioni possono essere un problema in alcuni scenari di firma specifica, dove l'attaccante deve scegliere i dati che deve essere firmata dalla vittima (in pratica, l'attaccante calcola una collisione, ha un messaggio firmato da parte della vittima, e la firma diventa valida per l'altro messaggio pure). Questo può essere contrastato anteponendo alcuni byte casuali al messaggio firmato prima di calcolare la firma (l'attacco e la soluzione in cui ha dimostrato nel contesto di certificati X.509).

La sicurezza HMAC si basa su un altro di proprietà che la funzione di hash deve soddisfare; vale a dire, che la "funzione di compressione" (il mattone elementare su cui è costruita la funzione di hash) agisce come una funzione Pseudo-Random (PRF). Dettagli su ciò che un PRF è sono abbastanza tecnico, ma, grosso modo, un PRF dovrebbe essere indistinguibile da un a caso Oracle . Un oracolo random è modellata come una scatola nera che contiene uno gnomo, alcuni dadi e un grande libro. Su alcuni dati di ingresso, lo gnomo selezionare un'uscita casuale (con i dadi) e scrive nel libro messaggio di input e l'output che è stato selezionato in modo casuale. Lo gnomo utilizza il libro per verificare se ha già visto lo stesso messaggio di input: se è così, allora lo gnomo restituisce lo stesso uscita rispetto al passato. Per costruzione, si può sapere nulla circa l'uscita di un oracolo random su un dato messaggio fino a quando lo si prova.

Il modello oracolo random consente la prova di sicurezza HMAC da quantificare in invocazioni della PRF. In sostanza, gli stati prova che HMAC non può essere rotto senza invocare il PRF un enorme numero di volte, e di "enorme" intendo computazionalmente infeasible.

Sfortunatamente, non abbiamo oracolo random, quindi, in pratica, dobbiamo usare le funzioni di hash. Non v'è alcuna prova che esistono realmente funzioni hash, con la proprietà PRF; in questo momento, abbiamo solo i candidati, vale a dire le funzioni per le quali non possiamo dimostrare (ancora) che le loro funzioni di compressione non sono PRF.

Se la funzione di compressione è un PRF poi la funzione di hash è automaticamente resistente alle collisioni. Questa è parte della magia della PRF. Quindi , se riusciamo a trovare collisioni per una funzione di hash, allora sappiamo che la funzione di compressione interna non è un PRF. Questo non si trasformi le collisioni in un attacco contro HMAC. Essere in grado di generare collisioni a volontà non aiuta a rompere HMAC. Tuttavia, tali collisioni dimostrano che la prova di protezione associato con HMAC non si applica. La garanzia non è valida. Questo è lo stesso di un computer portatile:. L'apertura del caso, non necessariamente infrange la macchina, ma poi si è da soli

In un articolo Kim-Biryukov-Preneel-Hong , alcuni attacchi contro HMAC sono presentato, in particolare un attacco contraffazione su HMAC-MD4. L'attacco sfrutta le carenze del MD4 (le sue "debolezze") che lo rendono un non-PRF. Varianti delle stesse debolezze sono stati utilizzati per generare collisioni sulla MD4 (MD4 è completamente rotto; alcuni attacchi generano collisioni più velocemente di quanto il calcolo della funzione di hash per sé!). Quindi, le collisioni non implicano l'attacco HMAC, ma entrambi gli attacchi nutrono la stessa fonte. Nota, però, che l'attacco falso trovi costo 2 58 , che è piuttosto elevata (senza falsificazione effettivo è stato prodotto, il risultato è ancora teorico) ma diminuire considerevolmente rispetto alla resistenza livello atteso da HMAC (con una funzione hash robusto con una n uscita bit, HMAC dovrebbe resistere fino a 2 n fattore lavoro; n = 128 per MD4).

Così, mentre le collisioni non lo fanno per se implica debolezze su HMAC, sono cattive notizie. In pratica, le collisioni sono un problema per pochissimi messe a punto. Ma sapere se le collisioni impatto di un determinato utilizzo di funzioni hash è abbastanza difficile, che è abbastanza saggio per continuare a utilizzare una funzione di hash per i quali sono state dimostrate le collisioni.

Per SHA-1, l'attacco è ancora teorica, e SHA-1 è ampiamente utilizzato. La situazione è stata descritta così: ". L'allarme è acceso, ma non c'è il fuoco visibile o fumo E 'il momento di dirigersi verso le uscite - ma non per correre"

Per ulteriori informazioni su questo argomento, inizia leggendo il capitolo 9 del Handbook of Applied Cryptography , da Menezes, van Oorschot e Vanstone, una lettura obbligata per il crittografo apprendista (da non confondere con "Applied Cryptography" di B. Schneier, che è un'introduzione ben scritta, ma da nessuna parte come approfondito come il " Handbook ").

Altri suggerimenti

L'unica volta che è sicuro da usare una funzione di hash rotto è quando le conseguenze di una collisione sono innocui o banali, per esempio quando si assegna i file in un secchio su un filesystem.

Quando non si cura se è sicuro o meno.

Scherzi a parte, non ci vuole alcuno sforzo in più per utilizzare una funzione hash sicuro in quasi tutte le lingue, e impatto sulle prestazioni è trascurabile, quindi non vedo il motivo per cui non lo sarebbe.

[Modifica dopo aver letto la tua domanda in realtà]

  

Secondo Schneier una funzione hash vulnerabile ad un attacco collsion può ancora essere utilizzato come HMAC. Credo che questo sia perché la sicurezza di un HMAC dipende dalla sua chiave segreta e una collisione non può essere trovato fino ad ottenere questa chiave.

In realtà, è dovuto essenzialmente al fatto di essere in grado di generare una collisione per un hash non necessariamente aiuta a generare una collisione per il hash-of-a-hash (combinata con la XOR usato da HMAC).

  

Ha poi diventare sicuro da usare un messaggio molto debole digerire come md4 per le password, se un sale è perpended alla password?

No, non se l'hash ha una preimage attacco che consente di anteporre i dati a l'ingresso. Per esempio, se l'hash era H(pass + salt), avremmo bisogno di un attacco preimage, che ci permette di trovare pass2 tale che H(pass2 + salt) = H(pass + salt).

Non ci sono stati attacchi di aggiunta in passato, quindi sono sicuro che gli attacchi prepend sono possibili.

siti di download utilizzano MD5 hash come una somma di controllo per determinare se il file è stato danneggiato durante il download, e direi un hash rotta è abbastanza buono per questo scopo.

Diciamo che un MITM decide di modificare il file (ad esempio un archivio zip, o un exe). Ora, l'attaccante ha a che fare due cose -

  1. Trovare una collisione hash e creare un file modificato da esso
  2. Assicurarsi che il file appena creato è anche un exe valido o una zip archivio

Con un hash rotto, 1 è un po 'più facile. Ma garantire che la collisione soddisfi contemporaneamente altre proprietà note del file è troppo costoso computazionalmente.

Questo è totalmente la mia risposta, e ho potuto essere terribilmente sbagliato.

La risposta dipende interamente da ciò che si sta usando per. Se è necessario per evitare che qualcuno la produzione di uno scontro con alcuni millisecondi sarei meno preoccupati che se è necessario per evitare che qualcuno la produzione di una collisione nel giro di pochi decenni.

Qual è il problema in realtà cercando di risolvere?

La maggior parte della preoccupazione circa usando qualcosa come MD4 una password è legata meno agli attacchi attualmente noti, oltre al fatto che una volta che è stato analizzato a tal punto che la generazione di collisione è facile, è generalmente presume di essere molto più probabile che qualcuno sarà in grado di utilizzare tale conoscenza per creare un attacco preimage -. e quando / se ciò accade, in sostanza, tutti i possibili usi di quella funzione di hash diventano vulnerabili

Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a StackOverflow
scroll top