Un serveur de cassage de mots de passe insensible : Combinaison des tables de Hellman et des protocoles PIR

Table des matières

• 1. Introduction
• 2. Préliminaires
  • 2.1 Tables d'inversion de hachage
  • 2.2 Récupération d'Information Privée
• 3. Vue d'ensemble de la solution
• 4. Détails techniques & Construction de l'algorithme
• 5. Protocoles PIR & Analyse de complexité
• 6. Résultats expérimentaux
• 7. Conclusion & Travaux futurs
• 8. Analyse originale & Commentaire d'expert
• 9. Détails techniques & Formulation mathématique
• 10. Cadre d'analyse & Étude de cas
• 11. Applications futures & Directions
• 12. Références

1. Introduction

Cet article aborde un défi crucial de confidentialité dans les opérations de sécurité offensive : effectuer un cassage de mots de passe via un serveur tiers sans révéler les hachages cibles. Le scénario implique un testeur d'intrusion avec des ressources locales limitées (par exemple, un smartphone) qui doit interroger de grandes tables de hachage précalculées (comme les tables Rainbow ou Hellman) hébergées à distance. Le problème central est de construire un serveur de cassage de mots de passe insensible où le serveur ne peut pas apprendre quelles paires mot de passe-hachage le client tente de casser, préservant ainsi le secret opérationnel.

2. Préliminaires

2.1 Tables d'inversion de hachage

Les systèmes de mots de passe stockent souvent des hachages cryptographiques. Les attaquants utilisent des tables précalculées pour inverser ces hachages. Les méthodes clés incluent :

• Tables de Hellman (1980) : Un compromis temps-mémoire utilisant des chaînes de hachages et de mots de passe, ne stockant que les points de début et de fin de chaîne.
• Points Distingués de Rivest (1982) : Une optimisation utilisant des valeurs de hachage spéciales "distinguées" comme points finaux de chaîne pour réduire les recherches.
• Tables Arc-en-ciel (Oeschlin, 2003) : Utilise une fonction de réduction différente à chaque étape de la chaîne, généralement plus rapide mais moins adaptée au modèle de requête PIR proposé.

L'article soutient que les tables de Hellman (ou leurs variantes avec points distingués) sont plus compatibles avec les protocoles PIR que les tables Arc-en-ciel pour cette application spécifique.

2.2 Récupération d'Information Privée

La Récupération d'Information Privée (PIR) permet à un client de récupérer un élément dans une base de données sans que le serveur apprenne quel élément a été consulté. Pour une base de données unique contenant une chaîne de n bits, un schéma PIR implique :

1. Génération de la requête (Client)
2. Transmission de la requête
3. Traitement de la requête (Serveur)
4. Transmission de la réponse
5. Décodage de la réponse (Client)

La complexité est mesurée par $O_C$ (traitement client), $O_S$ (traitement serveur) et $O_T$ (transfert). Une limite inférieure fondamentale est que $O_S$ doit être au moins $O(n)$ pour assurer la confidentialité, ce qui signifie que le serveur doit effectuer un travail proportionnel à la taille de la base de données.

3. Vue d'ensemble de la solution

La solution proposée combine ingénieusement les tables de Hellman (ou tables à points distingués) avec un protocole PIR à base de données unique. Le serveur stocke les tables de cassage précalculées. Lorsqu'un client souhaite casser un hachage, il utilise une requête PIR pour récupérer de manière privée les informations nécessaires depuis les emplacements spécifiques dans les tables de Hellman qui correspondent aux correspondances de chaîne potentielles, sans révéler les indices de recherche.

4. Détails techniques & Construction de l'algorithme

La construction se concentre sur l'adaptation des tables de Hellman pour le PIR. Une table de Hellman est définie par une fonction de hachage cryptographique $H$ et une fonction de réduction $R$. Une chaîne commence par un texte en clair $SP_i$, et calcule itérativement : $X_0 = SP_i$, $X_{j+1} = H(R(X_j))$, ne stockant que $(SP_i, EP_i)$ où $EP_i$ est la valeur finale après $t$ étapes. Pour vérifier un hachage $h$, le client calcule une chaîne de longueur $t$ à partir de $h$, vérifiant à chaque étape si la valeur intermédiaire correspond à un point final stocké. Le protocole PIR est utilisé pour récupérer de manière privée ces comparaisons de points finaux depuis la table du serveur.

5. Protocoles PIR & Analyse de complexité

L'article analyse la surcharge de calcul et de communication. En utilisant un protocole PIR computationnel standard (par exemple, basé sur l'hypothèse de résiduosité quadratique), le coût de traitement côté serveur $O_S$ évolue avec la taille de la table. Le coût client $O_C$ et la communication $O_T$ sont nettement inférieurs mais non négligeables. L'analyse montre que si le PIR introduit une surcharge par rapport à une requête en clair, c'est le prix nécessaire à une forte confidentialité des requêtes. Le choix des tables de Hellman plutôt que des tables Arc-en-ciel est justifié ici car ces dernières nécessitent de vérifier plusieurs colonnes avec différentes fonctions de réduction, conduisant à plus de requêtes PIR et à un coût global plus élevé.

