Performances de la cryptographie post-quantique

J'ai déjà beaucoup écrit sur l'impact de la cryptographie post-quantique sur les performances réseau (liens ci-dessous). J'ai néanmoins pensé qu'il serait utile de rédiger un nouvel article pour résumer la situation actuelle, apporter des informations et références supplémentaires, et peut-être tirer quelques conclusions.

En bref, si les primitives post-quantiques comme ML-KEM et ML-DSA n'entraînent qu'un surcoût CPU raisonnable, la taille nettement plus importante de leurs clés publiques et de leurs signatures pose un vrai problème de charge utile pour les réseaux réels. Faire transiter ces volumes de données plus importants par les protocoles de transport provoque de la fragmentation, dépasse les fenêtres de congestion initiales standard et déclenche des allers-retours supplémentaires qui dégradent directement la vitesse de connexion.

Cet article fait partie d'une série. Vous n'avez pas besoin d'avoir lu tous les épisodes précédents, mais je vous recommande ces deux-là pour le contexte qu'ils apportent :

• Effet des algorithmes post-quantiques sur les performances réseau
• Pourquoi les signatures post-quantiques dépassent les limites du handshake TLS

Ces deux articles se concentrent sur la théorie, mais vous remarquerez qu'ils apportent peu de preuves concrètes. Que disent l'industrie et le monde académique ?

Chrome a été le premier navigateur à déployer X25519MLKEM768 (un nouvel établissement de clés hybride et résistant aux ordinateurs quantiques) ; il est donc logique de commencer par lui. Qu'observe-t-on en pratique ?

« Chrome a constaté une augmentation de 4 % de la latence du handshake TLS lors du déploiement de ML-KEM, qui occupe environ 1 Ko d'espace supplémentaire dans le ClientHello. La taille du ClientHello a ainsi dépassé l'unité de transmission maximale (MTU) standard des paquets sur Internet, soit environ 1 400 octets, ce qui a entraîné sa fragmentation sur deux paquets de la couche de transport sous-jacente (TCP ou UDP). »

— David Adrian, dans Post-quantum cryptography is too damn big

Sur le même sujet, Cloudflare a publié plusieurs articles intéressants consacrés à la cryptographie post-quantique. Plutôt que de chercher la meilleure ressource, voici un lien vers l'ensemble de la catégorie. Pour vous faire gagner du temps : leurs conclusions rejoignent celles de Google. Des charges utiles plus importantes entraînent de la fragmentation TCP, une probabilité accrue de perte de paquets et des retards de connexion mesurables sur les réseaux réels.

Lorsqu'on introduit de nouvelles charges utiles cryptographiques et extensions de protocole dans la nature, on se heurte directement à l'ossification des middleboxes : des équipements réseau et dispositifs d'inspection de sécurité qui interrompent les connexions simplement parce qu'ils rencontrent des structures ou des tailles de données pour lesquelles ils n'ont pas été programmés.

À mesure que Google, Cloudflare, Meta et AWS ont étendu le déploiement de l'accord de clés post-quantique, une série de problèmes opérationnels spécifiques est apparue :

• Défaillances des middleboxes et pare-feu : les équipements réseau et passerelles de sécurité abandonnent fréquemment les messages ClientHello fragmentés sur plusieurs paquets ou rejettent les extensions TLS inconnues. Les pare-feu Sophos utilisant les modes d'inspection de la protection web ont historiquement eu du mal à gérer les handshakes clients post-quantiques. Parallèlement, des utilisateurs d'AWS Network Firewall ont rencontré des bugs de correspondance de règles lors du traitement de handshakes PQC avec OpenSSL 3.5.1.
• Écarts lors des déploiements à grande échelle : dans le déploiement TLS réel de Meta (TLS-PQR), même des taux d'intolérance infimes se sont traduits par des millions de connexions utilisateurs affectées. De même, les déploiements PQC plus larges de Cloudflare (pqc-to-origin et post-quantique pour tous) ont montré que les chemins edge-vers-origine et client-vers-edge rencontrent des environnements de middleboxes très différents.
• Cas extrêmes de fragmentation : lorsque la MTU d'un chemin réseau descend sous les standards habituels, ou lorsque les handshakes UDP/QUIC atteignent des limites d'amplification strictes, les messages PQC volumineux déclenchent des boucles de pertes, un phénomène documenté en détail par des projets de recherche comme tldr.fail.

