Función Resumen – Hash

Una función Resumen, Hash o algoritmo de aleatorización, toma un texto de longitud variable (M) produciendo como resultado otro, alfanumérico, de menor tamaño (N) y de longitud fija que lo representa h(M). El resumen de longitud N se construye aplicando la función unidireccional h (.), recursivamente a un valor inicial shN(s) =  h(h(…h(s)…))  (N veces).

 

Función Resumen - Hash

 

Las primeras experiencias prácticas de funciones hash se utilizaron para gestionar una tabla con una estructura de datos que asociaba claves con valores. Su objetivo era la búsqueda eficiente de los datos requeridos, lo hacía generando un hash con la clave que era transformada en un número y a partir de este, se obtenía la información asociada.

 

En 1.953, Hans Peter Luhn propuso una forma de buscar y validar “rápidamente” información y documentos que se transformaría en lo que hoy llamamos función resumen o Hash. A partir de esa fecha se produjo una intensa investigación debido a la importancia que se le había reconocido, nombrar el artículo “Indexing for rapid random-access memory” de Arnold I. Dumey de 1.956, a W.W. Peterson con una aproximación práctica en 1.957, a D. E. Knuth con “The Art of Computer Programming” de 1.973, G. D. Knott con “Hashing Functions” de 1.975, R. Sprugnoli con su “Perfect hashing functions” de 1.977, en la misma fecha a J. Lawrence Carter y  Mark N. Wegman que propusieron “The Universal hash functions” o las definiciones que R. C. Merkle publica en 1.979. Todas estas proposiciones sólo son el principio

 

Características.

Las funciones hash no son reversibles, a partir del resultado o huella digital no se puede obtener el texto origen. La imposibilidad de obtener el mensaje origen a partir del resumen obtenido se puede explicar con la aritmética modular (mod). Computacionalmente deben ser fáciles y rápidas de obtener.

 

Matemáticamente es una ecuación con propiedades específicas para el cifrado de información. Tiene el inconveniente de que dos textos de entrada distintos, pueden dar origen a uno mismo de salida, lo que se denomina colisión, situación inevitable pero asumible para el fin que se persigue. Por otro lado, tener una salida de longitud fija es un complemento de seguridad, si una entrada es de mayor tamaño que otra y produce una salida también mayor, el atacante tendría una pista más para atacar a la función. Cuando se utilizan para criptografía se construyen sobre otras funciones denominadas de compresión ( BU, DB, MP, etc. ) que se construyen en base a cifrados de bloques.

 

Originalmente se utilizaron para obtener las claves de direccionamiento en soporte físico cuando se almacenaba información en las bases de datos, en este caso al hash se le denomina direccionamiento calculado (Tablas Hash) y era una herramienta imprescindible, con posterioridad se han mejorado y adaptado para suministrar integridad y autentificación de mensajes. La mayoría de estas funciones son de dominio público.

Funciones Resumen Hash

Las funciones hash pueden utilizarse como:

  • MDC (Manipulation Detection Code). Sirve para resolver el problema de la integridad de la información, al mensaje se le aplica un MDC y se envía junto con el propio mensaje, al recibirlo el receptor aplica la función hash al mensaje y comprueba que sea igual al hash que se envió antes.
  • MAC (Message Authentication Code). Los MAC sirven para autentificar el origen de los mensajes así como también su integridad, para hacer esto se combina el mensaje M con una clave privada K y se les aplica un hash h (M, K). Se envía el resultado y al llegar a su destino si se comprueba la integridad de la clave privada K, entonces se demuestra que el único origen del mensaje es el que tiene la parte propietaria de la otra clave K.
  • Generadores de números pseudoaleatorios.
  • Funciones de derivación de claves.

En la actualidad se están utilizando mayoritariamente en los criptosistemas de clave pública debido a la necesidad de representar rápidamente el mensaje enviado asegurando su integridad y autenticidad.

 

Funciones Hash Unidireccionales (OWHF-UOWHF).

OWHF (One Way Hash Function) es un grupo de funciones que tienen el mismo rango y el mismo dominio (el dominio es más pequeño que el rango), de modo que cuando seleccionamos al azar una función h de H y un punto x del dominio, es difícil, dados h y x, encontrar un punto x’ ≠ x tal que h(x) = h(x’).

 

En 1.979 Merkle publica su tesis “Secrecy, Authentication and Public Key Systems” en la cual define los requisitos que una función resumen unidireccional debe cumplir. Respecto de las funciones hash comienza diciendo:

 

