¿Por qué los valores hash MD5 no son reversibles?

Un concepto sobre el que siempre me he preguntado es el uso de funciones y valores hash criptográficos. 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 hacen que sea imposible volver a rastrear las cadenas resultantes?

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

Si elige un número aleatorio y lo divide por 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?

Si las funciones hash como MD5 fueran reversibles, ¡habría sido un hito en la historia de los algoritmos de compresión de datos! Es fácil ver que si MD5 fuera reversible, entonces los fragmentos arbitrarios de datos de tamaño arbitrario podrían representarse con tan solo 128 bits sin pérdida de información. Por lo tanto, habría podido reconstruir 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 de hash con el mismo valor) de una función hash criptográfica causada por la diferencia entre el tamaño de entrada grande (potencialmente infinito) y el tamaño de salida fijo no es el punto importante : en realidad, preferimos las funciones hash en las que esas colisiones ocurren lo menos 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 dará como resultado:

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 aplíquelo hex2binen su hash y lo tendrá). 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 es bastante corta (excepto probando todas las entradas posibles hasta que encontremos 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 determinado (resistencia a la preimagen)
• es difícil encontrar una cadena diferente que produzca el mismo hash que una cadena dada (segunda resistencia a la preimagen)
• es difícil encontrar un par de cadenas con el mismo hash (resistencia a colisiones)

Obviamente mi simple_hashfunción 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 resistente a la segunda preimagen y a las colisiones).

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 imposible), por lo que no debería usar MD5 para cualquier cosa crítica. Aún no hay un ataque de preimagen, pero los ataques mejorarán.

Para responder a la pregunta real:

¿Qué tienen estas funciones que hacen que sea imposible volver a rastrear las cadenas resultantes?

Lo que MD5 (y otras funciones hash basadas en la construcción Merkle-Damgard) hacen efectivamente es aplicar un algoritmo de cifrado con el mensaje como clave y algún valor fijo como "texto sin formato", 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 utiliza para cifrar la salida del bloque anterior, XORed con su entrada para evitar cálculos inversos).

Los algoritmos de encriptación modernos (incluidos los que se usan en las funciones hash) están diseñados para dificultar la recuperación de la clave, incluso con texto plano y cifrado (o incluso cuando el adversario elige uno de ellos). Por lo general, lo hacen 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 en el interior si conoce la clave completa y la entrada o la 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).

La respuesta de Cody Brocious es la correcta. Estrictamente hablando, no puede "invertir" una función hash porque muchas cadenas están asignadas al mismo hash. Tenga en cuenta, sin embargo, que encontrar una cadena que se asigne a un hash dado o encontrar dos cadenas que se asignen al mismo hash (es decir, una colisión ) sería un gran avance para un criptoanalista. La gran dificultad de estos dos problemas es la razón por la que 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.

P.ej,

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

(Obviamente, eso no es un cifrado MD5 real)

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

Una buena forma 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 la cambia de tamaño a solo 32x32. Lo que tiene sigue siendo una representación de la imagen original, pero es mucho más pequeña y efectivamente ha "tirado a la basura" 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 de nuevo a 5000x5000, todo lo que obtendría es un desastre borroso. Sin embargo, debido a que una imagen de 32x32 no es tan grande, sería teóricamente concebible que otra imagen pudiera reducirse para producir exactamente los mismos píxeles.

Eso es solo una analogía, pero ayuda a comprender qué está haciendo un hash.

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

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

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

A veces se utilizan estos criterios:

1. Resistencia a la 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.
2. Resistencia a la segunda preimagen: para una determinada función y entrada de hash, debería ser difícil encontrar una segunda entrada diferente con el mismo hash.
3. Resistencia a colisiones: para una función de has dada, 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 mero 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 tiene fallas: cómo romper MD5 y otras funciones hash .

Pero aquí es donde entran en juego las tablas arcoíris. Básicamente, es solo una gran cantidad de valores hash por separado y luego el resultado se guarda en el disco. Entonces, el bit de inversión es "solo" para realizar 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" para crear 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 los flujos de datos de longitud variable se conviertan en un fragmento de datos de longitud fija, por lo que un solo hash es compartido por muchos flujos de datos de entrada.

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

La mejor manera de entender qué significan todas las respuestas más votadas es intentar revertir el algoritmo MD5. Recuerdo que intenté revertir el algoritmo MD5crypt hace algunos años, no para recuperar el mensaje original porque es claramente imposible, sino solo para generar un mensaje que produzca el mismo hash que el hash original. Esto, al menos en teoría, me proporcionaría una forma de iniciar sesión en un dispositivo Linux que almacenaba el 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 mal no recuerdo, el uso de salen el mensaje inicial me mató. Tuve que producir no solo un mensaje inicial válido, sino un mensaje inicial válido con sal, lo que nunca pude hacer. Pero el conocimiento que obtuve de este experimento fue bueno.

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

regd su pregunta: es hash unidireccional. La entrada (independientemente de la longitud) generará una salida de tamaño fijo (se rellenará según el algoritmo (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. revisé este artículo recientemente, http://www.win.tue.nl/hashclash/Nostradamus/

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

Hoy en día, los hashes MD5 o cualquier otro hashes se calculan previamente para todas las cadenas posibles y se almacenan para facilitar el acceso. Aunque en teoría MD5 no es reversible, utilizando estas bases de datos puede averiguar 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 usé para calcular el hash

aea23489ce3aa9b6406ebb28e0cda430

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

En realidad, esto es necesario para que cumplan con su función de determinar si alguien posee una copia no corrupta de los datos hash. Esto genera susceptibilidad a los 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 conocimientos matemáticos pero pocos conocimientos de descifrado. Varios cifrados simplemente XOR los datos con el flujo de claves, por lo que podría decir que un texto cifrado corresponde a todos los textos sin formato de esa longitud porque podría haber utilizado cualquier flujo de claves.

Sin embargo, esto ignora que un texto plano razonable producido a partir de la semilla passwordes mucho, mucho más probable que otro producido por la semilla, Wsg5Nm^bkI4EgxUOhpAjTmTjO0F!VkWvysS6EEMsIJiTZcvsh@WI$IH$TYqiWvK!%&Ue&nk55ak%BX%9!NnG%32ftud%YkBO$U6ohasta el punto de que cualquiera que afirme que el segundo es una posibilidad se reiría de él.

De la misma manera, si está tratando de decidir entre las dos posibles contraseñas passwordy Wsg5Nm^bkI4EgxUO, no es tan difícil de hacer como algunos matemáticos quieren que crea.

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 los humanos para cadenas como contraseñas. No tiene ningún beneficio de seguridad mejorado específico. Suponiendo que un atacante obtuvo acceso a una tabla con contraseñas hash, él / ella puede:

• Aplique una contraseña de su propia elección y coloque los resultados dentro de la tabla de contraseñas si tiene derechos de escritura / edición en 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 mero hecho de que estén codificadas.