Md5 ha una garanzia di univocità per le stringhe corte (numero finito di stringhe)?

Quindi ho capito che MD5 non è in grado di garantire univocità dato che ci sono più stringhe nell'universo rispetto alle stringhe di hash MD5, ma esiste una prova inversa per un numero finito di stringhe?Md5 ha una garanzia di univocità per le stringhe corte (numero finito di stringhe)?

Fondamentalmente, se ho delle stringhe di lunghezza massima di X, esiste una X per cui MD5 è garantito come univoco? se sì, allora cos'è quella X? e se ci sono più di un valore per X, qual è il valore massimo di X?

oppure c'è una tale X per qualsiasi altro algoritmo di hashing, SHA-1, ecc.?

fonte

2012-05-15 xtrahelp.com

x = 1024 bit in base alla seguente risposta http://stackoverflow.com/questions/1999824/whats-the-shortest-pair-of-strings-that-causes-an-md5-collision – Oli

@ Oli- risposta dice che la collisione di hash * not * più breve richiede 1024 bit. Poiché MD5 emette valori a 128 bit, è garantito che la collisione hash più breve deve essere molto più breve di 1024 bit. – templatetypedef

quindi è dimostrato che ** non è univoco ** per 1024 bit, ma ha dimostrato di essere ** unico ** per meno di 1024 bit? –

La risposta alla tua domanda è sì. Per qualsiasi funzione di hash, esiste una lunghezza massima X per cui si otterranno stringhe uniche. Trovare X, però, potrebbe essere molto difficile. L'idea è di eseguire questo programma:

X= 0; 
For i = 0 onward 
    For all strings of length i 
     Compute the hash code of that string. 
     If a collision is found, return X. 
    X = i

L'idea è di elencare solo stringhe sempre più lunghe fino a trovare una collisione hash. Alla fine dovrai farlo, poiché alla fine avrai generato più stringhe di quante siano le uscite hash possibili.

In attesa, supponendo che una funzione di hash sia in realtà abbastanza casuale, sarà necessario generare O (√ U) stringhe diverse prima di trovare una collisione, dove U è la dimensione dello spazio a cui la funzione hash si associa . Per gli hash a 256 bit, questo è 2 . Ciò significa che in pratica il programma di cui sopra non terminerebbe mai in realtà a meno che la funzione di hash non fosse abbastanza rotta, ma in teoria significa che il tuo numero X esiste.

Spero che questo aiuti!

fonte

2012-05-15 03:47:39 templatetypedef

beh sì, quindi qualcuno ha ancora trovato quella X? –

@templatetypedef che l'asserzione in realtà non tiene - ci sono un sacco di collisioni note e, per questo, gli attacchi che le usano, su algoritmi hash considerati forti. –

@ CharlesDuffy- Sì, hai ragione (mi dispiace per quello!).La mia intenzione era che trovare questo valore di X avrebbe probabilmente implicato che qualcuno avesse trovato la collisione di hash più breve, e la mia comprensione è che per la maggior parte delle funzioni hash questo non è ancora stato fatto (sappiamo solo di collisioni di hash brevi, non le più corte) . – templatetypedef

Riassumendo le risposte eccellenti qui: What's the shortest pair of strings that causes an MD5 collision?

L'attacco più breve nota su MD5 richiede 2 blocchi di ingresso, cioè 128 byte o 1024 bit.

Per qualsiasi algoritmo di hash che emette N bit, supponendo che distribuisca gli input approssimativamente in modo casuale, è possibile ipotizzare che una collisione sia più del 50% probabile in circa gli ingressi sqrt(2^N). Ad esempio, MD5 hash a 128 bit, quindi puoi aspettarti una collisione tra tutti gli input a 64 bit. Questo presuppone un hash uniformemente casuale. Eventuali punti deboli ridurrebbero il numero di input prima che si possa verificare una collisione.

fonte

2012-05-15 03:50:58 Clueless

La domanda precedente chiede la più piccola * nota * collisione dell'hash. Il valore di 1024 bit è molto più grande della dimensione di output della funzione hash di 128 bit e la risposta non ha senso in questa domanda. – templatetypedef

Bene, ci si può aspettare uno in ~ 64 bit, ma sappiamo solo come generarli in modo affidabile in 1024 bit. Non so se qualcuno abbia testato tutti gli ingressi brevi ~ 2^64 per le collisioni. È un sacco di lavoro, molti anni su un computer, ma non impossibile. – Clueless

@Clueless: ottengo 11000 anni per una macchina a 8 core a 4 GHz utilizzando 600 cicli per hash (utilizzando http://cr.yp.to/talks/2008.06.05/slides.pdf come riferimento per 600 cicli). – Charles

Md5 ha una garanzia di univocità per le stringhe corte (numero finito di stringhe)?

risposta

Problemi correlati