¿Cómo funcionan las funciones hash unidireccionales trabajo? (Edited)

Question

He leído el artículo de Wikipedia sobre hashes MD5 pero todavía no puedo entender cómo un hash no puede ser "reconstituido" de vuelta al texto original.

Podría alguien explicar a alguien que conoce muy poco acerca de cómo funciona este criptografía? ¿Qué parte de la función hace que sea unidireccional?

Answer 1

Como todo el mundo hasta ahora ha definido simplemente lo que era una función hash, voy a morder.

Una función unidireccional no es sólo una función hash - una función que pierde información - sino un f función para la que, dada una imagen y ( "SE" o 294 en respuestas existentes), es difícil de encontrar un pre-imagen x tal que f(x)=y.

Es por eso que se llaman de una sola vía:. Se puede calcular una imagen pero no se puede encontrar una imagen previa de una imagen dada

Ninguno de la función hash ordinario propuesto hasta ahora en las respuestas existentes tienen esta propiedad. Ninguno de ellos son de un solo sentido funciones hash criptográficas. Por ejemplo, dada "SE", se puede tomar fácilmente la entrada "SXXXE", una entrada con la propiedad de que X-codificación ( "SXXXE") = SE.

No hay funciones unidireccionales "simples". Ellos tienen que mezclar sus entradas tan bien que no sólo no reconoce la entrada en absoluto en la salida, y que no reconoce otra entrada tampoco.

SHA-1 y MD5 solían ser populares funciones de un solo sentido, pero los dos son casi roto (know especialista en cómo crear pre-imágenes para imágenes dadas, o son casi capaz de hacerlo). Hay un concurso en marcha para elegir una nueva norma, que será nombrado SHA 3 .

Un enfoque obvio para invertir una función unidireccional sería para calcular muchas imágenes y mantenerlos en una tabla que asocia a cada imagen la imagen previa que lo produjo. Para que esto sea imposible en la práctica, todas las funciones de un solo sentido tiene una gran salida, al menos 64 bits, pero posiblemente mucho mayor (hasta, por ejemplo, 512 bits).

EDIT: ¿Cómo hacer la mayor parte criptográfica funciones hash de trabajo

lo general, tienen en su núcleo una sola función que transformaciones complicado en un bloque de bits (una de bloques de cifrado ). La función debe ser casi biyectiva (no debe mapear demasiadas secuencias de la misma imagen, ya que causaría debilidades más adelante), pero no tiene que ser exactamente biyectiva. Y esta función se repite un número determinado de veces, lo suficiente como para hacer que la entrada (o cualquier entrada posible) imposible de reconocer.

Tome el ejemplo de madeja , uno de los fuertes candidatos para el contexto SHA-3. Su función núcleo se itera 72 veces. El único número de iteraciones para el que los creadores de los conocimientos función de cómo se relacionan las salidas a veces a algunas entradas es 25. Dicen que tiene un "factor de seguridad" de 2,9.

Answer 2

Piense en un hash muy básico - para la cadena de entrada, devuelve 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 de hash de 294, se puede saber cuál era la cadena original? Obviamente no, porque 'ABC' y 'cba' (y muchos otros) dan el mismo valor hash.

funciones hash criptográficas funciona de la misma manera, excepto que, obviamente, el algoritmo es mucho más compleja. No siempre van a ser las colisiones, pero si usted sabe cadena hash s a h, entonces debería ser muy difícil ( "computacionalmente imposible") a construcción otra cadena que también hashes a h.

Answer 3

Toma de una simple analogía aquí en lugar de una explicación compleja.

Para empezar, vamos a romper el tema en dos partes, las operaciones unidireccionales y hash. ¿Qué es una operación unidireccional y ¿por qué quieres uno?

Uno operaciones manera se llama así porque ellos 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 de módulo no se puede revertir. ¿Por qué es tan importante? Debido a que se desea proporcionar un valor de salida que 1) es difícil de duplicar sin los insumos originales y 2) no proporciona ninguna manera de averiguar las entradas de la salida.

