Un hash ha più di un possibile messaggio originale? [duplicare]

Question

Un hash ha più di un possibile messaggio originale? [duplicare]

#1 da (2 voti)

2

Molti algoritmi di hashing sembrano avere un digest di messaggi a lunghezza fissa come output.

Se computo l'hash md5 di due stringhe:

>>> hashlib.md5("This is a really really long text string to make a hash out of").hexdigest()
'2916991b5ebba69ab38a84a0a72b4176'

>>> hashlib.md5("Short").hexdigest()
'30bb747c98bccdd11b3f89e644c4d0ad'

Ricevo un'uscita di 32 caratteri per ciascuno, anche se c'è una differenza significativa nelle lunghezze degli input. E 'teoricamente possibile che io possa inventare due (o più) input completamente diversi che generano lo stesso output, dal momento che ci sono infinite possibilità per un input e solo un numero finito di caratteri con cui lavorare per l'output?

Se sì, qual è la probabilità di trovare un altro input che generi lo stesso output?

cryptography

posta jdickson 03.07.2012 - 00:19

fonte

1 risposta

Leggi altre domande sui tag cryptography

È sicuro che la porta 443 non è protetta dal firewall senza applicazione? Che cos'è un attacco attivo?

score 2 · Accepted Answer

Is it theoretically possible that I could come up with two (or more) completely different inputs that generate the same output, since there are infinite possibilities for an input and only a finite number of characters to work with for the output?

Sì, è teoricamente possibile. Ma le funzioni di hash sono così progettate per renderlo praticamente difficile. Quando dico praticamente difficile, intendo che occorreranno immensi cicli di calcolo (che si traducono in denaro e tempo) per calcolare una collisione.

If yes, what is the likelihood of finding another input that would generate the same output?

Dipende dalle funzioni di hash. La proprietà è chiamata Resistenza collisione

Per rappresentare tramite un esempio, consente di costruire una funzione hash che blocca i numeri in uno spazio indirizzo risultante più piccolo [0, 9]. La nostra semplice funzione di hash è hash(X) = X mod 10 . Quindi

hash(10)   = 0
hash(1864) = 4

Questa è una funzione di hash valida ma ha una resistenza di collisione molto scarsa. Ad esempio, l'hash di 24 e 1284 è lo stesso. Se si sta facendo affidamento sull'hash (4 in questo caso) per l'integrità del messaggio, un utente malintenzionato può tranquillamente sostituire il messaggio 24 a 1284 che esegue lo hash allo stesso valore. Questo particolare attacco è chiamato attacco Preimage La resistenza alla collisione di Preimage è una proprietà primaria di qualsiasi funzione di hash.