domingo, 19 de agosto de 2007

Buscando colisiones en SHA-1

El algoritmo SHA-1 es uno de los algoritmos de hash más importantes, por ser ampliamente usado en criptografía. Su función como algoritmos de hash, consiste en aceptar una entrada de longitud arbitraria y retornar un resumen (digest) de una longitud fija.

Entre las características principales de los algoritmos de hash destaca la necesidad de que las funciones sean de un solo sentido, es decir, que no se pueda obtener información de los datos origen a partir del resument resultado.
Otra característica importante es la resistencia a las colisiones, pues no deben existir dos entradas que produzcan el mismo resumen resultado. Pero lo cierto es que esta última característica es inalcanzable, desde el momento en que la longitud de la entrada puede ser superior a la de la salida.

Una forma de encontrar colisiones consiste en utilizar el ataque de cumpleaños o birthday attack, aunque este requiere 2^(n/2) operaciones de hash para encontrar una colisión. Impracticable en algoritmos como SHA-1.

Otra forma de hacerlo consiste en usar un ataque dedicado a SHA-1 que intente explotar sus debilidadades. Cierto trabajo de este estilo puede encontrarse en Finding Collisions in the Full SHA-1.


Por otra parte, la Universidad de Graz (Australia) ha puesto en marcha un proyecto dedicado a encontrar colisiones en SHA-1. Para tal propósito usa la plataforma distribuida de software libre BOINC, de la universidad de California en Berkeley. Esta plataforma permite usar los tiempos muertos de proceso para colaborar con el proyecto.

En Kriptopolis, han creado un equipo para participar en la búsqueda de colisiones. Puedes unirte a él descargando el soft de BOINC y siguiento las instrucciones de instalación de Kriptopolis.

2 comentarios:

Anónimo dijo...

Estoy al caso de toda esta operación, pero me gustaría saber cual és su propósito?

Ver que este algoritmo no es muy seguro a causa de que diferentes entradas te pueden dar la misma salida y ello puede causar confusión?

Gracias por explicar lo que es el SHA-1 y lo que significan colisiones... Ni en Kriptópolis lo explicaron... Tu blog es buenísimo! Una pena que se actualice de tanto en tanto!! Almenos la información es de calidad!

Daniel Lerch dijo...

Gracias!

La seguridad de un algoritmo de hash se basa en gran parte en que sea computacionalmente imposible encontrar colisiones.

Imagina que encontramos un algoritmo que, dado un valor hash, permita en un tiempo prudencial encontrar una entrada que de este mismo valor.

Esto podría afectar, por ejemplo, a la descarga de archivos firmados de internet, pues la verificación de la firma no nos garantizaría nada.
Otro uso común afectado podrían ser los passwords que se guardan en las bases de datos en forma de hash.