L’algoritmo Diffie-Helman rappresenta il primo esempio di crittografia a chiave pubblica. In particolare, esso consente a 2 utenti che vogliono comunicare in modo “sicuro”, di scambiarsi una chiave segreta da usare in fase di cifratura/decifratura.
La robustezza di tale algoritmo si basa sostanzialmente sulla difficoltà di calcolo dei logaritmi discreti. Quindi, per capire bene il funzionamento dell’algoritmo in questione, occorre definire in modo chiaro cos’è un logaritmo discreto.
Sia a la radice primitiva di un numero primo p, dove per radice primitiva si intende il numero le cui potenze generano tutti gli interi compresi tra 1 e p-1. In altre parole, i seguenti valori:
a mod p, a^2 mod p, …, a^p-1 mod p
saranno tutti compresi nell’intervallo [1, p-1]. Notate che sto utilizzando il modulo in quanto abbiamo a che fare con numeri discreti.
Ora, dato un qualunque numero intero b ed una radice primitiva a di un numero primo p, allora è possibile trovare un unico esponente i tale che:
b = a^i mod p
dove 0 <= i <= (p-1). L’esponente i rappresenta proprio il logaritmo discreto di b rispetto alla base a mod p e può essere rappresentato mediante la seguente notazione:
i = dloga,p(b)
Bene, ora che sappiamo cosa si intende per logaritmo discreto, possiamo illustrare il funzionamento dell’algoritmo Diffie-Helman.
Supponiamo che 2 utenti (A e B) vogliano instaurare una comunicazione bidirezionale cifrata. Essi utilizzeranno due valori pubblici, ovvero q ed a, con q numero primo ed a radice primitiva di q.
A questo punto, l’utente A sceglierà un intero casuale XA, con XA < q, che manterrà segreto. Successivamente, calcolerà YA, ovvero la chiave pubblica, dove:
YA = a^XA mod q
Tale operazione verrà effettuata anche dall’utente B, per il quale avremo:
YB = a^XB mod q
Adesso che entrambe le parti hanno generato le rispettive chiavi pubbliche, esse calcoleranno la chiave condivisa (K) nel modo seguente:
Utente A
K = YB^XA
Utente B
K = YA^XB
Ora, si può dimostrare che le due chiavi K così generate sono identiche:
1) K = YB^XA mod q
Sapendo che
2) YB = a^XB mod q
sostituendo la 2) nella 1) avremo:
K = (a^XB mod q)^XA mod q = (a^XB)^XA mod q = (a^XA)^XB mod q = (a^XA mod q)^XB mod q = YA^XB mod q
Facendo il punto della situazione, abbiamo 2 valori privati, ovvero XA ed XB, e 4 valori pubblici: a, q, YA ed YB. Affinchè l’attaccante possa individuare la chiave privata dell’utente B, egli dovrà calcolare:
XB = dloga,q(YB)
che, come affermato in precedenza, è un’operazione molto complessa dal punto di vista computazionale.
Attacchi bruteforce
Nel caso in cui il numero primo q scelto da una delle due parti che vogliono condividere una chiave K sia troppo piccolo, l’attaccante può provare, mediante un approccio a forza bruta, a calcolare uno dei due valori segreti (XA oppure XB).
Ma facciamo un esempio. Supponiamo che q sia pari a 353. Per definizione di algoritmo discreto abbiamo che:
b = a^i mod p
dove b è la chiave pubblica, i il logaritmo discreto in base a mod p ed a rappresenta la radice primitiva di q.
Come già detto in precedenza, i valori associati a b, a e p sono noti, nella fattispecie:
a = 3;
b = 90;
q = 353.
Quindi l’attaccante dovrà risolvere la seguente equazione:
90 = 3^i mod 353
Per trovare il valore di i (che rappresenta proprio la chiave segreta XA o XB, a seconda di quale dei due utenti sia la vittima dell’attacco) gli basterà calcolare tutte le potenze di 3 mod 353 fino a quando non otterrà 90 come risultato. A questo punto calcolerà K utilizzando la chiave pubblica della controparte. Ovviamente tale operazione diventa improponibile per valori di q elevati.
Attacchi replay
Ma come avviene lo scambio dei valori pubblici a e q tra l’utente A e l’utente B? Una possibile soluzione consiste nel concordarli a priori, oppure nel fare in modo che l’utente A (che inizializza la comunicazione) ne calcoli il valore e lo includa, successivamente, nel primo messaggio inviato alla controparte. Un altro approccio prevede l’uso di una directortory condivisa e fidata (per garantire in qualche modo l’autenticità della fonte), in cui salvare le chiavi pubbliche dei vari utenti. In questo caso possono comunque essere attuati degli attacchi di tipo replay.
Attacchi man-in-the-middle
Analizziamo il seguente scenario: supponiamo che Alice (utente A) e Bob (utente B) vogliano scambiarsi una chiave segreta, e che Darth (l’attaccante, ovvero l’utente D) sia in grado di intercettare le chiavi pubbliche di Alice (YA) e di Bob (YB) (nel momento in cui avviene lo scambio delle stesse).
Prima di intercettare le chiavi, l’utente D genererà una coppia di valori privati, ovvero XD1 ed XD2, che verranno usati per creare rispettivamente le chiavi pubbliche YD1 ed YD2. Nel momento in cui A invierà a B la propria chiave pubblica (ovvero YA), l’utente D la intercetterà e la sostituirà con YD1.
A questo punto, l’utente D è in possesso della chiave pubblica di A e la utilizzerà per calcolare la chiave condivisa K2:
K2 = YA^XD2 mod q
L’utente B, avendo ricevuto YD1 come chiave pubblica dell’utente A, calcolerà anch’egli K2:
K2 = YD1^XB mod q
A questo punto l’utente B invierà all’utente A la propria chiave pubblica YB. Essa verrà intercettata dall’utente D e sostituita dallo stesso con YD2.
L’utente A, convinto che YD2 sia la chiave pubblica dell’utente B, calcolerà la chiave condivisa K1:
K1 = YD2^XA mod q
Anche l’utente D calcolerà la chiave condivisa K1:
K1 = YB^XD1 mod q
Ora, l’utente A e l’utente B crederanno di condividere una chiave segreta K. In realtà, l’utente A condivide con l’utente D la chiave K1, mentre l’utente B condivide, sempre con l’utente D, la chiave K2. Darth può quindi: intercettare le comunicazioni provenienti da Alice o da Bob e/o alterare le informazioni dirette da Alice verso Bob e viceversa (tampering). Da ciò si deduce che l’algoritmo Diffie-Helman non può essere utilizzato nell’ambito della cifratura simmetrica (dato che non garantisce l’autenticazione della fonte), tornando comunque utile per lo scambio di una chiave segreta ad autenticazioni delle parti avvenuta.
Fine del post, a presto.