Classic McEliece: incapsulamento chiave basato sui codici

26 Feb

Alla fine del terzo round del processo di standardizzazione del NIST è stato selezionato il metodo di incapsulamento chiave CRYSTALS-Kyber volto a sostituire l’attuale schema ECDH.
Il NIST ha poi definito un quarto round di selezione, con lo scopo di differenziare le assunzioni di sicurezza alla base degli schemi standardizzati.

Questo round, ancora in corso, mira ad analizzare tre schemi di incapsulamento chiave basati sui codici, Classic McEliece, BIKE e HQC, tra i quali Classic McEliece rappresenta la scelta più conservativa in termini di sicurezza.

Il crittosistema alle fondamenta di Classic McEliece è il cifrario a chiave pubblica proposto da Niederreiter nel 1986, versione duale di quello proposto da McEliece nel 1978.

Neiderreiter PKE

Per descrivere lo schema, ricordiamo la seguente notazione.

Un $[n,k,d]$ -code è un codice lineare di lunghezza $n$ , dimensione $k$ e distanza $d$ . Questo vuol dire che la capacità correttiva del codice è $t = \frac{d-1}{2}$
Con $\mathrm{GL}(n,q)$ denotiamo l’insieme delle matrici invertibili $n \times n$ a coefficienti in $\mathbb{F}_q$ , mentre con $\mathcal{S}_n$ l’insieme delle matrici di permutazione $n\times n$ , ovvero quelle matrici invertibili che hanno esattamente un uno su ogni riga e su ogni colonna, e zero altrove.
L’insieme $\mathbb{F}_q^{n,t}$ contiene vettori a coefficienti in $\mathbb{F}_q$ di lunghezza $n$ e peso $t$ .

Nell’algoritmo di generazione delle chiavi viene scelto un $[n,k,2t+1]$ -codice con matrice di parità (parity-check matrix) $H$ di cui si conosce un algoritmo di decodifica $\mathsf{Decoding}_H$ efficiente. Successivamente si camuffa la matrice $H$ moltiplicandola per le matrici random $S$ e $P$ e si pubblica il risultato come chiave pubblica, assieme alla capacità correttiva del codice.

Il testo cifrato relativo ad un messaggio $m$ lungo $n$ con peso $t$ è dato dal suo prodotto con la matrice pubblica $H^{\text{pub}}$ : $c= H^{\text{pub}}m ^T$ .

Per decifrare $c$ , viene eseguito l’algoritmo di decodifica del codice sul vettore $S^{-1}c$ e, se la decodifica va a buon fine, viene applicata l’inversa di $P$ per recuperare il messaggio originale.

La sicurezza di questo crittosistema risiede nel fatto di non poter decodificare in modo efficiente il crittogramma $c$ se non si è conoscenza della matrice segreta $H$ , la quale è camuffata in $H^{\text{pub}}$ dalle matrici casuali $S$ e $P$ .

Classic McEliece Key Encapsulation Mechanism

A parte alcune ottimizzazioni su Neiderreiter per diminuire la lunghezza delle chiavi e i tempi di cifratura e decifratura, ciò che caratterizza Classic McEliece è la scelta di una specifica classe di codici: i codici di Goppa.
Nonostante nello schema di McEliece venne proposto l’uso dei codici di Goppa, nel sistema di Neiderreiter questi vennero sostituiti dai codici di Reed-Solomon generalizzati. Scelta che ha portato vantaggi da un punto di vista delle prestazioni, ma che è stata dimostrata insicura da Sidelnikov e Shestakov nel 1992.
Nel corso degli anni ci sono state altre proposte, ad esempio i codici di Reed-Muller o i codici di Goppa quasi ciclici e quasi diadici, ma nessuno di questi è risultato altrettanto sicuro come i codici di Goppa binari irriducibili, che ad oggi rappresentano il candidato migliore per i crittosistemi di McEliece e Niederreiter.

