¿Cómo funciona el hash?

Funciones hash criptográficas son objetos matemáticos que pueden describirse como «una gran mezcla y codificación de algunos bits «. Toman como entrada una secuencia de bits (posiblemente una muy larga) y ofrecen una salida de tamaño fijo. En términos generales, están tan enredados que, aunque no hay nada secreto sobre ellos (eso es solo un código determinista), nadie puede averiguar cómo «invertirlos» (encontrar una entrada coincidente para una salida dada) excepto por el método básico llamado «suerte»: pruebe entradas aleatorias hasta encontrar una coincidencia.

Cómo puede suceder, científicamente, que las funciones hash puedan existir es una buena pregunta .

El hash no es encriptación . No hay secreto ni clave en el hash.

Las funciones hash tienen muchos usos; uno de ellos es el «almacenamiento de contraseñas». Una función hash parece algo bueno para el almacenamiento de contraseñas. No queremos almacenar las contraseñas directamente (de lo contrario, un atacante echar un vistazo ocasional a nuestras bases de datos le daría demasiada información; consulte esta publicación de blog para ver una discusión) ; queremos almacenar tokens de verificación de contraseña : algo que permite la verificación de una contraseña (que presenta el usuario) pero no revela la contraseña en sí. Así que la idea es: almacenemos el hash de la contraseña. Cuando se va a verificar una contraseña, simplemente calculamos su hash y vemos si coincide con el valor almacenado. Pero adivinar la contraseña solo a partir del valor hash es difícil, ya que la función hash es resistente contra la «inversión» (ver más arriba).

Dado que las contraseñas son un tipo especial de datos (que son datos que los humanos pueden recordar), para una seguridad adecuada, necesitamos un «reforzado» función hash:

• Queremos una función hash muy lenta .
• No queremos una función hash, pero muchas funciones hash distintas, de modo que cada contraseña tendrá su propia función hash; se trata de disuadir ataques paralelos. Este proceso de convertir una sola función hash en muchas variantes se llama salazón .

Vea esta respuesta para un tratamiento completo del tema del hash de contraseñas.

Comentarios

• Lo siento, pero aunque su respuesta fue extremadamente completa y bien estructurada, encontré la otra respuesta se parece más a lo que estaba buscando.

El hash es una función de algunos cadena de bits (generalmente de longitud variable) a otra cadena de bits (generalmente más pequeña y de longitud fija).

El hash se usa en bases de datos para la recuperación de datos y en estructuras de datos en memoria llamadas tablas hash. Nos permite reducir datos arbitrarios, como una cadena de caracteres o un objeto complicado con muchos campos, a un número binario que luego se puede usar directamente como índice en una matriz dispersa para obtener los datos asociados (con algunos detalles para manejar hash colisiones).

Las funciones hash utilizadas de la manera anterior son «primos» de las funciones hash criptográficas. Están diseñados para diferentes requisitos. Deben ser rápidos de calcular y lograr una buena distribución.

En la informática segura, los hashes criptográficos se utilizan para digerir los datos en una pequeña cadena de bits representativa. Las funciones criptográficas tienen diferentes requisitos. Están diseñados para ser difíciles de revertir (para ser funciones de «trampilla» o «unidireccional»). No solo eso, sino que un requisito importante es que tiene que ser difícil encontrar, para un texto sin formato y un valor hash, otro texto sin formato que produzca el mismo hash.

El hash se puede utilizar no solo para contraseñas, sino como una suma de control para verificar la integridad de los datos y como parte de la implementación de firmas digitales. Para firmar digitalmente un documento grande, simplemente tenemos que aplicar un hash al documento para producir un «resumen» (un nombre que se usa para la salida de una función de hash, cuando se usa un hash de algo muy largo). Luego, este resumen se pasa por el sistema de cifrado de clave pública para producir una firma. Puede ver la debilidad allí: ¿qué pasa si un atacante logra producir un documento que tiene el mismo resumen? Entonces parece que la firma original producida sobre el documento genuino es en realidad una firma de un documento falsificado: se ha perpetrado efectivamente una falsificación de trasplante de firma.

El hash de contraseña permite que los sistemas no almacenen la versión de texto sin formato de una contraseña, pero les permite verificar si el usuario que intenta ingresar conoce esa contraseña. El hash no solo permite que los sistemas no almacenen las contraseñas de texto sin formato (que tendrían que protegerse con mucho cuidado), sino que también permite la posibilidad de que incluso si los hashes se exponen públicamente, las contraseñas siguen siendo seguras (de manera similar a cómo las claves públicas cripto los sistemas pueden revelar claves públicas). Aunque en la práctica, los hashes están protegidos del acceso público: por ejemplo, archivos /etc/shadow en sistemas similares a Unix, que complementan archivos /etc/passwd legibles en todo el mundo. .

