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

sha256 algorithm (16)

Ahora bien, los hashes 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 al usar 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 usé para calcular el hash

aea23489ce3aa9b6406ebb28e0cda430

Un concepto 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 e invertir el valor hash?

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

Científicos chinos han encontrado una forma llamada "colisiones de prefijos elegidos" 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 cantidad de archivos de entrada posibles es mayor que la cantidad de salidas de 128 bits, es imposible asignar de manera única 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 para la eficiencia). Por lo tanto, cambiar el documento original significa que el hash original no coincide con el documento modificado.

Estos criterios a veces se usan:

Resistencia de preimagen: para una función hash dada y 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 a colisiones: para una función dada tiene que ser difícil encontrar dos entradas diferentes con el mismo algoritmo 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 forjar documentos reemplazando el original por uno que coincida con hash. (Incluso si el reemplazo es un galimatías, el simple reemplazo del original puede causar interrupción).

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 .

Como ya se ha dicho, MD5 se diseñó para flujos de datos de longitud variable a un trozo de datos de longitud fija, por lo que muchos flujos de datos de entrada comparten un hash único.

Sin embargo, si alguna vez tuvo que averiguar los datos originales de la suma de comprobació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 google (o el buscador que prefiera) el hash para la respuesta que para la fuerza bruta. He descubierto con éxito algunas contraseñas con este método.

Contrariamente a lo que enfatizan las respuestas más votadas aquí, la no-inyectividad (es decir, que hay varias cadenas hash al mismo valor) de una función hash criptográfica causada por la diferencia entre tamaño de entrada grande (potencialmente infinito) y tamaño de salida fijo no es el punto importante : en realidad, preferimos las funciones hash donde esas colisiones ocurren tan pocas veces 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 muy 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(".com");

Esto dará como resultado:

737461636b6f766572666c6f772e636f6d

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

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

Las suposiciones importantes para una función de hash criptográfica son:

es difícil encontrar una cuerda que produzca un hash dado (resistencia de preimagen)
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, incluso es demostrable como resistente a segunda imagen y resistente a 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 es mucho trabajo), por lo que no debe utilizar MD5 para cualquier cosa crítica. 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 las cadenas resultantes sean imposibles de retrazar?

Lo que 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 el "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 encriptar la salida del bloque anterior, XORed con su entrada para evitar cálculos inversos).

Los algoritmos de encriptación modernos (incluidos los utilizados en las funciones hash) se crean de forma tal que dificultan la recuperación de la clave, incluso con texto simple y texto cifrado (o incluso cuando el adversario elige uno de ellos). Lo hacen generalmente haciendo muchas operaciones de mezcla de bits de forma tal que cada bit de salida está determinado por cada bit de clave (varias veces) y también por cada bit de entrada. De esta forma, solo podrás volver a recorrer fácilmente lo que sucede dentro si conoces la clave completa y la entrada o salida.

Para las funciones hash similares a MD5 y un ataque de preimagen (con una cadena hash de bloque único, 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).

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

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

La mejor forma de entender lo que significaron todas las respuestas más votadas es tratar de revertir el algoritmo MD5. Recuerdo que traté de revertir el algoritmo MD5crypt hace algunos años, no para recuperar el mensaje original porque es claramente imposible, sino simplemente para generar un mensaje que produciría 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 almacenaba el usuario: contraseña en el archivo / etc / passwd usando el mensaje generado (contraseña) en lugar de usar el original. Como 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 sal en el mensaje inicial me mató. Tuve que producir no solo un mensaje inicial válido, sino un mensaje inicial válido y salado, que nunca pude hacer. Pero el conocimiento que obtuve de este experimento fue agradable.

La respuesta de Cody Brocious es la correcta. Estrictamente hablando, no se puede "invertir" una función hash porque muchas cadenas se asignan al mismo hash. Tenga en cuenta, sin embargo, 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ía grandes avances para un criptoanalista. La gran dificultad de estos dos problemas es la razón por la cual las buenas funciones hash son útiles en la 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 encriptación 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 altamente improbable, pero aún es posible.

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

Haga clic en una contraseña de su elección y coloque los resultados dentro de la tabla de contraseña 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 simple hecho de que son hash.

Pero aquí es donde las tablas de arco iris entran en juego. Básicamente, se trata de una gran cantidad de valores con hashes separados y luego el resultado se guarda en el disco. Luego, el bit de inversión es "solo" para 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.

Si las funciones hash como MD5 fueran reversibles, entonces habría sido un evento decisivo en la historia de los algoritmos de compresión de datos. Es fácil ver que si MD5 era reversible, fragmentos arbitrarios de datos de tamaño arbitrario podrían representarse con 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.

Una buena forma de pensar en un algoritmo de hash es pensar en cambiar el tamaño de una imagen en Photoshop ... digamos que tienes una imagen de 5000x5000 píxeles y luego la cambias de tamaño a solo 32x32. Lo que tienes es todavía una representación de la imagen original, pero es mucho más pequeña y ha "tirado" efectivamente ciertas partes de los datos de la imagen para que quepa en el tamaño más pequeño. Entonces, si tuviera que cambiar el tamaño de esa imagen de 32x32 hasta 5000x5000, todo lo que obtendrá 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 podría reducirse para producir exactamente los mismos píxeles.

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

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

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

Esto es realmente necesario para que cumplan su función de determinar si alguien posee una copia no corrupta de los datos hash. Esto trae 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 otras partes entre las personas que tienen conocimiento matemático pero poco conocimiento de cifrado. Varios cifrados simplemente XOR los datos con el flujo de claves, por lo que podría decirse que un texto cifrado corresponde a todos los textos planos de esa longitud, ya que podría haber utilizado cualquier flujo de claves.

Sin embargo, esto ignora que un texto plano razonable producido a partir de la password Wsg5Nm^bkI4EgxUOhpAjTmTjO0F!VkWvysS6EEMsIJiTZcvsh@WI$IH$TYqiWvK!%&Ue&nk55ak%BX%9!NnG%32ftud%YkBO$U6o es mucho, mucho más probable que otro producido por la semilla Wsg5Nm^bkI4EgxUOhpAjTmTjO0F!VkWvysS6EEMsIJiTZcvsh@WI$IH$TYqiWvK!%&Ue&nk55ak%BX%9!NnG%32ftud%YkBO$U6o en la medida en que se Wsg5Nm^bkI4EgxUOhpAjTmTjO0F!VkWvysS6EEMsIJiTZcvsh@WI$IH$TYqiWvK!%&Ue&nk55ak%BX%9!NnG%32ftud%YkBO$U6o de cualquiera que Wsg5Nm^bkI4EgxUOhpAjTmTjO0F!VkWvysS6EEMsIJiTZcvsh@WI$IH$TYqiWvK!%&Ue&nk55ak%BX%9!NnG%32ftud%YkBO$U6o que el segundo era una posibilidad.

De la misma manera, si está tratando de decidir entre las dos contraseñas de password potenciales y Wsg5Nm^bkI4EgxUO , no es tan difícil de hacer como algunos matemáticos lo harán creer.

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

regd su pregunta: es de una manera hash. la entrada (independientemente de la longitud) generará una salida de tamaño fijo. (se rellenará en función de algo (límite de 512 bits para MD5)). La información se comprime (pierde) y prácticamente no es posible generar a partir de transformadas inversas.

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

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