¿Cómo es que los valores hash MD5 no son reversibles?

https://stackoverflow.com/questions/330207

11-07-2019
|

Pregunta

Un concepto que siempre me he preguntado es el uso de funciones y valores criptográficos hash. Entiendo que estas funciones pueden generar un valor hash que es único y prácticamente imposible de revertir, pero esto es lo que siempre me he preguntado:

Si en mi servidor, en PHP produzco:

md5("stackoverflow.com") = "d0cc85b26f2ceb8714b978e07def4f6e"

Cuando ejecuta esa misma cadena a través de una función MD5, obtiene el mismo resultado en su instalación de PHP. Se está utilizando un proceso para producir algún valor, a partir de algún valor inicial.

¿No significa esto que hay alguna forma de deconstruir lo que está sucediendo y revertir el valor hash?

¿Qué tienen estas funciones que hace que las cadenas resultantes sean imposibles de rastrear?

Solución

El material de entrada puede tener una longitud infinita, donde la salida siempre tiene 128 bits de longitud. Esto significa que un número infinito de cadenas de entrada generará la misma salida.

Si elige un número aleatorio y lo divide entre 2 pero solo escribe el resto, obtendrá un 0 o 1, par o impar, respectivamente. ¿Es posible tomar ese 0 o 1 y obtener el número original?

Otros consejos

Si las funciones hash como MD5 fueran reversibles, ¡habría sido un evento decisivo en la historia de los algoritmos de compresión de datos! Es fácil ver que si MD5 fuera reversible, los fragmentos arbitrarios de datos de tamaño arbitrario podrían representarse con solo 128 bits sin pérdida de información. Por lo tanto, podría haber reconstruido el mensaje original a partir de un número de 128 bits, independientemente del tamaño del mensaje original.

Contrariamente a lo que enfatizan las respuestas más votadas aquí, la no inyectividad (es decir, que hay varias cadenas que combinan con el mismo valor) de una función de cifrado criptográfica causada por la diferencia entre grandes (potencialmente infinito) tamaño de entrada y tamaño de salida fijo no es el punto importante & # 8211; en realidad, preferimos las funciones hash donde esas colisiones ocurren tan raramente como sea posible.

Considere esta función (en notación PHP, como la pregunta):

function simple_hash($input) {
     return bin2hex(substr(str_pad($input, 16), 0, 16));
}

Esto agrega algunos espacios, si la cadena es demasiado corta, y luego toma los primeros 16 bytes de la cadena, luego la codifica como hexadecimal. Tiene el mismo tamaño de salida que un hash MD5 (32 caracteres hexadecimales o 16 bytes si omitimos la parte bin2hex).

print simple_hash("stackoverflow.com");

Esto generará:

737461636b6f766572666c6f772e636f6d

Esta función también tiene la misma propiedad de no inyectividad resaltada por la respuesta de Cody para MD5: podemos pasar cadenas de cualquier tamaño (siempre que quepan en nuestra computadora), y generará solo 32 dígitos hexadecimales. Por supuesto que no puede ser inyectable.

Pero en este caso, es trivial encontrar una cadena que se asigne al mismo hash (solo aplica hex2bin en tu hash, y lo tienes). Si su cadena original tenía la longitud 16 (como nuestro ejemplo), incluso obtendrá esta cadena original. Nada de este tipo debería ser posible para MD5, incluso si sabe que la longitud de la entrada fue bastante corta (aparte de intentar todas las entradas posibles hasta encontrar una que coincida, por ejemplo, un ataque de fuerza bruta).

Los supuestos importantes para una función hash criptográfica son:

es difícil encontrar una cadena que produzca un hash dado (resistencia previa a la imagen)
es difícil encontrar una cadena diferente que produzca el mismo hash que una cadena dada (segunda resistencia de preimagen)
es difícil encontrar un par de cuerdas con el mismo hash (resistencia a la colisión)

Obviamente mi función simple_hash no cumple ninguna de estas condiciones. (En realidad, si restringimos el espacio de entrada a `` cadenas de 16 bytes '', entonces mi función se vuelve inyectiva y, por lo tanto, es incluso resistente a la segunda imagen previa y a la colisión).

Ahora existen ataques de colisión contra MD5 (por ejemplo, es posible producir un par de cadenas, incluso con un mismo prefijo dado, que tienen el mismo hash, con bastante trabajo, pero no mucho trabajo imposible), por lo que no debería No use MD5 para nada crítico. Todavía no hay un ataque de preimagen, pero los ataques mejorarán.

Para responder la pregunta real:

¿Qué tienen estas funciones que hace que el ¿Cadenas resultantes imposibles de volver?

Lo que efectivamente hace MD5 (y otras funciones hash basadas en la construcción Merkle-Damgard) es aplicar un algoritmo de cifrado con el mensaje como clave y algún valor fijo como "texto plano", utilizando el texto cifrado resultante como hash . (Antes de eso, la entrada se rellena y se divide en bloques, cada uno de estos bloques se usa para cifrar la salida del bloque anterior, XORed con su entrada para evitar cálculos inversos).

