MD5, un juguete al alcance de un portátil

Esto servirá como recordatorio a los que quieran huir de SHA-1: pasarse al MD5 es ir de Guatemala a Guatepeor.

Curiosamente, el gobierno español sigue empeñado en meternos el DNI digital en los bolsillos, sin importarle que las funciones hash tengan problemas:

"Telefónica compite con El Corte Inglés por el concurso del DNI digital

Un mínimo de cuatro grandes grupos de empresas van a concurrir al concurso para la implantación del DNI electrónico en España. El 14 de marzo se cierra el plazo para la admisión de ofertas y ultiman las suyas las alianzas formadas por Telefónica, Indra y Software AG; Accenture, Informática El Corte Inglés y Atos Origin; la pareja de Bull y Siemens, y también sumarán sus fuerzas Page y Telvent."
Noticia en Cinco Días

Y por cierto, ¿alguien sabe en qué ha quedado la ruptura de SHA-1? Lo único que los chinos han soltado es un papelajo de tres páginas en la que dicen haber roto SHA-0 y una versión reducida (menos rondas) de SHA-1. !Aún no han mostrado que SHA-1 está realmente roto!

¿Será un ataque psicológico contra la civilización occidental? Lo mismo han puesto todos sus ordenadores a trabajar para obtener una sola colisión de cumpleaños (sin rupturas ni nada, echándole 2^80 huevos) ... y nos vuelven micos obligándonos a abandonar el SHA-1. Cosa más rara...

Entre los si y las dudas de si fueron rotos o no.. que alguien me recomiende un algoritmo hash que sea considerado "bueno"

Ya hablamos (poco) una vez sobre eso.
http://www.kriptopolis.org/node/378

__
Me interesa el futuro porque es el sitio donde voy a pasar el resto de mi vida.
- Woody Allen

Estos señores, entre los que se encuentra uno de los miembros del equipo chino que comentaba una mejora importante al ataque del cumpleaños para el SHA-1, lo que ha logrado es materializar en un certificado el resultado de una colisión. Hasta este punto, la utilidad para cometer un fraude con el certificado es relativamente baja.

Veamos un poco lo que hay....

Se habla de dos certificados:

MD5Collision.certificate1.cer

y

MD5Collision.certificate2.cer

Además de un certificado de de una entidad de certificación CA:

MD5CollisionCA.cer

Primero importo el certificado de la entidad de certificación a mi adminstrador de certificados del KDE, para poder comprobar la validez de los dos certificados.

El primero, tiene un bloque de clave pública para firmar:

CA:B9:E7:42:C4:B6:26:87:1A:B9:A5:24:84:6B:05:C1:88:95:FB:93
65:E9:A6:9F:48:03:92:FF:2C:3B:3F:79:41:AD:34:06:FF:AD:B4:03
4B:DF:84:7A:4D:37:01:4F:DB:32:83:CB:19:D4:6F:A8:A7:65:C6:B3
F0:16:BF:30:6A:FF:7C:2E:57:73:68:9B:33:19:B8:15:64:AB:E7:F5
B9:CF:66:C5:E4:FE:79:0C:EE:04:7D:36:CC:77:B0:AE:5D:08:7F:30
B5:60:EB:88:72:B3:4D:40:67:78:66:2D:D8:84:64:67:7D:BD:9B:80
98:9E:F2:4F:B8:2E:0E:A3:2B:58:64:AF:33:B8:FE:86:59:B0:94:46
46:99:F4:77:A6:BF:CA:34:8C:23:CF:68:1E:C0:A8:46:A8:B2:7A:29
07:1B:56:3A:13:16:B0:5F:38:27:B8:2F:B1:F9:DE:1F:23:8F:3D:12
AD:0D:DA:A9:7D:DB:CF:CE:EA:D1:09:39:5E:46:E0:18:AE:23:7C:E5
93:55:AC:93:18:72:28:4C:3A:29:3F:E9:11:79:41:A1:AD:52:83:64
A0:68:7A:FF:60:83:B1:4B:00:9D:D9:52:C8:66:CA:43:A0:F4:1A:7D
CE:58:76:C1:6C:B3:46:E9:A7:18:09:1C:EC:3D:57:D9

