Come si può trovare una stringa il cui hash MD5 ha un prefisso specifico?

1

Ho sentito che esiste una stringa che contiene solo le lettere dalla a alla z il cui hash MD5 inizia con il prefisso esadecimale 314159265358 e il resto può essere arbitrario. Come si può trovare una stringa di questo tipo e quanto tempo impiegherebbe la ricerca su un normale laptop?

    
posta pi_layman 24.04.2018 - 22:51
fonte

2 risposte

2

L'unico modo per trovare un hash con un valore specifico (ignorando gli attacchi preimage, a cui MD5 è ancora protetto) è quello di eseguire i valori hash finché non ne trovi uno corrispondente. 314159265358 è 12 caratteri esadecimali, ovvero 48 bit. Ci si aspetterebbe di trovare uno specifico prefisso a 48 bit dopo che 2 47 suppone con probabilità 50%, quindi la domanda diventa quanto velocemente si possono fare 2 hash 47 su un normale laptop "?

Il mio laptop sta diventando piuttosto vecchio ora (penso che il 2013), ma ho eseguito hashcat su di esso in modalità benchmark per vedere come avrebbe potuto farlo. La GPU (GT 730M) è stata in grado di eseguire 535.6 MH / s, quindi mi aspetterei 2 hash 47 per circa 73 ore. Un GTX 1080 viene visualizzato per raggiungere circa 25 GH / s, quindi ci vorrebbe solo circa un'ora e mezza. Certo, è solo per una probabilità del 50%; potrebbe volerci più o meno tempo, ma è una stima decente.

Che la stringa con hash contiene solo a-z è per lo più irrilevante, poiché le funzioni di hash accettano input arbitrari e determinano in modo deterministico un numero fisso di bit. Dal momento che l'input è limitato a un numero inferiore di caratteri, è possibile che si ottenga una stringa più grande in hash, che potrebbe causare un rallentamento dell'hash in quanto esegue l'hashing di più dati. MD5 sembra funzionare su un blocco a 512 bit, ma a causa del suo padding puoi solo hash 447 bit prima di usare 2 blocchi (che presumibilmente lo farebbe prendere circa il doppio del tempo, ma non ho provato). 447 bit arrotondati a 440/8 = 55 byte, quindi è possibile eseguire l'hashing di 55 caratteri prima di perdere prestazioni. 55 caratteri con 26 valori possibili è 26 55 ; log 2 (26 55 ) ~ = 258, che è significativamente più grande della dimensione di output a 128 bit, quindi mi aspetto che quasi tutti gli output MD5 possano essere generati da hash una stringa di [a-z]{1,55} .

    
risposta data 25.04.2018 - 01:45
fonte
0

C'è una quantità infinita di stringhe che avranno un risultato MD5 che inizia con qualsiasi stringa fissa che ti piace, per la semplice ragione che lo spazio di input di MD5 è infinito mentre quello di uscita è finito e limitato a 128 bit.

Ovviamente non puoi trovarli con una sola operazione, devi fondamentalmente metterli alla prova quando sei felice.

Quindi nel tuo caso inizi con a , calcoli MD5, prova con i tuoi criteri, fermati qui o vai al prossimo caso b ... fino a z , poi aa fino a az , ba fino a bz e quindi fino a zz , quindi aaa , ecc.

Quindi puoi applicare varie ottimizzazioni, incluso l'utilizzo di elenchi di hash precompilati che puoi trovare online. Dai un'occhiata a "Rainbow Tables", per esempio qui: link Alcuni potrebbero offrirti "ricerca inversa", ma ovviamente non può essere esaustivo.

Per quanto tempo ci vorrà, come diciamo in francese: "dipende". Non c'è assolutamente alcun modo di darti dei veri numeri precisi per questo tipo di domande sulle prestazioni, dipende troppo dall'hardware.

A proposito, che cos'è un laptop "normale"?

    
risposta data 25.04.2018 - 01:00
fonte

Leggi altre domande sui tag