¿Cómo se puede encontrar una cadena cuyo hash MD5 tiene un prefijo específico?

1

He oído que hay una cadena que contiene solo las letras de la A a la Z cuyo hash MD5 comienza con el prefijo hexadecimal 314159265358 y el resto puede ser arbitrario. ¿Cómo se puede encontrar una cadena de este tipo y cuánto tiempo tomaría la búsqueda en una computadora portátil normal?

    
pregunta pi_layman 24.04.2018 - 22:51
fuente

2 respuestas

2

La única forma de encontrar un hash con un valor específico (sin tener en cuenta los ataques previos a la imagen, contra el que MD5 todavía está seguro) es mediante valores hash hasta que encuentre uno que coincida. 314159265358 son 12 caracteres hexadecimales, que son 48 bits. Usted esperaría encontrar un prefijo específico de 48 bits después de 2 47 con una probabilidad del 50%, por lo que la pregunta es qué tan rápido puede hacer 2 47 en "una computadora portátil normal "?

Mi computadora portátil se está volviendo bastante vieja ahora (creo que en 2013) pero ejecuté hashcat en el modo de referencia para ver qué tan bien podría funcionar. La GPU (GT 730M) pudo realizar 535.6 MH / s, por lo que esperaría que 2 hash 47 tomen alrededor de 73 horas. Un GTX 1080 aparece para alcanzar alrededor de 25 GH / s, por lo que solo tomaría alrededor de una hora y media. Por supuesto, eso es solo para un 50% de probabilidad; podría tomar más o menos tiempo que eso, pero es una estimación decente.

El hecho de que la cadena con hash contenga solo a-z es mayormente irrelevante, ya que las funciones de hash toman una entrada arbitraria y generan de manera determinista un número fijo de bits. Dado que la entrada está restringida a menos caracteres, puede terminar con una cadena más grande para el hash, lo que podría hacer que el hash sea más lento a medida que se trata de más datos. Parece que MD5 funciona en un bloque de 512 bits, pero debido a su relleno, solo puede hash 447 bits antes de usar 2 bloques (lo que presumiblemente causaría que tomara aproximadamente el doble de tiempo, pero no lo he probado). 447 bits se redondean a 440/8 = 55 bytes, por lo que puede hacer un hash de 55 caracteres antes de perder rendimiento. 55 caracteres con 26 valores posibles es 26 55 ; log 2 (26 55 ) ~ = 258, que es significativamente más grande que el tamaño de salida de 128 bits, por lo que espero que casi todas las salidas posibles de MD5 puedan generarse mediante el hashing una cadena de [a-z]{1,55} .

    
respondido por el AndrolGenhald 25.04.2018 - 01:45
fuente
0

Hay una cantidad infinita de cadenas que tendrán un resultado MD5 comenzando con la cadena fija que desee, por la sencilla razón de que el espacio de entrada de MD5 es infinito, mientras que la salida es finita y está limitada a 128 bits.

Por supuesto, no puede encontrarlos con una sola operación, básicamente tiene que probarlos a todos cuando esté satisfecho.

Entonces, en su caso, comienza con a , calcula MD5, prueba con sus criterios, se detiene aquí o pasa al siguiente caso b ... hasta z , luego aa hasta az , ba hasta bz y luego hasta zz , luego aaa , etc.

Luego puede aplicar varias optimizaciones, incluyendo el uso de listas de hashes precomputados que puede encontrar en línea. Eche un vistazo a "Rainbow Tables", por ejemplo aquí: enlace Algunos pueden ofrecerle "búsqueda inversa", pero, por supuesto, eso no puede ser exhaustivo.

En cuanto al tiempo que puede tomar, como decimos en francés: "depende". No hay absolutamente ninguna manera de proporcionarle números concretos precisos para este tipo de pregunta de rendimiento, ya que depende demasiado del hardware.

Por cierto, ¿qué es una computadora portátil "normal"?

    
respondido por el Patrick Mevzek 25.04.2018 - 01:00
fuente

Lea otras preguntas en las etiquetas