¿Cómo es posible que el hashing sea imposible de revertir? ¿Hay alguna prueba?

“ ¿Cómo es posible que el hashing sea imposible de revertir? ¿Hay alguna prueba?

Es trivialmente fácil escribir un programa para invertir cualquier función hash. Cualquier programador principiante podría escribir ese código y ese código es una prueba de que se puede hacer. Estás en lo correcto si estabas confundido por qué la gente seguía diciéndote que es imposible revertir, están equivocados (o más exactamente, probablemente entendiste mal su punto)

Las funciones hash obtienen su fuerza criptográfica no por ser imposibles de invertir, sino por el problema de que el código que invierte el hash tarda mucho tiempo en ejecutarse y encontrar la respuesta, digamos un millón de años.

Las funciones hash no son imposibles de invertir, no son prácticas para invertir.

Son una clase de programas que tienen la propiedad fascinante de que son muy rápidos de calcular en la dirección hacia adelante, pero muy lentos para calcular el inverso.

Este tipo de código aprovecha el hecho de que hay funciones básicas en todas las computadoras que destruyen la información. Esto significa que cuando tratamos de revertirlos, encontramos que hay muchos caminos posibles que el avance podría haber tomado para llegar a la respuesta. Si agrega dos dígitos binarios juntos y toma solo un dígito binario del resultado, comenzamos con dos bits de datos y terminamos con un bit. Destruimos o perdimos un bit de datos en el proceso. ¿Cómo revertimos ese código?

0 + 0 = 0

1 + 1 = 0

Hay dos entradas diferentes para la salida de 0. ¿Cuál de estas dos entradas tomó el código directo para obtener la salida de 0? Si todo lo que sabemos es que la salida es 0, no podemos saberlo. Pero si cualquiera de las entradas produce la misma salida, puede pensar que no necesitamos preocuparnos.

Sin embargo, para que las funciones hash funcionen, utilizan esta misma técnica de dos maneras diferentes, de modo que la opción de respuesta inversa solo funciona si todas las opciones de reversa se asignan a la misma entrada.

Supongamos que tiene dos bits que desea hacer hash, A y B, y la salida tiene la adición de un solo bit de A + B como un bit de la salida hash, y A OR B como el otro bit de la salida. Entonces, si la entrada es A = 0, B = 0, la salida es 00. Y si la entrada es A = 1, B = 1, la salida es 01.

Si miramos el primer bit de salida de 0, no podemos decir si la entrada fue 00 u 11. Si miramos el segundo bit de salida, de 1, no podemos decir si la entrada fue 01, 10 o 11. Tampoco si los pasos individuales se pueden revertir directamente. Tenemos que invertir ambos, generar una lista de todas las entradas posibles y luego buscar para encontrar un par de entradas coincidentes que produzcan la salida correcta para ambos bits. Para encontrar el inverso, tenemos que escanear 3 × 2 o 6 posibles caminos que el algoritmo de avance podría haber tomado. Esta simple función es aproximadamente 6 veces más lenta para invertir que para avanzar si no usamos la tabla de búsqueda para acelerarla.

Al combinar muchas operaciones como esta, la ruta inversa puede ser tan difícil de invertir que no se puede hacer trampa con una simple tabla de búsqueda inversa, y la única solución conocida es buscar todas las rutas posibles, lo que podemos hacer que sea grande que llevaría un millón de años.

Todo proviene del hecho de que las computadoras tienen muchas funciones primitivas (como la suma) que pierden información y, como tal, tienen múltiples posibles inversiones.

Las funciones de hash y otros programas similares que no son prácticos para revertir todo aprovechan esta cara, de modo que la única forma de invertir el hash es buscar en un árbol muy grande de muchos caminos posibles para encontrar el inverso correcto.

Hasta ahora, no hay atajos conocidos para hacer que el inverso sea rápido, pero nunca se ha demostrado que los atajos no existan. Eso es parte del problema P vs NP del que quizás hayas oído hablar.

