Cryptographie post-quantique - nouvel algorithme "disparu en 60 minutes"

Nous avons écrit sur PQC, abréviation de cryptographie post-quantique, plusieurs fois auparavant.

Au cas où vous auriez manqué tout l'engouement médiatique de ces dernières années pour l'informatique dite quantique…

…c'est (si vous me pardonnerez ce que certains experts considéreront probablement comme une simplification excessive et imprudente) un moyen de construire des dispositifs informatiques capables de suivre plusieurs issues possibles d'un calcul en même temps.

Avec beaucoup de soin, et peut-être un peu de chance, cela signifie que vous pouvez réécrire certains types d'algorithmes pour vous concentrer sur la bonne réponse, ou au moins éliminer correctement toute une série de mauvaises réponses, sans essayer de tester tous les résultats possibles. un par un.

Deux accélérations cryptanalytiques intéressantes sont possibles à l'aide d'un dispositif informatique quantique, en supposant qu'un dispositif suffisamment puissant et fiable puisse réellement être construit :

• Algorithme de recherche quantique de Grover. Habituellement, si vous souhaitez rechercher un ensemble de réponses ordonnées au hasard pour voir si la vôtre figure sur la liste, vous vous attendez à parcourir toute la liste, au pire, avant d'obtenir une réponse définitive. Par exemple, si vous vouliez trouver la clé de déchiffrement AES 128 bits pour déchiffrer un document, vous devez rechercher la liste de toutes les clés possibles, en commençant par 000..001, ..2, ..3, et ainsi de suite, jusqu'à FFF..FFF (16 octets de FF), pour être certain de terminer le problème. En d'autres termes, vous devez prévoir un budget pour essayer les 2¹²⁸ clés possibles avant de trouver la bonne clé ou de déterminer qu'il n'y en avait pas. L'algorithme de Grover, cependant, étant donné un ordinateur quantique suffisamment grand et puissant, prétend être capable de réaliser le même exploit avec le racine carrée de l'effort habituel, déchiffrant ainsi le code, en théorie, en seulement 2⁶⁴ essaie à la place.
• Algorithme de factorisation quantique de Shor. Plusieurs algorithmes de cryptage contemporains reposent sur le fait que la multiplication de deux grands nombres premiers ensemble peut être effectuée rapidement, alors que diviser leur produit en deux nombres avec lesquels vous avez commencé est pratiquement impossible. Pour avoir une idée de cela, essayez de multiplier 59 × 87 en utilisant un stylo et du papier. Cela peut prendre environ une minute pour le sortir (5133 est la réponse), mais ce n'est pas si difficile. Essayez maintenant dans l'autre sens. Divisez, disons, 4171 en ses deux facteurs. Plus dur! (C'est 43 × 97.) Maintenant, imaginez faire cela avec un nombre de 600 chiffres. En gros, vous êtes obligé d'essayer de diviser le nombre à 600 chiffres par chaque nombre premier à 300 chiffres possible jusqu'à ce que vous touchiez le jackpot ou que vous trouviez qu'il n'y a pas de réponse. L'algorithme de Shor, cependant, promet de résoudre ce problème avec le logarithme de l'effort habituel. Ainsi, la factorisation d'un nombre de 2048 chiffres binaires devrait prendre juste deux fois plus de temps que la factorisation d'un nombre de 1024 bits, et non deux fois plus longtemps que la factorisation d'un nombre de 2047 bits, ce qui représente une énorme accélération.

Contrer la menace

La menace de l'algorithme de Grover peut être contrée simplement en augmentant la taille des nombres que vous utilisez en les mettant au carré, ce qui signifie doubler le nombre de bits dans votre hachage cryptographique ou votre clé de chiffrement symétrique. (En d'autres termes, si vous pensez que SHA-256 est bon en ce moment, utiliser SHA-512 à la place fournirait une alternative résistante au PQC.)

Mais l'algorithme de Shor ne peut pas être contré aussi facilement.

Une clé publique de 2048 bits aurait besoin d'une taille augmentée de façon exponentielle, pas simplement au carré, de sorte qu'au lieu d'une clé de 2×2048=4096 bits, soit il faudrait une nouvelle clé avec la taille impossible de 2²⁰⁴⁸ morceaux…

… ou vous devriez adopter un tout nouveau type de système de cryptage post-quantique auquel l'algorithme de Shor ne s'applique pas.

Eh bien, l'organisme de normalisation américain NIST a mené une PQC "concours" depuis fin 2017.

Le processus a été ouvert à tous, tous les participants étant les bienvenus, tous les algorithmes publiés ouvertement et un examen public non seulement possible mais activement encouragé:

Appel à propositions. [Fermé le 2017/11/30]. […] Il est prévu que les nouvelles normes de cryptographie à clé publique spécifient un ou plusieurs algorithmes supplémentaires de signature numérique, de chiffrement à clé publique et d'établissement de clé non classifiés et divulgués publiquement, disponibles dans le monde entier et capables de protéger les informations sensibles du gouvernement. dans un avenir prévisible, y compris après l'avènement des ordinateurs quantiques.

Après trois séries de soumissions et de discussions, Le NIST a annoncé, le 2022/07/05, qu'elle avait choisi quatre algorithmes qu'elle considérait comme des « standards » avec effet immédiat, tous aux noms à consonance délicieuse : CRYSTALS-KYBER, CRYSTALS-Dilithium, FALCONet SPHINCS+.

