Verschlüsselte Dokumente durchsuchen: der verschlüsselte Suchindex (blind indexing)

Wenn der Server Ihre Dateien nicht lesen kann, wie kann er sie dann durchsuchen? Bei den meisten Ende-zu-Ende-verschlüsselten Speichern lautet die ehrliche Antwort: gar nicht. Sie bekommen bestenfalls eine Suche über Dateinamen, und nichts aus dem Inneren der Dokumente. NomadVault durchsucht Namen und Inhalte. Dieser Artikel erklärt, wie das funktioniert, ohne dass der Server die Wörter erfährt, und, ebenso wichtig, was er doch erfährt.

Suche ist ein Abgleichproblem

Auf den Kern reduziert ist Suche dies: Finde zu einem Wort, das Sie eingeben, die Dokumente, die es enthalten. Eine herkömmliche Suchmaschine baut einen Index, eine große Tabelle „Wort → Liste von Dokumenten”, und schlägt Ihr Wort darin nach. Der Index ist der Klartext jedes Dokuments, nur umsortiert. Ihn dem Server zu übergeben, würde die Verschlüsselung zunichtemachen.

Der Trick besteht darin, dieselbe Tabelle zu bauen, aber jedes Wort durch eine verkleidete Version seiner selbst zu ersetzen, und zwar so, dass der Server sie nicht zurückrechnen, Ihr Gerät sie aber reproduzieren kann. Wenn aus „Rechnung” immer dasselbe unlesbare Token wird, kann der Server weiterhin Tokens gegen Tokens abgleichen. Er weiß nur nicht, für welches Wort ein Token steht. Kryptografen nennen das einen blinden Index; wir sprechen vom verschlüsselten Suchindex.

Wie aus einem Wort ein Token wird

Jeder Nutzer hat einen geheimen Suchschlüssel, 256 Zufallsbits, die bei der ersten Verwendung im Browser erzeugt werden. Er wird auf dem Server gespeichert, versiegelt für Ihre eigenen Schlüssel mit derselben hybriden Verpackung, die Ihre Dateien schützt. Der Server hält ihn also, kann ihn aber nicht öffnen.

Wenn Sie ein Dokument hochladen, erledigt Ihr Browser die Arbeit:

Er extrahiert den Text. Bei PDFs, Word-, PowerPoint- und OpenDocument-Dateien sowie bei reinen Textformaten geschieht das auf Ihrem Gerät, nach einer etwaigen Inhaltsbereinigung und vor der Verschlüsselung.
Er zerlegt den Text in Wörter, schreibt sie klein, verwirft alles unter drei Zeichen, kurze Zahlen und eine Handvoll Stoppwörter wie „the” und „and”, und entfernt Dubletten. Der Dateiname durchläuft dieselben Regeln getrennt.
Jedes verbleibende Wort wird mit Ihrem Suchschlüssel durch HMAC-SHA-256 geschickt. HMAC ist eine schlüsselabhängige Einwegfunktion: Dasselbe Wort mit demselben Schlüssel ergibt immer dieselbe Ausgabe, und ohne den Schlüssel verrät die Ausgabe nichts über das Wort. Die ersten 16 Bytes jeder Ausgabe sind das Token.
Die Tokens, und nur die Tokens, werden an den Server geschickt und neben der Kennung der Datei gespeichert, gekennzeichnet als Namens- oder Inhaltstoken.

Wenn Sie suchen, wendet Ihr Browser dieselben Regeln auf Ihre Eingabe an, berechnet dieselben Tokens mit demselben Schlüssel und sendet sie. Der Server liefert jede Datei zurück, die eines dieser Tokens trägt. Ihr Browser entschlüsselt die Dateinamen zur Anzeige. Zu keinem Zeitpunkt hat ein Wort die Leitung passiert.

Weil die Tokens an Sie gebunden sind, erzeugt dasselbe Wort in den Indizes zweier Nutzer zwei voneinander unabhängige Tokens. Der Server kann nicht einmal erkennen, dass die Dokumente zweier Personen ein Wort gemeinsam haben.

Was der Server trotzdem erfährt

Das ist der Teil, nach dem ein sorgfältiger Prüfer fragen wird, und die Antwort lautet nicht „nichts”.

