Perché trovare una strong collisione solo metà del lavoro di una collisione debole?

Question

Perché trovare una strong collisione solo metà del lavoro di una collisione debole?

#1 da (3 voti)
#2 da (2 voti)

1

Riguardo alle collisioni di hash, un utente malintenzionato deve fare solo metà del lavoro per trovare una collisione quando può controllare entrambi i messaggi rispetto a quando sta cercando di trovare una collisione debole. Questo può essere spiegato con il paradosso del compleanno.

Capisco il paradosso del compleanno, ma non riesco a capire come si rapporta pienamente a forti collisioni e perché mostra che impiegano solo metà del lavoro di collisioni deboli. Con il paradosso del compleanno, ogni persona conosce già in anticipo il proprio compleanno, quindi quando la prima persona "dice" il proprio compleanno, tutti gli altri possono confrontarlo con il proprio, e così via e così via.

Se un utente malintenzionato tenta di trovare due hash dello stesso valore, gli hash dei messaggi appena modificati non sono già noti (diversamente dai compleanni delle persone), quindi un utente malintenzionato non deve creare un carico di hash per uno dei messaggi, memorizzali e poi fai lo stesso per l'altro messaggio e inizia a confrontare, quanto è più veloce di trovare una collisione debole?

La mia domanda è: in che modo un utente malintenzionato tenta di trovare due hash dello stesso valore, in modo tale che ci vuole solo metà del lavoro come se cercassero di trovare una collisione debole?

Grazie.

hash

posta RJSmith92 25.10.2015 - 00:29

fonte

2 risposte

2

Trovare una collisione usando il problema del compleanno significa che durante l'attacco stai memorizzando gli hash di tutti i tentativi precedenti, e per ogni nuovo hash, lo stai confrontando con tutti gli hash precedenti.

Invece di puntare su un certo hash, stiamo cercando la collisione .

Supponendo che abbiamo molta memoria e possiamo controllare rapidamente tutti gli hash precedenti, diventa più veloce.

risposta data 25.10.2015 - 00:44

fonte

Leggi altre domande sui tag hash

Gli attacchi man-in-the-middle possono colpire chiunque non sia connesso alla rete degli attaccanti? Come dovremmo archiviare e condividere documenti con accesso limitato

score 3 · Accepted Answer

Per trovare una collisione, l'attaccante genera un gran numero di messaggi unici e i loro hash corrispondenti. L'attacco ha esito positivo quando qualsiasi due hash corrisponde. Questo è proprio come il paradosso del compleanno, che parla della probabilità che qualsiasi due abbia la stessa data di nascita.

it only takes half the work

Attento, 2 ^ 128 non è la metà di 2 ^ 256. 2 ^ 128 è la radice quadrata di 2 ^ 256. 2 ^ 128 è un "2 ^ 128th" di 2 ^ 256.

the attacker has 2 messages 'place 10$ in my account' and 'place $1000 in my account' and they want them to hash to the same value [...] the attacker would continually keep changing both message until they hash to the same value

In questa situazione, l'attaccante riceve m1 e m2, e vuole trovare un x1 e x2 tale che H (m1 + x1) = H (m2 + x2). Supponiamo che H sia una funzione hash a 256 bit, come SHA-256. L'utente malintenzionato tenta 2 ^ 128 valori diversi per x1, calcolando e memorizzando 2 ^ 128 hash H (m1 + x1). L'utente malintenzionato prova ora diversi valori per x2, calcolando hash H (m2 + x2), cercando uno che corrisponda a uno degli hash x1. Alla fine, questo avrà successo, ma dopo quanti tentativi?

Ci sono 2 ^ 256 possibili valori di hash, quindi la probabilità di ciascun tentativo è 2 ^ 128/2 ^ 256 = 1/2 ^ 128. Pertanto, possiamo aspettarci che questo passaggio richieda circa 2 ^ 128 tentativi. Aggiungendo i due passi insieme, questo attacco richiederebbe, in media, circa 2 ^ 128 + 2 ^ 128 = 2 ^ 129 valutazioni della funzione di hash.

Non penso che di solito questo si chiama "attacco di compleanno", dal momento che la matematica delle probabilità è molto diversa. Entrambi gli attacchi hanno una complessità simile, tuttavia (su una radice quadrata dello spazio di ricerca, o 2 ^ (n / 2) per una funzione di hash n-bit).