El segundo:

CA:B9:E7:42:C4:B6:26:87:1A:B9:A5:24:84:6B:05:C1:88:95:FB:13
65:E9:A6:9F:48:03:92:FF:2C:3B:3F:79:41:AD:34:06:FF:AD:B4:03
4B:DF:84:7A:4D:B7:01:4F:DB:32:83:CB:19:D4:6F:A8:A7:65:C6:33
F0:16:BF:30:6A:FF:7C:2E:57:73:68:9B:33:19:B8:15:64:AB:E7:F5
B9:CF:66:45:E4:FE:79:0C:EE:04:7D:36:CC:77:B0:AE:5D:08:7F:30
B5:60:EB:88:72:B3:4D:40:67:F8:65:2D:D8:84:64:67:7D:BD:9B:80
98:9E:F2:CF:B8:2E:0E:A3:2B:58:64:AF:33:B8:FE:86:59:B0:94:46
46:99:F4:77:A6:BF:CA:34:8C:23:CF:68:1E:C0:A8:46:A8:B2:7A:29
07:1B:56:3A:13:16:B0:5F:38:27:B8:2F:B1:F9:DE:1F:23:8F:3D:12
AD:0D:DA:A9:7D:DB:CF:CE:EA:D1:09:39:5E:46:E0:18:AE:23:7C:E5
93:55:AC:93:18:72:28:4C:3A:29:3F:E9:11:79:41:A1:AD:52:83:64
A0:68:7A:FF:60:83:B1:4B:00:9D:D9:52:C8:66:CA:43:A0:F4:1A:7D
CE:58:76:C1:6C:B3:46:E9:A7:18:09:1C:EC:3D:57:D9

Varían en 6 bystes (están en negrita), pero sin embargo, estas secuencias dan el mismo MD5, por lo que al firmarlas con la clave pública de la entidad de certificación CA, en ambos casos nos da la mismo bloque de firma MD5/RSA.

Algoritmo de firma: md5WithRSAEncryption
Contenidos de la firma:
13:19:E6:FF:66:EF:86:21:AE:AE:0C:FB:D2:C0:67:B9:9C:38:34:C0
0B:E8:8E:0A:97:E6:02:05:BC:5E:CD:85:64:6B:66:98:BD:2E:91:32
48:26:C8:B1:0E:21:67:EF:F2:64:C5:E4:5A:23:4F:DE:57:23:A7:51
EA:2B:79:13:06:22:1B:54:B4:C2:0E:4C:D1:65:62:D6:98:AD:E4:D6
33:F0:53:D6:53:F8:BE:9C:4D:40:2E:C9:F9:2D:36:30:98:DD:56:05
96:F7:BF:09:5A:F3:C9:FE:D7:EE:2B:49:21:80:18:00:3F:5C:65:F0
51:1D:45:4E:6E:52:29:13:2D:04:94:B7:B6:5E:F9:58:5A:A9:D4:33
09:4F:DB:4F:9C:99:46:10:AF:E0:F2:3F:B2:6E:5D:24:65:39:AE:FF
B6:E0:B0:DF:35:B4:D9:AE:3C:F7:68:C5:AA:BC:93:55:8D:F8:7B:F4
21:28:8E:79:E9:AD:CB:B8:DA:23:64:52:8E:74:F8:13:48:FF:B9:F5
FA:C4:3E:97:4F:3D:79:CC:A2:22:FD:67:5B:FD:3B:80:8A:3F:66:10
42:32:C8:06:A2:53:09:A1:87:D1:03:D7:50:89:34:36:D4:A3:29:09
FE:5C:76:B4:54:95:F5:2F:29:CF:66:A9:E3:DD:47:3F

Para hacernos una idea de lo que hay en el certificado primero tenemos:

