IA e crittografia post-quantistica: come cambia la cybersecurity

Viviamo in un periodo di profonda trasformazione in cui l’avvento delle nuove tecnologie e la loro diffusione sempre più capillare aprono nuovi versanti sul perimetro d’attacco di ogni sistema.

La cybersecurity attraversa quindi una fase di radicale trasformazione e mi riferisco in particolar modo alle applicazioni di intelligenza artificiale ed ai computer quantistici.

Questi strumenti se da un lato favoriscono la sicurezza di server e dati, ad esempio un’applicazione immediata è l’analisi di grandi quantità di dati dai log di sistema al fine di rilevare pattern di attacco, dall’altro lato possono essere utilizzati per generare nuovi, più sofisticati e potenti strategie di attacco ai sistemi.

Proviamo dunque a chiarire cosa sono IA e computer quantistici, le caratteristiche che li differenziano dai sistemi informatici “classici” e come queste peculiarità si applichino agli ambiti di cybersecurity presenti e scenari futuri.

Impatto delle IA sulla crittoanalisi

L’intelligenza artificiale, specialmente con l’uso del machine learning (ML) e del deep learning (DL), ha aperto nuove possibilità per attaccare i sistemi crittografici.

Questi due rami dell’intelligenza artificiale hanno peculiarità e quindi campi di applicazione differenti.

Il “machine learning”è quel ramo dell’informatica che si occupa dell’addestramento di un sistema al fine di eseguire attività senza che queste siano state programmate esplicitamente. Si usano algoritmi statistici per elaborare grandi quantità di dati, identificare modelli di dati (pattern) e prevedere risultati accurati per scenari sconosciuti o nuovi, in definitiva…. la macchina impara “da sola”.

Il deep learning è un sottogruppo del machine learning e viene elaborato sulle reti neurali che sono strutture algoritmiche modellate sul cervello umano, dove si cerca di “imitare” il funzionamento dei neuroni biologici al fine di compiere operazioni complesse, idealmente come un essere umano.

Prima di procedere vediamo quindi come funziona una rete neurale al fine di comprenderne appieno le implicazioni in cybersecurity.

Come funziona una rete neurale?

Una rete neurale si basa, come suggerisce anche il nome, su un insieme interconnesso di neuroni artificiali detti “nodi”.

Ogni nodo, è costituito da tre strati: di input, di elaborazione (hidden), di output. Le connessioni ad un nodo hanno un loro “peso”, ovvero una misura di quanto conterà quel determinato input nel neurone. Il neurone artificiale effettua una sommatoria dei pesi e se il valore complessivo supera un determinato valore soglia del neurone, questo si “attiva” e l’input viene elaborato e quindi restituito in output, a sua volta con un suo “peso”, diversamente l’elaborazione non avverrà terminando la propagazione dell’elaborazione su quel nodo.

I percorsi di elaborazione possono dare luogo a numerosità notevoli e topologie complesse in funzione del numero dei nodi e delle loro interconnessioni. Consideriamo infatti che una rete può arrivare ad avere milioni o anche miliardi di nodi e che ogni nodo è connesso, in generale, a più di un nodo.

La fase di addestramento di un sistema di deep learning, passa per la definizione dei pesi e con funzioni di correzione che regolano i pesi in modo tale che l’output che ci si attende sia quanto più possibile analogo a quello effettivamente elaborato.

È questo il modo in cui il sistema si autocorregge, “apprende” per così dire ed è il motivo per cui i metodi di deep learning tentano di automatizzare attività più complesse che in genere richiedono l’intelligenza umana.

In generale, quindi, mentre un sistema ML potrebbe essere addestrato per identificare email di phishing basandosi ad esempio su determinate parole, un sistema DL potrebbe riconoscerle, analizzando il testo senza la pre-impostazione di caratteristiche (feature) particolari.

