Needham-Schroeder-Protokoll

Das Needham-Schroeder-Protokoll ist ein Protokoll für sicheren Datenaustausch in einem dezentralen Netzwerk. Es vereint Schlüsselaustausch und Authentifikation mit dem Ziel, eine sichere Kommunikation zwischen zwei Parteien in einem dezentralen Netzwerk zu etablieren. Es wurde 1978 von Roger Needham und Michael D. Schroeder im Xerox Palo Alto Research Center entwickelt.^[1] Die Grundlage für die Sicherheit des Protokolls sind sichere Verschlüsselungsalgorithmen mit beliebigen Schlüsseln, die weder durch Kryptoanalyse noch durch erschöpfende Suche gebrochen werden können, wobei symmetrische und asymmetrische Verfahren betrachtet werden.

Die auf asymmetrischer Kryptographie basierende Variante des Needham-Schroeder-Protokolls enthielt einen Fehler, der erst 17 Jahre später (1995) von Gavin Lowe durch eine computergeführte Analyse aufgedeckt wurde.^[2] Lowe beschrieb auch, wie sich der gefundene Fehler durch eine zusätzliche Information in einem Paket beheben lässt.^[3]

Voraussetzung für diese Protokoll-Variante ist, dass sowohl A als auch B jeweils einen geheimen Schlüssel mit dem Authentication-Server (AS) besitzen:

• ${\displaystyle K_{A}}$ – geheimer Schlüssel zwischen AS und A
• ${\displaystyle K_{B}}$ – geheimer Schlüssel zwischen AS und B

Durch Nachweis, dass A ${\displaystyle K_{A}}$ und B ${\displaystyle K_{B}}$ besitzt, werden A und B dem Gegenüber authentifiziert.

Das Protokoll wird von A begonnen. Im ersten Schritt (1) sendet A eine unverschlüsselte Nachricht an den AS, in der die eigene Identität und die des gewünschten Korrespondenten enthalten ist (A und B) sowie eine Nonce ${\displaystyle N_{A}}$. Die Nonce darf von A an dieser Stelle noch nie verwendet worden sein.

Im nächsten Schritt (2) verwendet der AS die geheimen Schlüssel beider Kommunikationspartner. Es wird eine Antwort an A gesendet, die komplett mit ${\displaystyle K_{A}}$ verschlüsselt ist. Sie enthält die Nonce ${\displaystyle N_{A}}$, um sicherzustellen, dass die Antwort nicht eine aufgezeichnete Nachricht eines vorigen Protokoll-Ablaufs ist, der die Verwendung eines alten Schlüssels erzwingen würde. Als Nächstes enthält sie die Identität von B. Damit soll verhindert werden, dass in der Nachricht des ersten Protokoll-Schrittes einfach die Identität von B durch eine andere ersetzt werden könnte, ohne dass A es merkt. Anschließend folgt der Sitzungsschlüssel ${\displaystyle S_{K}}$.

Der letzte Teil besteht aus einem Block, der mit ${\displaystyle K_{B}}$ verschlüsselt ist, welcher sich immer noch innerhalb der mit ${\displaystyle K_{A}}$ verschlüsselten Nachricht an A befindet. Dieser beinhaltet ebenfalls den Sitzungsschlüssel und die Identität von A. A ist nun im Besitz des Sitzungsschlüssels. Im dritten Schritt (3) sendet A den Teil, der in der Antwort vom AS mit ${\displaystyle K_{B}}$ verschlüsselt war, an B. Nur B kann diese Nachricht entschlüsseln und erfährt, dass A mit ihm eine sichere Kommunikation mit dem Sitzungsschlüssel ${\displaystyle S_{K}}$ durchführen möchte. An dieser Stelle besitzen sowohl B als auch A den zu verwendenden Sitzungsschlüssel.

