Quando si esegue l'hashing, i messaggi più lunghi hanno una maggiore probabilità di collisioni?

Question

Quando si esegue l'hashing, i messaggi più lunghi hanno una maggiore probabilità di collisioni?

#1 da (4 voti)
#2 da (-1 voti)

2

Durante la discussione delle lunghezze massime delle password, un poster ha fatto questo commento:

The longer the allowed input, the easier to supply an input that could cause a hash collision

Per spiegare (poiché la mancanza di contesto potrebbe rendere poco chiaro l'affermazione), il poster afferma che è più facile trovare una collisione hash per una password più lunga che per una più breve. Non l'avevo sentito prima, e ora sono curioso. La mia (ovviamente ingenua) aspettativa è che la probabilità di collisione dovrebbe essere abbastanza indipendente dalla dimensione del messaggio poiché le collisioni si verificano nello spazio di digest e il digest è una lunghezza fissa.

Quali pezzi del puzzle mi mancano? La facilità di trovare una collisione dipende dalla lunghezza dell'input?

passwords hash password-cracking

posta Conor Mancone 18.09.2017 - 19:44

fonte

2 risposte

-1

Penso che il poster del commento si riferisca al seguente:

Man mano che la dimensione dello spazio di input (tutte le stringhe di input possibili) aumenta, la probabilità di trovare una collisione quando si esaurisce lo spazio aumenta e raggiunge infine il 100% quando la dimensione dello spazio di input è maggiore della dimensione di tutti i possibili valori hash.

Esempio:

Supponendo una funzione hash ben gestita a 32 bit. Se si accettano solo le stringhe "0" e "1" come input, la probabilità di collisione dell'hash è bassa poiché la quantità di valori di input (2) è molto, molto più piccola della quantità di valori hash (2 ^ 32 = 4,294,967,296) . La possibilità di collisione è in realtà 1/2 ^ 32.

Tuttavia, se consenti a tutte le possibili stringhe di esattamente 8 caratteri minuscoli alfabetici, avrai la certezza di trovare una collisione hash poiché ora ci sono 26 ^ 8 = 208,827,064,576 valori di input, che è molto più grande di 2 ^ 32.

Modifica: intendevo postare questo come commento, ma non posso ancora commentare ...

risposta data 20.09.2017 - 04:21

fonte

Leggi altre domande sui tag passwords hash password-cracking

Metasploit apre Meterpreter ma non mostra alcun prompt, per favore aiuto Utilizzo di una tabula recta per memorizzare le password

score 4 · Accepted Answer

What pieces of the puzzle am I missing? Does the ease of finding a collision depend on input length?

Per trovare una collisione non è rilevante la durata di una stringa (a parte il tempo necessario per calcolare l'hash - che in realtà è più lungo per le stringhe lunghe) ma quante stringhe si provano. Dato che più ingressi hai, più alto è il caso che uno di questi risultati abbia lo stesso valore di hash (lunghezza fissa), cioè una collisione. E ci sono semplicemente più lunghe stringhe diverse rispetto alle stringhe corte.

Ad esempio: ci sono 10 ^ 3 = 1000 stringhe con 3 cifre ma già 10 ^ 6 = 1000000 stringhe con 6 cifre. Se immagini un hash composto da 4 cifre, potrebbe esserci una collisione con le stringhe a 3 cifre, ma ci saranno sicuramente molte collisioni all'interno delle stringhe a 6 cifre perché ci sono molti più valori di stringa rispetto ai valori hash.

The longer the allowed input, the easier to supply an input that could cause a hash collision

L'affermazione che citi è sbagliata nella forma attuale. È vero che la possibilità è più alta che le stringhe che troverai saranno lunghe. Ma poiché ci sono molte più lunghe di quelle corte, questo non rende più facile trovare una collisione. Di nuovo, ciò che conta è il numero di diversi input che hai e non la lunghezza.