HMAC a mangé mon autocomplétion : recherche à la saisie sur des e-mails chiffrés

Nous chiffrons les PII des utilisateurs au repos avec des clés par tenant, afin qu'un dump de base de données divulgué n'expose rien d'utile. La colonne e-mail est du texte chiffré. Numéros de téléphone, noms, attributs personnalisés : du texte chiffré. Nous en sommes fiers. C'est un argument de vente.

Et le jour de la mise en production, la barre de recherche du portail d'administration a discrètement cessé d'autocompléter.

Aucune erreur. Aucune ligne de log. Tapez ali dans la recherche d'utilisateurs, et l'administrateur du tenant qui voyait auparavant [email protected] apparaître après trois frappes ne voyait désormais... rien, sauf à taper l'adresse e-mail entière, exactement. La recherche n'était pas cassée : elle s'était silencieusement dégradée de « commence par » à « égale », et rien dans le système ne jugeait cela digne d'être signalé.

Voici l'histoire de la reconquête de la recherche à la saisie sur des données que nous refusons de stocker en clair, et des trois pièges rencontrés en chemin. La cryptographie s'est révélée être la partie facile.

Pourquoi le chiffrement dévore l'autocomplétion

Avec du texte en clair, la recherche par préfixe est exactement ce pour quoi les bases de données existent. Gardez un index ordonné par e-mail et starts with "ali" devient un parcours de plage : tout ce qui est >= "ali" et < "alj". Bon marché, évident, réglé.

Chiffrez la colonne et l'index ordonné disparaît. Le remplaçant standard est un blind index (index aveugle) : à côté du texte chiffré, on stocke un HMAC à clé de la valeur, et on retrouve les utilisateurs en recalculant le HMAC du terme recherché. HMAC(key, "[email protected]") est déterministe, donc la recherche par correspondance exacte fonctionne parfaitement, et l'index ne laisse rien filtrer de lisible, car sans la clé du tenant on ne peut pas calculer de condensat à comparer.

Mais observez à quoi sert HMAC. Son objectif de conception est précisément que des entrées similaires produisent des sorties sans rapport : inversez un bit, obtenez un condensat complètement différent. HMAC("ali") et HMAC("alistair") n'ont rien à voir l'un avec l'autre. La propriété qui rend le blind index sûr à divulguer est précisément celle qui le rend incapable de répondre à « commence par ». L'ordre est une fuite. Un blind index ne casse pas la recherche par préfixe par accident ; il la casse par principe.

La barre de recherche s'est donc dégradée en correspondance exacte, silencieusement, parce que la correspondance exacte était la seule question à laquelle l'index pouvait encore répondre.

La conception : indexer chaque préfixe comme une valeur à part entière

Si l'index ne sait répondre qu'à « égale », alors transformons « commence par » en « égale ».

Chaque préfixe de la partie locale normalisée de l'e-mail (la partie avant le @) reçoit sa propre ligne de blind index. Pour [email protected], cela donne des lignes pour al, ali, alis, alist, et ainsi de suite : PartitionKey = HMAC(prefix), RowKey = l'identifiant de l'utilisateur. Désormais, « commence par ali » est une recherche exacte sur HMAC("ali") : une seule requête ponctuelle, aucun ordre requis. Notre recherche par nom fonctionnait déjà ainsi pour la même raison ; l'e-mail n'a fait que la rejoindre.

