Nuove proposte di firme digitali post-quantum: la seconda competizione del NIST

Introduzione

In risposta alla minaccia del computer quantistico, nel 2017 il National Institute of Standards and Technology (NIST) ha avviato un processo di standardizzazione per la selezione di algoritmi di crittografia a chiave pubblica quantum-resistant. Il processo si è incentrato sulla selezione di algoritmi di negoziazione chiave e algoritmi di firma digitale.

Al termine di tre round di analisi, con la partecipazione di esperti accademici e rappresentanti industriali della comunità crittografica, il NIST ha annunciato una prima selezione di algoritmi che procederanno alla fase di  standardizzazione. Gli algoritmi scelti sono stati CRYSTALS-Kyber per la negoziazione chiave e CRYSTALS-Dilithium, Falcon e SPHINCS+ per le firme digitali post-quantum. Tutti gli schemi selezionati, ad eccezione di SPHINCS+, basano la propria sicurezza su problemi matematici legati ai reticoli strutturati¹.

Con lo scopo di differenziare le assunzioni di sicurezza alla base degli schemi standardizzati, nel settembre del 2022 il NIST ha annunciato che il processo sarebbe proseguito per un quarto round. Gli schemi ritenuti ammissibili per una valutazione aggiuntiva fanno parte unicamente della categoria della negoziazione chiave. Il NIST ha quindi ritenuto opportuno avviare un nuovo processo di standardizzazione focalizzato sulla selezione di firme digitali post-quantum.

Ad oggi, gli schemi di firma maggiormente usati sono RSA, ECDSA e, più di recente con la pubblicazione dello standard FIPS 186-5, EdDSA. Nonostante il loro largo utilizzo, questi schemi risultano vulnerabili ad attacchi quantistici e dovranno quindi essere sostituiti da algoritmi post-quantum come i già citati Dilithium, Falcon e SPHINCS+. Recentemente, il NIST ha pubblicato una prima bozza delle specifiche ufficiali di Dilithium e SPHINCS+, rispettivamente con i documenti FIPS 204 e FIPS 205, avviando di fatto l’ultima fase del processo che porterà alla prima definizione degli standard aggiornati.

Per la nuova competizione, il NIST ha dichiarato di essere interessato principalmente a proposte basate su assunzioni di sicurezza diverse da quelle legate ai reticoli strutturati. Ciò nonostante, l’istituto ha manifestato la propria apertura anche a sottomissioni basate su reticoli strutturati, a patto che queste presentino differenze sostanziali rispetto agli schemi già in fase di standardizzazione.

Le nuove sottomissioni

La competizione indetta nel 2017 ha raccolto in totale 64 sottomissioni, di cui solo 19 proponevano algoritmi di firme digitali. Nonostante il numero ridotto, le proposte iniziali risultavano eterogenee, con proposte affini alle principali categorie di problemi post-quantum, quali reticoli, codici lineari, sistemi multivariati, funzioni hash e primitive simmetriche. La diversificazione si è progressivamente ridotta nei round successivi, portando ad una rappresentazione eccessiva di algoritmi basati su reticoli strutturati.

A giugno 2023, con il termine della nuova fase di sottomissione, il NIST ha ricevuto 50 proposte e ne ha ritenute 40 valide e compatibili con i requisiti della competizione. Oltre alle macrocategorie già individuate nella competizione del 2017, tra le nuove proposte si trovano algoritmi basati su isogenie di curve ellittiche supersingolari e altri inquadrabili nel recente paradigma “MPC-in-the-head”. Di seguito sono riportate le principali famiglie di problemi e il numero di candidati per ciascuna di esse, con un confronto tra la precedente e la nuova competizione.

Le nuove proposte sono liberamente consultabili, con le relative specifiche ed implementazioni, sulla pagina ufficiale del progetto NIST.

Come per la competizione del 2017, il NIST ha definito cinque livelli di sicurezza. Ogni livello definisce la sicurezza tramite il confronto con una primitiva simmetrica standard: i livelli I, III e V fanno riferimento rispettivamente ad AES-128, AES-192 e AES-256; i livelli II e IV fanno riferimento rispettivamente a SHA-256 e SHA-384. Ad esempio, affinché un algoritmo sia inquadrabile nel livello I, ogni attacco noto in grado di romperne la sicurezza dovrà richiedere un costo computazionale (classico o quantistico) pari o superiore a quello richiesto per un attacco esaustivo ad AES con chiavi da 128 bit. Gli schemi sottomessi dovranno quindi proporre diverse parametrizzazioni in grado di coprire i diversi livelli di sicurezza. Nel complesso, tra le 40 sottomissioni
ammesse, sono state proposte 297 parametrizzazioni, con una preponderanza di parametri relativi ai livelli I, III e V.

