Intercanvi de claus de Diffie-Hellman

El protocol criptográfico Diffie-Hellman, per Whitfield Diffie i Martin Hellman (autors també del problema de Diffie-Hellman o DHP), és un protocol d'establiment de claus entre parts que no han tingut contacte previ, utilisant un canal insegur i de manera anònima (no autenticada).

S'ampra generalment com a mig per a acordar claus simètriques que seran amprades per al sifrat d'una sessió (establir clau de sessió). Sent no autenticado, no obstant, proveïx les bases per a varis protocols autenticados. La seua seguritat radica en l'extrema dificultat (conjeturada, no demostrada) de calcular logaritmos discrets en un cos finito.

El método du el nom dels criptógrafos Whitfield Diffie i Martin Hellman, els qui ho varen desenrollar i varen publicar en 1976 i varen rebre el prestigiós premi A.M. Turing de 2015 per este treball "que va revolucionar la seguritat informàtica".

Versió bàsica

El sistema es basa en l'idea de que dos interlocutors poden generar conjuntament una clau compartida sense que un intrús, que estiga escoltant les comunicacions, puga aplegar a obtindre-la.

Per a això s'elegixen dos números públics i, cada interlocutor, un número secret. Usant una fòrmula matemàtica, que inclou la exponenciación, cada interlocutor fa una série d'operacions en els dos números públics i el seu número secret. A continuació els interlocutors s'intercanvien els resultats de forma pública. En teoria, revertir esta funció és tan difícil com calcular un logaritmo discret (un sextillón de voltes més costosa que la exponenciación usada per a transformar els números). Per tant, es diu que este número és el resultat d'aplicar una funció unidireccional al número secret.

A continuació, abdós interlocutors utilisen per separat una fòrmula matemàtica que combina els dos números transformats en el seu número secret i al final els dos apleguen al mateix número resultat, que serà la clau compartida.

Descripció detallada

Diffie-Hellman.

Per a dos parts Alice i Bob, que intenten establir una clau secreta, i un adversari Mallory, la versió bàsica és com seguix:

• S'establixen un primer $p$ i un generador $g\in {𝐙}_p^{*}$ (). Estos són públics, coneguts no solament per les parts. Alice i Bob sino també per l'adversari Mallory.
• Alice tria $a\in {𝐙}_{p-1}$ a l'encert, calcula $A=g^{a}modp$, i envia $A$ a Bob.
• Bob tria $b\in {𝐙}_{p-1}$ a l'encert, calcula $B=g^{b}modp$, i envia $B$ a Alice.

Note's que tant $A$ com $B$ poden calcular el valor $K=g^{a\cdot b}modp$. En efecte, ho podem demostrar usant les propietats del grup ${𝐙}_p^{*}$:

Per a Alice: $B^{a}modp=(g^{b}modp{)}^{a}modp=(\stackrel{a}{\overbrace{(g^{b}modp)(g^{b}modp)\cdots (g^{b}modp)}})modp=g^{b\cdot a}modp=g^{a\cdot b}modp=K$

Per a Bob: $A^{b}modp=(g^{a}modp{)}^{b}modp=(\stackrel{b}{\overbrace{(g^{a}modp)(g^{a}modp)\cdots (g^{a}modp)}})modp=g^{a\cdot b}modp=K$

Com abdós parts poden calcular $K$, llavors la podem usar com a clau compartida.

Atacs

Atacs passius

Un adversari Mallory, que posseïra $(p,g,A,B)$, podria calcular el secret compartit si tinguera també un dels valors privats ($a$ o $b$). Obtindre $a$ o $b$ a partir de $A$ o $B$ invertint la funció ( $a={\mathrm{l}\mathrm{o}\mathrm{g}\mathrm{d}\mathrm{i}\mathrm{s}\mathrm{c}}_p(A)$ i $b={\mathrm{l}\mathrm{o}\mathrm{g}\mathrm{d}\mathrm{i}\mathrm{s}\mathrm{c}}_p(B)$) és el problema del logaritmo discret en ${𝐙}_p^{*}$, un problema que es creu intractable computacionalment sempre que $p$ siga un número primo gran de 200 o més dígits i que no complixquen certes característiques debilitantes.

