HMAC hat mein Autocomplete gefressen: Type-ahead-Suche über verschlüsselte E-Mail-Adressen

Wir verschlüsseln personenbezogene Daten (PII) unserer Nutzer at rest mit Schlüsseln pro Tenant, damit ein geleakter Datenbank-Dump nichts Brauchbares preisgibt. Die E-Mail-Spalte ist Ciphertext. Telefonnummern, Namen, benutzerdefinierte Attribute: alles Ciphertext. Wir sind stolz darauf. Es ist ein Verkaufsargument.

Und an dem Tag, an dem das live ging, hörte das Suchfeld im Admin-Bereich stillschweigend auf zu autocompleten.

Kein Fehler. Keine Logzeile. Wer ali in die Nutzersuche eintippte, also der Tenant-Admin, der früher [email protected] nach drei Tastenanschlägen aufpoppen sah, sah jetzt... nichts, es sei denn, er tippte die gesamte E-Mail-Adresse, exakt. Die Suche war nicht kaputtgegangen, sie war stillschweigend von "beginnt mit" zu "ist gleich" degradiert, und nichts im System hielt das für erwähnenswert.

Das ist die Geschichte, wie wir Type-ahead über Daten zurückbekamen, die wir uns weigern im Klartext zu speichern, und der drei Fallen, in die wir dabei getappt sind. Die Kryptographie erwies sich als der einfache Teil.

Warum Verschlüsselung das Autocomplete frisst

Mit Klartext ist Präfixsuche genau das, wofür Datenbanken da sind. Man hält einen Index nach E-Mail sortiert, und starts with "ali" ist ein Range-Scan: alles >= "ali" und < "alj". Billig, offensichtlich, erledigt.

Verschlüsselt man die Spalte, ist der sortierte Index weg. Der Standardersatz ist ein Blind Index (ein blinder Index): Neben dem Ciphertext speichert man einen keyed HMAC des Werts und schlägt Nutzer nach, indem man den HMAC des Suchbegriffs neu berechnet. HMAC(key, "[email protected]") ist deterministisch, also funktioniert der Exact-Match-Lookup perfekt, und der Index leakt nichts Lesbares, denn ohne den Tenant-Schlüssel kann man keinen Digest zum Vergleichen berechnen.

Aber man beachte, wofür HMAC gedacht ist. Sein gesamtes Designziel ist, dass ähnliche Eingaben völlig unzusammenhängende Ausgaben erzeugen: ein Bit kippen, und der Digest ist ein komplett anderer. HMAC("ali") und HMAC("alistair") haben nichts miteinander zu tun. Die Eigenschaft, die den Blind Index gefahrlos leakbar macht, ist genau die Eigenschaft, die ihn unfähig macht, "beginnt mit" zu beantworten. Ordnung ist Leakage. Ein Blind Index bricht die Präfixsuche nicht aus Versehen; er bricht sie aus Prinzip.

Also degradierte das Suchfeld stillschweigend zu Exact-Match, weil Exact-Match die einzige Frage war, die der Index noch beantworten konnte.

Das Design: jedes Präfix als eigenen Wert indexieren

Wenn der Index nur "ist gleich" beantworten kann, dann verwandelt man "beginnt mit" eben in "ist gleich".

Jedes Präfix des normalisierten Local Part der E-Mail (der Teil vor dem @) bekommt seine eigene Blind-Index-Zeile. Für [email protected] sind das Zeilen für al, ali, alis, alist und so weiter: PartitionKey = HMAC(prefix), RowKey = die User-Id. Jetzt ist "beginnt mit ali" ein Exact-Match-Lookup auf HMAC("ali"): eine Punktabfrage, keine Ordnung nötig. Unsere Namenssuche funktionierte aus demselben Grund bereits so; die E-Mail zog nur nach.