Più in generale, mentre nei sistemi ML l’algoritmo apprende dai dati, ma spesso ha bisogno che un programmatore selezioni manualmente quali caratteristiche (features) usare, nel DL non si richiede che il programmatore selezioni manualmente le caratteristiche in quanto le reti neurali le trovano da sole.

Caso emblematico è l’utilizzo della IA per il riconoscimento dei volti, dove vengono utilizzati dataset con migliaia o decine di migliaia di immagini di volti in modo che la rete neurale analizzi le immagini, imparando automaticamente a riconoscere caratteristiche come contorni, occhi, naso, bocca senza che lo sviluppatore abbia definito manualmente le caratteristiche così come avviene nelle applicazioni ML (che però hanno il vantaggio di operare su dataset pià piccoli e quindi con meno risorse necessarie al loro funzionamento).

Applicazione IA al rilevamento delle email di phishing

Indicati quindi i fondamentali relativi all’intelligenza artificiale, prima di proseguire vediamo due esempi emblematici di IA, declinati in versione Machine Learning e Deep Learning, in uno scenario reale del delicato perimetro esposto dal fronte e-mail (spam, phishing, malware).

Esempio di applicazione mediante Machine Learning

• si crea un dataset con email etichettate come “phishing” o “legittime”;
• si stabiliscono e quindi estraggono delle caratteristiche (features) quali la presenza di parole sospette (“password”, “verifica”, “urgente”), il numero di link e se puntano a domini sospetti;
• si colleziona l’indirizzo email del mittente;
• la classe di IP del mailserver mittente
• ecc…

Un modello viene addestrato su questi dati e quindi, dopo la fase di test, messo in produzione.

Quando arriverà una nuova email, il modello analizzerà le caratteristiche decidendo se si tratta di phishing o meno, spostando automaticamente la mail nel cestino oppure non recapitando affatto la mail al destinatario.

Il machine learning ha il vantaggio di funzionare bene con dataset moderati e non richiede molta potenza di calcolo ma se l’attaccante cambia strategia, utilizzando ad esempio parole nuove, il modello potrebbe diventare meno efficace.

Esempio di applicazione mediante Deep Learning

In questo caso si potrebbe utilizzare un dataset di URL etichettati come phishing o legittimi.

Si estraggono feature dagli URL, come:

• lunghezza
• numero di caratteri speciali (-, _, ?, =, @, ecc.)
• numero di sottodomini
• presenza di parole chiave sospette (es. “login”, “banking”, “secure”, “account”, ecc.)

Il modello imparerà automaticamente a distinguere i pattern dei phishing da quelli dei link legittimi.
In uno scenario reale, quando arriva una nuova email, la rete neurale la analizzerà determinando se è dannosa o no. Questo sistema ha il vantaggio di poter rilevare nuovi phishing senza la necessità di aggiornare le caratteristiche (così come avviene con gli algoritmi di Machine Learning) ma ha bisogno di grandi quantità di dati e richiede hardware potente per l’addestramento.

Versatilità delle IA negli attacchi e difese crittografiche

Le particolari caratteristiche elaborative dei sistemi IA, di addestramento ed autoapprendimento, consentono a questi sistemi di porre sotto stress gli algoritmi ed i protocolli crittografici.

Alcuni ambiti di applicazione dell’intelligenza artificale al campo della cybersecurity sono:

• Analisi dei pattern crittografici: l’IA può identificare schemi in dati cifrati che sarebbero difficili da individuare per un essere umano.
• Attacchi side-channel potenziati: i modelli di ML possono analizzare segnali fisici (consumo energetico, emissioni elettromagnetiche, tempi di esecuzione) per estrarre chiavi crittografiche.
• Cracking delle password: reti neurali avanzate possono prevedere password e chiavi crittografiche basandosi su enormi dataset.
• Attacchi basati su IA generativa: modelli come le GAN (Generative Adversarial Networks) possono generare input crittografici per testare la sicurezza dei sistemi.