Atacs actius

El protocol és sensible a atacs actius del tipo Man-in-the-middle. Si la comunicació és interceptada per un tercer, este es pot fer passar per l'emissor cara al destinatari i viceversa, ya que no es dispon de cap mecanisme per a validar l'identitat dels participants en la comunicació. Aixina, el "home en el mig" podria acordar una clau en cada participant i retransmetre les senyes entre ells, escoltant la conversació en abdós sentits. Una volta establida la comunicació simètrica, l'atacant té que seguir en mig interceptant i modificant el tràfic per a que no es donen conte. Observar que per a que l'atac siga operatiu, l'atacant té que conéixer el método de sifrat simètric que serà utilisat. Basar-se en l'ocultació d'algoritme simètric de sifrat no complix en els principis de Kerckhoffs (l'efectivitat del sistema no deu dependre de que el seu disseny permaneixca en secret).

Ataque man-in-the-middle en Diffie-Hellman.

Per a evitar este tipo d'atac, se sol usar una o més de les següents tècniques:

• Control de temps.
• Autenticació prèvia de les parts. Per eixemple, usar en protocol de capa subjacent autenticació. Podríem primer establir una conexió TLS i sobre eixa capa aplicar l'algoritme de Diffie-Hellman.
• Autenticació del contingut. Per eixemple, podríem usar MAC sobre el contingut dels mensages.
• Sifrant les claus públiques en un algoritme de clau pública (asimètric), evitant el problema de Man-in-the-middle, i a la seua volta comprovant que la clau pública siga distinta de 0 i 1.
• Usar un tercer (Carol) en el que o be Alice o be Bob mantenen un canal segur. Este tercer pot detectar el man-in-the-middle

si Alice o Bob estan sent escoltats/modificats, simplement desafiant a abdós a una prova implicant en dita prova la clau pública de l'atre. Si Mallory tergiversa la comunicació Alice-Bob, i també l'Alice-Carol, no pot tergiversar el canal segur Bob-Carol i serà detectat. I si tergiversa l'Alice-Bob i la Bob-Carol, no pot tergiversar l'Alice-Carol (per definició deu haver algun canal segur entre dos dels tres, encara que els atres dos canals siguen tergiversats per Mallory). Açò significa que el método Diffie-Hellman pot crear rets de múltiples nodos 100% segures, a partir de tan sol dos nodos prèviament segurs. Este método també servix per a testear canals que se sospita que puguen ser insegurs.

Eixemple

Alice Sec Calc p, g a ga mod p … (gb mod p)a mod p

$\to$ $\leftarrow$ =

Bob Calc Sec p, g b … gb mod p (ga mod p)b mod p

Alice i Bob acorden usar l'número primo p=23 i la base g=5. Alice elegix un número secret a=6, després envia a Bob (ga mod p) 56 mod 23 = 8. Bob elegix un número secret b=15, després envia a Alice (gb mod p) 515 mod 23 = 19. Alice calcula (gb mod p)a mod p 196 mod 23 = 2. Bob calcula (ga mod p)b mod p 815 mod 23 = 2.

Eixemple en implementació de sifrat

La necessitat per a este eixemple és: Bob necessita enviar-li un text sifrat a Alice pero sense compartir la clau de sifrat. ¿Cóm ho fa?

1. Alice elegix un número secret a=6, l'número primo p=23 i la base g=5. Després envia a Bob la clau pública d'Alice (g^a mod p), p i g:
   • 5⁶ mod 23 = 8.
   • 23
   • 5
2. Bob elegix un número secret b=15, després Bob calcula la clau de sifrat comuna (g^a mod p)^b mod p
   • 8¹⁵ mod 23 = 2.
