informatica - ¿Por qué no es posible revertir un hash criptográfico?

huella hash (5)

¿Por qué no puedes simplemente invertir el algoritmo como si pudieras invertir una función matemática? ¿Cómo es posible hacer un algoritmo que no sea reversible?

Y si usas una tabla arcoíris, ¿qué hace que usar una sal sea imposible de romper? Si está creando una tabla de arcoíris con fuerza bruta para generarla, entonces inventa cada valor de texto claro posible (a una longitud), que terminaría incluyendo la sal para cada contraseña posible y cada posible sal (la sal y la contraseña / texto acaba de unirse como una sola pieza de texto).

No creo que el md5 te brinde el resultado completo, así que no puedes trabajar al revés para encontrar las cosas originales que fueron md5-ed

Piense en 2 números del 1 al 9999. Agréguelos. Ahora dime el último dígito.

No puedo, a partir de esa información, deducir los números que originalmente pensaste. Ese es un ejemplo muy simple de un hash de un solo sentido.

Ahora, puedo pensar en dos números que dan el mismo resultado, y aquí es donde este simple ejemplo difiere de un hash criptográfico "apropiado" como MD5 o SHA1. Con esos algoritmos, debe ser computacionalmente difícil obtener una entrada que produzca un hash específico.

Una gran razón por la que no puede revertir la función hash es porque se pierden datos.

Considere una función de ejemplo simple: ''O''. Si aplica eso a sus datos de entrada de 1 y 0, rinde 1. Pero ahora, si sabe que la respuesta es ''1'', ¿cómo puede hacer retroceder los datos originales? No puedes. Podría haber sido 1,1 o tal vez 0,1 o tal vez 1,0.

En cuanto a las mesas de salazón y arcoiris. Sí, en teoría, podría tener una tabla de arcoíris que abarcaría todas las sales y contraseñas posibles, pero prácticamente, eso es demasiado grande. Si ha probado todas las combinaciones posibles de letras minúsculas, mayúsculas, números y doce símbolos de puntuación, hasta 50 caracteres, eso es (26 + 26 + 10 + 12) ^ 50 = 2.9 x 10 ^ 93 posibilidades diferentes. Eso es más que la cantidad de átomos en el universo visible.

La idea detrás de las tablas del arco iris es calcular el hash para un grupo de contraseñas posibles de antemano, y las contraseñas son mucho más cortas que 50 caracteres, por lo que es posible hacerlo. Es por eso que desea agregar una sal al frente: si agrega ''57sjflk43380h4ljs9flj4ay'' al frente de la contraseña. Mientras que alguien ya pudo haber calculado el hash para "pa55w0rd", nadie ya habrá calculado el que tiene para ''57sjflk43380h4ljs9flj4aypa55w0rd''.

md5 es 128bit, eso es 3.4 * 10 ^ 38 combinaciones.

el número total de contraseñas de ocho caracteres:

solo caracteres minúsculos y números: 36 ^ 8 = 2.8 * 10 ^ 12
mayúscula y minúscula y números: 62 ^ 8 = 2.18 * 10 ^ 14

Debe almacenar 8 bytes para la contraseña, 16 para el valor de md5, es decir, 24 bytes en total por entrada.

Por lo tanto, necesita aproximadamente 67000G o 5200000G de almacenamiento para su mesa arcoiris. La única razón por la que es posible descubrir las contraseñas es porque la gente usa las obvias.

MD5 está diseñado para ser criptográficamente irreversible . En este caso, la propiedad más importante es que es computacionalmente inviable encontrar el valor inverso de un hash, pero es fácil encontrar el hash de cualquier dato. Por ejemplo, pensemos solo en operar con números (después de todo, los archivos binarios podrían interpretarse como un número muy largo).

