Intercambio de claves Diffie-Hellman

El intercambio de claves Diffie-Hellman establece un secreto compartido entre dos partes que puede utilizarse para la comunicación segura y el intercambio de 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 con Alice y Bob , quienes acuerdan públicamente un color inicial cualquiera que no necesita mantenerse en secreto. En este ejemplo, el color es amarillo. Cada persona también elige un color secreto que guarda para sí misma; en este caso, rojo y cian. La parte crucial del proceso consiste en que Alice y Bob mezclan su color secreto con el color que compartieron, obteniendo así mezclas de naranja-marrón y azul claro, respectivamente. Luego, intercambian públicamente las dos mezclas. Finalmente, cada uno mezcla el color que recibió de su compañero con su propio color privado. El resultado es una mezcla final (amarillo-marrón en este caso) idéntica a la mezcla final de su compañero.

Si un tercero escuchara la conversación, solo conocería el color común (amarillo) y los primeros colores mezclados (naranja-marrón y azul claro), pero le sería muy difícil descubrir el color secreto final (amarillo-marrón). Volviendo a la analogía con una conversación real usando números grandes en lugar de colores, esta determinación es computacionalmente costosa; es imposible calcularla en un tiempo razonable incluso para las supercomputadoras modernas .

La implementación más simple y original, ^{[ 3 ]} formalizada posteriormente como Diffie-Hellman de Campo Finito en RFC 7919, ^{[ 9 ]} del protocolo utiliza el grupo multiplicativo de enteros módulo p , donde p es primo y g es una raíz primitiva módulo p . Para protegerse contra posibles vulnerabilidades, se recomienda utilizar números primos de al menos 2048 bits de longitud. Esto aumenta la dificultad para un adversario que intente calcular el logaritmo discreto y comprometer el secreto compartido. Estos dos valores se eligen de esta manera para asegurar que el secreto compartido resultante pueda tomar cualquier valor de 1 a p − 1. Aquí hay un ejemplo del protocolo, con valores no secretos en azul y valores secretos en rojo .

1. Alice y Bob acuerdan públicamente usar un módulo p = 23 y una base g = 5 (que es una raíz primitiva módulo 23).
2. Alice elige un número entero secreto a = 4, luego le envía a Bob A = g ^a mod p
   • A = 5 ⁴ mod 23 = 4 (en este ejemplo, tanto A como a tienen el mismo valor 4, pero esto no suele ser así).
3. Bob elige un número entero secreto b = 3, luego le envía a Alice B = g ^b mod p
   • B = 5 ³ mod 23 = 10
4. Alice calcula s = B ^a mod p
   • s =10 ⁴ mod23= 18
5. Bob calcula s = A ^b mod p
   • s =4 ³ mod23= 18
6. Alice y Bob ahora comparten un secreto (el número 18).

Tanto Alice como Bob han llegado a los mismos valores porque bajo el módulo p ,

${\displaystyle {\color {Blue}A}^{\color {Red}{\boldsymbol {b}}}{\bmod {\color {Blue}p}}={\color {Blue}g}^{\color {Red}{\boldsymbol {ab}}}{\bmod {\color {Blue}p}}={\color {Blue}g}^{\color {Red}{\boldsymbol {ba}}}{\bmod {\color {Blue}p}}={\color {Blue}B}^{\color {Red}{\boldsymbol {a}}}{\bmod {\color {Blue}p}}}$

Más específicamente,

${\displaystyle ({\color {Blue}g}^{\color {Red}{\boldsymbol {a}}}{\bmod {\color {Blue}p}})^{\color {Red}{\boldsymbol {b}}}{\bmod {\color {Blue}p}}=({\color {Blue}g}^{\color {Red}{\boldsymbol {b}}}{\bmod {\color {Blue}p}})^{\color {Red}{\boldsymbol {a}}}{\bmod {\color {Blue}p}}}$

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 en texto plano. La solidez del esquema radica en que calcular g ^ab mod p = g ^ba mod p requiere muchísimo tiempo con cualquier algoritmo clásico conocido, solo conociendo p , g , g ^a mod p y g ^b mod p . Una función de este tipo, 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 clave de cifrado, conocida solo por ellos, para enviar mensajes a través del mismo canal de comunicación 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 utilizan el algoritmo más rápido conocido no pueden encontrar a dados solo g , p y g ^a mod p . Este problema se llama el problema del logaritmo discreto . ^{[ 2 ]} 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. Nótese que g no tiene por qué ser grande en absoluto, y en la práctica suele ser un entero pequeño (como 2, 3, ...).

El siguiente gráfico muestra quién sabe qué, con los valores no secretos en azul y los secretos en rojo . En este caso, Eve es una espía : observa lo que se envían Alice y Bob, pero no altera el contenido de sus comunicaciones.

