Scambio di chiavi Diffie-Hellman

Lo scambio di chiavi Diffie-Hellman-Merkle (in inglese Diffie-Hellman-Merkle key exchange) è un protocollo crittografico che consente a due entità di stabilire una chiave condivisa e segreta utilizzando un canale di comunicazione insicuro (pubblico) senza la necessità che le due parti si siano scambiate informazioni o si siano incontrate in precedenza. La chiave ottenuta mediante questo protocollo può essere successivamente impiegata per cifrare le comunicazioni successive tramite uno schema di crittografia simmetrica.

Sebbene l'algoritmo in sé sia anonimo (vale a dire non autenticato) è alla base di numerosi protocolli autenticati ed è usato anche in alcune modalità di funzionamento del protocollo TLS.

Storia

Lo schema del protocollo Diffie-Hellman fu pubblicato per la prima volta nel 1976 nell'ambito di una collaborazione tra Whitfield Diffie e Martin Hellman e fu il primo metodo pratico per due interlocutori di accordarsi su un segreto condiviso (la chiave) utilizzando un canale di comunicazione non protetto. Il lavoro di Ralph Merkle sulla distribuzione delle chiavi pubbliche (i Puzzle di Merkle) ed il suggerimento da parte di John Gill di utilizzare il problema dei logaritmi discreti come base per la creazione di funzioni unidirezionali servirono da linee guida per lo sviluppo dell'algoritmo. Alla medesima idea erano giunti tuttavia anche alcuni ricercatori (Malcolm J. Williamson, James H. Ellis, Clifford C. Cocks) del GCHQ alcuni anni prima (1973) delle pubblicazioni di Diffie-Hellman e di quelle, risalenti al 1977, ad opera di Ron Rivest, Adi Shamir e Leonard Adleman del MIT che descrivono il noto algoritmo di crittografia asimmetrica conosciuto come RSA, ma i documenti riguardanti l'invenzione, all'epoca giudicata tecnologicamente impraticabile, sono stati segretati fino al 1997.

Nel 2002, Hellman scrisse:

(EN)

«The system (...) has since become known as 'Diffie-Hellman key exchange'. While that system was first described in a paper by Diffie and me, it is a public key distribution system, a concept developed by Merkle, and hence should be called 'Diffie-Hellman-Merkle key exchange' if names are to be associated with it. I hope this small pulpit might help in that endeavor to recognize Merkle's equal contribution to the invention of public key cryptography.»

(IT)

«Da quella volta il sistema (...) è stato conosciuto con il nome di 'Diffie-Hellman key exchange'. Sebbene questo sistema fu descritto per la prima volta in una pubblicazione firmata da me e Diffie, esso è un sistema di distribuzione di chiave pubblica, un concetto sviluppato da Merkle, e quindi, se dovessimo associarvi dei nomi, dovrebbe chiamarsi 'Diffie-Hellman-Merkle key exchange'. Spero che questo piccolo intervento possa aiutare l'intento di dare il giusto riconoscimento al contributo di Merkle all'invenzione della crittografia a chiave pubblica.»

Il brevetto (EN) US4,200,770, United States Patent and Trademark Office, Stati Uniti d'America., ora scaduto, descrive l'algoritmo e riporta Hellman, Diffie e Merkle come inventori.

Descrizione