Naturalmente vi sono già accorgimenti per contrastare l’incremento delle capacità di elaborazione, quali, ad esempio:

• Aumento della casualità: utilizzo di generatori di numeri casuali (TRNG) più sicuri per evitare pattern prevedibili.
• Resistenza agli attacchi side-channel: miglioramenti hardware per ridurre perdite di informazioni attraverso canali laterali.
• Autenticazione avanzata: sistemi multi-fattore e biometria per mitigare attacchi di forza bruta basati su ML.

Applicazioni del Machine Learning

Il machine learning è particolarmente utile nell’analisi dei pattern crittografici allo scopo di rilevare e prevedere sequenze.

Algoritmi

• Random Forest (RF): utile per classificare dati crittografici e individuare schemi ricorrenti.
• Support Vector Machines (SVM): può essere utilizzato per distinguere dati cifrati da dati in chiaro o per rilevare correlazioni deboli.
• K-Nearest Neighbors (KNN): utilizzato per il clustering di pattern crittografici simili.
• Hidden Markov Models (HMM): utile per prevedere sequenze crittografiche basandosi su dati storici.
• K-Means Clustering: utilizzato per raggruppare blocchi di dati simili in analisi di cifrari (ad es. AES).

Applicazioni in crittografia

• Analisi della forza delle chiavi crittografiche: determinazione della robustezza di una chiave rispetto a determinati attacchi.
• Riconoscimento di schemi crittografici: identificazione di algoritmi di cifratura basati su caratteristiche del testo cifrato.
• Rilevamento di attacchi crittografici: identificazione di vulnerabilità nei protocolli crittografici tramite pattern.

In definitiva il clustering di pattern crittografici mira a identificare e raggruppare schemi ricorrenti in dati crittografati. Identficando la struttura (pattern) si possono carpire informazioni sulla chiave o sull’algoritmo di cifratura utilizzato, informazioni che potranno poi essere utilizzate a scopo di difesa, verificando la qualità della protezione oppure a scopo di attacco, individuando e sfruttando le debolezze nel sistema.

Uno scenario tipico è quello di una comunicazione cifrata in cui ci si pone in ascolto in un punto intermedio ed utilizzando il volume di dati della comunicazione come input del sistema di machine learning.

Tecniche di deep learning applicate alla crittoanalisi

In merito invece al deep learning, questo viene particolarmente in aiuto alla crittoanalisi. È più adatto rispetto al machine learning quando si tratta di analizzare grandi quantità di dati complessi e rilevare pattern non evidenti.

Reti Neurali Convoluzionali (CNNs)

Possono essere usate per analizzare il testo cifrato e identificare strutture specifiche. Le CNNs sono particolari reti neurali adatte ad elaborare dati strutturati in forma di griglia, come immagini e video.

La “convoluzione” è un’operazione tra due funzioni che produce una terza funzione, mostrando come una si “propaga” attraverso l’altra.

Nelle CNN, la convoluzione viene applicata tra:

• Un’immagine di input (una matrice di pixel).
• Un filtro (o kernel) (una matrice più piccola con valori predefiniti o appresi).

Il filtro scorre (o “convolva”) l’immagine eseguendo prodotti scalari tra il filtro stesso e le porzioni dell’immagine, generando una feature map (mappa delle caratteristiche).

Operativamente:

Si prende una finestra dell’immagine grande quanto il filtro.

1. Si moltiplicano i valori dei pixel della finestra con i valori del filtro.
2. Si sommano i prodotti ottenuti.
3. Il valore risultante viene salvato nella posizione corrispondente della feature map.
4. Il filtro si sposta e il processo si ripete fino a coprire tutta l’immagine.

Esempio

Se l’immagine di input è:

1 2 3

4 5 6

7 8 9

e il filtro 2×2 è:

1 0

0 -1