3. Bob sifra, en un cifrador simètric com AES, el text clar usant la clau de sifrat generada.
4. TextoCifrado = CifradorSimetrico ( TextoClaro, 2 )
5. Bob envia a Alice el text sifrat i la clau pública de Bob (g^b mod p)
   • 5¹⁵ mod 23 = 19.
   • TextoCifrado
6. Alice calcula (g^b mod p)^a mod p
   • 19⁶ mod 23 = 2.
7. Alice usa eixa clau de sifrat generada per a dessifrar les senyes enviades per Bob
8. TextoClaro = DescifradorSimetrico ( TextoCifrado, 2 )

Valors molt més grans de a,b i p es necessitarien per a fer este eixemple segur. Ya que és molt senzill provar tots els valors possibles de g^ab mod 23 (hi haurà, com a màxim, 22 valors, inclusivament si a i b són números grans).

Òbviament la necessitat d'Alice d'enviar-li a Bob l'informació sifrada també la cobrix l'implementació.

Generalisacions

Aumentant el número de parts

L'idea de l'algoritme podem generalisar-la a la negociació de claus entre més de dos entitats. Vejam un eixemple per a tres entitats i a partir d'ahí podem aumentar el número de parts de forma fàcil:

1. Les parts (Alice, Bob i Carol) es posen d'acort en els paràmetros de l'algoritme $p$ i $g$.
2. Les parts generen les seues pròpies claus privades cridades $a$, $b$, i $c$ respectivament.
3. Alice calcula $g^{a}modp$ i ho envia a Bob.
4. Bob calcula $(g^a{)}^{b}modp=g^{ab}modp$ i ho envia a Carol.
5. Carol calcula $(g^{ab}{)}^{c}modp=g^{abc}modp$ i l'usa com la seua clau secreta.
6. Bob calcula $g^{b}modp$ i ho envia a Carol.
7. Carol calcula $(g^b{)}^{c}modp=g^{bc}modp$ i ho envia a Alice.
8. Alice calcula $(g^{bc}{)}^{a}modp=g^{bca}modp=g^{abc}modp$ i ho usa com la seua clau secreta.

1. Carol calcula $g^{c}modp$ i ho envia a Alice.
2. Alice calcula $(g^c{)}^{a}modp=g^{ca}modp$ i ho envia a Bob.
3. Bob calcula $(g^{ca}{)}^{b}modp=g^{cab}modp=g^{abc}modp$ i ho usa com la seua clau secreta.

Canviant de grup

Podem generalisar el protocol i els seus derivats si en lloc de basar-nos en el grup ${𝐙}_p^{*}$ nos basem en atres grups que complixquen les condicions necessàries per a poder aplicar l'algoritme (GDHP<-Generalized Diffie-Hellman Problem)

Formalisació

1. Els usuaris A i B seleccionen públicament un grup multiplicativo finito G d'orde n i generador $g\in G$ l'operació del qual multiplicació és una operació d'una via (no té inversa o difícilment invertible)
2. L'usuari A genera un número aleatori a,$1\le a\le n-1$, calcula $g^a\in G$ i transmet este element a B, mantenint secret a #

L'usuari B genera un número aleatori b,$1\le b\le n-1$, calcula $g^b\in G$ i transmet este element a A, mantenint secret b

1. L'usuari A rep $g^b$ i calcula $(g^b{)}^a\in G$
2. L'usuari B rep $g^a$ i calcula $(g^a{)}^b\in G$
3. A i B posseïxen un element comú secret del grup $g^{a\cdot b}$

Eixemples

Eixemples de grups que podríem usar: El grup multiplicativo anàlec dels camps de Galois ${𝔽}_{2^n}$, el grup de punts definits per una curva elíptica sobre un cos finito.

Bibliografia adicional

• Menezes, A.J., P.C. van Oorschot i S.A. Vanstone. Handbook of Applied Cryptography. Boca Raton, Fl.: CRC Press, 1997.
• Plantilla:Cita IETF