Al leer varias de estas respuestas, creo que podrían no tener sentido a menos que ya esté bien versado en la terminología relevante, así que permítame tratar de explicar esto de una manera que tenga más sentido para los no iniciados.

Un hash, como muchos han dicho, está destinado a ser una función unidireccional. Más importante aún, un hash asigna de un conjunto de cosas a un rango conocido. Por ejemplo, un hash se puede usar para convertir cualquier cadena en un número entre 0 y 4 millones.

Antes de llegar demasiado lejos, hablemos de las funciones unidireccionales y bidireccionales. ( Editar: Permítanme aclarar que no estoy usando las definiciones matemáticas o criptográficas formales; estoy comenzando con definiciones con sentido común para que sea más fácil pensar en ellas; al final de mi respuesta, insinuaré las propiedades de definiciones formales ) . Crear una función trivial unidireccional es fácil. Por ejemplo, f(x) = 0 es una función trivial unidireccional. Su salida es SIEMPRE 0, por lo que es imposible saber cuál fue la entrada de esa función basada en la salida. Lo contrario de una función unidireccional es una función bidireccional, como f(x) = x*2 . Esa es una función bidireccional, porque puede calcular la entrada en función de la salida simplemente dividiendo la salida por dos.

Las funciones de hash son mucho más complicadas que f(x)=0 (naturalmente), entonces, ¿cómo sabemos que son irreversibles? Bueno, depende de lo que quieras decir con irreversible.

Como dije, las funciones hash se asignan de un conjunto de entradas a otro conjunto de salidas. Normalmente, el tamaño del conjunto de salida es menor que el tamaño del conjunto de entrada. Por ejemplo, tome el venerable algoritmo de hash MD5. Asigna un conjunto de entradas (el conjunto de todas las secuencias de bytes, de cualquier longitud) a un conjunto de salidas (el conjunto de todos los números enteros (también conocidos como enteros) de 0 a 2 ^ 128). Ahora, ese conjunto de resultados es enorme . Escrito en formato largo, eso es 340,282,366,920,938,463,463,374,607,431,768,211,456 valores posibles. Afortunadamente, podemos representar cualquier número en ese conjunto con 128 bits (es decir, 16 bytes). Pero el conjunto de posibles entradas es aún mayor. Esencialmente, el conjunto de posibles entradas es infinito. Literalmente, no hay límite para el número de combinaciones de CUALQUIER número de bytes. Lo que eso significa, naturalmente, es que cada valor posible en ese rango (0 a 2 ^ 128) puede ser generado por múltiples entradas posibles. Si ha escrito bien su función hash, entonces cada valor posible en la salida podría generarse por un número infinito de entradas diferentes.

Literalmente, si el hash MD5 fuera perfectamente reversible, eso significaría algo sorprendente: significaría que solo hay 2 ^ 128 cosas posibles en el universo. Significaría que cualquier cosa y todo podría ser “comprimido” hasta 16 bytes; referido perfectamente por su identificador de 16 bits. Como ese no es el caso, el hash MD5 es, en ese sentido, una función irreversible o unidireccional.

Pero espera. Digamos que inventamos una función hash (la llamaremos ‘stupidHash’) que tomó cualquier entrada dada, representada como un número (es decir, cualquier secuencia de cualquier número de bytes), dividió esa entrada por 10 y devolvió el resto. El resto está garantizado para estar en el rango de 0 a 9 (inclusive). Entonces: ¿hemos creado una función unidireccional? Bueno, un poco, pero depende de cómo se defina “unidireccional”. Dada una salida (por ejemplo, 5) no puedo saber qué entrada le dio a esa función para generar esa salida (tal vez su entrada fue 35 o 155, ¿cómo podría saberlo?) … pero PUEDO encontrar fácilmente una entrada que usted PODRÍA dar el stupidHash que también generaría esa misma salida. ¿Es eso lo mismo que una función bidireccional? No exactamente … pero está lo suficientemente cerca como para el propósito de una “función unidireccional”, lo que hace que no sea unidireccional según la definición formal.

