Estas aquiContenido / Debilidad del SHA-1
Debilidad del SHA-1
Por Fernando Acero
Hace unos años investigadores chinos habían logrado reducir la complejidad del algoritmo SHA-1 a 2^69, es decir, habían logrado reducir su complejidad en 2^11 en relación con el ataque de cumpleaños de 2^80, dicho de otro modo, Shandong, Wang, Yin y Yu, durante la "Cripto Conference" de 2004, demostraron que habían debilitado el SHA-1 en un factor de 2048, lo que no es poco.
Ahora, según he podido leer en un boletín de Hispasec, unos investigadores australianos han logrado reducir su complejidad a 2^52, lo que es un logro impresionante, puesto que por cada unidad en la que se reduce el exponente, se reduce la fortaleza del algoritmo en un 50%. Dicho de otro modo, a fecha de hoy podemos decir que el algoritmo SHA-1 se ha debilitado en más de un 99% en relación con su fortaleza inicial derivada del ataque de cumpleaños, lo que es muy significativo, aunque nos parezca que 2^52 es una cifra suficientemente grande...
Si ya en el 2004/2005 se aconsejaba abandonar el SHA-1, con este nuevo avance logrado por los australianos, su sustitución por otros algoritmos más resistentes se hace indispensable. Una posible solución, hasta que se publique el SHA-3, es decir, el algoritmo que está llamado a sustituirlo, sería usar dos algoritmos consecutivos, por ejemplo SHA-1 Y RIPEMD-160, puesto que una colisión en SHA-1 es virtualmente imposible que coincida también en RIPEMD-160. Esta solución de la firma múltiple tiene como ventajas que usa algoritmos disponibles en sistemas criptográficos de todo tipo y no implica un excesiva computación.
Hay que señalar, que los documentos que hayamos firmado usando SHA-1 y que deban tener vigor en el tiempo, puede que no sean seguros dentro de unos meses. Como norma general, deberíamos usar algoritmos criptográficos que estimemos que vayan a ser seguros en un tiempo equivalente a la esperanza de vida de la persona que los utiliza y un 50% más.
Una caída del estándar SHA-1 también afectaría a la seguridad de los certificados digitales, puesto que sería factible generar certificados con el mismo fingerprint que otros, lo que permitiría suplantar la personalidad de personas, o de páginas web.
Hay que señalar, que el e-DNI se han establecido mecanismos que permiten construir el "PAHT" de Certificación (Cadena de Confianza) utilizando SHA-1 o SHA-256, para dar soporte a aquellos sistemas operativos que no contemplan el uso de SHA-256 como algoritmo de "hash" o resumen. Desgraciadamente, este mecanismo que depende del sistema operativo que estamos usando, es transparente al usuario la mayoría de las veces, siendo complicado saber la forma en la que se establece el "path" de confianza, sin embargo el e-DNI siempre usa el inseguro SHA-1 para firmar los documentos, según aparece en la página web oficial del mismo.
También hay que tener en cuenta, que las claves de los e-DNI de los usuarios están firmadas usando SHA-1, lo que puede ser un problema de seguridad a medio y largo plazo y con independencia de la validez en el futuro de los documentos que firmemos, o que hayamos firmado anteriormente, usando el omnipresente algoritmo SHA-1. Sin embargo, las claves raíz y subordinadas del e-DNI, con una vida de 30 y 15 años respectivamente, están firmadas usando SHA-1 y SHA-256, por lo que las podemos considerar seguras en este momento.
Ni que decir que ya he configurado mi GPG para que use la función SHA-256 en la firma de documentos y correos electrónicos, aunque también es cierto que en los correos uso siempre firma doble, GPG y de la FNMT, para que no haya problemas.
"Copyleft 2009 Fernando Acero Martín. Verbatim copying, translation and distribution of this entire article is permitted in any digital medium, provided this notice is preserved"
Versión para imprimir
Buenas,
¿Que ocurre en el caso de dispositivos de red como routers cisco con los que yo trabajo dia a dia y que usan sha-1 y/md5.?
¿Habra actualizacion via IOS a nuevos estandares?
Un saludo
pero creo que lo que se buscan (colisiones de cumpleaños) hacen bastante poco efectivos los ataques contra firmas ya hechas, que serían las que tienes tu generadas en tus routers.
Buscar una colisión directa contra una documento existente (es decir, en tu caso, que el hash generado por una contraseña falsa contra la misma información firmada conincidiera con el de la auténtica) sigue quedando fuera del alcance del ataque.
La vulnerabilidad del SHA-1 vendría, por ejemplo en el caso del eDNI que alguien elaborara una pareja de documentos tal que al firmar tu uno con tu eDNI en un sitio que sólo soportara SHA-1 generara el mismo hash que si hubieras firmado el otro (casi nada, contratas algún servicio y resulta que firmas que les regalas tu casa)
Un algoritmo de hash ha de mantener tres fortalezas:
Resistencia a la preimagen: One Way Hash Function, es decir, dada cualquier imagen, es computacionalmente imposible encontrar un mensaje x tal que h(x)=y. Otra forma como se conoce esta propiedad es que el algoritmo de hash sea de un solo sentido.
Resistencia a 2° preimagen: OWHF: Weak One Way Hash Function. Significa que dado x, es computacionalmente imposible encontrar una x’ tal que h(x)=h(x’). Otra forma de conocer esta propiedad es que el algoritmo de hash sea resistente a una colisión suave.
Resistencia a colisión: CRHF: Strong One Way Hash Function. Significa que es computacionalmente imposible encontrar dos diferentes mensajes x, x’ tal que h(x)=h(x’). Esta propiedad también se conoce como resistencia a colisión fuerte.
Cada una de estas debilidades provoca riesgos distintos, la reducción de la complejidad general del algoritmo afecta a cada una de ellas de forma distinta, por ejemplo si alguien logra una 2ª preimagen, un atacante podría encontrar un mensaje X' tal que h(X') = h(X), y reclamar que el documento firmado no es X sino X'. Es decir, que podría falsificar un documento, o incluso una clave que otro usuario compruebe a través de su fingerprint.
Un saludo, Fernando Acero
Si hablamos del ataque inicial de 2^80, entonces tenemos que la reducción ha sido de 2^28. Esto representa una reducción de 99.999999627%. ¿Es a éste número al que te referías cuando mencionaste que el algoritmo se ha debilitado "más de un 99%"?
Sí, a eso me refería, pero no debemos perder de vista que 2^52 es un número bastante grande.
... como parece. Una firma es tan confiable como lo sea su cadena de certificación (¿path?:-) y el entorno en que se generan las firmas implicadas en ella; es por ello que no basta un algoritmo de hash robusto_que_te_cagas. Imagina por un momento que con tu flamante GPG 1.4.9 generas en la oscuridad de tu dormitorio (lugar seguro donde los haya para estos menesteres) una pareja de claves de 4096 bits para a continuación firmar la clave pública con tu certificado de firma Ceres (RSA de 1024 bits con firma SHA-1, como el del DNIe, vamos), o al revés, o a la vez, da igual. ¿Por qué piensas que este escenario es más seguro que una firma creada en un DNIe, con una "belgian eID card", o con un "Cartão de Cidadão"?. Yo no confiaría en tu firma si tuviera que apostar algo por ella. En tu "cadena de confianza" aparece un certificado autofirmado por alguien que no es una Autoridad de Certificación reconocida... un tal Fernando Acero S.L...
Cuando creas una firma en el interior de un SSCD como el DNIe, si lo haces mediante una aplicación que cumpla con los perfiles de protección certificados Common Criteria que hace poco han publicado los de INTECO, es posible comprobar la cadena de confianza. Un "atacante", "falsificador" o lo que sea, deberá currárselo mucho para que la firma "fake" sea válida pues para ello deberá "tunear" las firmas que han hecho las AC implicadas (raíz e intermedia), no sólo la del titular del DNIe. El destinatario de la firma podrá decidir si se fía de ella en base a dicha cadena de confianza.
Un experimento de laboratorio vale como curiosidad en el ámbito algebraico para tirar por tierra una hipótesis, pero no para anular todos los mecanismos de seguridad redundantes existentes en una PKI moderna. ¡Apañados estaríamos si fuera así!.
Me parece un comentario muy acertado e interesante este que acabas de hacer en relación a los sistemas PKI y las cadenas de certificación, o "path" de certificación tal como lo denominan en la página del e-DNI.
Es cierto lo que dices en relación a las cadenas de confianza, pero también es cierto que hay una cadena, la construida en base al sha-1, que podía llegar estar comprometida en cierto tiempo. No debemos olvidar que esos certificados de los niveles superiores de la cadena tienen una validez de 15 y 30 años para poder ser "tuneados", frente a los 30 meses del "débil" certificado de usuario. Es decir, habría 15 años o 30 años para lograr un certificado de 2048 bits que tuviera el mismo SHA-1 que los originales.
Es evidente que la cadena basada en el SHA-256 no lo estaría por el momento, aunque no debemos olvidar tampoco, que los ataques realizados al SHA-1 le afectan por igual en lo que se refiere a la reducción de su grado de complejidad. De hecho, la NSA recomendó el uso del SHA-2 como solución temporal a la espera de un algoritmo de hash que lo pudiera sustituir, puesto que en el fondo, para muchas aplicaciones de alta seguridad no lo considera seguro.
Es cierto también lo que dics sobre el GPG/PGP, no es comparable con un sistema PKI basado en una AC y una sólida cadena de confianza, ni pretendo que lo sea, pero yo no uso el PGP en lugar de, lo uso de forma concurrente con, lo que es muy interesante y distinto. Por ejemplo, así no es necesario recurrir al intercambio de fingerprints para poder dar por válida mi clave pública PGP, basta con comprobar la firma FMNT de mi mensaje, para lo que solamente se necesita la clave pública del certificado raíz de la FNMT y lo puede realizar cualquier usuario otorgando a mi firma GPG el valor que desee.
Hecho esto, cualquier usuario puede hacer cualquier comprobación cruzada de mi firma GPG/FNMT de cualquier mensaje, siendo prácticamente imposible que una colisión en GPG coincida con otra de la firma basadoa en el certificado de la FNMT y viceversa. Es el certificado de la FNMT el que le da validez al GPG y es el destinatario del mensaje el que decide y otorga esa validez.
También es cierto que en los últimos meses he visto problemas serios en algunos sistemas PKI, por ejemplo, en la construcción de cadenas de confianza basándose en claves públicas embebidas en un PDF que el usuario "acepta" como buenas y cosas por el estilo. Creo recordar que por Kriptópolis hay un comentario muy interesante sobre los problemas para verificar y construir las cadenas de confianza con determinados e-DNI.
Estando de acuerdo con todo lo que dices y considerando que 2^52 es bastante grande, como ya he dicho antes, todos estos avances deberían ser motivo de preocupación y deben ser evaluados en su justa medida. No en vano, las funciones de hash son la "navaja suiza" de la criptografía moderna. Pero no hay que ir demasiado lejos, ya hay ataques efectivos y escenarios contra certificados digitales cuya firma es MD5 y puede que no se tarde mucho en verlos en los basados en SHA-1.
Un saludo, Fernando Acero
Ayer tenía una serie de cosas pendientes y no pude contestar todo lo que quería a este interesante comentario, por lo que aprovecho ahora para hacerlo ya que considero importante introducir algunas matizaciones.
Nos guste o no nos guste, desde el punto de vista más estricto, de acuerdo con los principios básicos de la criptografía moderna y al margen de posibles mecanismos de compensación o de sistemas de seguridad "redundantes" que se quieran introducir, el ciclo de vida de un sistema de firma electrónica debería acabar con la caída del algoritmo de hash que utiliza, puesto que sería el eslabón más débil de la cadena de firma. La seguridad ha de descansar en la fortaleza del algorimo, no en otros mecanismos "compensatorios" de la inseguridad criptográfica principal. Negar lo evidente y retrasar las acciones necesarias para evitar el problema, lo único que logrará es agravarlo seriamente llegando a crear un problema de seguridad global.
En el caso del e-DNI el problema del SHA-1 va más allá del establecimiento de la cadena de confianza, puesto que el certificado de usuario solamente cuenta con una firma basada en SHA-1 para verificar su autenticidad y este dispositivo solamente usa el algoritmo SHA-1 para firmar docimentos o generar evidencias, lo que evidentemente nos lleva a problema grave puesto que no solamente estamos hablando de la cadena de confianza.
Pero también hay señalar, que para mi sorpresa se eligió el SHA-1 para el e-DNI a pesar de que este algoritmo ya se daba por roto en el año 2005 y que el NIST americano dijo en su HASH Workshop de 2005 "señores, no usen el SHA-1 en ningún proyecto nuevo", por lo que nadie puede decir que no se estaba avisado del problema, pero está claro, que el SHA-1 era lo que venía "de serie" en las chips criptográficos más "cool" del momento.
La situación acutal considero que es crítica y más, ante un proyecto de la envergadura del e-DNI y con los plazos de despliegue elevados y unos costes igualmente élevados. ¿Qué pasaría si se entrase en razón y se decidiera sustitur el chip criptográfico del e-DNI por otro que use un algoritmo de hash más seguro?, es más, creo que no debemos ni podemos descartar una caída catastrófica del algoritmo en los próximos meses.
Con el escenario abierto con los problemas de seguridad del SHA-1 no es necesario "tunear" ningún certificado raíz para crear un problema de seguridad en los sistemas basados en este algoritmo, aunque su uso quede restringido a una parte de la cadena de firma. Por ejemplo, basta con generar otro certificado que tenga el mismo hash SHA-1 que uno ya existente y con ello, sería válido para firmar "legalmente" a nombre de esa persona y generar evidencias electrónicas en su nombre.
Pero no nos centremos en el e-DNI, debemos pensar en que el SHA-1 se usa para todo y en todos sitios, es la "navaja suiza" de la criptografía moderna, es así y eso no lo podemos evitar, por lo que cualquier avance en la ruptura del algoritmo nos debería preocupar y mucho.
Como ya he comentado antes, los problemas de los algoritmos de hash dependen de las "fortalezas" comprometidas y el grado de compromiso de cada una de ellas, por lo que los escenarios que se abren en este momento con la debilidad del SHA-1 son tan diversos como preocupantes.
Pero ¿qué es lo que piensan las Autoridades de Certificación de esto del SHA-1?, bueno, hay un documento que recomiendo leer, aunque ya tiene sus años. Como podremos ver, si antes la sutuación era mala (año 2005), ahora es mucho peor, tras la publicación del trabajo de los australianos.
Ataque SHA-1 [PDF]
Este documento ha sido escrito por ANF-AC, que es una Autoridad de Certificación española y en cuanto a su contenido, solamente no estoy de acuerdo en una cosa, en que la familia SHA-2 no sea vulnerable a los ataques. Desde mi punto de vista, el SHA-2 es tan vulnerable como el SHA-1 a los ataques actuales, sin embargo, al tener un espacio de firmas mayor se puede considerar "seguro" por el momento, por lo que también coincido con lo que dijo la NSA en 2005, "el SHA-2 es una solución temporal al grave problema abierto en el SHA-1".
Es más, como apunta este documento, ¿se está cumpliendo con los Artículos 20.d y 20.e de la Ley de Firma Electrónica o con el 18.b en la situación actual?, es posible que no. Donde la ley no distingue no cabe distinción, la ley no establece matizaciones sobre el "nivel de fortaleza" del algoritmo o sobre la "razonable" seguridad del mismo, se mueve en términos más que absolutos, o es seguro, o no lo es. Pero no pensemos solamente en el cumplimiento actual de ley, pensemos en el cumplimiento a corto o medio plazo, o en la validez demtro de unos meses, o de unos años, de un documento firmado a fecha hoy usando el algoritmo SHA-1.
Un saludo, Fernando Acero
Mirando por Internet me he encontrado con este artículo que habla de la situación real del SHA-1 y pone algunos números encima de la mesa:
Colisiones SHA-1 en 15 minutos, ¿posible?...
El artículo analiza el escenario con hardware específico y usando una botnet, ahora bien, dicho ataque debería explotar los descubrimientos y usar los métodos establecidos por los australianos, o estarísmos en un inalcanzable escenario de fuerza bruta. Hay que señaalar que el hecho de que no se encontrasen colisiones hasta el momento con el proyecto del "Reto SHA-1", no significa que no comiencen a aparecer como churros, si de adapta el proceso de búsqueda al trabajo de los australianos.
Por cierto, en la página de Graz pone:
"May 12, 2009 Project put on hold
Due to lack of progress, this project is put on hold. No new workunits will be generated for the time being."
Aunque los de Graz dicen que el sistema de búsqueda de colisiones estaba optimizado, habría que estudiar si dicha optimización permite un nivel similar al alcanzado por el equipo Chino en su momento, pero puede que estuvieran trabajando en un espacio demasiado grande, confiando en la potencia de la computación distribuida y en la aceptación del proyecto, seguramente en torno a 2^70.
Hay que señalar, que visto lo visto, y ante la ausencia de progresos de este intento de búsqueda de colisiones, podemos tener una falsa sensación de seguridad sobre la fortaleza real del SHA-1, puesto que si alguien establece un sistema de búsqueda distribuida que use el espacio de 2^52 que proclaman los australianos, la cosa cambia de forma radical.
Un saludo, Fernando Acero