Introduzione

Lo schema Forest Of Random Subset (FORS) rappresenta l’ultimo elemento necessario alla descrizione della struttura completa della firma digitale SPHINCS+, selezionata al termine del terzo round del processo di standardizzazione del NIST. L’inclusione di FORS permette di rendere SPHINCS+ uno schema di firma stateless, superando le principali criticità che affliggono altre hash-based signatures come XMSS e LMS. Dopo aver descritto il funzionamento di FORS, verrà presentata la struttura generale di SPHINCS+, sottolineando come la combinazione delle strutture crittografiche introdotte nei precedenti due articoli della presente rubrica dia origine allo schema in corso di standardizzazione da parte del NIST.

FORS

Tassello conclusivo nella costruzione di SPHINCS+ è quindi costituito dalla firma Forest Of Random Subsets (FORS). Si tratta di una Few Time Signature (FTS), ovvero di uno schema che permette di firmare un numero limitato di messaggi diversi con la stessa chiave privata. All’aumentare delle firme prodotte, la sicurezza dello schema subisce una graduale diminuzione fino ad esaurirsi, ma senza incorrere nella catastrofica ed immediata perdita di sicurezza che si ha quando vengono firmati due o più messaggi utilizzando una one-time signature come WOTS+.

Di seguito è riportata una descrizione ad alto livello di FORS.

Lo schema è determinato dai parametri k, t=2^a ed n, nell’ottica di firmare stringhe di ka bit. La chiave privata è costituita da k insiemi di t stringhe di lunghezza n bytes, generate a partire da un singolo seme (seed) segreto. Per ottenere la chiave pubblica è necessario calcolare i digest, tramite un’opportuna funzione di hash, di ciascuna delle kt stringhe segrete e distribuirli come foglie di k Merkle Tree di altezza a. Si ricorda che un generico nodo appartenente ai k alberi è ottenuto come hash della concatenazione dei suoi figli. Infine, una volta calcolate le k radici degli alberi risultanti, la chiave pubblica è data dall’hash della concatenazione di queste.

A scopo esplicativo, la struttura sotto riportata rappresenta il caso k=3 e t=2^2, in cui sono necessari 3 Merkle Tree di altezza 2. La chiave privata è data da sk_{0,0},\dots,sk_{2,3} mentre la chiave pubblica da f\!pk.

Dato un messaggio di ka bit, questo viene scomposto in k stringhe l_0,\dots, l_{k-1} di a bit, ciascuna interpretata come un intero nell’intervallo [0,t). La firma del messaggio è ottenuta concatenando le k stringhe sk_{0,l_0},sk_{1,l_1},\dots, sk_{k,l_{k-1}}, una per ogni Merkle Tree, e gli authentication path [1] per risalire alle radici r_i e di conseguenza alla chiave pubblica f\!pk. Di seguito sono evidenziati gli authentication path relativi alla firma del messaggio 11\,01\,10 nel caso k=3 e t=2^2.

Possiamo ora analizzare più nel dettaglio le caratteristiche che rendono FORS una Few Time Signature e che quindi permettono di firmare più messaggi con la stessa chiave privata mantenendo un elevato livello di sicurezza.

Nella maggior parte delle One Time Signatures ogni volta che viene apposta una firma viene resa pubblica una parte consistente della chiave privata del firmatario: un esempio chiaro in tal senso è la OTS proposta da Lamport [2], nella quale viene esposta metà chiave privata, rendendo impossibile il suo riutilizzo sicuro per la firma di un secondo messaggio. Si noti che anche in FORS, ogniqualvolta viene apposta una firma, vengono rivelate alcune parti della chiave privata, ma il leak di informazione è molto più contenuto.

Facendo riferimento allo schema riportato sopra, possiamo notare come una firma comporti la pubblicazione del valore di una sola stringa segreta per ciascuno dei tre Merkle Tree (sk_{0,3}, sk_{1,1}, sk_{2,2} nel caso qui considerato). Se si considera che nelle istanze di FORS di interesse per l’utilizzo all’interno di SPHINCS+ t può assumere valori da 2^6 fino a 2^{14}, appare chiaro che una firma, rivelando solamente una stringa in ciascuno dei k Merkle Tree, non sia sufficiente ad inficiare immediatamente la sicurezza di firme successive prodotte con la medesima chiave privata. Infatti, un attaccante può forgiare una firma di un messaggio, senza la conoscenza della chiave privata, solamente se il suo digest è composto da blocchi di a bit tali da identificare stringhe che sono già state rese pubbliche, ma se è a conoscenza di un numero limitato di firme questo scenario diventa estremamente improbabile. È chiaro, comunque, che man mano che il numero di firme apposte con la stessa chiave aumenta, cresce anche la probabilità che un attaccante riesca a trovare un messaggio per cui gli è possibile forgiare la firma.

La struttura di FORS garantisce anche una maggiore protezione nel caso di “weak messages”, ossia di messaggi in cui molti blocchi del digest risultano uguali e che possono comportare una riduzione della sicurezza in altre note FTS come ad esempio Hash to Obtain Random Subset (HORS), in cui invece di k Merkle Trees di t foglie se ne utilizza uno solo. Inoltre, in FORS vengono adottate altre accortezze quali ad esempio la randomizzazione dell’hash del messaggio. Questo impedisce ad un attaccante di costruire messaggi che permettono di massimizzare il leak di informazione derivante da ciascuna firma.