¿Por qué nos importa? Bueno, la cosa es que una de las cosas comunes que se deben hacer en las computadoras para evitar almacenar su contraseña es almacenar un hash de su contraseña. Esto es bastante inteligente, porque significa que la computadora no tiene que almacenar su contraseña, pero aún puede verificar cualquier contraseña de entrada para asegurarse de que sea la contraseña correcta. Cualquier contraseña de entrada se convertirá en hash, en comparación con el hash almacenado, y si los dos hashes coinciden, ¡esa debe ser la contraseña correcta! Incluso si un hacker logra robar el hash, el hacker aún no conoce su contraseña. Brillante, ¿verdad? ¡Pero espera! El hacker no NECESITA su contraseña exacta. Solo necesita algo que tenga el mismo valor. A veces, esa cosa que generará el hash con el mismo valor se denomina “pseudoinverso” del valor de hash.

Aquí es donde nos encontramos con respecto a la definición moderna (criptográfica) de “reversible”: si te digo el valor hash, ¿puedes averiguar alguna entrada que puedas dar a la función hash que generará ese mismo valor de salida? Si es así, la función se considera “reversible”, incluso si la otra cosa que le das no se parece en nada a la entrada original.

Para las funciones unidireccionales criptográficas fuertes, es realmente difícil hacerlo. No es imposible, de ninguna manera, pero REALMENTE difícil. La cuestión es que las personas se han vuelto muy buenas para descubrir formas inteligentes de almacenar valores parcialmente hash y facilitar el problema (este es el problema con el que se encontró MD5; es una técnica conocida como “tablas de arco iris”). Pero para funciones hash realmente bien escritas, eso requiere una cantidad astronómica de almacenamiento o una cantidad astronómica de potencia de cálculo (y a veces ambas).

Como han señalado otros, no hay pruebas de que las funciones unidireccionales sean verdaderamente unidireccionales (basadas en la definición bastante específica de unidireccional que se utiliza; consulte Wikipedia para obtener detalles matemáticos sangrientos), pero HEMOS demostrado que si existe una función unidireccional, eso significa que hay dos clases de problemas fundamentalmente diferentes: difícil (P) y loco-duro (NP). En otras palabras, si pudiéramos demostrar que un hash no trivial no se puede revertir (o seudo-revertir), entonces habríamos resuelto el mayor enigma teórico en toda la informática.

Muy buena pregunta. Primero comencemos nombrando las propiedades clave de la función hash.

• es determinista, por lo que el mismo mensaje siempre da como resultado el mismo hash
• es rápido calcular el valor hash para cualquier mensaje dado
• no es factible generar un mensaje a partir de su valor hash, excepto probando todos los mensajes posibles
• un pequeño cambio en un mensaje debería cambiar el valor de hash de manera tan extensa que el nuevo valor de hash parece no estar relacionado con el antiguo valor de hash
• no es factible encontrar dos mensajes diferentes con el mismo valor hash

Por lo tanto, está preguntando sobre el tercer punto de esta lista. En lugar de aburrirte con pruebas matemáticas reales, déjame crear una función. Llamémoslo un candidato hash.

En lugar de implementar todos los puntos mencionados anteriormente, solo me enfocaré en el punto en cuestión. 3er punto para ser más preciso.

Entonces, aquí está mi elegante función irreversible:

Lo creas o no … pero es tan simple como redondear un número. ¿Quieres una prueba?

Tomemos 4.6 como ejemplo. Por lo tanto, nuestro hash sería 5. (acabo de redondear para obtener 5). Si te digo que 5 es mi hash, ¿podrías revertirlo para obtener 4.6? Definitivamente no. Esto prueba que, de hecho, hay funciones irreversibles.

Por supuesto, esta sería una función hash porque falla la mayoría de los otros puntos. Pero la lógica se mantiene.

