I ricercatori dell'Università della California, San Diego, hanno sviluppato una tecnica avanzata di attacco all'algoritmo RSA, che consente di falsificare le firme digitali senza la necessità di fattorizzare i numeri primi alla base del RSA e senza dover recuperare la chiave privata. Le risorse necessarie per eseguire un attacco su una chiave RSA di 1024 bit sono state stimate in 1380 anni di calcoli su un singolo core di processore, il che ha permesso, sul cluster dell'università, di determinare in 5 mesi i parametri necessari per generare firme RSA fittizie (nell'esperimento non sono stati utilizzati acceleratori AI e GPU; utilizzandoli, il tempo di calcolo può ridursi significativamente). A titolo di confronto, il metodo classico di fattorizzazione richiede tra 500.000 e un milione di anni di calcolo su un singolo core di processore per ricreare la chiave privata RSA-1024.
Per eseguire l'attacco è necessaria la possibilità di inviare ripetutamente richieste per la firma dei dati generati dall'attaccante, ad esempio collegandosi a un servizio di autorizzazione o a un modulo HSM. Per determinare i parametri RSA-1024 è sufficiente inviare 232 di queste richieste, mentre per attaccare le chiavi RSA-2048 utilizzate nel protocollo Privacy Pass servono 243. Una volta ottenuto un insieme di dati firmati, inizia un lungo processo di calcolo dei parametri (per RSA-1024 sono circa 265 operazioni); dopo averli ottenuti, l'attaccante può creare firme fittizie per qualsiasi dato, impiegando circa 180 ore di calcolo su un singolo core per ogni firma.
Il metodo è applicabile solo per le firme RSA in cui non è utilizzato il formato e il riempimento aggiuntivo prima della crittografia (padding). Sono vulnerabili le implementazioni della firma cieca, incluse quelle utilizzate nel protocollo Privacy Pass. La maggior parte delle implementazioni RSA comuni, inclusi PKCS#1v1.5 e RSA-PSS (utilizzate in TLS e SSH), applicano un riempimento aggiuntivo e non sono vulnerabili all'attacco.
Alla base della crittografia RSA c'è l'operazione di elevazione a potenza modulo un grande numero. La chiave pubblica contiene il modulo e l'esponente. Il modulo è formato da due numeri primi casuali, noti solo al proprietario della chiave privata. Il metodo proposto si basa su uno studio pubblicato nel 2007, che ha dimostrato che estrarre la radice dell'esponente indicato nella chiave pubblica da un messaggio crittografato, senza informazioni sui fattori segreti, è un'operazione meno dispendiosa in termini di risorse rispetto alla fattorizzazione dei fattori stessi.
Utilizzando un metodo speciale conosciuto come il setaccio del campo numerico (SNFS), i ricercatori sono riusciti a ridurre la complessità della compromissione delle chiavi RSA-1024 a 265 operazioni, rendendo possibili attacchi pratici su cluster moderni. Per le chiavi RSA da 2048 bit, la complessità dell'attacco è stimata in 290, teoricamente realizzabile da grandi aziende o agenzie dei servizi segreti. Per le chiavi da 4096 bit, la complessità dell'attacco ammonta a 2119 operazioni, che attualmente è impraticabile, ma al di sotto del minimo di 2128 raccomandato dalla NSA, dal National Institute of Standards and Technology e dall'Agenzia europea per la sicurezza delle reti e dell'informazione.
Fonte: opennet.ru
