crittografia

Blockchain a rischio con i computer quantistici: quali soluzioni

L’avvento del quantum computer sta mettendo in discussione tutte le attività basate sugli algoritmi a chiave pubblica, a cominciare dalla blockchain. Ecco perché e le possibili soluzioni per una crittografia post quantistica

Pubblicato il 07 Ago 2018

Silvano Marioni

Content curator on ICT Security and Business Continuity, CISSP, AMBCI

Blockchain utilizza tecnologie crittografiche che saranno a rischio al momento in cui i computer quantistici supereranno l’attuale periodo di sperimentazione. Questo periodo, oggi stimato tra i 10 e 15 anni potrebbe risultare anche inferiore, vista la rapida evoluzione della tecnologia. Conoscere il problema e le possibili soluzioni può essere utile per prevenire falsi entusiasmi e definire una corretta strategia per il futuro.

Indice degli argomenti

Blockchain e crittografia

Per capire il problema, senza entrare nel dettaglio del funzionamento della tecnologia Blockchain, ci limiteremo ad esaminare le tecniche di crittografia fondamentali che la caratterizzano: gli algoritmi di hash e la firma digitale.

L’algoritmo di hash

L’algoritmo di hash è un sistema di cifratura che elabora un documento elettronico di qualsiasi dimensione e genera come risultato un riassunto composto da un insieme di bit di lunghezza fissa. Le caratteristiche degli algoritmi di hash sono l’impossibilità di essere utilizzati al contrario, e quindi di risalire dal riassunto al documento originale, e la certezza che sia generato un solo riassunto. Questo garantisce l’integrità del documento elettronico, assicurando che ogni modifica, sia pur minima, venga messa immediatamente in evidenza. Nella tecnologia Blockchain l’algoritmo di hash è utilizzato per garantire che i vari blocchi non possano essere modificati in momenti successivi senza essere segnalati a tutte le parti in gioco.

Per esempio il Bitcoin usa come algoritmo di hash SHA-256 che genera una stringa di 256 bit mentre Ethereum usa l’algoritmo di hash KECCAK-256, base del nuovo standard SHA-3, che genera una stringa di 256 bit.

La firma digitale

La firma digitale è un sistema per garantire la sicurezza di una transazione effettuata tra due parti e ne definisce il rapporto di fiducia. Utilizza un algoritmo a chiave pubblica che si basa su una coppia di chiavi. Il mittente usa una chiave privata, che deve tenere segreta, per firmare una transazione e il destinatario usa una chiave pubblica, divulgata dal mittente, per verificarla e avere la certezza che la transazione provenga dal mittente designato e che non sia stata alterata.

La firma digitale permette di effettuare in modo certo e sicuro la transazione Blockchain garantendone sia l’integrità, perché non è stata alterata successivamente al suo invio, sia l’autenticazione del mittente che l’ha firmata e di conseguenza assicurandone il non ripudio.

Elliptic Curve Digital Signature Algorithm (ECDSA)

Sia Bitcoin che Ethereum utilizzano per la firma digitale l’algoritmo Elliptic Curve Digital Signature Algorithm (ECDSA), un sistema crittografico a chiave pubblica basato su curve ellittiche, caratterizzato da efficienza e velocità nei processi di firma e verifica.

Il processo avviene in modo trasparente per l’utente che utilizza normalmente un indirizzo di un Wallet e una password per sbloccarlo. L’indirizzo del Wallet è associato alla chiave pubblica e la password è associata alla chiave privata. La perdita della password non permette di utilizzare la propria chiave privata e corrisponde all’impossibilità di certificare la propria identità. La conseguenza è la perdita di tutto quanto è memorizzato nella Blockchain.

Cos’è il quantum computing, i progetti e i primi successi

Il quantum computing è una tecnologia in evoluzione che promette di raggiungere potenze di calcolo inimmaginabili con le tecnologie dei moderni computer digitali. Basato sulle regole della meccanica quantistica e ipotizzato a livello teorico dal premio Nobel per la fisica Richard Feynman nel 1981, è stato in seguito confermato da numerose verifiche pratiche a livello sperimentale. Questo meccanismo, difficile da comprendere a livello intuitivo, si basa su una serie di bit quantistici, chiamati qubit, che a differenza dei bit tradizionali possono avere uno stato multiplo nello stesso istante.

