- La critique centrale est que, dans sa promotion de Kyber-512 comme standard de cryptographie post-quantique, le NIST aurait mal calculé le coût d’attaque et ainsi surestimé son niveau de sécurité
- Le point litigieux est que le coût de calcul et le coût d’accès mémoire par itération doivent être additionnés, alors que le NIST les aurait traités comme s’ils étaient multipliés, ajoutant « 40 bits de sécurité supplémentaires » à l’estimation de Matzov de 2^137
- Kyber-512 est présenté à un niveau de 2^118 selon Core-SVP, et le NIST voulait l’aligner sur le niveau d’AES-128, soit environ 2^143 opérations bit, mais il lui est reproché de combiner des valeurs dont les unités et la signification ne correspondent pas
- Kyber ne propose que des choix de paramètres limités, comme Kyber-512, Kyber-768 et Kyber-1024, tandis que NTRU et NTRU Prime offriraient des choix plus granulaires en matière de taille et de niveau de sécurité
- La standardisation de Kyber-512 comporte des incertitudes sur l’analyse des attaques, une absence de quantification du modèle de coût mémoire et un manque d’examen public ; l’auteur demande le retrait de Kyber-512 et la divulgation par le NIST de son erreur de calcul
Le cœur de l’erreur de calcul
- Le point de départ est un exemple simple : « 2^40 + 2^40 ne fait pas 2^80, mais 2^41 »
- Confondre les nombres à multiplier et ceux à additionner peut fortement gonfler le niveau de sécurité
- Dans le débat sur le niveau de sécurité de Kyber-512, la structure en cause est la suivante
- Une attaque se compose de nombreuses itérations
- Chaque itération a un coût de calcul et un coût d’accès mémoire
- Le coût total doit être calculé comme
nombre d’itérations × coût par itération - Dans le coût par itération, le coût de calcul et le coût d’accès mémoire doivent être additionnés
- La critique centrale est que le NIST n’aurait pas additionné le coût de calcul et le coût d’accès mémoire, mais aurait produit l’effet d’une multiplication
- Par exemple, 2^25 opérations bit/itération et 2^35 opérations bit/itération doivent être additionnées
- Si on les multiplie, l’unité devient
bitops^2/iter^2, ce qui n’est pas une unité de coût d’attaque - Une telle multiplication peut surestimer le coût d’attaque de plusieurs millions de fois ou davantage
Contexte de NISTPQC et de Kyber-512
- En 2022, le NIST a annoncé son intention de standardiser Kyber-512, puis a publié en 2023 un projet de standard Kyber-512
- La critique porte sur le fait que le NIST aurait commis une grave erreur de calcul en justifiant le niveau de sécurité de Kyber-512
- En mars 2022, une demande FOIA liée à NSA, NIST, and post-quantum cryptography a été déposée, puis des documents internes du NIST ont été partiellement rendus publics à la suite d’un procès
- La comparaison entre documents publiés et non publiés suggère que l’implication de la NSA dans le processus NISTPQC aurait été plus importante que ne l’indiquaient les explications publiques du NIST
- La liste de l’équipe
pqc@nist.goven 2016 aurait compté plus de personnes de la NSA que du NIST - Le NIST avait déclaré dans des documents publics en 2020 que les retours de la NSA n’avaient pas influencé ses décisions et que seul le NIST prenait des décisions sur la base d’informations publiques
- En janvier 2023, une nouvelle demande FOIA a été déposée au sujet des affirmations sur le niveau de sécurité de Kyber-512, et le NIST aurait de nouveau retardé sa réponse, entraînant une nouvelle action en justice
Choix de paramètres limités dans Kyber
- Il est souligné qu’avec Kyber, contrairement à RSA, ECC, McEliece ou NTRU, il est difficile d’augmenter progressivement le niveau de sécurité avec la taille souhaitée
- Il n’existe pas de Kyber-576, et l’option plus forte que Kyber-512 est Kyber-768, ce qui exige une augmentation de dimension de 50 %
- L’option plus forte que Kyber-768 est Kyber-1024
- Aucune option plus forte que Kyber-1024 n’est fournie
- La documentation officielle de Kyber mettait en avant comme avantage le fait de pouvoir traiter tous les jeux de paramètres avec une « NTT de dimension 256 », mais, dans cette structure, une dimension qui n’est pas un multiple de 256 exige un changement de conception fondamental
- Dans les applications limitées à 1 Ko, il est difficile d’utiliser Kyber-768, et Kyber-512 devient alors le choix Kyber offrant la meilleure sécurité
- Kyber-768 utilise une clé publique de 1184 octets et un ciphertext de 1088 octets
- Kyber-512 utilise une clé de 800 octets et un ciphertext de 768 octets
- Pour la même limite de 1 Ko, les familles NTRU offriraient des estimations Core-SVP plus élevées
sntrup653: clé de 994 octets, ciphertext de 897 octets, Core-SVP 2^129- NTRU-677 (
ntruhps2048677) : clé de 931 octets, ciphertext de 931 octets, Core-SVP 2^145 - La version round-3 de Kyber-512 est présentée avec Core-SVP 2^118
- Core-SVP est le mécanisme utilisé par l’équipe Kyber dans ses soumissions round-1 et round-2 pour estimer le niveau de sécurité, et le rapport round-2 du NIST de 2020 utilise également Core-SVP pour les comparaisons
Critères d’évaluation du NIST et comparaison avec NTRU
- L’appel officiel à soumissions du NIST en 2016 incluait la flexibilité parmi les critères d’évaluation
- Il considérait que, à condition d’offrir une « bonne sécurité et de bonnes performances globales », une approche plus flexible répond à davantage de besoins utilisateurs
- Il précisait que, même au sein d’une même catégorie, plusieurs jeux de paramètres pouvaient être proposés pour ajuster les performances ou la marge de sécurité
- En 2020, en éliminant NewHope, le NIST a cité parmi ses raisons le fait que Kyber prenait naturellement en charge un jeu de paramètres de catégorie 3
- Si Kyber-512 ne satisfait pas le niveau minimal de sécurité, Kyber ne conserve plus que Kyber-768 et Kyber-1024, ce qui accentue son manque de flexibilité par rapport à NTRU
- Le selection report 2022 du NIST disait avoir confiance dans la sécurité de Kyber comme de NTRU, et évaluait aussi les performances globales des KEM comme acceptables pour les applications généralistes
- Dans ces conditions, si Kyber-512 est retiré, l’argument est que NTRU devient plus avantageux que Kyber en proposant des options plus petites, des options plus sûres et des compromis taille/sécurité plus fins
Quatre critiques selon lesquelles le NIST aurait biaisé la compétition
-
1. Ignorer la flexibilité supplémentaire de NTRU
- La littérature sur NTRU aurait montré depuis longtemps qu’il était possible de proposer plusieurs niveaux de sécurité et plusieurs choix de taille
- En 2020, le NIST a déclaré qu’un « trop grand nombre de parameter sets » compliquait l’évaluation et l’analyse
- Alors que les critères officiels présentaient la flexibilité comme un point positif, la critique « too many » serait apparue en cours de route, et le NIST n’aurait pas clairement répondu à ce critère
-
2. Exagérer le coût de génération de clés
- Dans les benchmarks sur Golden Cove, Kyber-512 prend 25829 cycles pour l’encapsulation et 20847 cycles pour la décapsulation
- NTRU-509 prend 15759 cycles pour l’encapsulation et 25134 cycles pour la décapsulation, soit un total de traitement du ciphertext inférieur de 13 % à celui de Kyber-512
- En revanche, la génération de clés NTRU-509 prend 112866 cycles, contre 17777 cycles pour Kyber-512
- Mais l’auteur affirme qu’un KEM peut réutiliser les clés pour plusieurs ciphertexts, que le coût d’envoi et de réception des octets compte bien plus que les cycles, et que le Montgomery trick peut accélérer la génération de clés NTRU
-
3. Masquer le niveau de sécurité plus élevé de NTRU
- Dans son rapport round-2 de 2020, le NIST a commencé à recommander fortement des jeux de paramètres de catégorie 5
- NTRU proposait NTRU-1229 et NTRU-HRSS-1373, avec respectivement Core-SVP 2^301 et 2^310, supérieurs au 2^254 de Kyber-1024
- NTRU Prime proposait aussi des options comme
sntrup1277etntrulpr1277, avec Core-SVP 2^270 et 2^271 - Il est reproché aux graphiques du NIST de ne pas avoir suffisamment mis en évidence ces options NTRU à haute sécurité
-
4. Exclure NTRU-509, l’option la plus performante
- Il est reproché au NIST d’avoir exclu NTRU-509 d’un grand graphique, puis des figures et tableaux du selection report ultérieur
- NTRU-509 offre une clé et un ciphertext plus petits que Kyber-512, ce qui contredit selon l’auteur l’affirmation du NIST selon laquelle « NTRU a une clé publique et un ciphertext somewhat larger » que Kyber
- Pour exclure NTRU-509, il faudrait dire qu’il n’atteint pas le niveau minimal de sécurité AES-128, mais maintenir Kyber-512 selon le même critère serait une distinction très fragile
Incertitudes après Core-SVP
- Le Core-SVP de Kyber-512 est de 2^118, et le coût d’une attaque contre AES-128 est estimé à un peu plus de 2^140 opérations bit
- Les documents de soumission Kyber de 2017 et 2019 affirmaient que la sécurité dépassait Core-SVP d’au moins 30 bits, mais une partie des justifications serait erronée ou insuffisante
- Le bruit d’arrondi ne s’applique pas aux attaques sur les clés et ne constitue donc pas une raison d’augmentation de la sécurité
- L’affirmation d’une hausse subexponentielle du coût du sieving ne serait pas étayée, et les asymptotiques réelles pourraient être plus rapides que Core-SVP
- Le nombre d’appels à l’oracle SVP et le gate count peuvent être en partie valables, mais ne semblent pas suffisants pour sauver Kyber-512
- Le coût d’accès mémoire peut être important dans le coût d’attaque réel, mais le critère officiel du NIST exigeait 2^143 « classical gates », ce qui le rend difficile à utiliser directement comme argument pour sauver Kyber-512
- La soumission round-3 de Kyber aurait modifié Kyber-512 et changé aussi la définition de Core-SVP pour obtenir 2^118 au lieu de 2^112
- Cette soumission présentait la sécurité de Kyber-512 comme 151 bits ±16, et affirmait que même une baisse à 135 ne serait pas « catastrophic » en raison des besoins mémoire
- Par la suite, plusieurs analyses d’attaques sur les lattices, dont celles de Matzov, sont apparues, rendant les estimations de sécurité de Kyber-512 plus complexes et instables
La logique du NIST pour sauver Kyber-512
- L’appel officiel du NIST précise que chaque catégorie de sécurité prend comme borne inférieure une primitive de référence comme AES-128 selon diverses métriques « potentially relevant »
- Autrement dit, toute attaque doit exiger au moins autant de ressources que la référence dans toutes les métriques que le NIST considère comme potentiellement pertinentes pour la sécurité pratique
- Le NIST a longtemps évité de définir clairement les « classical gates » à la demande de certains, puis a expliqué dans son selection report 2022 qu’une lecture/écriture mémoire d’un bit pouvait compter comme une porte de coût 1
- Il est reproché au NIST d’avoir utilisé, pour exclure NTRU-509, un « non-local cost model », c’est-à-dire un critère considérant en pratique les coûts d’accès mémoire comme gratuits
- À l’inverse, pour maintenir Kyber-512 en catégorie 1, il considère que Kyber-512 satisfait la catégorie 1 si l’on tient compte des « realistic memory access costs »
- En conséquence, le reproche est qu’il aurait appliqué une métrique à mémoire gratuite à NTRU-509 et une métrique à mémoire coûteuse à Kyber-512
NISTBS : réfutation de l’explication du 7 décembre 2022
- Le 7 décembre 2022, le NIST a expliqué pourquoi il considérait que Kyber-512 satisfaisait la catégorie I du NIST, et ce texte l’appelle « NISTBS »
- NISTBS part de l’idée que le rapport Matzov estime le coût d’attaque de Kyber-512 à 2^137 opérations bit
- Le coût d’une attaque classique contre AES-128 est estimé à environ 2^143 opérations bit
- Il manque donc 6 bits
- NISTBS explique que les attaques par lattice sieving nécessitent des accès non structurés à une grande mémoire, et que le modèle RAM ignore ce coût
- Il cite ensuite les évaluations des documents de soumission NTRU et NTRU Prime pour calculer que, dans les attaques par sieving de catégorie 1, la prise en compte du coût d’accès mémoire peut ajouter « 20 à 40 bits » par rapport au modèle RAM
- Le problème est que le NIST semble avoir ajouté les 40 bits de NTRU Prime aux 2^137 de Matzov pour l’interpréter comme un niveau d’environ 2^177
- Les 40 bits de NTRU Prime semblent provenir de la différence, pour
sntrup653, entre le « real » 2^169 et le « free » 2^129 - 2^129 est Core-SVP, c’est-à-dire une estimation approximative du nombre d’itérations, et non un gate count du modèle RAM au sens du NIST
- Le coût d’accès mémoire doit être ajouté au coût par itération ; il ne peut pas être multiplié par le coût total de calcul déjà comptabilisé en opérations bit, ni ajouté comme exposant
- Les 40 bits de NTRU Prime semblent provenir de la différence, pour
Ce que signifient réellement les chiffres
- Le document NTRU Prime rapporte un Core-SVP de 2^129 pour
sntrup653- Il s’agit d’une estimation approximative du nombre d’itérations
- Le même document estime le coût total d’accès mémoire comme équivalent à 2^169 opérations bit
- Kyber-512 est présenté avec un Core-SVP de 2^118
- En estimant grossièrement le coût d’accès mémoire de la même manière, il serait équivalent à 2^154 opérations bit
- L’estimation de 2^151 « gates » dans le document Kyber n’est pas une estimation du coût d’accès mémoire
- C’est une estimation du nombre d’opérations bit dans le calcul interne de l’attaque
- En tenant compte des « known unknowns », elle est présentée comme une fourchette de 2^135 à 2^167
- Par conséquent, l’estimation de coût de calcul de 2^151 et l’estimation de coût d’accès mémoire ne sont pas des termes à multiplier entre eux ; ce sont des termes qui doivent être alignés sur le coût par itération et additionnés
Pourquoi l’erreur était considérée comme facile à détecter
- Un simple sanity check est le suivant
- Le document Kyber estime le coût de calcul d’une attaque contre Kyber-512 à 2^135~2^167 opérations bit
- NTRU Prime estime le coût d’accès mémoire de
sntrup653, qui semble plus difficile que Kyber-512, comme équivalent à 2^169 opérations bit - Il est jugé étrange que, alors que l’attaque s’est améliorée de 2^14, le NIST calcule le coût d’attaque de Kyber-512 à 2^177
- NISTBS a écrit que le document NTRU Prime estimait « 40 bits de sécurité supplémentaires » par rapport au modèle RAM, mais la section 6.11 de ce document ne contiendrait pas directement les expressions « 40 » ou « RAM model »
- La critique est que, pour permettre un examen clair, le NIST aurait dû expliquer d’où venait exactement le 40 et quelle valeur de quelle métrique il désignait
- Depuis décembre 2022, des questions de confirmation sur le scénario X précis — « est-il exact que le calcul est 137+40=177 ? » — auraient été posées, mais le NIST n’y aurait pas répondu
- Le NIST aurait ensuite répondu que cet e-mail « speaks for itself », sans confirmer l’interprétation précise du calcul ni proposer d’interprétation alternative
Les recherches nécessaires pour un calcul correct
- Un calcul correct doit distinguer deux effets
- Une partie de l’augmentation de l’estimation de sécurité par rapport à Core-SVP provient du coût des opérations bit dans le calcul interne aux itérations
- Une autre partie provient d’une boucle externe dans laquelle le nombre d’itérations lui-même augmente par rapport à Core-SVP
- L’effet d’augmentation du nombre d’itérations peut être multiplié par le coût d’accès mémoire
- En revanche, le coût de calcul interne à l’itération et le coût d’accès mémoire interne à l’itération doivent être additionnés ; multiplier ces deux éléments est l’erreur centrale
- Un calcul précis devrait suivre des centaines de pages d’articles sur les attaques lattice de l’état de l’art et réoptimiser toute la pile d’attaque en incluant le coût d’accès mémoire
- Par exemple, même pour savoir si, dans BKZ, la low-memory enumeration ou le high-memory sieving est préférable, il faut recalculer en intégrant les coûts d’accès mémoire
Projet de standard et question de responsabilité
- En août 2023, le NIST a publié le projet ML-KEM, un projet de standard Kyber
- ML-KEM-512 est security category 1
- ML-KEM-768 est category 3
- ML-KEM-1024 est « claimed » comme category 5
- Le problème est que le sujet de « claimed » n’est pas clair
- Il n’est pas clair si cette affirmation vient du NIST, des concepteurs ou de quelqu’un d’autre
- L’Appendix A du projet reprend le critère selon lequel la catégorie doit dépasser AES-128, AES-192 et AES-256 dans toutes les métriques potentially relevant
- L’analyse la plus récente du document Kyber indique que le coût d’attaque de Kyber-512 pourrait descendre à 2^135 « classical gates », soit moins que l’estimation de 2^143 gates du NIST pour AES-128
- Il est donc nécessaire que le NIST publie une analyse expliquant comment il justifie l’affirmation selon laquelle Kyber-512 est au moins au niveau d’AES-128 dans toutes les métriques pertinentes
Conclusion et propositions
- La conclusion est que la surface d’attaque des lattices est instable et insuffisamment comprise, et que standardiser Kyber-512 est donc imprudent
- Kyber-512 pourrait être beaucoup plus facile qu’AES-128 même en tenant compte des attaques déjà publiées et des coûts d’accès mémoire ; l’inverse est également possible, et établir l’état réel exige des recherches difficiles
- L’auteur souligne qu’AES-128 lui-même, dans des attaques multi-cibles, peut descendre à environ 2^88 calculs pour casser l’une des mille milliards de clés, si bien qu’une perte de 10 à 30 bits est difficile à ignorer
- Si Kyber-512 reste une option standard, même des applications capables de supporter Kyber-1024 ou NTRU-1229 risquent de choisir l’option rapide
- La recommandation finale est de retirer Kyber-512 et que le NIST reconnaisse publiquement son erreur de calcul du niveau de sécurité de Kyber-512 ainsi que la sélection opaque de données dans sa comparaison avec NTRU
1 commentaires
Commentaires Hacker News
Ce qu’il faut absolument savoir avant de lire cet article, c’est que ce ne sont pas le NIST et la NSA qui ont créé cet algorithme, ils ont évalué la compétition.
La majeure partie de l’analyse a été réalisée par les concurrents et le monde académique, et l’équipe Kyber comprenait Roberto Avanzi, Joppe Bos, Léo Ducas, Eike Kiltz, Tancrède Lepoint, Vadim Lyubashevsky, John M. Schanck, Gregor Seiler, Damien Stehlé, ainsi que Peter Schwabe, collaborateur de Bernstein.
Historiquement, seul le vainqueur est souvent adopté. Il suffit de regarder la compétition AES et de voir à quelle fréquence Serpent est mentionné, alors qu’il est considéré comme ayant une marge de sécurité plus importante que Rijndael.
Le NIST ne semble pas formuler ses recommandations sur la base d’analyses secrètes.
La triste réalité, c’est que Bernstein a peut-être raison, mais qu’il est difficile de savoir si la réponse — ou l’absence de réponse — du côté du NIST doit être vue comme de la tromperie, ou s’ils ne voulaient simplement pas s’embarquer avec quelqu’un arrivant avec une attitude très agressive.
Au NIST aussi, ce sont des gens ordinaires qui travaillent, et il est probable qu’ils aient reçu des demandes d’explications acerbes un peu comme la plupart d’entre nous recevons des rapports de bug agressifs.
Les accusations exagérées du genre « en recommandant d’utiliser Kyber à partir du moment où la licence de brevet s’activera en 2024, ils ont exposé trois ans de données utilisateur à des attaquants, et n’ont pas recommandé NTRU dès 2021 » n’aident pas. Il n’y aura sans doute pas, pendant un certain temps, beaucoup de déploiements immédiats de cryptographie post-quantique autonome, et en 2021 le NIST avait plusieurs alternatives qu’il aurait pu proposer. SIKE avait l’air plutôt correct jusqu’à sa cassure l’an dernier.
Le NIST n’a pas une réputation irréprochable dans ce domaine, mais pour critiquer les algorithmes et les procédures, ce serait bien d’avoir un résumé concis du pourquoi, accompagné d’une ou deux preuves décisives. Des analyses d’innombrables e-mails, une comparaison avec une seule soumission, et des accusations selon lesquelles tout le monde ferait traîner pour aspirer des données rendent l’ensemble difficile à prendre au sérieux. Si Kyber-512 est réellement aussi dangereux, cela devrait être communiqué plus clairement.
Le fait que la page fasse 17 000 mots joue aussi beaucoup. Même selon les standards de Harry Potter, cela représente 70 minutes de lecture pour un lecteur moyen, sauf que ce texte n’est pas un roman : il est rempli de chiffres, de considérations et de phrases où il faut peser le choix des mots, comme les citations du NIST. Même avec suffisamment de bagage pour comprendre la cryptographie post-quantique, il est difficile de le lire rapidement comme un livre ordinaire.
Au début, j’ai cliqué sur « That lawsuit has been gradually secret NIST documents, shedding some light on what was actually going on behind the scenes » et je me suis fait aspirer par un autre texte ; or la page liée faisait encore 54 000 mots. Sur mobile, sans barre de défilement, je n’avais aucune idée de la longueur et je la parcourais linéairement, jusqu’au moment où j’ai eu l’impression de m’être inscrit à un projet de recherche doctoral ; j’ai fermé l’onglet et suis revenu au texte d’origine.
Les lecteurs de HN sont nombreux à être intelligents et techniques, mais leurs domaines sont variés, si bien qu’il est difficile d’évaluer raisonnablement des preuves pleines de jargon censées étayer « NIST = méchant ». Étant dans un domaine voisin, je pense comprendre plus que le lecteur moyen, mais je ne me sens pas légitime pour juger sans avoir lu correctement. Le texte explique bien le contexte et les acronymes, mais il y en a tellement que je ne sais pas si quelqu’un qui ne connaît pas déjà le sujet aurait envie de s’y plonger. Toutes les soumissions n’ont pas besoin d’être compréhensibles par tout le monde, mais comme celle-ci contient des accusations, je me demande si c’est vraiment un texte adapté à HN.
Du coup, je pourrais revenir un peu sur ce que j’ai dit plus bas, ou au moins mieux comprendre le ton agressif compte tenu de l’historique de djb avec les recommandations du NIST. Des informations connexes se trouvent sur https://en.wikipedia.org/wiki/Daniel_J._Bernstein#Cryptograp....
Je n’aime pas trop qu’on privilégie excessivement le fond au détriment de la forme, mais dans ce cas, la forme du billet de blog était si mauvaise qu’il était difficile d’évaluer si le contenu avait de la valeur. N’étant pas cryptographe, je ne peux pas juger le fond, mais les sarcasmes et le dénigrement inutiles rendaient le message très suspect. Même lorsqu’il semblait mettre le doigt sur de bons points, le ton général ressemblait à une vidéo YouTube du genre « WhaT ThE ElITe DoN'T WanT YoU TO KnoW!! », et même si c’est vrai, l’auteur donne l’impression d’être assez désagréable.
Je me demande aussi s’il y a vraiment des gens qui l’ont lu jusqu’au bout. Il est peut-être vrai qu’Internet a tué notre capacité de concentration, mais à l’inverse, il y a aujourd’hui tellement d’informations qu’on choisit très strictement où consacrer son temps. Pour un billet de blog, les détails pertinents et le résumé devraient figurer dans les premiers paragraphes, et le long journal d’errance venir après. Si les éléments importants sont cachés comme dans Où est Charlie ? au milieu d’un journal interminable, il est difficile d’espérer que les gens le lisent jusqu’au bout.
La question centrale qu’il pose à répétition est de savoir pourquoi les critères d’évaluation ont été sans cesse modifiés après coup, pourquoi les résultats ont été présentés de manière trompeuse, et pourquoi des erreurs de calcul élémentaires ont été commises. Ces gens sont des experts, et tous ces éléments ont joué en faveur d’un seul algorithme.
À mes yeux, cela ressemble à un signal indiquant qu’ils voulaient faire de cet algorithme un standard. Si l’on ajoute à cela que l’implication de la NSA était bien plus importante que ce qui était connu, et qu’ils ont essayé de le cacher, cela me rend extrêmement méfiant envers ce standard.
Le problème, c’est que ces algorithmes vont bientôt être intégrés au matériel.
Maintenant que l’implémentation qui sera standardisée est fixée, les fabricants de matériel vont probablement commencer à concevoir des blocs calculant plus efficacement le standard FIPS 203. Ils en ont peut-être déjà conçu quelques-uns.
Étant donné que la publication du standard est attendue pour 2024 et que l’examen NIST CMVP des modules FIPS prend 1 à 2 ans, il ne serait pas surprenant de voir apparaître vers la mi-2026 des modules matériels FIPS 140-3 intégrant ML-KEM (Kyber, etc.).
Le point clé semble être la phrase de [1] : « Cependant, le NIST n’a pas formulé d’énoncé clair de bout en bout indiquant que Kyber-512 dispose, pour un (N,X) clairement spécifié, d’une marge de sécurité de N bits dans le scénario X ».
Dans [2], djb a résumé de façon concise ce qu’il entendait par « scénario X » et dit qu’une réponse oui/non suffit. Il pose la question à des personnes qui ont réellement besoin de savoir cela et disposent du bagage technique pour en discuter. C’est parce qu’il n’a pas obtenu de réponse qu’il a publié [1].
La réponse du NIST en [3] rejette [1] sans discussion sur la sécurité elle-même. Le deuxième paragraphe, en particulier, était frustrant. « L’e-mail cité (https://groups.google.com/a/list.nist.gov/g/pqc-forum/c/4MBu...) parle de lui-même. Le NIST reste intéressé par les avis des gens sur la question de savoir si le plan actuel de normaliser Kyber512 est une bonne idée. Les évaluateurs sont libres, pour le plaisir, d’essayer de réfuter ce que le NIST semble affirmer au sujet de la marge de sécurité, mais le résultat ne sera pas particulièrement utile au processus de normalisation. Les affirmations antérieures du NIST et leur interprétation n’ont aucun rapport avec le fait que les gens pensent ou non que normaliser Kyber512 est une bonne idée. »
Si le NIST considère les arguments de sécurité des évaluateurs comme « pas particulièrement utiles au processus de normalisation », pourquoi le public devrait-il faire confiance à cette norme, sachant que ces évaluateurs sont des cryptographes ?
Il ne peut pas y avoir de preuve décisive. Le problème actuel tient précisément à l’absence d’explication claire. Si l’on pouvait expliquer comment le niveau de sécurité de Kyber-512 a été calculé, ce serait une autre affaire.
Les estimations actuelles de tiers donnent, pour la force de sécurité de Kyber-512 — une valeur assez ambiguë —, un résultat inférieur aux exigences initiales ; une clarification ou une justification paraît donc nécessaire.
[1] : https://groups.google.com/a/list.nist.gov/g/pqc-forum/c/4MBu...
[2] : https://groups.google.com/a/list.nist.gov/g/pqc-forum/c/4MBu...
[3] : https://groups.google.com/a/list.nist.gov/g/pqc-forum/c/4MBu...
J’aurais peut-être été d’accord si ce texte venait d’un inconnu, mais ses auteurs sont DJB ou Tanja Lange, et aucun des deux n’est inconnu.
Ce genre de travail est forcément, dans une certaine mesure, antagoniste. La cryptanalyse exige aussi cette attitude, et il y a eu plusieurs affaires suspectes par le passé. Cela fait partie du domaine et de sa politique ; c’est difficile à éviter.
Ceci ressemble moins à un article qu’à un journal intime. Il y a beaucoup de jargon, ce n’est pas structuré, ça tourne en rond, et c’est très difficile à suivre
Cela dit, l’information elle-même peut être importante. Il y a une forte insinuation selon laquelle le NIST, avec l’aide de la NSA, aurait délibérément standardisé un algorithme faible
Nous savons tous qu’une telle chose est possible
Mais si quelqu’un suit ce domaine de plus près, j’aimerais qu’il explique ce que signifient les chiffres ici. J’ai toujours pensé qu’affaiblir ainsi la cryptographie publique était un pari risqué, puisqu’on ne peut pas garantir qu’un attaquant ne découvrira pas indépendamment le même fait. Une clé secrète de backdoor peut être cachée. C’était le soupçon à l’époque de Dual_EC_DRBG. Mais les résultats mathématiques sont vraiment difficiles à cacher
Pourquoi auraient-ils voulu prendre ce risque ici ?
Je ne vois même plus pourquoi cette discussion est nécessaire. Nous n’avons plus besoin d’eux. Les restrictions à l’exportation ont disparu
Ce qu’il faut, c’est un consortium capable d’attirer l’attention des fabricants de matériel, et de limiter le NIST et la NSA à un simple statut de participants. Ainsi, même si le gouvernement adopte des standards backdoorés, il sera le seul à les utiliser
Pourquoi cela l’intéresserait-elle ?
C’est l’hypothèse actuelle sur ce qui a pu se passer avec les courbes elliptiques du NIST
Dans ce cas, cela peut devenir, en pratique et pendant très longtemps, une backdoor réservée aux États-Unis
L’idée était qu’ils pourraient garder une longueur d’avance dans les attaques, et que DES serait remplacé par autre chose au moment où les clés de 56 bits deviendraient généralement trop faibles. Était-ce risqué ? Oui. Mais, d’une certaine manière, cela a « réussi ». Je ne supposerais donc pas qu’une chose similaire ne se reproduira jamais
La théorie sous-jacente s’appelle la kleptographie. Cela implique aussi que la NSA est assez délirante pour croire qu’elle peut voler des informations « en toute sécurité »
Il y avait eu l’an dernier un fil lié avec 443 commentaires
https://news.ycombinator.com/item?id=32360533 ("NSA, NIST, and post-quantum crypto: my second lawsuit against the US government (cr.yp.to)")
« Découvrir le fonctionnement secret de NISTPQC. En mars 2022, j’ai déposé une demande FOIA intitulée “NSA, NIST, and post-quantum cryptography”. Le NIST a enfreint la loi et a fait traîner les choses. Le cabinet d’avocats spécialisé dans les droits civiques Loevy & Loevy a intenté une action en justice en mon nom »
Personnellement, je n’aime généralement pas djb, mais professionnellement il a régulièrement mis la pression sur le gouvernement fédéral devant les tribunaux, donc je le soutiens toujours. Je suis très heureux de voir qu’il continue
Indépendamment du fait que DJB est une figure importante de la cryptographie, et du fait que j’ignore beaucoup de détails ici, il y a eu un point où sa crédibilité a fortement baissé à mes yeux
En particulier, dans la partie sur les graphiques, il dit que « le NIST a choisi d’utiliser des barres rouges plus fines dans le graphique de bande passante afin de les mettre moins en avant », mais les éléments avancés ne le démontrent pas du tout. Il existe une explication bien plus plausible. Le graphique où les barres sont plus fines est un graphique en barres avec davantage de points de données que les autres. Ouvrez n’importe quel outil de création de graphiques et comparez un graphique avec 12 points de données à un autre avec 9 : il est normal que les barres du premier soient plus fines. À ce moment-là, j’ai vraiment eu l’impression qu’il cherchait à interpréter chaque action de la façon la plus malveillante possible
Dans le point suivant, il se plaint de l’absence d’axe logarithmique, alors que les valeurs se situent dans le même ordre de grandeur. Cela ne ressemble pas à un bon cas d’usage pour un axe logarithmique, et je ne vois pas très bien comment cela pourrait se justifier ici
Quand on sait que DJB a participé à NTRU, il est difficile de ne pas y voir en grande partie une réaction amère à une défaite dans la compétition
Toute autre hypothèse me semble, au moins à moi, assez naïve
Il y a largement de quoi être soupçonneux
Il est normal que les concurrents de ce domaine examinent mutuellement leurs travaux
Ce que j’ai appris en observant professionnellement les bagarres explosives entre cryptographes : ne pariez pas contre Bernstein, et ne faites pas confiance au NIST
Le NIST a répondu : https://groups.google.com/a/list.nist.gov/g/pqc-forum/c/W2VO...
Je ne sais pas très bien s’il reste une quelconque crédibilité à N(IST)SA
Il est encourageant que curve25519 soit plus largement utilisée que leurs courbes P, et j’espère que la communauté continuera dans cette direction en les ignorant largement à l’avenir
Le gouvernement ne devrait ni diriger ni décider. Pour FIPS, la régulation, etc., il vaudrait mieux organiser les choses principalement autour d’un rôle de collecte et de suivi du consensus actuel