Sicherheitseigenschaften kryptografischer Verfahren

In der Kryptologie und Kryptoanalyse ist man an der Sicherheit kryptologischer Verfahren interessiert. Im Allgemeinen ist es sinnlos, ein Verfahren als „sicher“ zu bezeichnen, ohne den Begriff der Sicherheit genauer zu definieren. Ein Sicherheitsbegriff leistet genau das: Er gibt an, gegen welche Art von Angriff welche Art von Sicherheit erwartet werden kann. Auch für einen Sicherheitsbeweis ist es wichtig, eine genaue Definition der zu beweisenden Sicherheit zu haben.

Sicherheitsbegriffe für asymmetrische Verschlüsselungsverfahren

Die meisten Sicherheitsbegriffe für Public-Key-Verschlüsselungsverfahren bestehen aus zwei Komponenten. Die erste bezeichnet das zu erreichende Angriffsziel, eine Sicherheitseigenschaft, die der Angreifer verletzen will (z. B. Ciphertext Indistinguishability), die zweite beschreibt die Fähigkeiten der betrachteten Angreiferklasse (z. B. Chosen-Plaintext-Angriffe). Wenn kein Angreifer aus der Klasse gegen ein bestimmtes Verfahren (z. B. das RSA-Verschlüsselungsverfahren) das Angriffsziel erreicht, so erfüllt das Verfahren den Sicherheitsbegriff (in diesem Fall Ciphertext Indistinguishability gegen Chosen-Plaintext-Angriffe, kurz IND-CPA).

Sicherheitsziele

Zwei Sicherheitsziele für asymmetrische Verschlüsselungsverfahren sind recht naheliegend: Es soll nicht möglich sein, den geheimen Schlüssel aus dem öffentlichen zu berechnen (Asymmetrie), und niemand soll ohne den geheimen Schlüssel verschlüsselte Nachrichten lesen können (Einwegeigenschaft).

Unbreakability (UB)

Ein Angreifer kann die Asymmetrie oder Public-Key-Eigenschaft eines asymmetrischen Verfahrens brechen, indem er den geheimen Schlüssel aus dem öffentlichen berechnet. Dieses Sicherheitsziel ist die definierende Eigenschaft für alle asymmetrischen Verfahren.

Bricht ein Angreifer die Asymmetrie des Verfahrens, so hat er damit auch alle anderen Sicherheitsziele gebrochen, denn er kann den geheimen Schlüssel zusammen mit dem Entschlüsselungsalgorithmus benutzen, um Chiffrate zu entschlüsseln, als wäre er der Empfänger. Aus diesem Grund wird Asymmetrie auch als Unbreakability und ihr Bruch auch als Vollständiger Bruch (Total Break) bezeichnet.

One-wayness (OW)

Ein Angreifer bricht die Einwegeigenschaft eines Verschlüsselungsverfahrens, wenn er zu einem beliebigen Chiffrat den zugehörigen Klartext bestimmen kann.

Diese beiden Sicherheitsziele sind zwar notwendig, aber für ein reines Verschlüsselungssystem zu schwach. Ein Angreifer bricht die Einwegeigenschaft nämlich nur, wenn er den vollständigen Klartext berechnen kann. Eine wünschenswerte Eigenschaft ist es aber, dass kein Angreifer irgendwelche Informationen über den Klartext berechnen kann. Das ist nur möglich, wenn das Verschlüsselungsverfahren probabilistisch ist, weil der Angreifer sonst Nachrichten selbst verschlüsseln und so eine Chiffrat-Klartext-Tabelle anlegen kann, die ihm das Entschlüsseln häufiger Nachrichten ermöglicht. Für diese Eigenschaften gibt es drei im Wesentlichen äquivalente Formulierungen. Jeder Angreifer, der die Einwegeigenschaft bricht, bricht auch die folgenden Sicherheitsziele.

Semantische Sicherheit (SEM)

Ein Verschlüsselungsverfahren ist semantisch sicher, wenn jeder Angreifer jede Information, die er aus einem Chiffrat über die Nachricht ableiten kann, bereits dann ableiten kann, wenn er nur die Länge des Chiffrats kennt. Ein Chiffrat verrät also nichts über eine Nachricht als ihre Länge.

Real-Or-Random-Sicherheit (ROR)

Ein Verschlüsselungsverfahren ist ROR-sicher, wenn kein Angreifer unterscheiden kann, ob ein Chiffrat einen von ihm selbst gewählten Klartext verschlüsselt oder eine zufällige Nachricht gleicher Länge.

Ciphertext Indistinguishability (IND)

→ Hauptartikel: Ciphertext Indistinguishability

