filippo.io/mlkem768 : une cryptographie résistante au quantique pour l’écosystème Go

 (words.filippo.io)
1 points par GN⁺ 2024-02-02 | 1 commentaires | Partager sur WhatsApp
  • filippo.io/mlkem768 implémente en Go pur ML-KEM-768, en cours de standardisation par le NIST, afin de permettre l’évaluation d’un échange de clés résistant au quantique dans l’écosystème Go
  • Le projet se compose d’environ 500 lignes de code, 200 lignes de commentaires et 650 lignes de tests, sans dépendance autre que golang.org/x/crypto/sha3, ce qui facilite son intégration comme package interne dans la bibliothèque standard de Go
  • Au lieu de porter l’implémentation de référence pq-crystals, le code a été écrit directement à partir de la spécification FIPS 203, afin de vérifier si une implémentation interopérable peut être produite à partir de la seule spécification
  • Les zones les plus délicates sont la compression/décompression et les opérations en temps constant ; l’utilisation de la réduction de Barrett évite le risque d’instructions DIV à temps variable que l’on pouvait rencontrer dans la famille des implémentations de référence
  • L’optimisation des performances n’était pas l’objectif principal, mais le chemin Bob est comparable à X25519·P-256 de Go, et le chemin Alice reste sous un facteur 2, ce qui donne une vitesse exploitable en pratique même avec une implémentation simple

Implémentation ML-KEM-768 en Go pur

  • filippo.io/mlkem768 est une implémentation en Go pur de ML-KEM-768, qui privilégie la justesse et la lisibilité
  • ML-KEM, auparavant connu sous le nom de Kyber, est un mécanisme d’échange de clés résistant au quantique en cours de standardisation par le NIST
  • Le package se compose d’environ 500 lignes de code, 200 lignes de commentaires et 650 lignes de tests
  • Sa seule dépendance est golang.org/x/crypto/sha3
  • L’objectif est de l’intégrer en amont dans la bibliothèque standard de Go ; au départ, il est prévu comme package interne réservé à une expérimentation crypto/tls en opt-in

Une implémentation fidèle à FIPS 203

  • Cette implémentation n’est pas un portage de la bibliothèque de référence pq-crystals ; elle a été écrite depuis zéro sans lecture approfondie d’autres bases de code
  • L’objectif principal était de vérifier s’il est possible de produire une implémentation interopérable à partir de la seule spécification
  • Le document FIPS 203 fournit un pseudocode détaillé, des définitions complètes et des informations de type cohérentes, ce qui en fait un bon guide d’implémentation
  • Les noms de fonctions, de variables et l’ordre des opérations reflètent autant que possible la spécification FIPS afin de faciliter la revue et l’apprentissage
  • Les bases mathématiques nécessaires à l’implémentation de ML-KEM sont présentées séparément dans Enough Polynomials and Linear Algebra to Implement Kyber

Compression, décompression et implémentation en temps constant

  • Trois tâches d’implémentation essentielles restaient à résoudre
    • l’implémentation de l’arithmétique modulaire sur le nombre premier 3329
    • l’implémentation des fonctions de compression/décompression qui mappent les valeurs de [0, 3329) vers [0, 2ᵈ) puis inversement
    • la garantie d’opérations en temps constant
  • L’arithmétique modulaire a été relativement simple grâce à l’expérience accumulée sur RSA et les courbes elliptiques, et le petit nombre premier simplifie l’implémentation
  • La compression et la décompression ont constitué la partie la plus difficile
    • la spécification les définit de manière abstraite à l’aide de fractions et de règles d’arrondi
    • l’implémentation réelle doit les traiter avec de l’arithmétique en temps constant et des opérations sur les bits
  • L’implémentation de référence et nombre de ses portages utilisaient des divisions susceptibles de devenir des instructions DIV à temps variable selon les optimisations du compilateur et la plateforme
  • Ce package utilise dès le départ la réduction de Barrett, et n’est donc pas concerné ; BoringSSL emploie la même approche