Suponga que algún sistema usa (input% 13) como su función hash, y la función es públicamente conocida. Además, suponga que la contraseña solo puede ser enteros (no palabras).

Supongamos que piratea la base de datos y descubre que el hash de contraseña de un usuario en particular es 3. Su contraseña puede ser cualquiera de {3, 16, 29, 42 …}. Esto reduce a un ataques de fuerza bruta ̶, ̶ tratando cada 13 ̶ número entero, ̶ a partir de 3. Esto no es computacionalmente nada mejor que intenta cada ̶i̶n̶t̶e̶g̶e̶r̶.̶
(Corrección señalada por Scott Berry)

Ahora, esta era una mala función hash porque le permitía calcular alguna imagen previa (3,16,29 ..) a partir de la imagen (3). Las funciones hash del mundo real como SHA y MD5 están diseñadas de tal manera que no es factible computacionalmente calcular cualquier imagen previa, y mucho menos la imagen previa. La resistencia previa a la imagen es una de las propiedades esperadas de una función hash unidireccional. Un hash unidireccional que te permite calcular una preimagen es inútil. Esta propiedad debe complementar la propiedad de Resistencia de colisión: no es factible encontrar dos entradas que se asignen al mismo hash.

Tenga en cuenta que las funciones hash unidireccionales son solo conjeturas todavía. Aunque hay funciones que no hemos podido invertir, no hay pruebas de que no se pueda hacer. Pero lo positivo es que las personas más inteligentes no han podido encontrar la inversa de muchas funciones hash unidireccionales durante varios años y esperamos que nuestros piratas informáticos no sean más inteligentes que eso. Cuando una función hash unidireccional se “agrieta”, tendremos que encontrar alguna nueva función hash unidireccional, y así continuará.

Explicación infantil: Nuestros “datos” son un grupo de personas. Su función de “hashing” es solo su fecha de nacimiento.

Hash (Steve McDude, 05 de septiembre de 1987) = 05 de septiembre de 1987

Si su conjunto de no es demasiado grande, puede verificar la fecha de nacimiento de todos para confirmar quién es. Una vez que el conjunto se hace más grande, puede haber más de una persona con esa fecha de nacimiento (colisión hash).

Pero en cualquier caso, nada sobre “05 de septiembre de 1987” dice inherentemente “Steve McDude”.

Hay al menos dos formas de ver la pregunta.

• No se puede “invertir” en el sentido matemático, por razones de sentido común de que la salida hash tiene solo un número finito de valores, mucho más pequeño que el número de entradas potenciales.
• Sin embargo, a efectos prácticos, hay situaciones en las que puede estar bastante seguro de cuál era la entrada, para un hash de salida determinado, mediante búsqueda de diccionario o tabla de arco iris, simplemente porque las entradas de baja complejidad tienen hashes conocidos.

Por ejemplo, google eb61eead90e3b899c6bcbe27ac581660 .

Ellos pueden.

En general, el objetivo de una función Hash es que se asigne desde su conjunto de datos a sus depósitos de la manera más uniforme posible (para minimizar las colisiones), ser reversible es irrelevante para el “hashing”. (% N hace una función hash fina para N cubos).

Sin embargo, para una función criptográfica hash, la idea es hacer que no sea posible invertir (básicamente, esto significa que es excesivamente costoso para la fuerza bruta y no hay “trucos” para resolver). (% N realiza una función hash criptográfica * terrible *).

Posteriormente se descubre que algunas funciones hash criptográficas están rotas (es decir, posiblemente reversibles), y en mi opinión, es seguro asumir que una función se romperá eventualmente.

