Hash crittografiche

L’obiettivo è quello di ottenere una collisione.

Quale è il numero minimo di tentativi affinchè la probabilità di successo sia maggiore a 0,5? Può

essere riconducibile al problema dei compleanni.

Dato un valore di hash, la probabilità che considerando un’altra pre immagine si riottenga lo stesso

valore di hash è 1/n perché abbiamo n possibilità.

Se consideriamo la probabilità che sia diverso si fa il complemento ossia 1-(1/n). k

Se consideriamo con k tentativi indipendenti la probabilità che nessuno di questi riesca è [1-(1/n)]

m

Il numero di combinazioni possibili se il valore hash è un valore ad m bit è 2 (m-1)

Numero medio di tentativi per avere una probabilità di successo maggiore del 50% è 2

Se vogliamo valutare la capacità di resistere ad attacchi di tipo collisione l’obiettivo non è di trovare

una preimmagine a partire dall’hash, ma è di trovare direttamente due ingressi (preimmagini che

danno lo stesso valore di hash): si ha un hash range [1-n].

La probabilità che sia diverso al secondo tentativo è (n-1)/n

Su k tentativi la probabilità di non trovare match ossia di avere tutti i valori hash generati diversi tra

loro è (n-k+1)/n.  per l’attaccante questa è la probabilità di insuccesso

La probabilità di successo per l’attaccante è 1 – [(n-k+1)/n].

Il procedimento di attacchi alle collisioni a forza bruta è il seguente:

Il mittente vuole firmare un messaggio; per mettere la sua firma fa l’hash del messaggio e lo cifra

con la sua chiave privata in modo da aver garantito che è lui che ha creato quell’hash. L’attaccante

genera un numero di variazioni del messaggio originario con lo stesso significato; prende questi

messaggi che ha generato e ne calcola il valore di hash e lo memorizza; poi prepara un messaggio

fraudolento dove desidera che A sia il firmatario generando una serie di variazioni su quel

messaggio e per ogni variazione si calcola l’hash; poi continua fino a quando non trova un match