HIC Is All You Need : PAPKE post-quantique expliqué

Les mots de passe sont souvent vus comme la partie ancienne de la sécurité : utiles, familiers et fragiles. Le chiffrement à clé publique est vu comme la partie moderne : puissant, asynchrone, mais dépendant de clés publiques authentiques.

Password-Authenticated Public-Key Encryption relie ces deux idées. Cet article explique le primitif PAPKE original, pourquoi il ne se réduit pas au chiffrement d'un fichier avec un mot de passe, et comment cet article scientifique, HIC Is All You Need, rend la construction plus pratique dans un cadre post-quantique.

Le problème : les clés publiques doivent encore être authentifiées

Le chiffrement à clé publique résout un problème : un expéditeur peut chiffrer vers la clé publique d'un destinataire. Il en laisse un autre ouvert : comment l'expéditeur sait-il qu'il s'agit vraiment de la clé publique du destinataire ?

Dans les systèmes déployés, cette authenticité vient généralement d'une PKI, de certificats, d'un annuaire de confiance, d'un fournisseur de messagerie ou d'une comparaison manuelle d'empreintes. Ces mécanismes sont utiles, mais ils ne sont pas toujours disponibles, simples ou souhaitables.

Password-Authenticated Public-Key Encryption, ou PAPKE, demande si un court mot de passe partagé peut authentifier une clé publique sans transformer cette clé ou les chiffrés ultérieurs en outil de vérification hors ligne du mot de passe.

Ce que PAPKE ajoute

L'article PAPKE original de Bradley, Camenisch, Jarecki, Lehmann, Neven et Xu a introduit Password-Authenticated Public-Key Encryption comme primitif combinant chiffrement à clé publique et authentification par mot de passe.

À haut niveau, PAPKE permet au destinataire de publier une clé publique réutilisable authentifiée par un mot de passe partagé et mémorisable. Un expéditeur qui connaît ce mot de passe peut utiliser cette clé publique authentifiée et chiffrer un message de manière asynchrone.

Un attaquant qui remplace ou modifie cette clé publique ne devrait pas pouvoir monter une attaque de l'homme du milieu, sauf s'il peut deviner le mot de passe en ligne. En même temps, la seule observation de la clé publique authentifiée ou des chiffrés ne devrait pas permettre de tester des mots de passe hors ligne.

La limite est essentielle : l'authentification de la clé publique n'est aussi forte que le mot de passe partagé. PAPKE n'est pas une solution magique contre les mots de passe faibles ou réutilisés. Si le mot de passe est révélé plus tard, un attaquant peut reconnaître la clé publique authentifiée et envoyer de nouveaux messages chiffrés au destinataire, mais cela ne déchiffre pas à lui seul les messages déjà chiffrés ; ceux-ci dépendent toujours de la clé secrète du destinataire et de la sécurité du schéma de chiffrement sous-jacent.

• Clé publique réutilisable : le destinataire peut publier une clé publique authentifiée par mot de passe une seule fois et recevoir des messages chiffrés plus tard.
• Communication asynchrone : l'expéditeur peut chiffrer sans exécuter d'abord un échange de clés interactif avec le destinataire.
• Authentification par mot de passe : le mot de passe authentifie la clé publique acceptée ; il n'est pas traité comme une clé de chiffrement à haute entropie.
• Résistance au dictionnaire hors ligne : la clé publique authentifiée et les chiffrés ne doivent pas devenir des vérificateurs de mot de passe bon marché.

Comment PAPKE fonctionne à haut niveau

Un bon modèle mental consiste à séparer PAPKE en configuration et chiffrement.

Pendant la configuration, le destinataire crée une paire de clés de chiffrement à clé publique. La clé publique est ensuite transformée ou protégée avec le mot de passe partagé, afin qu'un expéditeur qui connaît le mot de passe puisse récupérer ou valider la bonne clé publique.

Pendant le chiffrement, l'expéditeur utilise le mot de passe pour traiter la clé publique authentifiée. Si le mot de passe est correct, il obtient la vraie clé publique de chiffrement et chiffre normalement. Si le mot de passe est faux, le processus ne doit pas révéler assez d'information pour tester des hypothèses hors ligne.

