Pregunta sobre hash, cryptography, hash-function – ¿Cuáles son los puntos importantes sobre las funciones hash criptográficas?

11

estaba leyendoesta pregunta en los valores de hash MD5 y la respuesta aceptada me confunde. Una de las propiedades principales, según entiendo, de una función criptográfica de hash es que no es factible encontrar dos mensajes diferentes (entradas) con el mismo valor de hash.

Sin embargo, la respuesta de consenso a la pregunta¿Por qué no son reversibles los valores de hash MD5? esPorque un número infinito de cadenas de entrada generará la misma salida. Esto me parece completamente contradictorio.

Además, lo que me deja perplejo es el hecho de que los algoritmos son públicos, pero los valores de hash son irreversibles. ¿Esto se debe a que siempre hay pérdida de datos en una función hash, por lo que no hay forma de saber qué datos se desecharon?

¿Qué sucede cuando el tamaño de los datos de entrada es más pequeño que el tamaño de los datos de salida fijos (por ejemplo, hashing de una contraseña "abc")?

EDITAR:

Bien, déjame ver si tengo esto en claro:

Es realmente muy difícil inferir la entrada del hashporque hay una cantidad infinita de cadenas de entrada que generarán la misma salida (propiedad irreversible).Sin embargo,hallazgo incluso una sola instancia de múltiples cadenas de entrada que generan la misma salida también es muy difícil (propiedad resistente a la colisión).
Sí, el "consenso" en las respuestas a lapregunta que has vinculado esta totalmente equivocado Acabo de añadir otra respuesta corrigiendo esto. Paŭlo Ebermann
No vi tu edición Creo que lo has resumido en esas dos balas. Alex Feinman
El motivo de la propiedad de reversibilidad no es la "cantidad infinita de cadenas de entrada", también debería ser el caso cuando se limita la entrada a algo pequeño (como alrededor del tamaño de salida). Paŭlo Ebermann

Tu respuesta

6   la respuesta
18

Advertencia: respuesta larga

Creo que a todas estas respuestas les falta una propiedad muy importante de las funciones criptográficas de hash: no solo es imposible calcular el mensaje original que se utilizó para obtener un hash determinado, sino que también es imposible de calcular.alguna mensaje que haría un hash a un valor de hash dado. Se llamaresistencia preimagen.

(Por "imposible": quiero decir que nadie sabe cómo hacerlo en menos tiempo del que se necesita para adivinar todos los mensajes posibles hasta que uno adivine el que estaba en su hash).

