La crypto devrait-elle craindre l'informatique quantique ?

Choses à savoir:

– L'informatique quantique, une technologie de pointe, recèle un immense potentiel pour révolutionner le calcul grâce à sa puissance de calcul inégalée. – L'informatique quantique, bien qu'elle soit à au moins plusieurs années d'une percée majeure, est perçue comme une menace importante pour la cryptographie en raison de ses immenses capacités de traitement des données. – L'impact potentiel de l'informatique quantique sur la cryptographie et les systèmes sécurisés tels que la preuve de travail de Bitcoin doit être soigneusement examiné. En tant que passerelle la plus sécurisée au monde vers la cryptographie, ces questions fondamentales méritent toute l'attention de Ledger.

Informatique quantique : le prochain saut technologique

Les ordinateurs que nous utilisons quotidiennement traitent les informations sur la base de « bits ». Un bit ne peut contenir qu'une des valeurs suivantes : 0 ou 1, et peut être enchaîné pour créer un morceau de code binaire. Aujourd'hui, tout ce que nous faisons avec un ordinateur, de l'envoi d'e-mails et du visionnage de vidéos au partage de musique, est possible grâce à ces chaînes de chiffres binaires. 

La nature binaire des ordinateurs traditionnels impose des limites à leur puissance de calcul. Ces ordinateurs n'exécutent les opérations qu'une étape à la fois et ont du mal à simuler avec précision les problèmes du monde réel. En revanche, le monde physique fonctionne sur la base d'amplitudes plutôt que de chiffres binaires, ce qui le rend beaucoup plus complexe. C'est là que les ordinateurs quantiques entrent en jeu.

En 1981, Richard Feynman a déclaré que "la nature n'est pas classique, et si vous voulez faire une simulation de la nature, vous feriez mieux d'en faire une mécanique quantique". Au lieu de manipuler des bits, l'informatique quantique utilise des "bits quantiques", ou qubits, ce qui lui permet de traiter les données de manière beaucoup plus efficace. Les qubits peuvent être zéro, un et, surtout, une combinaison de zéro et un.

L'informatique quantique se situe au carrefour de la physique et de l'informatique. Pour mettre les choses en perspective, un ordinateur quantique de 500 qubits nécessiterait plus de bits classiques que… le nombre d'atomes dans l'univers entier.

Quantum est-il une menace pour la cryptographie ?

La cryptographie à clé publique, également appelée cryptographie asymétrique, constitue le fondement de la sécurité des cryptomonnaies. Il s'agit d'une combinaison d'une clé publique (accessible à tous) et d'une clé privée. Les capacités de calcul rapides des qubits augmentent le potentiel de rupture du cryptage et de perturbation de la sécurité de l'industrie de la crypto-monnaie si l'informatique quantique continue de progresser.

Deux algorithmes doivent être étroitement considérés : celui de Shor et celui de Grover. Les deux algorithmes sont théoriques car il n'existe actuellement aucune machine pour les implémenter, mais comme vous le verrez, l'implémentation potentielle de ces algorithmes pourrait nuire à la cryptographie.

D'une part, l'algorithme quantique de Shor (1994), du nom de Peter Shor, permet de factoriser de grands entiers ou de résoudre le problème du logarithme discret en temps polynomial. Cet algorithme pourrait casser la cryptographie à clé publique avec un ordinateur quantique suffisamment puissant. L'algorithme de Shor briserait la grande majorité de la cryptographie asymétrique utilisée aujourd'hui puisqu'il est basé sur RSA (reposant sur le problème de la factorisation d'entiers) et sur la cryptographie à courbe elliptique (selon le problème du logarithme discret dans un groupe de courbes elliptiques). 

