💻 computer science

Half-Moon Cookie: Private, Similarity-Based Blocklisting with TOCTOU-Attack Resilience

Ce papier présente Half-Moon Cookie, un cadre de blocage privé et résilient aux attaques TOCTOU permettant de vérifier la similarité d'un élément avec une liste noire propriétaire sans révéler les requêtes du client ni divulguer la liste elle-même.

Auteurs originaux : Xinyuan Zhang, Anrin Chakraborti, Michael K. Reiter

Publié 2026-04-20

📖 4 min de lecture☕ Lecture pause café

CC BY 4.0

Auteurs originaux : Xinyuan Zhang, Anrin Chakraborti, Michael K. Reiter

Article original sous licence CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Ceci est une explication générée par l'IA de l'article ci-dessous. Elle n'a pas été rédigée ni approuvée par les auteurs. Pour une précision technique, consultez l'article original. Lire la clause de non-responsabilité complète

🍪 Le Concept : Le "Biscuit Demi-Lune"

Imaginez que vous êtes un chef (le Client) qui veut envoyer un gâteau (un fichier, comme un logiciel ou une pièce jointe) à un ami (un autre Client). Mais avant de l'envoyer, vous devez vous assurer qu'il n'est pas empoisonné (malveillant).

Le problème ?

Vous ne voulez pas montrer votre recette secrète au Garde-Manger (le Serveur) qui possède la liste des gâteaux empoisonnés, car votre recette est votre propriété intellectuelle.
Le Garde-Manger ne veut pas vous montrer sa liste noire complète, car c'est aussi son secret.
Si vous demandez au Garde-Manger de vérifier le gâteau à chaque fois que quelqu'un veut le manger, cela prend trop de temps. Entre le moment où vous vérifiez et le moment où l'ami mange, un voleur pourrait remplacer le gâteau par un poison (c'est ce qu'on appelle une attaque TOCTOU : Time-of-Check vs Time-of-Use).

La solution "Half-Moon Cookie" est une méthode magique en deux étapes pour résoudre ce casse-tête.

🕵️‍♂️ L'Analogie : Le Douanier et le Tampon Secret

Imaginons un aéroport (le Serveur) qui a une liste de passagers interdits (la Blocklist).

Étape 1 : La Vérification Explicite (Le Chef envoie le gâteau)