Nell'implementazione originale (e più semplice) del protocollo si considera inizialmente un numero g, generatore del gruppo moltiplicativo degli interi modulo p, dove p è un numero primo. Uno dei due interlocutori, ad esempio Alice, sceglie un numero casuale "a" e calcola il valore A = g^a mod p (dove mod indica l'operazione modulo, ovvero il resto della divisione intera) e lo invia attraverso il canale pubblico a Bob (l'altro interlocutore), assieme ai valori g e p. Bob da parte sua sceglie un numero casuale "b" , calcola B = g^b mod p e lo invia ad Alice. A questo punto Alice calcola K_A = B^a mod p, mentre Bob calcola K_B = A^b mod p.
I valori calcolati sono gli stessi, in quanto B^a mod p = A^b mod p.
A questo punto i due interlocutori sono entrambi in possesso della chiave segreta e possono cominciare ad usarla per cifrare le comunicazioni successive.
Un attaccante può ascoltare tutto lo scambio, ma per calcolare i valori a e b avrebbe bisogno di risolvere l'operazione del logaritmo discreto, che è computazionalmente onerosa e richiede parecchio tempo, in quanto sub-esponenziale (sicuramente molto più del tempo di conversazione tra i 2 interlocutori).

Esempio di funzionamento

Un esempio del funzionamento del protocollo è il seguente; vengono mostrati in verde i valori non segreti, in grassetto rosso i valori segreti.

Alice
Segreto	Pubblico	Calcola
	p, g
a
		g^a mod p

K_A=(g^b mod p)^a mod p

$\rightarrow$

$\leftarrow$

=

Bob
Calcola	Pubblico	Segreto
	p, g
		b

g^b mod p
		K_B=(g^a mod p)^b mod p

Alice e Bob si accordano di usare un numero primo p = 23 e la base g = 5.
Alice sceglie un numero segreto a = 6 e manda a Bob A = g^a mod p
- A = 5⁶ mod 23 = 8
Bob sceglie l'intero segreto b = 15 e manda ad Alice B = g^b mod p
- B = 5¹⁵ mod 23 = 19.
Alice calcola K_A = (g^b mod p)^a mod p = B^a mod p
- K_A = 19⁶ mod 23 = 2.
Bob calcola K_B = (g^a mod p)^b mod p = A^b mod p
- K_B = 8¹⁵ mod 23 = 2.

Alice e Bob trovano lo stesso risultato perché g^ab e g^ba sono uguali. Si noti come solo a, b e g^ab = g^ba sono segreti. Tutti gli altri numeri sono mandati in chiaro, ossia pubblici. Una volta che Alice e Bob calcolano la chiave segreta, essa può esser usata come chiave di criptazione, conosciuta solo a loro, per mandare messaggi tramite il canale di comunicazione in chiaro.

Chiaramente i valori di a, b e p devono esser molto maggiori di quelli usati nell'esempio; infatti sarebbe facile provare tutti i possibili valori di g^ab mod 23 (vi sono in ogni caso al massimo 23 valori anche se a e b sono grandi). Se p è un primo di almeno 300 cifre e a e b sono almeno di 100 cifre, il miglior algoritmo conosciuto oggigiorno non può trovare il valore di a (il numero segreto), a partire dalla conoscenza di g, p e g^a mod p usando tutta la potenza computazionale della terra. Questo è il problema del logaritmo discreto. Si noti come g non debba esser grande, infatti nella pratica è spesso 2 o 5.

Descrizione più generale del protocollo:

Alice e Bob concordano un gruppo ciclico G e un elemento generatore g appartenente a G. (Questo è generalmente fatto molto prima dell'utilizzo vero e proprio del protocollo; si assume che g sia conosciuto dai possibili malintenzionati.)
Alice sceglie un numero naturale casuale a e invia g^a a Bob.
Bob sceglie un numero naturale casuale b e invia g^b ad Alice.
Alice calcola (g^b)^a.
Bob calcola (g^a)^b.

Sia Bob che Alice sono ora in possesso dell'elemento g^ab, che servirà loro da chiave condivisa per cifrare un messaggio. I valori (g^b)^a e (g^a)^b sono uguali perché i gruppi sono con potenza associativa. (Vedi anche elevamento a potenza.)

Esempio con attacco di tipo eavesdropping

Per spiegare meglio i concetti di cui sopra, si procede con un esempio, considerando un semplice attacco al canale di comunicazione tra Alice e Bob. Eve è un "eavesdropper", cioè può intercettare le comunicazioni tra Alice e Bob, ma non alterare i contenuti delle comunicazioni.

Posto s = chiave segreta condivisa. s = 2
Posto a = chiave privata di Alice. a = 6
Posto b = chiave privata di Bob. b = 15
Posto g = base pubblica. g = 5
Posto p = numero primo pubblico. p = 23

Alice
conosce	non conosce
p = 23	b = ?
base g = 5
a = 6
A = 5⁶ mod 23 = 8
B = 5^b mod 23 = 19
K_A = 19⁶ mod 23 = 2
K_B = 8^b mod 23 = 2
K_A = K_B = 2

Bob
conosce	non conosce
p = 23	a = ?
base g = 5
b = 15
B = 5¹⁵ mod 23 = 19
A = 5^a mod 23 = 8
K_B = 8¹⁵ mod 23 = 2
K_A = 19^a mod 23 = 2
K_B = K_A = 2

Eve
conosce	non conosce
p = 23	a = ?
base g = 5	b = ?
	K_A = K_B = ?
A = 5^a mod 23 = 8
B = 5^b mod 23 = 19
K_A = 19^a mod 23 = ?
K_B = 8^b mod 23 = ?

Nota: deve essere difficile (deve richiedere troppo tempo di calcolo) per Alice ed Eve trovare la chiave privata di Bob, ugualmente per Bob ed Eve trovare la chiave privata di Alice. In caso contrario, Eve potrebbe trovare le chiavi dei due e utilizzarle per mettersi in mezzo, facendo credere a Bob di essere Alice, e ad Alice di essere Bob. In questo caso si avvierebbero due comunicazioni cifrate, una tra Alice ed Eve, e una tra Eve e Bob (e la sicurezza della comunicazione sarebbe completamente aggirata). Questo esempio mostra come sia importantissima l'autenticazione delle due parti che vogliono comunicare in modo sicuro.

Livello di sicurezza

Il protocollo è considerato sicuro contro gli eavesdropper se g e G sono scelti in modo appropriato. "Eve" deve risolvere il problema di Diffie-Hellman ottenendo g^ab. Questo oggi è considerato difficile. Un efficiente algoritmo per risolvere il problema del logaritmo discreto semplificherebbe il calcolo di a o b risolvendo il problema, e rendendo non più sicuri molti sistemi crittografici.

L'algoritmo Diffie-Hellman è resistente all'attacco "Man in the middle" se questo avviene dopo la generazione delle chiavi, tuttavia è invece vulnerabile se un agente terzo falsifica fin dall'inizio le informazioni pubbliche impiegate da Alice e Bob ed inganna le due parti.

L'algoritmo infatti attua lo scambio delle chiavi simmetriche segrete, ma con il presupposto di avere delle informazioni pubbliche condivise e si dimostra resistente nei confronti dell'intercettamento di queste ultime (a partire dalle informazioni pubbliche non si riesce a ricostruire la chiave, è computazionalmente difficile). Ma nulla può impedire che queste siano state modificate o falsificate; in questo caso Alice e Bob non avrebbero modo di accorgersi della frode appoggiandosi al solo algoritmo Diffie-Hellman, ma dovrebbero avere una fonte terza per verificarle. Ecco perché occorre che le informazioni pubbliche, ovvero le chiavi p e g degli esempi, possano essere autenticate tramite un algoritmo di autenticazione o da un Certification Authority.

Una variante del protocollo è DH-EKE, facente parte della famiglia Encrypted Key Exchange, che aggiunge allo scambio di chiavi una fase di (mutua) autenticazione basata su password.

Bibliografia

(EN) Martin E. Hellman, An overview of public key cryptography, in IEEE Communications Society Magazine, vol. 16, n. 6, novembre 1978, pp. 24–32, DOI:10.1109/MCOM.1978.1089772. URL consultato il 7 maggio 2024.
(EN) Martin E. Hellman, Bailey W. Diffie e Ralph C. Merkle, Cryptographic apparatus and method, US4200770A, 29 aprile 1980. URL consultato il 7 maggio 2024.