[fernando@casa fernando]$ openssl x509 -in MD5Collision.certificate1.cer -inform DER -text
Certificate:
Data:
Version: 3 (0x2)
Serial Number: 55604297 (0x3507449)
Signature Algorithm: md5WithRSAEncryption
Issuer: CN=Hash Collision CA, L=Eindhoven, C=NL
Validity
Not Before: Feb 1 00:00:01 2005 GMT
Not After : Feb 1 00:00:01 2007 GMT
Subject: CN=Hash Collision, O=we used a collision for MD5, L=Eindhoven, C=NL
Subject Public Key Info:
Public Key Algorithm: rsaEncryption
RSA Public Key: (2048 bit)
Modulus (2048 bit):
00:ca:b9:e7:42:c4:b6:26:87:1a:b9:a5:24:84:6b:
05:c1:88:95:fb:93:65:e9:a6:9f:48:03:92:ff:2c:
3b:3f:79:41:ad:34:06:ff:ad:b4:03:4b:df:84:7a:
4d:37:01:4f:db:32:83:cb:19:d4:6f:a8:a7:65:c6:
b3:f0:16:bf:30:6a:ff:7c:2e:57:73:68:9b:33:19:
b8:15:64:ab:e7:f5:b9:cf:66:c5:e4:fe:79:0c:ee:
04:7d:36:cc:77:b0:ae:5d:08:7f:30:b5:60:eb:88:
72:b3:4d:40:67:78:66:2d:d8:84:64:67:7d:bd:9b:
80:98:9e:f2:4f:b8:2e:0e:a3:2b:58:64:af:33:b8:
fe:86:59:b0:94:46:46:99:f4:77:a6:bf:ca:34:8c:
23:cf:68:1e:c0:a8:46:a8:b2:7a:29:07:1b:56:3a:
13:16:b0:5f:38:27:b8:2f:b1:f9:de:1f:23:8f:3d:
12:ad:0d:da:a9:7d:db:cf:ce:ea:d1:09:39:5e:46:
e0:18:ae:23:7c:e5:93:55:ac:93:18:72:28:4c:3a:
29:3f:e9:11:79:41:a1:ad:52:83:64:a0:68:7a:ff:
60:83:b1:4b:00:9d:d9:52:c8:66:ca:43:a0:f4:1a:
7d:ce:58:76:c1:6c:b3:46:e9:a7:18:09:1c:ec:3d:
57:d9
Exponent: 65537 (0x10001)
X509v3 extensions:
X509v3 Basic Constraints:
CA:FALSE
X509v3 Key Usage:
Digital Signature, Non Repudiation, Key Encipherment
Signature Algorithm: md5WithRSAEncryption
13:19:e6:ff:66:ef:86:21:ae:ae:0c:fb:d2:c0:67:b9:9c:38:
34:c0:0b:e8:8e:0a:97:e6:02:05:bc:5e:cd:85:64:6b:66:98:
bd:2e:91:32:48:26:c8:b1:0e:21:67:ef:f2:64:c5:e4:5a:23:
4f:de:57:23:a7:51:ea:2b:79:13:06:22:1b:54:b4:c2:0e:4c:
d1:65:62:d6:98:ad:e4:d6:33:f0:53:d6:53:f8:be:9c:4d:40:
2e:c9:f9:2d:36:30:98:dd:56:05:96:f7:bf:09:5a:f3:c9:fe:
d7:ee:2b:49:21:80:18:00:3f:5c:65:f0:51:1d:45:4e:6e:52:
29:13:2d:04:94:b7:b6:5e:f9:58:5a:a9:d4:33:09:4f:db:4f:
9c:99:46:10:af:e0:f2:3f:b2:6e:5d:24:65:39:ae:ff:b6:e0:
b0:df:35:b4:d9:ae:3c:f7:68:c5:aa:bc:93:55:8d:f8:7b:f4:
21:28:8e:79:e9:ad:cb:b8:da:23:64:52:8e:74:f8:13:48:ff:
b9:f5:fa:c4:3e:97:4f:3d:79:cc:a2:22:fd:67:5b:fd:3b:80:
8a:3f:66:10:42:32:c8:06:a2:53:09:a1:87:d1:03:d7:50:89:
34:36:d4:a3:29:09:fe:5c:76:b4:54:95:f5:2f:29:cf:66:a9:
e3:dd:47:3f
-----BEGIN CERTIFICATE-----
MIIDNTCCAh2gAwIBAgIEA1B0STANBgkqhkiG9w0BAQQFADA9MRowGAYDVQQDExFI
YXNoIENvbGxpc2lvbiBDQTESMBAGA1UEBxMJRWluZGhvdmVuMQswCQYDVQQGEwJO
TDAeFw0wNTAyMDEwMDAwMDFaFw0wNzAyMDEwMDAwMDFaMGAxFzAVBgNVBAMTDkhh
c2ggQ29sbGlzaW9uMSQwIgYDVQQKExt3ZSB1c2VkIGEgY29sbGlzaW9uIGZvciBN
RDUxEjAQBgNVBAcTCUVpbmRob3ZlbjELMAkGA1UEBhMCTkwwggEiMA0GCSqGSIb3
DQEBAQUAA4IBDwAwggEKAoIBAQDKuedCxLYmhxq5pSSEawXBiJX7k2Xppp9IA5L/
LDs/eUGtNAb/rbQDS9+Eek03AU/bMoPLGdRvqKdlxrPwFr8wav98LldzaJszGbgV
ZKvn9bnPZsXk/nkM7gR9Nsx3sK5dCH8wtWDriHKzTUBneGYt2IRkZ329m4CYnvJP
uC4OoytYZK8zuP6GWbCURkaZ9Hemv8o0jCPPaB7AqEaosnopBxtWOhMWsF84J7gv
sfneHyOPPRKtDdqpfdvPzurRCTleRuAYriN85ZNVrJMYcihMOik/6RF5QaGtUoNk
oGh6/2CDsUsAndlSyGbKQ6D0Gn3OWHbBbLNG6acYCRzsPVfZAgMBAAGjGjAYMAkG
A1UdEwQCMAAwCwYDVR0PBAQDAgXgMA0GCSqGSIb3DQEBBAUAA4IBAQATGeb/Zu+G
Ia6uDPvSwGe5nDg0wAvojgqX5gIFvF7NhWRrZpi9LpEySCbIsQ4hZ+/yZMXkWiNP
3lcjp1HqK3kTBiIbVLTCDkzRZWLWmK3k1jPwU9ZT+L6cTUAuyfktNjCY3VYFlve/
CVrzyf7X7itJIYAYAD9cZfBRHUVOblIpEy0ElLe2XvlYWqnUMwlP20+cmUYQr+Dy
P7JuXSRlOa7/tuCw3zW02a4892jFqryTVY34e/QhKI556a3LuNojZFKOdPgTSP+5
9frEPpdPPXnMoiL9Z1v9O4CKP2YQQjLIBqJTCaGH0QPXUIk0NtSjKQn+XHa0VJX1
LynPZqnj3Uc/
-----END CERTIFICATE-----

El otro será igual pero cambiando el bloque de la clave por el otro.

Sin embargo, como los dos certificados no son iguales, obvio.. su fingerprint no es el mismo:

130df04302123ad244b1aaa918aa9b42 certificate1.cer S/N=55604297
71c7aaa1c41e150677e0bdff40265418 certificate2.cer S/N=55604297

Valor de MD5 que nos aparece en la ventana a la hora de importar el certificado y que se debe comprobar siempre, repito, siempre. Una cosa es encontrar una colisión para el bloque de clave pública y otra muy distinta encontrar una colisión doble, es decir que sea válida para el bloque de clave pública (solamente se puede variar el contenido de este dentro del certificado) y que además, provoque la colisión del MD5 para todo el archivo del certificado, haciendo que el fingerprint de ambos certificados también coincida.

Moraleja... revisa siempre el fingerprint de cualquier certificado y comprueba que coincide con su número de serie, antes de aceptarlo.

Una colisión, aunque se materialice en dos certificados válidos, como es este el caso, no tiene mucha utilidad directa para cometer un fraude. Para ello, tendríamos que ser la entidad de certificación. Lo jugoso son las preimágenes y segundas preimágenes... pero todo se andará.. con varias colisiones se pueden buscar patrones de creación, como ahora se tienen algoritmos para calcular primos industriales. Sí es cierto que este asunto proporciona un grado de libertad a una entidad de certificación "malvada", poniendo en duda la seguridad y credibilidad global del sistema.

También hay que decir, que para construir estos certificados se han usado unos números primos un poco "especiales", aunque son válidos para la comprobación de firma. Esto se hace para reducir el tiempo necesario de factorización. La base del sistema es el Número Fermat-4 de la forma (2^2^^N)+1, en la que n=4, es decir 65537. Las cifras de tiempo para el cálculo son más que razonables, poniendo el límite en varios días, para los casos más complicados.

Ahora bien... señores, el río suena y agua lleva... a efectos de la factorización, se ha reducido la fortaleza de los algoritmos MD5 y SHA-1 en un 99,981 % ante las colisiones, lo que es una cifra muy grande aunque quede algo de margen en la complejidad en el caso del SHA-1. Seamos realistas, aunque no se hayan realizado preimágenes ni segundas preimágenes, la cosa está complicada y a punto de caramelo.

Aunque lo materializaré en un artículo que realizaré cuando tenga algo de tiempo, adelanto que ante las declaraciones del Ministro de Justicia, solamente puedo decir que no es el mejor momento para hacerlo. Las condiciones de incertidumbre tecnológica ante las funciones de hash, desaconsejan una inversión como la que se comenta en el artículo de Cinco" Días, pero seguro que opinones hay para todos los gustos y expertos en todas partes. La toma de una medida como esta en este momento, puede suponer la apertura de un problema de seguridad nacional muy complicado de resolver. Todo esto, sin hablar del informe sobre la seguridad de la plataforma de voto elaborada por el VotoBit, que al margen de la nota de Indra, parece que hay cosas en el informe, que no tienen mucho que ver con el asunto de un servidor en pruebas. Repito, sigo pensando que no es el mejor momento... pero, doctores tiene la Iglesia.

La única salida para ganar algo de tiempo, que no seguridad absoluta, sería usar desde este mismo momento la Suite-2, es decir SHA-2 + curvas elípticas, como recomienda la NSA. Además se deberían implementar sobre un sistema lo suficientemente flexible, como para se puedan realizar los cambios que fueran necesarios, en el caso de surgir problemas de seguridad sobre la pataforma.

Pero me temo que... "va a ser que no" y que el DNI saldrá, por "necesidades del guión", con un SHA-1 que está en un tris de ser roto por completo... y no solamente a nivel de colisiones. Si tenemos en cuenta la función de complejidad declarada por el equipo chino, se puede concluir que atendiendo solamente a la Ley de Moore, al DNI si sale hoy con el SHA-1, sin avances en los análisis, le quedan como mucho 3, años de vida medianamente segura.... el resto Dios dirá. Recomiendo el artículo...Analfabetismo Digital y sus Implicaciones en la Seguridad Informática, me temo que podemos estar en manos de alguno, a la vista de algunos acontencimientos de la historia reciente...

Dado que todas las funciones de HASH funcionan sobre esquemas semejantes, sería conveniente iniciar un plan de I+D+i en temas critográficos, por ser una necesidad de la seguridad nacional y Europea. Claro, que a este asunto, ha venido a entorpecer la reciente aprobación de la Directiva de Patentes de Software Europea, que como se puede ver, no ha podido venir en un peor momento tecnológico, limitando la capacidad de innovación en toda la zona euro. Algo, que además, considero que va en contra del espíritu del Artículo 248 del reciente Tratado de la Constitución Europea, que para los políticos de Bruselas, altamente "motivados" por las presiones de las multinacionales, parece como si no se hubiera aprobado.