Reversible

Adición

4 + 3 = 7  

Esto puede ser revertida mediante la adopción de la suma y resta de uno de los sumandos

7 - 3 = 4  

Multiplicación

4 * 5 = 20  

Esto puede ser revertido por tomar el producto y dividiendo por uno de los factores

20 / 4 = 5

No reversible

división Modulo :

22 % 7 = 1  

Esto no se puede revertir, porque no hay ninguna operación que se puede hacer para el cociente y el dividendo para reconstituir el divisor (o viceversa).

¿Se puede encontrar una operación de relleno en donde el '?' ¿es?

1  ?  7 = 22  
1  ?  22 = 7

Con eso se dice, las funciones hash unidireccionales tienen la misma calidad matemática como la división de módulo.

¿Por qué es esto importante?

Digamos que te di la llave de un armario en una terminal de autobuses que tiene mil taquillas y preguntado para entregarlo a mi banquero. Siendo el tipo inteligente que eres, por no hablar de sospechoso, que se vería inmediatamente en la clave para ver qué número de casillero está escrito en la tecla. Sabiendo esto, he hecho algunas cosas tortuosas; primero encontré dos números que cuando se divide usando la división de módulo me da un número en el intervalo entre 1 y 1.000, segunda Borré el número original y escrito en él el divisor del par de números, segundo elegí un terminal de autobuses que tiene una custodiar la protección de los armarios de malhechores sólo dejar que la gente trata de un armario de un día con su llave, tercero el banquero ya conoce el dividendo por lo que cuando se pone la llave que puede hacer los cálculos y averiguar el resto y saber qué armario para abrir.

Si decido los operandos sabiamente que puede acercarse a una relación de uno a uno entre el cociente y el dividendo que las fuerzas conocer cada casillero porque la respuesta diferenciales de los resultados de las posibles entradas en el rango de números deseados , las taquillas disponibles en el terminal. Básicamente, esto significa que no puede adquirir ningún conocimiento sobre el resto incluso si conoce uno de los operandos.

Por lo tanto, ahora puede 'confianza' que entregar la llave a su legítimo propietario sin preocuparse de que se puede adivinar fácilmente a qué vestuario pertenece. Claro, usted podría buscar la fuerza bruta todas las taquillas, pero que tomaría casi 3 años, tiempo suficiente para que mi banquero para utilizar la llave y vaciar el armario.

Ver las otras respuestas para más detalles sobre las diferentes funciones de hash.

Answer 4

Aquí hay un ejemplo muy sencillo. Asumo que soy un criptógrafo principio 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. ¿Qué fue mi archivo original?

Obviamente, no hay manera de saber (aunque es probable que podría descubrir con bastante facilidad que mi hash se basa en la longitud del archivo). No hay manera para "reconstituir" mi archivo basado en el hash porque el hash no contiene todo lo que hizo mi archivo.

Answer 5

A hash es una (muy) de codificación con pérdida.

Para darle un ejemplo más simple, imagina una carta ficticia 2-codificación de una palabra de 5 letras llamado el X-codificación. El algoritmo para el X-codificación es simple:. Tome la primera y última letras de la palabra

Por lo tanto,

X-encode( SAUCE ) = SE
X-encode( BLOCK ) = BK

Es evidente que no se puede reconstruir a partir de su codificación SALSA SE (asumiendo nuestra gama de posibles entradas es todas las palabras de 5 letras). La palabra podría ser sólo tan fácilmente ESPACIO.

Como acotación al margen, el hecho de que la salsa y ESPACIO SE ambos productos como la codificación se denomina colisión , y se puede ver que el X-ecoding no haría una muy buena hash. :)

Answer 6

En términos simples, una función hash funciona haciendo una gran maraña de los datos de entrada.

