Bitcoin, la menace quantique se rapproche

La menace quantique n’est pas pour demain matin, mais les récentes percées suggèrent que la communauté Bitcoina bien fait de lancer les grandes manœuvres.

La menace Google

Nous nous demandions en avril s’il fallait effacer les bitcoins de Satoshi Nakamoto avant l’arrivée de l’ordinateur quantique. Les chercheurs de Google nous redonnent l’occasion de creuser un peu plus le sujet en raison d’une avancée majeure dans le domaine de la factorisation quantique.

Casser les cryptographies classiques s’annonce bien plus facile qu’anticipé. Les ressources nécessaires pour casser le chiffrement RSA-2048 viennent d’être réduites par 20. Ce bond en avant est le résultat d’une optimisation de l’algorithme de Shor et d’une meilleure correction des erreurs liées à la décohérence quantique.

Il faut à présent un million de qubits pour casser RSA-2048, contre 20 millions de qubits auparavant. Cela dit, le plus grand processeur quantique ne possède actuellement que 1021 qubits (le Condor d’IBM). En sachant que la difficulté à maintenir la cohérence quantique augmente exponentiellement avec le nombre de qubits.

Par ailleurs, l’ordinateur quantique n’arrive toujours pas à factoriser un nombre aussi petit de 35. Donc, jusqu’à preuve du contraire, nous n’avons enregistré aucun progrès tangible malgré toutes les grandes annonces concernant l’augmentation du nombre de qubits et l’amélioration de la correction des erreurs.

Quoi qu’il en soit, il y a tout de même matière à réflexion. D’autant plus que des firmes comme Apple et Microsoft comptent adopter la cryptographie post-quantique dès cet automne.

Voici pour les curieux l’historique des percées scientifiques qui ont mené à l’ordinateur quantique :

Le Bitcoin menacé ?

La percée de Google concerne l’algorithme de Shor qui, allié à l’ordinateur quantique, peut résoudre le problème du logarithme discret exponentiellement plus rapidement qu’avec les ordinateurs classiques. En clair, il est possible d’obtenir une clé privée à partir d’une clé publique Bitcoin.

Mais bien que cet algorithme puisse résoudre efficacement à la fois le problème de factorisation (affectant RSA) et le problème du logarithme discret (affectant ECDSA / Bitcoin), le Bitcoin et sa courbe elliptique « secp256k1 » ne sont pas directement impactés par la récente avancée de Google.

Le fondateur de Pauli Group prévient toutefois que ECDSA est généralement plus facile à casser que RSA, et qu’il n’est pas impossible que l’IA parvienne à optimiser l’algorithme de Shor pour casser plus facilement ECDSA (Bitcoin).

Soit dit en passant (et c’est important), notez que le simple fait de doubler la longueur de la clé publique (par exemple, en utilisant une courbe elliptique « secp512k1 ») ne fait que rendre la dérivation de la clé privée deux fois plus difficile via l’algorithme de Shor. La protection serait donc insuffisante.

D’après le constructeur d’ordinateur quantique IonQ, la courbe elliptique « secp32k1 » pourrait être cassée en 2027. C’est 2029 pour la « secp256k1 » (Bitcoin). Ces prévisions sont toutefois à prendre avec de grosses pincettes.

Heureusement, le NIST planche sur la standardisation d’algorithmes de cryptographie post-quantique. Trois candidats ont le vent en poupe pour les signatures numériques : CRYSTALS-Dilithium, SPHINCS+ et FALCON. Ces algorithmes pourraient théoriquement remplacer ECDSA.

Mais ce ne sera pas « gratuit ». Les signatures et les clés sont beaucoup plus volumineuses, ce qui réduira forcément le débit de transactions onchain. Créer et vérifier les signatures prend aussi bien plus de temps.

Par exemple, pour CRYSTAL-Dilithium Level I, une clé publique représente 1 312 octets et une signature 2 420 octets, soit largement plus que les signatures ECDSA (72 bytes) ou Schnorr (64 bytes) actuelles.

[Le niveau de sécurité Level I du NIST offre une sécurité équivalente à des clés de 128 bits, et le Level V une sécurité de 256 bits]

