Hash, Secure Hash Algorithm o SHA, Checksum

Hash del español "picar y mezclar".

"Hash function, digest function"

"Funciones picadillo, funciones resumen o funciones de digest"

Son funciones computables mediante un algoritmo.

Resumen datos del conjunto dominio.... o de una cadena...

 Son de rango variable.

Conjunto U de hash: dominio de hash, clave o mensaje, preimagen.

Conjunto M de hash: imágen de función hash, a un elemento M se le llama valor hash o código hash, o hash.

Existen keyed hash function y unkeyed hash function.

Cuando son deterministas, cuando dada una cadena de entrada, se devuelve el mismo valor hash. No son deterministas cuando dependen de parámetros externos. 


La calidad de una función hash depende de:

Bajo costo de memoria.
Comprime datos.
Uniforme: Para un valor hash aleatorio se obtiene un valor hash determinado. A cada resumen o busqueda de datos se tiene que 2^m-n mensajes y una probabilidad de obtener el mismo resultado de salida de 2^-n.

Una función hash es inyectiva cuando un dato de entrada se mapea a un valor hash diferente.

Checksum

Verifica que no haya discrepancias entre los valores obtenidos al hacer una comprobación inicial y otra final tras la transmisión.

Colisión

k1 ≠ k2 y (h)k1 ≠ (h) k2 Cuando no se cumple esta propiedad ocurre una colisión; una colisión ocurre cuando hay dos salidas iguales. 

Resistencia a primera preimágen(preimage-resistant) dado un valor hash y, es computacionalmente intratable encontrar x tal que h(x)=y.
Resistencia a segunda preimágen(second preimage-resistant)  x ≠ x'

Collision Resistant Hash Function  CRHF

Es díficil encontrar dos entradas que tengan el mismo valor hash.

Cuando son resistentes a las colisiónes se dice que son "strong one way hash function" o One-Way Hash Function  OWHF .

One Way Function OWF

Si para cada x del dominio de la función, es fácil computar f(x), pero para todo y del rango de f, es computacionalmente intratable encontrar cualquier x tal que y=f(x).

Referencia: wikipedia.

Near Colission Resistance

Si es díficil encontrar dos mensajes, para los cuales sus imágenes difieran de pocos bits. 

Partial Preimage Resistance

Si es difícil encontrar una parte de la preimagen de un valor hash incluso conociendo el resto de la preimagen.

Con normalización de datos

Para hallar el valor hash es interesante ignorar las distinciones no relevantes entre las cadenas de entrada. 



Continuidad o efecto avalancha

Se dice que una función hash es continua cuando una modificación minúscula (ej un bit) en la cadena de entrada ocasiona pequeños cambios en el valor hash.

Computation-resistance

No debe ser posible encontrar K.

La propiedad que comenta lo imposible de calcular K o la clave,  es key non-recovery. 

Familia de funciones Hash

H es accesible, o K devuelve una instancia Hk.

D es muestreable, o tiene un algoritmo probabílistico de tiempo polinomial que selecciona uniformemente elementos de D. 

Hk es computable en tiempo polinomial, o hay un algoritmo de tiempo polinomial que sobre una entrada M ∈ D computa M ∈ D. 

Universal One-Way Hash Function o UOWHF

El adversario escoge un valor x del Rango, entonces recibe una clave K del espacio de claves escogida de forma aleatoria. El juego se gana si encuentra un x' tal que h_K(x)= h_K(x').

Longitud de bloque

El número de bits de la entrada X (en principio de longitud arbitraria) tiene que ser múltiplo de la longitud de bloque. Para conseguirlo se tiene una regla de padding que alarga la entrada a una longitud aceptable. Normalmente esta regla consiste en añadir al final de la entrada unos símbolos adicionales a los que se llama relleno o padding.

Initial Value

Función de ronda o función de compresión.

Función g es la función de salida. 

Secure Hash Algorithm (SHA)

Un hash permite crear una huella digital, teóricamente única, de un archivo. El SHA es una familia de funciones de hash de cifrado publicadas por el Instituto Nacional de Estándares y Tecnología (NIST). 

SHA-0 y SHA-1 producen una salida de 160 bits o 20 bytes, de un mensaje con un tamaño máximo de 2⁶⁴.  Se basa en principios similares a los del MD4 y MD5.

MD4

Implementa una función criptográfica de hash para el uso en comprobaciones de integridad de mensajes. La longitud del resumen es de 128 bits.

MD5 (Message-Digest Algorithm 5)

Es un algoritmo de reducción criptográfica de 128 bits. Casi siempre se representa como un número de 32 dígitos hexadecimal.

Tiger

El tamaño de la función es de 192 bits, aunque hay versiones de 128 y 169 bits de la misma, llamadas Tiger/128 y Tiger/160, que devuelven versiones truncadas de la versión Tiger/192.


Substitution Box (S-Box)

Toma un número m de bits de entrada y los transforma en n bits de salida(a esto se le conoce como Look up table).


Blowfish


Blowfish usa bloques de 64 bits y claves que van desde los 32 bits hasta 448 bits.