Ein Verschlüsselungsverfahren besitzt Ununterscheidbarkeit von Chiffraten, wenn kein Angreifer entscheiden kann, welche von zwei gleich langen (von ihm selbst gewählten) Nachrichten ein Chiffrat verschlüsselt. Die Sicherheitsziele semantische Sicherheit, Real-Or-Random-Sicherheit und Ununterscheidbarkeit von Chiffraten sind äquivalent.

Für einige Anwendungen wird eine andere Eigenschaft benötigt. Ein Beispiel für eine solche Anwendung ist eine Auktion. Hier kann es einem Angreifer genügen, ein Gebot abzugeben, das höher ist als das eines Konkurrenten, selbst wenn er nichts über dessen Gebot weiß.

Non-Malleability (NM)

Ein Verschlüsselungsverfahren ist nicht verformbar, wenn kein Angreifer ein Chiffrat so verändern kann, dass die zu den beiden Chiffraten gehörigen Klartexte in einer von ihm gewählten Relation stehen (zumindest nicht öfter, als das bei zufällig gewählten Klartexten der Fall wäre). Ein Angreifer bricht die NM-Sicherheit also, wenn er beispielsweise eine Nachricht $m_{1}$ verschlüsselt, aus dem dadurch entstandenen Chiffrat $c_{1}$ ein Chiffrat $c_{2}$ erzeugt und für dessen Entschlüsselung $m_{2}$ gilt $m_{1}<m_{2}$. Jeder erfolgreiche IND-Angreifer bricht auch die Non-Malleability.

Angreifermodelle

Angreifer können nach ihrer Stärke in drei Kategorien eingeordnet werden:

Adaptiver Chosen-Plaintext-Angriff (CPA)

Bei einem asymmetrischen Verfahren hat der Angreifer immer Zugriff auf den öffentlichen Schlüssel. Er kann also selbst nach Belieben Nachrichten verschlüsseln. Dies wird als Angriff mit frei wählbarem Klartext bezeichnet.

Nichtadaptiver Chosen-Ciphertext-Angriff (CCA1)

Der Angreifer hat Zugriff auf ein Entschlüsselungsorakel, das von ihm gewählte Chiffrate entschlüsselt. Dieses Orakel kann er benutzen, um sich auf die Entschlüsselung von Chiffraten vorzubereiten.

→ Hauptartikel: Chosen-Ciphertext-Angriff

Adaptiver Chosen-Ciphertext-Angriff (CCA2)

Der Angreifer hat Zugriff auf ein Entschlüsselungsorakel und darf die Chiffrate sogar abhängig von dem zu entschlüsselnden Chiffrat wählen. Das Chiffrat selbst darf er allerdings nicht entschlüsseln. Diese theoretische Beschränkung ist notwendig, weil der Begriff sonst unerfüllbar wäre.

Die praktische Relevanz dieses Angreifermodells wurde durch den Angriff von Daniel Bleichenbacher gegen den Standard PKCS#1 demonstriert.

Beziehungen zwischen Sicherheitsbegriffen

Sicherheitsbegriffe setzen sich aus den Sicherheitszielen und den Angreiferstärken zusammen und werden üblicherweise als ein Experiment oder Spiel definiert. Beim IND-CCA2-Experiment erhält der Angreifer Zugriff auf den öffentlichen Schlüssel und ein Entschlüsselungsorakel (CCA2). Dann muss er zwei gleich lange Nachrichten $m_{0},m_{1}$ finden, so dass er eine Verschlüsselung von $m_{0}$ von einer Verschlüsselung von $m_{1}$ unterscheiden kann. Je schwächer das Sicherheitsziel und je stärker der Angreifer, desto stärker der entstehende Sicherheitsbegriff. Sicherheit ist „besser“, wenn sie gegen stärkere Angreifer hält oder wenn der Angreifer selbst niedrig gesetzte Ziele nicht erreichen kann.

Daraus folgt, dass sowohl NM-CPA als auch IND-CCA1 stärker sind als IND-CPA. Die beiden Begriffe sind jedoch unabhängig voneinander, weder ist NM-CPA stärker als IND-CCA1, noch umgekehrt. Der stärkste Begriff der sich bilden lässt ist NM-CCA2. NM-CCA2 ist äquivalent zu IND-CCA2 und ROR-CCA2.

Transformationen

Es gibt mehrere Transformationen im Random-Oracle-Modell, die aus einem IND-CPA-sicheren Verfahren ein IND-CCA2-sicheres Verfahren machen.

Sicherheitsbegriffe für digitale Signaturen