6. Résultats expérimentaux

Un prototype a été implémenté en Python. Les expériences ont démontré la faisabilité de l'approche. Les métriques clés incluaient :

• Temps de requête : Le temps de bout en bout pour une tentative de cassage insensible, prenant en compte le calcul PIR et la latence de communication.
• Charge serveur : La charge de calcul sur le serveur par requête, confirmant la borne théorique $O(n)$.
• Taux de réussite : La probabilité de casser avec succès un hachage compte tenu de la couverture de la table, qui correspond aux probabilités de réussite standard des tables de Hellman.

Les résultats ont validé que le système fonctionne mais ont mis en évidence le compromis de performance : la confidentialité se fait au prix d'une augmentation du calcul serveur par requête par rapport à un service non privé.

7. Conclusion & Travaux futurs

L'article démontre avec succès une architecture novatrice pour un serveur de cassage de mots de passe insensible. Les directions de travaux futurs incluent :

• Explorer des protocoles PIR plus efficaces pour réduire $O_S$ et $O_T$.
• Étudier l'utilisation d'Environnements d'Exécution de Confiance (TEE) comme Intel SGX comme alternative ou complément au PIR cryptographique.
• Étendre le modèle à des configurations PIR distribuées ou multi-serveurs pour potentiellement améliorer les performances.

8. Analyse originale & Commentaire d'expert

Idée centrale : Cet article ne vise pas à casser les mots de passe plus vite ; il vise à les casser plus discrètement. Les auteurs ont identifié une lacune opérationnelle flagrante en sécurité offensive : l'empreinte numérique. Lorsqu'un membre d'une équipe rouge interroge un service de cassage basé sur le cloud, ces métadonnées de requête sont un risque. Ce travail propose de chiffrer l'intention elle-même en utilisant le PIR, rendant le serveur "insensible". C'est un exemple classique d'application d'une théorie cryptographique avancée (PIR) à un problème concret et réel de sécurité informatique. L'importance est similaire aux considérations de confidentialité dans les attaques par inversion de modèle ou les attaques par inférence d'appartenance contre les API d'apprentissage automatique, où la requête elle-même peut fuiter des informations sensibles.

Flux logique : L'argumentation est logiquement solide. 1) Définir le modèle de menace : un serveur tiers non fiable. 2) Sélectionner la primitive cryptographique appropriée : le PIR computationnel à base de données unique, qui est la seule option viable pour ce scénario à serveur unique sans collusion. 3) Adapter la primitive de cassage : Choisir les tables de Hellman plutôt que les tables Arc-en-ciel car leur structure nécessite moins de requêtes PIR, plus déterministes, par tentative de cassage. C'est une décision d'ingénierie cruciale qui montre une connaissance approfondie du domaine. Le flux allant du problème à l'outil cryptographique, puis à l'intégration système, est cohérent.

Forces & Faiblesses : La force majeure est la nouveauté et l'applicabilité directe. Le prototype prouve la viabilité du concept. Cependant, les faiblesses sont pratiques. La surcharge de performance du PIR est massive. Comme le notent les auteurs, le travail serveur est $O(n)$. Pour de grandes tables (téraoctets), cela est prohibitif pour un service commercial. C'est une solution qui privilégie une confidentialité parfaite au détriment de toute apparence d'efficacité. De plus, elle ne protège que la requête. Le serveur sait toujours que le client effectue une opération de cassage, ce qui peut suffire à déclencher des alertes dans certaines juridictions. Comparée aux approches par chiffrement complètement homomorphe (FHE) qui émergent, cette méthode basée sur le PIR est plus simple mais beaucoup moins flexible.

Perspectives exploitables : Pour les praticiens de la sécurité, c'est un plan pour des outils offensifs à haute assurance préservant la vie privée. Pour les chercheurs, cela ouvre une voie de travail sur le PIR efficace et utilisable. La prochaine étape immédiate est de comparer cette approche à une approche basée sur les TEE (par exemple, exécuter la logique de cassage dans une enclave SGX). Le TEE traiterait le calcul de manière privée avec potentiellement moins de surcharge que le PIR cryptographique, bien qu'il introduise une confiance dans le fabricant du matériel. La vision à long terme devrait être un modèle hybride : utiliser le PIR pour la recherche d'index initiale et la plus sensible, et peut-être du matériel de confiance pour les étapes suivantes, équilibrant les hypothèses de confiance et la performance. Ce travail, à l'instar de l'article fondateur CycleGAN qui combinait de manière créative des réseaux pour la traduction d'images non appariées, montre comment combiner deux technologies matures (les tables de Hellman et le PIR) peut créer une solution novatrice pour un problème de niche mais important.

9. Détails techniques & Formulation mathématique