C'est différent du chiffrement symétrique ordinaire basé sur un mot de passe. Si un attaquant obtient un chiffré protégé par mot de passe, il peut essayer un mot de passe, dériver une clé, déchiffrer, puis vérifier si le résultat ressemble à du texte normal. C'est un test de dictionnaire hors ligne. PAPKE conserve la structure du chiffrement à clé publique, mais utilise le mot de passe pour authentifier la clé publique tout en empêchant la clé authentifiée ou les chiffrés de devenir un oracle bon marché de vérification du mot de passe.

Pourquoi la construction originale utilise un chiffrement idéal

La construction PAPKE générique de l'article original utilise un schéma de chiffrement à clé publique anonyme et sécurisé CCA, avec un chiffrement idéal sur le domaine des clés publiques.

Cela crée une tension inhabituelle. Dans le chiffrement à clé publique ordinaire, la clé publique est faite pour être publique : tout le monde peut la connaître, la copier et chiffrer vers elle. Dans PAPKE, la vraie clé publique garde ce rôle après authentification, mais la clé publique authentifiée par mot de passe ne doit pas révéler assez de structure pour permettre à un attaquant de tester des mots de passe.

L'intuition est que le mot de passe cache ou transforme la clé publique de manière à ce qu'elle paraisse aléatoire pour quelqu'un qui ne connaît pas le mot de passe. Le modèle de chiffrement idéal est une abstraction théorique propre pour cette opération.

Cette abstraction est utile dans une preuve, mais difficile à instancier. Les chiffrements par blocs standards opèrent sur des blocs fixes comme 128 bits, alors que les clés publiques modernes, surtout post-quantiques, sont des objets structurés beaucoup plus grands.

Pourquoi le PAPKE post-quantique est plus difficile

De nombreuses constructions PAPKE et PAKE classiques reposent sur une algèbre de type Diffie-Hellman. De grands ordinateurs quantiques tolérants aux fautes casseraient les hypothèses derrière ces groupes classiques, et des estimations récentes rendent la pression de migration plus concrète. Un livre blanc de Google Quantum AI estime que l'algorithme de Shor contre les logarithmes discrets sur courbes elliptiques 256 bits pourrait s'exécuter en quelques minutes sur certaines architectures futures à horloge rapide avec moins d'un demi-million de qubits physiques. Un préprint Oratomic/Caltech soutient que des codes correcteurs à haut taux et des qubits atomiques reconfigurables pourraient ramener des instances cryptographiquement pertinentes de Shor dans une plage de 10 000 à 100 000 qubits, avec des temps d'exécution plus longs. Ce sont des estimations de ressources, pas des attaques déployées, mais elles expliquent pourquoi la migration post-quantique est traitée comme urgente.

L'idée naturelle est de remplacer le chiffrement à clé publique sous-jacent par un PKE ou un KEM post-quantique. Mais ce n'est pas un simple remplacement technique. La construction doit toujours authentifier les clés publiques par mot de passe sans fuite de structure ni attaque par dictionnaire hors ligne.

C'est là que la taille et la structure des clés post-quantiques deviennent importantes. Si la construction attend un chiffrement idéal sur le domaine des clés publiques, et que ces clés sont de grands objets de réseaux ou de codes, l'instanciation efficace de ce chiffrement devient un obstacle central.

HIC Is All You Need

Dans cet article, Arriaga, Mestel, Oupicky, Ronne, Skrobot et al. proposent une manière de contourner cet obstacle.

Au lieu d'exiger un chiffrement idéal complet sur le domaine des clés publiques, la construction utilise un Half-Ideal Cipher, ou HIC. HIC a été introduit dans un travail EUROCRYPT 2023 antérieur comme relaxation d'un chiffrement idéal suffisante pour certains protocoles authentifiés par mot de passe.

L'idée est pragmatique : ne pas instancier un objet idéalisé plus fort que ce que la preuve exige réellement. Si un objet plus faible et plus efficacement réalisable suffit, la construction post-quantique devient beaucoup plus plausible.

La construction obtenue, PAPKE-HIC, est présentée comme un schéma PAPKE sécurisé UC construit à partir d'un schéma de chiffrement à clé publique et d'un HIC.

Ce dont la variante post-quantique a besoin

L'article HIC ne dit pas que n'importe quel schéma de chiffrement post-quantique peut être utilisé aveuglément. Il conserve le besoin original d'un chiffrement à clé publique anonyme et sécurisé CCA, et resserre un point de la preuve PAPKE-IC.