MD5 por ejemplo. Se procesa los datos de entrada por bloques de 512 bits. Cada bloque está dividido en 16 palabras de 32 bits. Hay 64 pasos, cada paso usando una de las palabras de entrada 16. Por lo que cada palabra se usa cuatro veces en el curso del algoritmo. Aquí es donde un wayness proviene de: cualquier bit de entrada se introduce en varios lugares, y entre dos de estas entradas las mezclas de función todos los datos actuales juntos para que cada bit de entrada de la mayoría de los impactos del estado de ejecución de 128 bits. Esto le impide invertir la función o el cálculo de una colisión, mirando sólo una parte de los datos. Usted tiene que mirar todo el 128 bits, y el espacio de bloques de 128 bits es demasiado grande para ser eficiente atravesó.

Ahora MD5 no hace un trabajo bueno en eso, ya que las colisiones de esa función se pueden encontrar. Desde un punto de vista criptógrafo, MD5 es una función de cifrado girada. El procesamiento de un bloque de mensaje M (512 bits) utiliza 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- sabia Además, y 'e' pasa a ser una función de cifrado simétrico (también conocido como un 'cifrado de bloque'), que utiliza M como llave y V como el mensaje a cifrar. De un vistazo más de cerca, E lata es una especie de "red de Feistel extendida", similar a la de bloques de cifrado DES, con cuatro cuartos en lugar de dos mitades. Los detalles no son importantes aquí; mi punto es que lo que hace un "buen" función de control, entre las funciones de hash que utilizan esa estructura (llamado "Merkle-Damgard"), es similar a lo que hace un cifrado de bloques "seguro". Los exitosos ataques de colisión en MD5 criptoanálisis diferencial de uso, una herramienta que fue diseñado para atacar cifrados de bloque en el primer lugar.

A partir de un cifrado de bloques bien a una función de hash buena, hay un paso que es no ser despedido. Con la estructura Merkle-Damgard, la función hash es seguro si el bloque de cifrado subyacente es resistente a los "ataques claves relacionadas", una característica bastante oscura contra la cual las cifras de bloque raramente se fortaleció debido a que, para el cifrado simétrico, ataques clave relacionados apenas tienen ninguna práctica impacto. Por ejemplo, el cifrado AES resultó no ser tan resistente a los ataques clave relacionados como podría ser deseado, y esto no provocó pánico general. Esa resistencia no era parte de las propiedades que se buscaron para cuando se diseñó AES. Simplemente evita que dan vuelta a la AES en una función hash. Hay una función hash llamado Bañera de hidromasaje, que se basa en un derivado de Rijndael, "Rijndael" es el nombre inicial de lo que se convirtió en la AES; Bañera de hidromasaje, pero se encarga de modificar las partes de Rijndael que son débiles a los ataques de claves relacionadas.

Además, hay otras estructuras que pueden ser utilizados para la construcción de una función hash. Las funciones estándar actuales (MD5, SHA-1, y la familia "SHA-2", también conocido como SHA-224, SHA-256, SHA-384 y SHA-512) son funciones Merkle-Damgard, pero muchos de los posibles sucesores no lo son. Hay una competición en curso, organizado por el NIST (la organización federal de Estados Unidos que se ocupa de ese tipo de cosas), para seleccionar una nueva función hash estándar, conocido como "SHA-3". Ver esta página para más detalles. En este momento, se han reducido a 14 candidatos a partir de una inicial de 51 (sin contar una docena extra que no pasó la prueba de administración de enviar una presentación completa con código que compila y ejecuta correctamente).

Ahora vamos a echar un vistazo más conceptual. Una función hash seguro debe verse como una oráculo aleatorio : un oráculo es un cuadro negro, que, cuando se les da un mensaje M como entrada, da salida a una respuesta h (M ) que se elige al azar, de manera uniforme, en el espacio de salida (es decir, todos n cadenas -bit si la longitud de salida de la función hash es N ). Si se les da el mismo mensaje M de nuevo como entrada, el oráculo da salida el mismo valor que antes. entrada Aparte de que la restricción, la salida del oráculo en un no utilizado previamente M es impredecible. Uno puede imaginar el oráculo como contenedor de un gnomo que lanza los dados, y cuidadosamente registra los mensajes de entrada y salidas correspondientes en un libro grande, de modo que él cumplirá su contrato oráculo. No hay manera de predecir cómo será la próxima salida será desde el propio gnome no sabe que.