Wie viele verschiedene Wörter jede Datei hat. Eine Datei mit 40 Tokens ist eine kurze Notiz; eine mit 4.000 ein langer Bericht. Die Länge war über die Chiffratgröße ohnehin sichtbar, das kommt also kaum hinzu.

Welche Dateien Wörter gemeinsam haben. Innerhalb Ihres eigenen Index ist „Rechnung” in jeder Datei, die es enthält, dasselbe Token. Der Server kann sehen, dass die Dateien A, B und C ein Token teilen, ohne zu wissen, welches Wort es ist. Mit der Zeit und mit Außenwissen können solche Muster auf Inhalte hindeuten: Ein Token, das in fast jeder Datei vorkommt, ist vermutlich Ihr Firmenname. Das ist der bekannte Preis jeder durchsuchbaren Verschlüsselung, die schnell genug für den Alltag ist, und die Fachliteratur ist eindeutig, dass Häufigkeit und gemeinsames Vorkommen durchsickern. Wir tun nicht so, als wäre es anders.

Wonach Sie suchen, verblindet. Der Server sieht, welche Tokens Sie abgefragt haben und welche Dateien zurückkamen. Er weiß also, dass Sie nach etwas gesucht haben und was getroffen wurde. Er weiß nicht, was dieses Etwas ist.

Nichts von Gästen, nichts über Nutzer hinweg. Der Schlüssel ist pro Nutzer, also gibt es keinen Index, den der Server über Konten hinweg vergleichen könnte, und wer später Zugriff auf eine Datei erhält, erbt nicht automatisch die Tokens des Hochladenden.

Vergleichen Sie das mit der Alternative, die die meisten Produkte wählen, auf dem Server zu entschlüsseln und einen normalen Index zu bauen, und der Unterschied ist der zwischen einer Form und dem Text selbst.

Wo es endet

Der verschlüsselte Suchindex hat Grenzen, die aus dem Design folgen, und wir nennen sie lieber, als dass Sie sie selbst entdecken.

Nur ganze Wörter. Ein Token steht für ein vollständiges Wort, also sind „Rechnungen” und „Rechnung” verschiedene Tokens, und eine Suche nach „Rech” findet nichts. Eine Präfixsuche würde verlangen, Tokens für jedes Präfix jedes Wortes zu speichern, was den Index vervielfacht und das Leck vergrößert. Wir haben uns dagegen entschieden.
Ihr Index ist, was Sie indexiert haben. Tokens entstehen, wenn Sie etwas hochladen, anlegen oder umbenennen, unter Ihrem Schlüssel. Ein Dokument, das ein Kollege mit Ihnen geteilt hat, ist nicht in Ihrem Index, bis Sie es anfassen, und Dateien, die über einen anonymen Upload-Link eintreffen, werden gar nicht indexiert, weil der Hochladende Ihren Schlüssel nie hatte.
Gescannte PDFs sind Bilder. Kein Text, keine Tokens. Texterkennung auf dem Gerät würde das lösen und ist ein Kandidat für denselben lokalen Ansatz, den wir für Zusammenfassungen und Übersetzungen verwenden.

Warum dieser Kompromiss

Wir könnten keine Inhaltssuche anbieten und nichts preisgeben, oder serverseitige Suche und alles preisgeben. Der verschlüsselte Suchindex liegt dazwischen: Sie bekommen die Suche, die Menschen tatsächlich benutzen, und der Server bekommt die Form Ihres Vokabulars, nicht das Vokabular. Für eine Organisation, deren Bedrohungsmodell lautet „der Anbieter darf unsere Dokumente nicht lesen können”, ist das der richtige Punkt, und es ist der, bei dem jedes ernsthafte verschlüsselte Produkt mit Suche landet.

Entscheidend ist, dass die Form dokumentiert ist. Der Sicherheitsüberblick führt verblindete Suchtokens unter den Dingen auf, die unsere Server sehen können, und dieser Artikel ist die längere Fassung dieser Zeile.

Fragen?

Wenn Sie besprechen möchten, wie das Suchleck zu Ihrem eigenen Bedrohungsmodell passt, oder Ihr Sicherheitsteam die genauen Tokenisierungsregeln und das Indexschema möchte, schreiben Sie uns an hello@nomadvault.de.