Zwei Konstanten halten das Ganze vernünftig. Präfixe beginnen bei 2 Zeichen (Ein-Zeichen-Lookups waren nie nützlich und verdoppeln die Zeilenzahl) und enden bei 16 (das begrenzt den Fan-out pro E-Mail; eine längere Anfrage matcht einfach auf ihren ersten 16 Zeichen, und die Handvoll Kandidaten wird nach der Entschlüsselung gefiltert). Jede E-Mail kostet also höchstens 15 Indexzeilen: geschrieben beim Anlegen, verschoben bei E-Mail-Änderung, entfernt beim Löschen.

Das ist der Tausch in einem Satz: Man kauft sich die Ordnung zurück, die man sich weigerte zu leaken, und bezahlt dafür mit Write-Fan-out. Speicher und Writes sind billig; geleakte Struktur ist es nicht. Es ist ein guter Tausch.

Eine Feinheit im Verschieben-bei-Änderung-Pfad hat sich ihren eigenen Kommentar im Code verdient: Die Präfixzeilen sind auf den Local Part geschlüsselt, also muss das Neuschreiben ausgelöst werden, wenn sich der Local Part ändert, und zwar unabhängig von der Domain. Eine Umbenennung innerhalb derselben Domain, [email protected] → [email protected], sieht für einen Guard, der mit Blick auf den Domain-Index geschrieben wurde, aus wie "Domain unverändert, Indexarbeit überspringen" und würde die alten Präfixzeilen für immer auf den umbenannten Nutzer zeigen lassen.

Und um ehrlich zu sein über das, was wir gebaut haben: Dieser Index leakt bewusst Präfixgleichheit. Ein Angreifer mit Zugriff auf die Tabelle kann sehen, dass zwei Nutzer ein 3-Zeichen-E-Mail-Präfix teilen, aber nicht, welches. Searchable Encryption eliminiert Leakage nie; sie lässt einen sie wählen, bewusst, pro Query-Form. Gleichheit und Präfixgleichheit sind die Leakage, die wir gewählt haben. Diese Sichtweise (wähle deine Leakage, und konstruiere dann alles andere darum herum) ist die ganze Disziplin.

Das Design funktionierte. Dann begannen die Systemprobleme.

Falle eins: der Schlüssel, der sich nicht anlegen ließ

Blind Indexes brauchen einen HMAC-Schlüssel pro Tenant, provisioniert in Vaults Transit-Engine wie unsere Verschlüsselungsschlüssel. Das Anlegen lieferte einen 500er: invalid key size for HMAC key.

Vault verlangt für Schlüssel vom Typ hmac eine explizite key_size (32 bis 512 Bytes), während die Typen mit fester Größe (aes256-gcm96, ecdsa-p256) sie verbieten. Unser Key-Creation-Call schickte nur {"type":"hmac"}. Ein einziges fehlendes Feld.

Warum das eine Falle war und kein simpler Bug-Report: Jede Tokenize-Operation warf eine Exception, und der Login-Pfad tokenisiert, denn einen Nutzer beim Sign-in per E-Mail zu finden läuft über denselben Blind Index wie die Admin-Suche. Die Verschlüsselung einzuschalten brach nicht die Suche. Es brach den Login. Das Feature, dessen Verkaufsargument "deine Nutzer sind sicherer" lautet, legte beim ersten Aktivieren in Dev das Sign-in lahm. Der Fix ist key_size=32 (HMAC-SHA256) für hmac-Schlüssel, weggelassen bei den Typen mit fester Größe, plus eine feste Regel: den Tokenize-Pfad gegen ein echtes Vault smoke-testen, bevor man Verschlüsselung irgendwo einschaltet. Mocks validieren keine Key-Creation-Payloads.

Falle zwei: das Update, das einen Nutzer stranden lassen konnte

Eine E-Mail zu ändern bedeutet Indexpflege: die alten Zeilen entfernen, die neuen schreiben. Unsere erste Implementierung tat es in genau dieser Reihenfolge: erst löschen, dann schreiben. Natürlich, ordentlich, falsch.