Digamos que tenemos el número "7", y queremos tomar el hash de ello. Quizás lo primero que intentamos como nuestra función hash es "multiplicar por dos". Como veremos, esta no es una muy buena función hash, pero lo intentaremos para ilustrar un punto. En este caso, el hash del número será "14". Eso fue bastante fácil de calcular. Pero ahora, si miramos lo difícil que es revertirlo, ¡descubrimos que también es igual de fácil! ¡Dado cualquier hash, podemos dividirlo por dos para obtener el número original! Este no es un buen hash, porque el objetivo de un hash es que es mucho más difícil calcular el inverso de lo que es calcular el hash (esta es la propiedad más importante en al menos algunos contextos).

Ahora, probemos otro hash. Para este, voy a tener que introducir la idea de la aritmética del reloj. En un reloj, no hay una cantidad infinita de números. De hecho, va de 0 a 11 (recuerda, 0 y 12 son lo mismo en un reloj). Entonces, si "agregas uno" a 11, obtienes cero. Puede extender las ideas de multiplicación, adición y exponenciación a un reloj. Por ejemplo, 8 + 7 = 15, ¡pero 15 en un reloj realmente son solo 3! Entonces en un reloj, dirías 8 + 7 = 3! 6 * 6 = 36, pero en un reloj, 36 = 0! entonces 6 * 6 = 0! Ahora, para el concepto de poderes, puedes hacer lo mismo. 2 ^ 4 = 16, pero 16 es solo 4. ¡Entonces 2 ^ 4 = 4! Ahora, así es como se relaciona con hash. ¿Qué tal si probamos la función hash f (x) = 5 ^ x, pero con la aritmética del reloj? Como verá, esto conduce a algunos resultados interesantes. Tratemos de tomar el hash de 7 como antes.

Vemos que 5 ^ 7 = 78125 pero en un reloj, eso es solo 5 (si haces las matemáticas, verás que hemos rodeado el reloj 6510 veces). Entonces obtenemos f (7) = 5. Ahora, la pregunta es, si te dijera que el hash de mi número era 5, ¿serías capaz de descubrir que mi número era 7? Bueno, en realidad es muy difícil calcular el reverso de esta función en el caso general. Las personas mucho más inteligentes que yo han demostrado que, en ciertos casos, revertir esta función es mucho más difícil que calcularlo. (EDITAR: Nemo ha señalado que esto de hecho no ha sido "probado", de hecho, la única garantía que obtienes es que mucha gente inteligente ha intentado durante mucho tiempo encontrar una manera fácil de hacerlo, y ninguno de ellos han tenido éxito.) El problema de revertir esta operación se llama el " Problema del Logaritmo Discreto ". Búscalo para una cobertura más profunda. Esto es al menos el comienzo de una buena función hash.

Con las funciones hash del mundo real, la idea es básicamente la misma: encuentra alguna función que es difícil de revertir. La gente mucho más inteligente que yo ha diseñado MD5 y otros hash para hacerlos difícilmente reversibles.

Ahora, quizás antes se le ha ocurrido la idea: "¡sería fácil calcular el inverso! ¡Simplemente tomaría el hash de cada número hasta que encuentre el que coincida!" Ahora, para el caso donde los números son todos menos de doce, esto sería factible. Pero para el análogo de una función hash del mundo real, imagina que todos los números involucrados son enormes . La idea es que todavía es relativamente fácil calcular la función hash para estos números grandes, pero buscar a través de todas las entradas posibles se vuelve más difícil mucho más rápido. Pero con lo que te has tropezado es una idea todavía muy importante: buscar en el espacio de entrada una entrada que proporcione un resultado coincidente. Las tablas del arco iris son una variación más compleja de la idea, que utiliza tablas precalculadas de pares de entrada-salida de manera inteligente para posibilitar la búsqueda rápida a través de una gran cantidad de posibles entradas.

Ahora digamos que está usando una función hash para almacenar contraseñas en su computadora. La idea es esta: la computadora solo almacena el hash de la contraseña correcta. Cuando un usuario intenta iniciar sesión, compara el hash de la contraseña de entrada con el hash de la contraseña correcta. Si coinciden, supones que el usuario tiene la contraseña correcta. La razón por la que esto es ventajoso es porque si alguien roba su computadora, todavía no tienen acceso a su contraseña, solo el resumen. Debido a que la función de hash fue diseñada por personas inteligentes para que sea difícil tomarla al revés, no pueden recuperar fácilmente su contraseña.

