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

91

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?

barfoon
fuente
54
Un ejemplo simple de valor no reversible, por ejemplo, es módulo. Por ejemplo, 10% 3 = 1, pero no puede revertir el 1 a 10, ya que también podría ser 4
Gab Royer
57
Si pudiera reconstruir los datos, tendría el algoritmo de compresión sin pérdidas más eficiente de todos los tiempos :)
Dan Diplo

Respuestas:

204

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?

Cody Brocious
fuente
4
Es decir, ni número -> resto ni cadena -> md5 son "funciones inyectivas".
Federico A. Ramponi
Federico, seguramente quieres decir que tampoco las funciones biyectivas. Ambos son inyectivos.
Mihai Limbășan
10
moocha: Injetivo significa 1 a 1. El MD5 ciertamente no es 1 a 1, ya que el dominio es mayor que el rango. Otro punto que vale la pena señalar es que, dada una suma de comprobación MD5, es muy difícil encontrar ni siquiera una cadena que tenga un hash. Valdría la pena agregar a la respuesta para aclarar.
biozinc
4
Es imposible tener una función hash que genere valores únicos. Está mapeando un número infinito de valores en un número finito de valores, lo que garantiza colisiones.
Cody Brocious
4
Sugeriría que su respuesta no aborde el punto clave. Como mencionó biozinc, lo importante para un hash de contraseña seguro es que no puede encontrar ninguna entrada que cree la salida, no es que no pueda encontrar la entrada original. En esa nota, MD5 no es necesariamente tan seguro como podría ser ( en.wikipedia.org/wiki/MD5#Collision_vulnerabilities ).
Mike Pelley
53

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.

Autodidacta
fuente
9
Piense en lo rápido que sería descargar distribuciones de Linux si pudiera obtener el md5 en su lugar :)
Colin Pickard
15
@Colin Pickard: ya no descargaríamos distribuciones de Linux, las estaríamos escribiendo . :)
tzot
29

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).

Paŭlo Ebermann
fuente
4
Sí, sé que esta es una respuesta bastante tardía, pero la respuesta aceptada no debe dejarse de esta manera.
Paŭlo Ebermann
Creo que sus críticas tienen algún mérito, pero no ha respondido a la pregunta real "¿Qué tienen estas funciones que hacen que las cadenas resultantes sean imposibles de rastrear?" Su respuesta se centra en las cualidades que debería tener un hash criptográfico, pero no tiene ninguna explicación de cómo se implementan en md5. Puede indicar el algoritmo exacto para calcular las sumas MD5 aquí para mostrar cómo no es reversible, pero las otras respuestas brindan una explicación más simple sin entrar en los detalles.
Autodidacta
(cont ...) 2. Estas explicaciones usan "Math" para mostrar un problema fundamental debido al cual tales operaciones pierden información y se vuelven irreversibles.
Autodidacta
1
@SandeepDatta Agregué algunos párrafos sobre esto.
Paŭlo Ebermann
1
Si bien otras respuestas en este hilo son más técnicamente correctas, esta respuesta es la más útil. La función no inyectiva f (x) = 1 es irreversible pero poco interesante. La utilidad del hash radica en la resistencia a la preimagen, donde es difícil encontrar una entrada que produzca una salida específica.
Justin J Stark
18

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.

Federico A. Ramponi
fuente
12

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.

Trevel
fuente
8

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.

nbevans
fuente
3
Si bien el cambio de tamaño de la imagen es un proceso con pérdidas, aún es bastante fácil producir una imagen en el tamaño original de 5000 × 5000 que (al aplicar la función de reducción nuevamente) se reducirá a la misma imagen de 32 × 32. Encontrar tal preimagen debería ser difícil para una buena función hash.
Paŭlo Ebermann
4

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í.

Gamic
fuente
1
Hay 365 valores de cumpleaños posibles, que se encuentran entre 2 ^ 8 y 2 ^ 9. Un hash de 128 bits tiene 2 ^ 128 valores posibles, 2 ^ 120 veces más. Sí, las colisiones son más probables de lo que imagina, pero aún son astronómicamente improbables.
Tim Keating
Necesitará aproximadamente 2 ^ 64 valores diferentes para tener una buena probabilidad de una colisión de hash. Todavía bastante.
Paŭlo Ebermann
4

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 .

Geoglifo
fuente
2

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.

Martinlund
fuente
Ahh si. Disfruté leyendo la publicación de Jeff sobre Hash Tables ( codinghorror.com/blog/archives/000949.html ), y este hilo ha ayudado a comprender el concepto.
barfoon
1

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.

Tim Matthews
fuente
1

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.

Vinicius
fuente
Si pudiera generar una entrada que produjera el valor hash MD5 dado de una manera razonablemente eficiente, eso sería un gran problema para la comunidad criptográfica y debería publicarse. Eso es completamente independiente de si un insumo en particular fue salado.
Dave L.
0

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).

FL4SOF
fuente
0

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
Babar
fuente
Ah, sí, el hash de una palabra común de siete letras. Ahora úsala para descifrar esta letra de la canción de 11 palabras con espacios en blanco y puntuación: 9f2c08d4e6158bd4854b15be50c8daa8. Nos vemos en varios milenios.
Tim Keating
6fba2bbab8a8366309bf67c7df12c622? Sugerencia: ¡podría ser la versión OEM de una versión específica de Mac OS X!
Scherand
@Tim Keating, @scherand: Solo señalando la debilidad de los algoritmos hash, debido a que el hash de una cadena es siempre el mismo, no necesariamente necesitamos descifrar el algoritmo para descubrir la cadena real.
Babar
2
Pero eso no es lo que dijiste. Dijiste que los hash están "precalculados para todas las cadenas posibles y almacenados para facilitar el acceso", lo cual es evidentemente falso (el conjunto de "todas las cadenas posibles" es infinito ... e incluso el conjunto de "todas las cadenas plausibles" es realmente, muy grande ). En mi humilde opinión, esto tergiversa lo fácil que es hacer un ataque de diccionario contra una frase de contraseña razonable.
Tim Keating
0

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.

Olathe
fuente
¿De dónde obtiene su mayoría de cifrados simplemente XOR los datos con el conocimiento del flujo de claves ? Esto es cierto para los cifrados de flujo, pero también hay cifrados de bloque y no funcionan de esta manera.
Paŭlo Ebermann
-5

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.

webi
fuente
El valor real de los "valores hash" no es proporcionar marcadores de posición ilegibles para los humanos. Si 'password1' se ha convertido en 'newval', ¿eso todavía no oculta el valor de una manera similar, aunque el hash es legible y significativo? Además, las contraseñas son un MAL ejemplo, porque NUNCA deben tener hash. Suponiendo que el atacante tuviera acceso de escritura a dicha base de datos, definitivamente es una posibilidad. Sin embargo, parece que simplemente está descartando el uso adecuado de tales funciones hash, un ejemplo se describe en las muchas respuestas anteriores: integridad del mensaje. En realidad, es la razón por la que estoy en este hilo hoy.
Shane