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

Eduardo Trápani etrapani at gmail.com
Fri Feb 24 18:01:32 PST 2017


Preciosamente didáctico. ¡Gracias Carlos!

On 24/02/17 20:04, Carlos M. Martinez wrote:
> 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
> _______________________________________________
> Uylug-varios mailing list
> Uylug-varios at listas.uylug.org.uy
> http://listas.uylug.org.uy/listinfo.cgi/uylug-varios-uylug.org.uy


More information about the Uylug-varios mailing list