Formale Analyse kryptografischer Protokolle

Einführung

Seminar WS 2002/03

André Rosin

Inhalt

I. Einführung und Grundbegriffe

II. Szenario (Needham und Schroeder)

III. Ansätze nach Meadows

1. Zustandsmaschinen2. Modale Logiken3. Algebraische Termersetzungssysteme4. Formale Sprachen und Werkzeuge

IV. Schlußbetrachtung

Einführung und Grundbegriffe

Definition: Ein kryptografisches Protokoll ist ein Folge von Schritten mehrerer Teilnehmer zur Erreichung eines Ziels. Es beinhaltet kryptografische Elemente zur Erfüllung von Sicherheitsanforderungen.

Letztere umfassen die Vertraulichkeit, die Integrität, die Authenzität und die Nichtabstreitbarkeit von Daten; kryptografische Elemente werden im Folgenden vorgestellt.

Kryptografische Elemente

Definition: Authentisierung ist der Prozeß durch den ein Teilnehmer eines verteilten Systems seine Identität nachweist.

Typischerweise geschieht dies über einen vertrauenswürdigen Authentisierungsdienstgeber (im folgenden Authentication Server genannt).

Definition: Verschlüsselung (Entschlüsselung) ist die Wissenschaft einen Klartext (chiffrierten Text) in einen chiffrierten Text (Klartext) mittels eines geheimen Schlüssels und eines Verschlüsselungsalgorithmus zu überführen.

... Verschlüsselung Starke Verschlüsselung ist nicht mit vertretbarem

Aufwand (brute force) berechenbar. Man unterscheidet zwei

Ver-/Entschlüsselungsverfahren: symmetrisch: Für Ver- und Entschlüsselung

wird jeweils der gleiche geheime Schlüssel verwendet; arbeitet sehr schnell, aber n Teilnehmer benötigen n*(n-1)/2 Schlüssel

asymmetrisch: es existieren zwei zueinander inverse Schlüssel, private key und public key; langsamer, aber für n Teilnehmer 2*n Schlüssel

Digitale Signatur

Digitale Signatur ist das Analogon zur Unterschrift im realen Leben

Basiert auf asymmetrischen Verfahren: Alice signiert eine Nachricht an Bob mit ihrem eigenen privaten Schlüssel, Bob entschlüsselt sie mit dem öffentlichen Schlüssel von Alice.

Dadurch authentifiziert sich Alice unabstreitbar gegenüber Bob. Verschlüsselt wird in der Regel nur der Hashwert der Nachricht H=h(M).

Zertifikate Für das korrekte Funktionieren der Signatur ist es

unabkömmlich, dass der öffentliche Schlüssel von Alice echt ist

Dazu wird eine vertrauenswürdige dritte Partei, eine Zertifizierungsstelle, benötigt, welche allen bekannt ist

Nachdem sich Alice gegenüber dieser Partei identifiziert hat, bürgt sie gewissermaßen für Alice

Verschlüsselt wird in der Regel nach dem Signieren und nicht umgekehrt (Sicherheit)!

Aktualität von Nachrichten

Für die an in einem kryptografischen Protokoll involvierten Teilnehmer ist es essentiell erkennen zu können, ob eine Nachricht aus dem aktuellen Protokollablauf stammt oder von einem Angreifer aus einem vergangenen Protokollablauf wiederholt wird (alte Sitzungsschlüssel können kompromittiert sein).

Zeitliche Aspekte sollten deshalb in kryptografischen Protokollen modelliert werden, dazu zwei Möglichkeiten: Zeitstempel und Nonces

Zeitstempel und Nonces

Zeitstempel liefern genaue Zeitpunkte, aber erfordern synchronisierte Uhren bei allen Teilnehmern

Nonce (engl. a number used once) ist eine zufallsgenerierte Zahl, die in einem aktuellen Protokollablauf einen anderen Wert annimmt als in vorangegangenen Protokollabläufen

Unvorhersagbare Nonces sind Außenstehenden nicht bekannt, jedoch schwer zu erzeugen

Szenario

NetzAlice Bob

Authentication Server

Oskar

Das Bedrohungsmodell