Applicando la convoluzione, otterremo una feature map che evidenzierà i cambiamenti nei pixel.

Applicazioni tipiche sono il riconoscimento facciale (es. Face ID di Apple) oppure la generazione di immagini per la creazione di deepfake (es. GAN – Generative Adversarial Networks).

Reti Neurali Ricorrenti (RNNs) e LSTMs

Questo tipo di rete neurale è adatta per analizzare sequenze di cifratura e predire correlazioni temporali nei dati criptati.

Le RNN sono progettate per gestire input sequenziali grazie alla loro memoria interna, che consente di tenere traccia delle informazioni passate.

Hanno connessioni ricorrenti: ogni stato nascosto dipende non solo dall’input attuale, ma anche dallo stato precedente.

Possono essere addestrate con backpropagation attraverso il tempo (BPTT, Backpropagation Through Time). In questi casi durante l’addestramento, oltre ad aggiornare i pesi occorre considerare la dipendenza temporale dei dati basandosi sugli stati precedenti della rete.
Questo tipo di reti neurali “soffre” la cattura di dipendenze a lungo termine in quanto man mano che la sequenza diventa più lunga, le informazioni passate si degradano ed avviene il problema del vanishing gradient ovvero gli aggiornamenti dei pesi diventano sempre più piccoli man mano che la rete si propaga indietro nel tempo, rendendo difficile apprendere relazioni di lungo termine. Inoltre l’elaborazione richiede molte risorse ed è lenta.
Per ovviare a queste limitazioni, sono state introdotte le LSTM.
Le LSTM (Long Short-Term Memory) sono una variante delle RNN progettate con delle ottimizzazioni al fine di superare il problema del vanishing gradient e per gestire meglio le dipendenze a lungo termine. Queste introducono un meccanismo di gating (gate = cancello) per controllare il flusso delle informazioni all’interno della rete:

• Forget gate (Cancello di dimenticanza): stabilisce quali informazioni scartare.
• Input gate (Cancello di aggiornamento): stabilisce quali nuove informazioni aggiungere alla memoria.
• Output gate (Cancello di output): determina quale informazione della memoria deve essere utilizzata per l’output.

Questi tre gate permettono alle LSTM di memorizzare informazioni importanti più a lungo ed in modo più efficente rispetto alle RNN standard.

Autoencoder e la sfida dei captcha

Queste reti neurali hanno la caratteristica di avere un apprendimento non supervisionato, con l’obiettivo principale di comprimere e poi ricostruire i dati di input. Sono spesso impiegate per riduzione della dimensionalità (trasformare i dati da uno spazio con molte variabili – features – a uno spazio con meno variabili, preservando le informazioni più importanti), denoising e generazione di dati.

Un autoencoder è composto da due parti principali, l’encoder che comprime l’input in una rappresentazione più compatta (ad es. trasformando un’immagine 28×28 in un vettore di 32 elementi) ed il decoder che ricostruisce i dati originali dalla rappresentazione compressa.
Più il modello è addestrato, più la ricostruzione diventa accurata: l’obiettivo è che il modello impari a codificare solo le informazioni più rilevanti, eliminando il rumore o le ridondanze dai dati di input.

Possono essere usati sia per creare CAPTCHA che per tentare di risolverli, a seconda di come vengono progettati. In particolare vi sono i Variational Autoencoder (VAE) o le GAN (Generative Adversarial Networks) che possono generare CAPTCHA difficili da risolvere.

In questi casi si allena un VAE o una GAN su un dataset di CAPTCHA esistenti.
Il modello apprende a generare nuove immagini simili, ma con variazioni che le rendono uniche.
Si possono aggiungere distorsioni, rumore e pattern casuali per rendere il CAPTCHA ancora più difficile da decifrare.

All’inverso gli autoencoder possono anche essere addestrati a decodificare CAPTCHA, soprattutto se basati su immagini o testo distorto, avendo la caratteristica del denoising.

