Funciones Resumen I

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 LuhnHans 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 Suma Checksum de Luhn o Leninsigue 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.Tabla Hash

La dirección en la tabla hash se determina con el siguiente cálculo h:k → h(k)  ∈ Zn  {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 PetersonW. 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 FletcherJohn 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 SprugnoliRenzo 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.RivestR.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 2104 , 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 297 , en este caso las preimágenes son de longitud variable y otro de complejidad pseudo-preimagen 295 , 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 MerkleRalph 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 228,5 operaciones de tres pasos y 244,5 para cuatro pasos. Un ataque de cumpleaños lleva 264 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 Esquema de N-Hashdesarrollaron 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, cadafunción F N-HASH 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.RivestR.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−2 a 2−6 y su complejidad es inferior a 28 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.

MD4 Diagrama de colisiones equipo Wang y equipo Yu Sasaki

MD4 Diagrama de colisiones equipo Wang MD4 Diagrama de colisiones equipo Sasaki

 

Existen más ataques, pero con esto queda demostrado que Rivest se lució con MD4.😎

1.990-6 RIPEMD Proyecto RIPE, Hans DobbertinAntoon BosselaersBart PreneelHans 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.RivestR.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

Fuente en Java de MD5 Message Digest 5.

1.992 HAVAL Yuliang Zheng Josef PieprzykJennifer SeberryYuliang 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 26 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 AdlerMark Adler

Es una modificación de la suma de comprobación de Fletcher. Es más rápido que los CRC CRC Adler por lo fácilconvencionales. 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. :-)”.

 

CRC Adler por lo difícil

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 AndersonEli BihamRoss Anderson y Eli Biham Está desarrollado para plataformas de 64 bits, entrega resúmenes de 128 a 192 bits producidos Función de compresión Tigertras 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.