Das Bedrohunsmodell beschreibt die angenommenen Eigenschaften der Sicherheitsumgebung. Es beinhaltet Annahmen über die Teilnehmer und mögliche Störungen von böswilligen Akteuren. Es wird angenommen, dass es einen Angreifer gibt, der Nachrichten abfangen, löschen, modifizieren und nach belieben erzeugen kann -> Vorraussetzung: starke Verschlüsselung.

Weiterhin wird angenommen, dass die zugrundeliegenden Schlüssel und Verschlüsselungsalgorithmen perfekt sind.

Needham und Schoeder Austausch eines geheimen Schlüssels in einem

Netzwerk A(lice) möchte mit B(ob) über S(=AuS)

kommunizieren; dazu nötige Schritte:

1. A –> S : A, B, Na (unverschlüsselt) 2. S –> A : {Na, B, Kab, {Kab, A}Kbs }Kas 3. A –> B : {Kab, A}Kbs 4. B –> A : {Nb}Kab (=handshake) 5. A –> B : {Nb-1}Kab

Möglicher Angriff Der Angreifer Z besitzt im Gegensatz zu A und B

kein beschränktes Gedächtnis und hat vorangegangene Sitzungen mitgeschnitten und dadurch den Sitzungsschlüssel CK kompromittiert. Nun kann Z mittels CK B glaubhaft machen, dass er/sie A ist:

Z –> B : {CK, A}Kbc (für B neue Sitzung) B –> A : {Nb}CK (handshake) Z –> B : {Nb-1}CK (Z immitiert A)

Behandlung der Schwäche

Es wird ein Zeitstempel hinzugefügt:

2. S –> A : {T, Na, B, Kab, {Kab, A, ...

... T}Kbs }Kas 3. A –> B : {Kab, A, T}Kbs

Somit wird die Wiederholung von Schritt 3 als „alt“ erkannt und ignoriert.

Ansätze der formalen Analyse

Die formale Analyse von kryptografischen Protokollen ist eine relativ junge Wissenschaft, die in den frühen 90ern aus dem Bedürftnis heraus entstand, die Korrektheit dieser Protokolle hinsichtlich ihrer „Sicherheit“ zu beweisen

Vorweg: die Sicherheit eines Protokolls kann mit keiner der folgenden Methoden garantiert werden

Am beliebtesten sind die Ansätze 1 und 2, inbesondere jedoch die BAN-Logik (aus Ansatz 2)

(1) Zustandsmaschinen

Nach Meadows auch Expertensysteme genannt Das kryptografische Protokoll wird als eine Reihe

von Zuständen und Transformationsregeln betrachtet

Vorgegeben wird dann ein nicht gewünschter, bzw. fehlerhafter Zustand des Protokolls

Vom Initialzustand des Protokolls ausgehend wird nun in einer ausschöpfenden Suche ein Pfad zum unerwünschten Zustand gesucht

(1) Zustandsmaschinen

Gibt es einen solchen Pfad, so wurde ein möglicher Angriff erkannt.

Die Suche muß dabei nicht terminieren, da es gegebenenfalls unendlich viele Zustände in einem solchen regelbasierten System gibt

Somit können nur bekannte Protokollschwächen, jedoch keine unbekannten Protokollfehler mit Zustandsmaschinen modelliert werden

(1) Zustandsmaschinen Bekannte Vertreter für

Zustandsmaschinen/Expertensysteme sind:

Interrogator von Millen Longley und Rigby Tool NRL Protocol Analyzer

Diese Werkzeuge basieren teilweise auf Dolev und Yaos Model, welches unter Ansatz 3 aufgeführt ist.

(2) Modale Logiken Modale Logiken ähneln den Logiken von

„Glauben und Wissen“ in verteilten Systemen Beginnend mit einer initialen Menge von

Glaubens- und Wissensmodellierungen werden mittels Schlussregeln aus „alten“ neue Aussagen gewonnen

Glauben wird somit axiomatisiert Sind die gezogenen Schlüsse adäquat zu den

vordefinierten Glaubensaufstellungen, so wird das kryptografische Protokoll als korrekt betrachtet

Üblicherweise entscheidbar und berechenbar

(2) Modale Logiken

Modale Logiken können lediglich Authorisierungsprotokolle behandeln

So werden etwa Authorisierungsziele 1. oder 2. Ordnung angestrebt: 1. Ordnung: Es gibt Schlüssel K, sodaß