Les clients qui veulent communiquer avec des serveurs ne proposant ni X25519 ni X25519MLKEM768 devront émettre un HelloRetryRequest. À l'avenir, cela pourrait concerner les clients souhaitant utiliser un établissement de clés purement ML-KEM, imposant un aller-retour réseau supplémentaire chaque fois que le key share prédit par le client ne correspond pas aux capacités du serveur.

En attendant, nous observons des problèmes similaires avec les origines des CDN : si une origine ne prend pas en charge les méthodes d'échange de clés courantes, un aller-retour supplémentaire est nécessaire pour finaliser le handshake. Cloudflare dispose de données intéressantes, introuvables ailleurs, sur les préférences des origines en matière d'établissement de clés. Dans son étude Automatic Key Exchange for Origins, Cloudflare montre comment la négociation automatique et dynamique des préférences d'échange de clés évite les allers-retours HelloRetryRequest, si pénalisants pour les performances, entre les nœuds edge et les origines en amont.

Nous ne voyons pas encore ce problème, car les chaînes de certificats post-quantiques sont rares. Lorsqu'elles sont utilisées, c'est sur des réseaux privés (plus rapides) et par des clients qui maîtrisent davantage leurs paramètres réseau et peuvent optimiser leurs piles TCP.

La recherche académique donne cependant un aperçu clair de ce qui pourrait se passer lorsque l'authentification post-quantique atteindra la Web PKI publique :