• g , base pública (raíz primitiva), conocida por Alice, Bob y Eve. g = 5
• p , módulo público (primo), conocido por Alice, Bob y Eve. p = 23
• a , la clave privada de Alice, conocida solo por Alice. a = 6
• b , la clave privada de Bob, conocida solo por Bob. b = 15
• A , la clave pública de Alice, conocida por Alice, Bob y Eve. A = g ^a mod p = 8
• B , la clave pública de Bob, conocida por Alice, Bob y Eve. B = g ^b mod p = 19

Ahora bien, s es la clave secreta compartida y la conocen tanto Alice como Bob, pero no Eve. Nótese que no le resulta útil a Eve calcular AB , que es igual a g ^{a + b} mod p .

Nota: Debe ser difícil para Alice descifrar la clave privada de Bob, o para Bob descifrar la clave privada de Alice. Si no es difícil para Alice descifrar la clave privada de Bob (o viceversa), entonces un espía, Eve , puede simplemente sustituir su propio par de claves pública/privada, insertar la clave pública de Bob en su clave privada, generar una clave secreta compartida falsa y descifrar la clave privada de Bob (y usarla para descifrar la clave secreta compartida). Eve puede intentar elegir un par de claves pública/privada que le facilite descifrar la clave privada de Bob.

Aquí hay una descripción más general del protocolo: ^{[ 10 ]}

1. Alice y Bob acuerdan un número natural n y un elemento generador g en el grupo cíclico finito G de orden n . (Esto suele hacerse mucho antes que el resto del protocolo; se supone que todos los atacantes conocen g y n ). El grupo G se escribe multiplicativamente.
2. Alice elige un número natural aleatorio a tal que 1 < a < n , y envía el elemento g ^a de G a Bob.
3. Bob elige un número natural aleatorio b con 1 < b < n , y envía el elemento g ^b de G a Alice.
4. Alice calcula el elemento ( g ^b ) ^a = g ^ba de G.
5. Bob calcula el elemento ( g ^a ) ^b = g ^ab de G.

Tanto Alice como Bob poseen ahora el 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 exista un algoritmo eficiente para determinar g ^ab dados g , g ^a y g ^b .

Por ejemplo, el protocolo Diffie-Hellman de curva elíptica 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 computadoras cuánticas , pero fue vulnerada en julio de 2022. ^{[ 11 ]}

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 ) y ( y , Y ). Entonces, el protocolo es:

Las claves públicas a largo plazo deben transferirse de alguna manera. Esto puede hacerse previamente en un canal separado y seguro, o bien las claves públicas pueden cifrarse mediante un acuerdo de clave parcial para preservar el anonimato. Para obtener más detalles, así como otras mejoras como la protección contra canales laterales o la confirmación explícita de claves , además de mensajes anticipados y autenticación de contraseñas adicional, consulte, por ejemplo, la patente estadounidense «Advanced modular handshake for key agreement and optional authentication». ^{[ 15 ]}

X3DH se propuso inicialmente como parte del algoritmo Double Ratchet utilizado en el protocolo Signal . El protocolo ofrece confidencialidad directa y negabilidad criptográfica. Opera sobre 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 preclave firmada SPK _B y una preclave 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 ]}

Una CVE publicada 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. Otra publicación de CVE reveló que las implementaciones del intercambio de claves Diffie-Hellman pueden usar exponentes privados largos ( CVE-2022-40735 ) que posiblemente hacen que los cálculos de exponenciación modular sean innecesariamente costosos ^{[ 20 ]} o pueden verificar innecesariamente la clave pública de un par ( CVE-2024-41996 ) que tiene un requisito de recursos similar al cálculo de clave usando un exponente largo. ^{[ 21 ]} Un atacante puede explotar ambas vulnerabilidades juntas.

El algoritmo de criba de campos numéricos , que generalmente es el más efectivo para resolver el problema del logaritmo discreto , consta de cuatro pasos computacionales. Los tres primeros 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 de orden 1024  bits o menos. ^{[ 2 ]} Al precalcular los tres primeros pasos de la criba de campos numéricos para los grupos más comunes, un atacante solo necesita realizar el último paso, que es mucho menos costoso computacionalmente que los tres primeros 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, llamado grado de exportación . Los autores necesitaron varios miles de núcleos de CPU durante una semana para precalcular datos para un solo primo de 512 bits. Una vez hecho esto, los logaritmos individuales podían resolverse en aproximadamente un minuto utilizando dos CPU Intel Xeon de 18 núcleos. ^{[ 2 ]}

Según las estimaciones de los autores del ataque Logjam, el preprocesamiento, mucho más complejo, 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 se encuentra dentro del presupuesto de una gran agencia de inteligencia nacional como la Agencia de Seguridad Nacional (NSA) de Estados Unidos. Los autores de Logjam especulan que el preprocesamiento contra números primos DH de 1024 bits, ampliamente reutilizados, es la base de las afirmaciones contenidas en documentos filtrados de la NSA, según las cuales esta agencia es capaz de descifrar gran parte de la criptografía actual. ^{[ 2 ]}