Le cœur d'une chaîne de Hellman pour une fonction de hachage $H$ et une fonction de réduction $R$ est défini de manière itérative. Étant donné un texte en clair de départ $P_0$ : $$X_0 = P_0$$ $$X_{k+1} = H(R(X_k)) \quad \text{pour } k = 0, 1, ..., t-1$$ Le point final de la chaîne est $X_t$. La table stocke les paires $(P_0, X_t)$. Pour inverser un hachage $h$, on calcule une chaîne d'essai à partir de $h$ : $Y_0 = h$, $Y_1 = H(R(Y_0))$, ..., $Y_t = H(R(Y_{t-1}))$. À chaque étape $j$, on vérifie si $R(Y_j)$ est un point distingué ou si $Y_j$ correspond à un point final stocké $X_t$, déclenchant une régénération de chaîne pour trouver la préimage. Dans la version adaptée au PIR, la vérification contre la liste des points finaux stockés sur le serveur est effectuée via une requête PIR sur l'index correspondant à $R(Y_j)$ ou $Y_j$.

10. Cadre d'analyse & Étude de cas

Étude de cas : Test d'intrusion sécurisé en tant que service (PTaaS)
Imaginez une plateforme PTaaS basée sur le cloud proposant un audit de mots de passe. Une entreprise cliente télécharge une liste de hachages de mots de passe provenant de son propre système pour un audit de sécurité. En utilisant un service standard, le fournisseur cloud apprend à quels hachages spécifiques correspondent les mots de passe de l'entreprise, une violation potentielle. En utilisant le cadre du serveur insensible :

1. L'outil d'audit du client prétraite chaque hachage cible $h$.
2. Pour chaque $h$, il calcule localement les indices nécessaires $i_1, i_2, ... i_k$ dans les tables de Hellman du fournisseur.
3. Il utilise un protocole PIR pour générer des requêtes chiffrées pour ces indices et les envoie au serveur PTaaS.
4. Le serveur traite toutes les requêtes (effectuant un travail sur l'intégralité de sa base de données) et renvoie des blocs de données chiffrés.
5. Le client déchiffre les réponses et les traite localement pour voir si des correspondances de chaîne ont été trouvées, récupérant ainsi les mots de passe en clair.

Tout au long de ce processus, le fournisseur PTaaS ne voit que des requêtes chiffrées, d'apparence aléatoire, et n'apprend rien sur les hachages que le client testait, préservant ainsi la confidentialité de l'ensemble des mots de passe internes du client.

11. Applications futures & Directions

Les principes de cette recherche s'étendent au-delà du cassage de mots de passe :

• Recherches de renseignements sur les menaces préservant la vie privée : Interroger des indicateurs de compromission (IOC) depuis une base de données partagée sans révéler ses propres actifs.
• Correspondance confidentielle de séquences ADN : Un hôpital pourrait interroger une base de données génomique pour des marqueurs de maladie sans exposer le génome complet du patient.
• Filtrage privé dans l'analyse de journaux : Rechercher dans des journaux de sécurité partagés des modèles d'attaque sans révéler les modèles spécifiques auxquels votre organisation est vulnérable.
• La convergence avec le Chiffrement Complètement Homomorphe (FHE) est une direction clé. Alors que le PIR masque le modèle d'accès, le FHE pourrait permettre au serveur d'effectuer l'intégralité du calcul de cassage sur des données chiffrées, ne renvoyant qu'un résultat chiffré. Des projets comme Microsoft SEAL et OpenFHE rendent cela plus pratique.
• L'intégration avec la confidentialité différentielle pourrait ajouter une couche de confidentialité statistique, garantissant que même le succès ou l'échec d'une requête ne fuite pas trop d'informations.

12. Références

1. Calvo, A., Futoransky, A., & Sarraute, C. (2013). An Oblivious Password Cracking Server. arXiv preprint arXiv:1307.8186.
2. Hellman, M. (1980). A cryptanalytic time-memory trade-off. IEEE Transactions on Information Theory, 26(4), 401-406.
3. Rivest, R. L. (1982). How to reuse a "write-once" memory. (MIT Laboratory for Computer Science Technical Report).
4. Oechslin, P. (2003). Making a faster cryptanalytic time-memory trade-off. Advances in Cryptology - CRYPTO 2003 (pp. 617-630). Springer.
5. Chor, B., Goldreich, O., Kushilevitz, E., & Sudan, M. (1995). Private information retrieval. Proceedings of IEEE 36th Annual Symposium on Foundations of Computer Science (pp. 41-50). IEEE.
6. Zhu, J. Y., Park, T., Isola, P., & Efros, A. A. (2017). Unpaired image-to-image translation using cycle-consistent adversarial networks. Proceedings of the IEEE international conference on computer vision (pp. 2223-2232). (Cité comme un exemple analogue de combinaison créative de technologies).
7. Microsoft Research. (s.d.). Microsoft SEAL (Simple Encrypted Arithmetic Library). Récupéré de https://www.microsoft.com/en-us/research/project/microsoft-seal/