“Hay muchos casos en los que un campo de datos grande (por ejemplo, 10.000 bits) necesita ser autentificado, pero solo un campo de datos pequeño (por ejemplo, 100 bits) puede ser almacenado o autentificado. A menudo se requiere que no sea viable calcular otros campos de datos grandes con la misma imagen bajo la función hash, dando lugar a la necesidad de una función hash de una única dirección.”

 

Él habla de 10.000 bits, algo que en la actualidad es insignificante, pero lo importante no es eso, son las características que propone:

 

  1. F puede aplicarse a cualquier argumento de cualquier tamaño. F aplicado a más de un argumento (por ejemplo, F (x1, x2)) es equivalente a F aplicado a la concatenación de los argumentos, es decir, F «x1, x2».
  2. F siempre produce una salida de tamaño fijo, que, en aras de la concreción, tomamos como 100 bits.
  3. Dado F y x es fácil calcular F (x).
  4. Dados F y F (x), es computacionalmente imposible determinar x.
  5. Dados F y x, es computacionalmente imposible encontrar una x’ ≠ x tal que F (x) = F (x’).

Las tres primeras son obligatorias para la autenticación de mensajes y firmas digitales. La cuarta, también conocido como resistencia previa a la imagen o propiedad unidireccional, establece que es fácil generar un código de mensaje dado un mensaje pero difícil o imposible generar un mensaje dado el resumen. La quinta, también conocida como Segunda propiedad de resistencia de pre-imagen, garantiza que no se puede encontrar un resumen de mensajes alternativo al mismo resumen que un mensaje dado.

 

En 1.989 Moni Naorand y Moti Yung presentan UOWHF (Universal One Way Hash Functions) donde expone las ideas de una función resumen universal para demostrar que es posible construir esquemas de firma digital seguros basados en funciones unidireccionales. Dicen:

 

“Deje que U contenga un número finito de funciones hash, cada una con la misma probabilidad de ser utilizada. Deje que un algoritmo de tiempo polinomial probabilístico A (A es un adversario de colisión) funcione en dos fases.Inicialmente, A recibe la entrada k y genera un valor x conocido como valor inicial, luego se selecciona una función hash H de la familia U. A recibe entonces H y debe generar y tal que H (x) = H (y). En otras palabras, después de obtener una función hash, intenta encontrar una colisión con el valor inicial. Ahora se llamará a U como una familia de funciones hash universales de una sola vía si, para todos los tiempos polinomiales de A, la probabilidad de que A tenga éxito es insignificante”

 

Propiedades de seguridad de las funciones Hash.

Phillip Rogaway
Rogaway
Thomas Shrimpton
Shrimpton

En 2.004 Phillip Rogaway y Thomas Shrimpton agruparon, en tres grupos de resistencia, las propiedades básicas de seguridad de las funciones hash en criptografía:

 

 

1.Preimagen (Pre, aPre, ePre.), resistencia débil a las colisiones. Debería ser computacionalmente imposible, conocido un menaje M, encontrar otro M’ tal que h(M) = h(M’)Sea H:K×M→Y una familia de funciones hash y sea m un número tal que {0,1} m ⊆ M. Sea A un adversario. Entonces se define:

 

  • Pre (resistencia a preimagen), es la forma de definir cuándo una familia de funciones Hash es una función de un sólo sentido.
  • ePre (resistente a preimagen donde sea), intuye que es imposible encontrar la preimagen en cualquier rango seleccionado.

     Rogaway - Shrimpton
    Modelo Rogaway – Shrimpton

  • aPre (resistente a preimagen siempre), refuerza la definición Pre, en el sentido que se necesita para decir que una función X es de un sólo sentido. Tomando la familia SH1, se piensa en X como una función de esa familia de funciones hash y se desea decir que para esta función en particular de la familia, permanece siendo difícil encontrar una preimagen de un punto aleatorio.

 

 

 

2. Segunda preimagen (Sec, aSec, eSec), resistencia fuerte a las colisiones. Es posible encontrar múltiples definiciones para la resistencia de segunda preimagen, por ejemplo: dado un mensaje M, debería ser difícil encontrar otro M’ diferente con el mismo hash. En cualquier caso, el atacante conoce un punto del dominio M y una descripción de una función hash HK, el trabajo es encontrar una M’ diferente de M tal que H (K, M) = H (K, M).  La denominación de M’ y M es compañeros o socios.

 

