Un nuovo attacco ha messo facilmente fuori uso un potenziale algoritmo di crittografia

Apr 14, 2023

Dan Goodin, Ars Technica

Nella campagna in corso del governo statunitense per proteggere i dati nell’era dei computer quantistici, un nuovo e potente attacco che ha utilizzato un singolo computer tradizionale per violare completamente un candidato del quarto round evidenzia i rischi connessi alla standardizzazione della prossima generazione di algoritmi di crittografia.

Questa storia è apparsa originariamente su Ars Technica, una fonte affidabile di notizie sulla tecnologia, analisi delle politiche tecnologiche, recensioni e altro ancora. Ars è di proprietà della società madre di WIRED, Condé Nast.

Il mese scorso, il National Institute of Standards and Technology (NIST) degli Stati Uniti, ha selezionato quattro algoritmi di crittografia post-quantistica per sostituire algoritmi come RSA, Diffie-Hellman e Diffie-Hellman a curva ellittica, che non sono in grado di resistere agli attacchi di un sistema quantistico. computer.

Allo stesso tempo, il NIST ha avanzato quattro algoritmi aggiuntivi come potenziali sostituti in attesa di ulteriori test, nella speranza che uno o più di essi possano rappresentare alternative di crittografia adeguate in un mondo post-quantistico. Il nuovo attacco rompe SIKE, che è uno degli ultimi quattro algoritmi aggiuntivi. L'attacco non ha alcun impatto sui quattro algoritmi PQC selezionati dal NIST come standard approvati, i quali si basano tutti su tecniche matematiche completamente diverse da SIKE.

SIKE, abbreviazione di supersingular isogeny key incapsulation, è ora probabilmente fuori gioco, grazie alla ricerca pubblicata lo scorso fine settimana dai ricercatori del gruppo Computer Security and Industrial Cryptography della KU Leuven. L'articolo, intitolato "An Efficient Key Recovery Attack on SIDH (Preliminary Version)", descriveva una tecnica che utilizza matematica complessa e un singolo PC tradizionale per recuperare le chiavi di crittografia che proteggono le transazioni protette da SIKE. L'intero processo richiede solo circa un'ora. L’impresa fa sì che i ricercatori, Wouter Castryck e Thomas Decru, possano beneficiare di una ricompensa di 50.000 dollari da parte del NIST.

"La debolezza appena scoperta è chiaramente un duro colpo per SIKE", ha scritto in una e-mail David Jao, professore all'Università di Waterloo e co-inventore di SIKE. "L'attacco è davvero inaspettato."

L'avvento della crittografia a chiave pubblica negli anni '70 fu un importante passo avanti, perché permise a soggetti che non si erano mai incontrati di scambiare in modo sicuro materiale crittografato che non poteva essere violato da un avversario. La crittografia a chiave pubblica si basa su chiavi asimmetriche, con una chiave privata utilizzata per decrittografare i messaggi e una chiave pubblica separata per la crittografia. Gli utenti rendono la loro chiave pubblica ampiamente disponibile. Finché la loro chiave privata rimane segreta, lo schema rimane sicuro.

In pratica, la crittografia a chiave pubblica può spesso essere ingombrante, quindi molti sistemi si basano su meccanismi di incapsulamento delle chiavi, che consentono a parti che non si sono mai incontrate prima di concordare congiuntamente una chiave simmetrica su un mezzo pubblico come Internet. A differenza degli algoritmi a chiave simmetrica, i meccanismi di incapsulamento delle chiavi in ​​uso oggi possono essere facilmente violati dai computer quantistici. Si pensava che SIKE, prima del nuovo attacco, evitasse tali vulnerabilità utilizzando una complessa costruzione matematica nota come grafico di isogenesi supersingolare.

La pietra angolare di SIKE è un protocollo chiamato SIDH, abbreviazione di isogenesi supersingolare Diffie-Hellman. Il documento di ricerca pubblicato durante il fine settimana mostra come SIDH sia vulnerabile a un teorema noto come "colla e divisione" sviluppato dal matematico Ernst Kani nel 1997, così come agli strumenti ideati dai colleghi matematici Everett W. Howe, Franck Leprévost e Bjorn Poonen nel 2000. La nuova tecnica si basa su quello che è noto come attacco adattivo GPST, descritto in un articolo del 2016. La matematica dietro l’ultimo attacco è sicuramente impenetrabile per la maggior parte dei non matematici. Ecco il punto più vicino a cui potrai arrivare:

"L'attacco sfrutta il fatto che SIDH ha punti ausiliari e che il grado dell'isogenia segreta è noto", ha spiegato in un breve articolo Steven Galbraith, professore di matematica dell'Università di Auckland e la "G" nell'attacco adattivo GPST. sul nuovo attacco. "I punti ausiliari nel SIDH sono sempre stati un fastidio e una potenziale debolezza, e sono stati sfruttati per attacchi di faglia, attacco adattivo GPST, attacchi ai punti di torsione, ecc."