Funciones de Hash Criptograficas

Son pares de algoritmos:

• Gen: $s\leftarrow S$
• Hash: $h=H^s(m)\in \{0,1{\}}^L$, donde $L$ es la longitud del hash

Una diferencia importante es que $s$ no es una clave, simplemente es un selector. En muchas implementaciones $S=\{s_0\}$ (solo hay una función de hash en una familia). Se las suele llamar funciones de resumen, y son análogas a los MACs pero sin clave, por lo que funcionan como etiquetadores universales.

Se denomina colisión cuando $x\ne x^{\prime }$ pero $h(x)=h(x^{\prime })$. Si hay $n+1$ mensajes y $n$ valores de salida, existe al menos una colisión.

Propiedades

Resistencia a preimagenes: Para todo $y$, es computacionalmente imposible hallar $x/h(x)=y$ Resistencia a segundas imagenes: Para todo $x$, es computacionalmente imposible hallar $x\ne x/h(x^{\prime })=h(x)$ Resistencia a colisiones: Es computacionalmente imposible hallar $x,x^{\prime }/h(x)=h(x^{\prime })$ y $x\ne x^{\prime }$

Modelo General Iterativo

Es un modelo propuesto por merkle en 1989 que permite generar una función de hash. Es utilizado por muchas funciones #todo Revisar la clase donde se dio y rellenar.

En el paso de preprocesamiento, se ajusta el tamaño del mensaje, y se agrega un bloque con el tamaño original. Luego, se utiliza una función de compresión, que es similar al hash pero opera sobre bloques pequeños.

NOTE

La seguridad está dada por la función de compresión

Ejemplos de Funciones

• MD5
  • Entrada: Secuencia de hasta $2^{64}$ bits
  • Salida: Secuencia de 128 bits
  • Aplicación iterativa
  • Quebrada
• SHA-1
  • Entrada: Secuencia de hasta $2^{64}$ bits
  • Salida: Secuencia de 160 bits
  • Aplicación iterativa
  • Construida sobre la base de MD5
• SHA-2/256
  • Salida: 256 bits
• SHA-3/256-512
  • Fue recientemente seleccionada, antes era conocida como Keccak
  • Esta basada en un nuevo modelo llamado esponja

Funciones de Hash y MACs

Es posible construir un MAC a partir de una función de Hash. Dado $H(x)$ una función de hash libre de colisiones, la función $HMA{C}_k(x)$ es infalsificable (pasa la prueba MAC-Forge), donde $HMA{C}_k(x)$:

• GEN: $k\leftarrow K,s\leftarrow S$
• MAC: $t=H^s((k\oplus \text{opad})||H^s((k\oplus \text{ipad})||m))$, donde $\text{opad}=0x36\dots 36$ y $\text{ipad}=0x5c5c\dots 5c$.

El valor de $\text{ipad}$ y $\text{opad}$ no importa, siempre y cuando sean diferentes.

Privacidad e Integridad

Hay tres formas posibles de cifrar y autentificar un mensaje:

• Cifrar y autentificar: $c\leftarrow {\text{Enc}}_{k1}(m)$, $t\leftarrow {\text{Mac}}_{k2}(m)$
• Autentificar, luego cifrar: $t\leftarrow {\text{Mac}}_{k2}(m)$, $c\leftarrow {\text{Enc}}_{k1}(m||t)$
• Cifrar, luego autentificar: $c\leftarrow {\text{Enc}}_{k1}(m||t)$, $t\leftarrow {\text{Mac}}_{k2}(c)$

De estas tres formas, la única que esta garantizada que es segura es “Cifrar, luego Autentificar”. El resto depende de las primitivas criptográficas utilizadas, y requiere de un análisis complejo.