Los algoritmos de cifrado modernos (incluidos los que se usan en las funciones hash) se hacen de una manera que dificulta la recuperación de la clave, incluso dado el texto plano y el texto cifrado (o incluso cuando el adversario elige uno de ellos). Lo hacen generalmente haciendo muchas operaciones de mezcla de bits de manera que cada bit de salida esté determinado por cada bit de clave (varias veces) y también por cada bit de entrada. De esa manera, solo puede volver sobre lo que sucede si conoce la clave completa y la entrada o salida.

Para funciones hash similares a MD5 y un ataque de preimagen (con una cadena hash de un solo bloque, para facilitar las cosas), solo tiene entrada y salida de su función de cifrado, pero no la clave (esto es lo que está buscando para).

La respuesta de Cody Brocious es la correcta. Estrictamente hablando, no puedes '' invertir '' una función hash porque muchas cadenas se asignan al mismo hash. Sin embargo, observe que encontrar una cadena que se asigna a un hash determinado o encontrar dos cadenas que se asignan al mismo hash (es decir, una colisión ), serían avances importantes para un criptoanalista. La gran dificultad de ambos problemas es la razón por la cual las buenas funciones hash son útiles en criptografía.

MD5 no crea un valor hash único; El objetivo de MD5 es producir rápidamente un valor que cambie significativamente en función de un cambio menor en la fuente.

Por ejemplo,

"hello" -> "1ab53"
"Hello" -> "993LB"
"ZR#!RELSIEKF" -> "1ab53"

(Obviamente, eso no es cifrado MD5 real)

La mayoría de los hashes (si no todos) tampoco son únicos; más bien, son únicos suficientes , por lo que una colisión es altamente improbable, pero aún posible.

Una buena manera de pensar en un algoritmo hash es pensar en cambiar el tamaño de una imagen en Photoshop ... digamos que tiene una imagen de 5000x5000 píxeles y luego cambiar el tamaño a solo 32x32. Lo que tiene todavía es una representación de la imagen original, pero es mucho más pequeña y efectivamente se ha descartado. ciertas partes de los datos de la imagen para que quepan en el tamaño más pequeño. Entonces, si tuviera que cambiar el tamaño de esa imagen de 32x32 a 5000x5000, todo lo que obtendría sería un desastre borroso. Sin embargo, debido a que una imagen de 32x32 no es tan grande, ¡sería teóricamente concebible que otra imagen se redujera para producir exactamente los mismos píxeles!

Eso es solo una analogía, pero ayuda a entender lo que está haciendo un hash.

Una colisión de hash es mucho más probable de lo que piensas. Eche un vistazo a la cumpleaños paradoja para comprender mejor por qué es eso.

Como el número de archivos de entrada posibles es mayor que el número de salidas de 128 bits, es imposible asignar de forma exclusiva un hash MD5 a cada posible.

Las funciones hash criptográficas se utilizan para verificar la integridad de los datos o las firmas digitales (el hash se firma por eficiencia). Por lo tanto, cambiar el documento original debería significar que el hash original no coincide con el documento alterado.

Estos criterios a veces se usan:

Resistencia de preimagen: para una función hash dada y un hash dado, debería ser difícil encontrar una entrada que tenga el hash dado para esa función.
Segunda resistencia de preimagen: para una función y entrada de hash dada, debería ser difícil encontrar una segunda entrada diferente con el mismo hash.
Resistencia de colisión: para un dado tiene función, debería ser difícil encontrar dos entradas diferentes con el mismo hash.

Estos criterios se eligen para dificultar la búsqueda de un documento que coincida con un hash dado; de lo contrario, sería posible falsificar documentos reemplazando el original por uno que coincida con el hash. (Incluso si el reemplazo es un galimatías, el simple reemplazo del original puede causar interrupciones).

El número 3 implica el número 2.

En cuanto a MD5 en particular, se ha demostrado que es defectuoso: Cómo romper MD5 y otras funciones hash .

Pero aquí es donde entran en juego las mesas arcoiris. Básicamente, se trata de una gran cantidad de valores divididos por separado y luego el resultado se guarda en el disco. Entonces el bit de inversión es '' solo '' hacer una búsqueda en una tabla muy grande.

Obviamente, esto solo es factible para un subconjunto de todos los valores de entrada posibles, pero si conoce los límites del valor de entrada, podría ser posible calcularlo.

Un científico chino ha encontrado una forma llamada "colisiones de prefijo elegido" hacer un conflicto entre dos cadenas diferentes.

Aquí hay un ejemplo: http://www.win .tue.nl / hashclash / fastcoll_v1.0.0.5.exe.zip
El código fuente: http://www.win.tue.nl/hashclash /fastcoll_v1.0.0.5_source.zip

