iniqua

Colisiones SHA-1 en 15 minutos, ¿posible?…

La debilidad de Sha1:

¿ Cuánto tiempo tardaríamos en encontrar una colisión con un PC?, ¿y con una "Tesla" de Nvidia?, ¿ y con una Botnet?

A partir de la noticia del descubrimiento de los investigadores australianos en el cálculo de la complejidad de una colisión de SHA1 (Noticia en Hispasec), vamos ha hacer unos cuantos números:

1. Suponiendo que usamos el framework de Nvidia, CUDA. Que usamos el software, por ejemplo, "Extreme GPU Bruteforcer" (http://www.insidepro.com/eng/egb.shtml). Fiándonos de las medidas de rendimiento que tienen publicadas en la web, con una NVIDIA GeForce 8800GS pueden romper 70 millones de claves sha1 por segundo.
2. Según el nuevo análisis de los investigadores australianos con 2^52 combinaciones, en el peor de los casos, podemos encontrar una colisión. Por tanto tenemos:
   • 2^52=4503599627370496 combinaciones.
   • Si las dividimos por las combinaciones por segundo: 4503599627370496/70000000=64337138 seg
   • En horas-> 64337138/3600=17872 horas
   • En días-> 17872/24=745 días
   • En años => 2 años!.
3. Supongamos, por el motivo que sea, que tenemos dinero y nos interesa comprar unas cuantas U y enrackarlas: http://www.nvidia.com/object/product_tesla_s1070_us.html
4. Digamos que conseguimos 4, por ejemplo. A 4 GPU por U => 16 GPUs. (y sin tener en cuenta que las GPUs que lleva llegan a tener una capacidad de cálculo, entre todas ellas, de 345 GPLOPS! en aritmética flotante de doble precisión - mucho mayores que con la que el equipo de "Extreme GPU Bruteforcer" hizo las pruebas de rendimiento), por tanto:
   • Días que nos quedan: 745 días/ 16 = 46 días.
5. También podríamos contemplar el tema de una Botnet. Supongamos que tenemos una botnet de 100000 ordenadores (bastantes pocos), todos ellos con una Nvidia. Pongamos que no todos tienen el modelo de tarjeta de la medida de rendimiento mencionada en el primer punto sino, como media, tienen un modelo inferior. Supongamos que, aproximadamente, a efectos de cantidad de cálculos, se puede simular un cantidad de 80000 PCs con la tarjeta del primer punto. Por tanto, con esta botnet se tardaría en encontrar una colisión:
   • 745/80000=0,009 días, o lo que es lo mismo 13 minutos!!!!. Y esto teniendo en cuanta un botnet muy pequeña.
6. Si tenemos en cuenta la capacidad de cálculo de los "Tesla" de Nvidia el tiempo se reduce a menos de la mitad (esta medida es una estimación "a ojo", pues no puedo contrastarlo con nada, ni tengo medidas de rendimiento).
7. Por tanto en unos 10-20 días podríamos encontrar una colisión (o puede que en menos tiempo), en el peor de los casos.  Y ahora la pregunta:
   ¿A quien le puede interesar gastarse tal cantidad de dinero y tiempo en hacer esto?.
   Respuesta:
   Mafias, departamentos gubernamentales, espionaje industrial, etc etc etc.
8. Conclusión: Además de la obvia, que usemos sha2 512 hasta que sha3 vea la luz..... Que la seguridad yq no es ni un juego de niños, ni cosa de risa. Imaginemos el siguiente escenario:
   Una mafia hace un fake del site de un banco. Encuentra una colision en el certificado (firmado con SHA1). El cliente entraría y ni el navegador daría una alerta ni tan siquiera nosotros comprobando de forma manual el certificado podríamos encontrar que está falsificado.
   Esto es un claro ejemplo de es para tomarselo en serio, puesto que puede llegar a ser muy grave.

Si no estas de acuerdo con los cálculos o con cualquiera de las cosas comentadas deja un comentario.

Un saludo.

Enlaces:

- CUDA Nvidia
- Noticia en Hispasec
- Extreme GPU Bruteforcer
- Tesla Supercomputing de Nvidia

   Enviar articulo en formato PDF a