Introduzione
Dopo aver analizzato nel dettaglio gli schemi che basano la propria sicurezza su problemi matematici definiti sui reticoli (Kyber, Dilithium, Falcon) e sui codici a correzione di errori (Classic McEliece), possiamo focalizzare l’attenzione sulle funzioni di hash, ossia gli oggetti matematici alla base di SPHINCS+, schema di firma digitale selezionato al termine del terzo round della competizione del NIST e per il quale l’ente statunitense ha pubblicato nell’agosto 2023 la bozza di standard “FIPS-205: Stateless Hash-Based Digital Signature Standard”. Tale bozza rappresenta l’ultimo passo necessario prima della divulgazione, prevista per la metà del 2024, del documento che avrà valenza di standard federale e che rappresenterà il riferimento seguito dall’intera comunità crittografica internazionale nel processo di implementazione dell’algoritmo.
Road map
I prossimi tre articoli della presente serie a tema PQC saranno funzionali alla descrizione di SPHINCS+ e delle sue principali componenti. Come prima cosa verranno introdotte le proprietà fondamentali delle funzioni di hash che sono alla base della sicurezza di schemi come SPHINCS+ e analizzeremo le principali caratteristiche delle firme hash-based. Ci focalizzeremo in particolar modo su alcune peculiarità che le differenziano in modo significativo da altri schemi basati su differenti problemi matematici e che le rendono una scelta particolarmente conservativa dal punto di vista della sicurezza.
In seguito all’analisi degli aspetti più generali che accomunano la maggior parte degli algoritmi basati sulle funzioni di hash ci concentreremo specificatamente su SPHINCS+. Data la struttura modulare di questo schema procederemo in modo incrementale, descrivendo i diversi blocchi funzionali che vengono poi combinati in SPHINCS+ e le cui caratteristiche di sicurezza permettono di garantire i livelli di sicurezza richiesti dal NIST anche nei confronti di un attaccante in possesso di un computer quantistico. Verranno in particolare introdotte le One-Time Signatures (OTS) e le Few-Time Signatures (FTS), ponendo l’attenzione sulle limitazioni che ne precludono l’utilizzo nella maggior parte dei contesti applicativi reali; saranno però anche definiti altri oggetti matematici, quali i Merkle hash trees e gli Hypertrees che permettono di combinare ed estendere OTS e FTS così da renderle praticamente utilizzabili. Concluderemo infine con la descrizione della struttura generale di SPHINCS+, seguita da alcuni cenni alle principali parametrizzazioni e alle prestazioni dell’algoritmo.
Funzioni di hash e proprietà di sicurezza
Prima di evidenziare i principali vantaggi in termini di sicurezza che caratterizzano gli algoritmi hash-based è utile definire che cosa si intende con il termine “funzione di hash crittografica”. Una hash function crittografica è una funzione f\colon \{0,1\}^* \to \{0,1\}^n in grado di mappare stringhe di lunghezza arbitratria in stringhe di lunghezza fissata soddisfando le seguenti proprietà:
- Collision resistance: un attaccante [1] non deve essere in grado di trovare due input x, y tali che f(x) = f(y);
- Pre-image resistance: dato y\in \{0,1\}^n un attaccante non deve essere in grado di trovare x tale che f(x) = y;
- Second pre-image resistance: dati x_1 e y=f(x_1), un attaccante non deve essere in grado di trovare x_2\ne x_1 tale che f(x_2)=y.
Le funzioni di hash crittografiche e le costruzioni definite a partire da esse hanno conosciuto un’enorme diffusione e sono presenti all’interno della quasi totalità degli algoritmi e dei protocolli di comunicazione oggi utilizzati. Per tale motivo, le hash functions crittografiche sono diventate oggetto di numerosi studi che hanno permesso di accrescere la fiducia dei ricercatori nella sicurezza di tali primitive.
Gli algoritmi di firma digitale che si basano sulle funzioni di hash vengono giudicati dalla comunità crittografica internazionale la scelta più conservativa dal punto di vista della sicurezza, al pari di quanto succede tra i KEM con Classic McEliece. Tali schemi non rappresentano la miglior scelta in termini di prestazioni o di dimensione di chiavi pubbliche/firme: tuttavia, se paragonate con altri schemi, esse basano la propria sicurezza su un numero limitato di assunzioni ampiamente studiate in ambito crittoanalitico e quindi ritenute estremamente stabili di fronte agli attacchi conosciuti.
Se si considera infatti un generico algoritmo di firma digitale capace di operare su messaggi di lunghezza arbitraria (es. Dilithium o Falcon), si può notare come esso basi la propria sicurezza su due assunzioni:
- L’intrattabilità di un dato problema matematico (per es. il Shortest Vector Problem sui reticoli);
- La sicurezza della funzione di hash crittografica utilizzata all’interno dello schema.
Questo significa che se anche solo una delle due assunzioni venisse meno la sicurezza dello schema verrebbe irremediabilmente compromessa.
Le hash-based signatures come SPHINCS+ basano invece la propria sicurezza solamente sulla seconda condizione: ciò comporta che uno schema di firma digitale hash-based risulterebbe attaccabile solo qualora fosse possibile compromettere la sicurezza della funzione di hash utilizzata al suo interno, ma in tal caso verrebbe anche meno la sicurezza di tutti gli altri schemi che utilizzano la stessa funzione di hash.
In aggiunta a ciò, in alcuni schemi crittografici tra cui SPHINCS+, la sicurezza potrebbe essere garantita anche qualora la hash function utilizzata non fosse collision resistant. Rimane però chiaramente consigliabile l’utilizzo di primitive ritenute sicure e per le quali non sono mai stati pubblicati attacchi: gli schemi recentemente proposti fanno utilizzo di funzioni quali SHA2 e SHAKE (appartenente alla famiglia SHA3), mentre viene deprecato l’utilizzo di schemi ormai insicuri o obsoleti quali MD5 e SHA1.
Firme digitali stateful vs stateless
I primi due schemi di firma digitale quantum-resistant basati sulle funzioni di hash – XMSS e LMS – sono stati proposti in prima battuta dall’Internet Engineering Task Force (IETF) e standardizzati poi dal NIST. Si osservi che la loro approvazione è avvenuta antecedentemente e indipendentemente rispetto al processo del NIST per la crittografia post-quantum. La ragione principale per cui questi schemi, pur garantendo sicurezza a lungo termine sufficiente ai contesti applicativi reali, non sono stati ritenuti del tutto soddisfacenti risiede essenzialmente nella loro natura stateful.
Il termine stateful fa riferimento alla necessità di tenere traccia di tutte le firme prodotte nel tempo con una stessa chiave privata per preservare la sicurezza promessa dallo schema. Infatti, l’eventuale riutilizzo di determinati parametri per la firma di differenti messaggi risulterebbe catastrofico, consentendo ad un potenziale attaccante di forgiare firme fasulle. Tale requisito risulta limitante se non impraticabile in molteplici scenari, specialmente quelli in cui la memoria a disposizione è contenuta e il numero di firme da produrre è elevato. Inoltre, particolare attenzione deve essere fatta in fase implementativa per scongiurare errori di sincronizzazione; infatti, un disallineamento fra memoria non volatile e RAM potrebbe causare proprio il riutilizzo dei sopra citati parametri. Un’altra questione da considerare, per le medesime ragioni, è il problema della clonazione che si verifica quando una chiave privata è copiata e utilizzata parallelamente in più contesti senza coordinazione. Questo può accadere, ad esempio, nell’ambito delle macchine virtuali oppure del ripristino di informazioni ad uno stato precedente tramite backup.
Pertanto, il processo del NIST sulla PQC si è espressamente rivolto a soluzioni di tipo stateless, per cui la tracciatura di tutte le firme eseguite con un’unica chiave sia evitabile. Inoltre, gli schemi di firma digitale pre-quantum come ECDSA ed RSA sono stateless e, in ottica di sostituirli negli attuali sistemi crittografici nel modo più trasparente possibile, è cruciale che questa proprietà venga rispettata dalle alternative post-quantum.
WOTS+
Come riportato nella sezione introduttiva, elemento primario nella costruzione dello schema SPHINCS+ è dato dalla firma digitale Winternitz One-Time Signature Plus (WOTS+). Considerandola in modo a sé stante, si tratta di una soluzione che consente di firmare un unico messaggio per ciascuna coppia chiave privata-chiave pubblica, come suggerito dal nome.
Di seguito ne è riportata una descrizione ad alto livello.
Sia n la dimensione in byte del messaggio \texttt{msg} da firmare e sia w un numero intero positivo detto parametro di Winternitz. Il messaggio è suddiviso in blocchi di lg_w:=\log_2{w} bit, ciascuno interpretato come un numero intero minore di w:
\texttt{msg}=\underbrace{x_1x_2\dots x_{lg_w}}_{m_1}\underbrace{x_{lg_w+1}\dots x_{2lg_w}}_{m_2}\,\dots\,\underbrace{x_{8n-lg_w+1}\dots x_{8n}}_{m_{len_1}}ove x_i\in\{0,1\}, m_j\in\{0,1,\dots,w-1\} e len_1=\frac{8n}{lg_w}.
La chiave privata s_k è costituita da len (definito successivamente) stringhe segrete di n byte, mentre la chiave pubblica pk è ottenuta a partire da sk e da una funzione di hash \text{H}[2] tramite le catene sotto rappresentate.
\begin{align*} sk_1 & \rightarrow \text{H}(sk_1) \rightarrow \text{H}(\text{H}(sk_1)) = \text{H}^2(sk_1) \rightarrow \cdots \rightarrow \text{H}^{w-1}(sk_1)=:pk_1 \\ sk_2 & \rightarrow \text{H}(sk_2) \rightarrow \text{H}(\text{H}(sk_2)) = \text{H}^2(sk_2) \rightarrow \cdots \rightarrow \text{H}^{w-1}(sk_2)=:pk_2 \\ & \vdots \\ sk_{len} & \rightarrow \text{H}(sk_{len}) \rightarrow \text{H}(\text{H}(sk_{len})) = \text{H}^2(sk_{len}) \rightarrow \cdots \rightarrow \text{H}^{w-1}(sk_{len})=:pk_{len} \end{align*}Si osservi che, da un punto di vista computazionale, è facile “scorrere” queste catene da sinistra verso destra. Dato un elemento di una catena, per ottenere i termini che stanno a destra, basta applicare ripetutamente la funzione di hash coinvolta. D’altra parte, muoversi in direzione opposta risulta impraticabile per la proprietà di “resistenza al calcolo di preimmagini” della funzione di hash. Su questa asimmetria si basano l’usabilità e la sicurezza di WOTS+.
La firma di \texttt{msg} è calcolata come
\sigma_1\sigma_2\dots\sigma_{len_1}=\text{H}^{m_1}(sk_1)\text{H}^{m_2}(sk_2)\dots\text{H}^{m_{len_1}}(sk_{len_1}),
con \sigma_i = \text{H}^{m_i}(sk_i).
In fase di verifica il destinatario controlla le seguenti uguaglianze.
\begin{align*} \text{H}^{w - m_1 - 1}(\sigma_1) & \stackrel{?}{=} pk_1 \\ \text{H}^{w - m_2 - 1}(\sigma_2) & \stackrel{?}{=} pk_2 \\ & \vdots \\ \text{H}^{w - m_{len_1} - 1}(\sigma_{len_1}) & \stackrel{?}{=} pk_{len_1} \end{align*}Lo schema così descritto risulta però vulnerabile. A partire dalla firma del messaggio \texttt{msg} è possibile ottenerne una valida per un qualunque messaggio \texttt{msg}' con m_j\leq m_j' per ogni j. Infatti, è sufficiente calcolare:
\begin{align*} \sigma_1' & = \text{H}^{m_1' - m_1}(\sigma_1), \\ \sigma_2' & = \text{H}^{m_2' - m_2}(\sigma_2), \\ & \vdots \\ \sigma_{len_1}' & = \text{H}^{m_{len_1}' - m_{len_1}}(\sigma_{len_1}). \end{align*}Per ovviare a questa lacuna, viene concatenata a \sigma_1\dots\sigma_{len_1} la firma ottenuta con il medesimo principio della checksum del messaggio, ovvero C=\sum_{j=1}^{len_{1}}(w-m_j-1). Si può dedurre che la lunghezza in bit di C è data da
len_2 := \left\lfloor\frac{\log_2{(len_1(w-1))}}{lg_w}\right\rfloor+1e, di conseguenza, si ha
len = len_1 + len_2.È evidente che, con l’introduzione della checksum, un potenziale attaccante non sia più in grado di seguire la strategia sopra descritta ai fini di forgiare una firma fasulla. Infatti, se m_j\leq m_j' per ogni j segue che C\geq C' e quindi sarebbe necessario scorrere all’indietro almeno una delle catene di hash relative a C, ma questo corrisponderebbe ad invertire una funzione di hash, operazione che si assume impraticabile.
Come considerazione conclusiva, si evidenzia la natura one time dello schema, proprietà che rende WOTS+ poco appetibile per la maggior parte dei contesti applicativi, a meno che non sia una componente di costruzioni crittografiche più articolate come accade in SPHINCS+. Ad esempio, si consideri l’eventualità di due messaggi distinti \texttt{msg} = 01001010 e \texttt{msg}'=00101110 firmati con un’unica chiave privata sk e con parametro di Winternitz w=16. La lista completa dei parametri coinvolti risulta
\begin{align*} n & = 1, \\ w & = 16, \\ lg_w & = 4, \\ len_1 & = 2, \\ len_2 & = 2, \\ len & = 4. \end{align*}Inoltre, si ha
\begin{align*} \texttt{msg} & = 0100\,1010 = 2\,5 = m_1\,m_2, \\ \texttt{msg}' & = 0010\,1110 = 4\,7 = m_1'\,m_2', \end{align*}mentre le checksum relative ai due messaggi sono rispettivamente
\begin{align*} C & = 1110\,1000 = 7\,1 = C_1\,C_2, \\ C' & = 1000\,1000 = 1\,1 = C_1'\,C_2'. \end{align*}Data sk=sk_1sk_2sk_3sk_4 la chiave privata, le firme dei due messaggi sono rispettivamente
\begin{align*} \sigma & = \sigma_1\sigma_2\sigma_3\sigma_4 = \text{H}^2(sk_1)\text{H}^5(sk_2)\text{H}^7(sk_3)\text{H}(sk_4), \\ \sigma' & = \sigma_1'\sigma_2'\sigma_3'\sigma_4' =\text{H}^4(sk_1)\text{H}^7(sk_2)\text{H}(sk_3)\text{H}(sk_4). \end{align*}Si consideri ora il messaggio \dot{\texttt{msg}}=11000110, si ottiene
\begin{align*} \dot{\texttt{msg}} & = 1100\,0110 = 3\,6 = \dot{m_1}\,\dot{m_2}, \\ \dot{C} & = 1010\,1000 = 5\,1 = \dot{C_1}\,\dot{C_2}. \end{align*}A questo punto per forgiare la firma \dot{\sigma} corrispondente, bisognerebbe calcolare i valori
\text{H}^3(sk_1), \text{H}^6(sk_2), \text{H}^5(sk_3), \text{H}(sk_4).Questo è possibile farlo senza la conoscenza della chiave privata sk a partire dalle componenti \sigma_1, \sigma_2, \sigma_3', \sigma_4', applicando opportunamente la funzione di hash \text{H} e, pertanto, l’insicurezza dell’utilizzo di un’unica chiave per la firma WOTS+ di due messaggi distinti è confermata.
Dopo aver descritto le principali caratteristiche di sicurezza degli schemi di firma hash-based e aver presentato un primo esempio di algoritmo appartenente a tale famiglia, nel corso dei prossimi articoli verranno introdotti ulteriori costruzioni che permettono di aggirare alcuni dei problemi che affliggono WOTS+ e che risultano fondamentali per la definizione di SPHINCS+.
[1] L’attaccante considerato nella definizione di queste proprietà è un avversario, anche quantistico, computazionalmente limitato.
[2] instanziata come SHA-2 oppure SHAKE
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.