Attualmente numerose università in tutto il modo e organizzazioni, tra le quali IBM, NASA e Google, stanno lavorando su progetti di computer quantistici e si cominciano a vedere i primi successi, anche se limitati a modelli con processori in scala ridotta. Oggi la potenza dei computer quantistici è caratterizzata dal loro numero di qubit, IBM ha un sistema da 50 qubit e Google ne ha appena presentato uno da 72 qubit, ma il problema principale che li caratterizza è la gestione della loro instabilità.

Nella sua versione definitiva, aumentando il numero di qubit e risolvendo i problemi di stabilità, il quantum computing sarà in grado di trovare le soluzioni ai problemi con complessità esponenziale.

La sicurezza degli algoritmi a chiave pubblica

Questi problemi diventano computazionalmente intrattabili al crescere della loro complessità anche per il più potente computer digitale ma potrebbero essere risolti rapidamente da un computer quantistico. Un esempio di questo tipo di problemi riguarda gli algoritmi a chiave pubblica, quali ad esempio RSA, ECDSA, DSA e altri, che si basano su una funzione unidirezionale che è semplice da calcolare in modo diretto ma praticamente impossibile da risolvere in modo inverso. Questa impossibilità di risolvere il calcolo in modo inverso è quello che oggi garantisce la sicurezza di questi algoritmi.

L’avvento dei computer quantistico permetterà di eseguire in modo immediato questo calcolo inverso, scardinando la sicurezza degli algoritmi a chiave pubblica, che persa ogni efficacia, potrebbero diventare una semplice pietra miliare nella storia della crittografia.

L’algoritmo di Shor e rischi per la Blockchain

Gli algoritmi a chiave pubblica si basano sulla difficoltà di scomposizione in fattori del prodotto di grandi numeri primi, come nel caso di RSA, o sui logaritmi discreti e le curve ellittiche come nel caso di ECDSA.

Peter Shor degli AT&T Laboratories ha dimostrato matematicamente che con un computer quantistico è possibile scomporre rapidamente in fattori il prodotto di due numeri primi molto grandi. L’algoritmo di Shor sarà utilizzabile al momento in cui sarà disponibile un computer quantistico sufficientemente potente e permetterà di scardinare l’algoritmo RSA e con una piccola variante anche l’algoritmo ECDSA.

Il National Institute of Standards and Technology (NIST) ha stimato che per un attacco con l’algoritmo di Shor a un moderno algoritmo a chiave pubblica, quale ad esempio RSA a 2’048 bit, sarebbe sufficiente un computer quantistico con 5’000 qubit, una tecnologia ancora di là da venire, ma che avrebbe delle prestazioni impressionanti.

Oggi un computer digitale che usa il più efficiente algoritmo conosciuto effettuerebbe la scomposizione in fattori di un numero di 300 cifre in circa 150’000 anni. Un computer quantistico che utilizza l’algoritmo di Shor troverebbe la soluzione in pochi secondi.

L’utilizzo dell’algoritmo di Shor potrebbe creare un grosso problema per la tecnologia Blockchain perché eliminerebbe completamente la sicurezza degli algoritmi a chiave pubblica. Questo significa che sarebbe possibile ricavare la chiave privata conoscendo il testo cifrato e la chiave pubblica, evento estremamente pericoloso che permetterebbe il furto dei Bitcoin associati alla chiave privata o, se la transazione non fosse ancora registrata nella blockchain, la creazione di transazioni fasulle. Nel caso di Ethereum un altro possibile rischio potrebbe essere quello di possibili malversazioni nella gestione dei contratti intelligenti basati sulla firma digitale.

L’algoritmo di Grover

Un’altra tecnica crittografica possibile con l’avvento dei computer quantistici è l’algoritmo di Grover che permette di velocizzare la ricerca tra le possibili soluzioni.