D'autre part, l'algorithme de Grover (1996) est un algorithme de recherche quantique conçu par Lov Grover en 1996, qui peut être utilisé pour résoudre des problèmes de recherche non structurée. L'algorithme Grover met une brèche significative dans la sécurité des primitives symétriques mais n'est pas insurmontable. Il est généralement conseillé de doubler la longueur de la clé pour compenser la complexité racine carrée de cette rupture. L'utilisation d'AES256 au lieu d'AES128 est considérée comme suffisante, mais il convient de noter que cette règle empirique peut n'être valable que parfois pour tous les chiffrements[5]. Quant aux fonctions de hachage, qui font partie du paysage des primitives symétriques, on pense qu'elles n'ont pas d'impact sur la résistance aux collisions. Cependant, les chercheurs ont trouvé des cas du problème où c'est faux[6] (recherche de préimage multi-cibles, par exemple).

Essentiellement, les deux algorithmes présentent des dangers potentiels pour la cryptographie. L'algorithme de Shor simplifie le processus de factorisation des grands nombres, ce qui facilite la découverte d'une clé privée connectée à une clé publique, et l'algorithme de Grover est capable de compromettre le hachage cryptographique plus efficacement que les ordinateurs actuels.

Quand les ordinateurs quantiques cassant le cryptage émergeront-ils ?

Passons en revue certaines des dernières expériences et voyons à quelle vitesse la recherche avance. Le premier véritable ordinateur quantique reste loin, mais cela n'empêche pas une course mondiale d'atteindre la "suprématie quantique". Pour Ayal Itzkovitz, associé directeur d'un fonds de capital-risque axé sur le quantique, "s'il y a trois ans, nous ne savions pas s'il était tout à fait possible de construire un tel ordinateur, maintenant nous savons déjà qu'il y aura des ordinateurs quantiques capables de faire quelque chose de différent des ordinateurs classiques. 

Un événement dont tout le monde a probablement entendu parler était «l'expérience de suprématie quantique» de Google en 2019 utilisant un appareil à 54 qubits. En 2021, le Université des sciences et de la technologie de Chine résolu un calcul plus complexe en utilisant 56 qubits, atteignant 60 qubits plus tard. Son objectif était d'effectuer un calcul n'impliquant pas l'algorithme de Shor qui démontrerait également une accélération quantique par rapport au calcul classique.

Par définition, ces expériences ne montrent pas de progrès vers la rupture de la cryptographie car elles ont été conçues pour éviter la taille et la complexité de la factorisation d'entiers quantiques. Cependant, ils montrent que construire plus de qubits dans un ordinateur quantique n'est plus difficile, avec différentes solutions matérielles disponibles, Les qubits de la puce "Sycamore" de Google sont fondamentalement différents des photons de l'USTC. La prochaine étape vitale pour accéder à un ordinateur cassant le cryptage est généralement considérée comme la construction d'un calcul tolérant aux pannes et de qubits de correction d'erreurs. 

Statut du développement de l'ordinateur quantique de BSI [1] montre à quel point les ordinateurs quantiques actuels sont loin de casser un logarithme discret de 160 bits (ligne bleue la plus basse dans l'image suivante). L'abscisse montre comment la réduction du taux d'erreur grâce à des améliorations matérielles pures ou à l'informatique tolérante aux pannes permet d'atteindre de tels niveaux de calcul sans augmenter considérablement le nombre de qubits disponibles (axe y).

Implémenter l'algorithme de Shor de manière scalable nécessite un calcul tolérant aux pannes sur quelques milliers de qubits logiques : 2124 qubits au minimum afin de casser une courbe elliptique de 256 bits comme le secp256k1 de bitcoin, De Circuits quantiques améliorés pour les logarithmes discrets de courbe elliptique[7]. Un qubit « logique » dans un tel système est composé de plusieurs qubits conçus pour fonctionner comme une version corrigée des erreurs d'un seul qubit.