Die Sicherheitsbegriffe für digitale Signaturen sind analog zu denen für Verschlüsselungen aufgebaut und bestehen aus einem Teil, der das Sicherheitsziel beschreibt, und einer Beschreibung der Angreiferstärke.

Sicherheitsziele

Ähnlich den Sicherheitszielen für Verschlüsselungen gibt es auch hier eine Hierarchie.

Unbreakability (UB)

Ähnlich wie bei anderen Public-Key-Verfahren garantiert die Asymmetrie bei digitalen Signaturen, dass aus dem öffentlichen Verifikationsschlüssel nicht der geheime Signaturschlüssel berechnet werden kann. Ein Angreifer, der die Asymmetrie bricht, bricht auch alle anderen Sicherheitsziele.

Universal Unforgeability (UUF)

Ein Angreifer bricht die allgemeine Unfälschbarkeit, wenn er zu einer vorgegebenen Nachricht eine gültige Signatur erzeugen kann.

Selective Unforgeability (SUF)

Ein Angreifer bricht die selektive Unfälschbarkeit, wenn er zu einer Nachricht eine gültige Signatur erzeugen kann, die er ohne Kenntnis des Verifikationsschlüssels selbst gewählt hat. Jeder Angreifer, der die UUF bricht, bricht auch die SUF.

Existential Unforgeability (EUF)

Ein Signaturverfahren ist existenziell unfälschbar, wenn kein Angreifer ein beliebiges Nachrichten-Signaturpaar erzeugen kann. Jeder Angreifer, der die SUF bricht, bricht auch die EUF.

Beim Begriff EUF kann nun noch weiter differenziert werden. In der Standarddefinition muss der Angreifer eine Signatur zu einer Nachricht produzieren, zu der er noch keine Signatur vom Signaturorakel erhalten hat, welche folglich als weak existential unforgeability (wEUF) bezeichnet wird. In einer stärkeren Variante (sEUF) ist es bereits ausreichend, wenn er zu einer beliebigen Nachricht eine Signatur produziert, die er nicht bereits vom Signaturorakel erhalten hat. Hier ist ein Nachrichten-Signaturpaar also sogar dann gültig, wenn zu der Nachricht bereits eine andere Signatur bekannt ist. Jeder Angreifer, der die wEUF bricht, bricht auch die sEUF.

Non-Malleability (NM)

Ein Signaturverfahren ist nicht verformbar, wenn kein Angreifer zu einem gegebenen Nachrichten-Signaturpaar eine weitere gültige Signatur derselben Nachricht erzeugen kann. Das Prinzip von NM ist weit verbreitet in der Kryptographie. Bei Signaturen hingegen wurde NM im Kontext von Sicherheitszielen von sEUF-CMA als Terminologie abgelöst, da beide Definitionen äquivalent sind und im Kontext von Unforgeability sEUF-CMA konsistenter ist.

Angreifermodelle

Es gibt drei klassische Angreifermodelle, von denen aber Variationen existieren. In aufsteigender Stärke des Angreifers geordnet sind das:

Key-Only-Angriff (KOA)

Der Angreifer besitzt nur den Verifikationsschlüssel. Das ist das minimale Angreifermodell für ein Public-Key-Verfahren.

Known-Message-Angriff (KMA)

Der Angreifer kennt vorgegebene Klartext-Signaturpaare. Davon muss ausgegangen werden, wenn ein Signaturverfahren verwendet wird, schließlich sind Signaturen nicht geheim.

Adaptiver Chosen-Message-Angriff (CMA)

Der Angreifer hat Zugriff auf ein Signaturorakel, mit dem er Nachrichten seiner Wahl signieren kann. Die einzige Einschränkung hierbei ist, dass die für ein Sicherheitsexperiment benötigte sogenannte Challenge Nachricht nicht diesem Signaturorakel übergeben werden darf.

Hierbei kann nun weiter differenziert werden, indem man betrachtet, wie der Angreifer die Nachrichten wählt. Bei einem generic CMA werden alle Nachrichten für das Signaturorakel gewählt, bevor der Angreifer den öffentlichen Schlüssel kennt und bevor er Nachrichten Signaturenpaare vom Orakel erhält. Bei einem direct CMA werden die Nachrichten für das Signaturorakel gewählt, nachdem der Angreifer den öffentlichen Schlüssel erhalten hat, aber bevor er Nachrichten Signaturenpaare vom Orakel erhält. Schließlich, in der stärkesten Variante, dem adaptiven CMA, kann der Angreifer dem Signaturorakel Nachrichten geben, auch nachdem er Nachrichten Signaturenpaare davon erhalten hat.