Jeder Write neuer Zeilen involviert jetzt Vault (für das Berechnen der HMAC-PartitionKeys). Löscht man die alten Zeilen zuerst, hinterlässt ein Vault-Schluckauf während des Writes den Nutzer mit weder den alten Lookup-Zeilen noch den neuen. Er existiert, verschlüsselt, in der Tabelle, und nichts kann ihn finden. Auch der Login nicht. Das ist keine degradierte Suche; das ist ein ausgesperrter Nutzer, bis irgendwann ein künftiger Reindex vorbeikommt.

Der Fix ist Reihenfolge, nicht Fehlerbehandlung: schreiben vor löschen, überall, wo der Index gepflegt wird. Ein Crash zwischen den beiden Schritten hinterlässt jetzt eine überzählige veraltete Zeile (harmlos, wird lazy aufgeräumt) statt einer fehlenden. Der Fehlermodus wanderte von "Nutzer unerreichbar" zu "eine redundante Zeile", und zwar gratis. Wenn ein Write-Pfad eine Remote-Abhängigkeit involviert, wähle die Schrittreihenfolge, mit deren halbfertigem Zustand du leben kannst.

Falle drei: die Partition, die einen Import fraß

Wir führen außerdem einen Domain-Blind-Index (HMAC(domain) → Mitglieder), damit "alle bei acme.com" ein einziger Lookup ist. Deterministisches Hashing hat eine Konsequenz, die niemand einpreist, bis ein Import kommt: Jeder Nutzer einer Domain landet in einer Partition. Eine Azure-Table-Partition schafft grob 2.000 Operationen pro Sekunde. Ein Import von 50k Nutzern mit einer einzigen Domain aus Auth0 trichterte jeden Domain-Index-Write in genau diesen Flaschenhals.

Der Fix ist Bucketing: Mitglieder verteilen sich per Hash der User-Id auf 16 Partitionen, und Domain-Reads fächern über die Buckets auf (begrenzt, und selten genug, um nicht ins Gewicht zu fallen). Zwei Details trugen die Lektion. Der Bucket-Hash ist ein handgerollter FNV-1a, denn .NETs string.GetHashCode ist absichtlich instabil über Prozessgrenzen hinweg: Bucketet man danach, berechnet der Prozess von morgen für denselben Nutzer einen anderen Bucket und findet die Zeile nicht, die er löschen soll. Und der Lesepfad durchkämmt weiterhin die alten ungebucketen Partitionen, sodass bestehende Zeilen ganz ohne erzwungenen Backfill auffindbar blieben: Neue Writes verteilen sich sofort, alte Zeilen migrieren, wann immer der Nutzer das nächste Mal angefasst wird.

Die Lektion

Nichts an dieser Geschichte ist neuartige Kryptographie. HMAC ist Jahrzehnte alt; "hashe den Wert, indexiere den Hash" passt in einen Satz. Alles, was uns tatsächlich etwas gekostet hat, war Systemarbeit: welche Query-Formen das Produkt wirklich braucht (Gleichheit, Präfix, Domain: jede bekam ihren eigenen Index, denn ein Blind Index beantwortet genau eine Frage); wie Schlüssel provisioniert werden und was auf dem Login-Pfad passiert, wenn das schiefgeht; in welcher Reihenfolge Index-Writes geschehen, wenn ein Remote-KMS dazwischensitzt; und wo deterministisches Hashing Last konzentriert, die Klartext nie konzentriert hat.

Searchable Encryption wird als Krypto-Feature verkauft. Baut man sie, entdeckt man, dass sie ein Distributed-Systems-Feature im Krypto-Kostüm ist. Das Suchfeld autocompletet wieder (ali findet Alistair nach drei Tastenanschlägen), und ein gestohlener Dump derselben Tabelle zeigt HMAC-Digests, verteilt über sechzehn Buckets, sprich: nichts. Beides zugleich war immer der Punkt.