Differenza tra seconda resistenza pre-immagine e resistenza di collisione nelle funzioni hash crittografiche

7

Sto studiando l'argomento da queste note. Tuttavia non è chiaro qual è la differenza tra le proprietà "Seconda resistenza pre-immagine" e "Resistenza collisione" delle Funzioni hash crittografiche.

Come le note dicono in "Second Pre-image Resistance", dato x1 è computazionalmente impossibile dedurre x2 tale che h (x1) = h (x2). Qual è la relazione tra x1 e x2 qui?

In "Collision Resistance", è computazionalmente impossibile trovare un x1! = x2 tale che h (x1) = h (x2). È un sotto-caso di "Second Pre-image Resistance", dove x1! = X2?

Potresti chiarire la differenza tra questi due?

    
posta Michael 10.10.2014 - 20:29
fonte

2 risposte

8

Resistenza alla collisione riguarda l'impossibilità di trovare due distinti input m e m tali che h ( m ) = h ( m '). L'autore dell'attacco può scegliere arbitrariamente m e m , finché finisce con due messaggi distinti che cancellano lo stesso valore.

La resistenza del secondo preimage è molto simile, tranne per il fatto che l'attaccante non può scegliere m . Invece, gli diamo m e lo sfidiamo a trovare m (distinto da m ) tale che h ( m ) = h ( m ').

Anche un secondo preimage è una collisione, ma manteniamo il concetto distinto perché le seconde pre-immagini dovrebbero essere sostanzialmente più difficili. Se la funzione hash ha un'uscita di bit n ed è "perfetta" (nessuna debolezza nota), allora il costo di trovare una collisione è 2 n / 2 , mentre il costo di trovare un secondo preimage è 2 n (cioè molto di più).

Supponiamo che stiamo parlando di firme. Poiché un algoritmo di firma inizia con l'hashing dei dati che devono essere firmati e quindi funziona solo con il valore hash risultante, ne consegue che se h ( m ) = < em> h ( m '), quindi una firma s sul messaggio m sarà anche una firma valida sul messaggio m '. L'obiettivo dell'attaccante è di forgiare una firma, cioè ottenere una firma che sembra valida su un messaggio di sua scelta.

Se l'utente malintenzionato vede un messaggio m valido e firmato, allora potrebbe voler trovare un messaggio m ' che abbia lo stesso valore. Questo è il secondo modello di pre-imaging. Affinché il sistema di firma sia robusto, la funzione di hash deve fornire una resistenza di preimpressione secondaria.

La resistenza alle collisioni, d'altra parte, non è necessaria in questo caso. È necessario, tuttavia, con un altro modello in cui l'autore dell'attacco possa ottenere una firma su un messaggio m che sembra innocente e desidera che tale firma sia valida anche su un messaggio m con contenuti meno benigni. Per esempio, io sono l'attaccante e ti mando un contratto dove prometti di mandarmi 1 $. Tuttavia, ho creato quel contratto m in modo tale che collide (hash allo stesso valore) con un contratto leggermente diverso m ', dove prometti di inviarmi 1000000 $. Se riesco a farti firmare il primo contratto, quindi, grazie alla collisione, la tua firma si applica anche al secondo (e perdi).

Quindi, la resistenza alla collisione e la resistenza alla pre-seconda sono due concetti distinti e ciò che è necessario dipende dal contesto. Nel caso delle firme, hai bisogno della almeno resistenza pre-seconda; ma se il contesto è tale che l'attaccante può ottenere le firme sui dati che sceglie, allora è necessaria anche la resistenza alle collisioni. Questo è stato dimostrato con MD5 come funzione di hash e certificati X.509 (attenzione ai dettagli: il l'attacco di collisione su MD5 potrebbe essere applicato ai certificati perché i ricercatori hanno trovato una CA che genera numeri seriali di certificati in modo prevedibile).

    
risposta data 10.10.2014 - 21:24
fonte
2

La seconda resistenza pre-immagine ha semplicemente più vincoli della resistenza alla collisione.

Nei tuoi esempi, x1 e x2 sono gli input e h (x1) eh (x2) sono le uscite.

Per la seconda resistenza pre-immagine, viene assegnato x1 e deve trovare un input (x2) che esegue lo hash sullo stesso valore di output. Non puoi scegliere x1 in questo attacco.

Non esiste un tale vincolo per la resistenza alle collisioni. Sei libero di scegliere entrambi x1 e x2 nel tentativo di trovare una collisione delle uscite.

    
risposta data 10.10.2014 - 20:37
fonte

Leggi altre domande sui tag