Hay una larga lista de funciones hash criptográficas, aunque se ha descubierto que muchas son vulnerables y no deben usarse. Incluso si una función hash nunca se ha roto, un ataque exitoso contra una variante debilitada de la misma puede socavar la confianza de los expertos y conducir a su abandono. Por ejemplo, en agosto de 2004 se encontraron debilidades en una serie de funciones hash que eran populares en ese momento, incluidas SHA-0, RIPEMD y MD5. Esto ha puesto en duda la seguridad a largo plazo de los algoritmos posteriores que se derivan de estas funciones hash, en particular, SHA-1 (una versión reforzada de SHA-0), RIPEMD-128 y RIPEMD-160 (ambas versiones reforzadas de RIPEMD). Ni SHA-0 ni RIPEMD son ampliamente utilizados ya que fueron reemplazados por sus versiones reforzadas.

El ejemplo de hash de contraseña generalmente se hace más difícil de romper al almacenar una sal, una variable que también se pasa a la función de hashing, para cada usuario (lo que significa que debe romper el hash de cada usuario individualmente y no puede usar “tablas de arco iris” “), y utilizando algoritmos, como bcrypt , que son inherentemente lentos y difíciles de paralelizar, vea una respuesta de security.stackexchange sobre bcrypt. (Nota: las mejores prácticas probablemente cambiarán en algún momento en el futuro).

La respuesta simple es que hay información perdida durante la ejecución de la función hash unidireccional . Esto a diferencia del cifrado que es reversible.

En el caso de la operación de módulo que mencionó, 1% 13 rinde 1 pero también 14% 13 rinde 1 y 27 rinde 1. Muchos valores posibles de x rinden 1. Entonces dado 1 devuelve 1 o 14 o 27 o … En su Por ejemplo, su fórmula invertida solo devolverá un valor posible de x y nunca dará x = 1. Si x fuera la clave, ¿qué valor de x devuelve? Si estaba haciendo una fuerza bruta, entonces potencialmente hay una cantidad bastante considerable de x que debe intentar obtener la clave correcta.

Solo como una nota, usar simplemente módulo no es lo suficientemente bueno para una función hash criptográfica / segura. Pero, sirve como una demostración de irreversibilidad.

No hay prueba Si proporciona una prueba, lo hará (moderadamente) rico y famoso (al menos en algunos círculos).

Una prueba contraria a un hash específico respetado, digamos SHA-256, te haría famoso en algunos círculos si publicas, y muy rico o encarcelado (o quizás asesinado) si tomas una ruta nefasta.

¿Una contra prueba general? Más o menos lo mismo que antes, pero con mucha más fama y una mayor probabilidad de muerte.

La confianza es alta de que SHA-256 es seguro. Si no es así, miles de millones de dólares podrían perderse en un instante.

La confianza de que existen hashes seguros es quizás mil millones de veces mayor que la confianza de que SHA-256 es seguro. Aún así, no podemos probarlo.

Las posibles entradas que puede tener una función hash son infinitas, pero la salida hash está limitada a “solo” 2 ^ 256 valores (es decir, SHA-256). Esto significa, desde el principio de la paloma, que cada “cubo de hash” tiene un número infinito de entradas posibles. Este hecho por sí solo hace que la inversión sea imposible solo porque para cada cadena hash hay una infinidad de cadenas de entrada posibles. Es imposible si no puede hacer suposiciones sobre su entrada. Sin embargo, si agrega algunas restricciones a la entrada, como la longitud máxima (por ejemplo, 8 caracteres), solo la carcasa inferior, la carcasa superior, etc., aún puede “revertir” un hash forzándolo con fuerza bruta (es decir, probando todas las entradas posibles )

Sí, la prueba es fácil. Se llama el principio de Pigeonhole. Una función hash súper simple es arity, también conocido como módulo 2 o par / impar. El hash de 1 es 1, 2 es 0, 3 es 1, 4 es 0, etc. (arity se ha utilizado comúnmente como una función hash para la detección de errores en muchas aplicaciones; funciones hash ligeramente más complicadas con un tamaño mayor pero aún muy pequeño -rango todavía se usan a menudo).

Debido a que solo hay 2 valores hash posibles, si le digo un número hash a 0 no puede decirme si el original era 2 o 4 o 3750 o cualquier otro número par.