Visto che in Classic McEliece si utilizzano codici di Goppa, la generazione delle chiavi può apparire molto distante da quella di Niederreiter, ma è importante notare che le due generazioni seguono sostanzialmente la stessa logica con la differenza che la chiave privata di Classic McEliece contiene anche una stringa di $n$ bit $s$ scelta uniformemente random.
Gli algoritmi di incapsulamento e decapsulamento di Classic McEliece poggiano su cifratura e decifratura di Niederreiteir.
Nella fase di incapsulamento, si genera random un plaintext $e$ di peso $t$ e si cifra attraverso lo schema di cifratura di Niederreiter. La chiave condivisa $K$ è ottenuta a partire da $e$ e dal cifrato $c$ corrispondente.
Il decapsulamento di $c$ avviene decodificando $c$ attraverso la decodifica di Niederreiter.

Classic McEliece KEM è corretto. Ciò significa che per ogni coppia di chiavi prodotta da Gen e per ogni ciphertext e chiave di sessione prodotta da Encap, Decap produrrà la stessa chiave di sessione di Encap.

Notiamo che, come in CRYSTALS-Kyber, nel decapsulamento si ha implicit rejection: nel caso in cui il decapsulamento non dia esito positivo non viene restituito un messaggio d’errore ma una chiave $K$ random calcolata a partire dalla chiave privata. In questa eventualità, le due parti sono in possesso di due chiavi crittografiche distinte e la discrepanza viene rilevata solo in una fase di comunicazione successiva.

Performance

Il focus principale degli autori di Classic McEliece è stato la sicurezza, ma negli anni lo schema ha subito diverse modifiche volte a migliorarne l’efficienza senza comportare diminuzioni nella sicurezza.

Una modifica consiste nello scegliere come chiave pubblica l’unica matrice generatrice di $C$ in forma sistematica se questa esiste; cioè una matrice della forma $(I_k| T)$ .
Circa il $29\%$ delle scelte di $C$ ha questa forma; perciò, l’algoritmo di generazione della chiave richiede circa $3.4$ tentativi in media per avere successo, ma la chiave pubblica ha dimensione $(n-k)\times k$ invece di $n\times k$ bit.

Un ulteriore miglioramento si ha considerando matrici ancora più ottimizzate, in forma semi-sistematica, con cui la probabilità di fallimento nella generazione della chiave pubblica viene notevolmente ridotta^[1] preservando la sicurezza.

Il livello di sicurezza standard in crittografia oggi è IND-CCA2 che, a differenza dei più deboli OW-CPA e IND-CPA, è adatto a contesti applicativi reali.
In letteratura esistono diversi modi per costruire uno schema KEM IND-CCA2 a partire da uno schema PKE con un livello di sicurezza inferiore, uno degli aspetti comuni ai principali KEM diffusi è l’utilizzo di opportune versioni della trasformata di Fujisaki-Okamoto (FO). Per la costruzione del KEM CRYSTALS-Kyber, ad esempio, la versione utilizzata richiede che, una volta decifrato un ciphertext, il plaintext corrispondente venga ricifrato e confrontato con quello ricevuto. Qualora la comparazione abbia esito positivo, una chiave crittografica viene derivata, altrimenti il ciphertext viene ritenuto invalido e rifiutato.

La versione utilizzata in Classic McEliece per costruire il KEM a partire dal PKE effettua delle specifiche modifiche allo schema per ottenere una maggiore efficienza dello schema, ad esempio, lo schema non necessita della re-encryption FO.

Oltre alla riduzione del costo per la re-encryption si ha anche una riduzione della memoria, in quanto non è più necessario avere la chiave pubblica per decapsulare.

Altre proposte NIST basate sui codici

Oltre Classic McEliece, al quarto round della call del NIST sono presenti altre due proposte di KEM basate su codici, BIKE e HQC.

