AMIGOS PARA SIEMPRE: criptografía - funciones hash criptográficas

colisión de hash es una situación que se produce cuando dos entradas distintas a una función de hash producen la misma salida.

Es matemáticamente imposible que una función de hash carezca de colisiones, ya que el número potencial de posibles entradas es mayor que el número de salidas que puede producir un hash. Sin embargo, las colisiones se producen más frecuentemente en los malos algoritmos. En ciertas aplicaciones especializadas con un relativamente pequeño número de entradas que son conocidas de antemano es posible construir una función de hash perfecta, que se asegura que todas las entradas tengan una salida diferente. Pero en una función en la cual se puede introducir datos de longitud arbitraria y que devuelve un hash de tamaño fijo (como MD5), siempre habrá colisiones, debido a que un hash dado puede pertenecer a un infinito número de entradas.Para un

x

dado, si resulta computacionalmente fácil encontrar un

y \neq x

tal que

H(x) = H(y)

, se habla de una resistencia débil a colisiones. Si resulta computacionalmente difícil encontrar un par

(x, y)

tal que

H(x) = H(y)

, se habla de una resistencia fuerte a colisiones.Una de las propiedades deseables de las funciones de hash criptográficas es que sea computacionalmente imposible que se produzca una colisión. El valor de una función hash puede ser usado para certificar que un texto dado (o cualquier otro dato) no ha sido modificado, publicando el valor firmado de la función de hash si no es factible que se produzca una colisión. En este contexto, factible se refiere a cualquier método capaz de producirla más rápido que un ataque de cumpleaños de fuerza bruta.

El proceso de encontrar dos valores arbitrarios cuyos hashes collisionan se llama ataque de colisiones. El proceso de encontrar un valor arbitrario cuyo hash colisione con otrohash dado se llama ataque preimagen. Un ataque preimagen exitoso es mucho más serio que un ataque de colisiones exitoso.

Hashing Perfecto: Existe una Función de Enumeración que asigna a cada valor del dominio una única posición de memoria. No posee colisiones.
Hashing Puro: La función de Hash puede asignar a dos valores distintos el mismo valor hash. $x_1 \neq x_2$ y $h(x_1) = h(x_2)$ . Estos dos valores reciben el nombre desinónimos. Las estructuras de hashing puros poseen colisiones y en consecuencia se deberán establecer mecanismos para tratar los mismos. Podemos clasificarlos en estructuras cerradas y abiertas y dentro de las abiertas en estáticas y dinámicas:

Cerradas: No utilizan un nuevo espacio en memoria.
Abiertas: Utilizan espacio adicional.

Estática: La estructura principal no crece.
Dinámica: La estructura principal se expande a medida que aumenta la cantidad de elementos.

funciones hash criptográficas a aquellas funciones hash que se utilizan en el área de la criptografía. Este tipo de funciones se caracterizan por cumplir propiedades que las hacen idóneas para su uso en sistemas que confían en la criptografía para dotarse de seguridad. Estas propiedades las hacen resistentes frente ataques maliciosos que intentan romper esa seguridad.

Establecer qué propiedades tiene que cumplir una función hash criptográfica es difícil ya que son usadas en aplicaciones criptográficas muy diversas, y que por tanto requieren propiedades diferentes. Sin embargo en general podemos decir que es necesario que sean deterministas (un mensaje siempre tiene el mismo valor hash) y de bajo coste (para que sean utilizables en la práctica). Además normalmente se suele requerir que sean uniformes y con efecto avalancha con el objetivo de que sea imposible predecir cualquier valor hash a partir de otros valores hash capturados.

Para determinar las propiedades requeridas para asegurar la seguridad es necesario saber cuál es el objetivo principal de la función. Podemos distinguir dos tipos de funciones: las que tienen como objetivo principal verificar la integridad, a las que se llaman Códigos de detección de modificaciones, y las que tienen como objetivo principal la autenticación del origen del mensaje, a las que se llaman Códigos de autenticación de mensajes.³ Estos nombres no son muy correctos ya que estas funciones no soncódigos y además ambos tipos permiten la autenticación de mensajes. Sin embargo son los más ampliamente aceptados.El objetivo de estas funciones es poder detectar si un mensaje ha sido modificado o no. Por tanto permiten la verificación de la integridad del mensaje. Su funcionamiento consiste en calcular el valor hash del mensaje y que este sirva como prueba para una posible verificación de si el mensaje ha sido modificado. A las funciones hash diseñadas con este objetivo se las llama Códigos de detección de modificaciones o MDC ( siglas del inglés Modification Detection Codes)

Para cumplir su objetivo la función hash tiene que cumplir propiedades que la haga resistente frente ataques de adversarios maliciosos cuyo objetivo es que la función no cumpla su cometido. Según la propiedad que se estime necesaria que cumpla se puede decir que hay dos tipos de Códigos de detección de modificaciones: