¿seguridad razonable?
Interesante artículo de Sergio Hernando en kriptópolis a propósito de los descubrimientos de la doctora Wang y su equipo
dice textualmente:
«Llegados a este punto, conviene preguntarse qué implica esto para la vida útil de los algoritmos MD5 y SHA-1. Muchos medios se apresuran a tachar los algoritmos como totalmente inválidos a tenor de los resultados, y proclaman su sustitución inmediata como estándar de facto. Pensando sobre el tema, llegamos a la conclusión de que quizás ésto sea algo precipitado.»
y continúa más adelante:
«Es decir, las necesidades que tiene un usuario de UNIX cuando invoca los comandos “md5sum” o “sha1sum” para verificar la integridad de una imagen ISO que ha descargado no son las mismas que las que puede tener un laboratorio de alta seguridad que conserva muestras nucleares y cuyos medios de acceso físico requieren de cifrados muy robustos, por motivos obvios. Tampoco son iguales las necesidades de un portal PHP+SQL que conserva hashes SHA-1 de las claves de usuario, por citar meros ejemplos.»
Mi duda, como operador jurídico, es ¿que seguridad precisa una transacción on line con nuestro banco o, yendo más lejos, que seguridad precisa el cifrado de la AEAT o de las comunicaciones con los Tribunales de Justicia?
¿responden, en estos momentos, SHA-1 y MD5 al concepto de seguridad razonable atendido el estado de la técnica que predica nuestra normativa de firma electrónica?
Pedro, no es que yo sea un experto en criptografía, pero:
1) un hash es un número razonablemente largo que identifica un contenido (sea un iso, una foto o una transferencia de datos con tu banco).
2) los llamados ataques a los algoritmos SHA-1 o MD5 son «colisiones».
3) Dado un contenido y su hash, una «colisión» es otro contenido distinto cuyo hash es el mismo.
4) Una colisión sólo resulta práctica para la realización de un ataque si ambos contenidos tienen identica aplicación (dos isos, dos fotos o dos transferéncias de datos con tu banco).
5) Por lo anterior y a título de ejemplo, que un atacante construya un texto (una combinación de letras) cuyo hash es identico al este comentario (por poner un ejemplo) no sirve de mucho porque en los comentarios uno espera texto con significado semántico, y no manojos de letras.
6) Por todo lo anterior, creo que los actuales sistemas que empleo con mi banco o hacienda son suficientes (no conozco Justicia), si bien estos resultados académicos recuerdan que hay que seguir trabajando por lo que pueda venir en un futuro.
7) Los ataques que más daño están haciendo en la actualidad se llaman «phishing» o algo así y distan mucho de requerir los grandes conocimientos matemáticos del grupo de Wang.
Repito, no soy experto en temas de criptografía y es posible que algo se me escape, por lo que si tras leer lo anterior alguien me enmienda la plana, yo muy agradecido.
En el site de la Editorial Jurídica vLex.com podeis encontrar un Dossier Especial sobre LexNet con entrevistas realizadas a Cristina Thomas, subdirectora de Nuevas Tecnologías del Ministerio de Justicia, y a Fernando Fernández Cieza, presidente de la Comisión de Nuevas Tecnologías del Consejo General de Procuradores de España.
http://premium.vlex.com/actualidad/especiales/Sistema_LexNet_Administracion_Justicia/2500-LXN,05.html
A ver si alguno de los habituales de esta bitácora sabe sacarnos de dudas!
Hola a tod@s.
Cuando se habla de «hash» nos referimos a ciertas funciones (en el sentido matemático del término) biyectivas que cumplen, básicamente, dos propiedades: (1) inexistencia de colisiones, y (2) unidireccionalidad.
Tranquilos, paso a explicarme con más detenimiento.
Una función «hash» (también conocida en la lengua de Cervantes como «funcion de dispersión») es una función que dado un valor, devuelve un resultado al que llamaremos «clave».
f(x)=y
siendo «x» el valor, e «y» la clave resultante.
Toda función «hash» se pretende que sea BIYECTIVA (relación 1-a-1), es decir, que a cada valor le corresponda una única clave, y que a cada clave le corresponda un único valor. De este modo no existirán dos valores que correspondan a la misma clave, ni dos claves que correspondan al mismo valor. O lo que es lo mismo, no existen «colisiones» entre dos o más valores y una clave, o entre un valor y dos o más claves.
Gracias a la propiedad de la biyección (o «NO-COLISIÓN») conseguimos que si aplicamos la función «hash» a un documento, fotografía o archivo en formato digital, obtendremos una clave distinta para cada documento. De este modo, cualquier modificación que se realice sobre el documento, fotografía o archivo original, conllevará que la clave generada sea distinta. Así mismo, esa misma clave no podrá ser el resultado de aplicar la función «hash» a un documento distinto ya que dos documentos distintos generan claves distintas.
La principal ventaja de esta biyección es que si conocemos la clave original de un documento podemos comprobar si el documento ha sido o no alterado, recalculando la clave a partir del documento y comparándola con la original.
La función «hash» además de ser biyectiva se pretende que sea UNIDIRECCIONAL. Es decir, que a partir de un valor se pueda obtener su clave asociada, pero no al revés, esto es, que conocida la clave sea «computacionalmente imposible» calcular el valor originario.
El término «computacionalmente imposible» significa que no debe ser factible calcular ese valor en un tiempo computacionalmente menor a la «vida útil» del valor al que protege. Pongamos un ejemplo: una factura debe almacenarse durante 6 años para ser presentada en una supuesta inspección fiscal. Por tanto, si esa factura se firmara digitalmente haciendo uso de una función «hash», dicha función debería garantizar que durante al menos 6 años ningún ordenador (por potente que éste fuera) sería capaz de obtener el valor originario a partir de la firma digital de la factura. Transcurrido ese plazo, nos daría igual que el valor fuera obtenido ya que la factura no sería «útil» o «trascendente».
También se suele entender por «computacionalmente imposible» al hecho de que cualquier ataque debe tardar en deducir el valor originario a través de la clave COMO MÍNIMO el mismo tiempo que mediante un ataque de fuerza bruta, esto es, el mismo tiempo que si probáramos uno por uno el conjunto de todos los posibles valores originarios.
Con esta segunda propiedad, la unidireccionalidad, conseguimos que si el valor que se utilizó para calcular la clave era secreto, lo siga siendo ya que no es «posible» obtener el valor originario a través de la clave generada. De este modo, si solamente yo conozco el valor originario, solo yo puedo generar una determinada clave, por lo que todo documento, fotografía o similar que tenga dicha clave habrá sido firmado por mi, y no por otra persona. Esto permite identificar al autor de la firma y garantizar el «no-repudio».
Uniendo esta segunda propiedad a la primera, conseguimos conocer de forma fehaciente (1) quién el autor de un documento, y (2) que dicho documento no ha sido modificado por un tercero.
Hace ya algún tiempo que se demostró que la función SHA-1 no era biyectiva por completo, habiéndose encontrado colisiones, es decir, que dos o más valores distintos generaban la misma clave. Este descubrimiento suponía que YA NO PODEMOS GARANTIZAR AL 100% que un documento no ha sido modificado o que su autor es quién dice ser, ya que dos valores diferentes podían resultar en la misma clave. O lo que es lo mismo, dos documentos distintos podrían corresponder a la misma clave, o dos personas distintas podrían tener la misma firma.
Los experimentos de la doctora Wang han venido a confirmar lo que ya sabíamos. Es más, lo que han demostrado es que hay más colisiones de las que en un principio se pensaba y que es más fácil (léase rápido) encontrar dichas colisiones. Esto también conlleva que hay claves más probables, y claves menos probables (o incluso claves que nunca se usan) por lo que podemos incluso reducir el universo de posibles claves. Con esa información, es previsible que los ataques a dichas funciones «hash» se perfeccionen y que en poco tiempo se reduzca el tiempo que cuesta «romper» la función.
Ahora bien, lo que se ha logrado es encontrar parte de las colisiones de la función SHA-1 (digamos que son todas las que están, pero seguramente no están todas las que son ¿o viceversa… bueno no sé?). Eso no significa que dado un documento y una clave seamos capaces de encontrar un documento distinto que proporcione la misma clave. Y mucho menos que dado un documento y una clave seamos capaces de encontrar el valor originario.
Para entendernos, lo que la doctora Wang ha hecho es dar otro mazazo a los cimientos de la función SHA-1 y que, por tanto, ahora dicha función «hash» es un poco menos robusta o confiable. Si me permiten la metáfora, si SHA-1 fuera una presa de agua, diríamos que la doctora Wang ha detectado que las grietas que tenía la presa son más grandes de lo que pensabamos y que es de esperar que en poco tiempo alguien aproveche y las dinamite.
Personalmente, a día de hoy no me veo capaz de dar una respuesta taxativa a la pregunta que plantea Pedro. Ahora bien, lo que si puedo es recomendar el uso de cualquierda de las variantes de SHA (SHA-256, SHA-512, etc) en aquellos casos que sea posible. Para todo lo demás, ma$tercard… digo… SHA-1.
Muchísimas gracias Jorge, creo que ya nos ha quedado más claro, por lo menos a mí, donde puede estar el problema, y donde la solución.
Discuto algunos de los puntos del comentario de Juan Carlos…
1) un hash es un número razonablemente largo que identifica un contenido (sea un iso, una foto o una transferencia de datos con tu banco).
Más o menos de acuerdo. Lo que se suele entender como «hash de un documento» viene a ser como una especie de resumen de dicho documento. Normalmente, es dicho resumen lo que suele ir firmado y no el documento. En ocasiones se firma tanto el documento como el resumen, pero en cualquier caso siempre se firma el resumen.
Esto se debe a que es menos costoso (en tiempo y, por tanto, en recursos) firmar un resumen de un documento que el documento completo. Un notario podría dar fe de ello, si me permiten el chascarrillo.
2) los llamados ataques a los algoritmos SHA-1 o MD5 son “colisiones”.
Totalmente correcto. Los experimientos de la doctora Wang hablan sobre ataques por «colisión».
3) Dado un contenido y su hash, una “colisión” es otro contenido distinto cuyo hash es el mismo.
De nuevo, totalmente de acuerdo.
4) Una colisión sólo resulta práctica para la realización de un ataque si ambos contenidos tienen identica aplicación (dos isos, dos fotos o dos transferéncias de datos con tu banco).
Aquí no estoy tan de acuerdo. En muchas ocasiones la aplicación no es relevante para el problema. Por ejemplo, en sistemas UNIX/LINUX no se guardan las contraseñas de los usuarios directamente sino que se guardan los valores «hash» resultantes de aplicar MD5 a dichas contraseñas. De este modo, aunque alguien accediera al fichero donde se guardan, nunca averiguarían las contraseñas sino únicamente sus «hash». En evidente que una contraseña no tiene porqué tener sentido (de hecho, se recomienda que no lo tenga e incluso que sea aleatoria) y no importa, por tanto, su aplicación.
En el caso de documentos, fotografías y demás, el «hash» que se deriva de dichos documentos no tiene porqué tener sentido ya que el contenido del documento se traduce a dígitos y a partir de estos se obtiene el «hash». Por tanto, el resumen (clave «hash») del documento se obtiene a partir del documento pero típicamente contiene información «no legible» por un humano. Es decir, el resumen de un texto no está compuesto por palabras del texto, sino por cálculos realizados sobre dichas palabras.
Es por ello que sostengo que la aplicación de los contenidos no es muy (o nada) relevante.
5) Por lo anterior y a título de ejemplo, que un atacante construya un texto (una combinación de letras) cuyo hash es identico al este comentario (por poner un ejemplo) no sirve de mucho porque en los comentarios uno espera texto con significado semántico, y no manojos de letras.
En esto si estoy de acuerdo, pero solamente en aquellos casos en los que el contenido tiene un significado semántico. Recordemos que en el ejemplo de las contraseñas en sistemas UNIX/LINUX no hay semántica que valga.
6) Por todo lo anterior, creo que los actuales sistemas que empleo con mi banco o hacienda son suficientes (no conozco Justicia), si bien estos resultados académicos recuerdan que hay que seguir trabajando por lo que pueda venir en un futuro.
Bueno, yo también me mojaré: yo también pienso que los actuales sistemas son suficientes. Ahora bien, sin prisa pero sin pausa deberíamos ir buscando otro «techo» sobre el que cobijar nuestros datos porque han anunciado lluvias y nuestro actual «techo» empieza a tener goteras.
7) Los ataques que más daño están haciendo en la actualidad se llaman “phishing” o algo así y distan mucho de requerir los grandes conocimientos matemáticos del grupo de Wang.
Efectivamente, se llaman «phising» pero este tipo de ataques hacen uso (léase abuso) de la llamada «ingenería social» y no de las «colisiones hash», que es el tema que nos ocupa.
Por cierto, Juan Carlos, te manejas (en el sentido Español de la palabra) muy bien para no ser experto en criptografía.
Finalmente, expondré lo realmente «peligroso» del resultado de los expermientos de la doctora Wang. En el trabajo «Colisionando certificados X.509» se demuestra que existen certificados digitales distintos que poseen la misma firma. Y es precisamente la firma del certificado digital lo que permite identificar los certificados (ej: la web de mi banco tiene un certificado digital con una firma concreta y si la firma es distinta de la esperada, esa no es la web de mi banco). Esa firma es la que se utilizará para cifrar los contenidos de la web, para cifrar las comunicaciones con la web, etc.
En definitiva, significa que tú, Pedro y yo ya no podemos estar seguros 100% de que la Autoridad Certificadora que expide el certificado digital de nuestro banco (ya sea la Fábrica Nacional de Moneda y Timbre, la Cámara de Comercio, Verisign o cualquier otra) pueda garantizar que el dueño del certificado digital posea realmente la correspondiente clave privada. Es decir, que alguien podría hacerse pasar por mi banco y yo no me daría cuenta ya que el certificado digital del falso banco aparentemente es un certificado válido emitido por la Autoridad Certificadora correspondiente.
Por tanto, la doctora Wang está diciendo que es posible que exista (o pueda existir) otro certificado distinto al de la web de nuestro banco que tenga la misma firma, y que por tanto, podemos estar accediendo a una web bancaria falsa, que podemos estar bajando un parche de nuestro sistema operativo (Microsoft, Linux, Mac, etc) que no es el «oficial», que la factura digital que nos han dado es falsa…
Entiendanme bien, la doctora no dice que esté pasando, sino que ha demostrado puede llegar a pasar.
Por cierto, releyendo mi ultimo comentario me parece que ha quedado muy «catastrofista».
Decir, para tranquilidad de todos, que en el improbable e hipotético caso de que alguien consiguiera crear un certificado digital que tuviera la misma firma que el certificado digital de nuestro banco, nuestro abogado o nuestro médico, la probabilidad de que pudiera usar ese certificado falso de forma efectiva es tremendamente pequeña.
Esto es, en caso de crear dicho certificado (lo cual ya es muy difícil hoy por hoy, pero no imposible) probablemente no podría utilizarlo para nada ya que seguramente no tendría la clave privada del falso certificado y, en consecuencia, no podría leer los documentos cifrados con el certificado digital y no podría firmar documentos con dicho certificado digital.
Pero explicar esto es un poco más largo y tedioso (debido al par clave pública – clave privada).
De nuevo, quiero dar tranquilidad.
Bueno, la definición correcta de una función hash, según Bruce Schneier es:
«Una función Hash es una función que toma como entrada una cadena de bits de longitud arbitraria y produce un resultado de tamaño fijo».
Como consecuencia de esta propiedad, la única forma de que una función hash esté libre de colisiones es que el resultado de salida, de tamaño fijo, sea infinito. Es decir, el conjunto de entrada de la función hash es un dominio de cardinalidad infinita, es decir, de infinitos elementos. El conjunto de salida o codominio, es de tamaño fijo, y si lo expresamos como n bits, será de 2^n elementos, es decir, de tamaño finito. Para que no existan colisiones, es decir, para que se trate de una función 1-a-1, n tendría que tender a infinito.
En la práctica, n es un número pequeño, n
Vuelvo a mandar el comentario porque parece que no salió completo la primera vez. Lo siento.
Bueno, la definición correcta de una función hash, según Bruce Schneier es:
«Una función Hash es una función que toma como entrada una cadena de bits de longitud arbitraria y produce un resultado de tamaño fijo».
Como consecuencia de esta propiedad, la única forma de que una función hash esté libre de colisiones es que el resultado de salida, de tamaño fijo, sea infinito. Es decir, el conjunto de entrada de la función hash es un dominio de cardinalidad infinita, es decir, de infinitos elementos. El conjunto de salida o codominio, es de tamaño fijo, y si lo expresamos como n bits, será de 2^n elementos, es decir, de tamaño finito. Para que no existan colisiones, es decir, para que se trate de una función 1-a-1, n tendría que tender a infinito.
En la práctica, n es un número pequeño, menor o igual que 1024, por lo que es totalmente imposible que cualquiera de las funciones hash que existen estén libres de colisiones. Se dice, por tanto, que una propiedad ideal de cualquier función hash es que sea _resistente a colisiones_ (y no exenta de ellas) de tal forma que dado un mensaje m1, tal que h(m1) = h, sea muy complejo hallar otro mensaje m2, tal que h(m2) = h(m1) = h. Esto es precisamente un ataque de colisión y estadísticamente se calcula que, por fuerza bruta, puede hacerse en 2^(n/2) operaciones, donde n es el tamaño en bits del hash. De hecho, existen infinitas colisiones para cualquier función hash cuya salida tiene tamaño fijo y finito. Lo que se trata de evitar es que sea sencillo determinar cuáles son esas colisiones.
Otro tipo de ataque es el denominado de primera pre-imagen, por el cual dado un hash x, se pretende encontrar un mensaje M tal que h(M) = x. Pero esto ya es otra historia.
¡Ah! Por cierto, la Dr. Wang no ha demostrado que haya más colisiones de lo que se creía. Realmente, como he comentado anteriormente, existen infinitas colisiones en cualquier función hash, sea MD5, SHA-1 o SHA-512.
Lo que ha demostrado la Dr. Wang es que es posible hallar una colisión con un número de operaciones mucho más reducido que el caso medio o por fuerza bruta. El caso medio para SHA-1 de 160 bits es 2^80 operaciones, y la Dr. Wang lo ha conseguido hacer en 2^63, o lo que es lo mismo, ha mejorado el sistema en 2^17 veces = 131.072 veces más rápido.
Jorge B., comentaré más tarde sobre lo comentado, pero así a bote pronto y sin ánimo absoluto de crear polémica:
Una «hash» NO es biyectiva. Por ejemplo MD5 genera «hashes» de 128 bits. Eso significa que f(x) donde f es MD5 y x es un contenido puedo tomar «solo» 2^128 valores distintos. Puede paracer mucho, pero eso es el número de todos los ficheros distintos de tamaño 16 bytes. Lo que significa que si MD5 es capaz de devolver un hash distinto para cada fichero distinto de 16 bytes, TODOS aquellos ficheros más pequeños generarán colisión.
No hace falta criptografía, sino tan solo contar.
Todo esto viene al caso del episodio jurídico australiano en el que recurrieron una multa con la excusa de que es posible generar un colisión a la foto de los tráfico. El fiscal debería haber alegado que ese argumento sólo es válido si demuestra que una foto SIMILAR devuelve el mismo hash. Esto es, por ejemplo, que la misma foto con un número de matrícula distinto devuelva el mismo «hash».
Es la eterna interpretación entre lo «probable» y lo «posible».
Lo «probable» y lo «posible», Juan Carlos, en Derecho es fundamental ;), por eso cuando informática y derecho van tan de la mano como en el caso de la firma electrónica y la criptografía informáticos y juristas tenemos que encontrar un lenguaje común para entendernos.
pero….sigan vds. con su debate que yo estoy aprendiendo una barbaridad.
Ahora sí, Pedro B., si señor, yo pensando en el episodio de la foto de tráfico australiana y el tema de las claves de los UNIX que estaba delante de mis narices es mucho más sensible. Evidentemente si hacen falta 2^63 intentos, como dice noone (si bien hay que dejar que el root te deje leer /etc/shadow primero, pero bueno), como medida precautoria deberíamos cambiar las claves más frecuentemente (nada traumático por otro lado) aunque yo sospecho que llevar a cabo 2^62 intentos (probabilidad de llegar >0.5) debe de llevar unos meses.
El tema que no conocía era el de las colisiones con los X.509, y ese si que tiene implicaciones prácticas. Gracias por el enlace.
Definitivamente hay que empezar a pensar a migrar, aunque sospecho que hacer que el linux empiece a usar «hashes» más largos resulta trivial.
Ostras Jorge B., la demostración de colisiones en los X.509 (eso y dejándo pendiente el byte sobrante) también tiene efectos prácticos. Evidentemente hay información a la que el «enemigo» no tiene acceso pero aún así y a falta de que un gurú del ramo me enmiende la plana la situación no es grave pero parece ser que empieza a ser hora de migrar (ahora saltará alguno diciendo que Schneider dijo hace años que MD5 estaba muy ajada; no si ya te digo).
Me viene a la cabeza que la utilización de otras «hash» no depende de mi sino de mi administrador de sistema, de mi banco, o de la FNMT….
M@x, posible es que una rubia despampanente entre ahora mismo por la puerta de mi despacho y me plante un beso en los morros; muy probablemente en cuanto pulse el botón de «enviar comentario» me sumerja entre los papelotes que tengo a la derecha y no emerga hasta dentro de 4 horas sin interrupciones.
Perdón si la sugerencia de la rubia y el morreo sonaba a desvarío machista. Hubiera escrito que me ofrecía un helado si no fuera porque estoy a dieta.
Ja, ja, ja lo de la rubia está bien, y no creo que ninguna «parroquiana» se moleste.
Queriendo ser divulgativo he simplificado al máximo, y es posible que haya pecado de poco riguroso. Mil perdones. Procuraré ser igual de didáctico pero algo más riguroso.
Bueno, vamos por partes (y en orden).
Todos mis respetos (pero todos, todos) para el tito Schneier, pero las funciones hash no son exclusivas de la criptografía. La definición que comenta Noone está acotada a la criptografía y en concreto de la criptografía «más utilizada» (cosa que no está mal dado que es el tema que nos ocupa, pero yo estaba siendo generalista).
La función
f(x)=x
podría considerarse una buena función hash desde el punto de vista matemático ya que no produce ninguna colisión. Ahora bien, no es unidireccional ya que a partir de la clave puedo obtener el valor originario (por ejemplo, para a la clave 1234 le corresponde el valor 1234 y viceversa). Por tanto, pese a no presentar colisiones no es una buena candidata para cifrar nuestros documentos ya que puedo averiguar, de forma trivial, un valor originario a partir de una clave.
El tema de que una función hash devuelva una cadena de tamaño fijo se debe a que, de lo contrario, nos podríamos encontrar que una firma de un documento digital (i.e. el texto de «El Quijote») sería tan larga (o más) que el propio documento. Y esto no es muy deseable debido al tiempo de computación que requiere crear/comprobar dicha firma. Es por ello que se calculan resumenes (de tamaño fijo, como bien apunta Noone) de los documentos, y son estos resumenes los que se emplean en la firma digital.
Una vez situados, son muy ciertas las palabras de Noone de que al utilizar resumenes de tamaño fijo, las claves que se generan deben colisionar debido al «reducido» universo de posibles claves. Lo ideal es que el número de colisiones sea mínimo.
También estoy de acuerdo con Noone en que lo imprescindible es que sea difícil encontrar esas colisiones. Es aquí donde la doctora Wang ha hecho más grande una brecha que ya existía, ya que nos ha demostrado que era más fácil encontrar colisiones de lo que pensábamos, luego la función SHA-1 es más vulnerable de lo inicialmente imaginado. De hecho, aunque el artículo no lo mencione, la doctora Wang no ha encontrado esa colisión de una forma totalmente casual (no ha utilizado fuerza bruta al 100%), sino que sabía como acotar la búsqueda.
El siguiente paso de la doctora Wang (y de los cientos/miles de investigadores que se centrarán a partir de ahora en este tema) será encontrar más colisiones, y más adelante, deducir una fórmula que calcule el conjunto (parcial o total) de colisiones.
(… continúo …)
Esa fórmula existe (aunque, afortunadamente todavía no es conocida) ya que la dispersión no es aleatoria y sigue una distribución predecible (y desconocida, repito). Solamente es cuestión de tiempo (poco o mucho, eso ya se verá) que alguien descubra parte de la fórmula de marras, o su totalidad.
También comentas, Noone, que «la Dr. Wang no ha demostrado que haya más colisiones de lo que se creía. Realmente, como he comentado anteriormente, existen infinitas colisiones en cualquier función hash, sea MD5, SHA-1 o SHA-512». Cierto, permite que reescriba mi afirmación para ser más riguroso (y más cercano a mi pensamiento original): lo que Wang ha hecho es encontrar colisiones REALES en la función SHA-1 (sabíamos que habría colisiones, pero no cuáles eran). Y eso es malo, muy malo (aunque no catastrófico). Más aun si da la casualidad que la colisión que ha encontrado fuera justo el certificado digital de mi banco (que no es el caso). Pero si lo fuera, a mi me darían igual que existan infinitas colisiones ya que han encontrado una que me afecta directamente!!! (aquí iría una música de apocalipsis ;D ). En ese supuesto, mi banco debería, al menos, cambiar de certificado digital inmediatamente.
Desde mi punto de vista, los estudios interesantes sobre la materia versarán en el futuro sobre cuán predecibles son las colisiones y en hallar la «fórmula de las colisiones de oro». También tratarán sobre si la función SHA-1 presenta una distribución equiprobable para todo el conjunto de claves, o si, por el contrario, hay claves con mayor probabilidad de colisión y claves con menor probabilidad.
Eso sí (aquí voy a ser poco riguroso en mis palabras), aun encontrando la «superfórmula» digamos que solamente se verían comprometidas las claves públicas de los certificados digitales, las claves privadas aun estarían a buen recaudo. Ello se debe a que el otro pilar de la función hash, la propiedad de unidireccionalidad, sigue de momento intacto.
Pido disculpas de nuevo, Noone. Errar es humano y, como dice mi parienta, yo soy muy humano.
(… y finalizo …)
Com bien apunta Juan Carlos, los hallazgos son lo suficientemente importantes como para que los abogados del equivalente en Sydney a la «Dirección General de Tráfico» no pudieran presentar en la Corte Local ni un solo perito que certificase que las fotografías de una supuesta infracción tráfico firmadas mediante MD5 no habían sido alteradas y eran, efectivamente, las originales.
Las propiedades que se espera tenga una Infraestructura de Clave Pública (PKI) son:
1) Confidencialidad.
2) Integridad.
3) No-repudio.
4) No-reenvío.
5) Autenticación.
La propiedad que nos ocupa, la integridad, ya no se puede garantizar.
algo así intuía yo (ignorante picapleitos), y aunque el responsable de Nuevas Tecnologías del CGAE (al que dedicaré un post dentro de unos días) diga que ésto no afecta al sistema Lexnet…que va a ser que sí 😉
Jorge B. al contrario, los abogados de la «DGT australiana» deberían haber argumentado que hay sobradas razones de tipo científico para asegurar que no es posible, computacionalmente hablando, generar otra fotografía con el mismo hash.
Porque repito, una cosa son claves de un UNIX que deberían ser aleatorias y tal y toda combinación de caracteres tiene significado semántico y otra muy distinta es que las colisiones que genera «la doctora Woo» sean fotos de los guardias de tráfico. Repito, la diferencia entre posible (que existan colisiones) y probable (que dicha colisión sea un pavo conduciendo a más de lo que toca).
Don M@x, ahora que Vd. lo comenta, que seguro que sabe de ésto más que yo: mucho LexNet, muchas nuevas tecnologías… pero, hay algún mecanismo establecido para que los resultados de una autopsia, enviados por fax a las partes, lleguen correctamente?
Y no, no, no me refiero a una filtración de los forenses a la prensa que la cotejan con alguna de las partes y la consecuente retransmisión del juzgado al darse cuenta del asunto leyendo el periódico.
Es cierto que cuando hablo de funciones hash me refiero a las funciones hash criptográficas. Las funciones hash criptográficas (MD5, SHA-0, SHA-1 y las variantes conocidas como SHA-2).
Respecto al número de colisiones, es imposible reducir su número al mínimo: corolario -> si proyectas un espacio infinito (dominio) sobre un espacio finito (codominio), existirán siempre infinitas colisiones. Por mucho que el tamaño del codominio aumente, y éste sea finito, existirán infinitas colisiones. Siempre.
Con respecto al tema del certificado del banco, es cierto que se abre la puerta a que alguien sea capaz de generar un certificado X.509 diferente cuyo hash sea idéntico al del banco, pero la probabilidad de que dicho certificado falso contenga información coherente, y mucho menos de que dicho certificado falso contenga como «sujeto certificado» la URL de tu sitio Web, es mucho, mucho menor que 1/(2^63). Por lo tanto de momento yo no me preocuparía demasiado.
Además, para falsear un certificado X.509 no basta con hallar una colisión sobre SHA-1 o MD5, sino conseguir firmar dicho hash con la clave privada de alguna entidad certificadora que esté reconocida por el navegador, lo cual no es tarea sencilla.
Por ello, es cierto que estos descubrimientos deberían hacer que la comunidad criptográfica busque nuevos algoritmos, pero no creo que esto vaya a suponer ningún cambio a corto plazo. Yo, por el momento, sigo haciendo mis compras seguras y utilizando SHA-1 y SHA-2 tranquilamente.
completamente «off topic» 🙂 :
(ya me extrañaba a mí que no surgiera el tema del fax forense, jajaja). Te cuento el procedimiento «oficial»:
el sr. forense hace su informe, se lo entrega al funcionario judicial, el funcionario lo une a los autos, y saca providencia diciendo que ha llegado el informe y dando traslado a las partes, para que se pasen por el Juzgado y – a su costa, o a costa del Juzgado, dependiendo de los usos locales – las partes – generalmente los procuradores – hacen una fotocopia y firman «ante mí el secretario» (jajajajaja) que han recibido una copia.
Lo del fax, como tal no está regulado (y, más bien suena a «cortesía»), y tiene la virtualidad y fehaciencia que le quiera dar el Juzgado; pero – como pasa con google – lo que no está en los autos, no está en el mundo.
de LexNet….de LexNet mejor no hablamos, que me sale otro post XDDD
«Donde dije digo, digo diego».
Donde escribí «Lo ideal es que el número de colisiones sea mínimo» entiéndase como «Lo ideal es que el número de colisiones por clave sea mínimo». Es decir, el número estimado de colisiones que tendrá una clave debe ser igual al número estimado de colisiones para el resto de claves (equiprobabilidad). En definitiva, que el número infinito de colisiones no se concentren en un conjunto de claves.
Por cierto, el certificado «colisionador» de la doctora Wang contiene información más que coherente. Lo que sí es cierto es que sin la clave privada poco se puede hacer. Pero «poco» no es igual a «nada». Si yo fuera un malandrín, en algunos casos me bastaría con que el destinatario legítimo de un mensaje no pudiese leer su contenido, aunque yo tampoco pudiera hacerlo. La aplicación inmediata sería con fines militares, por ejemplo.
Si me permiten la broma, parafraseando la famosa cita de Arquímedes de «Dadme un punto de apoyo y moveré el mundo», diré que «Dadme un certificado digital falso con firma idéntica y me encargaré de hacer fechorías».
Juan Carlos, en la informática forense (o pericial) en muchas ocasiones no es posible utilizar términos como «nunca», «siempre», «nada», o «todo».
En el caso de la «DGT australiana» viene a corroborar mis palabras, ya que aunque es altamente improbable que alguien falsifique la fotografía con el mismo hash, no es imposible.
Es por ello que muchas veces se puede hablar, como mucho, de indicios y no de pruebas (no sé si estoy utilizando los términos legales más correctos, así que espero hacerme entender). Es decir, todo apunta a que las fotografías en cuestión no fueron alteradas, pero ningún perito puede certificarlo con todas las garantias.
Ahora bien, si me preguntaran si los peritos consultados se mojaron poco… en efecto, no se mojaron ni las uñas de los pies.
Por cierto, no soy experto en el tema (ni mucho menos) pero para comprobar si una fotografía ha sido o no alterada no es necesario tener una firma MD5. Los peritos son capaces de evalúar si una fotografía ha sido modificada a partir de la propia fotografía (incluso en formato digital).
La firma MD5 puede verse como un método redundante, esto es, si las características de la imagen indican al 99’99% que la imagen no ha sido alterada, y si la firma MD5 también indica que la probabilidad de que la fotografía sea la original es del 99’99%… blanco y en botella, leche.
«Lo ideal es que el número de colisiones por clave sea mínimo»
¿?¿Número de claves? Las funciones hash criptográficas no tienen clave: son funciones de una sola variable, el mensaje. No entiendo qué quieres decir. Las funciones hash criptográficas, sea cual sea su tamaño de salida (y mientras éste sea finito) tendrán un número infinito de colisiones.
Rebobinamos…
Una función “hash” […] es una función que dado un valor, devuelve un resultado al que llamaremos “clave”.
f(x)=y
siendo “x” el valor, e “y” la clave resultante.
Me explico mejor…
Supongamos que el dominio de «x» fueran los números enteros del 1 al 9, y el dominio de «y» fueran los números enteros del 1 al 9.
Supongamos también que f(x) fuera una función simple, por ejemplo, que devuelve «x», salvo si «x» es par, en cuyo caso devuelve siempre «2».
f(1) = 1, f(2) = 2, f(3) = 3, f(4) = 2, f(5) = 5 , f(6) = 2, etc…
La función presentaría una mala dispersión ya que algunos valores de «y» no tendrían ninguna colisión (1, 3, 5, 7, 9), otros no se utilizarían nunca (4, 6, 8) y otros tendrían muchas colisiones (2, 2, 2, 2).
Soy consciente de que no es el mejor de los ejemplos para el caso que nos ocupa, pero a estas horas del viernes estoy un poco «espesito».
Por cierto, quién tiene los pantalones en mi casa me dice que ya está bien por hoy. Así que buenas «chones» a todos.
Mañana más.
P.D.: Por cierto Pedro, creo que nos estamos yendo un poco del tema 😉
Quiero seguir insistiendo: estamos hablando de funciones hash criptográficas, no de las funciones de dispersión tradicionales utilizadas en programación para crear tablas de búsquedas y esas cosas. MD5, SHA-1 y compañia *son* funciones hash criptográficas, y como tales, existen infinitas colisiones, es decir, existen infinitos mensajes de entrada que generan el mismo valor de resultado:
Matemáticamente hablando, existe el conjunto M = { m1, m2, …, mn } tal que h(m1) = h(m2) = h(m3) = … = h(mn), donde h(x) es una función hash criptográfica, y n es tal que siempre existe un m tal que n
Sí, está claro (ya lo estaba hace muchos mensajes).
Llámalo «m sub i», llámalo «x».
Estamos hablando, entre otras, de estas colisiones. Y eso es, principalmente, de lo que hablo, que los tiempos que están consiguiendo ya empiezan a «preocuparme». Eso sí, no hace falta que salgamos corriendo, sino que habrá que empezar a plantearse emplear alternativas (sí es que no lo habían hecho ya).
N.B.: Si llega a ser necesario, podría dejar de ser didáctico pasa pasar a ser científicamente riguroso. El problema es que se nos descolgarán muchos de los asiduos al blog.
Creo que hace tiempo que estamos aburriendo a Pedro y a Juan Carlos. ;D
«La propiedad que nos ocupa, la integridad, ya no se puede garantizar.»
al hilo de esta frase de Jorge B; para tod@s:
¿Significa (dejando de lado – puntualmente – las cuestiones sobre interoperabilidad y neutralidad tecnológica) que los cifrados basados en SHA-1 pueden comprometer las comunicaciones vía webmail entre los operadores jurídicos y los tribunales de justicia? y de ser así, ¿existe una alternativa real a SHA-1?
Os ruego «claridad de exposición».
Realmente no sabría decir si el actual estado de seguridad de SHA-1 puede comprometer el actual estado de las comunicaciones. Yo sinceramente creo que no. Es cierto que la Dr. Wang y su equipo han conseguido encontrar colisiones más rápido de lo esperado, pero encontrar una colisión contra un mensaje que además de generar la misma huella digital sea semánticamente correcta y coherente, creo que está aún lejos.
Lo que sí que existen son alternativas a SHA-1, y son los denominados algoritmos SHA-2, variantes de SHA-1 donde la huella digital generada varía entre 256 y 512 bits. Tenemos, pues, SHA-256, SHA-384 y SHA-512. A día de hoy, intentar encontra una colisión contra una huella generada con SHA-512 supondría, por fuerza bruta, unas 2^256 operaciones, lo que está muy lejos computacionalmente de las 2^80 de SHA-1.
Por esta razón, si alguien está realmente preocupado por el estadio de seguridad o inseguridad que aportan MD5 y SHA-1 que empiece a utilizar SHA-512. De momento, existen algún otro algoritmo de huella digital, pero SHA-512 está respaldado por la NSA. Si alguien utiliza SHA-512 en sus comunicaciones digital segura, ningún otro podrá acusarle de imprevisión o irresponsabilidad.
Suscribo todo lo expuesto por Noone en su último comentario. Así que no me extenderé en demasía. Solamente decir que, a día de hoy, SHA-1 sigue aportandonos una seguridad más que razonable (eso incluye a Lexnet). Digamos que si antes la seguridad con SHA-1 en la mayoría de los casos era del 99’99% (asumiendo que la seguridad absoluta no existe), ahora será del 99’8% (sobre todo para el caso de la propiedad de integridad).
Total Don M@x, y volviendo al tema del fax, que algunos medios de comunicación montaron el escándalo a partir de algo que no foma parte del procedimiento sino que se hace por pura cortesía.
Sobre eso de que «lo probable y lo posible en Derecho es fundamental» o de que «en la informática forense (o pericial) en muchas ocasiones no es posible utilizar términos como nunca, siempre, nada, o todo» me vais a permitir que os cuente un chiste:
Estaban un matemático, un físico y un ingeniero en una discoteca cuando se percatan de que dos personas se van acercando de tal manera que cada 10 segundos reducen su distancia a la mitad. Preguntados los tres sobre cuando se reunirán el matemático contesta que en el infinito, el fsico dice que nunca y el ingeniero zanja el tema con un «en la práctica dentro de 2 minutos».
Pues eso, que dependiendo del caso el abogado se pondrá el sobrero de matemático, o de físico, pero en la práctica lo que cuenta es lo que dice el ingeniero, que a fin de cuentas es al que le tocará el marrón de construir otra foto con el mismo hash que la que le hizo la polica de trfico al c*br*n*z* que conducía de forma temeraria, o construir un paquete de información del tal manera que el LexNet se haga la picha un lío. A fin de cuentas si existen colisiones debe ser fácil encontrarlas, ¿no?
Desde mi punto de vista la correcta utilización de SHA-1 no compromete la seguridad de las aplicaciones (habla el ingeniero), eso y siendo posible (el físico), que no probable buscarle y encontrarle las cosquillas (el matemático).
ja,ja,ja
Mirad: si algún sistema de verdad requiere tantas garantías de resistencia ante colisiones (ya sea por motivos legales o de otro calibre), el problema se puede resolver empleando simultáneamente varios algoritmos de hash.
Ejemplo: sea un documento de carácter legal extremadamente importante, para realizar su firma digital baste con hallar su resumen digital con SHA-512 y RIPE-MD160, y luego que cada uno de dichos resúmenes sea cifrado con la clave privada RSA-2048 del firmante o emisor del documento.
Será posible hallar un mensaje que produzca una colisión con el resumen de otro con SHA-1 en 2^69 operaciones o menos, pero hacerlo para que ese mismo mensaje colisione simultéaneamente con SHA-512 y RIPE-MD160 cuando se trata de funciones hash distintas, será mucho, _mucho_ más complicado.
JuanCarlkos, muy bueno el chiste (yo conocía una versión similar pero uno de los tres era estadista). Y mejor aún la conclusión final.
Converjo de nuevo con NoOne (ahora acabo de entender el alias ;D ). El uso combinado de varias funciones hash incrementa notablemente la seguridad del documento. Miel sobre hojuelas (o como diría Homer Simpson: «Sólo el azúcar tiene más azucar»).
Estimado Pedro y lectores de blogespierre:
Algo tarde, pero bueno. Acabo de ver la referencia y quiero dar mi punto de vista. A tu pregunta «¿responden, en estos momentos, SHA-1 y MD5 al concepto de seguridad razonable atendido el estado de la técnica que predica nuestra normativa de firma electrónica?» pues yo creo que la respuesta más adecuada es sí.
Las posibilidades de encontrar colisiones en ambos algoritmos existen, pero soy, hoy por hoy, muy inaccesibles y difíciles, motivo por el cual defendía en el artículo que el hecho de que unos investigadores experimentales hayan logrado colisiones en tiempos inferirores a los de fuerza bruta, no implica necesariamente que mañana habrá un programita que nos convierta una cadena hash en la palabra código original. No conviene dramatizar.
Para mí, desde luego, ambos algoritmos responden perfectamente al concepto de seguridad. No menos cierto es que hay alternativas más seguras, como por ejemplo Tiger o WHIRPOOL, pero no por ello SHA-1 y MD5 dejan de serlo. Seguramente cuando las máquinas computadoras mejoren y sean mucho más veloces, los tiempos de ruptura aconsejen prescindir del uso de algoritmos de este tipo, pero desde luego ese día no ha llegado, ni personalmente auguro que llegue a medio plazo.
Saludos, y gracias por enlazar el documento. Un privilegio verlo reflejado en esta insigne bitácora 🙂
Como parece que este hilo va apagándose, voy a reavivar un poco las brasas.
Gracias a la gente de Hispasec, concretamente gracias a su boletín «una-al-día», he tenido conocimiento de un artículo muy interesante sobre el tema que nos ocupa.
Cito textualmente del mencionado boletín de Hispasec:
«Se trata de un corto artículo, en inglés, donde nos facilitan
dos archivos en formato .PS (PostScript) con dos documentos
absolutamente diferentes. No obstante, ambos archivos generan
la misma suma de control MD5.
Estos archivos se han podido generar utilizando una técnica
para la identificación de colisiones aleatorias en la función
de compresión MD5. Con solo algunas horas de proceso en un
ordenador PC fue posible la construcción de estos dos archivos
PostScript. En una presentación realizada en Eurocrypt 2005
(en ‘Más información’ facilitamos el enlace al archivo PDF de
dicha presentación) se explica someramente el funcionamiento
de esta técnica.»
El artículo en cuestión demuestra como es posible crear un documento distinto del original teniendo ambos el mismo hash MD5, y teniendo el documento «falso» contenido semántico totalmente coherente y relacionado con el documento original.
Más información:
Web
Attacking Hash Functions by Poisoned Messages – «The Story of Alice and her
Boss» (Eurocrypt 2005)
Mil perdones por el formato de mi anterior comentario, pero no ha salido como yo esperaba.
Por cierto, en «más información», a diferencia de lo que pueda parecer, hay dos enlaces, y no uno.
Buenas Tardes, tengo una llave privado y otra publico y necesito saber si me pueden ayudar es como conveierto, como valido esa informacion estoy muy desconcertado, soy programador y estoy desarrollando un sistema computacional el cual trabaja con firma digital se los agradeceria mucho.
saludos y gracias