Cos’è un Captcha

Ricordo qui brevemente che un CAPTCHA – Completely Automated Public Turing test to tell Computers and Humans Apart) è un test progettato per distinguere tra utenti umani e bot.

L’avanzamento delle reti neurali ha reso evidente un paradosso: i CAPTCHA, concepiti per distinguere uomini e macchine, sono ora risolvibili più velocemente e con maggiore precisione dalle macchine stesse. Questo solleva importanti questioni semantiche e filosofiche:

• dove si trova il confine tra umano e macchina? Se una rete neurale può risolvere un CAPTCHA meglio di un essere umano, il test rimane un criterio valido per la distinzione?
• l’illusione della sicurezza: molti CAPTCHA sono ormai una formalità, non una barriera efficace contro i bot, ivi compreso il ReCAPTCHA (quantomeno fino alla versione 2) di Google.

Il futuro dei CAPTCHA potrebbe quindi dipendere dall’uso di dati comportamentali, come il modo in cui un utente interagisce con una pagina web, o da test cognitivi più sofisticati in quanto i progressi del deep learning stanno rapidamente erodendo la sua efficacia.

Questo scenario impone la necessità di nuove soluzioni basate su tecnologie più avanzate, capaci di distinguere non solo tra umano e bot, ma tra comportamento umano naturale e azioni simulate da intelligenza artificiale. Il futuro della sicurezza online potrebbe risiedere in strategie più dinamiche e adattive, dove l’intelligenza artificiale non sia solo il problema, ma anche parte della soluzione.

Reti generative avversarie nella sicurezza informatica

Reti neurali possono essere usate per generare chiavi crittografiche sicure o attaccare cifrari generando dati simili a quelli originali. Sono composte da due reti che competono tra loro in un processo di apprendimento automatico:

1. Il Generatore (Generator, G): crea dati falsi a partire da un rumore casuale e cerca di ingannare il discriminatore producendo dati sempre più realistici.

2. Il Discriminatore (Discriminator, D): distingue tra dati reali (dal dataset) e dati falsi (generati dal generatore). Migliora nel riconoscere i dati falsi man mano che il generatore migliora.

Entrambe le reti vengono addestrate iterativamente: il generatore migliora nel creare dati convincenti, mentre il discriminatore affina la sua capacità di riconoscere i falsi.
Il processo continua finché il discriminatore non può più distinguere i dati reali da quelli generati.

Applicazioni del Deep Learning in crittografia

• Analisi delle tracce laterali: utilizzo di reti neurali per analizzare il consumo energetico o il tempo di esecuzione di un algoritmo crittografico e dedurre informazioni sulla chiave.
• Attacchi a cifrari simmetrici e asimmetrici: reti neurali possono essere addestrate per trovare pattern nei dati crittografati e predire informazioni sulle chiavi.
• Creazione di cifrari basati su reti neurali: sviluppo di cifrari con approcci generativi come le GANs.

Esempi pratici

• Analisi delle Tracce Laterali su AES: utilizzando un’RNN per predire la chiave AES analizzando il consumo di energia.
• Cracking di Captcha: utilizzo delle CNN per decifrare codici Captcha con immagini distorte.
• Predizione della Chiave RSA: sfruttando un dataset di chiavi generate, un modello di DL può apprendere pattern e predire chiavi deboli.

Strumenti per implementare sistemi di machine e deep learning

Per sperimentare lo sviluppo di sistemi di intelligenza artificiale, qui di seguito alcuni ambienti

• TensorFlow / PyTorch: framework per costruire e addestrare reti neurali.
• Scikit-learn: libreria per l’implementazione di modelli ML tradizionali.
• Keras: libreria di alto livello per DL

Personalmente ho avuto modo di utilizzare PyTorch che peraltro supporta le librerie CUDA per velocizzare l’elaborazione e l’ambiente Python favorisce il rapido apprendimento.

