encryption - informatica - ¿Cómo funcionan las funciones hash unidireccionales?
huella hash (7)
Aquí hay un ejemplo muy simple. Supongamos que soy un criptógrafo principiante y creo una función hash que hace lo siguiente:
int SimpleHash(file) {
return 0 if file.length is even;
return 1 if file.length is odd;
}
Ahora aquí está la prueba. SimpleHash(specialFile) es 0. ¿Cuál fue mi archivo original?
Obviamente, no hay forma de saberlo (aunque es probable que descubras con bastante facilidad que mi hash se basa en la longitud del archivo). No hay forma de "reconstituir" mi archivo basado en el hash porque el hash no contiene todo lo que hizo mi archivo.
Leí el artículo de Wikipedia sobre hashes md5, pero todavía no puedo entender cómo un hash no puede ser "reconstituido" de nuevo al texto original.
¿Podría alguien explicarle a alguien que sabe muy poco acerca de la criptografía cómo funciona esto? ¿Qué parte de la función lo hace de una sola dirección?
Como todos hasta ahora simplemente han definido qué función hash era, voy a morder.
Una función unidireccional no es solo una función hash, una función que pierde información, sino una función f para la cual, dada una imagen y ("SE" o 294 en las respuestas existentes), es difícil encontrar un pre imagen x tal que f(x)=y .
Es por eso que se llaman de una sola dirección: puede calcular una imagen pero no puede encontrar una imagen previa para una imagen determinada.
Ninguna de las funciones hash ordinarias propuestas hasta ahora en las respuestas existentes tiene esta propiedad. Ninguno de ellos son funciones hash criptográficas unidireccionales. Por ejemplo, dado "SE", puede recoger fácilmente la entrada "SXXXE", una entrada con la propiedad que X-encode ("SXXXE") = SE.
No hay funciones unidireccionales "simples". Tienen que mezclar sus entradas tan bien que no solo no reconoce la entrada en absoluto en la salida, sino que tampoco reconoce otra entrada.
SHA-1 y MD5 solían ser populares funciones unidireccionales, pero ambas están casi rotas (conocimientos especializados para crear imágenes previas para imágenes determinadas, o casi pueden hacerlo). Hay un concurso en curso para elegir uno nuevo estándar, que se llamará SHA-3 .
Un enfoque obvio para invertir una función unidireccional sería computar muchas imágenes y mantenerlas en una tabla asociando a cada imagen la preimagen que la produjo. Para que esto sea imposible en la práctica, todas las funciones de una sola vía tienen una salida grande, de al menos 64 bits pero posiblemente mucho más grande (hasta, por ejemplo, 512 bits).
EDITAR: ¿Cómo funcionan la mayoría de las funciones hash criptográficas?
Por lo general, tienen en su núcleo una única función que realiza transformaciones complicadas en un bloque de bits (un cifrado de bloque ). La función debería ser casi biyectiva (no debería mapear demasiadas secuencias a la misma imagen, porque eso causaría debilidades más adelante) pero no tiene que ser exactamente biyectivo. Y esta función se itera un número fijo de veces, lo suficiente como para hacer que la entrada (o cualquier entrada posible) sea imposible de reconocer.
Tomemos el ejemplo de Skein , uno de los candidatos fuertes para el contexto SHA-3. Su función central se itera 72 veces. La única cantidad de iteraciones para las cuales los creadores de la función saben cómo relacionar algunas veces las salidas con algunas entradas es de 25. Dicen que tiene un "factor de seguridad" de 2.9.
Disparando por una analogía simple aquí en lugar de una explicación compleja.
Para empezar, dividamos el tema en dos partes, operaciones unidireccionales y hash. ¿Qué es una operación unidireccional y por qué querrías una?
Las operaciones de una manera se llaman así porque no son reversibles. La mayoría de las operaciones típicas, como la suma y la multiplicación, se pueden invertir mientras que la división del módulo no se puede revertir. ¿Por qué es eso importante? Debido a que desea proporcionar un valor de salida que 1) es difícil de duplicar sin las entradas originales y 2) no proporciona ninguna forma de averiguar las entradas de la salida.
Reversible
Además :
4 + 3 = 7
Esto se puede revertir tomando la suma y restando uno de los sumandos
7 - 3 = 4
Multiplicación :
4 * 5 = 20
Esto se puede revertir tomando el producto y dividiéndolo por uno de los factores
20 / 4 = 5
No reversible
División de módulo :
22 % 7 = 1
Esto no puede revertirse porque no hay ninguna operación que pueda hacer con el cociente y el dividendo para reconstituir el divisor (o viceversa).
¿Puedes encontrar una operación para completar donde el ''?'' ¿es?
1 ? 7 = 22
1 ? 22 = 7
Dicho esto, las funciones hash unidireccionales tienen la misma calidad matemática que la división módulo.
¿Porque es esto importante?
Digamos que te di la llave de un casillero en una terminal de autobuses que tiene mil casilleros y te pedí que se la entregaras a mi banquero. Siendo el tipo inteligente que eres, por no mencionar sospechoso, inmediatamente mirarías la clave para ver qué número de casillero está escrito en la llave. Sabiendo esto, he hecho algunas cosas tortuosas; primero encontré dos números que al dividirme usando la división de módulo me da un número en el rango entre 1 y 1000, segundo borré el número original y escribí el divisor del par de números, en segundo lugar elegí una terminal de bus que tiene una proteger a los casilleros de los malhechores solo dejando que las personas prueben un casillero al día con su llave; el tercero, el banquero, ya sabe el dividendo, así que cuando obtenga la llave podrá hacer los cálculos y calcular el resto y saber qué casillero abrir.
Si elijo los operandos sabiamente, puedo llegar a una relación uno a uno entre el cociente y el dividendo que lo obliga a probar cada casillero porque la respuesta difunde los resultados de las posibles entradas sobre el rango de números deseados, los casilleros disponible en la terminal. Básicamente, significa que no puede adquirir ningún conocimiento sobre el resto, incluso si conoce uno de los operandos.
Entonces, ahora puedo ''confiar'' en que entregues la llave a su legítimo propietario sin preocuparte de que puedas adivinar fácilmente a qué casillero pertenece. Claro, podrías buscar por la fuerza bruta todos los casilleros pero eso tomaría casi 3 años, un montón de tiempo para que mi banquero use la llave y vacíe el casillero.
Vea las otras respuestas para más detalles sobre las diferentes funciones hash.
En términos simples, una función hash funciona haciendo un gran lío enredado de los datos de entrada.
Ver MD5 por ejemplo. Procesa los datos de entrada en bloques de 512 bits. Cada bloque se divide en 16 palabras de 32 bits. Hay 64 pasos, cada paso usando una de las 16 palabras de entrada. Entonces, cada palabra se usa cuatro veces en el transcurso del algoritmo. Aquí es de donde proviene la viabilidad: cualquier bit de entrada se ingresa en varios lugares, y entre dos de esas entradas, la función mezcla todos los datos actuales para que cada bit de entrada impacte la mayor parte del estado de ejecución de 128 bits. Esto le impide invertir la función o calcular una colisión observando solo una parte de los datos. Tienes que mirar los 128 bits completos, y el espacio de los bloques de 128 bits es demasiado ancho para que puedas atravesarlo eficientemente.
Ahora MD5 no hace un buen trabajo, ya que se pueden encontrar colisiones para esa función. Desde el punto de vista de un criptógrafo, MD5 es una función de cifrado rotativa. El procesamiento de un bloque de mensajes M (512 bits) usa un estado de entrada V (un valor de 128 bits) y calcula el nuevo estado V ''como V'' = V + E (M, V) donde ''+'' es una palabra- además, "E" es una función de cifrado simétrica (también conocida como "cifrado de bloque") que utiliza M como clave y V como el mensaje que se va a cifrar. Desde una mirada más cercana, E can es una especie de "red Feistel extendida", similar al cifrado de bloques DES, con cuatro cuartos en lugar de dos mitades. Los detalles no son importantes aquí; mi punto es que lo que hace una "buena" función hash, entre las funciones hash que usan esa estructura (llamada "Merkle-Damgård"), es similar a lo que hace que un cifrado de bloque sea "seguro". Los exitosos ataques de colisión en MD5 utilizan criptoanálisis diferencial, una herramienta que fue diseñada para atacar a las cifras de bloques en primer lugar.
Desde un buen cifrado de bloques hasta una buena función hash, hay un paso que no debe descartarse. Con la estructura Merkle-Damgård, la función hash es segura si el cifrado de bloques subyacente es resistente a los "ataques de clave relacionados", una propiedad bastante oscura contra la que los cifrados de bloque rara vez se refuerzan porque, para el cifrado simétrico, los ataques clave relacionados apenas tienen impacto. Por ejemplo, el cifrado AES no resultó tan resistente a los ataques clave relacionados como se podía desear, y esto no provocó el pánico general. Esa resistencia no era parte de las propiedades que se buscaban cuando se diseñó AES. Simplemente evita convertir el AES en una función hash. Hay una función hash llamada Whirlpool, que se basa en un derivado de Rijndael, "Rijndael" es el nombre inicial de lo que se convirtió en el AES; pero Whirlpool se ocupa de modificar las partes de Rijndael que son débiles para los ataques clave relacionados.
Además, hay otras estructuras que se pueden usar para construir una función hash. Las funciones estándar actuales (MD5, SHA-1 y la familia "SHA-2", también conocidas como SHA-224, SHA-256, SHA-384 y SHA-512) son funciones de Merkle-Damgård, pero muchas de las aspirantes a los sucesores no lo son Hay una competencia en curso, organizada por el NIST (la organización federal de EE. UU. Que se ocupa de ese tipo de cosas), para seleccionar una nueva función hash estándar, denominada "SHA-3". Vea esta página para más detalles. En este momento, tienen hasta 14 candidatos de un total inicial de 51 (sin contar una docena adicional que no pasó la prueba administrativa de enviar un envío completo con código que se compila y se ejecuta correctamente).
Ahora tengamos un aspecto más conceptual. Una función hash segura debe parecerse a un oráculo aleatorio : un oráculo es una caja negra que, cuando se le da un mensaje M como entrada, emite una respuesta h (M) que se elige al azar, uniformemente, en el espacio de salida (es decir, -bit strings si la longitud de salida de la función hash es n ). Si se le da el mismo mensaje M nuevamente como entrada, el oráculo emite el mismo valor que anteriormente. Aparte de esa restricción, la salida del oráculo en una entrada M no utilizada previamente es impredecible. Uno puede imaginarse el oráculo como un contenedor para un gnomo que tira los dados, y registra cuidadosamente los mensajes de entrada y las salidas correspondientes en un libro grande, para que cumpla con su contrato de oráculo. No hay forma de predecir cuál será la próxima salida, ya que el propio gnomo no lo sabe.
Si existe un oráculo aleatorio, entonces la inversión de la función hash ha costado 2 ^ n : para tener un resultado determinado, no hay mejor estrategia que usar mensajes de entrada distintos hasta que uno arroje el valor esperado. Debido a la selección aleatoria uniforme, la probabilidad de éxito es 1 / (2 ^ n) en cada intento, y el número promedio de solicitudes al gnomo que lanza los dados será 2 ^ n . Para las colisiones (encontrar dos entradas distintas que producen el mismo valor hash), el costo es aproximadamente * 1.4 * 2 ^ (n / 2) * (en términos generales, con * 1.4 * 2 ^ (n / 2) * salidas, podemos ensamble aproximadamente 2 ^ n pares de salida, cada uno con una probabilidad de 1 / (2 ^ n) de coincidencia, es decir, que tenga dos entradas distintas que tengan la misma salida). Estos son los mejores que se pueden hacer con un oráculo al azar.
Por lo tanto, buscamos funciones hash que sean tan buenas como un oráculo aleatorio: deben mezclar los datos de entrada de tal forma que no podamos encontrar una colisión de manera más eficiente que lo que costaría invocar simplemente la función 2 ^ (n / 2 ) veces La pesadilla de la función hash es la estructura matemática, es decir, atajos que le permiten al atacante ver el estado interno de la función hash (que es grande, al menos n bits) como una variación de un objeto matemático que vive en un espacio mucho más corto. 30 años de investigación pública sobre sistemas de encriptación simétrica han producido toda una parafernalia de nociones y herramientas (difusión, avalanchas, diferenciales, linealidad ...) que pueden aplicarse. En resumen, sin embargo, es que no tenemos pruebas de que un oráculo aleatorio pueda existir realmente. Queremos una función hash que no pueda ser atacada. Lo que tenemos son candidatos a función hash, para los cuales no se conoce ningún ataque en la actualidad, y, algo mejor, tenemos algunas funciones para las cuales se puede probar que algunos tipos de ataques no funcionan.
Todavía hay algo de investigación por hacer.
Piense en un hash realmente básico: para la cadena de entrada, devuelva la suma de los valores ASCII de cada carácter.
hash( ''abc'' ) = ascii(''a'')+ascii(''b'')+ascii(''c'')
= 97 + 98 + 99
= 294
Ahora, dado el valor hash de 294, ¿puedes decir cuál fue la cadena original? Obviamente no, porque ''abc'' y ''cba'' (y un sinnúmero de otros) dan el mismo valor hash.
Las funciones hash criptográficas funcionan de la misma manera, excepto que obviamente el algoritmo es mucho más complejo. Siempre habrá colisiones, pero si conoce hashes de cadena s para h , entonces debería ser muy difícil ("inviable computacionalmente") construir otra cadena que también se haya desplazado a h .
Un hash es una codificación (muy) con pérdida.
Para darle un ejemplo más simple, imagine una codificación ficticia de 2 letras de una palabra de 5 letras llamada codificación X. El algoritmo para la codificación X es simple: tome la primera y la última letra de la palabra.
Asi que,
X-encode( SAUCE ) = SE
X-encode( BLOCK ) = BK
Claramente, no puede reconstruir SAUCE a partir de su codificación SE (suponiendo que nuestro rango de posibles entradas sean todas palabras de 5 letras). La palabra podría fácilmente ser ESPACIO.
Como un aparte, el hecho de que SAUCE y SPACE producen SE como una codificación se llama colisión , y se puede ver que la ecocodificación X no sería muy buena. :)
formación
Con algunos entrecerrar los ojos, los arreglos asociativos se parecen mucho a los hashes. Las principales diferencias fueron la falta del símbolo% en los nombres hash, y que uno solo podía asignarles una clave a la vez. Por lo tanto, uno diría $foo{''key''} = 1; , pero solo @keys = keys(foo); . Las funciones familiares como cada una, las claves y los valores funcionaban como lo hacen ahora (y se agregó eliminar en Perl 2).
Perl 3 tenía tres tipos de datos completos: tenía el símbolo% en los nombres de hash, permitía asignar un hash entero a la vez y agregaba dbmopen (ahora obsoleto a favor de empate). Perl 4 usó claves hash separadas por comas para emular matrices multidimensionales (que ahora se manejan mejor con referencias de matriz).
Perl 5 dio el salto gigante de referirse a matrices asociativas como hashes. (Hasta donde yo sé, es el primer idioma que se ha referido a la estructura de datos, en lugar de "tabla hash" o algo similar). Irónicamente, también movió el código relevante de hash.c a hv.c.
Nomenclatura
Los diccionarios, como se explicó anteriormente, son colecciones desordenadas de valores indexados por claves únicas. A veces se llaman matrices asociativas o mapas. Se pueden implementar de varias maneras, una de las cuales es mediante el uso de una estructura de datos conocida como tabla hash (y esto es a lo que Perl se refiere como hash).
El uso de Perl del término "hash" es la fuente de una posible confusión, porque el resultado de una función hash también se denomina hash (especialmente en contextos criptográficos) y porque las tablas hash no suelen denominarse hash en ningún otro lado.
Para estar seguro, consulte la estructura de datos como una tabla hash, y use el término "hash" solo en contextos obvios y específicos de Perl.