Darüber hinaus weiß A, dass jede Nachricht, die mit ${\displaystyle S_{K}}$ verschlüsselt worden ist, nur von B stammen kann und dass jede Nachricht, die A mit ${\displaystyle S_{K}}$ verschlüsselt, nur von B gelesen werden kann. Beides ist sicher, da der Sitzungsschlüssel ${\displaystyle S_{K}}$ nur mit den geheimen Schlüsseln ${\displaystyle K_{A}}$ und ${\displaystyle K_{B}}$ verschlüsselt versendet worden ist. Für B gilt dasselbe in die umgekehrte Richtung. Zudem weiß A, dass er den Sitzungsschlüssel ${\displaystyle S_{K}}$ vorher noch nie verwendet hat, da die Nonce ${\displaystyle N_{A}}$ in den ersten beiden Protokollschritten eine Replay-Attacke verhindert. Diese Sicherheit liegt bei B noch nicht vor.

Die Nachricht in Protokollschritt 3 könnte eine aufgezeichnete Nachricht sein, die B zwingen würde, einen alten Sitzungsschlüssel wiederzuverwenden. Um dies zu verhindern, gibt es zwei weitere Protokollschritte. Als Nächstes sendet B an A (4) wiederum eine eigene Nonce ${\displaystyle N_{B}}$, die mit dem Sitzungsschlüssel ${\displaystyle S_{K}}$ verschlüsselt ist, und B erwartet im letzten Protokollschritt (5) eine zu dieser Nonce in Beziehung stehende Antwort von A, z. B. ${\displaystyle N_{B}-1}$, die ebenfalls mit ${\displaystyle S_{K}}$ verschlüsselt ist. Da ${\displaystyle N_{B}}$ vorher noch nie verwendet wurde, kann nur A eine entsprechende Antwort senden, denn nur A kennt den Sitzungsschlüssel ${\displaystyle S_{K}}$. B kann nun auch davon ausgehen, dass er keiner Replay-Attacke ausgesetzt ist.

• (1) A ${\displaystyle \rightarrow }$ AS ${\displaystyle \{A,B,N_{A}\}}$
• (2) AS ${\displaystyle \rightarrow }$ A ${\displaystyle \{N_{A},B,S_{K},\{S_{K},A\}_{K_{B}}\}_{K_{A}}}$
• (3) A ${\displaystyle \rightarrow }$ B ${\displaystyle \{S_{K},A\}_{K_{B}}}$
• (4) B ${\displaystyle \rightarrow }$ A ${\displaystyle \{N_{B}\}_{S_{K}}}$
• (5) A ${\displaystyle \rightarrow }$ B ${\displaystyle \{N_{B}-1\}_{S_{K}}}$

Es besteht keine Garantie, dass der Sitzungsschlüssel nicht geknackt werden kann. Dann ist die Authentisierung nicht mehr sichergestellt, weil ein Angreifer durch Wiedereinspielen der dritten Nachricht, die den ihm bekannten Sitzungsschlüssel enthält, die Authentizität untergraben kann. Umgehen lässt sich das, indem man Zeitstempel in die Nachrichten integriert, mit deren Hilfe man dann entscheiden kann, ob es sich um eine Wiedereinspielung handelt oder nicht. Dieses Verfahren setzt synchronisierte Uhren voraus. Anwendung findet es beispielsweise im Netzwerkauthentifizierungsprotokoll Kerberos.

Das Needham-Schroeder-Protokoll kann auch so modifiziert werden, dass es mit asymmetrischen Verschlüsselungsverfahren zusammenarbeitet. Hierzu wird auch wieder eine vertrauenswürdige Instanz T benötigt. Es wird vorausgesetzt, dass Alice, Bob sowie beliebig vielen weiteren Partnern der öffentliche Schlüssel ${\displaystyle P_{T}}$ von T bekannt ist. T kennt zudem die öffentlichen Schlüssel aller beteiligten (hier: ${\displaystyle P_{A}}$ von Alice und ${\displaystyle P_{B}}$ von Bob).

Alice möchte eine sichere Kommunikation mit Bob herstellen. Hierzu braucht sie den öffentlichen Schlüssel von Bob, um Nachrichten an ihn zu verschlüsseln. Da dieser durch einen Man-in-the-Middle-Angriff ausgetauscht werden könnte, muss die vertrauenswürdige Instanz T beteiligt werden, die den Schlüssel schon kennt.