(A pesar de la creencia popular en la inseguridad del MD5, el MD5 aún es resistente a la preimagen. Cualquiera que no me crea es libre de darme cualquier cosa que me permita2aaddf751bff2121cc51dc709e866f19. Lo que no tiene MD5 esresistencia a la colisión, que es algo completamente distinto.

Ahora, si la única razón por la que no puede "trabajar hacia atrás" en una función criptográfica de hash fue porque la función de hash descarta los datos para crear el hash, entonces no garantizaría la resistencia de preimagen: todavía puede "trabajar hacia atrás", y simplemente insertar datos aleatorios donde sea que la función hash descarta datos, y si bien no presentaría el mensaje original, aún aparecería un mensaje que contiene el valor hash deseado. Pero no puedes.

Entonces la pregunta es: ¿por qué no? (O, en otras palabras, ¿cómo hace que una función sea resistente a la preimagen?)

La respuesta es que las funciones criptográficas de hash simulan sistemas caóticos. Toman su mensaje, lo dividen en bloques, mezclan esos bloques alrededor, hacen que algunos de ellos interactúen entre sí, mezclan esos bloques alrededor y lo repiten muchas veces (bueno, una función criptográfica de hash hace eso; otros tienen su métodos propios). Como los bloques interactúan entre sí, el bloque C no solo tiene que interactuar con el bloque D para producir el bloque A, sino que tiene que interactuar con el bloque E para producir el bloque B. Ahora, claro, puedes encontrar los valores de los bloques C, D, E que produciría los bloques A y B en su valor hash, pero a medida que retrocede, de repente necesita un bloque F que interactúa con C para hacer D, y con E para hacer B, y ningún bloque de ese tipo puede hacer ambas cosas en ¡al mismo tiempo! Debes haber adivinado valores incorrectos para C, D y E.

Si bien no todas las funciones hash criptográficas son exactamente como se describieron anteriormente con la interacción de bloques, tienen la misma idea: que si intentas "trabajar hacia atrás", terminarás con un montón de callejones sin salida, y en el momento Los intentos para que pruebe los valores suficientes para generar una preimagen es del orden de cientos a millones de años (dependiendo de la función hash), no mucho mejor que el tiempo que tardaría en probar los mensajes hasta que encuentre uno que funcione.

12

1: El propósito principal de un hash es asignar un espacio muy, muy grande a un espacio más pequeño pero aún muy grande (por ejemplo, MD5, que tomará 'cualquier cosa' y lo convertirá en un espacio de tamaño 2 ^ 128 - grande , pero no tan grande como aleph-0.

Además de otras características,bueno Los hashes llenan el espacio de destino de manera homogénea. Los hashes incorrectos llenan el espacio de manera agrupada, y crean el mismo hash para muchas entradas comunes.

Imagine la función de hash idiota sum (, que solo suma todos los dígitos del número de entrada: logra mapear hacia abajo, pero hay un montón de colisiones (entradas con la misma salida, como 3 y 12 y 21 en el nivel bajo el final del espacio de salida y el extremo superior del espacio está casi vacío. Como resultado hace un uso muy pobre del espacio, es fácil de romper, etc.

Por lo tanto, un buen hash que haga un uso uniforme del espacio de destino dificultará la búsqueda de dos entradas con la misma salida, simplemente por las probabilidades: si MD5 fuera perfecto, las probabilidades de que dos entradas tuvieran la misma salida serían 2 ^ - 128. Estas son probabilidades bastante decentes: lo mejor que puede hacer sin tener que recurrir a un espacio de salida más grande. (En verdad, el MD5 no es perfecto, lo cual es una de las cosas que lo hace vulnerable.

Pero aún será cierto que una gran cantidad de entradas se asignarán a cualquier hash dado, porque el espacio de entrada es 'infinito', y dividir el infinito por 2 ^ 128 aún le da infinito.

2: Sí, los hashes siempre causan pérdida de datos, excepto en el caso de que el espacio de salida sea igual o mayor que el espacio de entrada, ¡y en ese caso probablemente no haya necesidad de hash!

3: Para entradas más pequeñas, la mejor práctica es agregar sal a la entrada. En realidad, esa es una buena práctica para cualquier hash criptográfico, porque de lo contrario, un atacante puede proporcionarle entradas específicas e intentar averiguar qué hash está utilizando. 'Salt' es solo un conjunto de información adicional que usted agrega (o antepone a sus comentarios; entonces hash el resultado.

editar: En la criptografía, también es importante que la función hash sea resistente a los ataques de preimagen, intuitivamente, que es difícil de adivinar la entrada para una salida dada, incluso al conocer muchos otros pares de entrada / salida. La función de "suma" probablemente podría adivinarse con bastante facilidad (pero dado que destruye los datos puede que no sea fácil revertirlos.

@ Paŭlo Ebermann, si tiene alguna sugerencia que sugerir, con mucho gusto los incorporaré. Sin embargo, es difícil ceder los votos de las respuestas a las preguntas anteriores, por lo que es posible que no tenga suerte en cuanto a cambiar la otra pregunta. Alex Feinman
Tu hash malo es como mi hash idiota: tiene una homogeneidad pobre y una estrategia de colisión terrible. Creo que lo editaré para indicar que las características que menciono son necesarias pero no suficientes para una función hash criptográficamente fuerte, ya que se explican algunos puntos que la respuesta de Zarel pasa por alto. Alex Feinman
-1 Se perdió el punto de que debería ser computacionalmente difícil revertir la función hash. Una función lineal puede distribuir los valores de hash muy bien y aún no ser adecuada para la criptografía. starblue
Lo siento, no quise dar a entender que la función distribuye linealmente la función, solo que la distribución de números debe ser suave en la gran escala. Alex Feinman
1

¿por qué los valores de hash MD5 no son reversibles?" es porque "un número infinito de cadenas de entrada generará la misma salida".

Esto es cierto para cualquier función hash, pero no es la esencia de una función hash criptográfica.

Para cadenas de entrada cortas, como contraseñas, teóricamente es posible revertir una función criptográfica hash, pero debería ser computacionalmente inviable. Es decir. su cálculo sería demasiado largo para ser útil.

El motivo de esta falta de viabilidad es que la entrada está tan "mezclada" en el valor hash que resulta imposible desenredarla con menos esfuerzo que el ataque de fuerza bruta de calcular el valor hash para todas las entradas

2

Sin embargo, una advertencia: el MD5 ya no debe utilizarse debido a las vulnerabilidades que se encuentran en él. Verifique la sección 'Vulnerabilidades' y los enlaces externos que detallan estos ataques.http://en.wikipedia.org/wiki/Md5 Puede realizar una colisión MD5 cambiando solo 128 bits en un mensaje.

SHA-1 es seguro para el hashing simple, aunque existen algunos ataques que lo debilitarían frente a entidades bien financiadas (gobiernos, grandes corporaciones)

SHA-256 es un punto de partida seguro contra la tecnología para las próximas dos décadas.

No necesariamente. La respuesta aceptada en la pregunta a la que me vinculé usa un ejemplo de función hash H (x) = x mod 2. Esta función hash exhibe la propiedad difícil de revertir pero no la propiedad de baja colisión. Rob Sobers
@ vg1890: propiedades decriptográfico funciones hash. H (x) = x mod 2 no es una función criptográfica hash. (Podría ser bueno para una tabla hash de 2 entradas, sin embargo.) Paŭlo Ebermann
6

la pregunta que usted cita es confuso. Uno de los requisitos para una función criptográfica hash es que debe ser resistente a la preimagen. Es decir, si conoce MD5 (x) pero no el mensaje x, entonces es difícil encontrar cualquier x '(igual x o diferente de x) tal que MD5 (x') = MD5 (x).

Ser resistente a la preimagen es una propiedad diferente a ser reversible. Una función es reversible si dada y = f (x) hay exactamente una x que se ajusta (ya sea fácil o no). Por ejemplo, defina f (x) = x mod 10. Entonces f no es reversible. Desde f (x) = 7 no puedes determinar si x fue 17, 27 o algo más. Pero f no es resistente a la preimagen, ya que los valores x 'tales que f (x) = 7 son fáciles de encontrar. x '= 17, 27, 12341237 etc todo el trabajo.

Cuando hace criptografía, normalmente necesita funciones que sean resistentes a la preimagen (y otras propiedades como la resistencia a la colisión), no solo algo que no sea reversible.

0

¿Por qué los valores de hash MD5 no son reversibles?; es porque ;un número infinito de cadenas de entrada> generará la misma salida;

esta es la razón por la que no es posible revertir la función hash (obtener la misma entrada). las funciones criptográficas de hash son resistentes a la colisión, lo que significa que también es difícil encontrar otro valor de entrada que se asigne a la misma salida (si su función de hash era mod 2: 134 mod 2 = 0; ahora no puede recuperar el 134 de la resultado, pero aún podemos encontrar el número 2 con el mismo valor de salida (134 y 2 en colisión).

Cuando la entrada es más pequeña que el tamaño de bloque,relleno Se utiliza para ajustarlo al tamaño del bloque.

Todavía no tiene sentido, es difícil encontrar dos entradas que produzcan la misma salida, pero el hecho de que muchas entradas tengan la misma salida es la razón por la que el hash es irreversible. ¿Cómo es que no es una contradicción? Rob Sobers
revertir la función es algo diferente a encontrar una colisión. Idealmente, la única forma de encontrar la colisión sería probando una entrada tras otra y comparando la salida de la función hash con el valor que desea revertir / encontrar colisión (eso es difícil). Pero incluso si hicieras eso, no sabrías si la colisión que encontraste fue la original o si acabas de encontrar una nueva cadena con el mismo valor de hash. cube

Preguntas relacionadas