SPHINCS+

L’introduzione di FORS permette di superare l’esigenza di tracciabilità delle firme già eseguite, presente ad esempio in XMSS, risultando fondamentale nel design di schemi stateless richiesti nel processo di standardizzazione post-quantum del NIST.

Combinando tutti gli ingredienti introdotti nel corso degli ultimi tre articoli, lo schema di firma SPHINCS+ risulta così composto.

Dato un messaggio da firmare, questo viene compresso a ka bit tramite una funzione di hash in accordo con i parametri di FORS. La scelta di firmare il digest, invece del messaggio stesso, è necessaria per garantire la sicurezza di FORS. Inoltre, la stessa è vantaggiosa sotto l’aspetto delle performance e della dimensione della firma, poiché assicura che l’oggetto che viene firmato abbia lunghezza costante e contenuta. Il digest ottenuto è firmato tramite uno schema FORS, mentre la chiave pubblica f\!pk corrispondente è successivamente autenticata da una firma XMSS^MT, discussa nel precedente articolo. Si ricorda che la realizzazione di questa ultima parte è a sua volta modulare. Nello specifico, nello schema XMSS^MT l’elemento da firmare è dato in input ad uno schema WOTS+, la cui chiave pubblica costituisce una foglia di un Merkle Tree. Il Merkle Tree è poi inserito in una struttura HyperTree, in cui più Merkle Tree sono distribuiti secondo un certo numero di livelli e la radice di ciascuno è firmata da una foglia di un albero di livello superiore. In figura, tratta da [3], è riportato lo schema completo ad alto livello.

La chiave privata di SPHINCS+ è costituita dal seme che genera le chiavi FORS con cui firmare il digest del messaggio e le chiavi WOTS+ che popolano le foglie dei Merkle Tree coinvolti. La chiave pubblica è invece identificata dalla radice dell’HyperTree. Le dimensioni di chiave pubblica e privata sono estremamente contenute e rappresentano sicuramente un punto di forza di questo algoritmo.

Infine, la firma SPHINCS+ di un messaggio è data dalla concatenazione della firma FORS, delle firme WOTS+ relative a chiave pubblica FORS e radici dei Merkle Tree coinvolti, e degli autentication path dei medesimi alberi.

Performance

Osservazione naturale è pertanto rivolta all’elevata dimensione della firma prodotta, che la rende poco appetibile in numerosi contesti nei quali sono presenti stringenti requisiti di memoria o banda. Anche in contesti più generali risulta comunque più conveniente l’utilizzo di schemi alternativi, quali CRYSTALS-Dilithium e Falcon, che a parità di livello di sicurezza garantiscono firme con dimensioni di un ordine di grandezza inferiori, come si può facilmente dedurre dall’istogramma riportato di seguito.

Nonostante le firme di dimensioni elevate ne limitino l’utilizzo in molti scenari, essendo basata esclusivamente sulle funzioni di hash, SPHINCS+ costituisce una scelta estremamente conservativa e adatta a contesti ad elevata sicurezza in cui le performance potrebbero non essere la priorità principale. Inoltre, all’interno del panorama delle firme hash-based, SPHINCS+ rappresenta un’opzione interessante grazie alla sua natura stateless. In schemi hash-based stateful come XMSS e LMS, infatti, i messaggi vengono firmati ricorrendo ad una OTS che implica la necessità di mantenere uno stato al fine di evitare di riutilizzare due volte la stessa chiave privata. In SPHINCS+, i messaggi vengono firmati utilizzando la FTS FORS e, se il numero di firme apposte utilizzando la stessa chiave privata SPHINCS+ non supera un determinato limite (solitamente 2^{64}), la probabilità che la stessa chiave privata FORS sia utilizzata un numero di volte tale da renderla insicura rimane trascurabile. In questo modo si evitano le problematiche già evidenziate in un precedente articolo di questa rubrica, relative al mantenimento di uno storico delle firme eseguite e conseguentemente al riutilizzo della medesima chiave privata.

[1] Insieme dei nodi necessari e sufficienti per calcolare, a partire dalle k stringhe segrete, le radici degli alberi.
[2] Leslie Lamport, Constructing Digital Signatures from a One Way Function, Rapp. tecn. CSL-98, 1979.
[3] Andreas Hülsing e Mikhail Kudinov, Recovering the tight security proof of SP HIN CS+, Cryptology ePrint Archive, Paper 2022/346, 2022.

Questo articolo appartiene ad una serie di contributi, a cura del Gruppo di Ricerca in Crittografia di Telsy, dedicata al calcolo quantistico e alle sue implicazioni sulla Crittografia. Per la consultazione di altri articoli si rimanda all’indice della rubrica.

Per altri articoli relativi ai temi Quantum e Crittografia si rimanda alle relative categorie nel blog.

Gli autori

Francesco Stocco, laureato magistrale in Matematica presso l’Università degli Studi di Padova e l’Université de Bordeaux frequentando il percorso di studi “Algebra Geometry And Number Theory” (ALGANT), entrato a far parte del Gruppo di Ricerca in Crittografia di Telsy alla fine del 2020.

Marco Rinaudo, laureato triennale in Matematica presso l’Università degli Studi di Torino e laureato magistrale con specializzazione in Crittografia presso l’Università di Trento. In seguito ad uno stage curricolare svolto nel 2022 in Telsy, da gennaio 2023 è parte del Gruppo di Ricerca in Crittografia.