Acord de claus
Diffie-Hellman

Creative Commons License
“Curs d'Introducció a la criptografia” by Jordi Íñigo Griera is licensed under a
Creative Commons Attribution 4.0 International License.
Project hosted at github.com/jig/crypto

Acord de claus DH

{Diffie, Hellman; 1976}

Permet acordar un nombre aleatori entre dos usuaris a partir de la hipòtesi CDH (hipòtesi computacional Diffie-Hellman). Aquest nombre aleatori es pot fer servir de clau per a xifrar les posteriors comunicacions fent servir xifrat simètric.
(DH no permet signar ni xifrar, però és la base d'altres algorismes que sí ho permeten)

CDH és un problema amb trampa relacionat amb el problema DLP (Problema del logaritme discret). El DLP conjectura que es difícil el càlcul del logaritme (funció inversa de l'exponenciació) en certs grups

DLP

(el problema del logaritme discret)

Tenim un $\mathbb{Z}_{p}^{*}$ ($p$ primer) i seleccionem
un element generador $\alpha\,$ ($\mathbb{Z}_{p}^{*}$ és cíclic)


Llavors, existeix un $0 \leq x < p-1$ únic que compleix per a cada $\beta \in \mathbb{Z}_{p}^{*}$:

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

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

...però és computacionalment difícil* calcular-lo

CDH

(hipòtesi computacional
Diffie-Hellman)

Suposem que tenim un grup cíclic sobre un conjunt $\mathbb{Z}_{p}^{*}$
($p$ primer) amb l'element generador $\alpha$


A partir de conèixer $\alpha$, $\alpha^i$ i $\alpha^j$ per a $0 \leq i,j < p-1$
llavors el càlcul de $\alpha^{ij}$ és computacionalment difícil...

...si és que no coneixem "la trampa"

CDH requereix que DLP sigui computacionalment difícil

CDH està relacionat amb la hipòtesi DDH (Decisional DH):
que diu que $\alpha^{ij}$ és indistingible d'un valor escollit aleatòriament de $\mathbb{Z}_{p}^{*}$

Totes les hipòtesis han de ser certes per a que DH sigui segur

La trampa

Si coneixem $i$ i $\alpha^j$ (ò $j$ i $\alpha^i$) llavors el càlcul d'$\alpha^{ij}$ és fàcil:

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

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

(en canvi si no coneixes ni $i$ ni $j$, és computacionalment difícil encara que coneguis $\alpha^i$ i $\alpha^j$)

protocol

  1. Donats dos usuaris $I$ i $J$ cal que generin respectivament dos nombres $i$ i $j$ i que els mantinguin en secret
  2. $I$ ha d'enviar $\alpha^i \pmod p$ a $J$;
    $J$ calcula $\alpha^{ij} = {(\alpha^i)}^{j} \pmod p$
  3. $J$ ha d'enviar $\alpha^j \pmod p$ a $I$;
    $I$ calcula $\alpha^{ij} = {(\alpha^j)}^{i} \pmod p$

A partir d'aquí $I$ i $J$ comparteixen el secret $\alpha^{ij}$

Un atacant que vegi el tràfic ($\alpha^i$ i $\alpha^j$) i conegui $\alpha$ no és capaç d'aprendre res sobre el secret $\alpha^{ij}$

Selecció dels paràmetres $p$, $\alpha$

Els paràmetres $p$ i $\alpha$ es poden seleccionar a priori, poden ser públics i fer-se servir múltiples vegades:

  • $p$: ha de ser un primer gran (en la forma $p=2q+1$ per a facilitar la cerca de generadors $\alpha$)
  • $\alpha$: seleccionar un valor aleatori $\alpha \in \mathbb{Z}_{p}^{*}$ que sigui generador de $\mathbb{Z}_{p}^{*}$
Nota: habitualment $\alpha$ és $2$ (per a optimitzar les operacions)

debilitats $\rightarrow$ contramesures

DH no autentica:

  • MITM $\rightarrow$ cal combinar DH amb algun protocol per a autenticar els extrems

problemes sobre la implementació:

  • Logjam attack $\rightarrow$ rèmora de l'export grade crypto: $512$ bit encara en algun software
  • moltes implementacions limiten la longitud de les claus (en el cas d'EDH, Ephemeral DH) a $1024$ bit (Apache, Java)
  • hi ha sospites que l'NSA és capaç de trencar (sistemàticament?) DH-1024

Longitud de clau

els atacs sobre DH són els millors algorismes per a calcular $log_{\alpha}(\alpha^{ij}) \pmod p$

el NIST recomana $\|p\| \geq 2048$ bit fins el 2030

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

(RSA) $\rightarrow$