Le Chef (l'expéditeur) arrive avec son gâteau. Il ne veut pas le donner au douanier pour qu'il le goûte.

La Magie : Au lieu de donner le gâteau, le Chef et le douanier utilisent une boîte noire magique (un circuit cryptographique). Le Chef met son gâteau dedans. Le douanier a la liste des poisons dedans.
Le Résultat : La boîte noire compare les deux sans jamais révéler le contenu du gâteau au douanier, ni la liste des poisons au Chef.
Le Tampon : Si le gâteau est sain, la boîte noire émet un Tampon Secret (un jeton) que le Chef reçoit. Ce tampon prouve que le gâteau a été vérifié, mais il est impossible à contrefaire.

Étape 2 : La Vérification Implicite (L'ami reçoit le gâteau)

Maintenant, le Chef envoie le gâteau à son Ami. L'Ami veut manger, mais il a peur que le gâteau ait été changé en route.

Le Problème : Si l'Ami doit refaire toute la vérification complexe avec le douanier, cela prendrait des heures.
La Solution : L'Ami montre simplement le Tampon Secret au douanier.
Le Résultat : Le douanier regarde son registre. "Ah oui, ce tampon correspond à un gâteau vérifié il y a 5 minutes !" C'est une vérification instantanée (comme une validation de billet de train). L'Ami peut manger en toute sécurité, sans avoir à refaire le test long et complexe.

🛡️ Pourquoi c'est génial ? (Les 3 Avantages)

La Confidentialité Totale (Privacy) :
- Le Garde-Manger ne sait jamais quel gâteau vous avez envoyé.
- Vous ne savez jamais quels gâteaux sont sur sa liste noire.
- C'est comme si vous compariez deux empreintes digitales dans un coffre-fort : vous savez si elles correspondent, mais vous ne voyez ni l'une ni l'autre.
La Vitesse (Performance) :
- Le test complet (Étape 1) est lourd et lent, mais il ne doit être fait qu'une seule fois par l'expéditeur.
- Le test rapide (Étape 2) est instantané pour tous les destinataires. C'est comme si le Chef payait le péage une fois, et que tous ses passagers pouvaient passer sans s'arrêter.
La Sécurité contre les Pièges (TOCTOU) :
- Si un pirate essaie de remplacer le gâteau sain par un poison après la vérification mais avant que l'Ami ne le mange, le Tampon Secret ne correspondra plus. Le système le détectera immédiatement. C'est comme si le tampon changeait de couleur si le gâteau était touché.

🧠 En résumé

Le papier "Half-Moon Cookie" propose un système où :

L'expéditeur fait le gros du travail (vérification lente mais privée).
Le destinataire fait le petit travail (vérification rapide via un tampon).
Le serveur garde ses secrets et ne voit pas vos données.

C'est une façon intelligente de dire : "Je vous fais confiance pour vérifier une fois, et je vous donne un passeport qui prouve que c'est bon, pour que tout le monde puisse passer vite et en sécurité."

Le nom "Half-Moon Cookie" vient simplement de la forme du biscuit (moitié vanille, moitié chocolat), symbolisant cette séparation entre le processus de vérification (lourd) et le processus de validation (léger), tout en restant un seul et même objet. 🌙🍪

1. Problématique

Le blocklisting (mise sur liste noire) est une technique fondamentale de sécurité informatique pour bloquer le contenu malveillant (malwares, spams, certificats révoqués, etc.). Cependant, les infrastructures traditionnelles présentent deux limitations majeures :

Vie privée : Soit la liste noire doit être publique (ce qui révèle les signatures de malware aux attaquants), soit le client doit révéler ses requêtes (le contenu de ses fichiers) au serveur, ce qui compromet la confidentialité des données propriétaires ou sensibles.
Vulnérabilité TOCTOU (Time-of-Check vs Time-of-Use) : Vérifier un fichier juste avant son utilisation est coûteux en temps de calcul et en latence. Si la vérification est faite plus tôt (par exemple, par l'expéditeur), le fichier peut être modifié ou la liste noire mise à jour entre le moment de la vérification et le moment de l'utilisation par le destinataire, créant une fenêtre d'exploitation pour les attaquants.

L'objectif est de concevoir un système permettant à un client de vérifier si un élément est proche d'une liste noire privée (basée sur la similarité, pas seulement sur l'égalité exacte) sans révéler l'élément au serveur ni la liste au client, tout en permettant une vérification rapide et résistante aux attaques TOCTOU pour les destinataires.

2. Méthodologie : Le Framework Half-Moon Cookie

Les auteurs proposent un protocole cryptographique à trois parties impliquant un client émetteur ( $C_{snd}$ ), un client récepteur ( $C_{rcv}$ ) et un serveur ( $S$ ). Le système repose sur deux phases distinctes : une vérification explicite et une vérification implicite.

A. Architecture Cryptographique

Le système utilise des outils de calcul sécurisé (Secure Multi-Party Computation - MPC) et de circuits garbés (Garbled Circuits) pour garantir la confidentialité :

Embedding (Encodage) : Les fichiers sont transformés en vecteurs dans un espace métrique (distance de Hamming) via des fonctions de hachage flou (fuzzy hashing) comme TLSH, ssdeep ou sdhash.
Circuits Garbés Réutilisables (Reusable Garbled Circuits - RGC) : Pour gérer les fichiers de grande taille sans que la taille du circuit ne croisse linéairement avec la taille du fichier, les auteurs utilisent le framework CRGC. Cela permet de découpler le coût de l'encodage de la taille du fichier.
Fonctionnalités Idéales : Le protocole est décomposé en trois primitives idéales :
1. FEM (Embed-and-Map) : Encode le fichier de l'émetteur dans l'espace métrique et applique une permutation imprévisible pour masquer les données.
2. FTC (Test-and-Commit) : Vérifie si l'élément encodé est proche d'un élément de la liste noire (distance $\le T$ ). Si ce n'est pas le cas, le serveur génère un jeton de liaison et de dissimulation (hiding and binding token) pour l'élément.
3. FIC (Implicit Check) : Permet au récepteur de vérifier rapidement si un jeton existe dans une liste blanche (allowlist) sans recalculer la distance par rapport à la liste noire.

B. Flux de Travail

Phase Explicite (Émetteur) :
- $C_{snd}$ envoie son fichier $w$ à $S$ via un circuit garbé.
- $S$ vérifie si $w$ est proche d'un élément de sa liste noire privée $L$ .
- Si $w$ est "propre", $S$ stocke un jeton $\gamma$ (dérivé de $w$ et de clés secrètes) dans une liste blanche (allowlist) et renvoie un nonce à $C_{snd}$ .
- $C_{snd}$ transmet le fichier $w$ , le nonce et des masques à $C_{rcv}$ .
Phase Implicite (Destinataire) :
- $C_{rcv}$ reçoit $w$ et le nonce.
- Au moment de l'utilisation, $C_{rcv}$ contacte $S$ pour vérifier si le jeton correspondant au nonce existe dans la liste blanche.
- Cette vérification est beaucoup plus rapide (complexité constante par rapport à la taille de la liste noire) car elle ne nécessite pas de recalculer la distance par rapport à tous les malwares.
- Si le jeton est trouvé, le fichier est autorisé.

C. Résistance aux attaques TOCTOU

Le système résout le problème TOCTOU grâce au jeton liant (binding) :

Le jeton $\gamma$ est cryptographiquement lié au fichier original $w$ . Un attaquant ne peut pas modifier le fichier après la vérification explicite sans que le jeton ne devienne invalide.
Si la liste noire est mise à jour, la liste blanche est purgée, forçant les nouveaux destinataires à effectuer une nouvelle vérification explicite, fermant ainsi la fenêtre d'exploitation.

3. Contributions Clés

Primitive Half-Moon : Définition formelle d'un protocole de blocklisting privé basé sur la similarité, séparant l'étape d'encodage de la vérification pour optimiser les performances.
Optimisation des Circuits Garbés : Utilisation de circuits garbés réutilisables (CRGC) pour rendre l'encodage de fichiers volumineux (ex: exécutables) indépendant de leur taille, réduisant drastiquement la latence et le trafic réseau.
Mécanisme de Vérification Implicite : Introduction d'un jeton de liste blanche qui permet aux destinataires de valider rapidement un résultat de vérification précédent, éliminant la nécessité de recalculer des distances complexes à chaque utilisation.
Sécurité Renforcée : Preuve de sécurité contre un client émetteur malveillant (qui tente de tromper le système) et un serveur semi-honnête (qui tente d'apprendre le contenu du fichier). Le protocole garantit que le serveur n'apprend rien si le fichier n'est pas bloqué.

4. Résultats Expérimentaux

Les auteurs ont implémenté le système en C++ et l'ont évalué sur un jeu de données de pièces jointes e-mail (Enron) et de malwares (Ember).

Performance de la Vérification Explicite :
- L'utilisation de circuits garbés réutilisables réduit le volume de communication et le temps de réponse de plusieurs ordres de grandeur par rapport aux circuits garbés monolithiques classiques.
- Pour un fichier de 5 Ko, le temps de réponse passe de ~1000s (sans RGC) à ~5s (avec RGC) pour l'algorithme TLSH.
- L'algorithme TLSH s'est révélé le plus performant globalement, offrant un bon équilibre entre précision et coût computationnel.
- La latence augmente légèrement avec la taille de la liste noire, mais reste gérable même pour des listes de 10 000 entrées.
Performance de la Vérification Implicite :
- La vérification implicite est extrêmement rapide (environ 0,19 seconde) et consomme très peu de bande passante (7,2 Ko).
- Elle est plus de 100 fois plus rapide et 1000 fois plus légère en communication que les solutions de type "Private Set Intersection" (PSI) floues existantes (comme Chakraborti et al. ou Blass et Noubir).
- Le coût est indépendant de la taille de la liste noire.
Scalabilité : Le serveur peut gérer plusieurs centaines de requêtes concurrentes avant de saturer, ce qui est suffisant pour de nombreuses applications pratiques comme la distribution de logiciels ou la sécurité e-mail.

5. Signification et Impact

Le travail "Half-Moon Cookie" représente une avancée significative dans le domaine de la sécurité privée :

Équilibre Performance/Vie Privée : Il résout le compromis traditionnel entre la confidentialité (nécessitant des calculs lourds) et la performance (nécessitant des vérifications rapides). En déplaçant le coût lourd vers l'expéditeur et en permettant une vérification légère pour les destinataires, il rend le blocklisting privé viable à grande échelle.
Sécurité Opérationnelle : En adressant spécifiquement les vulnérabilités TOCTOU, il offre une protection robuste pour les environnements où les fichiers sont distribués à de nombreux utilisateurs (ex: e-mails, CDN, distribution de logiciels).
Applicabilité : Bien que démontré sur la détection de malwares, le cadre est généralisable à d'autres domaines nécessitant une vérification de similarité privée, comme la détection de contenu abusif (CSAM), la vérification de credentials compromis ou le filtrage de spam.

En résumé, Half-Moon Cookie propose une architecture pratique et sécurisée permettant de vérifier la réputation d'un contenu sans compromettre la confidentialité des données ni la disponibilité du service, tout en fermant les brèches temporelles souvent exploitées par les attaquants.