Otro toque de atención y para la reflexión. La mayoría de los bancos/páginas web seguras utilizan certificados basados en MD5. A pesar de los problemas, que se conocen de este algoritmo desde hace tiempo, casi nadie se ha dado por enterado del problema. Si ocurre lo mismo, en el caso de que se rompa el SHA-1 con el DNI digital en marcha, nos podemos echar a temblar ¿qué mecanismos se piensan poner en marcha, para que en el caso de que ocurra, que ocurrirá, no afecte a la seguridad global del sistema?. Yo creo que debemos cambiar nuestro concepto de seguridad de los sistemas criptográficos y disponer de planes de contingencia para los casos, que aunque se consideren improbables, supongan la ruptura total del sistema critográfico.

No obstante, muchos estarán dispuestos a impugnar la primera elección que se realice por Internet, en cuanto aparezca la primera colisión sobre un certificado SHA-1 usado en un DNI digital.

Cuando escribí el artículo Consideraciones de Seguridad al DNI digital, lo criticó mucha gente, cosa que ha ocurrido hasta hace unos meses, pero parece que cada día que pasa está de más rabiosa actualidad y que hay cosas en él, que se deberían tener en consideración. Hasta se merece una actualización ¿verdad?

Finalmente, un tema delicado. Las monoculturas tecnológicas e ideológicas son muy peligrosas en temas de seguridad. En España, hay moy pocos interlocutores para los temas de criptografía, interlocutores, que como yo en muchos casos, pueden equivocarse en sus valoraciones y estudios, que todos somos personas y que pueden verse influidos por las presiones para implantar un determinado sistema o servicio desde algunas instancias. Hay que establecer protocolos y sistemas de asesoría y certificación, para que esto no ocurra en ningún caso.

Vuelvo a lo mismo, hace falta más I+D+i y abrir el debate, sobre sistemas criptográficos y seguridad, a nivel europeo. La forma de trabajar que se tiene en la actualidad, crea un ambiente de oscurantismo, que no facilita que los ciudadanos confíen en la tecnología. A mi mismo, que soy un pesimista crónico, no me hace ninguna gracia que se expida un DNI digital a mi nombre y menos, como están las cosas en este momento. Ante la duda... mejor no implantar y replantearse la base tecnológica, repito, señores no es el mejor momento, con esta tecnología no se debe hacer.

¿Qué hacemos si en cinco años, por poner un tiempo razonable, aparecen computadores cuánticos en el mercado y se comprometen las claves? ¿tiramos el DNI y nos olvidamos del comercio electrónico, de la e-administración, de la e-democracia y de los sistemas de firma dital?, necesitamos mejorar la tecnología de cifra, creando nuevos estándares, que nos permitan salir de las monoculturas. Mi evaluación de coste eficacia para la implantación del DNI electrónico, se decanta por el lado del excesivo coste por momentos. Lo que parecía una gran idea hace tres años, ahora, evidentemente, ha dejado de serlo y se deben buscar alternativas más razonables.

"Copyleft 2004 Fernando Acero Martín. Verbatim copying, translation and distribution of this entire article is permitted in any digital medium, provided this notice is preserved".

No cabe duda que el ataque de colisiones diferenciales (Chabaud-Joux) ha provocado un lindo revuelo en la seguridad de las funciones hash.
Todavía no está demostrado que SHA-1 haya muerto, eso sí, está bastante golpeado. El que ha fallecido es MD5 y tal vez todos los hash de 128 bits. Los de 160 están en la picota pero aún no se sabe como hacer un buen ataque de preimágen con contenido semántico... o sea fraguar (en un Home Banking y bajo SSL v3) un "cheque electrónico" originalmente de 100 Euros a 1.000.000 de Euros, algo que realmente movería al ambiente bancario mundial..

Aparte de eso... nada impide ir al standard SHA-2 (256 y 512 bits). A esos hashing todavía nadielos rozó.. A pesar que teóricamente toda la familia MD4 (y sus descendientes) ha quedado impregnada, no hay explotación concreta de ataques (Algo parecido al 3DES 168-bits, inexpugnable a pesar de la muertedel DES 56-bits).

Al que le interese algo mas acerca del tema, hay un pequeño artículo a nivel tecnico disponible en:
Ataques a Hashings (pdf)