Im ersten Schritt (1) sendet Alice an T eine unverschlüsselte Nachricht, dass sie mit Bob sprechen möchte.

T antwortet (2) mit dem öffentlichen Schlüssel (public key) von B sowie dessen Identität und signiert es mit seinem privaten Schlüssel ${\displaystyle C_{T}}$. Diese Nachricht kann mit dem öffentlichen Schlüssel ${\displaystyle P_{T}}$ von T überprüft werden, also von allen Partnern, die T kennen. Die Nachricht ist nicht geheim, sie soll nur sicherstellen, dass die Antwort wirklich von T kommt und kein Angreifer versucht, Alice einen gefälschten Schlüssel unterzuschieben.

Nun (3) kann Alice an Bob eine Nachricht schicken, die mit seinem öffentlichen Schlüssel ${\displaystyle P_{B}}$ verschlüsselt ist und sowohl eine Nonce ${\displaystyle N_{A}}$ und als Absender Alice beinhaltet. Allerdings kann Bob nicht wissen, ob die Nachricht wirklich von Alice kommt, außerdem kennt Bob den öffentlichen Schlüssel von Alice eventuell noch nicht.

Bob verwendet das gleiche Verfahren wie Alice in den Schritten (1) und (2), um Alices öffentlichen Schlüssel zu bekommen. (Schritte (4) und (5))

Nun antwortet Bob Alice, indem er ihre Nonce ${\displaystyle N_{A}}$ zurückschickt und eine eigene Nonce ${\displaystyle N_{B}}$ anhängt (6), diese Nachricht ist mit Alices öffentlichem Schlüssel verschlüsselt. Alice antwortet mit Bobs Nonce ${\displaystyle N_{B}}$, verschlüsselt mit Bobs öffentlichem Schlüssel (7). Diese letzten beiden Schritte stellen die Aktualität der Nachrichten sicher. Da nur A die Nonce ${\displaystyle N_{B}}$ entschlüsseln konnte und nur B die Nonce ${\displaystyle N_{A}}$ entschlüsseln konnte, können sich beide Parteien sicher sein, mit wem sie kommunizieren.

Sollte ein Angreifer Zugriff auf einen der privaten Schlüssel von Alice, Bob oder der vertrauenswürdigen Instanz T bekommen, ist das Verfahren nicht mehr sicher, da er, je nach gestohlenem Schlüssel, eine der Rollen einnehmen kann.

• (1) A ${\displaystyle \rightarrow }$ T ${\displaystyle A,B}$
• (2) T ${\displaystyle \rightarrow }$ A ${\displaystyle \{B,P_{B}\}_{C_{T}}}$
• (3) A ${\displaystyle \rightarrow }$ B ${\displaystyle \{A,N_{A}\}_{P_{B}}}$
• (4) B ${\displaystyle \rightarrow }$ T ${\displaystyle B,A}$
• (5) T ${\displaystyle \rightarrow }$ B ${\displaystyle \{A,P_{A}\}_{C_{T}}}$
• (6) B ${\displaystyle \rightarrow }$ A ${\displaystyle \{N_{A},N_{B}\}_{P_{A}}}$
• (7) A ${\displaystyle \rightarrow }$ B ${\displaystyle \{N_{B}\}_{P_{B}}}$

• Diffie-Hellman-Schlüsselaustausch
• Otway-Rees-Verfahren

1. ↑ Roger M. Needham, Michael D. Schroeder: Using encryption for authentication in large networks of computers. In: ACM (Hrsg.): Communications of the ACM. Band 21, Nr. 12, Dezember 1978, ISSN 0001-0782, S. 993–999, doi:10.1145/359657.359659. 
2. ↑ Gavin Lowe, An Attack on the Needham-Schroeder Public-Key Authentication Protocol (1995)
3. ↑ Gavin Lowe, Breaking and Fixing the Needham-Schroeder Public-Key Protocol using FDR (1996)