BIKE (Bit Flipping Key Encapsulation) si basa sul crittosistema di Niederreiter usando una particolare classe di codici, i quasi-cyclic moderate density parity check (QC-MDPC) codes, che permettono di ottenere dimensioni delle chiavi e dei testi cifrati paragonabili ai sistemi basati su reticoli. In particolare, anche se il testo cifrato risulta più grande di quello prodotto da Classic McEliece, la dimensione della chiave pubblica è due ordini di grandezza più piccola.

HQC (Hamming Quasi-Cyclic) utilizza un paradigma diverso rispetto ai due KEM visti sopra. Anche qui vengono utilizzati codici QC-MDPC, ma, diversamente da BIKE e Classic McEliece, viene impiegata una cifratura simile a quella basata su Learning With Errors (LWE). Anche se le dimensioni delle chiavi pubbliche e del testo cifrato sono più grandi di quelle di BIKE , HQC ha il vantaggio di essere molto veloce in software.

Sia HQC che BIKE hanno alla base i codici QC-MDPC che, a differenza dei codici di Goppa utilizzati in Classic McEliece, possiedono algoritmi di decodifica con una probabilità non zero di fallimento . Questa probabilità viene misurata attraverso la Decoding Failure Rate (DFR) ed i parametri dei codici impiegati vengono scelti in accordo ad essa.

Mentre HQC e BIKE hanno performance simili, ognuno con i suoi punti di forza, per HQC le prestazioni e per BIKE la dimensione delle chiavi, McEliece vanta i ciphertext più piccoli tra tutti i KEM proposti nel processo di standardizzazione del NIST.

La dimensione del ciphertext di Classic McEliece va da un minimo di 96 byte per la versione mceliece348864 ad un massimo di 208 per le versioni mceliece6688128 e mceliece8192128. Il KEM basato sui reticoli CRYSTALS-Kyber, invece, produce dei ciphertext da 768 byte per Kyber512 a 1568 per Kyber1024.

Nonostante ciò, il principale svantaggio di Classic McEliece che negli anni si è riuscito soltanto in parte a limare, è quello dell’efficienza. Per quanto riguarda la dimensione delle chiavi, si hanno almeno due ordini di grandezza in più rispetto a CRYSTALS-Kyber.
La chiave pubblica di Classic McEliece va da un minimo di 261,120 byte per la versione mcelice348864 a un massimo di 1,357,824 byte per la versione mcelice8192128, risultando significativamente maggiore della capacità massima di un pacchetto IP, detta Maximum Transmission Unit (MTU), che è tipicamente fissata a 1,500 byte.

Sebbene McEliece sia di difficile applicazione in ambiti caratterizzati da requisiti stringenti di performance o memoria, il suo utilizzo, grazie alle dimensioni ridotte del testo cifrato, può fornire vantaggio in tutti quei contesti in cui la trasmissione del materiale della chiave pubblica non è costantemente necessaria, ad esempio nelle VPN. Chiavi McEliece, infatti, possono essere utilizzate come chiavi statiche a lungo termine che non necessitano di essere ruotate spesso.
^[1] da circa $71\%$ a circa $2^{\mu-\nu}$ con $\mu = 32$ , $\nu = 64$ per opportuni parametri di Classic McEliece.

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

Veronica Cristiano, laureata triennale in Matematica presso l’Università di Pisa e laureata magistrale in Matematica con specializzazione in Crittografia presso l’Università di Trento, entrata a far parte del gruppo di ricerca in Crittografia di Telsy a metà del 2021.

Giuseppe D’Alconzo, laureato in Matematica con specializzazione in Crittografia presso l’Università di Trento, ha svolto nel 2019 uno stage presso Telsy, occupandosi di Multi-party Computation e Attribute Based Encryption. Attualmente è studente di dottorato in Matematica Pura e Applicata presso il Politecnico di Torino, con una borsa a tema “Crittografia Post-Quantum” nell’ambito del programma UniversiTIM e in collaborazione con il Gruppo di Ricerca di Telsy.