Deux constantes gardent le tout raisonnable. Les préfixes commencent à 2 caractères (les recherches à un seul caractère n'ont jamais été utiles et doublent le nombre de lignes) et plafonnent à 16 (ce qui borne la démultiplication par e-mail ; une requête plus longue est simplement mise en correspondance sur ses 16 premiers caractères, et la poignée de candidats est filtrée après déchiffrement). Chaque e-mail coûte donc au plus 15 lignes d'index : écrites à la création, déplacées au changement d'e-mail, supprimées à la suppression.

Voilà le compromis en une phrase : vous rachetez l'ordre que vous refusiez de laisser fuiter, et vous le payez en démultiplication des écritures. Le stockage et les écritures sont bon marché ; la structure divulguée ne l'est pas. C'est un bon compromis.

Une subtilité du chemin « déplacer au changement » a mérité son propre commentaire dans le code : les lignes de préfixe sont indexées sur la partie locale, donc la réécriture doit se déclencher quand la partie locale change, indépendamment du domaine. Un renommage au sein du même domaine, [email protected] → [email protected], ressemble à « domaine inchangé, sauter le travail d'index » pour un garde-fou écrit en pensant à l'index de domaine, et laisserait pour toujours les anciennes lignes de préfixe pointer vers l'utilisateur renommé.

Et pour être honnête sur ce que nous avons construit : cet index laisse délibérément fuiter l'égalité de préfixe. Un attaquant en possession de la table peut voir que deux utilisateurs partagent un préfixe d'e-mail de 3 caractères, sans pouvoir dire lequel. Le chiffrement interrogeable n'élimine jamais les fuites ; il vous permet de les choisir, consciemment, par forme de requête. L'égalité et l'égalité de préfixe sont les fuites que nous avons choisies. Ce cadre (choisir sa fuite, puis tout concevoir autour) constitue toute la discipline.

La conception fonctionnait. Puis les problèmes systèmes ont commencé.

Premier piège : la clé impossible à créer

Les blind index nécessitent une clé HMAC par tenant, provisionnée dans le moteur transit de Vault comme nos clés de chiffrement. La création de l'une d'elles renvoyait une erreur 500 : invalid key size for HMAC key.

Vault exige un key_size explicite pour les clés de type hmac, de 32 à 512 octets, alors que les types à taille fixe (aes256-gcm96, ecdsa-p256) l'interdisent. Notre appel de création de clé n'envoyait que {"type":"hmac"}. Un seul champ manquant.

Voici pourquoi c'était un piège et non un simple rapport de bug : chaque opération de tokenisation levait une exception, et le chemin de connexion tokenise, car retrouver un utilisateur par e-mail à la connexion passe par le même blind index que la recherche d'administration. Activer le chiffrement n'a pas cassé la recherche. Cela a cassé la connexion. La fonctionnalité dont l'argument de vente est « vos utilisateurs sont plus en sécurité » a mis la connexion hors service dès la première activation en dev. Le correctif est key_size=32 (HMAC-SHA256) pour les clés hmac, omis pour les types à taille fixe, plus une règle permanente : tester le chemin de tokenisation contre un vrai Vault avant d'activer le chiffrement où que ce soit. Les mocks ne valident pas les payloads de création de clé.

Deuxième piège : la mise à jour qui pouvait abandonner un utilisateur

Changer un e-mail implique de la maintenance d'index : supprimer les anciennes lignes, écrire les nouvelles. Notre première implémentation le faisait dans cet ordre : supprimer, puis écrire. Naturel, propre, faux.

Chaque écriture de nouvelle ligne implique désormais Vault (pour calculer les PartitionKey en HMAC). Supprimez d'abord les anciennes lignes, et un raté de Vault pendant l'écriture ne laisse à l'utilisateur ni les anciennes lignes de recherche ni les nouvelles. Il existe, chiffré, dans la table, et rien ne peut le retrouver. Y compris la connexion. Ce n'est pas une recherche dégradée ; c'est un utilisateur verrouillé dehors, jusqu'à ce qu'une future réindexation passe par là.

Le correctif tient à l'ordre des opérations, pas à la gestion d'erreurs : écrire avant de supprimer, partout où l'index est maintenu. Un crash entre les deux étapes laisse désormais une ligne obsolète en trop (inoffensive, nettoyée paresseusement) au lieu d'une ligne manquante. Le mode de défaillance est passé de « utilisateur introuvable » à « une ligne redondante », gratuitement. Quand un chemin d'écriture implique une dépendance distante, choisissez l'ordre des étapes dont l'état à moitié terminé reste vivable.

Troisième piège : la partition qui a englouti un import

Nous conservons aussi un blind index de domaine, HMAC(domain) → membres, pour que « tout le monde chez acme.com » soit une seule recherche. Le hachage déterministe a une conséquence dont personne ne mesure le coût avant un import : tous les utilisateurs d'un même domaine atterrissent dans une seule partition. Une partition Azure Table encaisse environ 2 000 opérations par seconde. Un import Auth0 de 50 000 utilisateurs sur un seul domaine a canalisé chaque écriture de l'index de domaine droit dans ce goulot d'étranglement.

Le correctif est le bucketing : les membres sont répartis sur 16 partitions selon un hachage de l'identifiant utilisateur, et les lectures de domaine s'étalent sur les buckets, une opération bornée et assez rare pour ne pas compter. Deux détails portent la leçon. Le hachage de bucket est un FNV-1a écrit à la main, parce que string.GetHashCode de .NET est délibérément instable d'un processus à l'autre : bucketez avec, et le processus de demain calculera un bucket différent pour le même utilisateur et ne retrouvera plus la ligne qu'il est censé supprimer. Et le chemin de lecture balaie encore les anciennes partitions non bucketées, si bien que les lignes existantes sont restées trouvables sans backfill forcé : les nouvelles écritures se répartissent immédiatement, les anciennes lignes migrent dès que l'utilisateur est de nouveau touché.

La leçon

Rien dans cette histoire ne relève d'une cryptographie nouvelle. HMAC a des décennies ; « hacher la valeur, indexer le hachage » tient en une phrase. Tout ce qui nous a réellement coûté était du travail systèmes : de quelles formes de requête le produit a réellement besoin (égalité, préfixe, domaine : chacune a eu son propre index, car un blind index répond exactement à une seule question) ; comment les clés sont provisionnées et ce qui arrive au chemin de connexion quand elles ne le sont pas ; dans quel ordre les écritures d'index se font quand un KMS distant se trouve au milieu ; et où le hachage déterministe concentre une charge que le texte en clair n'a jamais connue.

Le chiffrement interrogeable se vend comme une fonctionnalité crypto. Construisez-le et vous découvrirez que c'est une fonctionnalité de systèmes distribués déguisée en crypto. La barre de recherche autocomplète de nouveau (ali trouve Alistair après trois frappes) et un dump volé de la même table montre des condensats HMAC répartis sur seize buckets, autrement dit : rien. Les deux à la fois, c'était le but depuis le début.