El intercambio de claves Diffie-Hellman [nb 1] es un método matemático para intercambiar claves criptográficas de forma segura a través de un canal público y fue uno de los primeros protocolos de clave pública concebido por Ralph Merkle y que lleva el nombre de 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 confiable . 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 luego se puede utilizar para cifrar comunicaciones posteriores mediante un cifrado de clave simétrica .
Diffie-Hellman se utiliza para proteger una variedad de servicios de Internet . Sin embargo, una investigación publicada en octubre de 2015 sugiere que los parámetros utilizados por muchas aplicaciones de Internet DH en ese momento no son lo suficientemente fuertes como para evitar el compromiso de atacantes muy bien financiados, como los servicios de seguridad de algunos países. [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 británica de inteligencia de señales, habían previamente demostró en 1969 [5] cómo se podía lograr la criptografía de clave pública. [6]
Aunque el acuerdo de clave Diffie-Hellman en sí es un protocolo de acuerdo de clave no autenticado , proporciona la base para una variedad de protocolos autenticados y se utiliza para proporcionar secreto directo en los modos efímeros de Transport Layer Security (denominados EDH o DHE). dependiendo del conjunto de cifrado ).
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 expirada 4.200.770 [7] de 1977 describe el algoritmo ahora de dominio público . Da crédito a Hellman, Diffie y Merkle como inventores.
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... desde entonces se conoce como intercambio de claves Diffie-Hellman. Si bien 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 van a asociar nombres con él. . Espero que este pequeño púlpito pueda ayudar en ese esfuerzo por reconocer la contribución igualitaria 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 usarse para una comunicación secreta para el intercambio de datos a través de una red pública. Una analogía ilustra el concepto de intercambio de claves públicas mediante el uso de 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 elige un color secreto que guarda para sí mismo: en este caso, rojo y cian. La parte crucial del proceso es que Alice y Bob mezclan cada uno su propio color secreto con el color que comparten mutuamente, lo que da como resultado mezclas de naranja, tostado y azul claro, respectivamente, y luego intercambian públicamente los dos colores mezclados. Finalmente, cada uno mezcla el color que recibió de su pareja con su color privado. El resultado es una mezcla de colores final (amarillo-marrón en este caso) idéntica a la mezcla de colores final de su compañero.
Si un tercero escuchara el intercambio, sólo sabrí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 marron). Volviendo a la analogía con un intercambio de la vida real que utiliza grandes números en lugar de colores, esta determinación es computacionalmente costosa. Es imposible realizar cálculos en un período de tiempo práctico, incluso para las supercomputadoras modernas .
La implementación más simple y original, [2] posteriormente formalizada como Campo finito 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. A continuación se muestra un ejemplo del protocolo, con valores no secretos en azul y valores secretos en rojo .
Tanto Alice como Bob llegaron a los mismos valores porque bajo mod p,
Más específicamente,
Sólo 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 requiere tiempos extremadamente largos para calcularse mediante cualquier algoritmo conocido simplemente a partir del conocimiento de p , g , g a mod p y g b mod p . Una función que es fácil de calcular pero difícil de invertir se llama función unidireccional . Una vez que Alice y Bob calculan el secreto compartido, pueden utilizarlo como clave de cifrado, conocida sólo 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 sea seguro, ya que sólo hay 23 resultados posibles de n mod 23. Sin embargo, si p es un primo de al menos 600 dígitos, entonces incluso el Las computadoras modernas más rápidas que utilizan el algoritmo más rápido conocido no pueden encontrar un determinado g , p y g a mod p . Este problema se llama problema de logaritmos discretos . [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 número entero pequeño (como 2, 3, ...).
El siguiente cuadro muestra quién sabe qué, nuevamente con valores no secretos en azul y 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 . Tenga en cuenta que a Eve no le resulta útil 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 a Alice no le resulta difícil encontrar la clave privada de Bob (o viceversa), entonces una espía, Eve , puede simplemente sustituir su propio par de claves privada/pública, conectar la clave pública de Bob a su clave privada y producir un secreto compartido falso. clave 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 encontrar la clave privada de Bob.
Aquí hay una descripción más general del protocolo: [10]
Tanto Alice como Bob ahora poseen 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 módulo entero 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 fue diseñada para ser segura contra 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 incluso pueden ser mixtas, lo que se denomina DH semiestático. Estas variantes tienen diferentes propiedades y, por tanto, diferentes casos de uso. Puede encontrar una descripción general de muchas variantes y 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 claves 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 claves 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 mejorado por C. Kudla y KG Paterson en 2005 [14] y demostró ser seguro.
Las claves secretas a largo plazo de Alice y Bob se indican con a y b respectivamente, con las 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 confiable, o las claves públicas se pueden cifrar mediante algún acuerdo de clave parcial para preservar el anonimato. Para obtener más detalles de este tipo, así como otras mejoras como protección de canal lateral o confirmación de clave explícita , así como mensajes tempranos y autenticación de contraseña adicional, consulte, por ejemplo, la patente de EE. UU. "Apretón de enlace modular avanzado para acuerdo de clave y autenticación opcional". [15]
X3DH se propuso inicialmente como parte del algoritmo de doble trinquete utilizado en el protocolo de señal . El protocolo ofrece secreto directo y negación criptográfica. Opera sobre una curva elíptica. [dieciséis]
El protocolo utiliza cinco claves públicas. Alice tiene una clave de identidad IKA y una clave efímera EK A. Bob tiene una clave de identidad IKB , 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. Alice luego inicia el intercambio con Bob. [16] El OPK es opcional. [dieciséis]
El acuerdo de claves Diffie-Hellman no se limita a negociar una clave compartida por sólo dos participantes. Cualquier número de usuarios puede participar en un acuerdo realizando iteraciones del protocolo del 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, considerando que todas las operaciones son módulo p :
Un espía 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 modp .
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 giren 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 los suyos). 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 el número de exponenciaciones modulares realizadas por cada participante a log 2 ( N ) + 1 utilizando un enfoque de estilo divide y vencerás. , proporcionado 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 intrusos si G y g se eligen correctamente. En particular, el orden del grupo G debe ser grande, particularmente si el mismo grupo se utiliza para grandes cantidades de tráfico. El espía tiene que resolver el problema de Diffie-Hellman para obtener g ab . Actualmente, esto se considera difícil para 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, haciendo que éste y muchos otros criptosistemas de clave pública sean 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 de Pohlig-Hellman para obtener aob . Por esta razón, a veces se utiliza un primo q de Sophie Germain para calcular p = 2 q + 1 , llamado primo seguro , ya que el orden de G entonces solo es divisible por 2 y q . A veces se elige g para generar el subgrupo q de orden de G , en lugar de G , de modo que el símbolo de Legendre de g a nunca revela el bit de orden inferior de a . Un protocolo que utiliza esta opción es, por ejemplo, IKEv2 . [18]
El generador g suele ser un número 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 cuyas salidas no son completamente aleatorias y pueden predecirse hasta cierto punto, entonces es mucho más fácil escuchar a escondidas.
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 ante Bob, y viceversa, permitiéndole descifrar y luego volver a -cifrar, los mensajes pasados entre ellos. Tenga en cuenta que Mallory debe estar en el medio desde el principio y continuar así, descifrando y volviendo a cifrar mensajes activamente 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 podrá tener éxito. Si alguna vez está ausente, su presencia anterior se revela a Alice y Bob. Sabrán que todas sus conversaciones privadas han sido interceptadas y decodificadas por alguien del canal. En la mayoría de los casos, no les ayudará a obtener la clave privada de Mallory, incluso si ella usó la misma clave para ambos intercambios.
Generalmente se necesita un método para autenticar a las partes que se comunican entre sí para evitar este tipo de ataque. En su lugar, se pueden utilizar variantes de Diffie-Hellman, como el protocolo STS , para evitar este tipo de ataques.
El algoritmo de criba de campos numéricos , que generalmente es el más eficaz para resolver el problema de logaritmos discretos , consta de cuatro pasos computacionales. Los primeros tres pasos sólo dependen del orden del grupo G, no del número específico cuyo registro finito se desea. [19] Resulta que gran parte del tráfico de Internet utiliza uno de los pocos grupos que son del orden de 1024 bits o menos. [3] Al precalcular los primeros tres pasos del tamiz de campos numéricos para los grupos más comunes, un atacante solo necesita llevar a cabo 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 de un único número principal de 512 bits. Una vez hecho esto, los logaritmos individuales se pudieron resolver en aproximadamente un minuto utilizando dos CPU Intel Xeon de 18 núcleos. [3]
Según lo estimado por los autores del ataque Logjam, el cálculo previo, mucho más difícil, necesario para resolver el problema del registro discreto para un sistema primo de 1024 bits costaría del orden de 100 millones de dólares, 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 está detrás de las afirmaciones contenidas 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 cual no se conoce ningún ataque similar. En su defecto, recomiendan que el orden, p , del grupo Diffie-Hellman sea al menos de 2048 bits. Estiman que el cálculo previo requerido 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 directo 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 este tipo de 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 autenticada (PK) de Diffie-Hellman para evitar ataques de intermediario. Un esquema simple consiste en comparar el hash de s concatenados con la contraseña calculada de forma independiente en ambos extremos del canal. Una característica de estos esquemas es que un atacante sólo puede probar una contraseña específica en cada iteración con la otra parte, por lo que el sistema proporciona buena seguridad con contraseñas relativamente débiles. Este enfoque se describe en la Recomendación UIT-T X.1035 , que utiliza 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 de modo que solo Alice pueda descifrarlo, sin ninguna comunicación previa entre ellos aparte de que Bob tenga un 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 . Sólo Alice puede determinar la clave simétrica y, por tanto, descifrar el mensaje porque sólo ella tiene una (la clave privada). Una clave pública previamente compartida también evita 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 en gran medida a razones históricas y comerciales, [ cita necesaria ] es decir, 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 relacionados matemáticamente 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
{{cite journal}}: Citar diario requiere |journal=( ayuda )