Función hash

Una función resumen con clave H_K (en inglés keyed hash function) es una función resumen H que tiene un parámetro secreto K que pertenece al conjunto posible de claves ${\displaystyle {\mathcal {K}}}$ y en la que para una entrada x, h_K(x) es el valor resumen de x. Al resto de funciones resumen se dice que son sin clave (en inglés unkeyed hash function).

Calcular el valor hash necesita poco costo (computacional, de memoria, etc.).

Una función hash comprime datos si puede mapear un dominio con datos de longitud muy grande a datos con longitud más pequeña

Se dice que una función resumen es uniforme cuando para una clave elegida aleatoriamente es igualmente probable tener un valor resumen determinado, independientemente de cualquier otro elemento.

Para una función hash H uniforme del tipo H:{0,1}^m→{0,1}ⁿ, es decir:

• Las cadenas están construidas sobre un alfabeto de 2 símbolos (Alfabeto binario)
• El dominio es el conjunto de las cadenas de longitud m
• El rango es el conjunto de las cadenas de longitud n

podemos decir que a cada resumen le corresponde 2^m-n mensajes y que la probabilidad de que dos mensajes den como resultado la misma salida es 2^-n

Para algoritmos de búsqueda, si todas las entradas son igualmente probables, se busca esta propiedad para minimizar el número de colisiones ya que cuantas más colisiones haya, será mayor el tiempo de ejecución de las búsquedas.

En algunas funciones resumen el rango de valores resumen puede ser diferente a lo largo del tiempo. Ejemplo: funciones hash usadas para tablas resumen que necesitan expandirse. En estos casos a la función hash se le debe pasar un parámetro que le permita saber en qué rango se mueve la ejecución para hallar el valor resumen.

Se dice que la función resumen es inyectiva cuando cada dato de entrada se mapea a un valor resumen diferente. En este caso se dice que la función resumen es perfecta. Para que se dé, es necesario que la cardinalidad del conjunto dominio sea inferior o igual a la cardinalidad del conjunto imagen. Normalmente, sólo se dan funciones hash perfectas cuando las entradas están preestablecidas. Ejemplo: mapear los días del año en números del 1 al 366 según el orden de aparición.

Formalización:

${\displaystyle k1\neq k2}$ implica ${\displaystyle h(k1)\neq h(k2)}$

Cuando no se cumple la propiedad de inyectividad se dice que hay colisiones. Hay una colisión cuando ${\displaystyle k1\neq k2}$ y ${\displaystyle h(k1)=h(k2)}$.

Una función hash se dice que es determinista cuando dada una cadena de entrada siempre devuelve el mismo valor hash. Es decir, el valor hash es el resultado de aplicar un algoritmo que opera solo sobre la cadena de entrada. Ejemplos de funciones hash no deterministas son aquellas funciones hash que dependen de parámetros externos, tales como generadores de números pseudoaleatorios o la fecha. Tampoco son deterministas aquellas funciones hash que dependen de la dirección de memoria en la que está almacenada la cadena de entrada. Esa dirección es accidental y no se considera un cambio de la cadena entrada en sí. De hecho puede cambiar dinámicamente durante la propia ejecución del algoritmo de la función hash.

El estudio de este tipo de propiedades es muy útil en el campo de la criptografía para los llamados 'códigos de detección de modificaciones'.

==== Resistencia a la primera preimagen ====[4] Se dice que una función resumen tiene resistencia a la primera preimagen o simplemente que tiene resistencia a preimagen (del inglés preimage-resistant) si, dado un valor hash y, es computacionalmente intratable encontrar x tal que h(x)=y.