La función hash es cualquier cosa menos aleatoria. Sin embargo, la aleatorización se emplea para frustrar a los atacantes que crean grandes diccionarios de contraseñas y hashes, que les permiten buscar un código hash y recuperar la contraseña correspondiente.

Para hacer hash en una contraseña de forma más segura, simplemente podemos agregar algunos bits aleatorios se llaman «sal». Diferentes sales agregadas a la misma contraseña, por supuesto, conducen a diferentes hashes (con suerte con pocas o ninguna colisión).

Si la sal aleatoria tiene, digamos, 32 bits de ancho, significa que, en teoría, una contraseña puede utilizar un hash de más de cuatro mil millones de formas diferentes, lo que hace que sea muy poco práctico tener un diccionario precalculado de todos los hash posibles. de una gran cantidad de contraseñas.

Por supuesto, cuando el usuario está siendo autenticado, ella no sabe nada sobre esta sal. Eso está bien porque la sal se almacena junto con el hash en el perfil del usuario (a menudo, combinado con el hash en una única cadena de bits compacta). Cuando se valida la entrada de la contraseña del usuario, la sal se agrega a cualquier contraseña ella entró, para que el hashing se realice con la sal correcta. Si la contraseña es correcta, el hash coincidirá, ya que la sal que se está utilizando también es la correcta, ya que se ha extraído del perfil del usuario.

Así es como se incorpora la aleatoriedad en el hash de la contraseña, sin dejar de permitir que funcione.

Lo que hace que los hash sean difíciles de descifrar es que se construyen a partir de funciones de «trampilla» o «unidireccional». En matemáticas, hay muchos ejemplos de tales cosas. Por ejemplo , la simple suma es una trampa. Si agregamos algunos números enteros para producir una suma, es imposible recuperar los números originales, conociendo solo la suma.

Los hash de contraseña no son contraseñas encriptadas. Si un atacante ha el hash y la sal de una contraseña, y sucede que adivina la contraseña, luego puede confirmar esto fácilmente, exactamente de la misma manera que lo hace el software de autenticación de inicio de sesión: ejecuta la contraseña más sal a través de la función de hash y ve que la hash emerge.

Comentarios

• Excelentes habilidades de escritura y una Entender la respuesta que sea completamente correcta, pero que aborde todos los puntos y mantenga un flujo natural que la haga mucho más completa. Eso ‘ no es una hazaña fácil, ¡muchas gracias por tu respuesta!
• muy informativo. Cubriste todos los aspectos.

Una de las claves del hash es que desecha información. No se puede revertir un hash porque el conocimiento necesario se ha ido. Aquí hay algunos ejemplos de funciones de hash que funcionan (pero que no tienen ningún valor). Si me da una contraseña, podría hacer algo como uno de los siguientes:

• Contar el número de vocales
• Tomar el código ASCII de cada letra y XOR todas juntas
• Tome la suma de comprobación CRC32 de la representación binaria de la contraseña (esta es en realidad un hash real, pero no criptográfico)

En cada uno de estos casos, no puedo revertir el proceso. En cambio, tengo que volver a ejecutar el proceso cuando me des la contraseña nuevamente más tarde para ver si el cálculo que realicé coincide.

Para ejemplo: si inicialmente me da la contraseña «mono», podría almacenar el número 3 (3 vocales). Luego, más tarde, cuando intento autenticar la contraseña «dragón», ejecuto la misma verificación nuevamente y obtengo 2, que no coincide con 3. Sé que me dio la contraseña incorrecta. Pero si me da la contraseña «melissa», asumiría incorrectamente que escribió la contraseña correcta. Esta es una colisión hash .

El conjunto de reglas que aplicas para obtener el número que representa una contraseña dada es su función hash . Estas se consideran funciones «unidireccionales» porque no debería poder revertirlas. Las funciones hash de alta calidad están diseñadas para limitar el número de posibles colisiones, de modo que no tenga que preocuparse por ese problema. Un paso más allá, funciones hash criptográficas están diseñadas para dificultar la creación de una cadena que pueda coincidir con una salida determinada ( y tal vez crear colisiones intencionalmente). También están diseñados para limitar la cantidad de información que puede obtener sobre una entrada determinada solo a partir de la salida hash.

