In che modo MD5 è vulnerabile agli attacchi di collisione?

13

Ho letto spesso che MD5 (tra gli altri algoritmi di hashing) è vulnerabile agli attacchi di collisione. Comprendo la parte di collisione: esistono due (o più) ingressi tali che MD5 genererà la stessa uscita da questi input distinti e diversi. Ci sono 20 esempi di tali input forniti qui .

Giusto abbastanza, ma in che modo questo porta specificamente a una vulnerabilità? Qual è il vettore di attacco su un sistema con questo tipo di difetto?

Ad esempio, supponiamo di avere un sistema che blocca semplicemente le password degli utenti che utilizzano MD5 per "crittografia". Ora voglio guardare 2 scenari. (Per semplicità, anche supporre che nessun nuovo utente / password sia stato aggiunto al sistema).

Scenario 1 : nessuna delle password nel sistema è il tipo di input che potrebbero generare collisioni. In altre parole, tutte le password elaborate da MD5 generano hash univoci. C'è ancora una vulnerabilità di collisione lì?

Scenario 2 : una delle password nel sistema è questa bellezza ( Collisione 14, Messaggio 1 da l'elenco ):

Ó)\dvµ‡‚G ÌÕÀ˘∏8;å∑œPäÌ/+6éE≠3}˝óÙ|o‡¬{Ç9¸–Û≤‚Mgª%DWÌé$∞\˛UÊiJ;fÉ;™÷ÎQëµCI<˝y≠˜LùΩ]Owå˜1Ú'¬vo'âÃ(©tú√\îùf#4ú¿�(

Quindi esiste un'altra stringa antiestetica che genera una collisione MD5 con questa password. Tuttavia, a meno che l'autore dell'attacco non conosca già queste informazioni, in che modo viene esposta la vulnerabilità?

    
posta Arman H 12.07.2013 - 01:00
fonte

3 risposte

7

Un esempio comune che ho visto riguarda la firma digitale di documenti usando MD5.

Supponiamo di avere due documenti. Uno dei documenti è molto innocente e l'altro è malizioso. Poiché è possibile creare entrambi questi documenti, è possibile farlo in modo che abbiano le stesse firme MD5 (utilizzando postscript per rendere i PDF, ad esempio).

Ora si ottiene qualcuno a firmare il documento innocente (che in genere viene fatto firmando un hash del documento), ma poiché l'hash di entrambi i documenti è lo stesso, la persona ha accidentalmente firmato anche il documento dannoso (che potrebbe dì qualcosa come "Do il permesso a questa persona di prelevare un milione di dollari dal mio conto in banca). Ora puoi presentare il documento dannoso a qualcun altro e crederanno alla firma su di esso a causa della collisione nel documento.

    
risposta data 12.07.2013 - 02:31
fonte
5

Dai un'occhiata a questo link - link - per vedere una spiegazione e l'esempio .

Funziona esattamente come ha detto Oleksi nella sua risposta: hai due documenti che generano lo stesso hash MD5. L'hash è firmato, in modo che entrambi i documenti possano essere "validi".

    
risposta data 12.07.2013 - 03:53
fonte
4

L'hashing della password funziona su resistenza preimage : il processo di hashing della password deve essere tale che non sia possibile computazionalmente trovare un input (una password) corrispondente a un dato output (l'hash), salvo provando un sacco di potenziali input e "sii fortunato". L'attacco "get lucky" è ancora un problema, perché le password sono scelte dagli utenti umani, che non sono così fantasiosi e casuali come si potrebbe desiderare; ecco perché abbiamo bisogno di più di una semplice funzione di hash (abbiamo bisogno di sali, abbiamo bisogno di lentezza; vedi questo ). Tuttavia, le collisioni non hanno alcun impatto sulla sicurezza dell'hash delle password. La capacità di generare collisioni a volontà non dà ulteriore potere di cracking all'attaccante.

Come altri hanno sottolineato, le collisioni possono essere utilizzate per attacchi in altre configurazioni che implicano firme . Questi sono scenari in cui l'aggressore può:

  1. generare collisioni di coppie di messaggi, con un controllo sufficiente sul formato di questi messaggi in modo che un messaggio appaia "innocente" e l'altro sia adatto agli obiettivi dell'attaccante;
  2. ha il messaggio dall'aspetto innocente firmato da una terza parte la cui funzione di firma inizia con l'hashing del messaggio "così com'è".

In entrambe queste condizioni, la terza parte produrrà la firma, che sarà valida (per quanto riguarda i verificatori delle firme) per i messaggi entrambi . È come avere il firmatario emettere una firma su un messaggio senza mostrarlo al firmatario. Una dimostrazione è stata fatta nel 2008 con i "messaggi" come certificati X.509 e il firmatario un'autorità di certificazione. Un'applicazione reale dello stesso concetto è stata eseguita nel malware di fiamma .

Un punto da realizzare è che sebbene le firme grezze siano vulnerabili alle collisioni, come spiegato sopra, possono essere protette dal fatto che il firmatario include una casualità all'inizio di ciò che firma. Nel contesto di certificati X.509 falsi, l'utente malintenzionato deve essere in grado di prevedere tutti i bit dei certificati fino alla chiave pubblica; questo include il numero di serie del certificato scelto dalla CA. Se la CA utilizza numeri seriali casuali di grandi dimensioni, l'attacco non viene applicato, anche se MD5 viene utilizzato come funzione hash. D'altra parte, le CA che utilizzano numeri seriali sequenziali o basati sul tempo sono prevedibili.

Un'altra preoccupazione per le collisioni riguarda le prove di sicurezza . Alcuni protocolli crittografici possono essere dimostrati sicuri in base ad alcune ipotesi specifiche sulle primitive crittografiche utilizzate nel protocollo; ad esempio, alcuni protocolli che utilizzano le funzioni hash possono essere sicuri fino a quando si suppone che la funzione hash sia resistente alla collisione o altre proprietà. Un esempio è HMAC . HMAC riutilizza una funzione di hash sottostante ed è stato progettato in modo da adattarsi alle funzioni hash del Merkle- Damgård persuasion , in particolare MD5 e l'intera famiglia SHA. Tale funzione di hash è costruita attorno a una "funzione di compressione" interna. HMAC è stato provato sicuro supponendo che la funzione di compressione si comporti come una funzione pseudocasuale .

Tuttavia, se la funzione di compressione di MD5 è un PRF, non è possibile calcolare collisioni per MD5 con costi inferiori a 2 64 in media. Sappiamo come produrre collisioni MD5 per molto meno di questo. Ciò implica che la funzione di compressione MD5 è non un PRF. Quindi questo invalida la prova di sicurezza su HMAC / MD5.

Questo non significa che sappiamo come rompere HMAC / MD5 con collisioni! È "solo" che qualsiasi garanzia matematica di sicurezza che abbiamo avuto è svanita come una rugiada mattutina sotto il spietato sole di mezzogiorno. A tale riguardo, le collisioni MD5 non sono uno strumento per essere sfruttate dall'attaccante, ma meritano comunque qualche attenzione.

    
risposta data 16.07.2013 - 20:28
fonte

Leggi altre domande sui tag