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 Schroeder im Xerox Palo Alto Research Center (MIT) 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.

Interessanterweise enthielt das Needham-Schroeder-Protokoll für asymmetrische Verschlüsselung 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]

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 I_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 I_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 I_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 I_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. I_B − 1, die ebenfalls mit S_K verschlüsselt ist. Da I_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,I_A}
• (2) AS $\rightarrow$ A $\{I_A,B,S_K,\{S_K, A\}_{K_B}\}_{K_A}$
• (3) A $\rightarrow$ B $\{S_K, A\}_{K_B}$
• (4) B $\rightarrow$ A $\{I_{B}\}_{S_K}$
• (5) A $\rightarrow$ B $\{I_{B} - 1\}_{S_K}$

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 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 I_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 I_A zurückschickt und eine eigene Nonce I_B anhängt (6), diese Nachricht ist mit Alice öffentlichem Schlüssel verschlüsselt. Alice antwortet mit Bobs Nonce I_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 I_B entschlüsseln konnte und nur B die Nonce I_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,I_A}P_B
• (4) B $\rightarrow$ T B,A
• (5) T $\rightarrow$ B {A,P_A}C_T
• (6) B $\rightarrow$ A {I_A,I_B}P_A
• (7) A $\rightarrow$ B {I_B}P_B

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 dem ihm bekannten Sitzungsschlüssel enthält) die Authentizität untergraben kann. Umgehen lässt sich das, indem man Zeitstempel in die Nachrichten integriert (Otway-Rees Verfahren), 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.

Siehe auch

Diffie-Hellman-Schlüsselaustausch

Quellen

1. ↑ Roger M. Needham, Michael D. Schroeder: Using encryption for authentication in large networks of computers. In: ACM (Hrsg.): Communications of the ACM. 21, Nr. 12, New York, NY, USA 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)