Sea H : K × M Y una familia de funciones Hash y sea m un número tal que {0,1} m ⊆ M. Sea A un adversario. Entonces se define:

  • Sec (resistencia a segunda preimagen), es la definición estándar.
  • eSec (resistencia a segunda preimagen donde sea), es difícil de encontrar una pareja para cualquier punto del dominio. Esta noción es llamada también una familia universal de funciones Hash en un sólo sentido (UOWHF), fue definida por M. Naor y M. Yung en 1.989.
  • aSec (resistencia a segunda preimagen siempre), refuerza la definición Sec, en el sentido que se necesita para decir que una función X es resistente a segunda preimagen. Tomando la familia SH1, se piensa en X como una función de esa familia de funciones hash y se desea decir que para esta función en particular de la familia, permanece siendo difícil encontrar una pareja para un punto aleatorio.

 

3. Colisión. (Coll).  El resultado de la función resumen es fijo y pequeño comparado con el texto de entrada, por tanto es imposible que una función hash no tenga colisiones.

Debería ser difícil encontrar dos mensajes diferentes con el mismo hash. Sea H : K × M → Y una familia de funciones Hash y sea A un adversario. Entonces se define:

Si una función hash es resistente a la colisión, también es resistente a segunda preimagen.

 

También apuntan que la resistencia de colisión no garantiza la resistencia de preimagen y la resistencia a la colisión implica una resistencia de las funciones hash de 2ª preimagen.

 

Las propiedades anteriores quedarían solas si no se incluyesen:

  • Resistencia a la colisión cercana. Es computacionalmente difícil encontrar dos entradas diferentes M y M’ que tengan un peso Hamming bajo entre sus valores hash, es decir, h (M) difiere de h (M’) en un número reducido de bits.
  • Resistencia parcial de preimagen. Dado un valor hash, es computacionalmente difícil recuperar cualquier parte del mensaje.
  • No correlación. Los bits de entrada de (M) no deben estar correlacionados con los bits de salida de h (M).
  • Comportamiento aleatorio. La función hash debe tener un comportamiento aleatorio. Es decir, dada una entrada particular M, no debería ser factible predecir ningún bit de salida de h (M) sin aplicar realmente la función h.
  • Naturaleza determinista. La función hash h debe ser determinista, es decir, dada una entrada particular M, la función siempre calcula la misma salida h (M).

Ratio.

La Tasa/Ratio de una función hash iterada describe la relación entre el número de operaciones de cifrado de bloque y la salida. Más precisamente, si n denota la longitud en bits de salida del cifrado de bloque, la tasa representa la relación entre el número de bits procesados de entrada, bits de salida n y las operaciones de cifrado de bloque necesarias para producir estos n bits de salida. En general, el uso de menos operaciones de cifrado en bloque podría dar como resultado un mejor rendimiento general de toda la función hash, pero también conduce a un valor hash más pequeño que a menudo es indeseable. El ratio está expresado por:

donde

|xi longitud en bits del bloque de entrada xi,

s el número de  operaciones de cifrado de bloque

n la longitud de bloque.

 .

Utilización en criptografía.

El diseño de una función criptográfica hash se basa en uno o más cifrados de bloques. Desde finales de los años 1.970 esta metodología se desarrolló para convertirse en el enfoque dominante en el área del diseño de funciones hash y se han estudiado numerosas variantes (S.Hirose, X. Lai, J.L. Massey, B. Mennink, B. Preneel, R. Govaerts, J. Vandewalle, etc.). Sin embargo, estos diseños se caracterizan por el hecho de que la entrada de la clave al cifrado depende de los valores de entrada; esto implica que el programa clave debe ser sólido y que debe ejecutarse para cada cifrado (o para cada segundo cifrado), lo que implica un costo computacional considerable.

Un enfoque alternativo es crear una matriz de claves y restringir el diseño de la función hash para usar el cifrado de bloque solo para esas claves. El uso de cifrados de bloque de clave fija ó alternativamente de permutaciones, genera una ganancia al no ser necesario implementar un cifrado de bloque completo, sino solo un número limitado de instancias del mismo.

 

Ejemplo en Java.

En la actualidad estas funciones se incorporan en muchas y distintas herramientas, el objetivo es simplificar la obtención del resumen que nos interese. Aquí un ejemplo en lenguaje Java:

 

Hash lenguaje Java

 

Rendimientos.

Los rendimientos en velocidad que presentamos son los obtenidos en el proyecto eBASH (ECRYPT Benchmarking of All Submitted Hashes)  sobre las funciones resumen que les han sido enviadas, no todas han querido ser analizadas. El proceso se ha realizado en un Intel Core i3-8121U.

 