Como la mayoría ya ha dicho, MD5 fue diseñado para que las secuencias de datos de longitud variable se mezclen en una porción de datos de longitud fija, por lo que muchas secuencias de datos de entrada comparten un solo hash.

Sin embargo, si alguna vez tuvo que encontrar los datos originales de la suma de verificación, por ejemplo, si tiene el hash de una contraseña y necesita encontrar la contraseña original, a menudo es más rápido simplemente buscar en Google (o cualquier buscador que prefiera) ) el hash para la respuesta que la fuerza bruta. He encontrado con éxito algunas contraseñas con este método.

La mejor manera de entender lo que significan todas las respuestas más votadas es tratar de revertir el algoritmo MD5. Recuerdo que intenté revertir el algoritmo MD5crypt hace algunos años, no recuperar el mensaje original porque es claramente imposible, sino solo generar un mensaje que produzca el mismo hash que el hash original. Esto, al menos teóricamente, me proporcionaría una forma de iniciar sesión en un dispositivo Linux que almacenó al usuario: contraseña en el archivo / etc / passwd usando el mensaje generado (contraseña) en lugar de usar el original. Dado que ambos mensajes tendrían el mismo hash resultante, el sistema reconocería mi contraseña (generada a partir del hash original) como válida. Eso no funcionó en absoluto. Después de varias semanas, si no recuerdo mal, el uso de sal en el mensaje inicial me mató. Tenía que producir no solo un mensaje inicial válido, sino un mensaje inicial válido con sal, que nunca pude hacer. Pero el conocimiento que obtuve de este experimento fue agradable.

por definición, función Hash (hash criptográfico): no debe ser invertible; no debe tener colisiones (lo menos posible).

regd tu pregunta: es un hash unidireccional. La entrada (independientemente de la longitud) generará una salida de tamaño fijo (se rellenará según algo (límite de 512 bits para MD5)). La información está comprimida (perdida) y prácticamente no es posible generarla a partir de transformaciones inversas.

información adicional sobre MD5: es vulnerable a colisiones. revisado este artículo recientemente, http://www.win.tue.nl/hashclash/Nostradamus/

abre el código fuente para implementaciones de cifrado hash (MD5 y SHA) que se pueden encontrar en el código de Mozilla. (biblioteca freebl).

Hoy en día, los hash MD5 o cualquier otro hash para ese asunto se calculan previamente para todas las cadenas posibles y se almacenan para facilitar el acceso. Aunque en teoría MD5 no es reversible, pero utilizando tales bases de datos puede descubrir qué texto resultó en un valor hash particular.

Por ejemplo, pruebe el siguiente código hash en http://gdataonline.com/seekhash.php para averiguar qué texto utilicé para calcular el hash

aea23489ce3aa9b6406ebb28e0cda430

f (x) = 1 es irreversible. Las funciones hash no son irreversibles.

Esto es realmente requido para que cumplan su función de determinar si alguien posee una copia no corrupta de los datos hash. Esto trae susceptibilidad a ataques de fuerza bruta, que son bastante poderosos en estos días, particularmente contra MD5.

También hay confusión aquí y en otros lugares entre las personas que tienen conocimiento matemático pero poco conocimiento de descifrado. Varios cifrados simplemente XOR los datos con la secuencia clave, por lo que podría decir que un texto cifrado corresponde a todos los textos simples de esa longitud porque podría haber utilizado cualquier secuencia clave.

Sin embargo, esto ignora que un texto claro razonable producido a partir de la contraseña semilla es mucho, mucho más probable que otro producido por la semilla Wsg5Nm ^ bkI4EgxUOhpAjTmTjO0F! VkWvysS6EEMsIJiTZcvsh @ WI $ IH $ TYqiWv % & amp; Ue & amp; nk55ak% BX% 9! NnG% 32ftud% YkBO $ U6o en la medida en que cualquiera que diga que la segunda es una posibilidad se reiría.

Del mismo modo, si está tratando de decidir entre las dos posibles contraseñas password y Wsg5Nm ^ bkI4EgxUO , no es tan difícil de hacer como lo harían algunos matemáticos has creído.

Me gustan todos los diversos argumentos. Es obvio que el valor real de los valores hash es simplemente proporcionar marcadores de posición ilegibles para las cadenas, como las contraseñas. No tiene un beneficio específico de seguridad mejorado. Asumiendo que un atacante obtuvo acceso a una tabla con contraseñas hash, él / ella puede:

Escriba una contraseña de su elección y coloque los resultados dentro de la tabla de contraseñas si tiene derechos de escritura / edición sobre la tabla.
Genere valores hash de contraseñas comunes y pruebe la existencia de valores hash similares en la tabla de contraseñas.

En este caso, las contraseñas débiles no pueden protegerse por el simple hecho de que están en hash.

Licenciado bajo: CC-BY-SA con atribución

No afiliado a StackOverflow