Pourquoi cibler uniquement ML-KEM-768

  • L’implémentation ne cible que ML-KEM-768 parmi les trois niveaux de sécurité de ML-KEM : -512, -768 et -1024
  • L’équipe Kyber recommande -768 plutôt que -512, afin de disposer d’une marge de sécurité plus conservatrice face aux nouvelles avancées en cryptanalyse
  • -1024 est présenté comme une option pour le niveau de sécurité 256 bits, c’est-à-dire pour des raisons de conformité et d’alignement de force (strength matching)
  • Comme la plupart des protocoles expérimentaux ou en cours de standardisation convergent vers ML-KEM-768, se limiter à un seul niveau n’augmente presque pas les coûts
  • Ce ciblage unique réduit le nombre de pièces mobiles, au bénéfice de la lisibilité, de la sécurité et des performances
    • par exemple, au lieu de gérer la sérialisation d’entiers sur 1, 4, 10 et 12 bits avec un encodeur générique unique, le code utilise des encodeurs/décodeurs dédiés
    • en ne visant que ML-KEM-768, il n’était pas nécessaire d’implémenter l’encodage sur 5 et 11 bits

Stratégie de test et vecteurs de test publics

  • Les tests constituent, après la lisibilité, l’autre pilier majeur de la stratégie d’assurance de sécurité de ce package
  • Les tests de base incluent la boucle complète génération de clé / encapsulation / décapsulation ainsi que plus de 95 % de couverture de test
  • La couverture supplémentaire comprend notamment
    • la vérification de l’interopérabilité avec des vecteurs de test provenant du NIST et d’autres implémentations
    • la comparaison, pour toutes les combinaisons d’entrées, des additions, soustractions et multiplications modulo 3329 avec les valeurs attendues calculées via une méthode à temps variable
    • des tests exhaustifs de compression/décompression avec math/big.Rat comme référence
    • la vérification que les constantes précalculées correspondent bien à leur définition
    • la vérification que toutes les fonctions renvoient les erreurs appropriées si la longueur des entrées est trop grande ou trop petite
    • l’exécution de vecteurs de test fournis par Sophie Schmieg et destinés à être intégrés plus tard dans Wycheproof
  • Les vecteurs de test propres au projet sont publiés dans le cadre du projet CCTV, afin d’être réutilisables par d’autres implémentations
  • Les vecteurs CCTV incluent des valeurs intermédiaires permettant de tester et déboguer chaque étape intermédiaire et chaque sous-algorithme

Les erreurs détectées par des vecteurs spéciaux

  • Les Negative test vectors fournissent des clés d’encapsulation invalides dont certains coefficients sont supérieurs à 3329
    • les vecteurs de l’équipe Kyber et du NIST sont centrés sur les entrées valides, d’où des demandes fréquentes pour ce type de vecteurs
    • toutes les valeurs de 3329 à 2¹²-1 et toutes les positions de coefficient sont testées individuellement
    • les autres coefficients sont mutualisés afin de compresser 1–3MiB de données en 12–28KiB
  • Les vecteurs “unlucky” testent les cas où la lecture XOF nécessaire devient anormalement élevée
    • il s’agit d’une clé publique pour laquelle SampleNTT doit lire plus de 575 octets depuis le XOF SHAKE-128, alors que cela ne se produit normalement qu’avec une probabilité de 2⁻³⁸
    • les vecteurs de Sophie ont été encore davantage forcés par brute force jusqu’à nécessiter au maximum 591 octets
  • Les vecteurs strcmp font échouer les implémentations qui utilisent strcmp() dans ML-KEM.Decaps
    • lors de la décapsulation, si la comparaison entre le ciphertext et la sortie de K-PKE.Encrypt rencontre un octet nul, strcmp() peut s’arrêter prématurément
  • Les Accumulated vectors sont dérivés de l’implémentation de référence pq-crystals
    • au lieu de stocker 300MB de sorties de vecteurs aléatoires, celles-ci sont régénérées pendant le test à l’aide d’un RNG déterministe, puis hachées et comparées à la valeur attendue
    • cela permet aussi de produire des hachages de 1 million de tests aléatoires, au-delà des 10k de l’implémentation de référence
  • Plusieurs tests ajoutés après coup n’ont trouvé aucun problème dans filippo.io/mlkem768, et il existe au moins un cas signalé où les negative vectors ont permis de détecter un défaut dans une implémentation majeure

