Articolo Pubblicazioni

La competizione NIST sulla crittografia post-quantum (2016): perché è iniziata e come funzionerà

di · Pubblicato il 28 dicembre 2016

Abstract

Il 20 dicembre 2016 il NIST ha aperto un processo pubblico per selezionare e standardizzare algoritmi di crittografia a chiave pubblica resistenti ai computer quantistici, con scadenza per le proposte a novembre 2017. L’articolo spiega perché i computer quantistici minacciano RSA e la crittografia a curve ellittiche, quali famiglie matematiche sono candidate, come si svolgerà la selezione e perché la transizione deve essere pianificata con anni di anticipo.

Vincenzo Calabrò | La competizione NIST sulla crittografia post-quantum (2016): perché è iniziata e come funzionerà
 

La minaccia

La crittografia a chiave pubblica usata oggi su Internet si basa su problemi matematici difficili per i computer classici. RSA si fonda sulla difficoltà di scomporre grandi numeri in fattori primi, Diffie-Hellman e la crittografia a curve ellittiche sulla difficoltà del logaritmo discreto. Nel 1994 Peter Shor ha mostrato che un computer quantistico sufficientemente grande potrebbe risolvere entrambi i problemi in tempi ragionevoli. Se un computer del genere venisse costruito, scambi di chiavi, firme digitali e certificati oggi in uso perderebbero la loro sicurezza.
La crittografia simmetrica, come AES, e le funzioni di hash sono meno esposte. L’algoritmo di Grover offre un vantaggio quadratico nella ricerca esaustiva, che si compensa raddoppiando la lunghezza delle chiavi.

Quando

Nessuno sa quando esisterà un computer quantistico capace di rompere RSA a 2048 bit. I prototipi attuali hanno poche decine di qubit fisici, molto lontani dai milioni stimati per un attacco di questo tipo. Alcuni ricercatori ritengono possibile arrivarci in quindici o venti anni, altri sono più scettici. Il NIST, nel rapporto NISTIR 8105 pubblicato ad aprile 2016, osserva che il tempo necessario per sostituire l’infrastruttura crittografica è anch’esso misurabile in decenni. L’agenzia statunitense NSA aveva già annunciato nel 2015 l’intenzione di avviare la transizione per i sistemi di sicurezza nazionale.
C’è poi un rischio immediato. Un avversario può registrare oggi il traffico cifrato e conservarlo per decifrarlo quando disporrà di un computer quantistico. Per informazioni che devono restare riservate per molti anni, come dati sanitari, segreti industriali o comunicazioni diplomatiche, la minaccia riguarda già il presente.

Il bando

Il 20 dicembre 2016 il NIST ha pubblicato il bando definitivo per la presentazione di algoritmi, dopo una consultazione pubblica sui requisiti. Le proposte devono arrivare entro il 30 novembre 2017. Il processo riguarda due tipi di algoritmi:
  • cifratura a chiave pubblica e meccanismi di incapsulamento delle chiavi, per stabilire chiavi condivise;
  • firme digitali.
Il NIST precisa che il processo potrà concludersi con più algoritmi selezionati, a differenza delle competizioni che hanno portato ad AES e SHA-3. È probabile che vengano scelti più algoritmi, con caratteristiche diverse, per usi diversi. La valutazione considererà sicurezza, prestazioni, dimensione di chiavi e firme, semplicità di implementazione e flessibilità.

Le categorie di sicurezza

Per confrontare le proposte il bando definisce cinque categorie di sicurezza, legate alla difficoltà di attaccare primitive note. Le categorie uno, tre e cinque corrispondono alla difficoltà di trovare la chiave di AES a 128, 192 e 256 bit. Le categorie due e quattro alla difficoltà di trovare una collisione in SHA-256 e SHA-384. Gli autori devono indicare in quale categoria rientra ciascun insieme di parametri.

Le famiglie candidate

Le principali famiglie matematiche studiate dalla ricerca sono note:
  1. crittografia basata sui reticoli, con chiavi di dimensione moderata e buone prestazioni;
  2. crittografia basata sui codici correttori di errori, con una lunga storia di analisi ma chiavi pubbliche molto grandi;
  3. crittografia multivariata, usata soprattutto per le firme;
  4. firme basate su funzioni di hash, con ipotesi di sicurezza molto solide ma firme grandi;
  5. crittografia basata sulle isogenie di curve ellittiche, con chiavi piccole ma prestazioni più lente.
Nessuna famiglia è priva di compromessi. Gli algoritmi post-quantum sono più giovani di RSA e delle curve ellittiche e hanno ricevuto meno anni di analisi. Il processo pubblico serve proprio a sottoporli all’esame della comunità internazionale.

Scambio di chiavi e firme

Le due famiglie di algoritmi hanno urgenze diverse. Lo scambio di chiavi è esposto al rischio della registrazione oggi e decifratura domani, quindi la sua sostituzione è la più urgente per proteggere la riservatezza a lungo termine. Le firme digitali attestano autenticità e integrità. Un avversario capace in futuro di falsificarle resterebbe privo di effetti sulle verifiche già compiute in passato e potrebbe produrre nuovi falsi, per esempio aggiornamenti software o certificati. Per i dispositivi con una vita molto lunga, come apparati industriali, veicoli o satelliti, che verificano gli aggiornamenti con chiavi pubbliche installate in fabbrica, la questione va affrontata già in fase di progettazione.

Il calendario

Il NIST prevede più fasi di valutazione, ciascuna di diciotto mesi o più, con conferenze pubbliche e la possibilità per gli autori di modificare le proposte. Le prime bozze di standard sono attese a metà del prossimo decennio. Nel frattempo i ricercatori cercheranno di rompere i candidati, e alcuni cadranno.

Che cosa fare ora

Per un’organizzazione è presto per adottare algoritmi post-quantum in produzione. La preparazione richiede però anni, e conviene avviarla subito. Conviene censire dove si usa la crittografia a chiave pubblica, in protocolli, certificati, firme di documenti e di software, dispositivi con lunga vita utile. Conviene progettare i nuovi sistemi in modo che gli algoritmi possano essere sostituiti senza riscrivere le applicazioni, una proprietà chiamata crypto agility. Per i dati che devono restare riservati a lungo è utile valutare fin d’ora chiavi simmetriche più lunghe e la riduzione dei dati trasmessi su canali protetti solo da RSA o curve ellittiche.
 
Vedi anche: l’articolo del 2025 Sicurezza e vulnerabilità del quantum computing, l’articolo del 2026 Crittografia e transizione post-quantum e l’articolo del 2026 Q-Day e crypto-agility.
 
Vincenzo Calabrò | Ingegnere informatico specializzato in sicurezza informatica e investigazioni digitali. Funzionario informatico del Ministero dell'Interno; su incarico autorizzato si occupa di sicurezza informatica e di perizie informatiche forensi. Autore di articoli e saggi. Lecturer, Speaker, Trainer.
Profili: Google Scholar · ORCID · ResearchGate · Academia.edu · CyberSecurity360 · AgendaDigitale · ICT Security Magazine · LinkedIn