La mejor opción de un atacante es un ataque de fuerza bruta, donde intentan un montón de contraseñas. Al igual que podría intentar los números menos que 12 en el problema anterior, un atacante podría probar todas las contraseñas compuestas por números y letras de menos de 7 caracteres, o todas las palabras que aparecen en el diccionario. Lo importante aquí es que no puede probar todas las contraseñas posibles, porque hay demasiadas contraseñas de 16 caracteres posibles, por ejemplo, para probar alguna vez . Entonces, el punto es que un atacante tiene que restringir las posibles contraseñas que prueba, de lo contrario, nunca revisará un pequeño porcentaje de ellas.

Ahora, en cuanto a una sal, la idea es esta: ¿Qué pasaría si dos usuarios tuvieran la misma contraseña? Tendrían el mismo hash. Si lo piensas, el atacante en realidad no tiene que descifrar las contraseñas de cada usuario individualmente. Simplemente revisa todas las contraseñas de entrada posibles y compara el hash con todos los hashes. Si coincide con uno de ellos, entonces ha encontrado una nueva contraseña. Lo que realmente nos gustaría obligarlo a hacer es calcular un nuevo hash para cada combinación de usuario + contraseña que quiera verificar. Esa es la idea de una sal, es que hagas que la función hash sea ligeramente diferente para cada usuario, por lo que no puede reutilizar un solo conjunto de valores precalculados para todos los usuarios. La forma más sencilla de hacerlo es colocar una cadena aleatoria a la contraseña de cada usuario antes de tomar el hash, donde la cadena aleatoria es diferente para cada usuario. Entonces, por ejemplo, si mi contraseña es "shittypassword", mi hash podría aparecer como MD5 ("6n93nshittypassword") y si su contraseña es "shittypassword", su hash podría aparecer como MD5 ("fa9elshittypassword"). Este pequeño "fa9el" se llama "sal", y es diferente para cada usuario. Por ejemplo, mi sal es "6n93n". Ahora, este pequeño bit que está añadido a su contraseña también se almacena en su computadora. Cuando intenta iniciar sesión con la contraseña X, la computadora puede simplemente calcular MD5 ("fa9el" + X) y ver si coincide con el hash almacenado.

Así que la mecánica básica del inicio de sesión permanece sin cambios, pero para un atacante, ahora se enfrentan a un desafío más desalentador: en lugar de una lista de hashes MD5, se enfrentan a una lista de sumas y sales MD5. Ellos esencialmente tienen dos opciones:

Pueden ignorar el hecho de que los hash están salados y tratar de descifrar las contraseñas con su tabla de búsqueda como están. Sin embargo, las posibilidades de que realmente descifren una contraseña son muy reducidas. Por ejemplo, incluso si "shittypassword" está en su lista de entradas para verificar, lo más probable es que "fa9elshittypassword" no lo esté. Con el fin de obtener incluso un pequeño porcentaje de la probabilidad de descifrar una contraseña que tenían antes, tendrán que probar órdenes de magnitud más contraseñas posibles.
Pueden volver a calcular los hash por usuario. Entonces, en lugar de calcular MD5 (passwordguess), para cada usuario X, calculan MD5 (Salt_of_user_X + passwordguess). Esto no solo los obliga a calcular un nuevo hash para cada usuario que quieren descifrar, sino que también les impide utilizar tablas precalculadas (como la tabla rainbow, por ejemplo), porque no pueden saber qué Salt_of_user_X está antes de la mano, por lo que no pueden precalcular los hash para probar.

Entonces, básicamente, si están tratando de usar tablas precalculadas, el uso de una sal efectivamente aumenta en gran medida las posibles entradas que tienen que probar para descifrar la contraseña, e incluso si no están utilizando tablas precalculadas, todavía las ralentiza por una factor de N, donde N es la cantidad de contraseñas que está almacenando.

Espero que esto responda todas sus preguntas.