Autentificaci´ on. Firma Digital Juan Tena Ayuso

1

Introducci´ on

En el ´ambito de la seguridad de las telecomunicaciones, junto al cl´asico requisito criptogr´afico de la privacidad o confidencialidad, se plantean tambi´en los de autenticidad del emisor (autenticidad de origen o de usuario) y de no falsificaci´on o alteraci´on del mensaje (autenticidad o integridad del mensaje). En efecto, adem´as del ataque criptoanal´ıtico habitual, en el cual el criptoanalista rival intercepta la comunicaci´on y trata de ‘descifrar’ su contenido (ataque pasivo), aquel puede intentar hacerse pasar por qui´en no es, digamos B, entablando comunicaci´on con otro usuario A. Por tanto, cuando A recibe un mensaje que pretende ser de B, necesita una forma de garantizar que realmente es B quien lo env´ıa. Una tal identificaci´on del usuario puede ser directa, comprobando una caracter´ıstica propia de aquel, o indirecta, cuando el usuario demuestra estar en posesi´on de una pieza secreta de informaci´on (suele tomar la forma de Desafio-Respuesta: se plantea una cuesti´on a la que s´olo el usuario leg´ıtimo puede responder). El atacante puede tambi´en alterar, o substituir por otro, un mensaje enviado por B a A. Los protocolos de autentificaci´on del mensaje tratan de garantizar la integridad del mensaje. Ambos problemas, autentificaci´on de usuario e integridad del mensaje, est´an estrechamente relacionados y la Criptograf´ıa de Clave P´ ublica permite dar una soluci´on simple y satisfactoria a los mismos. De hecho esta fue (junto con el problema de la distribuci´on de llaves), una de las razones que llevaron a Diffie y Hellman a la introducci´on de dicha Criptograf´ıa. La firma digital, en tanto que an´alogo criptogr´afico de la firma ordinaria, puede considerarse un caso particular de autentificaci´on. Sin embargo presenta caracteristicas propias y una importancia creciente (que desborda el ´ambito criptogr´afico) lo que hace conveniente un tratamiento diferenciado.

2

M´ etodos de Autentificaci´ on

Antes de abordar de manera general el problema, consideremos un caso particular, que mostrar´a como pueden garantizarse los objetivos mencionados de autenticidad de usuario e integridad del mensaje utilizando el criptosistema RSA (ver [3], en este mismo volumen). El remitente j, que desea autentificar un mensaje M , enviado a i, cifra este con su propia llave privada dj (en lugar de hacerlo con la p´ ublica del destinatario, como en el caso

180

Juan Tena Ayuso

en que el objetivo buscado era la confidencialidad de M ). A la recepci´on, i descifra con la llave p´ ublica de j y recupera M dj ej ≡ M (mod nj ) La autenticidad del remitente es evidente, porque solo j ha podido cifrar tal mensaje. La integridad del mensaje queda asimismo garantizada, porque puede probarse que la probabilidad de que un falso mensaje se descodifique correctamente con la clave p´ ublica de j es pr´acticamente nula. El proceso anterior queda ‘ilustrado’ en la figura siguiente en la que el uso del RSA se representa mediante una caja fuerte con dos llaves.

El esquema de autentificaci´on, descrito anteriormente, no proporciona sin embargo secreto (ya que cualquiera puede tener acceso a la clave p´ ublica de j y por tanto puede leerlo). Si se desea conjugar ambos aspectos puede cifrarse dos veces, seg´ un el esquema siguiente: supongamos j, con claves (nj , ej , dj ) desea enviar M a i, con claves (ni , ei , di ). Distingamos (por razones t´ecnicas) dos casos: • Si ni < nj , M se cifra como [M ei (modni )]dj (modnj )  e • Si nj < ni , M se cifra como M dj (modnj ) i (modni ) El proceso se representa en la figura de la p´agina siguiente. Planteemos ahora el problema de la autentificaci´on de manera general. Los procesos de autentificaci´on constituyen un tipo particular de una amplia gama de aplicaciones criptogr´aficas que reciben el nombre gen´erico de Protocolos Criptogr´aficos (ver [9], para otros tipos de protocolos).

Autentificaci´on. Firma Digital

181