À haut niveau, le schéma de chiffrement doit se comporter assez bien pour que les clés publiques authentifiées par mot de passe et les chiffrés ne fuient pas la mauvaise information et ne créent pas de comportement de déchiffrement ambigu.

• Sécurité CCA : le PKE sous-jacent doit rester confidentiel même face à des attaques adaptatives par chiffrés choisis. C'est plus fort et plus précis que de dire simplement que les chiffrés sont difficiles à inverser.
• Anonymat des chiffrés : un chiffré ne doit pas révéler sous quelle clé publique il a été produit, même si l'attaquant connaît les clés candidates.
• Clés publiques pseudo-uniformes : les clés publiques générées doivent être difficiles à distinguer de la distribution de clés que la construction HIC manipule.
• Robustesse de déchiffrement : un chiffré ne doit pas se déchiffrer validement en messages contradictoires sous différentes clés secrètes de manière à casser la preuve du protocole. L'article capture la version nécessaire avec DROB-CCA et la relie à des notions de robustesse plus fortes.

Instanciations concrètes

L'article rend ensuite la construction concrète. Il étudie PAPKE-HIC construit sur une couche de chiffrement KEM+DEM avec ML-KEM, FrodoKEM et Classic McEliece. ML-KEM et FrodoKEM s'insèrent dans l'analyse grâce à la transformation Fujisaki-Okamoto avec hachage de préfixe, qui donne une route directe vers la propriété de robustesse de déchiffrement requise. Classic McEliece est plus délicat : l'article discute une variante modifiée et une transformation par hachage de la clé publique comme moyen plus boîte noire d'obtenir la robustesse nécessaire. Le code de benchmark est public dans le dépôt PAPKE-HIC benchmarks, implémenté en C++ avec Botan pour les primitives cryptographiques et Catch2 pour les mesures. Les benchmarks montrent l'intérêt pratique de HIC : pour ML-KEM, PAPKE-HIC nécessite une seule opération hash-to-group là où PAPKE-IC en exige plusieurs ; pour le chiffrement Classic McEliece, la variante HIC est rapportée à environ 0,26x le temps de la variante PAPKE-IC avec Feistel à 8 tours.

Le sens pratique

La promesse de PAPKE est un chiffrement asynchrone sans PKI basé sur un mot de passe partagé. Cela convient aux situations où deux personnes peuvent convenir d'un mot de passe mais ne veulent pas dépendre de certificats, de fournisseurs de comptes ou de comparaisons manuelles d'empreintes.

La promesse de PAPKE-HIC est de déplacer cette idée vers le cadre post-quantique. Au lieu de dépendre d'hypothèses Diffie-Hellman, la construction peut être instanciée avec des outils de chiffrement à clé publique post-quantiques adaptés.

La limite est que c'est de la conception de protocole cryptographique, pas une simple fonctionnalité applicative. La sécurité ne vient pas du simple mélange d'un mot de passe avec une clé publique. Elle vient d'un primitif soigneusement spécifié, d'un modèle de preuve et d'exigences précises sur le schéma de chiffrement sous-jacent et la transformation HIC de la clé publique.

À retenir

PAPKE est utile parce qu'il traite les mots de passe comme un outil d'authentification des clés publiques, tout en cherchant à empêcher les attaques par dictionnaire hors ligne.

Le travail PAPKE original définit le primitif et son lien avec PAKE. HIC Is All You Need montre comment l'idée PAPKE générique peut devenir pratique dans une direction post-quantique en remplaçant un composant difficile de chiffrement idéal par une construction Half-Ideal Cipher.

En termes simples : les mots de passe peuvent authentifier des clés publiques, le chiffrement à clé publique peut permettre des messages asynchrones, et les variantes post-quantiques deviennent réalistes quand la transformation de clé publique utilise la bonne abstraction cryptographique.

Références

• Bradley et al.: Password-Authenticated Public-Key Encryption
• Arriaga, Mestel, Oupicky, Ronne, Skrobot: HIC Is All You Need
• Freitas Dos Santos, Gu, Jarecki: Randomized Half-Ideal Cipher on Groups
• Babbush et al.: Securing Elliptic Curve Cryptocurrencies against Quantum Vulnerabilities
• Cain et al.: Shor's algorithm is possible with as few as 10,000 reconfigurable atomic qubits
• PAPKE-HIC benchmark implementation repository