Acuerdo de claves
Diffie-Hellman

Creative Commons License
“Curso de Introducción a la Criptografía” by Jordi Íñigo Griera is licensed under a
Creative Commons Attribution 4.0 International License.
Project hosted at github.com/jig/crypto

Acuerdo de claves DH

{Diffie, Hellman; 1976}

Permite acordar un número aleatorio entre dos usuarios a partir de la hipótesis CDH (hipótesis computacional Diffie-Hellman). Este número aleatorio se puede utilizar como clave (simétrica) para posteriores comunicaciones.
(DH no permite cifrar ni firmar, pero es la base de otros sistemas que si lo permiten)

CDH es un problema con trampa relacionado con el problema DLP (Problema del logaritmo discreto). El DLP conjetura que es difícil el cálculo del logaritmo (función inversa de la exponenciación) en ciertos grupos

DLP

(el problema del logaritmo discreto)

Tenemos un $\mathbb{Z}_{p}^{*}$ ($p$ primo) y seleccionamos
un elemento generador $\alpha\,$ ($\mathbb{Z}_{p}^{*}$ es cíclico)


Entonces, existe un $0 \leq x < p-1$ único que cumple para cada $\beta \in \mathbb{Z}_{p}^{*}$:

$x \equiv \log_{\alpha} \beta \pmod p$

(o de forma equivalente: $\beta \equiv \alpha^x \pmod p$)

...pero es computacionalmente difícil* calcularlo

CDH

(hipótesis computacional
Diffie-Hellman)

Supongamos que tenemos un grupo cíclico sobre un conjunto $\mathbb{Z}_{p}^{*}$
($p$ primo) con el elemento generador $\alpha$


A partir de conocer $\alpha$, $\alpha^i$ y $\alpha^j$ para $0 \leq i,j < p-1$
entonces el cálculo de $\alpha^{ij}$ es computacionalmente difícil…

...si es que no conocemos "la trampa"

CDH requiere que DLP sea computacionalmente difícil

CDH está relacionado con la hipótesis DDH (Decisional DH):
que dice que $\alpha^{ij}$ es indistingible de un valor escogido aleatoriamente de $\mathbb{Z}_{p}^{*}$

Todas estas hipótesis deben ser ciertas para que DH sea seguro

La trampa

Si conocemos $i$ y $\alpha^j$ (ó $j$ y $\alpha^i$) entonces el cálculo de $\alpha^{ij}$ es fácil:

Si conocemos $i$: $\alpha^{ij} = {(\alpha^j)}^{i} \pmod p$

Si conocemos $j$: $\alpha^{ij} = {(\alpha^i)}^{j} \pmod p$

(en cambio si no conocemos ni $i$ ni $j$, es computacionalmente difícil aunque conozcas $\alpha^i$ y $\alpha^j$)

protocolo

  1. Dados dos usuarios $I$ y $J$ hace falta que generenen respectivamente dos números $i$ y $j$ y que los mantingan en secreto
  2. $I$ debe enviar $\alpha^i \pmod p$ a $J$;
    $J$ calcula $\alpha^{ij} = {(\alpha^i)}^{j} \pmod p$
  3. $J$ debe enviar $\alpha^j \pmod p$ a $I$;
    $I$ calcula $\alpha^{ij} = {(\alpha^j)}^{i} \pmod p$

A partir de aquí $I$ y $J$ comparten el secreto $\alpha^{ij}$

Un atacante que vea el tráfico ($\alpha^i$ y $\alpha^j$) y conozca $\alpha$ no es capaz de descubrir nada sobre el secreto $\alpha^{ij}$

Selección de los parámetros $p$, $\alpha$

Los parámetros $p$ y $\alpha$ se pueden seleccionar a priori, pueden ser públicos y utilizarse múltiples veces:

  • $p$: debe ser un primo grande (en la forma $p=2q+1$ para facilitar la búsqueda de generadores $\alpha$)
  • $\alpha$: seleccionar un valor aleatorio $\alpha \in \mathbb{Z}_{p}^{*}$ que sea generador de $\mathbb{Z}_{p}^{*}$
Nota: habitualmente $\alpha$ es $2$ (lo que optimiza las operaciones)

debilidades $\rightarrow$ contramedidas

DH no autentica:

  • MITM $\rightarrow$ hace falta combinar DH con algún protocolo para autenticar los extremos

problemas sobre la implementación:

  • Logjam attack $\rightarrow$ rémora del export grade crypto: $512$ bit aún en algún software
  • muchas implementaciones limitan la longitud de las claves (en el caso de EDH, Ephemeral DH) a $1024$ bit (Apache, Java)
  • se sospecha que la NSA es capaz de romper (¿sistemáticamente?) DH-1024

Longitud de clave

los ataques sobre DH son los mejores algoritmos para calcular $log_{\alpha}(\alpha^{ij}) \pmod p$

el NIST recomienda $\|p\| \geq 2048$ bit hasta 2030

RSA AES (bits de seguridad)
$1024$ $\leftrightarrow$ $80$ $80$
$2048$ $\leftrightarrow$ $112$ $112$
$3072$ $\leftrightarrow$ $128$ $128$
$15360$ $\leftrightarrow$ $256$ $256$

Clave asimétrica

Clave pública: ($\alpha^i$, Parámetros públicos)

Clave privada: ($i$, Parámetros públicos)

Parámetros públicos: primo $p$ grande ($\ge 2048 \text{ bit}$) de la forma $p=2q+1$;
generador $\alpha$ ($2$ ò $5$)

Diffie-Hellman efímero

las claves simétricas són siempre las mismas si $i$ y $j$ (claves privadas son las mismas)

Dado que el coste de generación de claves DH es muy bajo (random grande + exponenciación) podemos generarla a cada uso

En pro: cada interacción genera una clave distinta (DHE; DH Ephemeral)

Por contra: no podemos autenticar al interlocutor (MITM) (DH; DH non-ephemeral)

Aplicación

TLS: es del todo recomendable el uso de DH efímero (DHE ó ECDHE)

WhatsApp: uso de DH no efímero para comunicación peer-to-peer o entre grupos (paper)

(RSA) $\rightarrow$