Objetivos de un protocolo de autentificaci´ on de usuario 1. Debe permitir a una parte A demostrar a otra B su identidad. 2. Tras un protocolo de autentificaci´on entre A y B, este u ´ltimo no debe poder utilizar la informaci´on obtenida de A para suplantarlo ante C. 3. La probabilidad de que C, ejecutando el protocolo, pueda conseguir ser aceptado por B como A es despreciable. Un tal protocolo utiliza, como herramientas, diversas funciones criptogr´aficas. Podemos clasificarlas en tres tipos: • Cifrado: El remitente y/o el mensaje se autentifican con un algoritmo de cifrado. 1. Con clave privada: Proporcionan autentificaci´on impl´ıcita: si el receptor del mensaje, al descifrar con la llave que comparte con quien dice enviarselo, obtiene un mensaje con sentido sabe que la probabilidad de que un atacante, sin acceso a la llave, haya podido crear un falso mensaje cifrado es pr´acticamente nula (tal hecho est´a basado en la redundancia de los lenguajes naturales, ver [8]). 2. Con clave p´ ublica: El mensaje, cifrado con la llave privada del remitente, garantiza la autenticidad de origen y de contenido. Es el caso del ejemplo antes descrito con el algoritmo RSA.

182

Juan Tena Ayuso

• MAC (Message Authentication Codes) Definici´ on 2.1. Un MAC es un bloque de de tama˜ no fijo Ck (M ), obtenido a partir de un mensaje M , de cualquier longitud y k una llave secreta compartida por dos usuarios A, B, el cual se adjunta al mensaje: (M, Ck (M )). Ejemplo 2.2. El Data Authentication Algorithm, basado en DES, obtiene un MAC de 64 bits, ver [4]. • Funciones hash o funciones resumen Definici´ on 2.3. Una funci´on hash es una funci´on de una v´ıa, p´ ublicamente conocida (a diferencia del MAC no utiliza ninguna llave) que produce, a partir de un mensaje M de longitud variable, un bloque H(M ) de longitud fija Requerimientos de una funci´ on hash 1. h = H(M ) debe ser f´acil de computar. 2. Conocido h debe ser computacionalmente imposible encontrar un M tal que H(M ) = h. 3. Dado M debe ser computacionalmente imposible encontrar un mensaje M 0 6= M tal que H(M 0 ) = H(M ). Si adem´as se verifica, 4. Es computacionalmente imposible encontrar dos mensajes (M, M 0 ) tales que H(M ) = H(M 0 ), se habla de funci´on hash fuerte (permite evitar ataques basados en la denominada paradoja del cumplea˜ nos, ver [6]) Ejemplo 2.4. Diferentes modelos de funciones hash han sido propuestos. Los m´as conocidos actualmente son el SHA (Secure Hash Algorithm) y el MD5 (Message Digest 5), que producen un comprimido de 128 bits del mensaje. Ver [7] o [4]. Nota 2.5. Las funciones hash constituyen una herramienta importante en Criptograf´ıa (por ejemplo constituyen un ingrediente fundamental de la firma digital, como veremos m´as adelante) y en otras ramas.

Protocolos de Desaf´ıo-Respuesta Definici´ on 2.6. Son protocolos que demuestran la identidad de una parte A a otra B (el verificador), demostrando la posesi´on de un cierto secreto (sin revelar este). Para ello A debe proporcionar una respuesta a un cierto desaf´ıo planteado por el verificador. Habitualmente tal respuesta debe ser dada en un plazo determinado. De no hacerlo as´ı B considerar´a terminado el protocolo y fallida la autentificaci´on.

Autentificaci´on. Firma Digital

183

