Funciones Hash

Una función hash o función digest es un algoritmo determinista que toma como entrada un mensaje de longitud arbitraria y devuelve una salida de tamaño fijo, comúnmente llamada digest o resumen. Se pueden computar de una manera eficiente y los valores de salida están uniformemente distribuidos en el espacio de salida evitando aglomeraciones. Las funciones hash se suelen denotar como

$H:\{0,1{\}}^{\ast }\to \{0,1{\}}^n$ donde tenemos el conjunto de entrada de longitud indefinida representado como

$\{0,1{\}}^{\ast }$ y el conjunto de salida de longitud fija

$n$ como

$\{0,1{\}}^n$.

Propiedades:

Dada una funcion hash

$H:\{0,1{\}}^{\ast }\to \{0,1{\}}^n$, sean

$x,y\in \{0,1{\}}^{\ast }$ se tiene que

• Resistencia a colisiones:
  No se puede encontrar de manera eficiente
  $x$ e
  $y$ distintos tales que
  $H(x)=H(y)$. Es decir que una función
  $H$ es resistente a colisiones si para todo adversario
  $\mathcal{A}$ con tiempo polinomial probabilístico, la siguiente probabilidad es negligible:

$$P[\mathcal{A}\text{ encuentra }x,y\in \{0,1{\}}^{\ast }\text{ tal que }x\ne y\text{ y }H(x)=H(y)]$$

• Resistencia a la preimagen:
  Dado un valor
  $H(x)$, es computacionalmente inviable encontrar una entrada
  $y$ tal que
  $H(x)=H(y)$. Es decir que una función
  $H$ es resistente a preimagen en una sola dirección si para todo adversario con tiempo polinomial probabilístico, la siguiente probabilidad es negligible:

$$P{[x\leftarrow \mathcal{U}(\{0,1{\}}^{\ast }),\text{Dado }H(x)\text{, }\mathcal{A}\text{ encuentra }y\in \{0,1{\}}^n\text{ tal que }H(x)=H(y)]}^{(1)}$$

• Resistencia a la segunda preimagen:
  Dada una entrada

  $x$, no se puede hallar otra entrada
  $y$ distinta de
  $x$ tal que
  $H(x)=H(y)$. Es decir que una función
  $H$ es resistente a segunda preimagen si para todo adversario con tiempo polinomial probabilístico, la siguiente probabilidad es negligible:
  $$P{[x\leftarrow \mathcal{U}(\{0,1{\}}^{\ast }),\mathcal{A}\text{ encuentra }y\in \{0,1{\}}^{\ast }\text{ tal que }H(x)=H(y)]}^{(1)}$$

(1)

$x\leftarrow \mathcal{U}(\{0,1{\}}^{\ast })$ significa que se elige de manera aleatoria con distribucion uniforme un elemento de

$\{0,1{\}}^{\ast }$.

Es importante observar que no toda función hash cumple con estas propiedaes, se le pueden pedir otras propiedades mas o quitar alguna de estas, dependiendo de la literatura. Estas cualidades hacen que las funciones hash sean ideales para proteger la integridad de los datos y verificar la autenticidad en aplicaciones, esquemas y protocolos criptograficos.

Aplicaciones de las funciones hash

Primitivas criptográficas

Las funciones hash juegan un papel fundamental en la criptografía, proporcionando seguridad en varias operaciones:

• **Compromisos (Commitments):** Se utilizan en esquemas de compromiso para garantizar la integridad y confidencialidad de un mensaje.
• Firmas digitales: En esquemas de firmas digitales, las funciones hash se utilizan para generar un resumen compacto de un mensaje antes de firmarlo.
• Contraseñas seguras: En el almacenamiento de contraseñas, no se guarda la contraseña en texto plano, sino su hash. Esto proporciona seguridad adicional en caso de que una base de datos sea comprometida.

Integridad de datos

• Verificación de archivos y documentos: Al calcular el hash de un archivo o documento en el momento de su creación, los usuarios pueden comprobar más tarde si el archivo ha sido alterado. Si el hash del archivo actual coincide con el hash original proporcionado, se garantiza que el archivo no ha sido modificado.
• Cadenas de bloques (blockchain): Las funciones hash son cruciales en la tecnología blockchain para garantizar la inmutabilidad de los datos. Cada bloque de la cadena contiene un hash que depende del bloque anterior, creando una cadena donde cualquier alteración en un bloque afectaría a toda la estructura anterior, lo que permite detectar y prevenir manipulaciones.

Estructuras de datos eficientes

• Árboles de Merkle: Los árboles de Merkle son estructuras de datos que utilizan funciones hash. Cada nodo del árbol contiene un hash, y el hash de cada nodo padre es el resultado de combinar los hashes de sus nodos hijos. Esta estructura se utiliza en sistemas distribuidos, como las blockchains, y para optimizar la verificación de integridad de grandes volúmenes de datos.

Algunas funciones de hash conocidas son:

MD5 (Message Digest Algorithm 5)

• Longitud de salida: 128 bits (16 bytes).
• Descripción: Fue desarrollado en 1991 por Ron Rivest (la R en el algoritmo RSA). Es uno de los primeros algoritmos de hash ampliamente utilizados. Aunque fue popular en su momento, hoy en día se considera inseguro debido a la vulnerabilidad ante colisiones (cuando dos entradas diferentes producen el mismo hash).

SHA-1 (Secure Hash Algorithm 1)

• Longitud de salida: 160 bits (20 bytes).
• Descripción: Diseñado por la NSA y publicado por el NIST en 1993, se usó ampliamente en seguridad informática. Sin embargo, desde 2005 se encontraron vulnerabilidades en el algoritmo, por lo que se considera obsoleto y ha sido reemplazado por versiones más seguras de SHA.

SHA-2 (Secure Hash Algorithm 2)

• Variantes: SHA-224, SHA-256, SHA-384, SHA-512.
• Longitud de salida:
  • SHA-224: 224 bits.
  • SHA-256: 256 bits (32 bytes).
  • SHA-384: 384 bits.
  • SHA-512: 512 bits (64 bytes).
• Descripción: Publicado en 2001 por la NSA, es una familia de algoritmos de hash más seguros que SHA-1. SHA-256 y SHA-512 son los más utilizados en la actualidad, con una mayor longitud de salida, lo que aumenta la resistencia a ataques de colisión y preimagen.

Poseidon

• Descripción: Publicado en 2019 es una nueva función hash que tiene buena cohesión respecto a las pruebas de conocimiento cero. Dado que aprovecha las estructuras algebraicas de los conjuntos con los que se trabaja en el área. Actualmente existen otras actualizaciones propuestas como Poseidon2 como una propuesta más rapida.

Para ganar intuición

En este link tenemos una calculadora de diferentes funciones hash. https://www.fileformat.info/tool/hash.htm

En la siguiente pagina se puede ver de una manera algo gráfica como funciona el algoritmo SHA-256. https://sha256algorithm.com/.

Referencias

https://crypto.stanford.edu/~dabo/cryptobook/BonehShoup_0_6.pdf

https://www.geeksforgeeks.org/hash-functions-and-list-types-of-hash-functions/

https://en.wikipedia.org/wiki/Hash_function

https://eprint.iacr.org/2019/458

https://eprint.iacr.org/2023/323

El SHA-256 de este articulo es 49cba6a2584f7ceed0ef8f76e6e67bf49ef6e62c288c2a9bbdb1a52308d9cf4a