Impatto dei Computer Quantistici sulla crittografia

Il nuovo fronte della battaglia crittografia/crittoanalisi si svolge anche sul campo dei computer quantistici e della crittografia quantistica.

I computer quantistici utilizzano i principi della Meccanica Quantistica quali la sovrapposizione e l’entanglement per eseguire calcoli che i computer classici non possono affrontare in tempi realistici.

Desidero però, prima di andare avanti, fornire alcuni concetti di base in merito ai computer quantistici, qubit e modalità operativa della crittografia quantistica e di come i sistemi quantistici possano mettere in difficoltà gli attuali standard crittografici.

Il qubit, ovvero il quantum bit, come suggerito anche dal nome, rappresenta l’unità minima di informazione in un sistema quantistico ed è nella tecnologia quantistica, l’analogo del bit in un sistema computazionale ordinario.

Mentre il bit può assumere soltanto i due valori 0 ed 1 alternativamente, il qubit ha la proprietà di assumere contemporanemente i valori 0 ed 1 che sono detti stati di base, fin quando il valore del qubit non venga misurato, momento in cui il valore diventa univoco. Questa proprietà è detta “sovrapposizione” e differenzia notevolmente un sistema di memoria di un computer ordinario da quello di un computer quantistico poiché in una cella ordinaria di memoria il registro può assumere in un dato istante un solo valore e non due contemporaneamente.

Questa caratteristica consente ad un computer quantistico di eseguire molte operazioni in parallelo, aumentando esponenzialmente la potenza di calcolo rispetto ad un computer classico.

Nel qubit il fenomeno quantistico detto “entanglement” indica che due o più qubit diventano interdipendenti, indipendentemente dalla loro distanza. Una misura su uno dei qubit, influenzerà automaticamente l’altro, anche se si trovasse dall’altra parte dell’universo!
L’entanglment nel qubit permette di correlare informazioni tra i qubit in modi che non sono possibili nei computer classici incrementando velocità ed efficienza negli algoritmi che facciano uso specifico di questa proprità (algoritmi quantistici).

Ad esempio Google ha usato il processore quantistico Sycamore per eseguire un algoritmo di campionamento di circuiti casuali. Il computer quantistico ha completato l’algoritmo in circa 200 secondi, mentre un supercomputer classico (Summit, il più potente in quel momento) è stato stimato che avrebbe richiesto circa 10.000 anni.
Il test fu contestato dalla IBM, che suggerì ottimizzazioni che avrebbero ridotto il tempo di calcolo a 2-3 giorni. Resta comunque una dimostrazione di vantaggio quantistico: nel migliore dei casi parliamo di 2, 3 giorni contro 2, 3 minuti. Traslando nel campo della crittografia, un sistema crittografico che sarebbe possibile “bucare” in anni richiederebbe, nel peggiore dei casi, solo pochi mesi o giorni in un caso ottimistico (per l’attaccante)!

Algoritmi crittoanalitici su computer quantistici

Sono due, principalmente, gli algoritmi che minacciano la crittografia moderna:

• Algoritmo di Shor: capace di fattorizzare numeri interi in un tempo polinomiale, rendendo vulnerabili RSA, Diffie-Hellman e ECC.
• Algoritmo di Grover: Permette di accelerare la ricerca delle chiavi simmetriche, dimezzando la loro sicurezza effettiva (es. una chiave AES-256 diventerebbe equivalente a una AES-128).

A questo punto, riferendomi all’algoritmo di Shor, è bene precisare cosa si intenda per “tempo polinomiale” sgomberando il campo da eventuali dubbi.

Problemi P – NP

Per definizione un algoritmo è una sequenza finita di operazioni eseguibili che risolvono un determinato problema. Abbiamo quindi un ordine delle operazioni, dalle prime alle ultime e queste operazioni devono concludersi con la risoluzione del problema cui è stato applicato l’algoritmo. Ciò che viene esplicitato è che il numero delle operazioni deve essere “finito” ovvero l’algoritmo deve terminare fornendo il risultato che ci si attende.