• Chaînes de certificats et débit des handshakes : une étude de performance approfondie de Sikeridis et al. (NDSS 2020) a évalué les candidats de signature PQC du NIST au sein de chaînes de certificats TLS 1.3. Elle a montré qu'utiliser un seul schéma de signature PQC volumineux sur toute la chaîne dégrade fortement le débit et la latence du serveur. Pour y remédier, les auteurs ont proposé des chaînes de certificats mixtes (combinant des algorithmes rapides mais plus volumineux comme Falcon avec des algorithmes plus compacts mais plus lents comme Dilithium ou SPHINCS+), qui accélèrent nettement les handshakes et rétablissent les taux de connexion.
• Latence réseau vs goulets d'étranglement CPU : Benchmarking post-quantum cryptography in TLS, de Paquin, Stebila et Tam (Microsoft Research), a démontré à l'aide d'un framework d'émulation réseau que le temps de calcul CPU est rarement le principal goulet d'étranglement du TLS post-quantique. Ce sont plutôt la latence réseau et la perte de paquets qui dominent le temps total de chargement des pages, en raison de la taille même des clés publiques et des chiffrés post-quantiques.
• TTFB et TTLB en conditions réseau réelles : les travaux de Kampanakis et Childs-Klein (MADWeb 2024) ont évalué l'ensemble du cycle de vie de la connexion, le Time-To-First-Byte (TTFB) et le Time-To-Last-Byte (TTLB). Ils ont constaté que si les chaînes de certificats PQC volumineuses augmentent la latence initiale du handshake de 20 à 30 % sur des liaisons saines, leur impact relatif est largement amorti lors du transfert de grandes quantités de données ou sur des connexions déjà dégradées ou sujettes aux pertes.
• Microbenchmarks en boîte blanche et en boîte noire : Sosnowski et al. (ACM CoNEXT '23) ont montré que si l'échange de clés à base de réseaux euclidiens s'exécute plus rapidement que les algorithmes classiques côté CPU, la taille accrue des clés et des chaînes de certificats augmente la latence au niveau réseau sur les chemins sujets aux pertes.

Lorsqu'on quitte les navigateurs de bureau et les puissants serveurs edge pour les modules de sécurité matériels (HSM), les microcontrôleurs IoT et les systèmes embarqués, l'empreinte mémoire importante et la taille des paquets de la PQC imposent de sévères contraintes physiques.

Les protocoles IoT standard (comme CoAP, DTLS et EDHOC) fonctionnent sur des réseaux sans fil basse consommation sujets aux pertes, où les tampons de paquets se mesurent en kilo-octets. Stocker et réassembler des clés publiques ou des signatures PQC de plusieurs kilo-octets mène rapidement à l'épuisement des tampons, à des boucles de pertes de fragments et à une forte consommation de batterie. En outre, les HSM et les cartes à puce sont confrontés à des limites strictes de stockage non volatil et à une bande passante de bus interne restreinte lorsqu'ils gèrent du matériel de clés PQC et traitent de lourdes signatures de firmware OTA (Over-The-Air).

L'IETF développe activement des solutions techniques pour adapter les environnements contraints aux exigences post-quantiques :

• RFC 9958: Post-Quantum Cryptography for Engineers : publié par le groupe de travail PQUIP, ce document présente des recommandations opérationnelles, les compromis de performance et des critères de sélection des algorithmes pour les piles réseau contraintes.
• draft-ietf-pquip-pqc-hsm-constrained : traite des limites des ressources matérielles et détaille comment les contraintes d'état, de RAM et de NVRAM dans les HSM, les cartes à puce et les microcontrôleurs embarqués affectent le stockage des clés PQC, les temps de traitement et les mises à jour de firmware.
• draft-rfcxml-pqc-key-fragmentation : analyse les risques de réassemblage au niveau réseau et formule des recommandations pour éviter l'épuisement des tampons et les boucles de pertes de paquets lors de la transmission de clés PQC fragmentées sur des réseaux sans fil basse consommation (CoAP, DTLS, EDHOC, OSCORE).
• Signatures compactes et à état : des recommandations pour adopter des schémas de signature à base de hachage avec état (comme LMS et XMSS, définis dans les RFC 8554 / RFC 8708) afin que le code et le coût de vérification des signatures restent assez légers pour les bootloaders embarqués.

Les problèmes ne manquent pas, mais la puissance de calcul n'en fait pas partie. Les algorithmes PQC modernes à base de réseaux euclidiens, en particulier ML-KEM et ML-DSA, sont rapides à calculer. Sur les processeurs x86 et ARM modernes, la génération de clés, l'encapsulation et la décapsulation à base de réseaux euclidiens nécessitent souvent moins de cycles CPU que les échanges ECDH ou RSA traditionnels. Heureusement, c'est au moins un point dont nous n'avons pas à nous soucier, sauf si nous décidons un jour de passer à d'autres algorithmes.

Malgré ces obstacles structurels, plusieurs benchmarks empiriques soutiennent que le TLS post-quantique ne fera pas tomber Internet, et qu'il pourrait même améliorer les performances là où on s'y attend le moins :

• La supériorité de calcul compense les octets : Sosnowski et al. (ACM CoNEXT '23) ont démontré que, comme les primitives à base de réseaux euclidiens (ML-KEM) nécessitent beaucoup moins de cycles CPU que les courbes classiques à haut niveau de sécurité ou RSA, le débit global des serveurs peut en réalité augmenter dans des conditions réseau normales.
• Les microcontrôleurs peuvent être plus rapides avec la PQC : Gillot, Buchanan et Turino (arXiv:2610.27766) ont directement remis en cause l'idée que le matériel IoT allait céder sous le poids des charges utiles PQC. En testant des dizaines de configurations TLS 1.3 sur des microcontrôleurs contraints (comme le Raspberry Pi Pico W), ils ont constaté que les opérations mathématiques peu gourmandes en cycles de ML-KEM permettaient aux handshakes TLS post-quantiques de se terminer nettement plus vite (jusqu'à ~41 % plus rapidement dans les benchmarks) que les handshakes classiques, prouvant que les appareils embarqués peuvent exécuter sans difficulté un échange de clés résistant au quantique.
• Amortissement de la charge utile dans le trafic réel : les travaux de Kampanakis et Childs-Klein (MADWeb '24) soulignent que si la latence du handshake PQC augmente prise isolément, elle devient statistiquement négligeable lorsqu'on l'évalue au regard du Time-to-Last-Byte (TTLB) réel et de charges utiles HTTP typiques (>40 Ko).
• Des correctifs d'architecture comme KEMTLS : les travaux de Schwabe, Stebila et Wiggers (ACM CCS '20) prouvent que l'authentification ne nécessite pas forcément des signatures de plusieurs kilo-octets : remplacer les signatures du handshake par des KEM (AuthKEM) maintient le volume du handshake bien en deçà des limites standard de la fenêtre TCP.