Los hash criptográficos tienen más opciones, pero un hash de 256 bits sigue siendo muy limitado; incluso un archivo de 40 caracteres tiene 320 bits, por lo que es obvio que hay varios archivos con el mismo valor de hash. Un hash dado simplemente no tiene suficiente información para identificar de forma exclusiva el valor original.

Lo que es más interesante es la cuestión de si, dado un valor hash, puede producir al menos una entrada que tenga hash para ese valor. Las funciones criptográficas de hash intentan dificultar eso, pero demuestran que es difícil en general (prohibitivamente).

Muchas buenas respuestas aquí. Proporcionaré uno muy simple que funcionó en el niño de 12 años de mis vecinos.

Digamos que hacemos el hash simplemente cuadrando el número (multiplicando por sí mismo). Digamos que el código secreto es -3. El hash calculado será 9 y ese es el valor de control visible y expuesto.

Supongamos ahora que un pirata informático malvado obtiene ese valor e intenta descifrar el código original. Tendrán un problema porque puede ser tanto 3 como -3.

Ahora, en la práctica, utilizamos la operación de módulo y un montón de otros trucos para codificar la ingeniería inversa del código original, pero la idea es la misma: hay más códigos para codificar que los codificadores disponibles, por lo que es posible verificar que el código proporcionado corresponde a un hash almacenado, pero no es posible calcular hacia atrás qué código conduce a él.

Los algoritmos de hash incluyen como parte de sus funciones lógicas que producen la misma salida para muchas entradas diferentes.

Para un ejemplo muy simple, por ejemplo X mod 5 = 3 es verdadero para 3, 8, 13, 18, …

Si sabe que el hash produjo 3 como resultado, todavía tiene un número infinito de entradas posibles, por lo que no hay forma de revertir el hash y determinar la entrada.

Las funciones logarítmicas y trigonométricas proporcionan muchas otras opciones para funciones que no admiten la determinación de la entrada desde la salida.

Hashing es una función. Toma varias entradas y recibe una salida. Las funciones más comunes no son reversibles. Considere la siguiente función

F (x, y) = x / y

Si le doy esta función, y una salida de esta función no puede deducir los valores originales de x & y. Si te digo que el resultado de F (x, y) es 5, entonces (x, y) podría ser (5,1) pero también puede ser igualmente (10,2) o (15,3). Todo lo que sabría con certeza en este caso es que x = 5 * y. Del mismo modo, algunas funciones con un solo argumento siguen siendo irreversibles. Considere la siguiente función:

G (x) = x mod 7

Si le doy una salida resultante de esa función, no puede saber cuál era el valor de entrada de x. Por ejemplo, si la respuesta a G (x) es 3, entonces sabes que x podría ser 3 o 10 o 17 o 24 o 31 o … … solo sabes que x = 7k + 3 para algún valor entero desconocido de ‘k’ . Por último, considere esta siguiente función:

H (x) = x * x

¡Decir ah! bueno, esta función es trivialmente reversible. Si te digo que la respuesta fue 25, entonces sabes que x debe ser la raíz cuadrada de 25, por lo que x debe ser 5.… Bueno, también puede ser -5.

Si considera los dos casos anteriores, puede observar una similitud crítica. Las 3 funciones producen espacios de solución ambiguos cuando intentamos resolver sus funciones inversas. El problema es que estas funciones no son biyecciones, lo que significa que múltiples valores diferentes para la entrada x pueden producir la misma salida resultante. Fundamentalmente, el dominio de estas funciones es mayor que el rango de sus soluciones.

Imagínese compartir una clase con otro estudiante con su nombre, cada vez que el maestro dice solo su nombre, ambos responden porque simplemente no hay suficiente información para desambiguar a cuál de ustedes se está haciendo referencia. El hash es similar, es posible que conozca la solución a un hash, pero fundamentalmente no necesariamente tiene suficiente información para desambiguar qué elemento del rango originó esa salida.