Desaf´ıo-Respuesta con clave p´ ublica Aunque existen protocolos basados en t´ecnicas simetricas, como el Kerberos (ver [7]) nos limitamos aqu´ı al caso de clave p´ ublica. Supondremos pues que A posee un par de llaves (CA , DA ). Para identificarse demuestra al verificador B que posee su llave privada DA (sin revelar esta). 1. Descifrando un desaf´ıo cifrado con su llave p´ ublica: Para ello B env´ıa a A : (IB , e = CA (r)) donde IB es el identificador de B, r un n´ umero aleatorio, y e es el desaf´ıo propiamente dicho. A debe descifrar e utilizando su clave privada, recuperar r y enviarlo a B (en el plazo preestablecido). B acepta la identificaci´on si el n´ umero recibido coincide con el r enviado. 2. Firmando un desaf´ıo con su llave privada: En este caso B env´ıa a A : (IB , rB ), con rB aleatorio. A construye y env´ıa el vector (rA , IB , DA (rA , rB , IB ). B descifrar´a la u ´ltima componente (utilizando la clave p´ ublica de A), comprobar´a que los IB y rA que obtiene coinciden con los que estaban en claro en las dos primeras componentes y que rB coincide con el que envi´o.

Protocolos de Conocimiento Cero En los protocolos de desaf´ıo-respuesta, aunque A no revela el secreto, en el proceso cierta informaci´on puede ser conseguida por B. Definici´ on 2.7. Una prueba de conocimiento cero permite a una persona demostrar a otra que posee un secreto, sin que esta u ´ltima pueda obtener en el proceso ninguna informaci´on que no hubiese podido obtener por si sola. Nota 2.8. Nos limitaremos aqu´ı al uso de las pruebas de conocimiento cero en los protocolos de autentificaci´on, aunque el tema sea m´as amplio, ver [6] o [5]. Las pruebas de conocimiento cero adoptan la forma de una demostraci´on interactiva, implicando un cierto n´ umero de etapas. En cada etapa: • B presenta un desaf´ıo a A. • A realiza una cierta computaci´on privada. • A env´ıa a B una respuesta al desaf´ıo planteado. Si alguna de las respuestas es incorrecta B considera que A no posee el secreto y rechaza su autenticidad. Por contra si todas son correctas la acepta.

184

Juan Tena Ayuso

Condiciones de una prueba de conocimiento cero: a) Si A posee el secreto siempre puede conseguir que B acepte su demostraci´on. b) Si A no posee el secreto la probabilidad de que enga˜ ne a B puede hacerse tan peque˜ na como se quiera. Veamos un par de protocolos de autentificaci´on basados en pruebas de conocimiento cero.

Protocolo de identificaci´ on de Fiat-Shamir Requerimientos previos: 1. Una tercera parte confiable T ha elegido y hecho p´ ublico n = pq, p, q primos, guardando p, q secretos. 2. A elige el secreto s, 1 ≤ s ≤ n − 1 y computa v = s2 (mod n), que registra con T como llave p´ ublica. Algoritmo 2.9. Consta de t rondas (por ejemplo t=50) cada una implicando 3 intercambios de mensajes. 1. A elige aleatoriamente r, 1 ≤ r ≤ n − 1 y env´ıa a V el testigo x = r2 (mod n). 2. V elige y env´ıa a A, e ∈ {0, 1}. 3. A computa y env´ıa a V : y = r, si e = 0. y = rs, si e = 1. 4. Si y = 0, V rechaza la prueba (r 6= 0). Caso contrario la acepta si y solo si y 2 ≡ xv e (mod n). Nota 2.10. Un adversario impersonando A puede enviar a V , x = r2 /v. Podr´ıa entonces responder (correctamente) y = r si e = 1, pero no si e = 0. Luego tendr´ıa una probabilidad 1/2 de acierto en cada ronda.

Autentificaci´on. Firma Digital

185

Protocolo de identificaci´ on de Schnorr Basado en el problema del logaritmo discreto. Requiere solo tres intercambios de mensajes. Requerimientos previos: 1. Una tercera parte confiable T ha elegido: a1) p primo, q primo, q|p − 1, (p ∼ 21024 , q ∼ 2160 ). a2) 1 ≤ β ≤ p − 1 de orden q (mod p) a3) Cada participante posee copia autentificada de (p, q, β) a4) Un par´ametro de seguridad t, t ≥ 40, 2t < q. 2. Par´ametros de A, b1) Identificador IA b2) Llave privada 0 ≤ a ≤ q − 1 b3) Llave p´ ublica v = β −a (mod p) b4) Certificado emitido por T : CertA = (IA , v, DT (IA , v)) (DT llave privada de T ). Algoritmo 2.11. 1. A elige aleatoriamente r, 1 ≤ r ≤ q − 1 y env´ıa a V : CertA , x ≡ β r (mod p). 2. Tras verificar la llave p´ ublica de A, V elige y env´ıa a A, 1 ≤ e ≤ 2t . 3. A env´ıa a V , y ≡ ae + r (mod q). 4. V acepta la identidad de A si z ≡ β y v e (mod p) = x.

3

Firma Digital

El desarrollo del comercio electr´onico y de los requerimientos de autentificaci´on, hacen necesario un an´alogo electr´onico de la firma ordinaria, incluso con valor legal, para zanjar disputas respecto a la autenticidad de documentos transmitidos electr´onicamente. Ello confiere a la firma digital obvias implicaciones econ´omicas, pero tambi´en legislativas y jur´ıdicas, como lo muestra el inter´es reciente del mundo del derecho por el tema y la legislaci´on a la que ha dado lugar: Real Decreto-ley de firma electr´onica de 17/9/1999, LSSI, directivas europeas, etc. La firma electr´onica debe tener pues una serie de propiedades formalmente an´alogas a las de la firma escrita ordinaria. En particular:

186

Juan Tena Ayuso

• Personal: Solo el propietario puede producirla. • Infalsificable: El intento, por parte de un usuario ilegal, de falsificar tal firma debe ser computacionalmente imposible. • F´ acil de Autentificar: El receptor y eventualmente un arbitro o juez, deben ser capaces de atestiguar, la autor´ıa de la firma. • No repudiaci´ on: El autor de la firma no debe tener la posibilidad de rechazarla como falsa. • F´ acil de Generar. Nota 3.1. Sin embargo, a diferencia de la firma ordinaria, que es siempre la misma, la firma digital depende del mensaje particular firmado. Se trata de un requisito de seguridad ya que si la firma fuese independiente del mensaje y a˜ nadida a este, un criptoanalista que intercepte un tal mensaje firmado, puede substituir el mensaje propiamente dicho por otro falso, pero conservando la firma final. Tal falsificaci´on tendr´ıa entonces la garant´ıa de una firma leg´ıtima. Un esquema de firma digital comporta dos partes: 1. Algoritmo de firma 2. Algoritmo de verificaci´on de la firma El algoritmo de firma puede ser, Definici´ on 3.2. Determinista: Dos firmas del mismo mensaje producen el mismo resultado (por ejemplo las firmas basadas en RSA). Aleatoria: dependiente de un conjunto de ´ındices (por ejemplo las basadas en ElGamal). Por otra parte existen dos tipos fundamentales de esquemas de firma, Definici´ on 3.3. Esquema de firma con recuperaci´ on del mensaje: El mensaje firmado se recupera durante el proceso de verificaci´on de la firma. Es el proceso esquematizado al comienzo de la secci´on de autentificaci´on. Esquema de firma con ap´ endice: Requieren el mensaje original como input para la verificaci´on de la firma.

Autentificaci´on. Firma Digital

187

Las firmas con recuperaci´on del mensaje tienen el inconveniente de tener que cifrar (dos veces si se desea garantizar secreto y autenticidad) todo el mensaje a autentificar, el cual puede ser muy largo, con clave p´ ublica (que es muy lenta). En consecuencia, para firmar un mensaje, habitualmente se obtiene previamente un comprimido de peque˜ no tama˜ no del mensaje, que es lo que se cifra para obtener la firma. Tales comprimidos se obtienen utilizando las funciones hash anteriormente descritas. Un protocolo de firma digital con ap´endice de un mensaje M (eventualmente cifrado previamente, por ejemplo con clave privada, para garantizar el secreto) ser´ıa como sigue:

Algoritmo 3.4. 1. Obtener el comprimido hash H(M ) y su firma F (H(M )) (obtenida con la llave privada del remitente, por ejemplo la llave privada de RSA). 2. Enviar el par (M, F (H(M ))). 3. El receptor calcula H(M ) por dos caminos: a partir del primer elemento del par y de la funci´on (p´ ublicamente conocida) H y a partir del segundo elemento (aplic´andole la llave p´ ublica del remitente). 4. El receptor compara los dos valores de H(M ) obtenidos, aceptando el mensaje si coinciden y rechaz´andolo en caso contrario. 5. Eventualmente, si M estaba previamente cifrado, el receptor lo descifrar´a para obtener el mensaje en claro.

Tipos de ataques El objetivo para un atacante a un proceso de firma digital es forjar firmas que sean aceptadas como v´alidas. Seg´ un el ´ambito de tales falsificaciones se habla de: 1. Rotura total: El atacante posee un algoritmo de firma funcionalmente equivalente al aut´entico. 2. Rotura selectiva: El atacante es capaz de forjar una firma para un tipo particular de mensaje. 3. Rotura existencial: El atacante es capaz de forjar una firma para al menos un mensaje.

188

Juan Tena Ayuso Para m´as detalles ver [4].

Aunque diversos protocolos de firma basados en la Criptograf´ıa de clave privada han sido propuestos (como por ejemplo el esquema de Lamport-Diffie, ver [5]) la Criptograf´ıa de clave p´ ublica permite resolver mucho m´as eficientemente el problema. Dado que el proceso de firma con RSA ha sido ya esquematizado veamos dos esquemas de firma basadas en el problema del logaritmo discreto.