Gli algoritmi possono quindi essere classificati in base alla loro complessità temporale, vale a dire all’intervallo di tempo impiegato ad essere completati in funzione dei dati in ingresso (input).

In generale sono più efficienti gli algoritmi che terminano in un intervallo di tempo direttamente proporzionale al volume di dati di ingresso, risultando invece meno efficienti quelli che terminano in un intervallo di tempo che non è più direttamente proporzionale al volume dei dati di ingresso.

Un algoritmo con complessità temporale quadratica termina in un intervallo di tempo che è proporzionale al quadrato del volume dei dati in ingresso e così via. Una complessità temporale di ordine n si indica con il simbolo O(dⁿ) dove d è l’insieme dei dati di input.

La complessità computazionale è invece un concetto più generale, che comprende sia la complessità temporale che la complessità spaziale (uso della memoria).

Ebbene, un algoritmo è risolvibile in un tempo polinomiale (Classe P – Polynomial time) se può essere risolto da una macchina deterministica in un tempo proporzionale a una potenza di n, ossia
𝑂(𝑛^𝑘). Gli algoritmi che hanno questa caratteristica sono considerati efficientemenre risolvibili dai computer “classici”.

Algoritmi NP (Classe NP – Nondeterministic Polynomial time) sono quelli per cui la soluzione può essere verificata in tempo polinomiale da una macchina deterministica e non è però noto alcun algoritmo per cui possano essere risolti in un tempo polinomiale.
I problemi di questo tipo (NP) sono alla base della crittografia moderna a chiave pubblica che consente, mediante la procedura di handshake, di stabilire la chiave segreta da utilizzare per la successiva comunicazione simmetrica risolvendo il problema dello scambio sicuro della chiave.

Fattorizzazione e logaritmo discreto

Fondamentali in crittografia sono i due problemi NP della fattorizzazione di numeri primi e del logaritmo discreto su curve ellittiche (ECDLP): risulta estremamente facile e veloce calcolare il prodotto di due numeri primi interi grandi ma risulta molto difficile e quindi lento lo scomporre il prodotto nei suoi fattori primi, così come è facile e veloce calcolare il modulo di una elevazione a potenza ma risulta difficile calcolarne il logaritmo discreto: tutte coppie di operazioni queste, una l’inversa dell’altra, dove in una direzione il calcolo è pressocché immediato mancando però algoritmi efficienti che realizzino la funzione inversa.

Tra gli altri problemi NP notevoli usati in crittografia vi è il problema della soddisfacibilità booleana (SAT).

Problema SAT

Consiste nel determinare se esiste un’assegnazione di valori di verità (vero/falso) per le variabili booleane di una formula booleana tale che la formula stessa risulti vera.

Il problema SAT è uno dei problemi NP-completi, il che significa che è il più “difficile” tra i problemi che appartengono alla classe NP (Teorema di Cook-Levin).

SAT può essere utilizzato sia per costruire funzioni crittografiche che per mettere alla prova la sicurezza degli algoritmi crittografici, analizzando la difficoltà di risolvere determinati problemi di soddisfacibilità.

Anche i problemi SAT sono “sotto attacco” dei computer quantistici in quanto, anche se non ridotti ad un tempo polinomiale (si tratta di problemi NP-Completi), l’applicazione dell’algoritmo di Grover fornisce un’accelerazione quadratica nella ricerca di soluzioni ed ulteriori ottimizzazioni potrebbero essere pubblicate in ogni momento.

Contromisure alla crittoanalisi quantistica

Come si vede occorre già pensare a contromisure efficaci alla computazione quantistica al fine di salvaguardare la riservatezza ed integrità dei dati.

Alcune di queste contromisure sono:

