# 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. 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. Lowe beschrieb auch, wie sich der gefundene Fehler durch eine zusätzliche Information in einem Paket beheben lässt.

## Symmetrisches Needham-Schroeder-Protokoll

Voraussetzung für diese Protokoll-Variante ist, dass sowohl A als auch B jeweils einen geheimen Schlüssel mit dem Authentication-Server (AS) besitzen:
* $K_{A}$ – geheimer Schlüssel zwischen AS und A
* $K_{B}$ – geheimer Schlüssel zwischen AS und B
Durch Nachweis, dass A $K_{A}$ und B $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 $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 $K_{A}$ verschlüsselt ist. Sie enthält die Nonce $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 $S_{K}$.
Der letzte Teil besteht aus einem Block, der mit $K_{B}$ verschlüsselt ist, welcher sich immer noch innerhalb der mit $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 $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 $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 $S_{K}$ verschlüsselt worden ist, nur von B stammen kann und dass jede Nachricht, die A mit $S_{K}$ verschlüsselt, nur von B gelesen werden kann. Beides ist sicher, da der Sitzungsschlüssel $S_{K}$ nur mit den geheimen Schlüsseln $K_{A}$ und $K_{B}$ verschlüsselt versendet worden ist. Für B gilt dasselbe in die umgekehrte Richtung. Zudem weiß A, dass er den Sitzungsschlüssel $S_{K}$ vorher noch nie verwendet hat, da die Nonce $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 $N_{B}$, die mit dem Sitzungsschlüssel $S_{K}$ verschlüsselt ist, und B erwartet im letzten Protokollschritt (5) eine zu dieser Nonce in Beziehung stehende Antwort von A, z. B. $N_{B}-1$, die ebenfalls mit $S_{K}$ verschlüsselt ist. Da $N_{B}$ vorher noch nie verwendet wurde, kann nur A eine entsprechende Antwort senden, denn nur A kennt den Sitzungsschlüssel $S_{K}$. B kann nun auch davon ausgehen, dass er keiner Replay-Attacke ausgesetzt ist.
* (1) A $\rightarrow$ AS $\{A,B,N_{A}\}$
* (2) AS $\rightarrow$ A $\{N_{A},B,S_{K},\{S_{K},A\}_{K_{B}}\}_{K_{A}}$
* (3) A $\rightarrow$ B $\{S_{K},A\}_{K_{B}}$
* (4) B $\rightarrow$ A $\{N_{B}\}_{S_{K}}$
* (5) A $\rightarrow$ B $\{N_{B}-1\}_{S_{K}}$

### Probleme und Lösungsansätze

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.

## Needham-Schroeder-Protokoll für asymmetrische Verschlüsselung

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 $P_{T}$ von T bekannt ist. T kennt zudem die öffentlichen Schlüssel aller beteiligten (hier: $P_{A}$ von Alice und $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 $C_{T}$. Diese Nachricht kann mit dem öffentlichen Schlüssel $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 $P_{B}$ verschlüsselt ist und sowohl eine Nonce $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 $N_{A}$ zurückschickt und eine eigene Nonce $N_{B}$ anhängt (6), diese Nachricht ist mit Alices öffentlichem Schlüssel verschlüsselt. Alice antwortet mit Bobs Nonce $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 $N_{B}$ entschlüsseln konnte und nur B die Nonce $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 $\rightarrow$ T $A,B$
* (2) T $\rightarrow$ A $\{B,P_{B}\}_{C_{T}}$
* (3) A $\rightarrow$ B $\{A,N_{A}\}_{P_{B}}$
* (4) B $\rightarrow$ T $B,A$
* (5) T $\rightarrow$ B $\{A,P_{A}\}_{C_{T}}$
* (6) B $\rightarrow$ A $\{N_{A},N_{B}\}_{P_{A}}$
* (7) A $\rightarrow$ B $\{N_{B}\}_{P_{B}}$