Nonostante le specifiche degli schemi siano state pubblicate da poche settimane, la comunità crittografica ha rapidamente avviato un’approfondita analisi delle sottomissioni. Già nei primi giorni dopo la pubblicazione, sono state individuate importanti vulnerabilità che hanno comportato l’eliminazione prematura di alcune proposte. Al momento della scrittura di questo articolo, dei 40 schemi inizialmente sottomessi ne risultano 9 completamente rotti (3WISE, EagleSign, EHTv3, eMLE Sig 2.0, FuLeeca, HPPC, KAZ-Sign, Xifrat1-Sign, DME-Sign) e 3 con una sicurezza
ridotta rispetto alle specifiche originali (Biscuit, HuFu, SDitH). Oltre ai requisiti di sicurezza basilari, vi sono alcune proprietà aggiuntive rilevanti o comunque desiderabili nella
valutazione di un algoritmo.

In particolare, il NIST ha espresso interesse per le seguenti proprietà:

• Resistenza ad attacchi side-channel. Sebbene le vulnerabilità side-channel coinvolgano principalmente le implementazioni di un algoritmo, vi sono schemi naturalmente meno suscettibili ad attacchi di questo tipo. Tale caratteristica semplifica notevolmente le implementazioni e spesso permette di evitare contromisure costose in fase di ottimizzazione.
• Resistenza ad attacchi multi-chiave. In un attacco multi-chiave, un avversario tenta di compromettere contemporaneamente più chiavi. Talvolta, scenari di questo tipo risultano favorevoli per l’avversario rispetto ad un attacco singolo.
• Misuse-resistance. Con questo termine si fa riferimento alla capacità di uno schema crittografico di rivelare poca informazione nel caso di un uso scorretto in fase di implementazione o di utilizzo.
• Nozioni avanzate. Riguardano ulteriori proprietà di sicurezza quali exclusive ownership, message-bound signatures e re-signability.

Trade-offs e prestazioni

Nella valutazione di un algoritmo di firma digitale, possiamo individuare numerose metriche relative a costi di comunicazione, prestazioni, efficienza e caratteristiche implementative. Il NIST, similmente alla competizione del 2017, non ha stabilito una chiara priorità, osservando come importanti scenari reali possano richiedere diversi compromessi.

Indipendentemente dallo scenario applicativo, è auspicabile che un buon candidato spicchi in almeno una delle metriche descritte di seguito:

• Dimensione delle chiavi pubbliche e delle firme. La lunghezza di una firma rappresenta il principale costo di comunicazione, in quanto la trasmissione della firma nella sua interezza è sempre necessaria. Per quanto riguarda le chiavi pubbliche, invece, in alcuni scenari è possibile procedere offline con la loro memorizzazione, riducendo quindi l’impatto di una dimensione maggiore critico soprattutto in caso di trasmissione.
• Costi computazionali. L’efficienza computazionale di uno schema di firma viene valutata principalmente dall’analisi delle operazioni private (l’algoritmo di firma) e pubbliche (l’algoritmo di verifica). Poiché gli schemi di firma utilizzano tipicamente chiavi statiche², il costo di generazione di una nuova coppia di chiavi è spesso secondario. La valutazione precisa di questi costi dipende dalle caratteristiche della piattaforma su cui lo schema sarà implementato. Per questa ragione il NIST richiede implementazioni software e hardware, con analisi su piattaforme eterogenee (es. desktop, embedded, FPGA).

Rispetto alla crittografia classica, dove esistono schemi con caratteristiche ottimali rispetto a tutte le metriche precedenti, la crittografia post-quantum necessita di maggiori trade-off e presenta un generale incremento delle dimensioni di chiavi e firme. Nelle intenzioni del NIST, una selezione più ampia di standard crittografici rispetto al passato favorirà l’adozione di schemi post-quantum nella maggior parte degli scenari applicativi.

Nella figura sottostante è riportato un grafico delle dimensioni di firme e chiavi pubbliche, mettendo a confronto le nuove proposte sottomesse, gli schemi di firma vincitori nella competizione post-quantum e gli standard pre-quantum. Per semplificare il confronto, il grafico riporta solamente le parametrizzazioni di livello I e II. Il bordo rosso sulle nuove proposte indica che sono state rilevate delle vulnerabilità di sicurezza³.

