Honey Encryption

Grundidee

Honey Encryption ist eine symmetrische Verschlüsselungsmethode. Ihr besonderes Merkmal ist: Derselbe Ciphertext wird unter jedem möglichen Schlüssel zu einem plausiblen Klartext entschlüsselt. Das Verfahren wurde im Mai 2014 von Ari Juels und Thomas Ristenpart auf der Eurocrypt cryptography conference vorgestellt.

Bei einer üblichen symmetrischen Verschlüsselung wird ein Klartext mit einem geheimen Schlüssel in einen Ciphertext umgewandelt. Ein Angreifer kann dann eine Brute-Force-Attacke versuchen: Er entschlüsselt den Ciphertext nacheinander mit allen möglichen Schlüsseln und prüft, welcher resultierende Klartext sinnvoll wirkt. Das ist besonders leicht, wenn der Angreifer schon Informationen kennt, etwa eine erwartete Dateistruktur.

Honey Encryption soll diese Plausibilitätsprüfung verhindern oder erschweren. Da jeder ausprobierte Schlüssel eine plausible Nachricht liefert, kann der Angreifer bei einem Brute-Force-Versuch nicht allein aus dem Ergebnis erkennen, welcher Schlüssel richtig ist.

Ablauf der Ver- und Entschlüsselung

Das Verfahren unterscheidet drei Mengen:

• den Nachrichtenraum ${\mathcal {M}}$ (Message Space), also alle möglichen Nachrichten,
• den Schlüsselraum ${\mathcal {K}}$ (Key Space), also alle möglichen Schlüssel,
• den Seed-Raum ${\mathcal {S}}$ (Seed Space), eine Repräsentation der Nachrichten vor der eigentlichen Verschlüsselung.

Die Verschlüsselung hat zwei Schritte. Zuerst bildet eine DTE (Distribution Transforming Encoder) den Klartext auf einen Seed ab. Danach verschlüsselt ein herkömmliches symmetrisches Verfahren diesen Seed mit dem gewählten Schlüssel zu einem Ciphertext.

Bei der Entschlüsselung wird der Ciphertext mit dem Schlüssel zunächst wieder zu einem Seed dekodiert. Die DTE ordnet diesen Seed anschließend einer Nachricht zu. Wird ein falscher Schlüssel verwendet, entsteht ein anderer Seed und damit eine falsche, aber plausible Nachricht.

Aufgabe der DTE

Die DTE ist der wesentliche Bestandteil von Honey Encryption. Sie besteht aus zwei Algorithmen: encode bildet eine Nachricht auf einen Seed ab, decode bildet einen Seed auf eine Nachricht ab.

Einer Nachricht dürfen mehrere Seeds zugeordnet sein, aber jeder Seed darf nur zu genau einer Nachricht gehören. Gibt es für eine Nachricht mehrere mögliche Seeds, wählt encode zufällig genau einen davon aus. encode ist deshalb randomisiert. decode ist dagegen deterministisch: Ein bestimmter Seed führt immer zu derselben Nachricht.

Eine DTE gilt als sicher, wenn die Zahl der Seeds für jede Nachricht ihrer Wahrscheinlichkeit entspricht. Der relative Anteil der Seeds einer Nachricht an allen Seeds soll also möglichst genau der Wahrscheinlichkeit dieser Nachricht entsprechen. Um eine solche DTE zu erstellen, muss die Wahrscheinlichkeitsverteilung der Nachrichten bekannt sein.

Anforderungen an die verwendete Verschlüsselung

Für den zweiten Schritt kann grundsätzlich eine konventionelle symmetrische Verschlüsselungsmethode verwendet werden. Sie kann daher flexibel gewählt werden.

Die notwendige Bedingung ist, dass eine Entschlüsselung mit jedem möglichen Schlüssel auf den Seed-Raum abbildet. Nur dann kann die DTE jeden dabei entstehenden Seed in eine plausible Nachricht umwandeln.

Beispiel und Sicherheitsgrenzen

Im Beispiel werden die möglichen Nachrichten durch die RGB-Farbanteile r, g und b dargestellt. Blau wird mit einer Wahrscheinlichkeit von 50 % gewählt, Rot und Grün jeweils mit 25 %. Die DTE ordnet daher den Nachrichten Seeds entsprechend dieser Verteilung zu. Der Nachricht Grün wird im dargestellten Fall der Seed 01 zugewiesen. Mit dem Schlüssel 10 wird XOR-verknüpft:

$01\oplus 10=11$

Der Ciphertext ist also 11. Bei der Entschlüsselung gilt:

$11\oplus 10=01$

Der Seed 01 wird durch die DTE wieder auf Grün abgebildet. Probiert ein Angreifer stattdessen den Schlüssel 00, erhält er $11\oplus 00=11$. Dieser Seed wird zu Blau dekodiert. Er kann anhand dieses plausiblen Ergebnisses nicht erkennen, dass der Schlüssel falsch ist.

Plausible Ergebnisse allein garantieren jedoch nicht, dass ein Angreifer den richtigen Schlüssel nie findet. Kennt er weitere Informationen, beispielsweise Teile des Klartexts, kann er die entschlüsselten Texte und damit die Schlüssel weiter auf Plausibilität prüfen. Dafür muss er alle möglichen Schlüssel ausprobieren; dies entspricht einer Brute-Force-Attacke. Honey Encryption ist damit mindestens so sicher wie die verwendete Verschlüsselung. Wenn der Angreifer keine zusätzlichen Informationen besitzt und die DTE gut gewählt ist, kann er keinen Schlüssel als den richtigen identifizieren.