Riepilogo
Kyber è stato sottoposto a crittoanalisi estensiva dalla sua pubblicazione nel 2017. Fino a luglio 2026, non si conosce alcun attacco che rompa i parametri raccomandati in tempo pratico. Tuttavia, esistono attacchi che riducono il costo e linee di ricerca aperte.
Attacchi Classici
Attacchi a Reticoli (BKZ + SVP)
L'attacco più conosciuto contro LWE è risolvere il problema di reticolo sottostante usando l'algoritmo BKZ (Block Korkine-Zolotarev) con un oracolo SVP (Shortest Vector Problem).
Costo stimato per ML-KEM-768:
- BKZ con blocco β ≈ 500
- Tempo stimato: > 2²⁰⁷ operazioni
- Memoria: diversi TB
La complessità cresce esponenzialmente con la dimensione del blocco. Per Kyber, i parametri sono scelti affinché il blocco necessario superi qualsiasi capacità pratica prevedibile.
Attacchi di Decisione
L'attaccante può tentare di distinguere istanze LWE da casuali usando tecniche statistiche. Questi attacchi non recuperano la chiave ma possono rompere la sicurezza semantica.
Per Kyber, i parametri sono scelti affinché il vantaggio del distinguitore sia trascurabile (< 2⁻¹⁴⁰).
Attacchi Algebrici
Alcuni lavori hanno esplorato attacchi algebrici sfruttando la struttura ad anello (per esempio, usando basi di Gröbner). Per Module-LWE con i parametri di Kyber, non è stata trovata una riduzione significativa del costo.
Attacchi Quantistici
Attacchi di Grover sul segreto
Grover può cercare il segreto s in spazio O(2^(n/2)). Per Kyber:
| Parametro | Ricerca classica | Ricerca quantistica (Grover) |
|---|---|---|
| ML-KEM-512 | 2²⁵⁶ | 2¹²⁸ |
| ML-KEM-768 | 2³⁸⁴ | 2¹⁹² |
| ML-KEM-1024 | 2⁵¹² | 2²⁵⁶ |
Grover offre un'accelerazione quadratica, ma rimane intrattabile per le dimensioni di Kyber.
Algoritmo di Shor
Shor non risolve LWE. Shor risolve il problema del logaritmo discreto e la fattorizzazione sfruttando la struttura di gruppo abeliano nascosto. LWE su reticoli non ha quella struttura — è un problema di approssimazione di reticoli, non di gruppi.
Algoritmo di Regev (quantistico)
Regev (2023) ha proposto un nuovo algoritmo quantistico che risolve LWE in tempo 2^(n/2) sotto certe condizioni, comparabile all'attacco classico con BKZ ma con vantaggi di memoria. Fino ad ora, non è stato dimostrato che superi gli attacchi classici per i parametri di Kyber.
Attacchi di Fourier
Gli attacchi quantistici basati sulla trasformata di Fourier su reticoli (come l'algoritmo di Kuperberg per isogenie) non hanno un analogo conosciuto che sia efficiente per LWE standard o Module-LWE.
Attacchi Side-Channel
Temporizzazione
L'implementazione di riferimento di Kyber è costante in tempo. Tuttavia, implementazioni errate possono far trapelare:
- Il segreto
stramite variazioni nella moltiplicazione NTT non costante - Il valore
mnella decompressione se non implementata con cura
Mitigazione: usare l'implementazione di riferimento verificata o librerie auditate (liboqs, AWS-LC, BoringSSL).
Consumo di Potenza / EM
Gli attacchi di analisi di potenza (DPA/SPA) possono recuperare s se il dispositivo non ha contromisure. Kyber è particolarmente vulnerabile in dispositivi embedded senza schermatura.
Mitigazione: blinding di esponenti, randomizzazione delle operazioni NTT, disaccoppiamento dei segnali.
Errori di Calcolo (Fault Attacks)
Indurre errori nel calcolo di NTT durante il disincapsulamento può fare sì che il risultato errato filtri informazioni su s.
Mitigazione: verifica ridondante, rilevamento errori in NTT.
Attacchi Ibridi
La NSA raccomanda X25519Kyber768 proprio perché nessuno si fida al 100% del solo Kyber. Un attacco che rompa Kyber ma non X25519 sarebbe comunque fermato dal livello classico, e viceversa.
Linee di Ricerca Aperte
| Linea | Rischio attuale | Note |
|---|---|---|
| Algoritmi quantistici per LWE | Basso | Non si conosce accelerazione subesponenziale |
| Attacchi algebrici migliorati | Basso-Medio | La struttura di modulo potrebbe essere sfruttabile |
| Attacchi con rete neurale | Basso | Le NN non hanno mostrato vantaggio su BKZ |
| Side-channel in implementazioni reali | Alto | Il maggior rischio reale oggi |
| Errori di parametrizzazione nei protocolli | Alto | Kyber è sicuro; il protocollo che lo usa forse no |
Conclusione
Kyber è sicuro contro ogni attacco conosciuto a luglio 2026. Il suo maggior rischio non è crittoanalitico ma implementativo e protocolare: una cattiva implementazione o un protocollo mal progettato possono rompere la sicurezza sebbene l'algoritmo sottostante sia solido.
Questo non è diverso dalla crittografia classica. La novità è che, essendo più recente, ha meno auditoria cumulativa di AES o SHA-3.
Riferimenti
- Albrecht, M. et al. (2022). "Estimate all the LWE, NTRU schemes!" — Stime di costo degli attacchi.
- Regev, O. (2023). "An Efficient Quantum Algorithm for LWE?" — Preprint, dibattito aperto.
- Bernstein, D. J. & Lange, T. (2020). "Post-quantum cryptography: handling the fallout."
- Xagawa, K. (2022). "Side-channel attacks on lattice-based KEMs." CHES 2022.