Intente comprender qué es el hashing mirando 10 implementaciones. Puede requerir que comprenda qué es una máquina de estados (por lo tanto, comprender la programación). Los matemáticos lo explican de esta manera: X -> B donde X es el conjunto de posibles entradas y B es el conjunto de posibles resultados. hash (X) -> B para la mayoría de las funciones hash significa que múltiples X producen el mismo B. Por ejemplo, el hash md5 en un cdrom seguirá siendo solo 32bytes. ¿Cómo convertir 32 bytes en un cdrom? Revertir se llama encontrar colisiones de hash y es una forma de cambiar las cosas con el hecho de que se conozcan. Por lo tanto, encontrar un hack que produzca el mismo hash de 32 bytes se llama ataque. Pero encontrar ese truco es ‘mucho trabajo’ y mucho ‘intento y error’ y, por lo general, no vale la pena el esfuerzo. Si el esfuerzo es bajo, entonces la función hash se considera débil (dado un problema).

Hashing no es imposible de revertir en absoluto.

Aquí hay una manera simple de revertir el hash, y funciona para cada función de hash: pruebe todas las entradas hasta que toque la correcta.

Es solo que para el hashing criptográficamente relevante, solo usamos funciones hash para las cuales esa es aproximadamente la forma más eficiente conocida de invertir la función hash. Si el conjunto de entrada es lo suficientemente grande, esto hace que la inversión sea tan lenta que prácticamente no vale la pena.

Una vez que se conoce una forma considerablemente más eficiente de invertir una función hash, o el hardware de la computadora se vuelve lo suficientemente rápido como para abordar el tamaño del conjunto de entrada, las personas pasan a un conjunto de entrada más grande o a una función hash más complicada.

Por ejemplo, MD5 y SHA1 se pueden invertir con éxito en muy poco tiempo (dependiendo del tamaño del conjunto de entrada).

El hash puede ser reversible, normalmente no lo es. Suponga que toma el hash más simple de números, módulo aritmético, digamos 10. Si su conjunto de datos son los enteros 1–9, entonces puede reconstruir datos a partir del hash. Sin embargo, normalmente un hash pierde información, por lo que si su conjunto de datos son los enteros 1–99, entonces sabe cuál es el último dígito pero se pierde la información relativa al primero.

Revertir es menos un problema que colisionar: una entrada diferente que produce el mismo hash que, en casi todos los usos del hash, es igual de bueno. MD5 solía ser considerado como un hash unidireccional (no reversible), pero se demostró que era colisionable hace muchos años. SHA512 es mucho más complejo, por lo que puede llevar siglos descubrir que está sujeto a la misma falla, o puede que nunca se encuentre. Pero un hash unidireccional que puede colisionar es un agujero de seguridad, incluso si no se puede revertir. (Muchos de los llamados programadores usan un hash MD5 para, por ejemplo, contraseñas, y se dan cuenta de que están listos: el sitio es seguro. Gran error. Ni siquiera usaría SHA512 como está).

Una respuesta realmente intuitiva utiliza la analogía de la función mod.

9 mod 2 = 1, entonces aquí 9 es nuestra clave, x mod 2 es nuestra función de hashing y 1 es el valor en esa clave en la matriz. Pero supongamos que con un valor 1 deseamos ‘invertir’ el hash para encontrar la clave, bueno, hay una cantidad infinita de claves que podrían haber producido ese valor (1) además de 9, por ejemplo, 3 mod 2 = 1. Por lo tanto, tenemos ‘ colisiones ‘(¡tanto 9 como 3 hashes a 1!).

Eche un vistazo al principio del palomar para el argumento cs estándar de por qué las funciones hash deben tener colisiones. Pero se reduce a: tenemos más claves posibles de las que tenemos espacio en la matriz, por lo que al menos una ranura en la matriz debe tener más de un valor. Por lo tanto, no estamos seguros de qué clave hash a un valor específico.

Otros ans: ¿Por qué no se pueden revertir las funciones hash?