Le premier (CRYSTALS-KYBER) est utilisé comme ce qu'on appelle un Mécanisme d'accord clé (KEM), où les deux extrémités d'un canal de communication public concoctent en toute sécurité une clé de cryptage privée à usage unique pour échanger en toute confidentialité les données d'une session. (Tout simplement: les espions n'obtiennent que du chou râpé, de sorte qu'ils ne peuvent pas écouter la conversation.)

Les trois autres algorithmes sont utilisés pour Signatures numériques, grâce auquel vous pouvez vous assurer que les données que vous avez envoyées de votre côté correspondent exactement à ce que l'expéditeur a mis de l'autre, empêchant ainsi la falsification et garantissant l'intégrité. (Tout simplement: si quelqu'un essaie de corrompre ou de manipuler les données, vous le saurez.)

Plus d'algorithmes nécessaires

Parallèlement à l'annonce des nouvelles normes, le NIST a également annoncé une quatrième tour de ses concurrents, mettant en avant quatre autres algorithmes en tant que KEM alternatifs possibles. (Rappelez-vous qu'au moment de la rédaction de cet article, nous avons déjà le choix entre trois algorithmes de signature numérique approuvés, mais un seul KEM officiel.)

C'étaient: BIKE, Classic McEliece, HQC ainsi que SIKE.

Curieusement, le Algorithme de McEliece a été inventé dans les années 1970 par le cryptographe américain Robert Mc Eliece, décédé en 2019, bien après que le concours du NIST était déjà en cours.

Cependant, il n'a jamais fait son chemin, car il nécessitait d'énormes quantités de matériel clé par rapport à l'alternative populaire de l'époque, l'algorithme Diffie-Hellman-Merkle (DHM, ou parfois simplement DH).

Malheureusement, l'un des trois algorithmes du Round Four, à savoir SIKE, semble avoir été fissuré.

Dans un article casse-tête intitulé UNE ATTAQUE DE RÉCUPÉRATION DE CLÉ EFFICACE SUR SIDH (VERSION PRÉLIMINAIRE), les cryptographes belges Wouter Castryk et Thomas Decru semblent avoir porté un coup fatal à l'algorithme SIKE

Au cas où vous vous poseriez la question, SIKE est l'abréviation de Encapsulation de clé d'isogénie supersingulière, et SIDH signifie Isogénie supersingulière Diffie-Hellman, une utilisation spécifique de la Algorithme SIKE par lequel les deux extrémités d'un canal de communication exécutent une « cryptodance » de type DHM pour échanger un ensemble de données publiques qui permet à chaque extrémité de dériver une valeur privée à utiliser comme clé de cryptage secrète à usage unique.

Nous n'allons pas essayer d'expliquer l'attaque ici; nous allons juste répéter ce que le papier prétend, à savoir que :

En termes très vagues, les entrées ici incluent les données publiques fournies par l'un des participants à la cryptodanse de l'établissement clé, ainsi que les paramètres prédéterminés (et donc connus du public) utilisés dans le processus.

Mais la sortie qui est extraite (les informations appelées l'isogénie φ ci-dessus) est censée être la partie jamais révélée du processus - la soi-disant clé privée.

En d'autres termes, à partir des seules informations publiques, telles que les données échangées ouvertement lors de la configuration de la clé, les cryptographes prétendent pouvoir récupérer la clé privée de l'un des participants.

Et une fois que vous connaissez ma clé privée, vous pouvez facilement et de manière indétectable prétendre être moi, de sorte que le processus de cryptage est interrompu.

Apparemment, l'algorithme de craquage de clé prend environ une heure pour faire son travail, en utilisant un seul cœur de processeur avec le type de puissance de traitement que vous trouveriez dans un ordinateur portable de tous les jours.

Cela va à l'encontre de l'algorithme SIKE lorsqu'il est configuré pour répondre au niveau 1, le niveau de sécurité de cryptage de base du NIST.

Que faire?

Rien!

(C'est la bonne nouvelle.)

Comme le suggèrent les auteurs de l'article, après avoir noté que leur résultat est encore préliminaire, "Avec l'état actuel des choses, SIDH semble être complètement cassé pour toute courbe de base générée publiquement."

(C'est la mauvaise nouvelle.)

Cependant, étant donné que l'algorithme SIKE n'est pas encore officiellement approuvé, il peut maintenant être soit adapté pour contrecarrer cette attaque particulière (ce que les auteurs admettent être possible), soit simplement abandonné complètement.

Quoi qu'il arrive finalement à SIKE, c'est un excellent rappel des raisons pour lesquelles essayer d'inventer vos propres algorithmes de chiffrement est semé d'embûches.

C'est aussi un exemple pointu de la raison pour laquelle les systèmes de cryptage propriétaires qui reposent sur le secret de l'algorithme lui-même pour maintenir leur sécurité sont tout simplement inacceptables en 2022.

Si un algorithme PQC tel que SIKE survivait à la persuasion et à l'investigation d'experts du monde entier pendant plus de cinq ans, bien qu'il ait été divulgué spécifiquement pour qu'il puisse être soumis à un examen public…

…alors il n'est pas nécessaire de vous demander si vos algorithmes de cryptage maison et cachés à la vue sont susceptibles de fonctionner lorsqu'ils sont diffusés dans la nature !

---