Entonces, como resultado, la única forma de saber qué contraseña coincide con un hash criptográfico determinado es probar todas las posibilidades hasta que se encuentre con una que funcione. Otras contramedidas (salt, BPKDF2, etc.) hacen que este proceso de adivinación sea aún más difícil al hacer que la persona que adivina la contraseña pase por más aros en cada intento.

Tenga en cuenta que pasé por alto por completo cómo lo hace una función hash criptográfica es difícil encontrar una contraseña que funcione (incluso si no es la original). Esto se denomina « ataque de preimagen «. En el ejemplo trivial anterior, crear» melissa «como contraseña candidata que contiene 3 vocales es un ejemplo de tal ataque.

Las funciones de hash criptográficas suelen hacer esto ejecutando la entrada a través de varias» rondas «de un proceso dado, donde la salida de cada ronda se convierte en parte de la entrada a la siguiente.Para averiguar la entrada de la primera ronda, tendrá que averiguar la entrada de la segunda ronda, que a su vez requiere que averigüe la entrada de la tercera ronda, etc., lo que significa que cada conjetura de cada componente debe verificarse a través de un conjunto largo y complejo de cálculos. Thomas Pornin tiene una bonita explicación exhaustiva de cómo funciona esta resistencia; lectura bastante útil si realmente quieres entiéndalo.

1. Determine el valor constante de z que satisface esta ecuación: xy ^ 7 + yz ^ 5 + x ^ 3z = 0. ¿Necesitas ayuda? Vale, x = 32. ¿Aún no puedes resolverlo? Entonces no debería saber la respuesta en primer lugar.

   El valor de y, que lo reducirá a una ecuación de una sola variable, haciendo que resolverla para esa única variable sea trivial para cualquier estudiante de sexto grado (posiblemente necesita calculadora), es un secreto que solo he compartido con personas en las que confío. Sin él, z podría ser cualquier cosa; su valor depende de y, por lo que no puede resolverse satisfactoriamente sin una y constante conocida. Si no » No conozco su valor, es porque no he confiado en usted lo suficiente como para dárselo en privado.

   Este es el principio básico de la criptografía; la fórmula matemática u otro proceso determinista está bien -documentado, y una o más de las posibles variables de la fórmula también pueden ser conocidas públicamente, lo que permite que las dos partes acuerden una forma de configurar sus cifrados para que cada uno pueda descifrar lo que el otro cifra. Sin embargo, dos variables permanecer en secreto; si conoce uno, puede descubrir el otro. El que debe conocer es la clave, y el que puede descubrir con la clave es el mensaje.

   Para un hash, es un poco diferente. Un hash no requiere que se guarde un secreto para mantener otro. En cambio, los hash funcionan en función de una transformación matemática irreversible; para cualquier H (x) = y, no hay H ^-1 (y) = x excepto para probar H (x) para todas las x posibles hasta obtener y. Por lo general, esto se debe a que varios resultados intermedios de la ecuación son ambiguos; por ejemplo, calcular la raíz cuadrada de un número positivo produce técnicamente ambos un resultado positivo y negativo, ya que cualquier número podría multiplicarse por sí mismo para producir el resultado. La inversa de un módulo es igualmente ambigua; el número 1, producido por x mod 3, podría haber sido producido por cualquier x = 3k + 1. Estos tipos de transformaciones «unidireccionales» se combinan de tal manera que tratar de calcular la función hash inversa genera infinitas posibilidades; la forma más fácil (más fácil) de resolverlas es simplemente probar todas las entradas posibles hasta que coincida una salida. todavía lleva mucho tiempo.

2. Los hash no son aleatorios. Como dije anteriormente, los hash son el resultado de una operación matemática irreversible. Esa operación debe seguir siendo determinista; dada una entrada constante, la salida es constante independientemente de cuántas veces realice la operación. No hay ningún componente aleatorio.

   Lo que podría haberle confundido es en el término que simula un hash, que es un oráculo aleatorio . Imagínese una caja negra, dentro de la cual hay un hombrecito con memoria fotográfica y algún método místico de generar números perfectamente aleatorios. Escribe algo en una hoja de papel y lo empuja a través de una ranura donde el hombre lo obtiene. Lo lee y sucede una de dos cosas. O no lo ha leído antes, en cuyo caso generará un nuevo número aleatorio y se lo dará, guardando tanto su mensaje como el número en su memoria. O, ha leído exactamente este mensaje antes, en cuyo caso recuerda el número que generó la primera vez que lo leyó y le da ese número. El generador de números aleatorios nunca generará un número que ya ha generado, tiene una magnitud posible infinita, y el hombrecito la memoria es ilimitada e infalible. Por lo tanto, el hombrecillo nunca pensará que ha leído un mensaje antes si no lo ha hecho, nunca olvidará que ha leído un mensaje antes, por lo que nunca, nunca, producirá dos números diferentes para el mismo mensaje exacto ni el mismo. para dos mensajes diferentes.

   Esto es lo que las funciones hash intentan simular. No pueden modelar a este hombrecito con la memoria fotográfica, porque eso requeriría un espacio de almacenamiento infinito y una disponibilidad universal ilimitada, incluso para dispositivos que no están conectados a ningún otro dispositivo de ninguna otra manera. En cambio, se basan en un cálculo determinista pero aleatorio de aspecto que «digiere» el mensaje en su valor hash. La misma función hash, dado el mismo mensaje, producirá el mismo resumen; sin embargo, estas funciones están limitadas en el número de valores hash que pueden devolver. Esto crea la posibilidad de lo que llamamos colisiones hash; hay más mensajes posibles que valores hash, por lo que tarde o temprano (ojalá más tarde), dos yo diferentes Los mensajes producirán el mismo hash.