Si existe un oráculo aleatorio, a continuación, invertir la función hash tiene costo 2 ^ n : con el fin de tener una salida dada, no hay mejor estrategia que el uso de mensajes de entrada distintos hasta que uno rendimientos la espera valor. Debido a la selección aleatoria uniforme, probabilidad de éxito es 1 / (2 ^ n) en cada intento, y el número promedio de peticiones al GNOME dados de lanzamiento será 2 ^ n . Para colisiones (encontrar dos entradas diferentes que da el mismo valor hash), el coste es de aproximadamente * 1,4 * 2 ^ (n / 2) * (en términos generales, con * 1.4 * 2 ^ (n / 2) * salidas, podemos montar sobre 2 ^ n pares de salida, cada uno con una probabilidad de 1 / (2 ^ n) de juego, es decir, que tiene dos entradas distintas que tienen la misma salida). Estos son los mejores que se pueden hacer con un oráculo aleatorio.

Por lo tanto, buscamos funciones hash que son tan buenos como un oráculo aleatorio: deben mezclar los datos de entrada de tal manera que no podemos encontrar una colisión más eficiente que lo que costaría simplemente invocar la función 2 ^ (n / 2) veces. La pesadilla de la función hash es estructura matemática, es decir, los accesos directos que permiten que el atacante ver el estado interno función hash (que es grande, por lo menos n bits) como una variación de un objeto matemático que vive en una espacio mucho más corto. 30 años de investigación pública en los sistemas de cifrado simétrico han producido toda una parafernalia de las nociones y herramientas (difusión, avalancha, diferenciales, linealidad ...) que se pueden aplicar. La línea de fondo, sin embargo, es que no tenemos ninguna prueba de que un oráculo aleatorio puede existir realmente. We queremos una función hash que no puede ser atacado. Lo que Tienes son candidatos función hash, para los que no ataque está en conocido , y, un poco mejor, tenemos algunas funciones para las que algunos tipos de ataque puede ser demostrado que no trabajo.

Todavía hay algunas investigaciones que hacer.

Answer 7

array
 Con un poco bizco, matrices asociativas se parecen mucho a los hashes. Las diferencias principales fueron la falta del símbolo% en los nombres de hash, y que sólo se podían asignar a ellos una tecla a la vez. Por lo tanto, se podría decir $foo{'key'} = 1;, pero sólo @keys = keys(foo);. funciones familiares como cada uno, claves y valores trabajados como lo hacen ahora (y de eliminación se añadió en Perl 2).

Perl 3 tenía tres tipos de datos enteros: tenía el símbolo% en los nombres de hash, permitió todo un hash que se asignará a la vez, y ha añadido dbmopen (ahora obsoleto en favor de empate). Perl 4 claves hash separados por comas utilizan para emular matrices multidimensionales (que están ahora mejor manipularse con referencias de matriz).

Perl 5 tomó el gran salto de referirse a las matrices asociativas como hashes. (Por lo que yo sé, es la primera lengua que se han referido a la estructura de datos de este modo, en lugar de "tabla hash" o algo similar.) Irónicamente, también se trasladó el código relevante de hash.c en hv.c.

Nomenclatura
Diccionarios, como se explicó anteriormente, son colecciones de valores desordenados indexados por claves únicas. A veces se llaman matrices asociativas o mapas. Ellos se pueden implementar de varias maneras, una de ellas es el uso de una estructura de datos conocida como una tabla hash (y esto es lo Perl se refiere a como un hash).

El uso de Perl del término "control" es la fuente de cierta confusión potencial, debido a que la salida de una función hash también a veces se llama un hash (especialmente en contextos criptográficos), y porque las tablas hash no se suele llamar hashes en cualquier parte más.

Para estar en el lado seguro, se refieren a la estructura de datos como una tabla hash, y utiliza el término "control" sólo en, contextos Perl-específicos obvias.