On a déjà parlé ici d’algorithmes de cryptographie post-quantique (PQC, Post-Quantum Cryptography) récemment sélectionné par le NIST pour être standardisés.
La compétition PQC du NIST ne s’arrête pas là, néanmoins. Quatre algorithmes ont déjà été promus à la standardisation (KYBER, DILITHIUM, FALCON, et SPHINCS+) à l’issue du troisième tour de la compétition, mais celle-ci continue et d‘autres algorithmes sont toujours en lice pour un quatrième tour.
L’un de ces algorithmes est SIKE (Supersingular Isogeny Key Encapsulation). Il est basé sur SIDH (Supersingular Isogeny Diffie-Hellman key exchange), une variante du protocole Diffie-Hellman. Il a été proposé initialement en 2011 et était globalement bien considéré.
Jusqu’à ce weekend.
Deux cryptanalystes de l’Université Catholique (néerlandophone) de Louvain , Wouter Castryck et Thomas Decru, viennent en effet de publier une attaque dévastatrice (le lien ci-dessus). Une attaque totalement praticable, qui permet, avec un seul cœur de processeur même pas quantique, d’obtenir la clef privée d’une des parties communiquantes en l’espace de quelques heures.
SIKE est donc aujourd’hui complètement cassé (et Castryck et Decru sont a priori éligibles à recevoir le prix de $50 000 offert par Microsoft). Il n’est pas encore clair si l’algorithme plus général SIDH peut toujours être sauvé.
Ça me fait prendre conscience que les algorithmes de cryptographie post-quantiques ne sont pas basés sur un accroissement de la complexité algorithmique mais sur la recherche d'algorithmes inaccessibles par nature aux ordinateurs quantiques. Mais bien sûr, se mettre à l'abri des ordinateurs quantiques n'a d'intérêt que si on reste aussi à l'abri des ordinateurs classiques…
Dans le même genre, on a aussi eu RAINBOW, un algorithme de signature qui était parmi les finalistes du troisième tour de la compétition PQC… avant d’être complètement cassé il y a quelques mois par une attaque au titre un brin moqueur (« un ordinateur portable et un week-end suffisent à casser RAINBOW »).
On peut évidemment se féliciter que ces attaques (contre RAINBOW ou contre SIKE) apparaissent pendant la compétition (où il est encore temps d’éliminer ces algorithmes) plutôt qu’après la sélection éventuelle d’un de ces algorithmes.
On peut même dire que c’est un des rôles de la compétition que de stimuler la cryptanalyse des algorithmes candidats, et là-dessus il semble clair que la compétition a bien eu l’effet escompté : RAINBOW a été décrit pour la première fois en 2005, SIDH en 2011, et pendant des années ils sont apparus comme solides. Commence la compétition du NIST en 2017, et quelques années après les attaques efficaces arrivent, ce n’est sûrement pas un hasard.
Sauf que quand même, je trouve un peu inquiétant que des algorithmes soient complètement et pratiquement cassés alors qu’ils sont au stade final de la compétition.
Si l’on compare avec la compétition AES, à ma connaissance aucun des finalistes de la compétition (RIJNDAEL, SERPENT, TWOFISH, RC6, MARS) n’a jamais été pratiquement cassé. Ils ont eu leurs lots d’attaques théoriques, certes (y compris et peut-être même surtout le vainqueur RIJNDAEL), mais jamais d’attaque pratique et dévastatrice du genre de celles dont on parle ici. Pareil à ma connaissance pour les compétitions CAESAR (sélection de modes de chiffrement authentifié), SHA-3 (sélection d’algorithmes de condensation), ou PHC (sélection d’algorithmes de condensation de mot de passe).
the maturity level of the post-quantum algorithms presented to the NIST process should not be overestimated. Many aspects lack cryptanalytical hindsight or are still research topics
Ça conduit certains spécialistes sur Twitter à penser que le domaine de la cryptographie post-quantique manque de maturité.
Est-ce surprenant ? La compétition AES a été lancée en 1997, et terminée en 2000. Diffie-Hellman date de 1976. Il y a eu 20 ans. Et Diffie-Hellman n'est pas sorti de nulle part, ça fait des siècles qu'on fait de la cryptographie… classique. Pendant ce temps-là, le premier algorithme cryptographique qui a donné de l'intérêt à l'ordinateur quantique, c'est Shor en 1994. Y a même pas 30 ans. Et depuis, on n'en est qu'à la théorie, un peu comme Turing : on sait que ça va être possible un jour, mais aucun moyen de l'appliquer réellement.
C'est très bien de s'y pencher maintenant, mais faut pas en attendre la lune non plus ! La recherche, ça prend du temps. Beaucoup. De la chance, un tout petit peu. Et des génies un peu fous aussi.
C’est bien là le problème (et c’est plus ou moins ce que dit l’ANSSI) : le domaine en est encore au stade de la recherche théorique, mais le NIST lui en est au stade de la standardisation, et il y a de quoi se demander si ce n’est pas beaucoup trop tôt.
C'est très bien de s'y pencher maintenant mais faut pas en attendre la lune non plus !
Dès lors qu’il est question de standardisation, on devrait au moins en attendre des algorithmes au moins aussi résistant à des attaques non-quantiques que les algorithmes que l’on a déjà ! Que des finalistes s’avèrent être des trucs que je peux craquer sur mon vieux portable en tâche de fond pendant que je moule sur DLFP, ça n’inspire pas vraiment confiance…
En même temps, un domaine n’acquiert pas de la maturité en restant dans les cartons … au pire on a pas d’ordinateurs quantiques avant des décennies et il y a bien le temps de standardiser d’autres algos (qui risquent finalement d’être cassés par les vraies machines quantiques :p )
D’ici là bon on peut dormir tranquille. Une compet de ce style offre au moins la possibilité de tester des idées qui seraient peut-être restées bien plus confidentielles sinon, il y a des chances qu’au final ça fasse progresser le domaine et fasse émerger de nouvelles idées. Après j’imagine que les (des) gens publieront quand même les attaques après la publication.
Posté par aiolos .
Évalué à 6.
Dernière modification le 01 août 2022 à 09:32.
La compétition AES a été lancée en 1997, et terminée en 2000. Diffie-Hellman date de 1976. Il y a eu 20 ans.
AES et Diffie-Hellman n'ont strictement rien à voir. Ces 20 ans ne veulent rien dire pour la solidité d'AES… Bon, tu aurais pu citer le DES dont la publication date de 1975 ;)
Le premier algo de chiffrement asymétrique résistant à l'ordinateur quantique est, à ma connaissance, le chiffrement de McEliece, et il date de 1979… Il est (presque) aussi vieux que RSA !
RSA est théoriquement vulnérable à l'ordinateur quantique, mais on a besoin de millions de qbits, alors que le maximum pratique aujourd'hui est de 1000 (arrangé un à un par un laser).
Donc, pour casser un algo classique avec un ordinateur quantique, il faudra un ordinateur quantique très puissant.
# Contexte
Posté par gouttegd (site web personnel) . Évalué à 10.
On a déjà parlé ici d’algorithmes de cryptographie post-quantique (PQC, Post-Quantum Cryptography) récemment sélectionné par le NIST pour être standardisés.
La compétition PQC du NIST ne s’arrête pas là, néanmoins. Quatre algorithmes ont déjà été promus à la standardisation (KYBER, DILITHIUM, FALCON, et SPHINCS+) à l’issue du troisième tour de la compétition, mais celle-ci continue et d‘autres algorithmes sont toujours en lice pour un quatrième tour.
L’un de ces algorithmes est SIKE (Supersingular Isogeny Key Encapsulation). Il est basé sur SIDH (Supersingular Isogeny Diffie-Hellman key exchange), une variante du protocole Diffie-Hellman. Il a été proposé initialement en 2011 et était globalement bien considéré.
Jusqu’à ce weekend.
Deux cryptanalystes de l’Université Catholique (néerlandophone) de Louvain , Wouter Castryck et Thomas Decru, viennent en effet de publier une attaque dévastatrice (le lien ci-dessus). Une attaque totalement praticable, qui permet, avec un seul cœur de processeur même pas quantique, d’obtenir la clef privée d’une des parties communiquantes en l’espace de quelques heures.
SIKE est donc aujourd’hui complètement cassé (et Castryck et Decru sont a priori éligibles à recevoir le prix de $50 000 offert par Microsoft). Il n’est pas encore clair si l’algorithme plus général SIDH peut toujours être sauvé.
# ça serait ballot
Posté par mahikeulbody . Évalué à 10.
Ça me fait prendre conscience que les algorithmes de cryptographie post-quantiques ne sont pas basés sur un accroissement de la complexité algorithmique mais sur la recherche d'algorithmes inaccessibles par nature aux ordinateurs quantiques. Mais bien sûr, se mettre à l'abri des ordinateurs quantiques n'a d'intérêt que si on reste aussi à l'abri des ordinateurs classiques…
[^] # Re: ça serait ballot
Posté par gouttegd (site web personnel) . Évalué à 5.
Dans le même genre, on a aussi eu RAINBOW, un algorithme de signature qui était parmi les finalistes du troisième tour de la compétition PQC… avant d’être complètement cassé il y a quelques mois par une attaque au titre un brin moqueur (« un ordinateur portable et un week-end suffisent à casser RAINBOW »).
[^] # Re: ça serait ballot
Posté par gouttegd (site web personnel) . Évalué à 10.
Pour élaborer un peu :
On peut évidemment se féliciter que ces attaques (contre RAINBOW ou contre SIKE) apparaissent pendant la compétition (où il est encore temps d’éliminer ces algorithmes) plutôt qu’après la sélection éventuelle d’un de ces algorithmes.
On peut même dire que c’est un des rôles de la compétition que de stimuler la cryptanalyse des algorithmes candidats, et là-dessus il semble clair que la compétition a bien eu l’effet escompté : RAINBOW a été décrit pour la première fois en 2005, SIDH en 2011, et pendant des années ils sont apparus comme solides. Commence la compétition du NIST en 2017, et quelques années après les attaques efficaces arrivent, ce n’est sûrement pas un hasard.
Sauf que quand même, je trouve un peu inquiétant que des algorithmes soient complètement et pratiquement cassés alors qu’ils sont au stade final de la compétition.
Si l’on compare avec la compétition AES, à ma connaissance aucun des finalistes de la compétition (RIJNDAEL, SERPENT, TWOFISH, RC6, MARS) n’a jamais été pratiquement cassé. Ils ont eu leurs lots d’attaques théoriques, certes (y compris et peut-être même surtout le vainqueur RIJNDAEL), mais jamais d’attaque pratique et dévastatrice du genre de celles dont on parle ici. Pareil à ma connaissance pour les compétitions CAESAR (sélection de modes de chiffrement authentifié), SHA-3 (sélection d’algorithmes de condensation), ou PHC (sélection d’algorithmes de condensation de mot de passe).
Ça conduit certains spécialistes sur Twitter à penser que le domaine de la cryptographie post-quantique manque de maturité. Dans la même veine l’ANSSI déclarait déjà en début d’année, dans ses vues sur la transition vers la cryptographie post-quantique que
[^] # Re: ça serait ballot
Posté par Glandos . Évalué à 10.
Est-ce surprenant ? La compétition AES a été lancée en 1997, et terminée en 2000. Diffie-Hellman date de 1976. Il y a eu 20 ans. Et Diffie-Hellman n'est pas sorti de nulle part, ça fait des siècles qu'on fait de la cryptographie… classique. Pendant ce temps-là, le premier algorithme cryptographique qui a donné de l'intérêt à l'ordinateur quantique, c'est Shor en 1994. Y a même pas 30 ans. Et depuis, on n'en est qu'à la théorie, un peu comme Turing : on sait que ça va être possible un jour, mais aucun moyen de l'appliquer réellement.
C'est très bien de s'y pencher maintenant, mais faut pas en attendre la lune non plus ! La recherche, ça prend du temps. Beaucoup. De la chance, un tout petit peu. Et des génies un peu fous aussi.
[^] # Re: ça serait ballot
Posté par gouttegd (site web personnel) . Évalué à 8.
C’est bien là le problème (et c’est plus ou moins ce que dit l’ANSSI) : le domaine en est encore au stade de la recherche théorique, mais le NIST lui en est au stade de la standardisation, et il y a de quoi se demander si ce n’est pas beaucoup trop tôt.
Dès lors qu’il est question de standardisation, on devrait au moins en attendre des algorithmes au moins aussi résistant à des attaques non-quantiques que les algorithmes que l’on a déjà ! Que des finalistes s’avèrent être des trucs que je peux craquer sur mon vieux portable en tâche de fond pendant que je moule sur DLFP, ça n’inspire pas vraiment confiance…
[^] # Re: ça serait ballot
Posté par Thomas Douillard . Évalué à 4.
En même temps, un domaine n’acquiert pas de la maturité en restant dans les cartons … au pire on a pas d’ordinateurs quantiques avant des décennies et il y a bien le temps de standardiser d’autres algos (qui risquent finalement d’être cassés par les vraies machines quantiques :p )
D’ici là bon on peut dormir tranquille. Une compet de ce style offre au moins la possibilité de tester des idées qui seraient peut-être restées bien plus confidentielles sinon, il y a des chances qu’au final ça fasse progresser le domaine et fasse émerger de nouvelles idées. Après j’imagine que les (des) gens publieront quand même les attaques après la publication.
[^] # Re: ça serait ballot
Posté par Misc (site web personnel) . Évalué à 10.
Sauf le domaine très spécifique de la survie à l'intérieur d'un carton.
[^] # Re: ça serait ballot
Posté par aiolos . Évalué à 6. Dernière modification le 01 août 2022 à 09:32.
AES et Diffie-Hellman n'ont strictement rien à voir. Ces 20 ans ne veulent rien dire pour la solidité d'AES… Bon, tu aurais pu citer le DES dont la publication date de 1975 ;)
Le premier algo de chiffrement asymétrique résistant à l'ordinateur quantique est, à ma connaissance, le chiffrement de McEliece, et il date de 1979… Il est (presque) aussi vieux que RSA !
[^] # Re: ça serait ballot
Posté par Nicolas Boulay (site web personnel) . Évalué à 3.
RSA est théoriquement vulnérable à l'ordinateur quantique, mais on a besoin de millions de qbits, alors que le maximum pratique aujourd'hui est de 1000 (arrangé un à un par un laser).
Donc, pour casser un algo classique avec un ordinateur quantique, il faudra un ordinateur quantique très puissant.
"La première sécurité est la liberté"
Suivre le flux des commentaires
Note : les commentaires appartiennent à celles et ceux qui les ont postés. Nous n’en sommes pas responsables.