[uylug-varios] [ssac] SHA-1 collision found...

[Carlos M. Martinez]

Hola Eduardo,

Los hashes siempre tienen colisiones, está en su definición (el hash 
tiene menos bits que los mensajes que se hashean). El tema es *como* 
encontrar una colisión. Dado un archivo, ¿como ‘construyo’ otro 
archivo que tenga el mismo hash que el primero?.

El peor caso es el de fuerza bruta, si el hash tiene h bits, entonces en 
el peor de los casos tendré que probar 2^h casos (en realidad me va a 
alcanzar con probar algo más de 2^(h/2), ya que este problema es igual 
al de la “paradoja del cumpleaños” [1])

Los hashes evolucionan con el tiempo mas o menos de esta forma:

1- período idílico: el algoritmo es nuevo y no se conocen ataques 
mejores que los de fuerza bruta
2- se pierde el amor: aparece alguien (generalmente un chino ;-) ) y 
encuentra un ataque que es un poco mejor (i.e. de menor complejidad) que 
un ataque de fuerza bruta, generalmente solo a nivel teórico
3- se pierde un poco mas el amor: aparece alguien que puede explotar 
esta debilidad teórica para generar una colisión pero a un costo muy 
grande
4- distanciamiento: generar colisiones a medida comienza a ser viable -> 
**este es el momento de abandonar el barco en masa**
5- divorcio: generar colisiones a medida se vuelve práctico

Con lo de ayer SHA-1 está en (3). Llevó 12 años pasar de (2) a (3), 
las primeras debilidades teóricas de SHA-1 se publicaron en 2005. El 
ataque de fuerza bruta en SHA-1 es de 2^80 operaciones, y el primer 
ataque teórico encontrado fue uno de 2^69 en 2005, seguido rápidamente 
de uno de 2^63 [2].

SHA-2 está en (2) con un pié en (3) ya que pertenece a la misma 
familia matemática de algoritmos de hash. SHA-3 está en pleno idilio 
:-)

MD5 esta en (5) desde hace unos años.

Salute!

-Carlos

[1] https://en.wikipedia.org/wiki/Birthday_problem
[2] https://en.wikipedia.org/wiki/SHA-1#Attacks

On 24 Feb 2017, at 19:35, Eduardo Trápani wrote:

>> Supongo que ya lo vieron por todos lados, y ya se sabía que tarde o
>> temprano iba a pasar, pero no deja de ser interesante.
>
> No, yo no sabía. No termino de entender algo, colisiones va a haber
> siempre no, o sea, es un hash. El tema es que uno no las pueda hacer a
> medida.
>
> Pero por lo que veo, tampoco es que ellos hayan encontrado una manera
> simple de hacerlo. Al parecer lleva un montón enorme de recursos.
>
> Si se hubiese dado por casualidad (que hubiese podido pasar), o si lo
> hubiesen resuelto por fuerza bruta, ¿levantaría ese revuelo?
>
> Igual es impresionante el impacto que va a tener algo así de obsoleto
> (desde hace tanto tiempo). Aunque, sin los detalles del algoritmo, 
> capaz
> que para los efectos prácticos, ese hash sigue siendo útil.
>
> Gracias por compartir, Eduardo.
> _______________________________________________
> Uylug-varios mailing list
> Uylug-varios at listas.uylug.org.uy
> http://listas.uylug.org.uy/listinfo.cgi/uylug-varios-uylug.org.uy