Résultats de performance

  • Les performances ne sont pas l’objectif principal de ce package, ni des packages cryptographiques Go en général, mais elles doivent rester suffisantes pour être utiles
  • ML-KEM est suffisamment rapide, et cette implémentation simple atteint déjà un niveau compétitif face aux implémentations Go de P-256 et X25519 optimisées en assembleur
  • La comparaison doit se faire sur la base du travail total que chaque côté doit effectuer lors de l’établissement de clé
    • ECDH effectue deux multiplications scalaires, dont une sur base fixe
    • un KEM effectue d’un côté la génération de clé et la décapsulation, et de l’autre l’encapsulation
    • ECDH est symétrique, tandis que l’établissement de clé ML-KEM est asymétrique
  • Dans les benchmarks, « Alice » effectue la génération de clé et la décapsulation, tandis que « Bob » effectue l’encapsulation
    • la décapsulation inclut une opération complète de chiffrement pour vérifier que le ciphertext d’entrée correspond bien au résultat
    • Alice exécute chiffrement, déchiffrement et génération de clé, ce qui la rend plus lente que Bob
  • Au final, Bob est aussi rapide que X25519 ou P-256, et Alice reste à moins du double
  • Comparé à des implémentations rapides de ML-KEM comme BoringSSL et libcrux, ce package prend environ deux fois plus de temps

Chiffres de benchmark et marge d’optimisation

  • Les mesures relevées sont les suivantes
    • sur macOS arm64, ECDH/P256-8 est à 49.43µs, ECDH/X25519-8 à 77.46µs
    • dans le même environnement, RoundTrip/Alice-8 est à 109.4µs, RoundTrip/Bob-8 à 56.19µs
    • sur Linux amd64, ECDH/P256-4 est à 78.88µs, ECDH/X25519-4 à 115.6µs
    • dans le même environnement, RoundTrip/Alice-4 est à 223.8µs, RoundTrip/Bob-4 à 114.7µs
  • L’implémentation suit les patterns Go haute performance, notamment en réduisant les allocations sur le tas
  • x/crypto/sha3 a été retravaillé pour pouvoir être utilisé sans allocation sur le tas, mais comme cela a eu un effet négatif sur Apple M2, le changement n’a pas encore été fusionné et n’est pas inclus dans les benchmarks ci-dessus
  • Les marges d’optimisation restantes sont claires
    • comme la génération de clé et la décapsulation échantillonnent la matrice à partir de la même valeur, stocker cette matrice lorsque les deux opérations s’enchaînent côté Alice pourrait faire gagner environ 10 % de temps
    • il est peut-être possible de réduire les copies dans le chemin de lecture de sha3
    • ensuite, il faudra optimiser l’implémentation du corps

Prendre en charge Kyber v3 avec une implémentation ML-KEM

  • Le NIST a apporté quelques petites modifications à la soumission Kyber Round 3, résumées dans la section 1.3 du brouillon FIPS
  • Plusieurs protocoles expérimentaux basés sur Kyber v3 ou “draft00” existent, y compris le principal échange de clés PQ TLS déployé
  • Il est possible de prendre en charge Kyber v3 avec une implémentation ML-KEM sans package séparé
  • L’un des changements ajoute une validation pour un cas particulier d’encodage non canonique des coefficients de clé publique
    • une implémentation correcte ne produit pas de telles clés, donc elles peuvent être rejetées conformément au brouillon FIPS
    • ce comportement permet de distinguer une implémentation Kyber-sur-ML-KEM, mais sans autre effet néfaste
  • Un autre changement supprime l’étape de hachage appliquée à l’entrée du CSPRNG
    • comme les octets d’entrée sont aléatoires, aucune des parties ne peut faire la différence
  • Le plus grand changement concerne le hachage du ciphertext dans le secret partagé
    • cette différence peut empêcher l’interopérabilité
    • il suffit de produire le secret partagé ML-KEM K, puis d’appliquer SHAKE-256(K || SHA3-256(c))[:32] pour obtenir le secret partagé Kyber
    • cela ne casse pas l’abstraction ML-KEM
  • Kyber et ML-KEM hachent tous deux le secret et le ciphertext lors de la décapsulation pour l’implicit rejection
    • si l’on applique cette dérivation de clé au-dessus de ML-KEM, le ciphertext est alors haché deux fois dans l’implicit rejection
    • ce résultat d’implicit rejection est, par conception, imprévisible et non destiné à l’interopérabilité, ce qui ne pose donc pas de problème

À lire aussi

