Ciphertext Indistinguishability

Ciphertext Indistinguishability (englisch für Ununterscheidbarkeit von Geheimtexten) ist ein Begriff, der bei Sicherheitsbeweisen von Verschlüsselungsverfahren verwendet wird. Bei einem Verfahren mit dieser Eigenschaft kann ein Angreifer nicht zwischen den Geheimtexten zweier Klartexte unterscheiden, selbst wenn er die Klartexte kennt.

Um über die Sicherheit von Verschlüsselungsverfahren zu sprechen, muss man sich zuerst im Klaren sein, was mit Sicherheit genau gemeint ist. Der erste Gedanke, dass der Angreifer aus dem Geheimtext nicht den Klartext ableiten können darf, ist zu kurz gegriffen. Damit ist nämlich nicht ausgeschlossen, dass ein Angreifer Informationen über Teile des Klartextes erhält, auch wenn er nicht den ganzen Klartext ableiten kann. Es muss also mindestens gefordert werden, dass der Angreifer keine Information über den Klartext lernen kann. Aber auch diese Formulierung ist unter manchen Umständen nicht ausreichend. Wenn ein Public-Key-Verschlüsselungsverfahren nämlich deterministisch ist (also bei gleicher Eingabe immer die gleiche Ausgabe liefert, wie das beispielsweise bei der Lehrbuch-RSA-Verschlüsselung der Fall ist) und der Angreifer den Klartextraum einschränken kann (er weiß z. B., dass die verschlüsselte Nachricht entweder „ja“ oder „nein“ ist), kann er alle möglichen Klartexte mit dem öffentlichen Schlüssel verschlüsseln. Dann kann er durch einfaches Vergleichen des Geheimtexts mit den Geheimtexten, die er selbst erzeugt hat, den zugehörigen Klartext bestimmen. Es gilt also, einen Sicherheitsbegriff zu definieren, bei dem dies nicht möglich ist.

Es ist im Allgemeinen nicht sinnvoll, bei kryptologischen Verfahren von „Sicherheit“ zu sprechen, ohne diese genauer zu qualifizieren. Ein Sicherheitsbegriff besagt, dass ein Angreifer ein bestimmtes Ziel nicht erreichen kann. Die Definition besteht also aus zwei Teilen: Einem Angreifer mit genau beschriebenen Fähigkeiten und dem Sicherheitsziel. Ciphertext indistinguishability (IND) ist ein Sicherheitsziel, nämlich dass es einem Angreifer nicht möglich sein soll, zwischen der Verschlüsselung zweier beliebiger Klartexte gleicher Länge zu unterscheiden (die Verschlüsselungen zweier Klartexte unterschiedlicher Länge können sich durch die Länge des Chiffrats unterscheiden, daher wird die Geheimhaltung der Länge des Klartextes im Allgemeinen nicht gefordert). Damit das auch bei ungünstiger Wahl der Klartexte zutrifft, darf der Angreifer sich zwei Klartexte aussuchen, von denen einer verschlüsselt wird. Dazu können verschiedene Angreiferstärken definiert werden. In der Regel wird der Angreifer in seiner Laufzeit beschränkt, um zu verhindern, dass er den ganzen Schlüsselraum durchsucht oder Aufgaben löst, die in der realen Welt, wo Rechenleistung nicht unbegrenzt verfügbar ist, praktisch unlösbar sind. Bei einem asymmetrischen Verschlüsselungsverfahren muss zudem immer angenommen werden, dass der Angreifer den öffentlichen Schlüssel kennt. Damit kann er selbst beliebige Klartexte seiner Wahl verschlüsseln und mit dem Geheimtext vergleichen, um so etwas über den unbekannten Klartext zu lernen. Dieser Angriff heißt Chosen-plaintext Angriff (CPA). Ein Verschlüsselungsverfahren hat also das Sicherheitsniveau IND-CPA (ciphertext indistinguishability under chosen plaintext attacks), wenn es keinem CPA-Angreifer gelingen kann, das Ziel IND zu erreichen, also die Geheimtexte zweier selbstgewählter Klartexte zu unterscheiden.

Um das formal auszudrücken, wird das Experiment IND-CPA definiert, das zwischen zwei probabilistischen Algorithmen mit polynomialer (in einem Sicherheitsparameter ${\displaystyle k}$) Laufzeitbeschränkung, dem Angreifer A und der Umgebung U, in fünf Schritten abläuft.

