¿Cuáles son los puntos importantes acerca de las funciones hash criptográficas?

Question

Estaba leyendo this question en valores de hash MD5 y la respuesta aceptada me confunde. Una de las propiedades principales, según tengo entendido, de una función hash criptopráfica es que no es factible encontrar dos mensajes diferentes (entradas) con el mismo valor hash.

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

Además, lo que me deja algo perplejo es el hecho de que los algoritmos son públicos, pero los valores hash son aún 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 descartaron?

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

EDIT:

OK, vamos a ver si lo he entendido bien:

1. Es muy, muy difícil inferir la entrada a partir del hash porque hay un infinito cantidad de cadenas de entrada que generarán la misma salida (propiedad irreversible).
2. Sin embargo, buscando incluso una única instancia de múltiples cadenas de entrada que generan la misma salida también es muy, muy difícil (propiedad resistente a colisiones).

Answer 1

Puede estar confundido, porque la respuesta a the question you citees confusa. Uno de los requisitos para una función de cifrado hash es que debe ser resistente a las imágenes. Es decir, si conoce MD5 (x) pero no el mensaje x, entonces es difícil encontrar cualquier x '(ya sea x o diferente de x) tal que MD5 (x') = MD5 (x).

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

Al realizar la criptografía, generalmente necesita funciones que sean resistentes a las imágenes (y otras propiedades como la resistencia a la colisión), no solo algo que no sea reversible.

Answer 2

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 la convertirá en un espacio de tamaño 2^128 - grande, pero no tan grande como aleph-0.)

Además de otras características, buenos hash llenan el espacio de destino de forma homogénea. Los hash malos llenan el espacio de forma agrupada y crean el mismo hash para muchas entradas comunes.

Imagine la idiota función hash sum(), que simplemente suma todos los dígitos del número de entrada: logra mapear, pero hay un montón de colisiones (entradas con el mismo resultado, como 3 y 12 y 21) en el extremo inferior 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 descifrar, etc.

Así que un buen hash que hace que incluso el uso del espacio de destino dificulte encontrar dos entradas con el mismo resultado, solo por las probabilidades: si MD5 fuera perfecto, las probabilidades de que dos entradas tengan la misma salida serían 2^-128. Es una probabilidad bastante decente: lo mejor que puede hacer sin recurrir a un mayor espacio de salida. (En verdad MD5 no es perfecto, que es una de las cosas que lo hace vulnerable.)

Pero seguirá siendo cierto que una gran cantidad de entradas se correlacionará con cualquier hash dado, porque el espacio de entrada es ' infinito ', y dividir el infinito por 2^128 todavía le da infinito.

2: Sí, los valores hash siempre causan pérdida de datos, excepto en el caso en que el espacio de salida sea igual o mayor que el espacio de entrada, y en ese caso probablemente no necesite hash.

3: Para entradas más pequeñas, la mejor práctica es salar la entrada. En realidad, esa es una buena práctica para cualquier hash criptográfico, porque de lo contrario un atacante puede alimentar tus entradas específicas y tratar de averiguar qué hash estás usando. 'Salt' es solo un conjunto de información adicional que usted agrega (o antepone) a su entrada; entonces hash el resultado.

edición: En criptografía, también es importante que la función hash es resistente a ataques imagen inversa, de manera intuitiva, que es difícil de adivinar la entrada para una salida dada saber siquiera muchos otros pares de entrada/salida. La función "suma" probablemente podría adivinarse con bastante facilidad (pero dado que destruye datos, puede que no sea fácil revertirla).

Answer 3

Sin embargo, la respuesta de consenso a la pregunta "¿por qué no son reversibles los valores de hash MD5?" es porque "un número infinito de cadenas de entrada generará el mismo resultado".

Esto es válido 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, es teóricamente posible revertir una función hash criptográfica, pero no debería poder computarizada. Es decir. su computación funcionaría demasiado tiempo para ser útil.

La razón de esta falta de viabilidad es que la entrada es tan a fondo "mezclados" en el valor hash que se hace imposible de desenredar con menos esfuerzo que el ataque de fuerza bruta para calcular el valor hash para todas las entradas

Answer 4

"¿por qué no son reversibles los valores de hash MD5?" 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 hash criptográficas son resistentes a colisiones, eso significa que también es difícil encontrar otro valor de entrada que coincida con la misma salida (si su función hash fue mod 2: 134 mod 2 = 0; ahora no puede recuperar la 134 el resultado, pero aún podemos encontrar el número 2 con el mismo valor de salida (134 y 2 chocan)).

Cuando la entrada es más pequeña que el tamaño del bloque, padding se usa para ajustarlo al tamaño del bloque.

Answer 5

Estas son las propiedades de las funciones hash en general.

Sin embargo, una palabra de cautela, MD5 ya no debería usarse debido a las vulnerabilidades que se han encontrado 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 los simples hash aunque hay algunos ataques que harían más débil frente bien financiados entidades (gobiernos, las grandes corporaciones)

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

Answer 6

Advertencia: Respuesta larga

creo que todas estas respuestas están perdiendo una propiedad muy importante de las funciones hash criptográficas: No sólo es imposible calcular el mensaje original que fue hash para obtener un hash dado, es imposible calcular cualquier mensaje que haría hash a un valor hash dado. Esto se llama resistencia a la preimagen.

(Por "imposible" - me refiero a que nadie sabe cómo hacerlo en menos tiempo del que se necesita para adivinar cada mensaje sea posible hasta que adivinar la que fue ordenada en su hash.)

(A pesar La creencia popular en la inseguridad de MD5, MD5 todavía es preimagen resistente. Cualquier persona que no me crea es libre de darme cualquier cosa que tenga valores hash a 2aaddf751bff2121cc51dc709e866f19. Lo que MD5 no tiene es collision resistance, que es algo completamente diferente).

Ahora, si la única razón por la que no puede "trabajar al revés" en una función hash criptográfica fue porque la función hash descarta datos para crear el hash, entonces no garantizaría la resistencia de la imagen: todavía puede "trabajar hacia atrás", e inserte datos aleatorios donde la función de hash descarte los datos, y aunque no aparezca el mensaje original, usted tendría todavía se le ocurre un mensaje que hash al valor de 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 las imágenes?)

La respuesta es que las funciones hash criptográficas simulan sistemas caóticos. Toman tu mensaje, lo dividen en bloques, mezclan esos bloques, hacen que algunos de los bloques interactúen entre ellos, mezclan esos bloques y lo repiten muchas veces (bueno, una función de hash criptográfica hace eso, otros tienen su métodos propios). Dado que 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, seguro, puede encontrar los valores de los bloques C, D, E que produciría los bloques A y B en su valor de 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! Debe haber adivinado los valores incorrectos para C, D y E.

Si bien no todas las funciones hash criptográficas son exactamente como se describió anteriormente con la interacción de bloques, tienen la misma idea: que si intenta "trabajar hacia atrás", Va a terminar con un montón de callejones sin salida, y el tiempo que le toma probar suficientes valores para generar una preimagen es del orden de cientos o millones de años (dependiendo de la función de hash), no mucho mejor que el tiempo que tomaría simplemente probar los mensajes hasta que encuentres uno que funcione.