• Aumento della lunghezza delle chiavi: per AES e altre crittografie simmetriche, chiavi di almeno 256 bit sono raccomandate.
• PQC – Post Quantum Cryptography: sono algoritmi resilienti ai computer quantistici. I principali sono gli algoritmi lattice-based, hash-based e code-based.
• Hybrid Cryptography: combinazione di sistemi classici e quantistici.

Approfondiamo adesso alcuni aspetti relativia gli algoritmi PQC.

Algoritmi lattice-based

Questi algoritmi si basano sulla difficoltà dei problemi sui reticoli, in particolare sul problema di trovare il “shortest vector” o il “closest vector” all’interno di un reticolo in uno spazio multidimensionale. Gli algoritmi lattice-based sono considerati resistenti agli attacchi quantistici poiché mentre fattorizzazione e calcolo del logaritmo discreto logaritmo, come abbiamo visto, sono vulnerabili ad un attacco quantistico, i problemi sui reticoli sembrano resistere agli algoritmi quantistici come Shor. Alcuni esempi di algoritmi lattice-based includono anche la fondamentale crittografia a chiave pubblica – per lo scambio della chiave – come NTRU e Kyber.

Algoritmi hash-based

Ricordo qui che un hash crittografico è una funzione che trasforma un input di qualsiasi dimensione in un valore fisso di lunghezza predefinita. Questo valore è chiamato hash e rappresenta il digest o impronta digitale del dato cui è stato applicato l’algoritmo ed è unico (con un’elevata probabilità) per ogni input.

Ebbene questa classe di algoritmi crittografici post-quantistici si basa proprio sull’uso di funzioni hash crittografiche per costruire schemi di firma digitale sicuri. Il principio è che la difficoltà di invertire una funzione hash rende difficile per un attaccante creare una firma falsa, anche in presenza di un computer quantistico. Algoritmi come XMSS (eXtended Merkle Signature Scheme) e SPHINCS+ sono esempi di sistemi hash-based che possono essere usati per creare firme digitali sicure in un contesto post-quantistico.

Algoritmi code-based (basati su codici)

Gli algoritmi code-based utilizzano la teoria dei codici correttori di errori, in particolare i codici di Goppa, per creare sistemi crittografici sicuri. La difficoltà di decodificare un codice è il cuore della sicurezza di questi algoritmi. Un esempio noto è McEliece, che è un algoritmo di cifratura a chiave pubblica resistente agli attacchi quantistici.

NIST e standard PQC

L’esigenza di cautelarsi sul versante aperto dalle IA e dai computer quantistici è tale che il NIST (National Institute of Standards and Technology) ha avviato già dal 2016 un’iniziativa per stabilire standard di crittografia post-quantistica per una resilienza a lungo termine.

Questa iniziativa si articola in due principali obiettivi:

• 1. Sviluppare algoritmi sicuri contro i computer quantistici: questi algoritmi dovranno essere resistenti agli attacchi di computer quantistici e di computer classici.
• Sostituire gli attuali algoritmi per la crittografia a chiave pubblica, la firma digitale e lo scambio di chiavi.

Il 14 agosto 2024 sono stati pubblicati gli ultimi risultati, ovvero, cito: “il NIST ha selezionato quattro algoritmi che standardizzerà come risultato del PQC Standardization Process. Il meccanismo di incapsulamento a chiave pubblica selezionato è stato CRYSTALS-KYBER, insieme a tre schemi di firma digitale: CRYSTALS-Dilithium, FALCON e SPHINCS+. Si prevede che questi algoritmi saranno in grado di proteggere le informazioni sensibili del governo degli Stati Uniti nel prossimo futuro, anche dopo l’avvento dei computer quantistici”. L’annuncio del NIST è reperibile qui.

Ulteriori approfondimenti su algoritmi crittografici, reti e crittografia quantistica nel mio libro: “La Crittografia da Cesare ai quanti“