El intercambio de claves Diffie–Hellman ( DH ) [nb 1] es un método matemático para generar de forma segura una clave criptográfica simétrica a través de un canal público y fue uno de los primeros protocolos de clave pública concebido por Ralph Merkle y nombrado en honor a Whitfield Diffie y Martin Hellman . [1] [2] DH es uno de los primeros ejemplos prácticos de intercambio de claves públicas implementado en el campo de la criptografía. Publicado en 1976 por Diffie y Hellman, este es el primer trabajo conocido públicamente que propuso la idea de una clave privada y una clave pública correspondiente.
Tradicionalmente, la comunicación cifrada segura entre dos partes requería que primero intercambiaran claves por algún medio físico seguro, como listas de claves en papel transportadas por un mensajero de confianza . El método de intercambio de claves Diffie-Hellman permite que dos partes que no tienen conocimiento previo entre sí establezcan conjuntamente una clave secreta compartida a través de un canal inseguro . Esta clave puede luego usarse para cifrar comunicaciones posteriores utilizando un cifrado de clave simétrica .
El protocolo Diffie-Hellman se utiliza para proteger diversos servicios de Internet . Sin embargo, una investigación publicada en octubre de 2015 sugiere que los parámetros que se utilizaban en muchas aplicaciones de Internet DH en ese momento no eran lo suficientemente sólidos como para evitar que los ataques con fondos muy altos, como los servicios de seguridad de algunos países, los comprometieran. [3]
El esquema fue publicado por Whitfield Diffie y Martin Hellman en 1976, [2] pero en 1997 se reveló que James H. Ellis , [4] Clifford Cocks y Malcolm J. Williamson de GCHQ , la agencia de inteligencia de señales británica, habían demostrado previamente en 1969 [5] cómo se podía lograr la criptografía de clave pública. [6]
Aunque el intercambio de claves Diffie-Hellman en sí es un protocolo de acuerdo de claves no autenticado , proporciona la base para una variedad de protocolos autenticados y se utiliza para proporcionar secreto hacia adelante en los modos efímeros de seguridad de la capa de transporte (denominados EDH o DHE según el conjunto de cifrados ).
El método fue seguido poco después por RSA , una implementación de criptografía de clave pública que utiliza algoritmos asimétricos.
La patente estadounidense 4.200.770 [7] , de 1977, ya vencida, describe el algoritmo, que ahora es de dominio público . Atribuye la invención a Hellman, Diffie y Merkle.
En 2006, Hellman sugirió que el algoritmo se llamara intercambio de claves Diffie-Hellman-Merkle en reconocimiento a la contribución de Ralph Merkle a la invención de la criptografía de clave pública (Hellman, 2006), escribiendo:
El sistema... se ha conocido desde entonces como intercambio de claves Diffie-Hellman. Aunque ese sistema fue descrito por primera vez en un artículo escrito por Diffie y por mí, es un sistema de distribución de claves públicas, un concepto desarrollado por Merkle, y por lo tanto debería llamarse "intercambio de claves Diffie-Hellman-Merkle" si se le asocian nombres. Espero que este pequeño púlpito pueda ayudar en ese esfuerzo por reconocer la contribución equivalente de Merkle a la invención de la criptografía de clave pública. [8]
El intercambio de claves Diffie-Hellman establece un secreto compartido entre dos partes que puede utilizarse para la comunicación secreta con el fin de intercambiar datos a través de una red pública. Una analogía ilustra el concepto de intercambio de claves públicas utilizando colores en lugar de números muy grandes:
El proceso comienza cuando las dos partes, Alice y Bob , acuerdan públicamente un color inicial arbitrario que no necesita mantenerse en secreto. En este ejemplo, el color es amarillo. Cada persona también selecciona un color secreto que se guarda para sí misma: en este caso, rojo y cian. La parte crucial del proceso es que Alice y Bob mezclan cada uno su propio color secreto junto con su color compartido mutuamente, lo que da como resultado mezclas de naranja-marrón y azul claro respectivamente, y luego intercambian públicamente los dos colores mezclados. Finalmente, cada uno de ellos mezcla el color que recibió de su pareja con su propio color privado. El resultado es una mezcla de colores final (amarillo-marrón en este caso) que es idéntica a la mezcla de colores final de su pareja.
Si un tercero escuchara el intercambio, solo conocería el color común (amarillo) y los primeros colores mezclados (naranja tostado y azul claro), pero le resultaría muy difícil descubrir el color secreto final (amarillo marrón). Si volvemos a la analogía de un intercambio de la vida real en el que se utilizan grandes números en lugar de colores, esta determinación es computacionalmente costosa. Es imposible calcularla en un tiempo práctico incluso para las supercomputadoras modernas .
La implementación más simple y original, [2] formalizada posteriormente como Finite Field Diffie–Hellman en RFC 7919 , [9] del protocolo utiliza el grupo multiplicativo de números enteros módulo p , donde p es primo y g es una raíz primitiva módulo p . Estos dos valores se eligen de esta manera para garantizar que el secreto compartido resultante pueda tomar cualquier valor entre 1 y p –1. Aquí hay un ejemplo del protocolo, con valores no secretos en azul y valores secretos en rojo .
Tanto Alice como Bob han llegado a los mismos valores porque bajo mod p,
Más específicamente,
Solo a y b se mantienen en secreto. Todos los demás valores ( p , g , g a mod p y g b mod p ) se envían sin cifrar. La fortaleza del esquema proviene del hecho de que g ab mod p = g ba mod p tarda muchísimo tiempo en calcularse mediante cualquier algoritmo conocido solo a partir del conocimiento de p , g , g a mod p y g b mod p . Una función de este tipo, que es fácil de calcular pero difícil de invertir, se denomina función unidireccional . Una vez que Alice y Bob calculan el secreto compartido, pueden usarlo como una clave de cifrado, conocida solo por ellos, para enviar mensajes a través del mismo canal de comunicaciones abierto.
Por supuesto, se necesitarían valores mucho mayores de a , b y p para que este ejemplo fuera seguro, ya que solo hay 23 resultados posibles de n mod 23. Sin embargo, si p es un primo de al menos 600 dígitos, entonces incluso las computadoras modernas más rápidas que usan el algoritmo más rápido conocido no pueden encontrar un solo g , p y g a mod p dados . Un problema de este tipo se llama problema del logaritmo discreto . [3] El cálculo de g a mod p se conoce como exponenciación modular y se puede realizar de manera eficiente incluso para números grandes. Tenga en cuenta que g no necesita ser grande en absoluto, y en la práctica suele ser un entero pequeño (como 2, 3, ...).
El gráfico que aparece a continuación muestra quién sabe qué, nuevamente con los valores no secretos en azul y los valores secretos en rojo . Aquí Eve es una espía : observa lo que se envía entre Alice y Bob, pero no altera el contenido de sus comunicaciones.
Ahora s es la clave secreta compartida y tanto Alice como Bob la conocen, pero Eve no . Nótese que no es útil para Eve calcular AB , que es igual a g a + b mod p .
Nota: Debería ser difícil para Alice resolver la clave privada de Bob o para Bob resolver la clave privada de Alice. Si no es difícil para Alice resolver la clave privada de Bob (o viceversa), entonces un espía, Eve , puede simplemente sustituir su propio par de claves pública/privada, conectar la clave pública de Bob en su clave privada, producir una clave secreta compartida falsa y resolver la clave privada de Bob (y usarla para resolver la clave secreta compartida). Eve puede intentar elegir un par de claves pública/privada que le facilite resolver la clave privada de Bob.
A continuación se presenta una descripción más general del protocolo: [10]
Tanto Alice como Bob están ahora en posesión del elemento de grupo g ab = g ba , que puede servir como clave secreta compartida. El grupo G satisface la condición requerida para una comunicación segura siempre que no haya un algoritmo eficiente para determinar g ab dados g , g a y g b .
Por ejemplo, el protocolo de curva elíptica Diffie-Hellman es una variante que representa un elemento de G como un punto en una curva elíptica en lugar de como un entero módulo n. También se han propuesto variantes que utilizan curvas hiperelípticas . El intercambio de claves de isogenia supersingular es una variante de Diffie-Hellman que se diseñó para ser segura contra las computadoras cuánticas , pero se rompió en julio de 2022. [11]
Las claves utilizadas pueden ser efímeras o estáticas (a largo plazo), pero también pueden ser mixtas, denominadas DH semiestáticas. Estas variantes tienen diferentes propiedades y, por lo tanto, diferentes casos de uso. Se puede encontrar una descripción general de muchas variantes y también algunas discusiones, por ejemplo, en NIST SP 800-56A. [12] Una lista básica:
Es posible utilizar claves efímeras y estáticas en un acuerdo de clave para proporcionar más seguridad, como se muestra, por ejemplo, en NIST SP 800-56A, pero también es posible combinarlas en un único intercambio de clave DH, que luego se denomina triple DH (3-DH).
En 1997, Simon Blake-Wilson, Don Johnson y Alfred Menezes propusieron una especie de triple DH [13] , que fue mejorada por C. Kudla y KG Paterson en 2005 [14] y se demostró que era segura.
Las claves secretas a largo plazo de Alice y Bob se denotan por a y b respectivamente, con claves públicas A y B , así como los pares de claves efímeras x, X e y, Y . Entonces el protocolo es:
Las claves públicas a largo plazo deben transferirse de alguna manera. Esto se puede hacer de antemano en un canal independiente y de confianza, o las claves públicas se pueden cifrar utilizando algún acuerdo de clave parcial para preservar el anonimato. Para obtener más detalles sobre este tema, así como otras mejoras como la protección de canal lateral o la confirmación explícita de clave , así como mensajes tempranos y autenticación de contraseña adicional, consulte, por ejemplo, la patente estadounidense "Advanced modular handshake for key agreement andoptional authentication" [15] .
X3DH se propuso inicialmente como parte del algoritmo Double Ratchet utilizado en el protocolo Signal . El protocolo ofrece secreto hacia adelante y negación criptográfica. Opera en una curva elíptica. [16]
El protocolo utiliza cinco claves públicas. Alice tiene una clave de identidad IK A y una clave efímera EK A . Bob tiene una clave de identidad IK B , una clave previa firmada SPK B y una clave previa de un solo uso OPK B . [16] Bob primero publica sus tres claves en un servidor, que Alice descarga y verifica la firma. Luego, Alice inicia el intercambio con Bob. [16] La OPK es opcional. [16]
El acuerdo de clave Diffie-Hellman no se limita a negociar una clave compartida por solo dos participantes. Cualquier número de usuarios puede participar en un acuerdo realizando iteraciones del protocolo de acuerdo e intercambiando datos intermedios (que no necesitan mantenerse en secreto). Por ejemplo, Alice, Bob y Carol podrían participar en un acuerdo Diffie-Hellman de la siguiente manera, con todas las operaciones consideradas como módulo p :
Un fisgón ha podido ver g a mod p , g b mod p , g c mod p , g ab mod p , g ac mod p y g bc mod p , pero no puede usar ninguna combinación de estos para reproducir eficientemente g abc mod p .
Para extender este mecanismo a grupos más grandes, se deben seguir dos principios básicos:
Estos principios dejan abiertas varias opciones para elegir en qué orden los participantes contribuyen a las claves. La solución más simple y obvia es organizar a los N participantes en un círculo y hacer que N claves roten alrededor del círculo, hasta que finalmente todos los N participantes hayan contribuido a cada clave (terminando con su propietario) y cada participante haya contribuido a N claves (terminando con la suya propia). Sin embargo, esto requiere que cada participante realice N exponenciaciones modulares.
Al elegir un orden más deseable y confiar en el hecho de que las claves se pueden duplicar, es posible reducir la cantidad de exponenciaciones modulares realizadas por cada participante a log 2 ( N ) + 1 utilizando un enfoque de estilo divide y vencerás , dado aquí para ocho participantes:
Una vez completada esta operación, todos los participantes poseerán el secreto g abcdefgh , pero cada participante habrá realizado sólo cuatro exponenciaciones modulares, en lugar de las ocho que implica una disposición circular simple.
El protocolo se considera seguro contra los espías si G y g se eligen correctamente. En particular, el orden del grupo G debe ser grande, en particular si se utiliza el mismo grupo para grandes cantidades de tráfico. El espía tiene que resolver el problema de Diffie-Hellman para obtener g ab . Esto se considera actualmente difícil para los grupos cuyo orden es lo suficientemente grande. Un algoritmo eficiente para resolver el problema del logaritmo discreto facilitaría el cálculo de a o b y resolvería el problema de Diffie-Hellman, lo que haría que este y muchos otros criptosistemas de clave pública fueran inseguros. Los campos de características pequeñas pueden ser menos seguros. [17]
El orden de G debe tener un factor primo grande para evitar el uso del algoritmo Pohlig–Hellman para obtener a o b . Por esta razón, a veces se utiliza un primo de Sophie Germain q para calcular p = 2 q + 1 , llamado primo seguro , ya que el orden de G solo es divisible por 2 y q . A veces se elige g para generar el subgrupo de orden q de G , en lugar de G , de modo que el símbolo de Legendre de g a nunca revele el bit de orden bajo de a . Un protocolo que utiliza tal elección es, por ejemplo, IKEv2 . [18]
El generador g suele ser un entero pequeño, como 2. Debido a la autorreducibilidad aleatoria del problema del logaritmo discreto, un g pequeño es igualmente seguro que cualquier otro generador del mismo grupo.
Si Alice y Bob utilizan generadores de números aleatorios cuyos resultados no son completamente aleatorios y pueden predecirse hasta cierto punto, entonces es mucho más fácil espiarlos.
En la descripción original, el intercambio Diffie-Hellman por sí solo no proporciona autenticación de las partes que se comunican y puede ser vulnerable a un ataque de intermediario . Mallory (un atacante activo que ejecuta el ataque de intermediario) puede establecer dos intercambios de claves distintos, uno con Alice y el otro con Bob, haciéndose pasar efectivamente por Alice para Bob, y viceversa, lo que le permite descifrar y volver a cifrar los mensajes que pasan entre ellos. Tenga en cuenta que Mallory debe estar en el medio desde el principio y seguir estando así, descifrando y volviendo a cifrar activamente los mensajes cada vez que Alice y Bob se comunican. Si llega después de que se hayan generado las claves y la conversación cifrada entre Alice y Bob ya haya comenzado, el ataque no puede tener éxito. Si alguna vez está ausente, su presencia anterior se revela a Alice y Bob. Sabrán que todas sus conversaciones privadas habían sido interceptadas y descifradas por alguien en el canal. En la mayoría de los casos, no les ayudará a obtener la clave privada de Mallory, incluso si usó la misma clave para ambos intercambios.
Por lo general, se necesita un método para autenticar a las partes que se comunican entre sí para evitar este tipo de ataques. En su lugar, se pueden utilizar variantes de Diffie-Hellman, como el protocolo STS , para evitar este tipo de ataques.
Un CVE publicado en 2021 ( CVE-2002-20001 ) reveló un ataque de denegación de servicio (DoS) contra las variantes del protocolo que utilizan claves efímeras, llamado ataque D(HE)at. [19] El ataque explota que el intercambio de claves Diffie-Hellman permite a los atacantes enviar números arbitrarios que en realidad no son claves públicas, lo que desencadena costosos cálculos de exponenciación modular en el lado de la víctima. Otro CVE publicado reveló que las implementaciones de intercambio de claves Diffie-Hellman pueden usar exponentes privados largos ( CVE-2022-40735 ) que posiblemente hagan que los cálculos de exponenciación modular sean innecesariamente costosos [20] o pueden verificar innecesariamente que la clave pública del par ( CVE-2024-41996 ) tiene un requisito de recursos similar al cálculo de clave utilizando un exponente largo. [21] Un atacante puede explotar ambas vulnerabilidades juntas.
El algoritmo de tamiz de campo numérico , que generalmente es el más eficaz para resolver el problema del logaritmo discreto , consta de cuatro pasos computacionales. Los primeros tres pasos solo dependen del orden del grupo G, no del número específico cuyo logaritmo finito se desea. [22] Resulta que gran parte del tráfico de Internet utiliza uno de un puñado de grupos que son del orden de 1024 bits o menos. [3] Al precalcular los primeros tres pasos del tamiz de campo numérico para los grupos más comunes, un atacante solo necesita realizar el último paso, que es mucho menos costoso computacionalmente que los primeros tres pasos, para obtener un logaritmo específico. El ataque Logjam utilizó esta vulnerabilidad para comprometer una variedad de servicios de Internet que permitían el uso de grupos cuyo orden era un número primo de 512 bits, el llamado grado de exportación . Los autores necesitaron varios miles de núcleos de CPU durante una semana para precalcular los datos para un solo primo de 512 bits. Una vez hecho esto, los logaritmos individuales se podrían resolver en aproximadamente un minuto utilizando dos CPU Intel Xeon de 18 núcleos. [3]
Según los autores del ataque Logjam, el cálculo previo, mucho más complicado, necesario para resolver el problema del logaritmo discreto para un número primo de 1024 bits costaría alrededor de 100 millones de dólares, una cifra que está dentro del presupuesto de una gran agencia de inteligencia nacional como la Agencia de Seguridad Nacional de Estados Unidos (NSA). Los autores de Logjam especulan que el cálculo previo contra números primos DH de 1024 bits ampliamente reutilizados es la causa de las afirmaciones en documentos filtrados de la NSA de que la NSA es capaz de descifrar gran parte de la criptografía actual. [3]
Para evitar estas vulnerabilidades, los autores de Logjam recomiendan el uso de criptografía de curva elíptica , para la que no se conoce ningún ataque similar. En su defecto, recomiendan que el orden, p , del grupo Diffie-Hellman sea de al menos 2048 bits. Calculan que el cálculo previo necesario para un número primo de 2048 bits es 10 9 veces más difícil que para números primos de 1024 bits. [3]
Se han propuesto esquemas de cifrado de clave pública basados en el intercambio de claves Diffie-Hellman. El primero de estos esquemas es el cifrado ElGamal . Una variante más moderna es el Esquema de cifrado integrado .
Los protocolos que logran el secreto hacia adelante generan nuevos pares de claves para cada sesión y los descartan al final de la sesión. El intercambio de claves Diffie-Hellman es una opción frecuente para dichos protocolos, debido a su rápida generación de claves.
Cuando Alice y Bob comparten una contraseña, pueden utilizar una forma de acuerdo de clave (PK) autenticada por contraseña de Diffie-Hellman para evitar ataques de intermediarios. Un esquema simple es comparar el hash de s concatenado con la contraseña calculada independientemente en ambos extremos del canal. Una característica de estos esquemas es que un atacante solo puede probar una contraseña específica en cada iteración con la otra parte, por lo que el sistema proporciona una buena seguridad con contraseñas relativamente débiles. Este enfoque se describe en la Recomendación X.1035 de la UIT-T , que se utiliza en el estándar de redes domésticas G.hn.
Un ejemplo de dicho protocolo es el protocolo de contraseña remota segura .
También es posible utilizar Diffie–Hellman como parte de una infraestructura de clave pública , lo que permite a Bob cifrar un mensaje para que solo Alice pueda descifrarlo, sin comunicación previa entre ellos más allá de que Bob tenga conocimiento confiable de la clave pública de Alice. La clave pública de Alice es . Para enviarle un mensaje, Bob elige una b aleatoria y luego envía a Alice (sin cifrar) junto con el mensaje cifrado con clave simétrica . Solo Alice puede determinar la clave simétrica y, por lo tanto, descifrar el mensaje porque solo ella tiene a (la clave privada). Una clave pública precompartida también evita los ataques del tipo "man in the middle".
En la práctica, Diffie-Hellman no se utiliza de esta manera, ya que RSA es el algoritmo de clave pública dominante. Esto se debe en gran medida a razones históricas y comerciales, [ cita requerida ] a saber, que RSA Security creó una autoridad de certificación para la firma de claves que se convirtió en Verisign . Diffie-Hellman, como se explicó anteriormente, no se puede utilizar directamente para firmar certificados. Sin embargo, los algoritmos de firma ElGamal y DSA están matemáticamente relacionados con él, así como MQV , STS y el componente IKE del conjunto de protocolos IPsec para proteger las comunicaciones del Protocolo de Internet .
Recibido en agosto de 1975; revisado en septiembre de 1977
