Firma digital

Una de las creencias más extendidas, y que más me asusta, es aquella que hace parecer a la firma digital un sustituto infalible de la firma escrita.

Fundamentalmente, la firma digital se apoya en dos conceptos criptográficos:

  • Funciones criptográficas de clave pública

    Las más representativas son RSA (las siglas de Rivest, Shamir y Adleman) y DSA (las siglas de Digital Signature Algorithm, a veces también llamado DSS, Digital Signature Standard), o ElGammal.

  • Funciones criptográficas de resumen

    Las más representativas son MD5, SHA-1, la familia SHA-2 (SHA-256, SHA-384 y SHA-512) o RIPE-MD160.

Brevemente, para firmar digitalmente un documento, llamémoslo M, se calcula, mediante una función criptográfica de resumen, un resumen de éste, sea H:


[1] H = f(M)

A este resumen H también se le conoce como huella digital.

Posteriormente, se cifra esta huella digital H utilizando la clave privada del firmante. El resultado es lo que se conoce como firma digital.

El problema de la firma digital es que no se firma el documento original, sino un derivado de éste (en este caso, un resumen obtenido de él a partir de una función criptográfica de resumen). Tal y como se mostrará a continuación, existe un gran número de mensajes, distintos del mensaje original M, a los cuales, si se les aplica la función de resumen f(x), se obtiene el mismo resumen o huella digital H.

Por consiguiente, cuando se firma digitalmente un documento, en realidad, la firma digital resultante corresponde al documento original y a un número muy alto (teóricamente infinito) de documentos diferentes del original.

¿Qué ocurre si un individuo pudiera generar un documento M', distinto en contenido de M, pero semánticamente similar, tal que al resumir este M' se obtuviera la misma huella digital H que corresponde al documento original M? (véase [2]) ¿Qué ocurriría si este documento M fuese un documento PDF que contiene un contrato mercantil, y fuera posible hallar otro documento M', también en formato PDF, con un contrato mercantil similar al anterior pero distinto en importe o condiciones, pero que resume al mismo valor que M? Evidentemente, la validez de la firma digital quedaría en entredicho, siendo difícil argumentar a cual de los dos documentos representa. La respuesta correcta sería argumentar que la firma digital representa a ambos documentos.

Se ha visto que f(x) es una función de resumen criptográfica, como MD5. Esta función cumple una serie de propiedades, pero la más destacable es que genera un número infinito de colisiones: La cardinalidad del conjunto {M}, es decir, la cardinalidad del conjunto formado por todos los posibles mensajes M, tiende a infinito. Por el contrario, la cardinalidad del conjunto {H} formado por todos los posibles resúmenes o huellas digitales correspondientes a cada uno de los elementos del conjunto {M} es un número finito. Para la función MD5, equivale a 2128, para SHA-1 equivale a 2160, y para los miembros de la familia SHA-2, sean éstos SHA-256, SHA-384 y SHA-512, equivale a 2256, 2384 y 2512 respectivamente. Esto es consecuencia de [1].

Cuando se resume un mensaje M a través de una de estas funciones, se puede demostrar que existe, al menos otro mensaje M', distinto de M, que cumple:

[2] H = f(M) = f(M'), para M M'

Es más, para funciones criptográficas de resumen como las mencionadas anteriormente, lejos de la función ideal, se demuestra que existe un gran número (teóricamente infinito) de mensajes distintos de M que resumen al mismo valor que M (colisiones). De todos estos mensajes nos quedaremos con un M', de tal forma que sea éste un mensaje coherente con M (es decir, semánticamente similar o relacionado). Por ejemplo, si M es un documento en formato PDF, M' es también un documento en formato PDF, con un contenido muy similar, y que cumple la propiedad [2] anterior.

Para firmar digitalmente el documento M:


H = f(M)
FD = E(e, H)
, donde e es la clave privada utilizada para firmar

En el supuesto anterior, FD es la firma digital, H es la huella digital y M es el documento que se pretende firmar. Además, M' es tal que f(M') = f(M), lo cual es perfectamente posible, por lo que tenemos:


H' = f(M')
FD' = E(e, H')

pero como H' = H, entonces FD' = E(e, H') = E(e, H) = FD.

Como puede observarse, la firma digital FD representa no al documento original M, sino a sendos documentos M y M' simultáneamente. Ante un juez, ¿cuál de los dos es el que está firmado? Muy sencillo: ambos. Si ambos documentos entraran en contradicción, sería alto probable que la firma digital no tuviera validez legal alguna.

Ahora bien, ¿es ésto lo que quieren imponernos con el DNI digital? Espero que no.

Advertisements

15 thoughts on “Firma digital

  1. No sé tronko, no estoy muy puesto en el tema pero los principios básicos que debe tener una función hash son:

    * f(M) sea de longitud fija (independientemente de la longitud del mensaje M)
    * Que sea fácil calcular f(M) a partir de M
    * Que teniendo f(M) sea computacionalmente imposible recuperar M
    * Que sea computacionalmente imposible que se de: f(M) = f(M’)

    Este último aspecto es el que te preocupa, y como sabemos que la teoría y la práctica muchas veces no van de la mano, seguro que sí es posible que se de el último punto…

    … ahora bien, no creo que sea tan probable. Por lo poquito que sé, al menos en las funciones del tipo MDC (algo así como Modification Detection Codes), se incluye información sobre el tamaño del mensaje en f(M), con lo cual se reducen las posibilidades de que dos mensajes distintos den el mismo valor en su resumen.

    Por cierto, el SHA-1 ya lo han roto unos chinos así que se acabó el considerarlo seguro y libre de puertas traseras.

    Yyyy… del DNI electrónico pronto veremos qué tal funciona…. En marzo comienza a funcionar (una prueba piloto) no recuerdo si en Burgos o en Zaragoza….. Se irá extendiendo poquito a poco durante los meses siguientes dependiendo del resultado de esta prueba. No me llega a quedar muy claro si el dispositivo seguro de creación de la firma electrónica va en el propio chip del DNI; imagino que sí, ya que la firma del DNI electrónico se considera una firma electrónica avanzada y por tanto, el firmante debe mantener bajo su exclusivo control el medio por el que se crea… y dónde sino en el propio chip del DNI.

  2. Ah! y otra cosita para preocuparte un poquito más… por favor, si no es correcto lo que digo, que alguien me corrija pero: no se niega eficacia jurídica ni admisibilidad como prueba en un juicio a una firma electrónica (ni siquiera tiene que ser avanzada) aunque no se base en un certificado reconocido o éste no haya sido expedido por un prestador acreditado o no esté creada por un dispositivo seguro de creación…..

    … creo que estoy en lo cierto! (aunque cueste creerlo a priori!)

  3. Las tres primeras características que has comentado las cumplen casi todas las funciones hash que existen en la actualidad. El problema es que la última no.

    Por ejemplo, con SHA-1 es posible encontrar un mensaje M’ a partir de otro mensaje M, de manera que resuman al mismo H en 2^69 pasos (en lugar de 2^80, que sería el caso normal para ataques por fuerza bruta), tal y como han encontrado “los famosos Chinos”.

    Si miras el enlace del mensaje original, verás cómo es posible fabricar dos certificados X.509 con la misma firma digital, y también dispongo de un enlace que hace exactamente lo mismo con dos documentos PDF.

    Con respecto a incluir el tamaño del mensaje en el cálculo f(M), esto añade cierta resistencia, pero en el caso de documentos electrónicos con formatos binarios estrictos (como X.509 que usa ASN.1) es posible hacer ciertas modificaciones al documento para obtener otro diferente que genera el mismo resumen (en enlace del artículo original hace eso, precisamente).

    Así mismo, la función SHA-1 y MD5 incluyen “padding” en el cálculo del resumen, pero esto no evita los ataques de extensión.

    Actualmente, la única forma segura de implementar firma digital es utilizar una función resumen de la familia SHA-2 (como SHA-256, por ejemplo).

  4. Genial, lo que faltaba… ¿me estás diciendo que puedo firmar digitalmente un documento con un certificado que no esté reconocido a nivel mundial, como Entrust o Verisign, y ante un juez tiene validez legal?

  5. Nooop! no digo que tenga validez legal… lo que digo es que no por no reunir las características que te comentaba se descarte su posible validez legal… Vamos, que no se rechaza de entrada sino que se estudia si realmente puede tener validez (en unos se determinará que sí la tiene y en otros que no)

    De todas formas de esto no estoy 100% seguro (lo oí en la charlita de seguridad que tuve hace un par de meses en uno de los hoteles Melia Castilla, a la que pude asistir gracias a mi jefa).

  6. Pingback: meneame.net

  7. A mí me parece muuuucho más preocupante que lo que plantea el autor el hecho, casi sin trascendencia en los medios, de que el responsable del DNI digital fuera detenido el año pasado por traficar con los datos de los españolitos…

    Lo del MD5… minucias…

  8. La teoría dice que existen infinitos M’ de M, igual que dice que hay infinitos números primos. El problema es que encontrarlos requiere una gran (infinita en teoría) potencia de calculo. Lo que se ha conseguido es crear M y M’ con el mismo hash, no encontrar M’ a partir de M (preimagenes).
    A la firma digital le pasa lo mismo que a la manuscrita. Nosotros no vamos siempre acompañados de un calígrafo que de fe de que todas las firmas que hacemos son nuestras. Firmamos y, el que diga que es falsa, que lo demuestre con su calígrafo.
    Por ahora es peligroso presentarle a un juez un M y un M’ con el mismo hash, ya que implica que los has generado antes de darle a firmar a alguien un documento, es decir, que te delatas tu mismo.
    Otro tema es que la firma electrónica depende mucho de la resolución del programador que la implementa. Por ejemplo yo no cifro el hash del documento, yo cifro un encadenamiento de distintas funciones hash de un documento, es decir, que si tengo el documento M, le aplico un MD5, un SHA1, y un RIPE-MD160, por ejemplo, y esos resultados encadenados es lo que le doy al usuario a firmar con su certificado. El usuario le aplicara la función hash de su certificado, MD5 por ejemplo, y lo cifrara con su privada. El M’ tendría que ser un documento que tuviese el mismo MD5, SHA1, y RIPE-MD160 que M, una triple colisión vamos.

  9. Con respecto a M y M’, es cierto que los actuales ataques contra MD5, SHA-0 y SHA-1 son ataques por colisión y no por pre-imagen. En cualquier caso, es posible montar un ataque por fuerza bruta de pre-imagen contra MD5 en aproximadamente 2128 pasos, que aunque es muy superior a los 269 pasos de un ataque por colisión, sigue siendo factible para ataques contra documentos, como contratos mercantiles, que tienen una durabilidad muy alta (varios años). Además, hay que contar con lo que dice la NSA, y es que los ataques son cada vez mejores, nunca peores, por lo que no es decartable que en un futuro no muy lejano se pueda romper MD5 fácilmente.

    También estoy totalmente de acuerdo que al utilizar tres funciones hash diferentes se incrementa notablemente la seguridad de la firma digital. El problema es que la mayoría de los sistemas de hoy en día se limitan a una sola función de resumen, normalmente MD5. Afortunadamente, ya existen diversos grupos de trabajo en el IETF para cambiar estándares como Kerberos, IPSec o DNSSec de manera que se contemplen funciones más seguras coma SHA-256, por lo menos.

  10. Estoy de acuerdo en que en un futuro los ataques serán mejores, pero en los comentarios se hablaba de en la actualidad.
    No estoy de acuerdo en lo de que sea factible un ataque por fuerza bruta de 2^128.
    Supongamos que tenemos un Earth Simulator/5120 Nec con una potencia teórica (nunca a llegado a tanto) de 40.960 billones de operaciones por segundo.
    Supongamos que en cada operación es capaz de áplicar hash y ver si hay colisión (serían cientos de operaciones).
    Existen:
    2^128 = 340.282.366.920.938.592.532.472.206.020.233.786.982 claves posibles.

    340.282.366.920.938.592.532.472.206.020.233.786.982 / 40.960.000.000.000.000 = 8.307.674.973.655.724.205.649 Segundos.
    8.307.674.973.655.724.205.649 /60 = 138.461.249.560.928.736.761 Minutos
    138.461.249.560.928.736.761 / 60 = 2.307.687.492.682.145.612 Horas
    2.307.687.492.682.145.612 / 24 = 96.153.645.528.422.734 Días
    96.153.645.528.422.734 / 365 = 263.434.645.283.350 Años.

    No creo que un contrato dure tantos años 😉

  11. Por cierto, no hay que irse a ningún grupo de trabajo como el IETF para ver aplicaciones que usan encadenamiento de hash. Todos los navegadores que solportan TLS (la mayoría) usan encadenamiento de hash en la firma del handshake. Es decir casi todo el mundo que entra en un servidor seguro (TLS, no SSL) lo usa aunque no lo vea.

  12. Bueno, 2128 es el peor caso. Estadísticamente podría encontrarse un mensaje M’ en 280 pasos, lo cual es sustancialmente menor.

    Además, tal y como funcionan las funciones resumen, sería posible tomar el mensaje M, eliminar el último bloque (512 bits) y probar combinaciones de bloques distintos que, concatenados a M menos el último bloque generen el mismo resumen que M. Por supuesto, el trabajo sigue siendo igual en número de pasos, pero computacionalmente es más rápido calcular el resumen a partir de un estado intermedio que hacerlo desde el comienzo del mensaje.

  13. Bueno, si quieres calcular que potencia de calculo real es necesaria, tienes que coger el numero real de operaciones que tiene que hacer el procesador por cada calculo resumido que dices, y no una, como he puesto en el ejemplo, multiplicar por miles el tiempo vamos, y hacerlo con ordenadores reales, los que un interesado podría llegar a disponer para un fraude, no el ordenador mas rápido del mundo como he puesto en el ejemplo, y todo esto pasarlo a dinero, para ver si es rentable el fraude, aunque yo me se alguna colisión que si que lo sería, los raíces de alguna CA, por ejemplo 😉
    Un caso peor que el de 2^128 sería, por ejemplo, el encadenamiento del TLS 2^288, MD5+SHA1

  14. Estoy de acuerdo contigo, pero la complejidad de la mayoría de los ataques se miden en “pasos”, independientemente de lo que signifique paso. Evidentemente, no todo el mundo tiene acceso a supercomputadoras, pero nunca hay que menospreciar a los gobieros y agencias de inteligencia.

    En el caso del encadenamimento de SHA-1 y MD5, el proceso resulta tremendamente complicado, ya que los ataques contra ambas funciones son diferentes y encontrar un M y M’ que cumplan las condiciones de colisión para ambos es cualquier cosa menos trivial. Si añadimos RIPE-MD160, la complejidad es incalculable actualmente. De hecho, es el sistema que utiliza FreeBSD para la verificación de las fuentes en los ports: cada archivo de código fuente se resume con SHA-1, MD5 y RIPE-MD160 de forma separada.

    En cualquier caso, tampoco hay que ser alarmistas. Los recientes ataques contra MD5 y SHA-1 son sólo un aviso de que hay que empezar a investigar más y mejor en funciones criptográficas de resumen pero, a día de hoy, SHA-1 es suficientemente seguro para el uso en transacciones comerciales (lo cual no quita que siempre me gusta ponerme en la posición más derrotista y negativa, como buen paranoico de la seguridad que soy).

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s