Il progetto Quantum-Secure Net (parte 1/3): La minaccia quantum alla crittografia moderna

25/01/21

Questo articolo è suddiviso in tre puntate, ed ha l’intento di ripercorrere i principali elementi della crittografia e dei cambiamenti che il mondo “quantum” ha introdotto fino ad arrivare alla Quantum Key Distribution ed il progetto Europeo Quantum-Secure Net portato avanti da Italtel, Cefriel, Politecnico di Milano, CNR, Università Politecnica di Madrid e Telefonica.

La prima parte, a partire dallo stato attuale della crittografia arriva a definire i contorni della cosiddetta “minaccia quantum”. La seconda parte racconta i contorni della crittografia quantistica e post-quantistica, arrivando ad introdurre la Quantum Key Distribution (QKD). La terza parte racconta il progetto Quantum-Secure Net.

1. Lo stato attuale della crittografia

La crittografia a chiave pubblica è vitale per la sicurezza online e viene usata in moltissimi sistemi di uso quotidiano, da quelli bancari alle applicazioni mobili che usiamo tutti i giorni. Quando due o più parti vogliono comunicare, allo stato attuale della tecnologia, la crittografia a chiave pubblica assicura che le informazioni siano riservate e accurate e che le parti corrette stiano comunicando. La maggior parte delle volte la crittografia funziona dietro le quinte e non ci si rende conto del suo utilizzo, per non parlare del tipo di crittografia che è attualmente in uso. Quando si visita un sito web HTTPS (nell'immagine seguente dettaglio del certificato di un sito HTTPS), utilizzando Safari o Google Chrome, cliccando sull’icona relativa al Certificato e poi Dettagli, e scorrendo verso il basso fino a “Public Key Info” per vedere quali algoritmi stanno proteggendo la connessione a questo sito, probabilmente si vedranno algoritmi RSA o a ECC.

Alla base di ogni schema a chiave pubblica si trova un problema matematico “complesso”, cioè di complessa (ma non impossibile) risoluzione o, con una elevata “complessità numerica”. Se una persona o un computer può risolvere efficacemente questo problema, può bypassare il sistema crittografico. Non tutti i problemi matematici complessi sono adatti all'uso nella crittografia; la caratteristica chiave è che il problema deve essere difficile da risolvere in una direzione, ma facile nella direzione opposta. Per esempio, è facile moltiplicare due grandi numeri primi, ma è molto difficile fattorizzare un numero elevato nei numeri primi che lo costituiscono (in particolare all’aumentare della dimensione e del numero di numeri primi che fattorizzano il numero scelto).

La crittografia a chiave pubblica attualmente in uso si basa su problemi che coinvolgono la fattorizzazione in numeri primi (RSA), i logaritmi discreti (Diffie-Hellman) e le curve ellittiche (ECC). Anche se questi sembrano problemi diversi, in realtà sono tutti casi di un problema generale chiamato problema del sottogruppo nascosto abeliano. Questo problema è difficile da risolvere, specialmente con algoritmi classici che hanno una complessità cosiddetta (sub)esponenziale. Ci vorrebbero anni per rompere l’attuale crittografia a chiave pubblica anche con il più potente dei computer, supponendo che il sistema sia implementato correttamente.

2. Come si attaccano i sistemi di cifratura

In generale un attaccante di un sistema crittografico puro ha a disposizione due metodi di base: usare la forza bruta per decifrare un messaggio, provando tutte le chiavi possibili, o la risoluzione del problema matematico che sta alla sua base.

Gli attacchi a forza bruta tipicamente occupano molto tempo e sono direttamente dipendenti dalla lunghezza delle chiavi crittografiche usate (es., quanti numeri primi sono stati usati). In questo caso nulla impedisce all’attaccante di avere successo, se non il tempo.

La risoluzione del problema matematico è viceversa un problema di robustezza dell’algoritmo di cifratura. Un problema matematico può essere definito come difficile da risolvere in senso incondizionato o pratico. Ad esempio, un problema matematico oggigiorno di difficile risoluzione potrebbe non esserlo un domani, all’aumentare della potenza di calcolo dell’attaccante. In crittografia si indicano con il termine sicurezza computazionale incondizionata (unconditional computational security) quei problemi che risultano di impossibile risoluzione qualsiasi sia la potenza di calcolo dell’attaccante. Mentre si indicano con “pratica” (practical computational security) quelli che sono intrattabili con le risorse di calcolo attualmente disponibili, ma che potrebbero diventare trattabili un domani.

3. La minaccia quantum

I ricercatori sanno da decenni che nel momento in cui sarà possibile costruire un computer quantistico su larga scala, potrebbe svolgere calcoli ad un ritmo tale da minacciare i sistemi di crittografia su cui oggi contiamo per la sicurezza.

La attuale crittografia a chiave pubblica è bastata per decenni, ma il recente sviluppo dei computer quantistici rappresenta una minaccia concreta. I computer quantistici sono basati sulla fisica quantistica piuttosto che sulla fisica classica. Nell'informatica classica, l'unità di base dell'informazione è un bit, dove il valore 0 o 1 può rappresentare due livelli di tensione distinti. Nel calcolo quantistico, questa unità è sostituita da un qubit, dove il valore, una combinazione di 0 e 1, può rappresentare uno spin di elettroni o una polarizzazione di fotoni. I computer quantistici sfruttano il fenomeno quantistico che permette loro di risolvere certi problemi in modo molto più efficiente.

In particolare, l'algoritmo di Shor e i relativi algoritmi quantistici, senza addentrarsi nei dettagli, hanno dimostrato come sia possibile decifrare le chiavi utilizzate nella cifratura asimmetrica con tempi che crescono poco al crescere della lunghezza delle chiavi crittografiche (in altre parole, permette di risolvere il problema del sottogruppo nascosto abeliano in un tempo polinomiale invece che esponenziale, rispetto alla lunghezza della chiave). Quindi tutti gli algoritmi di cifratura che hanno l’attributo practical computational security (es. RSA, ECC, AES) risultano violabili in un tempo praticamente indipendente dalla lunghezza delle chiavi (l’attaccante riesce a calcolare le chiavi di cifratura impiegando una potenza di calcolo ed un tempo “normali”).

Nell’ipotesi che un computer quantistico sufficientemente potente venga sviluppato, questo algoritmo pone le basi teoriche necessarie per corrompere la attuale crittografia a chiave pubblica, indipendentemente dalla dimensione delle chiavi usate.

Sebbene attualmente non esista un computer quantistico adatto, ci sono molte ragioni per cui le organizzazioni stanno già esaminando la crittografia quantistica sicura, tra cui le seguenti.

  1. È difficile stimare quando il calcolo quantistico raggiungerà una applicabilità tale da corrompere gli attuali sistemi crittografici. Si tratta di una nuova forma di scienza e tecnologia, con aziende, governi e università che tentano approcci diversi, e le stime vanno da dieci a trent'anni. Tuttavia, occorre che la nuova crittografia quantistica sia studiata, implementata e testata prima che qualcuno sviluppi un computer quantistico.
  2. La transizione dei sistemi di crittografia può richiedere molti anni. Questo aspetto è spesso trascurato, ma la transizione di qualsiasi tecnologia, soprattutto in una grande organizzazione, è un processo difficile e può richiedere tempi nell’ordine di grandezza del decennio. Anche un semplice aggiornamento di un algoritmo o di una chiave può richiedere molto tempo. Può richiedere nuove infrastrutture, formazione per gli sviluppatori, riprogettazione di vecchie applicazioni e nuovi standard crittografici, distribuzione della nuova soluzione nella rete. Questo vale per l’intera struttura su cui è basata larga parte della rete Internet oggigiorno.
  3. Oltre al dato cifrato in transito occorre rendere sicura la memorizzazione dei dati. Le compagnie stanno già memorizzando dati crittografati in ottemperanza anche alle norme legislative (es., GDPR). Seppure oggigiorno il mondo quantum rappresenti un rischio relativamente remoto, e alcuni dati possano non essere così rilevanti tra dieci o trent'anni, la maggior parte dei dati saranno ancora sensibili. Dati come le informazioni personali o sanitarie (personal identifiable information / personal healthcare information PII/PHI) o le informazioni governative, necessitano di crittografia a lungo termine.
  4. Gli algoritmi di sicurezza quantistica sono più sicuri sia contro gli attacchi quantistici che contro quelli classici e, in alcuni casi, sono anche più efficienti e flessibili.

Quindi, quali sono gli algoritmi quantistici sicuri in sostituzione di quelli attuali e, come si può rispondere al crescente bisogno di sicurezza? Le risposte sono di due possibili categorie: la crittografia quantistica e la crittografia post-quantistica.

Enrico Frumento (1), Nadia Fabrizio (1), Paolo Maria Comi (2)

(1) CEFRIEL Politecnico di Milano, Viale Sarca 226 – 20126 Milano

(2) Italtel, Via Reiss Romoli – loc. Castelletto – 20019 Settimo Milanese (Mi)

Lavori Citati

[1]

R. Jozsa, “Quantum factoring, discrete logarithms, and the hidden subgroup problem,” Computing in Science & Engineering, vol. 3, no. 2, pp. 34-43, 17 12 2001.

[2]

“Difficoltà a comprendere l'algoritmo quantistico per il problema del sottogruppo nascosto abeliano,” [Online]. Available: https://qastack.it/cstheory/19129/difficulty-in-understanding-the-quantu....

[3]

Wikipedia, “Shor's algorithm,” [Online]. Available: https://en.wikipedia.org/wiki/Shor%27s_algorithm.

Immagini: GCN / web