Fecha Ciclos / byte
10/01/2019 4.096 bytes 64 bytes 8 bytes
Hash Media Media Media
bash256 5,56 11,78 95,75
bash384 7,20 11,78 95,50
bash512 10,87 22,53 96,75
bblake256 5,77 40,66 266,50
blake256 6,00 13,00 59,75
blake2b 2,94 6,16 49,00
blake2s 4,15 4,09 37,75
blake32 6,19 13,72 61,00
blake512 4,25 9,47 78,50
blake64 4,32 10,50 88,75
bmw256 4,57 14,28 78,25
bmw512 3,09 15,88 127,00
cubehash161 178,53 214,06 466,00
cubehash1616 11,61 47,03 291,25
cubehash162 89,81 125,81 377,75
cubehash1632 6,31 37,56 253,75
cubehash164 45,98 81,75 337,75
cubehash168 22,68 59,09 312,25
cubehash512 5,97 15,41 76,25
cubehash81 90,25 110,66 256,00
cubehash816 5,87 25,62 167,75
cubehash82 45,51 65,62 207,25
cubehash832 3,09 22,94 167,75
cubehash84 22,48 43,00 191,75
cubehash88 11,40 31,19 171,75
echo256 3,29 11,28 90,50
echo512 41,88 84,53 675,75
echosp256 22,52 77,91 623,75
echosp512 32,78 100,00 800,75
edonr256 3,45 9,03 49,25
edonr512 1,83 7,31 58,50
essence224 43,01 88,34 539,00
essence256 43,03 88,16 537,50
essence384 31,64 97,12 782,00
essence512 31,70 98,22 789,00
fsb256 35,10 133,97 1066,25
fugue256 13,54 38,16 213,75
fugue384 19,78 63,38 375,50
fugue512 26,11 91,69 561,50
groestl256 8,51 27,94 161,00
groestl512 11,81 41,31 314,50
hamsi 16,45 21,59 60,00
jh224 13,54 27,66 224,00
jh256 13,51 27,50 222,00
jh384 13,56 27,38 223,00
jh512 13,53 27,47 229,00
k12 2,62 10,03 80,00
keccak 9,14 20,34 167,25
keccakc1024 15,62 20,16 163,50
keccakc256 7,00 20,75 165,25
keccakc256treed2 3,78 37,97 303,50
keccakc448 8,06 21,16 169,00
keccakc512 8,58 20,41 156,75
keccakc512treed2 4,59 38,16 304,50
keccakc768 11,01 20,03 162,25
lane256 20,53 61,84 505,25
lane512 29,55 170,28 1362,25
luffa256 8,46 17,62 76,00
luffa384 8,83 22,75 114,75
luffa512 15,61 39,25 195,75
mcssha4 42,39 87,69 411,25
mcssha5 43,07 128,97 740,50
mcssha6 42,42 88,47 420,00
md4 3,06 7,94 39,00
md5 5,15 11,94 55,25
md6d224 18,62 116,50 931,50
md6d256 20,05 124,97 1000,25
md6d384 25,82 162,09 1297,00
md6d512 31,58 199,22 1594,50
mgrostl256 36,40 113,59 909,50
nasha256 15,03 31,16 130,50
nasha512 15,15 32,19 257,25
rfsb509 12,25 26,62 141,00
ripemd160 12,76 27,50 117,75
round3jh256 15,09 30,09 248,75
round3jh512 15,09 30,12 247,00
sarmal256 5,52 12,16 105,75
sarmal512 6,82 14,78 126,75
sha1 2,29 6,78 37,75
sha224 3,64 9,72 50,00
sha256 3,60 7,69 39,25
sha3224 6,40 14,69 116,75
sha3256 6,68 14,59 118,50
sha3384 8,87 14,72 116,25
sha3512 12,22 14,62 118,75
sha384 5,31 15,16 125,00
sha512 5,32 15,47 126,75
shabal256 5,52 28,66 179,00
shabal512 5,50 27,31 162,75
shake128 5,12 14,75 119,25
shake256 6,68 14,72 119,75
shavite3256 13,64 27,62 118,25
shavite3512 22,77 45,53 363,50
simd256 25,43 53,91 437,75
simd512 16,70 68,56 551,25
skein10241024 6,83 30,12 240,75
skein256256 7,81 13,03 73,00
skein512256 5,41 12,59 101,00
skein512512 5,40 12,47 103,00
tiger 5,62 14,22 66,50
whirlpool 21,91 46,41 197,00