Lo scambio di chiavi Diffie-Hellman (DH, Diffie-Hellman key exchange) è un protocollo crittografico attraverso cui due entità sono in grado di condividere le proprie chiavi segrete su un canale di comunicazione pubblico, quindi considerato insicuro.
Ora, abbandoniamo per qualche secondo la definizione concisa per una presentazione più leggera.
Seguimi.
Adottando l’approccio problema – soluzione, capiremo perché sia necessario lo scambio di chiavi Diffie-Hellman e come funzioni!
Prima però, lascia che ti spieghi una cosa.
Ho pensato questo post affinché possa essere capito anche da chi non ha alcuna pregressa conoscenza in materia.
Mi perdonerai quindi se alcune spiegazioni ti appariranno banali: sopportale, e ricorda che c’è sempre qualcuno che ne sa meno di te!
Introduzione
Per capire in modo concettuale lo scambio di chiavi Diffie-Hellman, intendo presentarti un semplice problema.
Consideriamo due sconosciuti, Alice (si legge Alis) e Bob, che vogliano scambiarsi un messaggio criptato usando uno schema di crittografia simmetrico (symmetric encryption scheme).
Devi sapere che uno schema di criptazione simmetrico impiega la medesima chiave crittografica sia per la criptazione del testo in chiaro (plaintext) che per la decifrazione del testo cifrato (ciphertext).
Per questa ragione, Alice e Bob hanno bisogno di condividere la chiave per la criptazione e la decifrazione del testo.
Come possono allora accordarsi sulla chiave da impiegare, evitando che Eve intercetti (eavesdropping) tutte le loro comunicazioni?
Caratteristiche dello scambio chiavi Diffie-Hellman
La soluzione al problema è trovare due funzioni unidirezionali (one-way functions) basate su parametro segreto (secret-based), la cui composizione è cumulativa (cumulative composition).
Questa parte è importante perché contiene i principi su cui si basa lo scambio di chiavi Diffie-Hellman (DH)
Analizziamo insieme ciascuno dei termini.
- Funzioni unidirezionali: sono funzioni per cui è semplice calcolare l’output dall’input, ma è molto difficile fare il processo opposto. Un esempio è l’impiego di una funzione di hash che aggiunge una parola (salt) a una stringa, rendendo unica la stringa di hash.
- basate su un parametro segreto: per applicare la funzione a un input è necessario conoscere il parametro segreto.
- composizione: la composizione di funzioni consiste nel combinare due o più funzioni in una singola funzione (e.g. A(x) = x + 5, B(x) = x * 3, AB(x) = A(B(X))
- cumulativa: significa che l’ordine non cambia, per cui A(B(x)) produce lo stesso risultato di B(A(x))
Per completezza d’informazione, l’esempio delle funzioni che ti ho proposto non è cumulativo perché aggiungere 5 e moltiplicare per 3 produce un risultato diverso se eseguito in diverso ordine.
Ti faccio inoltre notare che le funzioni di hash sebbene siano unidirezionali, non soddisfano generalmente il requisito di composizione cumulativa.
Ora ci siamo: è arrivato il momento di capire come funzioni lo scambio di chiavi Diffie-Hellman.
Come funziona lo scambio chiavi di Diffie-Hellman (DH)?
La proposta iniziale di Diffie e Hellamn è di usare l’ esponenziazione modulare, un’operazione in grado di calcolare il resto quando un intero b (la base) elevato all’ e-esima potenza (l’esponente) viene diviso per un intero positivo m (il modulo).
Pertanto l’esponenziazione modulare c calcolata sulla base b, l’ esponente e e il modulo m assume la forma di:
c = be mod m
Questa funzione ha la particolarità di rendere complesso il calcolo di b ed e dato solo il risultato del modulo di m.
Prendendo allora due esponenti segreti a e b otteniamo altrettante funzioni unidirezionali, dalla composizione cumulativa:
- f1 (x) = xa mod p
- f2 (x) = xb mod p
Per rompere il protocollo sarebbe necessario risolvere il problema del logaritmo discreto, che richiede un tempo computazionale tale per cui il Diffie-Hellman exchange protocol risulti al momento sicuro.
Il protocollo Diffie-Hellman (DH)
Ecco allora le fasi necessarie per l’applicazione del Diffie-Hellman.
- Alice genera una chiave privata a e sceglie un numero primo p grande, e un numero g radice primitiva modulo p (i.e. un intero g le cui potenze modulo n sono congruenti con i numeri coprimi a n)
- Poi calcola A = ga mod p
- Quindi Alice invia p, g e il valore A a Bob.
- Bob a sua volta genera casualmente una chiave privata b.
- Poi calcola gab mod p calcolando Ab mod p.
- Quindi calcola B = gb mod p
- Infine Bob invia il valore calcolato B indietro ad Alice.
- Alice può ora calcolare gab mod p calcolando Ba mod p.
I due sconosciuti condividono ora una chiave privata gab mod p.
Eve, che ha intercettato le comunicazioni, conosce solo g,p, A e B. Non può derivare la chiave segreta a dal valore A, così come quella b dal valore B senza risolvere il problema del logaritmo discreto che ti accennavo prima.
Senza questi valori non è in grado di calcolare la chiave privata condivisa.
Limitazioni del protocollo Diffie-Hellman (DH)
Purtroppo il protocollo Diffie-Hellman, seppur robusto contro gli eavesdropper, è suscettibile ad attacchi di tipo Man in the middle.
Durante un attacco di questo tipo, un agente terzo sarebbe in grado di falsificare le chiavi pubbliche di Alice e Bob, ingannando le due parti senza che queste possano accorgersene.
Senza dilungarci troppo, una soluzione a questo problema è quella di usare un servizio di autenticazione (i.e. un algoritmo o una Certifiction Authority) per certificare la bontà delle chiavi.
Una variante del protocollo DH, è il DH-EKE che aggiunge un fase di mutua autenticazione, basata su password, allo scambio delle chiavi.
Conclusione
Il protocollo Diffie-Hellman (DH) può essere usato per la creazione di protocolli di Private Set Intersection, una tecnica per calcolare l’intersezione tra dati tutelando la privacy degli stessi.
Questo post è quindi parte della serie sulle tecnologie di Privacy Preserving Machine Learning.
Per il momento è tutto.
Per aspera, ad astra.
Un caldo abbraccio, Andrea
Per approfondire, ti consiglio di dare un’occhiata a questo post.