Firma digital de ElGamal Requerimientos previos: 1. Se ha elegido un primo adecuado p (con p ∼ 200 bits) y un elemento primitivo g (generador del grupo multiplicativo Fp∗ ). 2. El firmante elige una llave secreta n, 1 < n < p − 1 y hace p´ ublica K ≡ g n mod p. Algoritmo 3.5. Para firmar un mensaje M (o el comprimido hash del mismo h(M )) 1. Se elige aleatoriamente un n´ umero k, mcd(k, p − 1) = 1 y se computa X ≡ g k mod p. 2. Se despeja Y de la congruencia M ≡ nX + kY mod p − 1. 3. Firma: (M, f (M ) = X, Y ) 4. Verificaci´ on de la firma: Sea A ≡ K X X Y . La firma se acepta como v´alida si A ≡ M g mod p.

Esquemas DSA y DSS En 1991 el USA National Institute of Standards and Technology (NIST) propuso el algoritmo DSA (Digital Signature Algorithm). El DSA fue adoptado como standard DSS (Digital Signature Standard). Tal standard utiliza como funci´on hash el SHA-1. Requerimientos previos: 1. Con el objetivo de reducir la longitud de la firma (y por tanto el coste computacional de su generaci´on y verificaci´on) se eligen dos primos: p con 512 bits y q con 160 bits y divisor de p − 1. Se elige tambi´en un elemento g ∈ Fp de orden q. 2. El firmante elige una llave secreta n, 1 < n < q y hace p´ ublica K ≡ g n mod p. Algoritmo 3.6. Para firmar un mensaje M , 1 < M < p 1. Se elige aleatoriamente un n´ umero k, 1 < k < q).

Autentificaci´on. Firma Digital 2. Se computan r ≡ [g k mod p] mod q y s ≡

189 M +nr k

mod q.

3. Firma: (M,f(M)=r,s). 4. Verificaci´ on de la firma: Sean w ≡ s−1 mod q, u ≡ M w mod q y v ≡ rw mod q. La firma se acepta como v´alida si r ≡ [g u K v mod p] mod q.

Tipos particulares de Firmas Digitales Existen tipos de firmas digitales con propiedades o requerimientos particulares. Esquematicemos brevemente algunas de tales firmas. M´as detalles pueden encontrarse en [4] o [6]. Firmas de un solo uso: Solo pueden ser empleadas una vez. Tienen la ventaja de su bajo coste computacional, lo que las hace indicadas para plataformas como las tarjetas inteligentes. Firmas en presencia de arbitro: Una tercera parte confiable participa en los procesos de firma y de verificaci´on. Firmas ciegas: Permiten a una parte A conseguir que otra B (una cierta autoridad) firme un mensaje M sin que en el proceso B pueda conocer el contenido de M . Firmas no repudiables (undeniables): El proceso de verificaci´on requiere la participaci´on activa del firmante. Si este rehusa hacerlo puede interpretarse como culpabilidad. Si realiza la verificaci´on incorrectamente o bien tr´as el protocolo declara que la firma no es suyo, existe un segundo protocolo de desacuerdo. Firmas Fail-Stop: Permiten a A probar que una firma, supuestamente suya, es falsa. Firmas de Grupo: Pueden ser realizadas por cada miembro de un cierto grupo de personas.

Bibliograf´ıa [1] P. Alegr´ıa, M.A. Garc´ıa, I. Martinez, J. Tena, A. Vera, Aplicaciones de las Matem´ aticas. Editorial Antonio Vera, 2002. [2] A. Fuster, D. de la Gu´ıa, L. Hernandez, F.Montoya, J.Mu˜ noz, T´ecnicas Criptogr´aficas de protecci´on de datos. Ed. Ra-Ma, 1997. [3] J. Guti´errez, A. Ibeas, Criptograf´ıa. Protocolos Criptogr´aficos y Seguridad en Redes. (Eds. J. Gutierrez, T. Ayuso), Servicio de Publicaciones Universidad de Cantabria, 2003.

190

Juan Tena Ayuso

[4] A.J. Menezes, P.C van Oorschot, S.A. Vanstone, Handbook of Applied Cryptography. C.R.C., 1997. [5] J. Pastor, M.A. Sarasa, Criptograf´ıa Digital. Fundamentos y Aplicaciones. Prensas de la U. de Zaragoza, 1997. [6] B. Schneider, Applied Criptography. J. Wiley, 1994. [7] W. Stalling, Cryptography and Network Security. Prentice Hall, 1998. [8] D.R. Stinson, Cryptography. Theory and Practice, C.R.C., 1995. [9] J. Tena, Protocolos Criptogr´ aficos. Protocolos Criptogr´aficos y Seguridad en Redes. (Eds. J. Gutierrez, T. Ayuso), Servicio de Publicaciones Universidad de Cantabria, 2003.