3. Los hash se pueden descifrar por tres razones básicas.Primero, debido a que son una derivación matemática determinista de su mensaje, los matemáticos (y por lo tanto los atacantes) finalmente encuentran una relación matemática entre un mensaje y su hash, o entre dos mensajes y sus hash resultantes. Lo que alguna vez fue de apariencia aleatoria ya no lo es. Eso permitiría una serie de ataques basados en la naturaleza de la debilidad encontrada; si hay una forma algorítmica, dado un mensaje y su hash, para generar un mensaje en colisión, eso es un problema. Si hay una forma de manipular un mensaje y predecir el hash resultante, ese es un problema diferente. Si de hecho hay una manera de revertir el hash, produciendo un mensaje a partir del hash que, cuando se vuelve a hacer hash, produce el mismo hash, ese «es un problema grave .

   En segundo lugar, debido a que los hash tienen un tamaño de resumen limitado, tarde o temprano, dos mensajes producirán el mismo hash. Eso significa que un atacante no tiene que encontrar el mensaje que usas para producir un determinado hash. ; todo lo que tiene que hacer es encontrar un mensaje que produzca el mismo hash. Las probabilidades de que esto ocurra son escasas, teóricamente una posibilidad entre la cantidad de hash posibles que haya, pero aún mejor que una en el infinito.

   Por último, si bien hay muchos mensajes posibles, hay muchos más pequeños número de mensajes probables . Los mensajes que normalmente damos a las funciones hash suelen tener alguna estructura (basada en el idioma, el tema, el formato electrónico y el propósito), lo que significa que, dada una parte del mensaje, podemos adivinar con mayor precisión otras partes del mensaje. Esto significa, en términos de ciencia de la información, que los mensajes que se convierten en hash a menudo tienen una entropía menor que la función hash en sí; En pocas palabras, una función hash que produce resúmenes de 256 bits teóricamente puede producir cualquier permutación de esos bits, 2 ^ 256. Sin embargo, si hay, digamos, solo 10,000 mensajes posibles que podrían ser ingresados en esta función hash por un sistema que está siendo estudiado para ataque, entonces solo 10,000 de los 2 ^ 256 posibles valores hash serán vistos, y lo más importante, un El atacante, en el peor de los casos, solo tendría que probar las 10,000 entradas posibles para encontrar la que produzca el valor hash que está buscando.

Comentarios

• Y esto … es por eso que me encanta la seguridad de TI ‘ s cosa del sitio de intercambio de pila.
• También su explicación del # 1 es exactamente lo que necesitaba. Sin embargo, tengo una pregunta. Parece que » hashes » son como versiones numéricas de una cosa determinada (contraseñas en este caso). Entonces, si tengo un sitio web y 100000 personas se registran. Luego, el 50% usa la contraseña » contraseña » Puedo ahorrar una tonelada de espacio simplemente almacenando el valor hash de » contraseña » en lugar de contraseña muchas veces?
• Bueno, si ‘ usando un hash seguro (> = tamaño de resumen de 256 bits) y luego almacenando el valor hash de » contraseña » aumentará su tamaño de almacenamiento. Además, si un atacante llegara a ver que el 50% de las cuentas de usuario tenían el mismo hash de contraseña, ‘ sabría que todos ‘ tendría que descifrar una contraseña y tener acceso al 50% de las cuentas de usuario. Debería estar » salando » los hashes de su contraseña; Hay una variedad de métodos, pero el resultado final es que la misma contraseña procesada por el mismo algoritmo produce un resumen diferente, debido a un valor de sal único adicional para cada cuenta.