Para evitar estas vulnerabilidades, los autores de Logjam recomiendan el uso de criptografía de curva elíptica , para la cual no se conoce ningún ataque similar. En caso contrario, recomiendan que el orden, p , del grupo Diffie-Hellman sea de al menos 2048  bits. Estiman que el preprocesamiento requerido para un primo de 2048 bits es 10⁹ ^veces más difícil que para primos de 1024 bits. ^{[ 2 ]}

Las computadoras cuánticas pueden romper esquemas criptográficos de clave pública, como RSA, DH de campo finito y protocolos de intercambio de claves DH de curva elíptica, utilizando el algoritmo de Shor para resolver el problema de factorización , el problema del logaritmo discreto y el problema de la búsqueda de periodos. En 2023 se propuso una variante post-cuántica del algoritmo Diffie-Hellman , que se basa en una combinación del protocolo CRYSTALS-Kyber resistente a la computación cuántica, así como del antiguo protocolo X25519 de curva elíptica .

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 garantizan el secreto hacia adelante generan nuevos pares de claves para cada sesión y los descartan al finalizar la misma. El intercambio de claves Diffie-Hellman es una opción frecuente para este tipo de protocolos debido a su rápida generación de claves.

Cuando Alice y Bob comparten una contraseña, pueden usar un protocolo Diffie-Hellman con autenticación de clave pública (PK) para prevenir ataques de intermediario. Un método sencillo consiste en comparar el hash de la contraseña concatenada con la contraseña, calculado independientemente en ambos extremos del canal. Una característica de estos métodos 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 ofrece una buena seguridad incluso con contraseñas relativamente débiles. Este enfoque se describe en la Recomendación X.1035 de la UIT-T , utilizada por el estándar de redes domésticas G.hn.

Un ejemplo de este tipo de 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 de forma que solo Alice pueda descifrarlo, sin comunicación previa entre ellos, salvo que Bob tenga conocimiento de confianza de la clave pública de Alice. La clave pública de Alice es${\displaystyle (g^{a}{\bmod {p}},g,p)}$Para enviarle un mensaje, Bob elige una b al azar y luego se la envía a Alice.${\displaystyle g^{b}{\bmod {p}}}$(sin cifrar) junto con el mensaje cifrado con clave simétrica${\displaystyle (g^{a})^{b}{\bmod {p}}}$Solo Alice puede determinar la clave simétrica y, por lo tanto, descifrar el mensaje, ya que solo ella posee la clave privada. Una clave pública compartida previamente también previene los ataques de intermediario.

En la práctica, Diffie-Hellman no se utiliza de esta manera, siendo RSA el algoritmo de clave pública dominante. Esto se debe principalmente a razones históricas y comerciales, concretamente a que RSA Security creó una autoridad de certificación para la firma de claves que posteriormente se convirtió en Verisign . Como se explicó anteriormente, Diffie-Hellman no puede utilizarse directamente para firmar certificados. Sin embargo, los algoritmos de firma ElGamal y DSA están matemáticamente relacionados con él, al igual que MQV , STS y el componente IKE del conjunto de protocolos IPsec para la seguridad de las comunicaciones del Protocolo de Internet .

• Gollman, Dieter (2011). Seguridad informática (2.ª  ed.). West Sussex, Inglaterra: John Wiley & Sons, Ltd. ISBN 978-0470741153.
• Williamson, Malcolm J. (21 de enero de 1974). Cifrado no secreto mediante un campo finito (PDF) (Informe técnico). Communications Electronics Security Group. Archivado (PDF) del original el 23 de marzo de 2017. Consultado el 22 de marzo de 2017 .
• Williamson, Malcolm J. (10 de agosto de 1976). Reflexiones sobre el cifrado no secreto más económico (PDF) (Informe técnico). Communications Electronics Security Group. Archivado (PDF) del original el 19 de julio de 2004. Consultado el 25 de agosto de 2015 .
• Historia del cifrado no secreto, por JH Ellis, 1987 (archivo PDF de 28 KB) ( versión HTML )
• Los primeros diez años de la criptografía de clave pública , Whitfield Diffie, Actas del IEEE, vol. 76, n.º 5, mayo de 1988, págs.: 560–577 (archivo PDF de 1,9 MB).
• Menezes, Alfred ; van Oorschot, Paul ; Vanstone, Scott (1997). Manual de criptografía aplicada. Boca Raton, Florida: CRC Press. ISBN 0-8493-8523-7( Disponible en línea )
• Singh, Simon (1999) El libro de códigos: la evolución del secreto desde María Estuardo hasta la criptografía cuántica. Nueva York: Doubleday ISBN 0-385-49531-5
• Introducción a la criptografía de clave pública. Martin E. Hellman, IEEE Communications Magazine, mayo de 2002, págs.  42-49. (Archivo PDF de 123 kB)