Un millier de qubits logiques se traduisent approximativement par plusieurs millions de qubits, couvrant la taille d'un terrain de football. Une démonstration pratique d'un tel calcul tolérant aux fautes a été récemment faite dans Contrôle tolérant aux pannes d'un qubit corrigé d'erreurs[2], où un seul qubit logique dont la probabilité d'erreur est inférieure à celle des qubits qui le composent. On s'attend à ce que l'amélioration de ce domaine suive rapidement car il deviendra le centre d'intérêt. 

Les progrès dans cette direction se traduiront directement par une menace concrète pour la cryptographie à clé publique. Enfin, une autre possibilité de progrès rapides peut provenir d'améliorations purement algorithmiques ou de découvertes uniquement matérielles. Statut du développement de l'ordinateur quantique de BSI[1] explique : « Il peut y avoir des découvertes perturbatrices qui changeraient radicalement [l'état actuel des connaissances], les principales étant des algorithmes cryptographiques qui peuvent être exécutés sur des machines sans correction d'erreur à court terme ou des percées spectaculaires dans le taux d'erreur. de certaines plateformes. En d'autres termes, ce n'est pas seulement un problème de pouvoir construire de gros ordinateurs avec beaucoup de qubits (en fait, construire plus de qubits de manière fiable n'est pas l'objectif principal, l'informatique tolérante aux pannes l'est), mais aussi un problème algorithmique et éventuellement une recherche matérielle un.

Au moment où nous écrivions cet article, IBM a publié ses résultats sur une puce de 127 qubits avec un taux d'erreur de 0.001 et prévoit de publier une puce de 433 qubits l'année prochaine et une puce de 1121 qubits en 2023. 

Dans l'ensemble, il reste difficile de prédire à quelle vitesse un ordinateur quantique prendra vie. Néanmoins, nous pouvons nous fier à l'avis d'experts en la matière : Un cadre d'estimation des ressources pour les attaques quantiques contre les fonctions cryptographiques - Développements récents[3] et Sondage d'experts sur le risque quantique[4] montrent que de nombreux experts s'accordent à dire que dans 15 à 20 ans, nous devrions disposer d'un ordinateur quantique.

Citant Un cadre d'estimation des ressources pour les attaques quantiques contre les fonctions cryptographiques - Développements récents [3] en résumé :

« Les schémas de clé publique actuellement déployés, tels que RSA et ECC, sont complètement cassés par l'algorithme de Shor. En revanche, les paramètres de sécurité des méthodes symétriques et des fonctions de hachage sont réduits d'au plus un facteur deux par les attaques connues - par des recherches par «force brute» utilisant l'algorithme de recherche de Grover. Tous ces algorithmes nécessitent des machines quantiques à grande échelle et tolérantes aux pannes, qui ne sont pas encore disponibles. La plupart des experts s'accordent à dire qu'ils deviendront probablement une réalité d'ici 10 à 20 ans.

Maintenant que nous avons examiné pourquoi les algorithmes quantiques pourraient nuire à la cryptographie, analysons les risques substantiels impliqués pour les domaines crypto et Web3. 

Quantum : Quels risques pour les crypto-monnaies ?

L'affaire Bitcoin :

Commençons par l'analyse de Pieter Wuille du problème du Bitcoin, parfois considéré comme "quantum-safe" en raison des adresses étant hashes des clés publiques et donc de ne pas les exposer.

Ne pas pouvoir casser une clé privée Bitcoin en se basant sur l'hypothèse que les hachages la rendent impossible repose également sur le fait de ne jamais divulguer sa clé publique, quel que soit le moyen, ce qui est déjà faux pour de nombreux comptes.

Se référant à un autre fil, Pieter Wuille donne une idée de l'impact du vol des ~37% des fonds exposés (à l'époque). Le bitcoin serait probablement tanké, et même non exposé, tout le monde y perdrait également.

Le point crucial ici est la mention que les progrès vers la construction d'un ordinateur quantique seront incrémental: des milliards de dollars sont investis publiquement dans ce domaine et toute amélioration résonne dans le monde entier, comme l'a montré l'expérience de suprématie quantique de Google.

