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\}^∗→\{0,1\}^n$ donde tenemos el conjunto de entrada de longitud indefinida representado como $\{ 0,1\}^*$ y el conjunto de salida de longitud fija $n$ como $\{0,1\}^n$.

Propiedades:

Dada una funcion hash $H:\{0,1\}^∗→\{0,1\}^n$, sean $x,y \in \{0,1\}^*$ 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\left[ \mathcal{A} \text{ encuentra } x , y \in \{0,1\}^* \text{ tal que } x\neq y \text{ y } H(x)=H(y) \right] $$

• 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\left[ x \leftarrow \mathcal{U}(\{0,1\}^*), \text{Dado } H(x) \text{, }\mathcal{A} \text{ encuentra } y \in \{0,1\}^n \text{ tal que } H(x)=H(y) \right]^{(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\left[ x \leftarrow \mathcal{U}(\{0,1\}^), \mathcal{A} \text{ encuentra } y \in \{0,1\}^ \text{ tal que } H(x)=H(y) \right]^{(1)} $$

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

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.