A und B jeweils glauben A B über K 2. Ordnung: Es gibt Schlüssel K, sodaß

A glaubt B glaubt A B über K und

B glaubt A glaubt A B über K

(2) Modale Logiken Der Hauptvertreter ist die erfolgreiche, aber auch

umstrittene BAN-Logik (Burrows,Abadi und Needham), welche sich durch ihre Einfachheit und Abstraktionsweise abhebt

Erweiterungen zur BAN-Logik gibt es viele: GNY-Logik (Gong,Needham und Yahalom), Kailar, Gligor und Gong-Logik, Mao und Boyd-Logik sowie Gaarder und Suekkenes-Logik

Weitere Vertreter: Biebers CKT5, Syversons KPL, Rangans Logik des „Vertrauens“, Mosers Logik und das System von Yahalom, Klein und Beth

(3) Algebraische Termersetzungssystem

Das kryptografische Protokoll wird als ein algebraisches System betrachtet und der Zustand des Wissens der Teilnehmer über das Protokoll wird modelliert

Im Gegensatz zu Zustandsmaschinen versucht man zu zeigen, dass aus dem Initialzustand unsichere Zustände nicht erreicht werden können und bestätigt somit die Korrektheit des Protokolls

(3) Algebraische Termersetzungssysteme

Modelliert wird die Fähigkeit des Angreifers Wörter zu generieren, die das Regelwerk des Protokolls zulässt und welche in der geheimen Menge der tatsächlichen Wörter vorhanden sind

Dieser Ansatz verbindet die Ansätze 1 und 2 miteinander, also Zustandsmaschinen mit modalen Logiken und könnte somit verbesserte Zustandsmaschinen hervorbringen hinsichtlich des Wissens, das ein Angreifer des Protokolls erlangen kann

(3) Algebraische Termersetzungssysteme

Als Hauptvertreter dieses Ansatzes ist das Model von Dolev und Yao zu verzeichnen

Weitere Vertreter finden sich in der PhD thesis von Merrit, im Narrower Algorithmus von Meadows und im Toussaint Model

Obwohl viel versprechend ist dieser Ansatz bisher nicht weit verbreitet, da die Modellierungen sehr komplex sind

(4) Formale Sprachen und Werkzeuge

Dieser Ansatz beschäftigt sich mit Spezifikationssprachen und Verifikationswerkzeugen, welche ursprünglich nicht für die Analyse kryptografische Protokolle entwickelt wurden

Viel mehr handelt es sich um Werkzeuge die allgemein die Korrektheit von Software nachzuweisen versuchen

Da jedoch Korrektheit im Allgemeinen nicht gleich Sicherheit gesetzt werden kann, ist dieser Ansatz weniger für die Analyse geeignet

(4) Formale Sprachen und Werkzeuge

Vertreter dieses Ansatzes sind endliche Automaten, die Sprache LOTOS (language of temporal ordering specification) und die Sprache Ina Jo, welche eine Erweiterung der Prädikatenlogik erster Stufe darstellt

Mit diesem Ansatz wurden bisher keine konkreten Ergebnisse erzielt

Schlußbetrachtung Fazit ist: keine formale hier vorgestellte Methode

kann wirklich alle Aspekte eines kryptografischen Protokolls modellieren

Man kann lediglich garantieren, daß ein solches Protokoll korrekt in bezug auf eine Menge von wohldefinierten Annahmen ist

Speziell die BAN-Logik liefert große Kontroversen über die Modellierung von Logiken und Annahmen

Prinzipiell kann man jedoch nicht sagen, dass ein Modell nützlicher ist, desto detailierter es ist

Schlußbetrachtung (2) Auf verschiedenen Abstraktionsebenen haben

jedoch alle Modelle einen gewissen Nutzen So sollten etwa abstrakte Modelle am Anfang der

Designphase eines kryptografischen Protokolls eingesetzt werden, wenn noch keine konkreten Implementationsdetails behandelt werden

Für die Strukturfestlegung der Nachrichten könnte dann ein zustandsbasiertes Modell verwendet werden usw.

So läßt sich ein Minimum an Aufwand bei der Implementation eines solchen Protokolls erzielen

Ende

Gibt es Fragen?