Funciones Resumen I – Numerentur.org

Aquí un conjunto de las primeras funciones resumen / hash. Muchas de ellas han sido rotas, otras no, pero se puede ver el interés en crearlas de forma robusta y su importancia.

Funciones Resumen – Hash _{? Pulsar en el nombre de la columna para clasificar.}

Año	Nombre	Autor	Comentario
1.953	Luhn	Hans Peter Luhn	Idea y posteriormente patenta un dispositivo mecánico de mano que tenía como objetivo resolver varios problemas comunes que confirmarían la validez de números de identificación de: cheques bancarios, números de la Seguridad Social, etc. Su función inicial era la protección contra errores accidentales de datos. En la actualidad se sigue utilizando en las tarjetas bancarias y otros documentos de identificación. A partir de esta primera versión, se creó otra que soportaba cadenas de texto no numéricas denominada Luhn mod N. La secuencia subyacente de los cálculos de su primera función se la conoce como el algoritmo del módulo 10. De todas formas, lo importantes es que su idea se convirtió en la base de uno de los algoritmos más importantes de nuestra era, la función resumen / hash como la conocemos hoy.
1.956	Tabla Hash	Arnold I. Dumey	Arnold publica “Indexing for rapid random-access memory” un artículo donde propone que la administración de la memoria sea responsable de proporcionar memoria adicional para una tabla de n celdas, que actúe como gestor para proporcionar la dirección del registro con clave k,(identificador registro = clave) en un bloque de memoria. La dirección en la tabla hash se determina con el siguiente cálculo h:k → h(k) ∈ Z_n {0,1,2,3…n-1} donde k es una clave y D [k] es la dirección del registro.
1.957 – 1.961	CRC	W. Wesley Peterson	Cyclic Redundancy Check. Es un código para la verificación y detección de errores o cambios en la información asociada. La información y el código CRC se transmiten simultáneamente, el receptor vuelve a realizar el cálculo y comprueba la igualdad de los dos CRC, en el caso de que los valores no coincidan, la información ha sido modificada o se ha introducido ruido en la transmisión. El código de verificación CRC tiene una longitud fija y la función que lo genera se usa ocasionalmente como función hash. A lo largo del tiempo se han ido produciendo nuevas versiones de 16, 32 y 64 bits.
1.970	Fletcher	John George Fletcher	Es un algoritmo para calcular una suma de comprobación dependiente de la posición. Su objetivo era proporcionar propiedades de detección de errores similares a los CRC, pero con menor coste computacional. Las versiones son de 4, 8, 16 y 32 bits. La suma de comprobación de Fletcher no puede distinguir entre bloques con todos los bits a 0 y bloques con todos los bits a 1. Por ejemplo, si un bloque de 16 bits cambia de 0x0000 a 0xFFFF, la suma de comprobación sigue siendo la misma.
1.977	Perfect	Renzo Sprugnoli	Publica Perfect hashing functions, un método de ajuste de las funciones hash que permite la recuperación de un elemento en una tabla estática con un único acceso. Muestra dos formas de construir funciones perfectas, es decir, funciones que transforman los elementos de I, en direcciones únicas. Las dos técnicas, “reducción de cociente” y “reducción de resto”, son aplicables a pequeños conjuntos.
1.988	MD2	R.L.Rivest	Message Digest 2 se desarrolló como una función hash para computadoras de 8 bits, con una salida de 128 bits. Los cálculos se realizan en un bloque temporal de 48 bytes más una tabla S-Box de 256 bytes que contiene dígitos al azar del número π (pi). El cálculo implica una permutación de cada byte, 18 veces por cada 16 bytes de entrada. Una vez que todos los bloques han sido procesados, se toma el primer bloque del temporal y se convierte en el valor de hash del mensaje. En 2.004 F. Muller presentó el primer ataque con complejidad temporal de aproximadamente 2¹⁰⁴ , las imágenes previas son siempre de 128 bloques. En 2.005 Lars R. Knudsen y John E. Mathiassen proponen un ataque de complejidad de preimagen de alrededor de 2⁹⁷ , en este caso las preimágenes son de longitud variable y otro de complejidad pseudo-preimagen 2⁹⁵ , donde las preimágenes pueden tener la longitud deseada. Tiene 18 rondas, una salida de 128 bits y fue roto. No se recomienda utilizar MD2, es mucho más lento y menos eficiente que MD4 y MD5.
1.990	SNEFRU	Ralph Merkle	Tiene una salida de 128 o 256 Bits y la función de compresión es de 2, 4 u 8 pases. El mensaje se divide en bloques de 512-(m), m es la longitud del valor de hash. Si la salida es de un valor de 128 bits, entonces los bloques tienen una longitud de 384 bits. Cada pase está compuesto de 64 rondas aleatorias. Parte de su fucionamiento tiene influencias de Khafre. En 1.993 Biham y Shamir demuestran mediante el criptoanálisis diferencial la inseguridad de Snefru-128 de dos pasos. Su ataque encuentra pares de mensajes que tienen el mismo valor en 2^28,5 operaciones de tres pasos y 2^44,5 para cuatro pasos. Un ataque de cumpleaños lleva 2⁶⁴ operaciones.
1.990	N-HASH	Nippon T.T. Akihiro Shimizu y Shoji Miyaguchi	Tiene un tamaño de 128 Bits. Está basado en la función de ronda de FEAL que también desarrollaron Shimizu y Miyaguchi. El mensaje se divide en bloques de 128 bits y cada bloque se combina con el valor hash calculado hasta el momento. Utiliza una función de compresión denominada “g”, que inicialmente contenía ocho rondas, cada una de las cuales utiliza la función F, similar a la utilizada en FEAL. Bert den Boer descubrió una forma de producir colisiones en la función de ronda y E. Biham – A.Shamir también lo rompieron utilizando el criptoanálisis diferencial en 1.991.
1.990	Pearson	Peter K. Pearson	Función diseñada, inicialmente, para procesadores de 8 bits. Su implementación computacional es fácil y corta, necesita una tabla T con permutaciones de valores de 0 a 255 con longitud de 256 bytes y una entrada de C caracteres. El algoritmo que Pearson propone es el siguiente: h[0] := 0 ; for i in 1..n loop h[i] :– T [ h[i-1] xor C[i] ] ; end loop ; return h[n] ;
1990	MD4	R.L.Rivest	Message Digest 4 se desarrolla para sustituir a MD2 y para máquinas de 32 bits. Utiliza 3 rondas, trata bloques de 128 a 512 bits y el tamaño del resumen es de 128 bits. La función de relleno agrega primero un byte con el valor hexadecimal de 0x80 y después completa el tamaño del bloque. Fue el primero que se contruyó usando Merkle-Damgård y ha influido en el desarrollo de MD5, SHA-1 y RIPEMD entre otros. La seguridad es su punto débil: En 1.991 Den Boer y Bosselaers publican las debilidades del algoritmo. El primer ataque de colisión lo publica Hans Dobbertin en 1.996, dijo que podía encontrar colisiones con una probabilidad de 2^-22. En 1.998, H. Dobbertin señala que las dos primeras rondas no tienen una propiedad de una sola vía. En 2.004 Xiaoyun Wang, Dengguo Feng, Xuejia Lai y Hogonbo Yu dicen que su ataque puede encontrar colisiones con una calculadora manual y en 2.005 informan de que su ataque encuentra una colisión con una probabilidad de 2⁻² a 2⁻⁶ y su complejidad es inferior a 2⁸ operaciones MD4. En 2.005 Y. Naito, Y. Sasaki, N. Kunihiro y K. Ohta presentan mejoras en el ataque respecto de las anteriores, encuentra una colisión con complejidad menor a 3 operaciones MD4. En 2.006 M. Schlëaffer y E. Oswald proponen un algoritmo sobre cómo construir rutas diferenciales para el ataque de colisión. Una comparativa de dos ataques similares. Existen más ataques, pero con esto queda demostrado que Rivest se lució con MD4.?
1.990-6	RIPEMD	Proyecto RIPE, Hans Dobbertin, Antoon Bosselaers y Bart Preneel	RACE Integrity Primitives Evaluation Message Digest. Trata bloques de 128 a 320 bits y puede utilizar de 48 a 80 rondas. La primera versión RIPEMD fue publicada en 1.992 como propuesta europea y variante mejorada de MD4 en la cual se basó, cumple con el Criterio Estricto de Avalancha (SAC). En 1.995, Hans Dobbertin describe un ataque contra una versión reducida de RIPEMD en la que se omite la primera o la última ronda de la función de compresión. La versión 160 es mucho más segura que MD5 y tanto como SHA. Es más lento que los dos, pero es preferible en una situación donde la seguridad es la mayor preocupación. Las versiones de 256 y 320 bits disminuyen la posibilidad de colisión accidental y no tienen niveles de seguridad más altos (contra ataques de preimagen) en comparación con las versones de 128 o 160 bits.
1.991	FFT	Claus Schnorr	Es una proposición basada en la transformada discreta de Fourier. J. Daeman, A. Bosselaers, R. Govaerts y J. Vandewalle lo rompieron a finales de 1.991 y en 1.992 T. Baritaud, H. Gilbert y M. Girault indicaron que no estaba libre de colisiones. A partir de aquí Schnorr propuso una versión revisada, FFT-Hash II que se rompió por S. Vaudenay en el mismo año. Schnorr ha seguido trabajando en su mejora pero los resultados en velocidad no han sido exitosos.
1.992	MD5	R.L.Rivest	Message Digest 5. Es una de las funciones más utilizadas en la actualidad y diseñada como mejora de MD4. Procesa los bloques en tamaño de 512 bits, divididos en 16 subbloques de 32 bits. La salida del algoritmo es un conjunto de cuatro bloques de 32 bits, que se concatenan para formar un solo valor hash de 128 bits. La función de relleno agrega primero un byte con el valor hexadecimal de 0x80 y después completa el tamaño del bloque. En 1.993, Bert den Boer y Antoon Bosselaers encontraron una seudo-colisión que está hecha del mismo mensaje con dos conjuntos diferentes de valor inicial. En 1.996 H. Dobbertin también encontró una colisión. En 2.005 Xiaoyun Wang, Dengguo Feng, Xuejia Lai y Hongbo Yu también lo rompieron. Después de estos ataques se la sigue considerando segura. Descarga fuente en Java de MD5
1.992	HAVAL	Yuliang Zheng, Josef Pieprzyk y Jennifer Seberry	Hash of Variable Length. Puede producir salidas de diferentes longitudes, 128, 160, 192, 224 y 256 bits, también es definible el número de rondas (3, 4 o 5) y trata bloques de 1.024 bits. Las características principales son: Es altamente no lineal. Cumple con el Criterio Estricto de Avalancha (SAC), Su código se revisó por última vez en abril de 1.997 para corregir un error detectado por Paulo Barreto. En 2.000 P. R. Kasselman y W T Penzhorn rompen el hash de 128 bits en las últimas rondas. En 2.004 Xiaoyun Wang, Dengguo Feng, Xuejia Lai y Hogonbo Yu publican que existe un error grave en la versión de 128 bits. Dicen: “Rompemos el HAVAL-128 completo con solo 2⁶ cálculos”. Para el resto de versiones aún no se conocen deficiencias. De todas formas se considera más seguro y rápido que MD5.
1.993	Crab	Burt Kaliski y Matt Robshaw	Fue desarrollado para demostrar que las funciones hash podrían usarse para crear un cifrado rápido. Trabaja con bloques de 1.024 bits y es muy similar a MD5.
1.995	Adler	Mark Adler	Es una modificación de la suma de comprobación de Fletcher. Es más rápido que los CRC convencionales. Las versiones son de 8, 16 y 32 bits. En la versión de 32 bits la suma de control se obtiene calculando 2 sumas de 16 bits y después conectando los bits en un único resultado de 32. La primera suma (A) es la suma de todos los bytes más uno, la segunda (B) es el total de todos los valores de cada paso en A. En el inicio A es 1 y B es 0, las sumas se realizan módulo 65.521 y la información se almacena en orden “big-endian”. En 2.001 Jonathan Stone descubrió la debilidad de este sistema cuando se tratan mensajes cortos. Su mensaje fue: “En pocas palabras, el problema es que, para paquetes muy cortos, Adler-32 garantiza una cobertura deficiente de los bits disponibles. No confíe en mi palabra, pregúntele a Mark Adler. :-)”. El problema es que la suma (A) no se ajusta para mensajes cortos. El valor máximo de (A) para un mensaje de 128 bytes es 32.640, que está por debajo del valor 65.521 utilizado por la operación de módulo.
1.995	TIGER	Ross Anderson y Eli Biham	Está desarrollado para plataformas de 64 bits, entrega resúmenes de 128 a 192 bits producidos tras 24 rondas (tres pases de 8) y con bloques de texto en claro de 512 bits. Los valores intermedios, en cada ronda, son almacenados en tres registros de 64 bits denominados a, b y c. No se definen valores de inicialización distintivos; son simplemente prefijos del valor hash total. Valores iniciales: a = 0x0123456789ABCDEF b = 0xFEDCBA9876543210 c = 0xF096A5B4C3B2E187 Las variables y0, y1, …, y7 y z0, z1, …, z7 denotan los valores de x0, x1, …, x7 en los pases segundo y tercero. El último valor intermedio se toma como la salida, está compuesto de los valores iniciales de a, b, c y de los obtenidos en la úiltima ronda. Usa Merkle-Damgård, además de operaciones XOR para realizar la compresión. Tiger2 es una variante en la que utiliza un esquema de relleno agregando primero un byte con el valor hexadecimal de 0x80 como en MD4, MD5 y SHA, en lugar de con el valor hexadecimal de 0x01 como en el caso de Tiger. Las dos variantes son por lo demás idénticas. Una ventaja, es de libre disposición pero su implantación ha sido baja.
1.998	PANAMA	John Daemen y Craig Clapp	Panamá es una herramienta criptográfica que se puede usar como función hash o como cifrador de flujo. Está diseñada para obtener buen rendimiento en arquitecturas de 32 bits que no procesen mensajes cortos. Proporciona una salida de 256 bits. La función de relleno convierte un texto a una longitud múltiplo de 256 agregando un solo “1”, seguido de un número n de 0 bits con 0 ≤ n <256. La parte hash realiza iteraciones “Push” con bloques de mensajes como entrada, donde el estado y el búfer (544 y 8192 bits respectivamente) se pueden actualizar en una iteración. Hay dos modos para la función de iteración: Entrada. Introduce un bloque y no genera ninguna salida. Extracción. No toma ninguna entrada y genera una salida. (Una iteración de extracción en blanco es una iteración de extracción en la que se descarta la salida). Si se han introducido todos los bloques de mensajes, se realizan varias iteraciones de extracción en blanco para permitir que los últimos bloques de mensajes se difundan en el búfer y el estado. A esto le sigue una iteración final de extracción para recuperar el resultado final, el hash. Tiene colisiones que han sido encontradas en 2.001 por Vincent Rijmen, Bart Van Rompay, Bart Preneel y Joos Vandewalle. En 2.007 también se encuentran colisiones por Joan Daemen y Gilles Van Assche.