Attacchi ad RSA
Se è stato dimostrato che al momento l’algoritmo RSA non è suscettibile ad attacchi di forza bruta, è bene sottolineare che esso può comunque essere soggetto anche a forme di attacco più intelligenti.
Questi attacchi richiedono in qualche modo il coinvolgimento dei partecipanti (che chiameremo Alice e Bob).
Le forme di attacco che possono essere tentate sono due:
- Attacco 1
l’hacker intercettando i dati scambiati tra Alice e Bob entra in possesso del messaggio cifrato C.
L’hacker può ricavare il messaggio M sfruttando la collaborazione inconsapevole di Alice, destinataria del messaggio M.
Per riuscire nel suo scopo l’hacker sottopone ad Alice un opportuno messaggio Y chiedendole di restituirlo codificato proprio con la chiave privata di Alice.
Il messaggio Y viene costruito dall’hacker nel modo seguente:
1) Sceglie un numero casuale R;
2) ricava X = Re mod n (l’hacker non ha difficoltà a ricavare X in quanto conosce l’esponente e nonchè il modulo n, componenti della chiave pubblica di Alice);3) ricava Y = (X * C) mod n e lo invia ad Alice;
4) ricava T = R-1 mod n.Se Alice, ricevuto Y, esaudisce le richieste dell’hacker come richiesto, la sua risposta vale U = Yd mod n.
A questo punto, disponendo di U, l’hacker è in grado di ricavare il messaggio originario M effettuando la seguente trasformazione: M’ = (T * U) mod n.
Infatti (T * U) mod n = R-1 Yd mod n = R-1 Xd Cd mod n = R-1 RCd mod n = Cd mod n = M.Per evitare che l’attaccante ricavi il messaggio M occorre fare attenzione all’uso che si fa della propria chiave privata.
Ogni partecipante dovrebbe limitarsi a usare la propria chiave privata per codificare messaggi generati localmente.
È profondamente sconsigliato codificare con la propria chiave privata messaggi di origine incerta. - Attacco 2
L’hacker, intercettando i dati inviati da Alice entra in possesso di due copie cifrate dello stesso messaggio (una copia destinata a Bob e una a un terzo partecipante).
Le due copie sono naturalmente codificate utilizzando una chiave pubblica diversa, essendo indirizzate a due diversi destinatari.
Se le due chaivi pubbliche {e1, n1} e {e2, n2} prevedono esponenti e1 ed e2 primi tra loro, ma hanno lo stesso modulo n (ovvero n1 = n2), l’hacker è in grado di ricavare il messaggio M senza bisogno di altre informazioni.
I dati conosciuti dall’hacker sono: n, e1, e2, C1=Me1 mod n, C2=Me2 mod n.
Utilizzando l’algoritmo di Euclide l’hacker è in grado di ricavare due numeri r e s, di cui uno risulta negativo, tali che: re1 + se2 = 1.
Ipotizzando che sia r il numero risultante negativo, l’hacker può determinare M con la seguente trasformazione: M’ = (C1-1)-r * (C2)s mod n.Infatti (C1-1)-r * (C2)s mod n = (Me1r)(Me2s) mod n = M mod n = M.
A differenza della prima forma di attacco, per la quale è richiesta la partecipazione attiva dell’hacker, questa seconda tecnica può avvenire in forma completamente passiva (tramite semplice packet sniffing).
Per scongiurare questo attacco Alice deve prestare la massima attenzione non solo agli esponenti utilizzati dall’algoritmo RSA, ma anche al modulo n.
È opportuno non condividere lo stesso modulo n fra più utenti.
Sotto particolari condizioni esistono altre forme di attacco che possono essere effettuate con successo.
La prima condizione si verifica quando si codificano messaggi troppo brevi.
Per scongiurare questo attacco è opportuno che il messaggio M sia della stessa dimensione del modulo n.
Per garantire questo si ricorre a implementazioni dell’algoritmo che aggiungono bit non significativi al messaggio per aumentare la dimensione finale.
La seconda condizione da evitare si verifica in presenza di un esponente d relativamente piccolo rispetto al modulo n.
Per evitare questo inconveniente occorre scegliere gli esponenti in modo che d risulti grande.
Considerato che, usando l’algoritmo RSA con accortezza è possibile evitare tutte le forme di attacco precedentemente descritte, risulta pienamente comprensibile l’enorme successo incontrato dalle diverse implementazioni dell’algoritmo in ambito telecomunicazioni, e in particolar modo nei principali servizi Internet.
