RSA si può attaccare senza fattorizzare la chiave: svolta storica

RSA è uno degli algoritmi crittografici più importanti della storia dell’informatica moderna. Ideato alla fine degli anni ’70 da Ron Rivest, Adi Shamir e Leonard Adleman, ha reso possibile usare una coppia di chiavi differenti – una pubblica e una privata – per proteggere comunicazioni, verificare identità e soprattutto creare firme digitali difficili da falsificare.

Come abbiamo spiegato nell’articolo sulla sicurezza di RSA, per quasi 50 anni l’affidabilità dell’algoritmo è stata associata alla difficoltà di scomporre un enorme numero intero nei due fattori primi che lo hanno generato. È la ragione per cui la lunghezza del modulo RSA – 1024, 2048, 3072 o 4096 bit – si traduce abitualmente in una stima della quantità di lavoro necessaria a un attaccante.

Un nuovo risultato ottenuto dai ricercatori della University of California San Diego e di INRIA mostra però che, in alcune condizioni molto precise, esiste una strada assai meno costosa: falsificare firme RSA senza fattorizzare affatto il modulo pubblico.

Perché RSA è sempre stato legato alla fattorizzazione

RSA nasce nel 1977 e si basa su un’idea semplice da descrivere: si scelgono due grandi numeri primi e li si moltiplica tra loro. Il risultato entra nella chiave pubblica, mentre i due numeri originali servono per costruire la chiave privata.

La sicurezza dipende proprio da questa asimmetria. Moltiplicare due numeri primi enormi è facile per un computer; partire dal loro prodotto e risalire ai due fattori, invece, diventa estremamente difficile quando i numeri raggiungono le dimensioni usate in crittografia.

Quando RSA viene utilizzato per creare una firma digitale, il software calcola prima una sorta di impronta del messaggio, cioè il suo hash, e la elabora secondo lo schema di firma adottato. La chiave privata applica quindi una trasformazione matematica a quel valore e produce la firma. Chi riceve il documento può controllarla usando la chiave pubblica: se la verifica riesce, può stabilire che la firma è compatibile con quella chiave privata e che il contenuto non è stato modificato.

Per questo, per decenni, “rompere RSA” è stato quasi sinonimo di riuscire a fattorizzare il grande numero contenuto nella chiave pubblica: lo abbiamo spiegato nell’articolo citato in apertura. Ma non è sempre necessario arrivare fin lì. Alcune modalità d’uso di RSA possono esporre operazioni o proprietà matematiche che offrono all’attaccante una strada diversa. Il nuovo lavoro sfrutta proprio una di queste scorciatoie: non ricava i due numeri primi originali e non recupera direttamente la chiave privata, ma riesce comunque a costruire firme valide in condizioni molto specifiche.

La novità: falsificare una firma RSA senza scoprire la chiave privata

La novità sta proprio qui. I ricercatori hanno dimostrato che, in una particolare modalità d’uso di RSA, un attaccante può arrivare a produrre una firma valida senza conoscere la chiave privata e senza prima fattorizzare il modulo pubblico.

È un risultato importante perché, fino a oggi, il modo più naturale di immaginare un attacco di questo tipo era molto più costoso: partire dalla chiave pubblica, fattorizzare il grande numero che contiene, ricostruire la chiave privata e soltanto a quel punto generare le firme desiderate.

Il nuovo metodo non “indovina” la chiave e non la estrae dal sistema. Sfrutta piuttosto un servizio che esegue operazioni RSA per conto dell’utente e che accetta valori scelti dall’attaccante. In crittografia un servizio del genere viene chiamato oracle: gli si forniscono determinati input e si osservano le risposte ottenute.

Immaginiamo, per esempio, un dispositivo che custodisce una chiave privata RSA e permette di inviare valori da elaborare con quella chiave. L’attaccante non vede mai il segreto custodito all’interno, ma può sottoporre una grande quantità di richieste costruite con attenzione e raccogliere i risultati. Il nuovo attacco dimostra che quelle risposte, combinate con una tecnica matematica specifica, possono fornire informazioni sufficienti per costruire in seguito altre firme valide.

Il test su RSA a 1024 bit: da 1 milione core-year a 1.380 core-year

I ricercatori non si sono limitati a descrivere l’attacco sulla carta. Lo hanno eseguito realmente contro RSA a 1024 bit, una dimensione oggi considerata obsoleta ma ancora molto utile per misurare concretamente il costo della nuova tecnica.

Secondo le stime riportate nel lavoro, fattorizzare direttamente un modulo RSA-1024 con le tecniche migliori oggi disponibili richiederebbe tra circa 500.000 e un milione di CPU core-year. Un core-year equivale, semplificando, al lavoro svolto da un singolo core del processore lasciato in esecuzione per un anno.

La falsificazione realizzata dal gruppo ha richiesto invece circa 1.380 core-year, distribuiti su un’infrastruttura di calcolo parallelo. L’esperimento è durato circa 5 mesi e il miglioramento rispetto alla fattorizzazione diretta non è quindi di qualche punto percentuale: parliamo di diversi ordini di grandezza.

Per arrivare al risultato, però, l’attaccante deve prima poter interrogare moltissime volte il servizio RSA vulnerabile. Nell’esperimento sono servite circa 2³² richieste, vale a dire oltre quattro miliardi di operazioni.

RSA non è improvvisamente “rotto”

Il nuovo metodo non funziona contro qualsiasi implementazione dell’algoritmo RSA: richiede una situazione piuttosto specifica, nella quale l’attaccante può sottoporre valori scelti liberamente a un sistema che esegue una trasformazione RSA con la chiave privata.

Le normali firme RSA impiegate oggi utilizzano generalmente schemi come PKCS#1 v1.5 oppure RSA-PSS. Prima dell’operazione matematica vera e propria, questi formati preparano il messaggio secondo regole precise e impediscono all’attaccante di controllare liberamente il valore sottoposto alla chiave privata. Il nuovo attacco non si applica quindi direttamente alla grande maggioranza delle firme RSA in uso.

Il problema riguarda soprattutto costruzioni particolari, nelle quali il protocollo permette intenzionalmente a un utente di presentare valori trasformati a un server che li firma senza conoscerne direttamente il contenuto originale.

La conclusione corretta non è “RSA-2048 è stato violato“. La scoperta dice qualcosa di più sottile, ma molto interessante per chi si occupa di crittografia: in determinate condizioni, la sicurezza di RSA non dipende più soltanto dal costo della fattorizzazione. Un attaccante può riuscire a produrre firme valide seguendo una strada diversa e molto meno onerosa dal punto di vista computazionale.