1 commentaires

 
GN⁺ 2024-02-02
Commentaires Hacker News

  • Bonjour de chez Kudelski Security. C’est très opportun, car nous avons récemment dû abandonner l’autre bibliothèque de cryptographie résistante au quantique pour Go, qui était quasiment la seule autre existante
    Toute l’histoire est ici : https://research.kudelskisecurity.com/2024/02/01/the-kybersl...

    • Kyber-512 n’avait-il pas été intentionnellement affaibli par des membres côté NSA du NIST ?

  • Je me demande jusqu’où en est réellement l’informatique quantique pour que ce genre de chose devienne nécessaire
    Est-ce qu’on n’est pas dans une situation où, comme avec l’IA, plutôt qu’une vraie apparition de quelque chose, on redéfinit simplement les termes pour sortir de nouveaux produits sous un nom existant ?

    • La cryptographie traite la menace des ordinateurs quantiques d’une façon particulière. Une partie des données chiffrées et des connexions d’aujourd’hui ne doivent pas devenir déchiffrables dans 30 ou 50 ans
      Donc la question n’est pas « est-ce que les ordinateurs quantiques arrivent bientôt ? », mais « est-il plausible qu’ils apparaissent au cours du prochain demi-siècle ? ». Il n’y a pas de consensus précis, mais la réponse n’est pas « non », d’où cette dynamique aujourd’hui
      C’est aussi pour cela qu’on voit davantage de progrès du côté de l’échange de clés PQC que des signatures. Vérifier une signature aujourd’hui ne sera pas affecté par un ordinateur quantique dans 50 ans, alors que le chiffrement, oui
    • Il ne s’agit pas de contrer les ordinateurs quantiques actuels
      Le risque, c’est qu’un attaquant stocke aujourd’hui des textes chiffrés pour les déchiffrer plus tard. Plus on bascule vite vers une cryptographie sûre face au quantique, moins on laisse derrière nous de « stock de textes chiffrés » vulnérable à de futures attaques
    • Si la réponse était « la NSA exécute déjà de la cryptanalyse quantique en production et il faut considérer ECDH comme totalement cassé », quiconque le saurait se retrouverait dans une situation extrêmement délicate au moment de le dire
      Cela semble peu probable en pratique, mais cette question reste difficile à trancher dans une certaine mesure. À l’heure actuelle, ce n’est pas une menace connue, mais le degré de paranoïa à avoir vis-à-vis de ce potentiel reste subjectif
    • Au cours des deux dernières années environ, le NIST a retenu quelques algorithmes de cryptographie post-quantique, et les implémentations se multiplient depuis. L’informatique quantique est encore loin, mais l’attitude semble être : « quel mal y a-t-il à commencer dès maintenant ? »
      Je n’en suis pas certain, mais j’imagine que la cryptographie sur courbes elliptiques avait aussi déjà pas mal d’implémentations bien avant son usage généralisé. Si quelqu’un a connu cette époque et que je me trompe, qu’il me corrige
    • Pour qu’un ordinateur quantique casse RSA-2048, il faudrait grosso modo multiplier par 10 la qualité des qubits physiques actuels, et par 10 000 leur quantité. Ce sont des chiffres très approximatifs
      Le prochain jalon majeur à surveiller est un qubit logique dont la fidélité est 1 000 fois supérieure à celle des qubits physiques qui le composent. Si cela arrive, ce sera le signal que la qualité des qubits physiques est suffisante et qu’il ne reste plus qu’à commencer à passer à l’échelle en nombre

  • Dans cette discussion, le récent guide d’introduction de John Arundel à l’implémentation de systèmes cryptographiques avec les dernières versions de Go peut être utile. La dernière section évoque brièvement la cryptographie post-quantique, et une fois que la PQ du NIST sera standardisée, John pourra peut-être intégrer cette bibliothèque et mettre le livre à jour
    Explore Go: Cryptography (Go 1.22 edition):
    https://bitfieldconsulting.com/books/crypto

  • Corrigez-moi si je me trompe, mais si c’est écrit en Go pur, est-ce que ce n’est pas vulnérable aux attaques par canal auxiliaire de timing/alimentation ?

    • Il est difficile de dire que Go est plus vulnérable que C, et il l’est peut-être même moins. La différence, c’est qu’en Go il n’y a essentiellement qu’un compilateur majeur et il a tendance à ne pas sur-optimiser, alors qu’en C il faut recourir à des astuces de plus en plus complexes pour empêcher le compilateur de comprendre l’intention et de transformer le tout en branchements à temps variable plus efficaces
      Cette implémentation est écrite de manière à éviter les chemins de code qui varient selon des valeurs secrètes. Les canaux auxiliaires liés à l’alimentation, qui nécessitent un accès physique, sont hors du modèle de menace de Go
    • Il est indiqué que « toutes les opérations critiques sont effectuées en temps constant »
      J’aurais dû suivre les liens jusqu’à la documentation du projet, mais il semble bien que cet aspect soit pris en compte
    • Existe-t-il un langage immunisé contre les attaques par canal auxiliaire de puissance ? L’idée même ne me paraît pas tenir debout
      Et pour ce qui est des attaques par timing, je ne vois pas pourquoi Go serait plus vulnérable aux canaux auxiliaires temporels que d’autres langages

  • Quelqu’un connaît-il des implémentations pour d’autres langages comme Java ou C# ?

  • C’est sympa que cela puisse aussi fonctionner avec draft00/kyber v3
    À quel point serait-il difficile de prendre en charge le mode Kyber 90’s, plus rapide, sans SHA-3 ? J’imagine que dans ce cas il faudrait probablement casser l’abstraction

    • Changer le hachage nécessiterait un fork. Dans cette implémentation, seulement environ 20 % du temps CPU est consacré à SHA-3, donc le gain ne serait pas énorme
      Même si l’optimisation de l’implémentation du corps de calcul ferait monter cette part, cela ne suffirait probablement pas à justifier l’usage d’un mode non standardisé et moins testé

  • Sans rapport, mais Filo, la table des appels système 32 bits est toujours marquée « coming soon » :')

    • Haha, oui, j’avoue. Chaque fois que je pense à retravailler cette page, le périmètre ne cesse de s’élargir, par exemple en voulant la faire générer automatiquement par la CI à partir du code source du noyau :)

  • Je ne suis pas capable d’évaluer la qualité de cet algorithme ou de cette implémentation, mais j’aime beaucoup l’idée d’utiliser Unicode dans les noms de variables
    ρ, σ := G[:32], G[32:]
    D’une certaine façon, c’est bien mieux que de voir "rho" et "sigma"

    • Difficile d’être d’accord. C’est joli à regarder, mais je n’ai pas vraiment envie de voir ça dans du vrai code
      Déjà, je ne saurais même pas comment les taper au clavier. Et la plupart des gens ne connaîtront probablement même pas le nom de ces symboles. Bien sûr, ceux qui lisent ce code ont plus de chances de les connaître, mais je ne trouve pas ça très bienveillant
      La clarté est essentielle, et "rho" ou "sigma" sont assez clairs. En plus, si on a à la fois la constante "n" et la constante "η", c’est parfait pour semer la confusion
    • Je n’aime pas du tout. Tout caractère absent de mon clavier ajoute une étape de saisie, ce qui crée trop de friction. Et j’ai l’impression que je lirais ρ comme p, pour finir avec de mystérieuses erreurs de compilation
      Et si on se met à ajouter des accents ou des cédilles aux lettres ? Ça ne fait qu’augmenter la complexité. Mieux vaut s’en tenir au plus petit dénominateur commun
    • Go autorise les indices Unicode dans les noms de variables ?
      Dans les langages que j’ai vérifiés, Perl, Python et JavaScript ne les autorisaient pas dans Chrome et Firefox, tandis que PHP les autorisait

  • La personne qui a créé ça est aussi celle qui a créé https://github.com/FiloSottile/age
    J’aime vraiment beaucoup cet outil

    • C’est dommage qu’il n’y ait pas de négation plausible intégrée. Je veux dire qu’on devrait au minimum pouvoir chiffrer deux fichiers et, selon la clé fournie, en déchiffrer l’un ou l’autre
      Ça ressemble à une faille de sécurité commune à la plupart des outils de ce genre. S’il n’existe qu’une seule clé possible, quelqu’un avec un marteau peut vous forcer à la donner. Mais si le nombre de clés est inconnu, on peut en livrer quelques-unes, cacher le vrai fichier à protéger et espérer que l’attaquant s’en aille
    • J’ai envie d’aimer cet outil, mais il manque de manuel ou de tutoriel expliquant les cas d’usage typiques. Je ne parle pas de l’utilisation en ligne de commande, mais de la manière de gérer et distribuer les clés, et des points auxquels il faut faire attention
      Toute la couche sociale qui se superpose à la technique reste floue pour moi. J’aimerais bien une histoire d’exemple avec Alice et Bob
    • Age est correct, mais il semble au point mort. La dernière version date de 2022, et il n’utilise pas de fonction de dérivation de clé à partir d’un mot de passe plus moderne, comme argon
      Si vous cherchez quelque chose conçu pour stocker/partager des secrets, rot peut aussi valoir le détour : https://github.com/candiddev/rot

  • La spécification : https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.203.ipd.pdf est également liée dans l’article