Questo algoritmo è applicabile solo per scardinare algoritmi di cifratura simmetrici (AES, DES, algoritmi di hash) e riesce a dimezzare i tempi nel caso di ricerche di “forza bruta”. Le sue prestazioni non sono così innovative e pericolose come per l’algoritmo di Shor perché può essere facilmente contrastato aumentando la lunghezza della chiave di cifratura.

Nella tecnologia blockchain i più importanti tipi di algoritmi simmetrici usati sono quelli di hash che non sono quindi particolarmente vulnerabili al Quantum Computing. Paradossalmente con un computer quantistico che utilizza l’algoritmo di Grover si potrebbero addirittura aumentare le prestazioni delle attività di “mining” per creare nuova moneta.

Possibili soluzioni

Per far fronte ai rischi del computer quantistico, in tutto il mondo università, istituti di ricerca e aziende si stanno impegnando per trovare nuove soluzioni crittografiche.

Sia il National Institute of Standards and Technology (NIST) che l’European Telecommunications Standards Institute (ETSI) stanno affrontando il problema per definire gli standard per una crittografia post quantistica (PQC – Post-Quantum Cryptography).

Completa sostituzione degli algoritmi a chiave pubblica

Questa crittografia deve garantire la sicurezza dei nuovi sistemi di cifratura e di firma e offrire dei percorsi di transizione dagli algoritmi attuali alle nuove soluzioni. Se per gli attuali algoritmi a chiave simmetrica può bastare il semplice aumento della lunghezza della chiave, per gli algoritmi a chiave pubblica è necessaria la loro completa sostituzione. Sono disponibili da tempo nuove famiglie di algoritmi a chiave pubblica a prova di quantum computing ma fino ad ora il loro utilizzo non è stato ritenuto necessario perché è stato più conveniente utilizzare algoritmi a chave pubblica quali RSA, DSA e ECDSA.

Gli algoritmi per una crittografia post quantistica

Il NIST nel suo rapporto sulla Post-Quantum Cryptography elenca i seguenti algoritmi:

Algoritmi Lattice-based
Per il calcolo utilizzano un reticolo di vettori e permettono sia la firma digitale che la cifratura a chiave pubblica. Un esempio di algoritmo è NTRU (1998) il cui brevetto è scaduto lo scorso anno per questo è diventato interessante.
Algoritmi Code-based
Sono basati su una tecnica di rilevazione degli errori nelle comunicazione che risale agli anni ’50, Per ora permettono solo la cifratura. Un esempio di algoritmo è McElience (1978) che è molto veloce ma ha una chiave di cifratura molto grande.
Algoritmi Multivariate polynomial
Sono basati sulla matematica dei polinomi multivariati e permettono solo la cifratura. Un esempio di algoritmo è HFE (1996)
Algoritmi Hash-based
Sono basati sull’algoritmo di hash e sulla costruzione di un albero di operazioni di hash. Permettono solo la firma digitale. Un esempio di algoritmo è Merkle (1979) che ha però dei problemi di lunghezza della chiave con l’aumento della dimensione dell’albero

Il loro uso a livello commerciale è ancora molto limitato ma iniziano a comparire le prime applicazioni pratiche.

Blockchain e algoritmo di Merkle

Quantum Resisten Ledger è un sistema di blockchain sviluppato da Peter Waterland, che utilizza per la firma digitale l’algoritmo di Merkle e può funzionare anche su sistemi di potenza limitata quali laptop o smartphone. Il progetto, iniziato nel 2016, è attualmente in fase di conclusione con la posibilità di fare tutte le operazioni classiche di una blockchain, smart contracts e criptovalute, in modo sicuro e a prova di quantum computer.

A livello di criptovalute esiste già IOTA, una moneta post quantistica che è anche una delle monete importanti sul mercato. Usa un sistema basato sui grafi e non ha costi per le transazioni.

I rischi del quantum computing non riguardano solo la tecnologia blockchain. L’avvento del quantum computer sta mettendo in discussione tutte le attività basate sugli algoritmi a chiave pubblica, che sono molte di più di quante noi oggi riusciamo ad immaginare e che riguardano praticamente tutto Internet come lo conosciamo oggi. Stay tuned.

_________________________________________________