Descubierta la primera colisión de SHA-1

Recientemente se ha publicado en el blog de seguridad de Google un artículo donde se demuestra de forma práctica que existen colisiones en el algoritmo SHA-1.

¿Qué es un hash?

Una función hash es una función utilizada para resumir un archivo en una cadena de caracteres, con ello se obtiene un número en teoría único para cada archivo. Para generar hashes SHA1 en nuestro terminal de GNU/Linux podemos usar el siguiente comando:

echo "hola" | sha1sum

El resultado del comando anterior es un checksum SHA-1 de la palabra “hola”, al aplicarle el algoritmo SHA-1, da como resultado la cadena de texto 63bbfea82b8880ed33cdb762aa11fab722a90a24.

¿Qué es una colisión?

Cuando dos archivos distintos tienen la misma firma (checksum) fruto de aplicar el mismo algoritmo hash se conoce como una colisión. Resulta matemáticamente imposible que un algoritmo carezca de colisiones, ya que el número de entradas posibles siempre será mayor al número de hashes posibles generados, no obstante, las colisiones se dan con más frecuencia en algoritmos de menor robustez. Uno de los algoritmo más conocidos vulnerable a colisiones es MD5 y podemos encontrar pruebas de concepto que demuestran esto y librerías como evilize.

¿Qué es SHA-1?

SHA (Secure Hash Algorithm) es un conjunto de funciones criptográficas publicadas por el NIST. La primera versión fue SHA-0, publicada en 1993, dos años más tarde se publicó SHA-1 y posteriormente, en 2001, se publicó SHA-2 formado por las funciones SHA-224, SHA-256, SHA-384 y SHA-512. El último algoritmo en llegar a esta familia es SHA-3 el cual fue seleccionado en 2012.

Desde 2005 se conocen vulnerabilidades teóricas de este algoritmo y en su momento se lograron necesitar un máximo de 269 operaciones para lograr romperlo, unas 2000 veces más rápido que aplicando fuerza bruta que suponía un máximo de 280 operaciones. Más adelante, en 2015, el investigador Marc Stevens publica un paper en el cual describe cómo teóricamente se puede generar una colisión con el algoritmo SHA-1.

Primera colisión

Una investigación fruto de un equipo formado por Google y CWI Amsterdam, han anunciado la primera colisión de SHA-1 bajo el nombre de SHAttered. Podemos encontrar el artículo en el blog de seguridad de Google. Para la implementación de este ataque se han necesitado una gran cantidad de procesadores gráficos trabajando en paralelo. En resumidas cuentas nueve quintillones de operaciones con SHA-1 en total. Aunque a priori estos números nos parezcan una barbaridad, el ataque shattered es unas 100.000 veces más rápido que un ataque de fuerza bruta, que de hecho resulta impracticable.

Para verlo más claro necesitamos unas 110 GPU’s trabajando durante un año para poder realizar este ataque, pero para aplicar fuerza bruta necesitamos unos 12.000.000 procesadores de gráficos funcionando durante un año para llevar a cabo el ataque por completo lo que lo hacía inviable a diferencia de Shattered.

Se ha publicado en el git de Marc Stevens unas librerías para detectar colisiones en SHA-1.

¿En qué afecta todo esto?

Una vez se demuestra que existe una colisión en el algoritmo, se demuestra que éste resulta inseguro ya que al existir la posibilidad que dos archivos distintos tengan la misma firma, el algoritmo no cumple su función para la que ha sido diseñado.

SHA-1 fue etiquetado como obsoleto por el NIST en 2011, y pueden verse afectadas distintas tecnologías que siguen usándolo actualmente como por ejemplo:

  • Firmas de certificado digital
  • Firmas PGP/GPG
  • Firmas de fabricantes de software
  • Actualizaciones de software
  • checksums de imágenes ISO
  • GIT

La recomendación del equipo de investigación es usar algoritmos más seguros como por ejemplo SHA-256 o el novedoso SHA-3. Actualmente Firefox dejó como obsoleto SHA-1 el pasado 24 de Febrero de 2017. Además el navegador Chrome y los archivos enviados a través de Gmail y Google Drive están protegidos ante este tipo de ataques.