El ataque de cumpleaños


De vez en cuando se hace mención en algunos artículos técnicos a que un determinado algoritmo de hash como SHA-1 o MD5 se ha “roto”. En rigor, estos algoritmos no se “rompen” sino que se cuestiona su robustez en determinados supuestos, gracias al avance de las matemáticas.

En particular, en muchos de estos artículos se hace referencia a la “paradoja del cumpleaños”, un clásico de la estadística que se enuncia, más o menos, de la siguiente forma: Suponiendo que la función de probabilidad de nacimientos es uniforme (es decir, que es igualmente probable nacer nacer en un dia que en otro) la probabilidad de que una persona nazca un dia concreto es de 1/365, 25. Sin embargo, si nos planteamos cuantas personas tenemos que meter en una habitación para tener una probabilidad mayor del 50% de que dos de ella compartan cumpleaños, la sorprendente respuesta es 23.  Lo cierto es que por las influencias del clima y de las costumbres, la ditribución de probabilidad de nacimiento no es uniforme  y algunos meses (singularmente los que distan 9 meses de los de verano) computan más nacimientos que otros. De esta forma la probabilidad de que 2 personas en una sala llena de gente cumplan años el mismo dia es bastante alta.

Trasladado a la probabilidad de que dos documentos diferentes en una colección de ellos computen el mismo hash, el valor, con la mayor parte de los algoritmos, es significativamente mayor que 1/(2^numbits).

Si los documentos con los que trabajamos son de tipo estructurado (es decir, solo se pueden modificar campos concretos para que no se afecte su estructura) esta debilidad de los algoritmos no es significativa. Sin embargo, si trabajamos sobre documentos con áreas modificables (por ejemplo, ficheros gráficos o discos duros), la debilidad comienza a ser significativa, ya que un atacante podría modificar de forma ventajosa para el la parte del contenido modificable generando resultados que podrían resultar ser colisiones respecto al valor de hash del documento original.

Es por este motivo por el que surgen proyectos como Binum.

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s