[4] Se dice que una función resumen tiene resistencia a la segunda preimagen (en inglés second preimage-resistant) si dado un mensaje x, es computacionalmente intratable encontrar un x', ${\displaystyle x\neq x'}$, tal que h(x)=h(x').

==== Resistencia a colisiones (CRHF) ====[4] Se dice que una función hash tiene resistencia a colisiones o que es resistente a colisiones o CRHF (del inglés Collision Resistant Hash Function) si encontrar un par ${\displaystyle (x,y)}$ con ${\displaystyle y\neq x}$ tal que ${\displaystyle h(x)=h(y)}$ es computacionalmente intratable. Es decir, es difícil encontrar dos entradas que tengan el mismo valor resumen.

Como encontrar una segunda preimagen no puede ser más fácil que encontrar una colisión, entonces la resistencia a colisiones incluye la propiedad de resistencia a la segunda preimagen.[6][7] Por otro lado se puede decir que la mayoría de las funciones resumen CRHF son resistentes a preimagen.[4] La resistencia a colisiones implica resistencia a preimagen para funciones hash con salida aleatoria uniforme.[8]

En algunos trabajos a estas funciones se les llama funciones resumen de un solo sentido fuertes (del inglés strong one way hash function) para resaltar que es fuerte debido a que hay libre elección de los dos valores x e y.

[9] Una función hash se dice que es una función resumen de un solo sentido o que es OWHF (del inglés One-Way Hash Function) si tiene las propiedades de resistencia a preimagen y de resistencia a segunda preimagen. Es decir, es difícil encontrar una entrada cuya hash sea un valor resumen preespecificado.

Observar que es diferente a la definición general que se hace de funciones de un solo sentido:

[4] Una función se dice que es una función de un solo sentido o que es 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 f(x)=y.

La diferencia entre OWHF y OWF es que OWF no requiere que sea función resumen ni que sea resistente a segunda preimagen.

En algunos trabajos a estas funciones se les llama funciones hash de un solo sentido débiles (del inglés weak one way hash function) para resaltar que es débil en contraste con CRHF (que es fuerte) debido a que al cumplir la propiedad de resistencia a segunda preimagen no hay libre elección en la selección del valor x, y por tanto del valor h(x), en el que se tiene que producir la colisión.

[10] H es resistente a la casi colisión (en inglés near-colission resistance) si es difícil encontrar dos mensajes ${\displaystyle m}$ y ${\displaystyle m'}$ con ${\displaystyle m\neq m'}$ para las cuales sus imágenes ${\displaystyle H(m)}$ y ${\displaystyle H(m')}$ difieran solamente en unos pocos bits.

[11] Por ejemplo podemos tener una función resistente a colisiones de 256 bits que no es resistente a la casi colisión porque se pueden encontrar casi-colisiones para los 224 bits de más a la izquierda.

Son funciones en las que invirtiendo cierto coste en procesamiento de CPU y memoria es posible encontrar en tiempos razonables dos entradas que produzcan resultados en los que sus bits se parezcan en cierto grado. Por ejemplo que se parezcan en un porcentaje de bits, o más comúnmente que sean iguales es los n-bits más significativos.

Por ejemplo con SHA1 para conseguir una colisión total con fuerza bruta necesitaríamos ${\displaystyle 2^{160}}$ comprobaciones o al menos ${\displaystyle 2^{80}}$ usando la paradoja del cumpleaños. Sin embargo si vamos reduciendo el número de bits más significativos que tienen que coincidir, el número de comprobaciones va bajando paulatinamente.

[12] Una función resumen tiene resistencia a preimágenes parciales (en inglés Partial-preimage resistance) si es difícil encontrar una parte de la preimagen de un valor hash incluso conociendo el resto de la preimagen. Es decir, se debe recurrir a la fuerza bruta: si se desconocen t bits de la preimagen, se deben realizar en promedio 2^n-t operaciones de hash encontrarlo.

A una función resumen resistente a preimágenes parciales también se le dice que es localmente de un solo sentido (del inglés local one-wayness).

En algunas aplicaciones, las cadenas de entrada, depende la entrada uno nunca sabe 1313 pueden contener características que son irrelevantes cuando comparamos las cadenas. Por ejemplo en algunas aplicaciones las mayúsculas pueden ser irrelevantes. Por tanto para hallar el valor hash es interesante ignorar las distinciones no relevantes entre las cadenas de entrada. De esta forma cadenas distintas con diferencias no relevantes, tienen asociados valores hash iguales.

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

En una función resumen se dice que no hay correlación cuando los bits de las cadenas de entrada y los bits de las cadenas de salida no están relacionados, es decir, cuando una modificación minúscula (por ejemplo un bit) en la cadena de entrada ocasiona cambios en el valor hash comparables a un cambio de cualquier otro tipo. Por tanto cualquier cambio en el mensaje original idealmente hace que cada uno de cualquier bit del valor resumen resultante cambie con probabilidad 0.5. Cuando esto sucede (o casi) se dice que se produce un efecto avalancha

En funciones resumen usadas para búsqueda normalmente se buscan funciones tan continuas como sea posible; de forma que entradas que difieran un poco deberían tener valores hash similares o iguales. Sin embargo la continuidad no es deseable para funciones resumen usadas para sumas de verificación o funciones criptográficas por evidentes razones.

[13] Una función resumen con clave K, ${\displaystyle h_{K}(x)}$ se dice que tiene resistencia a la computación de nuevos valores hash (en inglés Computation-resistance) si a partir de un rango de pares conocidos ${\displaystyle (x_{i},h_{K}(x_{i}))}$ no puede ser computado para un nuevo dato x ${\displaystyle h_{K}(x)}$ con ${\displaystyle x\neq x_{i}}$ para cualquier i, sin que K sea conocida.

Observar que la propiedad anterior implica que no debería ser posible calcular K a partir de un rango de pares conocidos ${\displaystyle (x_{i},h_{K}(x_{i}))}$. A esta propiedad se la llama propiedad de no recuperación de clave (en inglés key non-recovery).

El estudio de este tipo de propiedades son muy útiles en el campo de la criptografía para los llamados códigos de autenticación de mensajes.

Podríamos imaginarnos un algoritmo probabilístico de tiempo polinomial con dos mensajes codificados en el algoritmo que dan lugar a una colisión para una específica función resumen. El algoritmo simplemente devolvería los dos mensajes que causan la colisión. Crear tal algoritmo puede ser extremadamente difícil, pero una vez construido podría ser ejecutado en tiempo polinomial. Sin embargo, definiendo una familia de funciones resumen como una familia infinita de funciones resumen impide que la búsqueda de este algoritmo tenga éxito para todas las funciones resumen de la familia, porque hay infinitas. Por tanto las familias resumen proporcionan un mecanismo interesante para el estudio y categorización de las funciones resumen respecto a su fortaleza frente a la búsqueda de colisiones por parte de un adversario. Este tipo de estudios es muy útil en el campo de la criptografía para los llamados códigos de detección de modificaciones.

Sea ${\displaystyle D=\Sigma \ ^{l}}$, el dominio de la función, sea ${\displaystyle R=\Sigma \ ^{n}}$ el rango de la función. Sea ${\displaystyle {\mathcal {K}}}$ el conjunto de todas las posibles claves (teóricamente es infinito aunque en la práctica es finito),

Una familia de funciones hash ${\displaystyle {\mathcal {H}}}$ es un conjunto infinito de funciones hash de la forma ${\displaystyle H:{\mathcal {K}}\times \ D\rightarrow \ R}$ (notación equivalente ${\displaystyle H_{K}:D\rightarrow \ R)}$, donde cada función de la familia es indexada por una clave ${\displaystyle K\in {\mathcal {K}}}$ que cumple las siguientes propiedades:

• ${\displaystyle {\mathcal {H}}}$ es accesible, es decir hay un algoritmo probabilístico de tiempo polinomial, que sobre una entrada ${\displaystyle K}$ devuelve una instancia ${\displaystyle H_{K}}$
• ${\displaystyle D}$ es muestreable, es decir, hay un algoritmo probabilístico de tiempo polinomial, que selecciona uniformemente elementos de ${\displaystyle D}$.
• ${\displaystyle H_{K}}$ es computable en tiempo polinomial, es decir, hay un algoritmo de tiempo polinomial (en l) que sobre una entrada ${\displaystyle M\in D}$ computa ${\displaystyle M\in D}$.

Ejemplo: SHA-1 es una sola instancia de función resumen, no una familia. Sin embargo SHA-1 puede ser modificado para construir una familia finita de funciones. M. Bellare y P. Rogaway[15] modificaron SHA-1 de tal forma que la claves especifica las constantes usadas en la cuarta ronda de las funciones. En este caso el tamaño de la clave es de 128 bits y por tanto ${\displaystyle {\mathcal {K}}=\Sigma \ ^{128}}$, ${\displaystyle D=\Sigma \ ^{2^{64}}}$ y ${\displaystyle R=\Sigma \ ^{160*3}}$.

Observar que en la definición de una función resumen el dominio se puede formalizar como ${\displaystyle \Sigma \ ^{*}}$, sin embargo en una función resumen definida como instancia de un elemento de una familia de funciones resumen el dominio es ${\displaystyle \Sigma \ ^{l}}$. Esto es debido a que para que se cumplan las propiedades de seguridad es necesario que el dominio sea muestreado uniformemente en tiempo polinomial. Una familia de funciones ${\displaystyle {\mathcal {H}}}$ puede siempre ser definida con aquel tamaño apropiado para acomodar cualquier mensaje que sea necesario.

De forma informal una familia de funciones es familia de funciones resumen resistente a colisiones, también llamadas CRHF por sus siglas en inglés (Collision Resistant Hash Function), dada una función escogida aleatoriamente de la familia, un adversario es incapaz de obtener una colisión para ella.[16]

[17] Se dice que una familia de funciones resumen es una (t,ε)-familia resumen resistente a colisiones ${\displaystyle {\mathcal {H}}}$ con la forma ${\displaystyle {\mathcal {H}}:\Sigma \ ^{k}\times \;\Sigma \ ^{n}\rightarrow \ \Sigma \ ^{l}}$ con n,l y k enteros positivos y n>=l, que satisfacen la siguiente condición: Sea ${\displaystyle {\mathcal {F}}}$ un buscador de colisiones de cadenas que para una entrada K en el espacio de claves usa tiempo ${\displaystyle \leq \;t}$ y obtiene como salida ${\displaystyle \bot \;}$, un par ${\displaystyle x,x'\in \Sigma \ ^{n}}$ tal que ${\displaystyle {\mathcal {H}}_{K}(x)={\mathcal {H}}_{K}(x')}$. Para cada ${\displaystyle {\mathcal {F}}}$,

${\displaystyle Pr_{K}[{\mathcal {F}}({\mathcal {H}})\neq \ \bot \ ]<\epsilon \ }$.

Observar que la probabilidad es tomada sobre las elecciones aleatorias de ${\displaystyle {\mathcal {F}}}$.

Mirando esta definición se ve que son interesantes aquellas familias que tienen un t/ε suficientemente grande.

Estrictamente hablando hablamos de familias CRHF pero por simplicidad se suele hablar simplemente de CRHF.

La definición no se mete en cómo se eligen las funciones resumen de la familia. Este punto es crucial.[18] En realidad, en cualquier aplicación de funciones resumen resistentes a colisiones, alguna parte P tienen que elegir una función de la familia de forma aleatoria para producir la descripción de la función. Es importante distinguir entre dos casos:

• La elección aleatoria se puede hacer pública (o 'public-coin'). La elección aleatoria puede ser revelada como parte de la descripción de la función.
• La elección aleatoria se tiene que mantener secreta (o 'secret-coin'). La revelación la elección aleatoria realizada puede que permita encontrar colisiones. Por tanto P tiene que mantener secreta la elección después de producir la descripción de la función.

Evidentemente una familia CRHF elegible de forma pública (public-coin) también puede trabajar si uno elige o mantiene la elección de forma privada (secret-coin).

Una función resumen universal es una familia de funciones donde la probabilidad de colisión entre dos textos escogidos es despreciable.[19]

Una k-familia de funciones resumen universal es un conjunto H de funciones ${\displaystyle h:A\to \;B}$ tal que para cada elemento ${\displaystyle x_{1},x_{2},...,x_{k}\in A}$ y todos los (no necesariamente distintos) ${\displaystyle b_{1},b_{2},...,b_{k}\in B}$.

${\displaystyle Pr_{h\in H}[h(x_{1})=b_{1}\land ...\land h(x_{k})=b_{k}]=|B|^{-k}}$

[21] Una familia de funciones resumen ${\displaystyle {\mathcal {H}}}$ es ε-casi universal o ε-AU (del inglés ε-almost universal) si es menor que ε la probabilidad de que dos entradas distintas m,n tengan el mismo valor resumen asociado, estando la función resumen elegida aleatoriamente entre los miembros de ${\displaystyle {\mathcal {H}}}$. De la definición se percibe que son interesantes aquellas familias que tienen un valor pequeño de ε indicando que el adversario no puede encontrar un par de entradas que producen el mismo valor resumen, para una función resumen elegida aleatoriamente de entre los elementos la familia.

Una familia de funciones resumen universal de un solo sentido, también llamadas UOWHF por sus siglas en inglés (Universal One-Way Hash Function), es una familia de funciones resumen universales donde, elegida una clave K aleatoriamente en el espacio de claves, dada una cadena x con valor resumen h_K(x) es difícil encontrar un x' distinta de x tal que h_K(x)=h_K(x'). Al par (x,x') se le llama par de colisión

[22][23] Se dice que una familia de funciones resumen ${\displaystyle {\mathcal {F'}}}$ es (t,ε)-función resumen universal de un solo sentido (UOWHF) si no existe ningún adversario que en tiempo menor que t pueda ganar el siguiente juego con probabilidad mayor o igual que ε: 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').

El adversario está compuesto por dos algoritmos ${\displaystyle {\mathcal {F'}}=({\mathcal {F'}}_{1},{\mathcal {F'}}_{2})}$.

• ${\displaystyle F'_{1}}$ solo tiene como parámetro de entrada el conjunto de la familia de funciones resumen. Produce como salida x y State. x es el valor resumen objetivo y State es alguna información extra que puede ayudar a A₂ a encontrar la colisión.
• ${\displaystyle F'_{2}}$ tiene como parámetros de entrada K,x y State y produce como salida x'

por tanto

${\displaystyle Pr_{K}[{\mathcal {F'}}({\mathcal {H}})\neq \ \bot \ ]<\epsilon \ }$.

siendo ${\displaystyle \bot \;}$ un par ${\displaystyle (x,x')}$ con ${\displaystyle x\neq x'}$ tal que h_K(x)= h_K(x')

Observar que, al igual que en la definición de (t,ε)-CRHF la probabilidad es tomada sobre las elecciones aleatorias de ${\displaystyle {\mathcal {F'}}}$. La gran diferencia es que aquí la entrada x se fija primero.

Mirando esta definición se ve que son interesantes aquellas familias que tienen un t/ε suficientemente grande.

Una familia UOWHF es una noción más débil que una familia CRHF. En una CRHF, al oponente primero se le da la clave y después ella o él tiene que producir la pareja de entradas que colisiona. Encontrar colisiones para un parámetro fijo de una UOWHF, puede que sea bastante más fácil, pero esto no ayudará a un oponente a violar la seguridad. Simon[25] ha demostrado que existe un oráculo relativo al cual UOWHF existe, pero no CRHF.

[26] Una de las aplicaciones que tienen los punteros hash es que pueden ser utilizados para construir una cadena de bloques (blockchain), mediante la utilización de listas enlazadas.

El primer bloque (bloque 0) de la cadena se conoce como bloque génesis,[27] en el cual se origina la cadena de bloques. A partir del segundo bloque (bloque 1) se almacena un puntero hash al bloque anterior, el valor hash del bloque anterior y la información del bloque actual. Gracias a este mecanismo, es imposible interferir en un bloque de la cadena de bloques sin que los demás se den cuenta.

Para cualquier bloque de la cadena; el bloque i almacenará un puntero hash al boque i-1, el valor hash del bloque i-1 y la información del bloque i.

Solamente es necesario mantener el puntero hash al último bloque de la cadena de bloques.

Entonces, cuando alguien muestra la cadena de bloques completa y afirma que los datos no se han modificado, podemos saber si algún bloque de la cadena fue alterado, ya que es posible recorrer los bloques hacia atrás y verificar todos los valores hash uno por uno.

• Un atacante quiere manipular un bloque de la cadena de bloques, por ejemplo, el bloque 1.
• El atacante cambia el contenido del bloque. Debido a la propiedad de resistencia a colisiones de las funciones hash, no será capaz de encontrar otra información que tenga el mismo valor hash que el anterior. Por tanto, ahora el valor hash del bloque 1 ha cambiado.
• Ahora, tras el cambio, se podría detectar la inconsistencia entre estos datos y el puntero hash del siguiente bloque, a menos que el atacante también cambie dicho puntero hash en el bloque siguiente, bloque 2.
• Si el atacante modifica el puntero hash, estos dos coinciden, pero el contenido del bloque 2 ha cambiado. Esto significa que su valor hash no va a coincidir con el puntero hash del bloque 3, por lo que para que todo sea coherente, será necesario modificar el puntero hash del bloque 3.
• Ocurrirá lo mismo con todos los bloques siguientes.
• Finalmente, el atacante va al puntero hash del último bloque de la cadena de bloques, el cual es un obstáculo para el atacante, ya que nosotros guardamos y recordamos el puntero hash del último bloque. Detectaríamos la inconsistencia.

Si un atacante quiere modificar los datos en cualquier parte de la cadena, debe modificar todos los punteros hash desde el principio para conseguir la coherencia, pero al llegar al puntero hash que guarda el último bloque no podrá manipular el encabezado de la cadena