1. Zuerst erzeugt die Umgebung zu dem gegebenen Sicherheitsparameter ${\displaystyle k}$ ein Schlüsselpaar aus einem geheimen und einem öffentlichen Schlüssel. Der Angreifer erhält den öffentlichen Schlüssel.
2. Nun darf der Angreifer beliebige Berechnungen ausführen. Am Ende dieses Schritts muss er zwei Klartexte gleicher Länge ${\displaystyle M_{0}}$ und ${\displaystyle M_{1}}$ ausgeben.
3. Die Umgebung zieht ein zufälliges Bit ${\displaystyle b}$ und verschlüsselt ${\displaystyle M_{b}}$. Diesen Geheimtext erhält nun der Angreifer.
4. Der Angreifer darf wiederum beliebige Berechnungen oder Verschlüsselungen ausführen. Am Ende gibt er ein Bit ${\displaystyle b'}$ aus.
5. Falls ${\displaystyle b=b'}$, so gibt die Umgebung „1“ aus, sonst „0“.

Falls die Umgebung eine „1“ ausgibt, hat der Angreifer richtig geraten. Ein Angreifer, der im vierten Schritt unabhängig von allem, was vorher passiert ist, ein Zufallsbit zieht und es ausgibt, liegt mit Wahrscheinlichkeit 1/2 richtig. Ein Verschlüsselungsverfahren wird IND-CPA sicher genannt, wenn kein Angreifer eine Erfolgswahrscheinlichkeit hat, die wesentlich höher als 1/2 liegt, wenn also ${\displaystyle Pr[U=1]-1/2}$ vernachlässigbar klein ist (wenn sie für jedes Polynom ${\displaystyle p}$ ab einer bestimmten Größe von ${\displaystyle k}$ kleiner bleibt als ${\displaystyle 1/p(k)}$). Ein vernachlässigbarer Unterschied muss zugelassen werden, weil es für einen Angreifer sehr leicht ist, seine Erfolgswahrscheinlichkeit über 1/2 zu steigern: Er rät einfach einen geheimen Schlüssel und versucht damit den Geheimtext zu entschlüsseln. Die Erfolgswahrscheinlichkeit dabei ist sehr klein, aber größer als 0. Es ist bei der Definition wichtig, dass über den Angreifer bis auf seine Laufzeitbeschränkung keinerlei Annahmen getroffen werden.

Der Begriff IND-CPA taucht schon 1984 bei Goldwasser und Micali unter dem Namen „polynomiale Sicherheit“ (polynomial security) auf.^[1] Die oben gegebene Definition ist formal nicht ganz korrekt, weil ein Algorithmus in der Informatik nach der Ausgabe stoppt. Ein Angreifer besteht also aus zwei Algorithmen, von denen der erste die zwei Klartexte und seinen Zustand ausgibt. Der zweite erhält als Eingabe die beiden Klartexte, den Zustand und den Geheimtext und gibt ein Bit aus. Durch die Übergabe des Zustandes kann der zweite Algorithmus aber auch als Fortsetzung des ersten verstanden werden.

Der oben eingeführte CPA-Angreifer ist nicht der stärkstmögliche. Den stärkeren Sicherheitsbegriff IND-CCA erhält man, wenn dem Angreifer zusätzlich zu dem öffentlichen Schlüssel noch ein Entschlüsselungsorakel zugestanden wird. Ein Orakel ist ein Algorithmus, der nur zu Eingaben Ausgaben liefert, aber nicht analysiert werden kann. Dadurch ist der im Entschlüsselungsorakel enthaltene geheime Schlüssel dem Angreifer nicht zugänglich. Der Angreifer kann dann in Schritt 2 und 4 beliebige Geheimtexte entschlüsseln lassen, mit Ausnahme des Geheimtexts, den er in Schritt 3 bekommen hat. Dieses Angreifermodell heißt adaptiver chosen-ciphertext Angriff (CCA). Seine praktische Relevanz wurde 1998 vorgeführt, als es Daniel Bleichenbacher gelang, gegen die in PKCS#1 definierte IND-CPA-sichere RSA-Variante einen realistischen Angriff in diesem Modell zu führen.^[2]

In der Literatur wird gelegentlich zwischen CCA1 und CCA2-Angreifern unterschieden. Der CCA2-Angreifer ist der oben als CCA beschriebene, während der CCA1-Angreifer das Entschlüsselungsorakel nur in Schritt 2 zur Verfügung hat. Weil dadurch die Anfragen an das Entschlüsselungsorakel nicht vom Geheimtext in Schritt 3 abhängen können, wird dieser Angriff auch nichtadaptiver chosen-ciphertext Angriff genannt.

• Mihir Bellare, Anand Desai, David Pointcheval and Phillip Rogaway: Relations Among Notions of Security for Public-Key Encryption Schemes. In: Advances in Cryptology - Proceedings of CRYPTO '98. 1998, S. 26–45 (ens.fr). 

1. ↑ Shafi Goldwasser and Silvio Micali: Probabilistic encryption. In: Journal of Computer and System Sciences. Band 28, Nr. 2, 1984, S. 270–299 (mit.edu [PDF; 7,8 MB]). 
2. ↑ Daniel Bleichenbacher: Chosen Ciphertext Attacks Against Protocols Based on the RSA Encryption Standard PKCS #1. In: CRYPTO '98. 1998, S. 1–12 (bell-labs.com).