En somme, la parade existe déjà, mais encore faut-il choisir l’algorithme qui va bien. Et que chacun migre manuellement vers des adresses post-quantique.

BIP-360 : Pay to Quantum Resistant Hash (P2QRH)

BIP-360, proposé par Hunter Beast, est un « premier pas pragmatique » (soft fork) en introduisant un nouveau type d’UTXO appelé « Pay to Quantum Resistant Hash » (P2QRH) dont les adresses commenceraient par « bc1r ».

Explication :

Actuellement, une transaction Bitcoin (destruction et création simultanée d’UTXO) s’opère en révélant une clé publique ainsi qu’une signature reposant sur l’algorithme ECDSA.

BIP-360 propose que les transactions comportent à la fois des signatures ECDSA et des signatures post-quantiques, à la manière des transactions multi-sig. Ce mix permet d’avoir la solution de secours ECDSA si une faille est découverte dans l’algorithme post-quantique choisi.

Hunter Beast plaide pour l’algorithme FALCON qui a l’avantage de permettre l’agrégation de signatures. Son premier candidat (SQIsign) a finalement été abandonné à cause de sa lenteur.

Comme dit plus haut, il y a un prix à payer. Les clés publiques et signatures post-quantiques sont beaucoup plus volumineuses qu’une signature Schnorr de 64 bytes.

Les signatures SLH-DSA (SPHINCS+) peuvent atteindre 29 000 bytes, voire plus (ou moins) selon les paramètres choisis. Soit environ 40 fois moins de transactions par bloc ! Les signatures FALCON sont 20 fois plus grandes que les signatures Schnorr et 13 fois fois plus grandes que les signatures ECDSA.

D’autres propositions sont sur la table. En voici une liste :

Notons par exemple le BIP « Quantum-Resistant Address Migration Protocol » (QRAMP) proposé par Agustin Cruz. Ce BIP prévoit plutôt un hard fork. Dit autrement, les bitcoins qui ne migreraient pas vers des adresses post-quantiques seraient perdus à jamais.

Deloitte estimait en 2020 que 25 % des bitcoins sont liés à de vieux types d’adresse vulnérables aux attaques quantiques.

Comment protéger ses bitcoins ?

De nos jours, les « clés publiques » ne sont plus vraiment publiques. Elles sont encodées en passant à la moulinette des fonctions de hachage résistantes à l’ordinateur quantique SHA-256 et RIPEMD-160. Le hash résultant est ce que l’on appelle une « adresse Bitcoin ».

Néanmoins, les clés publiques doivent être révélées au moment des transactions. Elles sont donc vulnérables tout le temps qu’elles passent dans le mempool en attendant qu’un mineur l’ajoute dans un bloc.

La menace s’arrête dès que le bloc se propage. À moins que vous fassiez l’erreur de renvoyer des fonds vers la même adresse.

Voici le résumé d’une transaction pour bien comprendre :

Votre wallet contient un UTXO de 1 BTC. Cet UTXO est public et contient plusieurs informations comme le montant (1 BTC) et un script de verrouillage de type P2PKH (Pay-to-Public-Key-Hash).

Maintenant, imaginons que vous réalisiez un paiement de 0.5 BTC. Vous apportez votre clé publique et une signature pour déverrouiller le script afin de réaliser la transaction.

Vu que votre UTXO fait 1 BTC, voici ce qui se que génère la transaction :

-0,5 BTC vers l’adresse du destinataire.
-0.0001 BTC vers l’adresse du mineur (frais de transaction).
-0,4999 BTC renvoyé à une NOUVELLE adresse de change générée par votre wallet.

Chacune de ces trois transactions crée un nouvel UTXO. Le change de 0.4999 BTC étant lié à une nouvelle adresse Bitcoin (une nouvelle clé publique), il n’est plus vulnérable.

En revanche, il ne faut surtout pas virer de nouveaux fonds vers l’adresse originale qui contenait 1 BTC puisqu’elle est désormais connue de tous.

Voici un autre article sur la menace quantique : Bitcoin et la menace quantique.