Case study: TLS e WebPKI

Una delle principali applicazioni delle firme digitali riguarda la protezione delle comunicazioni web e in particolare l’impiego nel protocollo TLS.

Il protocollo TLS, acronimo di “Transport Layer Security,” è un fondamentale protocollo di sicurezza utilizzato su Internet per garantire la privacy e l’integrità delle comunicazioni tra client e server. Questo protocollo opera a livello di trasporto, fornendo uno strato aggiuntivo di sicurezza al protocollo sottostante, solitamente TCP. TLS utilizza una combinazione avanzata di primitive crittografiche per impedire l’intercettazione non autorizzata dei dati durante il trasferimento e per autenticare le parti coinvolte.

Un elemento fondamentale nell’implementazione del TLS è la Public Key Infrastructure (PKI) del web. La WebPKI è un insieme di standard, protocolli e servizi che gestisce la creazione, la distribuzione e la gestione delle chiavi crittografiche pubbliche e dei certificati digitali. Nel contesto del TLS, la WebPKI svolge un ruolo cruciale nella verifica dell’identità dei server e dei siti web. Ogni server web che desidera utilizzare TLS deve ottenere un certificato digitale da un’autorità di certificazione (CA) affidabile. Questo certificato contiene la chiave pubblica del server unitamente ad altre informazioni e viene utilizzato per dimostrare l’autenticità del sito web ai client, tramite l’utilizzo di firme digitali.

La migrazione degli algoritmi di firma classici ai nuovi standard post-quantum rappresenta una delle maggiori sfide del processo di transizione avviato dal NIST. L’aumento non trascurabile dei costi dei nuovi schemi, in termini di comunicazione o efficienza, rende complessa una sostituzione diretta degli algoritmi impiegati nella WebPKI. In particolare, sono desiderabili schemi con firme di lunghezza ridotta (per le comunicazioni durante il protocollo TLS), con lunghezza congiunta di chiave pubblica e firma ridotta (per la trasmissione dei certificati) ed efficienti
in fase di verifica (per il controllo dei certificati da parte dei client). Di seguito è riportato un confronto tra gli schemi di firma in fase di standardizzazione ed ECDSA-P256, largamente utilizzato nell’ambito della WebPKI.

Dalla tabella precedente appare evidente come nessuno tra i nuovi schemi permetta una sostituzione diretta nel contesto web. L’unica apparente eccezione, costituita da Falcon, presenta a sua volta delle criticità implementative che richiedono l’uso di aritmetica in virgola mobile, limitandone le possibilità di utilizzo.

Tra le nuove proposte sottomesse, possiamo tentare un’analisi preliminare andando ad individuare gli schemi con caratteristiche compatibili con i requisiti del TLS e della WebPKI. Concretamente, consideriamo come valori soglia quelli di Dilithium2 e ECDSA. Di seguito sono riportati gli schemi che raggiungono o migliorano tali valori nelle metriche precedentemente individuate.

Anche considerando i nuovi schemi, continua a non essere semplice sostituire direttamente le firme classiche. D’altra parte, alcune delle nuove proposte presentano caratteristiche interessanti, in particolare per quanto riguarda le dimensione delle firme. Tale caratteristica, se supportata nel tempo da una conferma della sicurezza e delle prestazioni, potrebbe favorire questi candidati nell’adozione in ambito web.

Conclusioni

Con l’annuncio degli algoritmi vincitori alla competizione del NIST, il processo di transizione al post-quantum ha fatto un importante passo avanti, segnando la strada per la futura adozione di schemi quantum-resistant. Queste soluzioni sono da ritenersi valide e applicabili nel breve termine alla maggior parte dei casi d’uso. Il nuovo processo dedicato alle firme digitali non va quindi considerato come alternativo al precedente, né sarebbe saggio per l’industria attenderne la conclusione prima di avviare la transizione. L’obiettivo del NIST è infatti quello di ampliare l’offerta di algoritmi post-quantum, così da raggiungere più facilmente scenari particolari e allo stesso tempo garantire un’opportuna diversificazione delle assunzioni di sicurezza.

Come nel caso della competizione precedente, è plausibile che il processo richiederà più round e diversi anni prima di giungere ad una conclusione.