Funcion Hash

Se ha sugerido que este artículo o sección sea fusionado con función hash (discusión). Una vez que hayas realizado la fusión de artículos, pide la fusión de historiales aquí.

Las funciones de hash de una vía (one-way) son una construcción criptográfica empleada en muchas aplicaciones. Son usadas junto con los algoritmos de clave pública para cifrado y firma digital.

Son usadas en la verificación de integridad, en autenticación. Conforman aplicaciones de muchos protocolos diferentes. Mucho más que los algoritmos de cifrado, las funciones de hashing de una vía son los verdaderos caballos de trabajo de la criptografía moderna.

En 1990, Ron Rivest (la R de RSA) inventó la función hash MD4. En 1992, mejoró el MD4 y desarrolló otra función hash: MD5. En 1993, la National Security Agency (organismo dependiente del gobierno de EE.UU.) publicó una función hash muy similar al MD5, llamada SHA (Secure Hash Algorithm). Cuando, en 1995, se descubrieron debilidades, la NSA hizo cambios al SHA. El nuevo algoritmo fue llamado SHA-1. Hoy la función más popular de hash es SHA-1.

Las funciones de hash de una vía deben tener dos propiedades:

  1. Ser de una sola vía. Esto significa que es fácil tomar un mensaje y computarlo en el valor del hash, pero es imposible
     (o dificultar mucho) tomar el valor del hash y recrear el mensaje original.
  
  2. Estar libres de colisiones. Quiere decir que es imposible encontrar dos mensajes que generen un digesto del mismo valor. 

Quebrar una función hash significa mostrar que cada una o ambas de estas propiedades no son ciertas.

En febrero del 2005, tres criptógrafos chinos mostraron que el SHA-1 no está libre de colisiones. Esto es: desarrollaron un algoritmo para encontrar las colisiones más rápido que la fuerza bruta.

SHA-1 produce un digesto de 160-bit. Cada mensaje “hasheado” genera un número de 160-bit. Teniendo que hay infinito número de mensajes que se resumen en cada valor posible, hay infinito número de posibles colisiones. Pero debido a que el número de posibles digestos es también muy grande, la posibilidad de encontrar uno por azar es increíblemente pequeña (uno en 2**80, para ser exactos). Si se hace hashing de 2**80 mensajes aleatorios, podrá encontrar un par cuyo digesto es el mismo valor. Esta es la forma en que por “fuerza bruta” se encuentran las colisiones, y dependen únicamente de la longitud del valor del hash. "Quebrar" la función hash significa contar con la posibilidad de encontrar colisiones más rápido que eso.

Ellos encontraron colisiones en el SHA-1 en 2**69 cálculos, cerca de 2.000 veces más rápido que la fuerza bruta. Ahora, esto es justo en el lejano borde de las facilidades de la actual teccnología. Dos cálculos masivos comprables ilustrarán este punto.

En 1999, un grupo de criptógrafos construyeron un DES cracker. Tenía la posibilidad de ejecutar 2**56 operaciones DES en 56 horas. El costo para construir la máquina fue de $ 250.000(dólares estadounidenses), los duplicados podrían haber sido hechos por 50 -75 mil dólares. Extrapolando esta máquina empleando la ley de Moore, una máquina similar construida hoy podría ejecutar 2**60 cálculos en 56 horas, y 2**69 cálculos en 3,25 años. O una máquina que cueste $25 millones - $38 millones podría ejecutar 2**69 cálculos en las mismas 56 horas.

Del lado del software, la comparación es una búsqueda de una clave de 2**64. Un artículo lo puso de esta forma en el 2002: "En el curso de la competencia, alrededor de 331.252 usuarios participantes permitieron que sus ciclos de procesador sin uso fuese empleados para descubrir la llave. Después de 1.757 días (4,81 años), un participante en Japón descubrió la llave ganadora." La ley de Moore indica que hoy este cálculo debería llevar un cuarto de su tiempo -- o habría requerido un cuarto del número de computadoras es decir hoy un cálculo de 2**69 debería tomar ocho veces más tiempo o requerir ocho veces más computadoras.

• El contenido de este artículo incorpora material de una entrada de la Enciclopedia Libre Universal, publicada en español bajo la licencia Creative Commons Compartir-Igual 3.0.