Cela signifie que se retrouver avec des fonds à risque prendra du temps et que des solutions alternatives peuvent être correctement définies. On peut imaginer mettre en place un fork de la chaîne en utilisant des algorithmes cryptographiques post-quantiques pour signer et permettre aux gens de transférer leurs fonds vers cette nouvelle chaîne depuis l'ancienne fois que la nouvelle d'un ordinateur quantique raisonnablement costaud semble imminente.

L'affaire Ethereum :

Le cas d'Ethereum est intéressant car ETH 2.0 inclut un plan de secours en cas de panne catastrophique dans EIP-2333.

En cas de rupture des signatures BLS d'ETH2, ce qui se produirait en même temps que l'ECDSA puisqu'elles sont toutes deux également vulnérables face à l'algorithme de Shor, un hard fork de la blockchain sera exécuté avant que l'algorithme ne soit suspecté d'être compromis. Ensuite, les utilisateurs révèlent une préimage de leur clé que seuls les propriétaires légitimes peuvent posséder. Cela exclut les clés récupérées en cassant une signature BLS. Avec cette préimage, ils signent une transaction spécifique leur permettant de passer au hard fork et d'utiliser de nouveaux algorithmes post-quantiques.

Ce n'est pas encore un passage à une chaîne post-quantique, mais cela fournit une issue de secours. Quelques informations supplémentaires ici.

Signatures post-quantiques :

Certaines choses pourraient être améliorées concernant le passage à un schéma de signature post-quantique à utiliser dans une crypto-monnaie. Les finalistes actuels du NIST ont des besoins en mémoire assez importants. Lorsque la taille de la signature n'est pas déraisonnablement supérieure à celle d'un ECDSA, la taille de la clé publique augmente la taille des blocs et les frais associés.  

Nom du candidat	Taille
Rainbow	58.3 kB
Dilithium	3.5 kB
Falcon	1.5 kB
GeMSS	352 kB
pique-nique	12 kB
SPHINCS +	7 kB

L'algorithme Falcon a été conçu pour minimiser la taille de la clé publique et de la signature. Cependant, ses 1563 octets sont encore loin des 65 octets qu'ECDSA atteint actuellement.

Les techniques cryptographiques peuvent réduire la taille des blocs, comme l'agrégation de plusieurs signatures ensemble. Ce [schéma multisignature](https://eprint.iacr.org/2020/520) pour la signature GeMSS fait exactement cela et réduit le coût de stockage par signature à quelque chose d'acceptable, malgré les frais uniques importants d'une signature GeMSS .

Menaces pour le matériel cryptographique :

La taille des signatures a également un impact sur les portefeuilles matériels où la mémoire est très limitée : un Ledger Nano S dispose de 320 Ko de mémoire Flash disponibles et de seulement 10 Ko de RAM. Si du coup on avait besoin d'utiliser des signatures Rainbow, générer la clé publique de manière native ne serait pas faisable.

Cependant, étant donné que l'ensemble de la communauté cryptographique est touchée par le problème, y compris les secteurs bancaire, des télécommunications et de l'identité, qui constituent l'essentiel du marché des puces sécurisées, nous nous attendons à ce que le matériel s'adapte rapidement au besoin d'algorithmes post-quantiques. matériel convivial et supprimez cette mémoire (ou parfois ces performances) à temps.

Les conséquences de ces ruptures sont la chute du système bancaire actuel, des télécommunications et des systèmes d'identité tels que les passeports. Que faire face à un futur aussi apocalyptique ? N'ayez pas peur, ou un peu, car les cryptographes l'ont couvert.

Y a-t-il un remède, docteur ?

Alors que nos ordinateurs actuels auraient besoin de milliers d'années pour casser la cryptographie à clé publique, des ordinateurs quantiques entièrement développés le feraient en quelques minutes ou heures. Des normes de « sécurité quantique » seront inévitablement nécessaires pour contrer cette menace et assurer la sécurité de nos futures transactions financières et communications en ligne.

Des travaux sont déjà en cours concernant ce que l'on appelle communément la « cryptographie post-quantique » qui serait peut-être être "compatible avec les ordinateurs d'aujourd'hui mais qui sera également capable de résister aux attaquants des ordinateurs quantiques à l'avenir." La cryptographie post-quantique fait passer les algorithmes et les normes mathématiques au niveau supérieur tout en permettant la compatibilité avec les ordinateurs actuels.

Le Concours NIST créé juste pour l'occasion a déjà atteint son troisième tour et produit une liste de candidats potentiels à la normalisation. Le Conférence sur la sécurité post-quantique a été lancé dès 2006 pour étudier les primitives cryptographiques qui résisteraient aux attaques quantiques connues.

Les fondements de cette recherche découlent d'avertissements d'experts selon lesquels les données cryptées risquent déjà d'être compromises, car les premiers ordinateurs quantiques pratiques devraient apparaître dans les 15 prochaines années.
Ce type d'attaque est connu sous le nom de "thésauriser les données maintenant, attaquer plus tard", où une grande organisation stocke des informations cryptées d'autres parties qu'elle souhaite briser et attend qu'un ordinateur quantique suffisamment puissant lui permette de le faire. C'est le même souci de cet article par exemple, "Les États-Unis craignent que les pirates ne volent des données aujourd'hui afin que les ordinateurs quantiques puissent les casser dans une décennie», mais cela ne dit pas ce que les acteurs au niveau de l'État pourraient faire dans la même veine. Ils ont beaucoup plus de ressources et de stockage disponibles.

Réflexions de clôture

La vitesse exacte à laquelle les communications cryptées deviendront vulnérables à la recherche quantique reste difficile à déterminer.

Une chose est sûre : bien que des progrès significatifs soient réalisés en informatique quantique, nous sommes encore loin de posséder la capacité de cracker la cryptographie avec ces machines. La probabilité d'une percée soudaine résultant de la conception d'un tel ordinateur est minime, ce qui nous laisse le temps de nous préparer à son arrivée. Si cela devait se produire du jour au lendemain, les ramifications seraient désastreuses, affectant non seulement les crypto-monnaies, mais un large éventail de secteurs. 

Heureusement, des solutions, y compris la cryptographie post-quantique, sont disponibles pour faire face à la menace, mais l'industrie de la cryptographie n'a pas encore vu l'urgence d'investir dans ces mesures. 

Le marché de la crypto-monnaie doit surveiller de près les développements quantiques. En ce qui concerne le matériel, il n'y a pas lieu de s'inquiéter car nous anticipons le développement de nouveaux éléments sécurisés pour répondre à la demande. Il est crucial de se tenir au courant des dernières avancées en matière de versions à canal latéral et résistantes aux pannes de ces algorithmes, afin de fournir une implémentation fiable à nos utilisateurs.

Bibliographie:

[1]: Statut du développement de l'ordinateur quantique de BSI

[2]: Contrôle tolérant aux pannes d'un qubit corrigé d'erreurs

[3]: Un cadre d'estimation des ressources pour les attaques quantiques contre les fonctions cryptographiques - Développements récents

[4]: Sondage d'experts sur le risque quantique

[5]: Au-delà des accélérations quadratiques dans les attaques quantiques sur les schémas symétriques

[6]: Un algorithme efficace de recherche de collision quantique et ses implications sur la cryptographie symétrique

[7]: Circuits quantiques améliorés pour les logarithmes discrets de courbe elliptique

• Contenu propulsé par le référencement et distribution de relations publiques. Soyez amplifié aujourd'hui.
• Platoblockchain. Intelligence métaverse Web3. Connaissance Amplifiée. Accéder ici.
• La source: https://www.ledger.com/blog/should-crypto-fear-quantum-computing