DE60200496T2

DE60200496T2 - Verfahren und Vorrichtung zur Ausführung eines effizienten mittels Kennwort authentifizierten Schlüsselaustauschs

Info

Publication number: DE60200496T2
Application number: DE60200496T
Authority: DE
Inventors: Philip D. Maplewood MacKenzie
Original assignee: Lucent Technologies Inc
Current assignee: Nokia of America Corp
Priority date: 2001-04-05
Filing date: 2002-03-22
Publication date: 2005-06-23
Anticipated expiration: 2022-03-23
Also published as: EP1248408A3; JP2002335238A; EP1248408A2; EP1248408B1; US20020194478A1; JP4237970B2; CA2376947C; CA2376947A1; US7076656B2; DE60200496D1

Description

Erfindungsgebiet
Die vorliegende Erfindung betrifft allgemein Techniken zur Bereitstellung von Netzwerkauthentisierung und Schlüsselaustausch und insbesondere Techniken zur Verbesserung der rechnerischen Effizienz, die einer solchen Netzwerkauthentisierung und einem Schlüsselaustausch zugeordnet ist.
Allgemeiner Stand der Technik
Die Authentisierung über ein Netzwerk ist ein wichtiger Teil der Sicherheit für Systeme, die entfernten Clients einen Zugriff auf Netzwerkserver erlauben. Authentisierung wird im allgemeinen erreicht, indem z. B. folgendes verifiziert wird:

(i) etwas einem Benutzer Bekanntes, z. B. ein Passwort;
(ii) etwas, das ein Benutzer ist, d. h. biometrische Informationen, wie zum Beispiel ein Fingerabdruck; und
(iii) etwas, das ein Benutzer besitzt, d. h. ein bestimmtes Identifizierungs-Token, wie zum Beispiel eine Chipkarte.

Zum Beispiel verifiziert ein Geldautomat (ATM) zwei davon: etwas, das ein Benutzer besitzt, die ATM-Karte, und etwas, das einem Benutzer bekannt ist, eine persönliche Geheimnummer (PIN). ATM-Authentisierung ist wesentlich einfacher als Authentisierung über ein Datennetzwerk, da der ATM selbst als vertrauenswürdige Hardware betrachtet wird, so dass ihm anvertraut wird, das Vorhandensein der ATM-Karte zu verifizieren und die korrekten Informationen sicher zu einem zentralen Transaktionsserver zu transferieren.
Zusätzlich zu der Authentisierung ist Schlüsselaustausch ein wichtiger Teil der Kommunikation über ein Datennetzwerk. Nachdem ein Client und ein Server authentisiert wurden, muss ein sicherer Kommunikationskanal zwischen ihnen eingerichtet werden. Dazu tauschen der Client und Server im allgemeinen einen Schlüssel aus, der als Sitzungsschlüssel bezeichnet und während der Kommunikation nach der Authentisierung verwendet wird.
Die Authentisierung über ein Datennetzwerk, insbesondere ein öffentliches Datennetzwerk wie das Internet, ist schwierig, weil die Kommunikation zwischen dem Client und dem Server für viele verschiedene Arten von Attacken anfällig ist. Zum Beispiel kann bei einer Lauschattacke ein Gegenspieler geheime Informationen erfahren, indem er die Kommunikation zwischen dem Client und dem Server abfängt. Wenn der Gegenspieler Passwortinformationen erfährt, kann der Gegenspieler diese Informationen dem Server abspielen, um sich bei einer sogenannten Wiederabspielattacke für den rechtmäßigen Client auszugeben. Wiederabspielattacken sind auch dann effektiv, wenn das von dem Client gesendete Passwort verschlüsselt ist, weil der Gegenspieler das tatsächliche Passwort nicht kennen muss, sondern dem Server nur etwas geben muss, das der Server von dem rechtmäßigen Client erwartet (in diesem Fall ein verschlüsseltes Passwort). Eine weitere Art von Attacke ist eine Spoof-Attacke, bei der sich ein Gegenspieler für den Server ausgibt, so dass der Client glaubt, dass er mit dem rechtmäßigen Server kommuniziert, stattdessen aber mit dem Gegenspieler kommuniziert. Bei einer solchen Attacke kann der Client dem Gegenspieler heikle Informationen zuführen.
Ferner gibt es bei jedem Authentisierungsprotokoll auf Passwortbasis die Möglichkeit, dass Passwörter schwach sind, so dass sie für Wörterbuchattacken anfällig sind. Eine Wörterbuchattacke ist eine Brute-Force-Attacke auf ein Passwort, die durch Ausprobieren einer großen Anzahl wahrscheinlicher Passwörter (z. B. aller Wörter in einem englischen Wörterbuch) an bestimmten bekannten Informationen über das gewünschte Passwort durchgeführt wird. Die bekannten Informationen können öffentlich verfügbar sein oder vom Gegenspieler durch eine der obenbeschriebenen Techniken erhalten worden sein. Wörterbuchattacken sind häufig effektiv, weil Benutzer häufig Passwörter wählen, die man sich leicht merken kann und die leicht erraten werden können.
Es gibt verschiedene bekannte Techniken zur Netzwerkauthentisierung. Diese Techniken werden in zwei Klassifizierungen eingeteilt. Die erste Klassifizierung umfasst die Techniken, die dauerhaft gespeicherte Daten in dem Client-System erfordern. Die zweite Klassifizierung umfasst die Techniken, die keine dauerhaft gespeicherten Daten in dem Client-System erfordern.
Mit Bezug auf die erste Klassifizierung können dauerhaft gespeicherte Daten entweder geheime Daten umfassen (z. B. Geheimschlüssel, die mit dem Authentisierungsserver geteilt werden), die niemals enthüllt werden dürfen, oder nicht geheime, aber heikle Daten (z. B. den öffentlichen Schlüssel des Authentisierungsservers), die manipulationssicher sein müssen. Bei beiden Arten von dauerhaften Daten sind zusätzliche Sicherheitsanforderungen notwendig, um die Daten vor einer Attacke eines Gegenspielers zu schützen. Wenn ein Authentisierungsprotokoll verwendet wird, das sowohl Passwörter als auch dauerhaft gespeicherte Daten verwendet, kann eine Kompromittierung eines dieser zu einer Anfälligkeit des anderen führen. Zum Beispiel kann die Kompromittierung eines Geheimschlüssels zu einer möglichen Wörterbuchattacke an dem Passwort führen. Ein weiteres Problem bei dieser ersten Klasse von Protokollen besteht darin, dass dauerhaft gespeicherte Daten die Erzeugung und Verteilung von Schlüsseln erfordert, was umständlich sein kann und im allgemeinen ein weniger flexibles System ergibt.
Die zweite Klassifizierung wird als Nur-Passwort-Authentisierungsprotokolle bezeichnet, da keine Anforderung dauerhaft gespeicherter Daten in dem Client besteht. Der Client muss nur in der Lage sein, ein rechtmäßiges Passwort bereitzustellen. Das Prinzip des Bereitstellens einer starken Sicherheit und Authentisierung unter Verwendung potentiell schwacher Passwörter scheint widersprüchlich zu sein. Es gibt jedoch mehrere Nur-Password-Benutzerauthentisierungs- und Schlüsselaustauschprotokolle, die sicher ausgelegt sind. Eine Beschreibung dieser Protokolle findet sich in D. Jablon, Strong Password-Only Authenticated Key Exchange, ACM Computer Communication Review, ACM SIGCOMM, 26(5): 5–20, 1996. Ein Teil der bemerkenswerteren der Nur-Passwort-Protokolle umfasst verschlüsselten Schlüsselaustausch (EKE), wie in S. M. Bellovin und M. Merritt, Encrypted Key Exchange: Password-Based Protocols Secure Against Dictionary Attacks, Proceedings of the IEEE Symposium on Research in Security and Privacy, S. 72–84, 1992; Augmented-EKE (A-EKE), S. M. Bellovin und M. Merrit, Augmented Encrypted Key Exchange: A Password-Based Protocol Secure Against Dictionary Attacks and Password File Compromise, Proceedings of the First Annual Conference on Computer and Communications Security, 1993, Seiten 244–250; Modified EKE (M-EKE), M. Steiner, G. Tsudik und M. Waidner, Refinement and Extension of Encrypted Key Exchange, ACM Operating System Review, 29: 22–30, 1995; Simple Password EKE (SPEKE) and Diffie-Hellman EKE (DH-EKE), beides beschrieben in D. Jablon, Strong Password-Only Authenticated Key Exchange, ACM Computer Communication Review, ACM SIGCOMM, 26(5): 5–20, 1996; Secure Remote Password Protocol (SRP), T. Wu, The Secure Remote Password Protocol, Proceedings of the 1998 Internet Society Network and Distributed System Security Symposium, Seiten 97–111, 1998; Open Key Exchange (OKE), Stefan Lucks, Open Key Exchange: How to Defeat Dictionary Attacks Without Encrypting Public Keys, Security Protocol Workshop, Ecole Normale Sup'erieure, 7.–9.4.1997; "Authenticated Key Exchange (AKE)", M. Bellare, D. Pointcheval und P. Rogaway, "Authenticated Key Exchange Secure Against Dictionary Attacks", Advances in Cryptology, S. 139–155, Eurocrypt 2000; und EP-A-1 069 726 beschrieben wird.
Das Problem bei den meisten bekannten Nur-Passwort-Authentisierungsprotokollen besteht darin, dass sie sich nicht als sicher erwiesen haben. Tatsächlich kann das EKE-Protokoll gegenüber bestimmten theoretischen Attacken anfällig sein, wie in S. Patel, „Number Theoretic Attacks on Secure Password Schemes", Proceedings of the IEEE Symposium on Research in Security and Privacy, Seiten 236–247, 1997, beschrieben wird. Obwohl sich das AKE-Protokoll als sicher erwiesen hat, erfordert es starke Annahmen, um Sicherheit zu beweisen. Außerdem basiert das SNAPI-Protokoll, das sich zwar auch als sicher erwiesen hat, jedoch nicht auf Diffie-Hellman, sondern auf dem RSA-Algorithmus.
Aus EP-A-1 134 929 (veröffentlicht am 19.9.2001, nach dem für die vorliegende Anmeldung beanspruchten Konventionsprioritätsdatum) ist ein sicheres Nur-Passwort-Protokoll für gegenseitige Netzwerkauthentisierung und Schlüsselaustausch bekannt, das nachweisbar sicher ist und ein gemeinsames Geheimnis des Diffie-Hellman-Typs verwendet, aber so modifiziert ist, dass sich die beiden Parteien gegenseitig unter Verwendung eines gemeinsam benutzten Passworts authentisieren können.
Aus Boyko V. et al: „Provably Secure Password-Authenticated Key Exchange Using Diffie-Hellman" Advances in Cryptology – EUROCRYPT 2000. International Conf. on the Theory and Application of Cryptographic Techniques. Bruges, BE, 14.–18.5.2000, Proceedings, Lecture Notes in Computer Science, Berlin: Springer, DE, Band 1807, 14.5.2000 (2000-05-14), Seiten 156–171, XP000896058 ISBN: 3-540-67517-5 ist ein Protokoll bekannt, dass ein passwortauthentisiertes Schlüsselaustauschprotokoll auf Diffie-Hellman-Basis ist, das einen formalen Beweis der Sicherheit gegenüber sowohl passiven als auch aktiven Gegenspielern gibt.
Kurze Darstellung der Erfindung
Verfahren und Vorrichtungen gemäß der Erfindung werden in den unabhängigen Ansprüchen definiert. Bevorzugte Formen werden in den abhängigen Ansprüchen definiert.
Die vorliegende Erfindung stellt ein sicheres Nur-Passwort-Protokoll für die gegenseitige Netzwerkauthentisierung bereit, das nachweisbar sicher ist. Gemäß dem erfindungsgemäßen Protokoll erzeugen zwei Parteien unter Verwendung eines Schlüsselaustausches des Diffie-Hellman-Typs ein gemeinsames Geheimnis. Bekanntlich gibt es gemäß dem Schlüsselaustausch des Diffie-Hellman-Typs einen Gruppengenerator g für eine bestimmte Gruppe, einen einer Partei bekannten Index x, einen der anderen Partei bekannten Index y und das gemeinsame Geheimnis g^xy. Eine Partei erzeugt g^x, die andere Partei erzeugt g^y und die Parteien tauschen diese Werte aus, so dass jede Partei nun das gemeinsame Geheimnis g^xy erzeugen kann. Obwohl Diffie-Hellman ein Schlüsselaustauschprotokoll definiert, hat das Protokoll keine Authentisierungsaspekte.
Gemäß der vorliegenden Erfindung wird somit ein Protokoll bereitgestellt, das ein gemeinsames Geheimnis des Diffie-Hellman-Typs verwendet, das aber so modifiziert ist, dass die beiden Parteien sich unter Verwendung eines gemeinsam benutzten Passworts gegenseitig authentisieren können. Ferner haben die Verfasser bewiesen, dass dieses Protokoll sicher ist.
Gemäß der Erfindung erzeugt eine Partei den Diffie-Hellman-Wert g^x und kombiniert ihn mit einer Funktion mindestens des Passworts unter Verwendung einer Gruppenoperation, wobei ein beliebiger Teil eines mit der Funktion assoziierten Ergebnisses, der außerhalb der Gruppe liegt, randomisiert wird. Der resultierende Wert wird zu der anderen Partei gesendet. Die Gruppenoperation ist für die bestimmte verwendete Gruppe definiert und wird später ausführlicher beschrieben. Für die vorliegenden Zwecke reicht es aus, zu erkennen, dass jede Gruppe eine Gruppenoperation und eine entsprechende inverse Gruppenoperation aufweist.
Nach dem Empfang des Werts führt die andere Partei die inverse Gruppenoperation an dem empfangenen Wert und der Funktion mindestens des Passworts durch und entfernt die Randomisierung jedes Teils des mit der Funktion assoziierten Ergebnisses, der außerhalb der Gruppe liegt, um g^x zu extrahieren, so dass die andere Partei dann unter Verwendung ihrer Kenntnis von y das gemeinsame Geheimnis g^xy erzeugen kann.
Die Verwendung der Gruppenoperation und der inversen Gruppenoperation in Verbindung mit einem Schlüsselaustauschprotokoll des Diffie-Hellman-Typs, so wie sie hier beschrieben wird, hat gegenüber Nur-Passwort-Protokollen zur gegenseitigen Netzwerkauthentisierung Vorteile. Die Randomisierung jedes Teils des mit der Funktion assoziierten Ergebnisses, der außerhalb der Gruppe liegt, verringert die rechnerische Intensität, die den durch die eine Partei durchgeführten Operationen zugeordnet ist. Vorteilhafterweise liefert die vorliegende Erfindung ein Protokoll, von dem bewiesen werden kann, dass es gegenüber Attacken durch Gegenspieler, die Zugang zu dem Kommunikationskanal haben, sicher ist.
Wie oben beschrieben, wird der Diffie-Hellman-Wert g^x mit einer Funktion mindestens des Passworts kombiniert.
Der Begriff „mindestens" wird benutzt, weil bei verschiedenen Ausführungsformen g^x mit einer Funktion nur des Passworts kombiniert werden kann, oder mit einer Funktion des Passworts zusammen mit Kennungen der Parteien in den Protokoll, um sicherzustellen, dass das Passwort für ein beliebiges bestimmtes Parteienpaar einzigartig ist.
Gemäß einer Ausführungsform der Erfindung können sich die Parteien gegenseitig authentisieren, indem sie eine Funktion mindestens bestimmter Parameter berechnen, den berechneten Wert zu der anderen Partei senden und dann jede Partei den empfangenen Wert mit seinem eigenen berechneten Wert vergleichen. Die für die Berechnung verwendeten Parameter können eine Parteikennung, der Diffie-Hellman-Wert (g^x oder g^y), das gemeinsame Geheimnis und/oder das gemeinsame Passwort sein. Durch Berechnen einer Funktion mindestens einer dieser Werte können die Parteien authentisieren, dass die andere Partei das gemeinsam benutzte Passwort besitzt.
Diese und andere Aufgaben, Merkmale und Vorteile der vorliegenden Erfindung werden aus der folgenden ausführlichen Beschreibung von Ausführungsbeispielen deutlich, die in Verbindung mit den beigefügten Zeichnungen gelesen werden soll.
Kurze Beschreibung der Zeichnungen
1 zeigt das Diffie-Hellman-Schlüsselaustauschprotokoll;
2 zeigt ein Protokoll für gegenseitige Authentisierung und Schlüsselaustausch, bei dem beide Parteien ein gemeinsam benutztes Passwort besitzen;
3 zeigt ein Protokoll für gegenseitige Authentisierung und Schlüsselaustausch mit verbesserter Effizienz gemäß einer Ausführungsform der vorliegen Erfindung, bei dem beide Parteien ein gemeinsam benutztes Passwort besitzen; und
4 zeigt eine verallgemeinerte Hardwarearchitektur eines Datennetzwerks und von Computersystemen, die sich für die Implementierung einer oder mehrerer der durch Passwort authentisierten Schlüsselaustauschmethodologien gemäß der vorliegenden Erfindung eignen.
Ausführliche Beschreibung bevorzugter Ausführungsformen
Kryptographie ist eine wohlbekannte Technik zur Bereitstellung einer sicheren Kommunikation zwischen zwei Parteien. Vor der Beschreibung verschiedener Ausführungsformen der vorliegenden Erfindung werden einige Hintergrundinformationen und grundlegende Terminologie angegeben.
Informell ist eine Funktion f von einer Menge S in eine Menge T eine Einwegfunktion, wenn f(x) für alle x in S leicht berechenbar ist, es aber für die meisten y in T rechnerisch impraktikabel ist, irgendein x in S zu finden, für das f(x) = y gilt. Ein Beispiel für eine Einwegfunktion ist modulare Exponentionierung. Es sei p eine große Primzahl und g ein Generator der multiplikativen Gruppe mod p (das heißt die Zahlen im Bereich 1, ..., p – 1). Von f(x) = g^x mod p wird dann allgemein angenommen, dass es sich um eine Einwegfunktion handelt. Die Umkehrfunktion, die als diskrete log-Funktion bezeichnet wird, ist schwierig zu berechnen. Außerdem gibt es andere Gruppen, bei denen die diskrete log-Funktion schwierig zu berechnen ist, wie zum Beispiel bestimmte Gruppen elliptischer Kurven.
Es seien k und l Sicherheitsparameter, wobei k der Hauptsicherheitsparameter ist und als allgemeiner Sicherheitsparameter für Hash-Funktionen und geheime Schlüssel (z. B. 160 Bit) angesehen werden kann, und wobei l > k als Sicherheitsparameter für öffentlichen Schlüssel auf diskret-log-Basis (z. B. 1024 oder 2048 Bit) betrachtet werden kann. Es sei {0,1}^* die Menge endlicher Binärketten und {0,1}ⁿ die Menge binärer Ketten der Länge n. Eine reellwertige Funktion ε(n) ist vernachlässigbar, wenn für jedes c > 0 ein n_c > 0 existiert, so dass ε(n) < 1/n für alle n > n_c gilt. Es seien q der Größe mindestens k und p der Größe l Primzahlen, so dass für einen bestimmten Wert r, der zu q Koprim ist, p = rq + 1 gilt. Es sei g ein Generator einer Untergruppe von Z * / p von der Größe q. Diese Untergruppe heiße G_p,q.
Ein als Diffie-Hellman-Schlüsselaustausch bezeichnetes Schlüsselaustauschprotokoll wird in W. Diffie und M. Hellman, New Directions in Cryptography, IEEE Transactions on Information Theory, Band 22, Nr. 6, 644–654, 1976, beschrieben und basiert auf der modularen Exponentiierungsfunktion. Genauer gesagt vereinbaren zwei Parteien A und B einen Geheimschlüssel gemäß dem in Verbindung mit 1 beschriebenen Protokoll. Im Schritt 102 wählt A ein zufälliges x aus der Gruppe Z_q (d. h. x ∊_R Z_q), mit Z_q = {0, 1, ..., q – 1} (oder einfach die ganzen Zahlen mod q). Im Schritt 104 berechnet A X = g^x mod p. Im Schritt 106 sendet A X zu B. Im Schritt 108 wählt B ein zufälliges y aus Z_q (d. h. y ε_R Z_q). Im Schritt 110 berechnet B Y = g^y mod p und sendet Y im Schritt 112 zu A. An diesem Punkt kann sowohl von A als auch von B ein gemeinsames Geheimnis g^xy (d. h. ein Geheimschlüssel) berechnet werden. Man beachte, dass im folgenden der einfacheren Schreibweise halber die Notation mod p ignoriert werden kann, wenn klar ist, daß in mod p gearbeitet wird. Da im Schritt 106 X = g^x von A zu B gesendet wurde, kann B im Schritt 116 durch Berechnen von X^y das gemeinsame Geheimnis g^y berechnen. Da im Schritt 112 Y = g^y von B zu A gesendet wurde, kann ähnlich A durch Berechnen von Y^x im Schritt 114 das gemeinsame Geheimnis g^xy berechnen. Das gemeinsame Geheimnis S kann nun von A und B als Sitzungsschlüssel für die sichere Kommunikation verwendet werden.
Der Diffie-Hellman-Schlüsselaustausch kann auch über andere Gruppen durchgeführt werden, in denen die diskrete log-Funktion schwierig zu berechnen ist, wie zum Beispiel bestimmte Gruppen elliptischer Kurven. Gruppen sind in der Technik wohlbekannt, siehe z. B. I. N. Herstein, Topics in Algebra, 2. Auflage, John Wiley & Sons, New York, 1975, und zwar folgendermaßen. Eine nichtleere Menge von Elementen G wird als eine Gruppe bildend bezeichnet, wenn in G eine binäre Operation definiert ist, die als Produkt bezeichnet und als · geschrieben wird, so daß folgendes gilt:

1. aus a, b ∈ G folgt a·b ∈ G (geschlossen).
2. aus a, b, c ∈ G folgt a·(b·c) = (a·b)·c (Assoziativgesetz).
3. Es gibt ein Element e ∈ G, so dass für alle a ∈ G a·e = e·a = a (Existenz eines Identitätselements in G).
4. Für jedes a ∈ G existiert ein Element a^–1 ∈ G mit a·a^–1 = a^–1·a = e (Existenz von Inversen in G).

Allgemeiner arbeitet der Diffie-Hellman-Schlüsselaustausch also in einer spezifischen Gruppe, wobei die Geheimschlüssel x und y Indizes auf Elemente der Gruppe sind. Man betrachte also eine Gruppe G mit einem Gruppengenerator g ∈ G und G = {g, g·g, g·g·g, g·g·g·g, ...}, wobei · die Gruppenoperation ist. Wenn zum Beispiel die Gruppenoperation für G Multiplikation ist, dann ist G = {g¹, g², g³, g⁴, ...}. Wenn die Gruppenoperation · für G Addition ist, dann ist G = {1g, 2g, 3g, 4g, ...}. Da die vorliegende Erfindung mit verschiedenen Gruppen implementiert werden kann, bedeutet die Notation g^x im folgenden, dass die Gruppenoperation x mal an dem Gruppengenerator g angewandt wird. Außerdem gibt es für jede Gruppe auch eine inverse Gruppenoperation, die hier als – dargestellt wird.
Im Nachfolgenden wird die inverse Gruppenoperation folgendermaßen definiert. Die inverse Gruppenoperation an x und y, d. h.
ist als x·y^–1 definiert.
2 zeigt ein Protokoll für gegenseitige Authentisierung und Schlüsselaustausch gemäß einem expliziten Authentisierungsansatz, bei dem beide Parteien ein gemeinsam benutztes Passwort besitzen. Das Kommunikationsprotokoll in 2 ist aus der oben zitierten EP-A-1134929 bekannt.
Im allgemeinen verwendet das Kommunikationsprotokoll ein gemeinsames Geheimnis des Diffie-Hellman-Typs, das aber so modifiziert ist, dass sich die beiden Parteien unter Verwendung eines gemeinsam benutzten Passworts gegenseitig authentisieren können. Ferner hat sich erwiesen, dass dieses Protokoll sicher ist.
Gemäß 2 werden auf der linken Seite der Figur gezeigte Schritte durch eine erste Partei A durchgeführt, und auf der rechten Seite der Figur werden durch eine zweite Partei B durchgeführt. A ist in der Regel eine Client-Maschine (Computersystem) und B ist eine Server-Maschine (Computersystem). Dies ist jedoch nicht erforderlich, und A und B werden nur als Beispiel als Client bzw. Server bezeichnet, um den typischen Fall zu zeigen. Es versteht sich also, dass der in 2 gezeigte Ansatz nicht auf den Fall begrenzt ist, dass A und B Client und Server sind, sondern stattdessen auf beliebige zwei Parteien A und B anwendbar ist. Pfeile repräsentieren Kommunikation zwischen den Parteien. Gemäß dem Protokoll authentisiert sich der Server selbst dem Client gegenüber und der Client authentisiert sich selbst dem Server gegenüber. Nachdem sich beide Seiten authentisiert haben, erzeugt jede einen geheimen Sitzungsschlüssel, der für die nachfolgende sichere Kommunikation verwendet werden kann.
Es wird angenommen, dass der Client und der Server vor der Einleitung des Protokolls ein Passport π besitzen, mit dem der Client sich bei dem Server authentisiert.
Es wird angemerkt, dass das folgende Protokoll sowohl den Server als auch den Client authentisiert. Weder der Server noch der Client werden also als authentisch angenommen und somit kann entweder der Server oder der Client ein Gegenspieler sein. Der Client kann ein Gegenspieler sein, der versucht, sich selbst zu authentisieren, um Zugang zu dem Server zu erhalten. Der Server kann ein Gegenspieler sein, der versucht, sich für einen anderen authentischen Server auszugeben, um zu versuchen, heikle Informationen von einem nichtsahnenden Client zu erhalten.
Wieder mit Bezug auf 2 wählt der Client im Schritt 202 einen Zufallswert für den Index x aus Z_q. Im Schritt 204 berechnet der Client dann einen Parameter m als m = g^x·(H₁(A, B, π))^r mod p, wobei A eine eindeutige Kennung des Clients, B eine eindeutige Kennung des Servers, π das Passwort des Clients für diesen bestimmten Server, H₁ eine Zufalls-Hash-Funktion ist und die Gruppenoperation repräsentiert. H₁(A, B, π) wird zur r-ten Potenz erhoben, um sicherzustellen, dass das Ergebnis in G_(pq) liegt. Informell wird eine Funktion H von einer Menge S in eine Menge T als Zufalls-Hash-Funktion bezeichnet, wenn die Ausgabe von H zufällig aussieht oder zumindest unvorhersehbar ist, bis die Funktion mit einer Eingabe x in S berechnet wird. Da H₁ etwas ausgeben muss, das zufällig in Z * / p aussieht, sollte es |p| + sec in Bit ausgeben (wobei |p| die Anzahl von Bit von p und sec der Sicherheitsparameter ist. Der Sicherheitsparameter kann zum Beispiel 160 betragen. Bekannte Funktionen, die sich allgemein auf diese Weise verhalten, sind SHA-1, beschrieben in FIPS 180-1, Secure Hash Standard, Federal Information Processing Standards Publication 180-1, 1995; und RIPMED-160, beschrieben in H. Dobbertin, A. Bosselaers, B. Preneel, „RIPEMD-160: In a strengthened version of RIPEMD, Fast Software Encryption, 3. Intl. Workshop, 71–82, 1996.
Das Tupel (A, B, π) wird anstelle nur des Passworts verwendet, um sicherzustellen, dass es für jedes Client-Server-Paar einzigartig ist. Für heuristische Sicherheit ist nur das Passwort alleine erforderlich, wie später ausführlicher besprochen wird, werden die Namen von Client und Server jedoch verwendet, um einen formalen Sicherheitsbeweis sicherzustellen. Gemäß dem Protokoll in 2 wird also eine Funktion mindestens des Passworts mit dem Diffie-Hellman-Wert g^x kombiniert, indem die Gruppenoperation an der Funktion mindestens des Passworts und dem Diffie-Hellman-Wert g^x ausgeführt wird. Dies ist ein wichtiger Schritt des Protokolls, da er sicherstellt, dass der Diffie-Hellman-Wert g^x nur von einer Person, die das Passwort kennt, von dem Parameter m extrahiert werden kann. Diese Extraktion des Diffie-Hellman-Werts g^x wird nachfolgend ausführlicher in Verbindung mit Schritt 214 beschrieben. Im Schritt 206 sendet der Client den Parameter m zum Server.
Nach dem Empfang des Parameters m prüft der Server im Schritt 208 den Parameterwert, um sicherzustellen, dass der Wert nicht 0 mod p ist. Wenn der Wert 0 mod p ist, beendet der Server das Protokoll, weil 0 nicht in Z * / p liegt. Andernfalls wählt der Server im Schritt 210 einen Zufallswert für den Index y aus Z_q. Im Schritt 212 weist der Server dem berechneten Diffie-Hellman-Wert g^y einen Parameter μ zu. Als nächstes berechnet der Server im Schritt 214 das gemeinsame Geheimnis g^xy gemäß Diffie-Hellman (das in diesem Protokoll als σ bezeichnet wird), unter Verwendung des empfangenen Parameters m, wie folgt:
mod p. Dieser Schritt wird nun ausführlicher beschrieben (wobei der Einfachheit halber die Notation mod p weggelassen wird). Als erstes sollte man sich erinnern, dass wie oben beschrieben für jede Gruppenoperation eine inverse Gruppenoperation existiert, so dass die inverse Gruppenoperation an x und y, d. h.
als x·y^–1 definiert ist. Für Fachleute ist also erkennbar, dass die Berechnung von
im Schritt 214 die inverse Gruppenoperation an m und der Funktion mindestens des Passworts durchführt. Durch Ersetzen des Werts von m aus Schritt 204 erhält man
. Wenn der Server das korrekte Passwort π besitzt, kann der Server dann also den Diffie-Hellman-Wert g^x aus dem Wert des empfangenen Parameters m extrahieren. Die Berechnung im Schritt 214 führt also dazu, dass der Server das gemeinsame Geheimnis g^xy gemäß Diffie-Hellman erzeugt.
Als nächstes berechnet der Server im Schritt 216 k = H_2a(A, B, m, μ, σ, π), wobei H_2a eine weitere Zufalls-Hash-Funktion ist, die sec Bit ausgeben muss, wobei sec der Sicherheitsparameter ist. Wie unten beschrieben, authentisiert der Client A mit dem Parameter k, dass der Server das korrekt Passwort besitzt. Im Schritt 218 sendet der Server die Parameter μ und k zu dem Client.
Nach dem Empfang der Parameter μ und k berechnet der Client σ = μ^x mod p im Schritt 220. Wegen μ = g^y gilt μ^x = g^xy, wobei es sich um das gemeinsame Geheimnis nach Diffie-Hellman handelt. Im Schritt 222 berechnet der Client H_2a (A, B, m, μ, σ, π) unter Verwendung seiner Kenntnis von π und prüft, ob das Ergebnis gleich dem im Schritt 218 von dem Server empfangenen Parameter k ist. Wenn sie übereinstimmen, hat der Client den Server authentisiert. Wenn sie nicht übereinstimmen, beendet der Client das Protokoll, da der Server sich nicht authentisiert hat. Im Schritt 224 berechnet der Client k' = H_2b(A, B, m, μ, σ, π), und der Server authentisiert damit den Client wie nachfolgend beschrieben. Im Schritt 226 erzeugt der Client den Sitzungsschlüssel K als K = H₃(A, B, m, μ, σ, π). Im Schritt 228 sendet Client k' zum Server. Wiederum sind H_2b und H₃ Zufalls-Hash-Funktionen, die sec Bit ausgeben müssen, wobei sec der Sicherheitsparameter ist.
Im Schritt 230 berechnet der Server H_2b(A, B, m, μ, σ, π) unter Verwendung seiner Kenntnis von π und prüft, ob das Ergebnis gleich dem im Schritt 228 von dem Client empfangenen Parameter k' ist. Wenn sie übereinstimmen, hat der Server den Client authentisiert. Wenn sie nicht übereinstimmen, beendet der Server das Protokoll, da sich der Client nicht authentisiert hat. Im Schritt 232 erzeugt der Server den Sitzungsschlüssel K als K = H₃(A, B, m, μ, σ, π).
An diesem Punkt haben sich sowohl der Client als auch der Server gegenseitig authentisiert und sowohl der Client als auch der Server haben denselben sicheren Sitzungsschlüssel K erzeugt, der für die nachfolgende sichere Kommunikation zwischen Client und Server verwendet werden kann.
Obwohl das Kommunikationsprotokoll von 2 die Vorteile eines Schlüsselaustausches mit Authentisierung mit Passwortbasis liefert, kann die Erzeugung des Parameters m als g^y·(H₁(A, B, μ))^r mod p rechnerisch intensiv sein. Dies kann problematisch sein, wenn die Client-Einrichtung nicht die rechnerischen Betriebsmittel zur adäquaten Durchführung dieses Teils des Protokolls besitzt. Dies kann der Fall sein, wenn der Client A eine kleinere, langsamere Einrichtung ist, wie zum Beispiel ein PC älterer Generation, oder eine Chipkarte oder ein tragbarer persönlicher digitaler Assistent (PDA), um nur einige wenige Beispiele zu nennen. Obwohl B ein Server sein kann und angenommen wird, dass er rechnerisch besser ausgestattet als der Client ist, kann das Protokoll zusätzlich auch zwischen zwei Einrichtungen des Client-Typs durchgeführt werden, und deshalb ist rechnerische Effizienz auf beiden Seiten des Protokolls wichtig. Eine Lösung, die die Berechnung auf der Clientseite um mindestens einen Faktor 2 reduzieren kann, wird gemäß der vorliegenden Erfindung bereitgestellt und im Kontext von 3 dargestellt.
Nunmehr mit Bezug auf 3 wird gemäß einer Ausführungsform der vorliegenden Erfindung, bei der beide Parteien ein gemeinsam benutztes Passwort besitzen, ein Protokoll für gegenseitige Authentisierung und Schlüsselaustausch mit verbesserter Effizienz bereitgestellt. Das Kommunikationsprotokoll ist ein sicheres durch Passwort authentisiertes Schlüsselaustauschprotokoll und nimmt die Härte des Entscheidungs-Diffie-Hellman-Problems (DDH) in G_p,q an. Es sei DH(X, Y) der Diffie-Hellman-Wert g^xy von X = g^x und Y = g^y wie oben beschrieben. Eine Formulierung besteht darin, dass bei gegebenem g, X, Y, Z in G_p,q, wobei X = g^x und Y = g^y zufällig gewählt werden und Z entweder DH(X, Y) oder zufällig ist, jeweils mit Halbwahrscheinlichkeit, zu bestimmen, ob Z = DH(X, Y) ist. Das Brechen des DDH impliziert die Konstruktion eines Gegenspielers polynomischer Zeit, der mit nichtvernachlässigbarem Vorteil gegenüber einem zufälligen Raten Z = DH(X, Y) von einem Zufalls-Z unterscheidet.
Ferner definiert man Hash-Funktionen H_2a, H_2b, H₃: {0,1}* → {0,1}^k < und H₁: {0,1}^* → {0,1}ⁿ > mit η ≥ l + κ. Außerdem nimmt man an, dass H₁, H_2a, H_2b und H₃ unabhängige Zufallsfunktionen sind, so wie es oben bei dem Ansatz von 2 verwendet wurde. Man beachte, dass zwar H₁ als eine Bitkette zurückgebend beschrieben wird, an seiner Ausgabe jedoch als eine Zahl modulo p gearbeitet wird.
Gemäß dem Kommunikationsprotokoll von 2 beachte man, dass der Client zwei |q|-Bit-Exponentiierungen durchführt (Schritte 204 und 220), sowie eine |r|-Bit-Exponentiierung (Schritt 204). Wie später im Kontext von 3 erläutert werden wird, muss gemäß einem Kommunikationsprotokoll der vorliegenden Erfindung der Client nur drei |q|-Bit-Exponentiierungen durchführen, was im allgemeinen im Vergleich mit dem Protokoll von 2 viel weniger Berechnungen erfordert. Die Erfindung kann auf die folgende Weise einen solchen Vorteil bereitstellen. Statt zu erzwingen, dass das Ergebnis der Hash-Funktion, mit der der Parameter m erzeugt wird, in der Gruppe G_p,q liegt, lässt man als das Ergebnis der Hash-Funktion ein beliebiges Element in Z * / p zu und randomisiert diesen Teil des Ergebnisses der Hash-Funktion außerhalb von G_p,q. Dadurch wird der m-Wert von einem Zufallswert in Z * / p (anstelle eines Zufallswerts in G_p,q) ununterscheidbar, es ist aber immer noch möglich, den Hash-Wert und die zusätzliche Randomisierung zu extrahieren.
In diesem Fall gilt p = rq + 1 mit gcd (r, q) = 1 (wobei gcd für den größten gemeinsamen Teiler steht), um die zusätzliche Randomisierung zu extrahieren. Für zufällig gewähltes q und p (zum Beispiel unter Verwendung des von NIST genehmigten Algorithmus, der in U.S. Department of Commerce/NIST, Springfield, VA, FIPS186, „Digital Signature Standard", Federal Information Processing Standards Publication 186, 1994 beschrieben wird) kann diese Beziehung natürlich mit großer Wahrscheinlichkeit erfüllt werden.
Wie in 2 werden auf der linken Seite von 3 gezeigte Schritte von einer ersten Partei A und auf der rechten Seite von 3 gezeigte Schritte von einer zweiten Partei B durchgeführt. Wiederum wird lediglich als Beispiel, um eine typischen Fall zu zeigen, A als eine Client-Maschine (Computersystem) und B als eine Server-Maschine (Computersystem) bezeichnet. Es versteht sich also, dass das in 3 gezeigte Protokoll auf zwei beliebige Entitäten oder Parteien A und B anwendbar ist. Wiederum repräsentieren Pfeile Kommunikation zwischen den Parteien. Gemäß dem Protokoll von 3 authentisiert sich der Server selbst dem Client gegenüber und der Client authentisiert sich selbst dem Server gegenüber. Weder der Server noch der Client werden also als authentisch angenommen, und somit kann entweder der Server oder der Client ein Gegenspieler sein, wie oben erläutert. Nachdem sich beide Seiten authentisiert haben, erzeugt jede einen geheimen Sitzungsschlüssel, der für nachfolgende sichere Kommunikation verwendet werden kann.
Wie bei dem Protokoll von 2 wird angenommen, dass der Client und der Server vor der Einleitung des Protokolls von 3 der Erfindung ein Passwort π besitzen, mit dem sich der Client dem Server gegenüber authentisiert.
Wieder mit Bezug auf 3 wählt der Client im Schritt 302 einen Zufallswert für den Index x aus Z_q (d. h. x ∈_k Z_q). Im Schritt 304 wählt der Client einen Zufallswert h aus der Gruppe Z * / p (d. h. h ∈_k Z * / p). Im Schritt 306 berechnet der Client dann einen Parameter m als m = g^x·h^q·H₁(A, B, π). Dabei ist A eine eindeutige Kennung des Client, B eine eindeutige Kennung des Servers, π das Passwort des Client für diesen bestimmten Server, H₁ eine Zufalls-Hash-Funktion, · stellt die Gruppenoperation dar und h^q ist eine Randomisierungsoperation. Man beachte, dass in dem Protokoll von 2 H₁(A, B, π) zur r-ten Potenz erhoben wird, um sicherzustellen, dass das Ergebnis in G_p,q liegt. Statt zu erzwingen, dass das Ergebnis der Hash-Funktion, mit der der Parameter m erzeugt wird, in der Gruppe G_p,q liegt, ermöglicht das Protokoll von 3 gemäß der vorliegenden Erfindung jedoch, dass das Ergebnis der Hash-Funktion ein beliebiges Element in Z * / p ist, und randomisiert den Teil des Ergebnisses der Hash-Funktion außerhalb von G_p,q. Man erreicht dies über die Randomisierungsoperation h^q. Dadurch wird der m-Wert von einem Zufallswert in Z * / p, anstelle eines Zufallswerts in G_p,q, ununterscheidbar, aber der Server B kann immer noch den Hash-Wert und die zusätzliche Randomisierung extrahieren. Durch Erheben des Zufallsparameters h zu dem Exponenten q wird vorteilhafterweise alles in dem Ergebnis der Hash-Funktion außerhalb der Untergruppe G_p,q randomisiert.
Wie oben erläutert bezeichnet man eine Funktion H von einer Menge S in eine Menge T als Zufalls-Hash-Funktion, wenn die Ausgabe von H zufällig aussieht oder zumindest unvorhersehbar ist, bis die Funktion mit einer Eingabe x in S berechnet wird. Da H₁ etwas ausgeben muss, das zufällig in Z * / p aussieht, sollte es daher |p| + sec Bit ausgeben (wobei |p| die Anzahl von Bit von p und sec der Sicherheitsparameter ist. Der Sicherheitsparameter kann zum Beispiel 160 betragen. Wiederum sind SHA-1 oder RIPEMD-160 bekannte Funktionen, die sich auf diese Weise verhalten.
Wie bei dem Protokoll von 2 wird das Tupel (A, B, π) verwendet (anstelle nur des Passworts), um sicherzustellen, dass es für jedes Client-Server-Paar einzigartig ist. Für heuristische Sicherheit ist nur das Passwort alleine erforderlich, aber man kann Namen von Client und Server verwenden, um einen formalen Beweis der Sicherheit sicherzustellen. Gemäß dem Protokoll in 3 wird also eine Funktion mindestens des Passworts mit dem Diffie-Hellman-Wert g^x kombiniert, indem die Gruppenoperation an der Funktion mindestens des Passworts und dem Diffie-Hellman-Wert g^x ausgeführt wird. Wieder ist dies ein wichtiger Schritt des Protokolls, da er sicherstellt, dass der Diffie-Hellman-Wert g^x nur von einer Person, die das Passwort kennt, aus dem Parameter m extrahiert werden kann. Im Schritt 308 sendet der Client den Parameter m zu dem Server.
Nach dem Empfang des Parameters m prüft der Server im Schritt 310 den Parameterwert, um sicherzustellen, dass der Wert nicht 0 modp ist. Wenn der Wert 0 mod p ist, beendet der Server das Protokoll, da 0 nicht in Z * / p liegt. Andernfalls wählt der Server im Schritt 312 einen Zufallswert für den Index y aus Z_q. Im Schritt 314 weist der Server dem berechneten Diffie-Hellman-Wert g^y einen Parameter μ zu. Als nächstes berechnet der Server im Schritt 316 das gemeinsame Geheimnis g^xy nach Diffie-Hellman (das in diesem Protokoll als σ bezeichnet wird) unter Verwendung des empfangenen Parameters m, wie folgt:
. Dieser Schritt wird nun ausführlicher beschrieben. Als erstes erinnere man sich, dass es, wie oben beschrieben, für jede Gruppenoperation eine inverse Gruppenoperation gibt, dergestalt, dass die inverse Gruppenoperation an x und y, d. h. x/y, als x·y^–1 definiert ist. Für Fachleute ist also erkennbar, dass die Berechnung von
im Schritt 316 die inverse Gruppenoperation an m und der Funktion mindestens des Passworts ausführt, sowie die mit der Client-Zufallsoperation h^q assoziierte Randomisierung extrahiert. Durch Ersetzen des Werts von m aus Schritt 306 erhält man g^x. Wenn der Server das korrekte Passwort π besitzt, kann der Server dann also den Diffie-Hellman-Wert g^x aus dem Wert des empfangenen Parameters m extrahieren. Die Berechnung im Schritt 316 führt also dazu, dass der Server das gemeinsame Geheimnis g^xy nach Diffie-Hellman erzeugt.
Als nächstes berechnet der Server im Schritt 318 k = H_2a(A, B, m, μ, σ, π), wobei H_2a eine weitere Zufalls-Hash-Funktion ist, die sec-Bit ausgeben muss, wobei sec der Sicherheitsparameter ist. Mit dem Parameter k authentisiert der Client A wie nachfolgend beschrieben, dass der Server das korrekte Passwort besitzt. Im Schritt 320 sendet der Server die Parameter μ und k zu dem Client.
Nach dem Empfang der Parameter μ und k berechnet der Client im Schritt 322 σ = μ^x mod p. Wegen μ = g^y gilt μ^x = g^xy, wobei es sich um das gemeinsame Geheimnis nach Diffie-Hellman handelt. Im Schritt 324 berechnet der Client H_2a(A, B, m, μ, σ, π) unter Verwendung seiner eigenen Kenntnis von π und prüft, ob das Ergebnis gleich dem im Schritt 320 von dem Server empfangenen Parameter k ist. Wenn sie übereinstimmen, hat der Client den Server authentisiert. Wenn sie nicht übereinstimmen, beendet der Client das Protokoll, da sich der Server nicht authentisiert hat. Im Schritt 326 berechnet der Client k' = H_2b(A, B, m, μ, σ, π), womit der Server den Client wie nachfolgend beschrieben authentisiert. Im Schritt 328 erzeugt der Client den Sitzungsschlüssel K als K = H₃(A, B, m, μ, σ, π). Im Schritt 330 sendet der Client k' zu dem Server. Wiederum sind H_2b und H₃ Zufalls-Hash-Funktionen, die sec Bit ausgeben müssen, wobei sec der Sicherheitsparameter ist.
Im Schritt 332 berechnet der Server H_2b (A, B, m, μ, σ, π) unter Verwendung seiner eigenen Kenntnis von π und prüft, ob das Ergebnis gleich dem im Schritt 330 von dem Client empfangenen Parameter k' ist. Wenn sie übereinstimmen, hat der Server den Client authentisiert. Wenn sie nicht übereinstimmen, beendet der Server das Protokoll, da sich der Client nicht authentisiert hat. Im Schritt 334 erzeugt der Server den Sitzungsschlüssel K als K = H₃(A, B, m, μ, σ, π).
An diesem Punkt haben sich der Client als auch der Server gegenseitig authentisiert und sowohl der Client als auch der Server haben denselben sicheren Sitzungsschlüssel K erzeugt, der für nachfolgende sichere Kommunikation zwischen dem Client und dem Server verwendet werden kann.
Wie bereits erwähnt, verringert das Kommunikationsprotokoll der Erfindung, so wie es im Kontext von 3 dargestellt wird, die Berechnungen auf der Clientseite um mindestens einen Faktor 2 im Vergleich zu dem Protokoll von 2. Dies wird aus dem folgenden Beispiel ersichtlich. Man nehme an, dass p eine 1024-Bit-Primzahl und q eine 160-Bit-Primzahl ist. Dann beträgt r 864 Bit. Jede Exponentiierung in Z * / p nimmt proportional zu der Anzahl von Bit des Exponenten Zeit in Anspruch. In dem Protokoll von 2 ist dann, wenn zwei q-Bit-Exponentiierungen und eine r-Bit-Exponentiierung durchgeführt werden, die Zeit proportional zu 2*160 + 864 = 1184, während in dem Protokoll der Erfindung (siehe 3), wenn drei q-Bit-Exponentiierungen durchgeführt werden, die Zeit proportional zu 3*160 = 480 ist. Vorteilhafterweise beträgt dieser Wert (480) weniger als die Hälfte des Werts, der dem Protokoll von 2 zugeordnet ist (1184).
4 zeigt die verallgemeinerte Hardwarearchitektur eines Datennetzwerks und von Computersystemen, die sich zur Implementierung einer passwortauthentisierten Schlüsselaustauschmethodologie zwischen zwei Entitäten A und B gemäß der vorliegenden Erfindung eignen. Wie gezeigt, umfasst die Entität A ein Computersystem 402, während die Entität B ein Computersystem 404 umfasst. Die beiden Computersysteme 402 und 404 werden über ein Datennetzwerk 404 gekoppelt. Das Datennetzwerk kann ein beliebiges Datennetzwerk sein, über das A und B kommunizieren möchten, z. B. das Internet. Die Erfindung ist jedoch nicht auf eine bestimmte Art von Netzwerk beschränkt. Wie in 4 bezeichnet, ist A in der Regel eine Client-Maschine und B eine Server-Maschine. Dies ist jedoch nicht erforderlich, und A und B werden lediglich als ein Beispiel als Client bzw. Server bezeichnet, um den typischen Fall zu zeigen. Es versteht sich somit, dass das Kommunikationsprotokoll der vorliegenden Erfindung nicht auf den Fall beschränkt ist, dass A und B Client und Server sind, sondern stattdessen auf beliebige Datenverarbeitungseinrichtungen, die A und B umfassen, anwendbar ist.
Für Durchschnittsfachleute ist ohne weiteres erkennbar, dass der Server und der Client als programmierte Computer implementiert werden können, die unter der Kontrolle von Computerprogrammcode wirken. Der Computerprogrammcode wäre in einem computerlesbaren Medium (z. B. einem Speicher) gespeichert und der Code würde durch einen Prozessor des Computers ausgeführt. Anhand der Offenlegung der Erfindung könnten Fachleute ohne weiteres entsprechenden Computerprogrammcode erzeugen, um die hier beschriebenen Protokolle zu implementieren.
Trotzdem zeigt 4 allgemein eine beispielhafte Architektur für jedes über das Netzwerk kommunizierende Computersystem. Wie gezeigt, umfasst die Client-Einrichtung E/A-Einrichtungen 408-A, einen Prozessor 410-A und Speicher 412-A. Das Server-System umfasst E/A-Einrichtungen 408-B, einen Prozessor 410-B und Speicher 412-B. Es versteht sich, dass der hier benutzte Begriff „Prozessor" eine oder mehrere Verarbeitungseinrichtungen umfassen soll, darunter eine zentrale Verarbeitungseinrichtung (CPU) oder andere Verarbeitungsschaltkreise. Außerdem soll der Begriff „Speicher" hier einen Speicher umfassen, der einem Prozessor oder einer CPU zugeordnet ist, wie zum Beispiel RAM, ROM, eine Festspeichereinrichtung (z. B. Festplatte) oder eine wechselbare Speichereinrichtung (z. B. eine Diskette oder CDROM). Außerdem soll der Begriff „E/A-Einrichtungen" hier eine oder mehrere Eingabeeinrichtungen (z. B. Tastatur, Maus) zum Eingeben von Daten in die Verarbeitungseinheit, sowie eine oder mehrere Ausgabeeinrichtungen (z. B. CRT-Anzeige) zur Bereitstellung von der Verarbeitungseinheit zugeordneten Ergebnissen umfassen. Softwareanweisungen oder Code zur Durchführung der hier beschriebenen Methodologien der Erfindung können folglich in einer oder mehreren der zugeordneten Speichereinrichtungen z. B. in ROM, festem oder wechselbarem Speicher, gespeichert werden und können, wenn sie für die Verwendung bereit sind, in RAM geladen und durch die CPU ausgeführt werden.
Obwohl hier mit Bezug auf die beigefügten Zeichnungen beispielhafte Ausführungsformen der vorliegenden Erfindung beschrieben wurden, versteht sich, dass die Erfindung nicht auf diese genauen Ausführungsformen beschränkt ist und dass Fachleute verschiedene andere Änderungen und Modifikationen vornehmen können, ohne von dem durch die Ansprüche definierten Schutzumfang der Erfindung abzuweichen. Obwohl die Lehren der Erfindung im Kontext eines Kommunikationsprotokolls, das gegenüber dem oben in 2 beschriebenen Kommunikationsprotokoll rechnerische Effizienzen liefert, dargestellt wurden, versteht sich zum Beispiel, dass die Erfindung im Kontext anderer Kommunikationsprotokolle angewandt werden kann. Zum Beispiel kann die Randomisierungsoperation der Erfindung gemäß anderen Protokollausführungsformen verwendet werden, die in der oben zitierten EP-A-1 134 929 beschrieben werden.
Zum Beispiel kann die Erfindung gemäß dem impliziten Authentisierungsansatz der oben zitierten Anmeldung verwendet werden, und auch mit dem hier beschriebenen Passwortverifiziereransatz. Obwohl bestimmte Parameter bei der Auswertung der Hash-Funktionen des Kommunikationsprotokolls der Erfindung verwendet werden, versteht sich ferner, dass für heuristische Sicherheit nicht alle Parameter erforderlich sind. Das heißt, es werden zusätzliche Parameter verwendet, um einen formalen Beweis der Sicherheit des Protokolls zu ermöglichen. Zum Beispiel kann in den in den Schritten 318, 324, 326, 328, 332 und 334 verwendeten Hash-Funktionen nur der Parameter σ in der Funktion notwendig sein, damit das Protokoll heuristisch sicher wird.

Claims

Verfahren zur Kommunikation zwischen zwei Parteien, die ein gemeinsames Passwort besitzen, über ein Datennetzwerk unter Verwendung eines Diffie-Hellman-Schlüsselaustausches in Bezug auf eine bestimmte Gruppe zur Erzeugung eines gemeinsamen Geheimnisses g^xy, wobei g der beiden Parteien bekannte Gruppengenerator ist, x ein der einen Partei bekannter Index und y ein der anderen Partei bekannter Index ist, wobei die Gruppe eine Gruppenoperation und eine inverse Gruppenoperation aufweist und das Verfahren folgende Schritte umfasst: das Erzeugen eines Parameters m (306) mittels Ausführung der Gruppenoperation an g^x und einer Funktion von mindestens dem Passwort und Übertragen von m (308) an die andere Partei durch eine Partei, wodurch es der anderen Partei ermöglicht wird, die umgekehrte Gruppenoperation an m und die Funktion von mindestens dem Passwort auszuführen, um g^x zu extrahieren und das gemeinsame Geheimnis g^xy zu berechnen (316); dadurch gekennzeichnet, dass die Erzeugung von m das Randomisieren jedes Teils eines mit der Funktion assoziierten Ergebnisses umfasst, der außerhalb der Gruppe liegt, wobei der anderen Partei ermöglicht wird, die Randomisierung zu entfernen.
Verfahren nach Anspruch 1, wobei die bestimmte Gruppe, die als G_p,q bezeichnet ist, eine Untergruppe einer Gruppe Z * / p ist, wobei p und q Primzahlen sind, so dass p gleich rq + 1 für einen Wert r ist, der relativ prim im Verhältnis zu q ist, und wobei der Schritt des Randomisierens jedes Abschnitts eines mit der Funktion assoziierten Ergebnisses, der außerhalb der Gruppe G_p,q liegt, durch Berechnen eines Parameters h, der zufällig aus der Gruppe Z * / p ausgewählt wird, Erhöhen des Parameters h auf den Exponenten q und Multiplizieren von h mit dem mit der Funktion (306) assoziierten Ergebnis ausgeführt wird.
Verfahren nach Anspruch 1, wobei die eine Partei ein Client (402) und die andere Partei ein Server (404) ist.
Verfahren nach Anspruch 1, das des Weiteren folgenden Schritt umfasst: Empfanger von g^y von der einen Partei durch die andere Partei und Erzeugen des gemeinsamen Geheimnisses g^xy(322).
Verfahren nach Anspruch 4, das des Weiteren folgenden Schritt umfasst: Authentisieren der anderen Partei durch die eine Partei mittels Vergleich eines empfangenen Werts mit einer Funktion von mindestens entweder einer Kennung der einen Partei, einer Kennung der anderen Partei, m, g^y, dem gemeinsamen Geheimnis oder dem Passwort (324).
Verfahren nach Anspruch 4, das des Weiteren folgenden Schritt umfasst: Übertragen (330) einer Funktion von mindestens entweder einer Kennung der einen Partei, einer Kennung der anderen Partei, m, g^y, dem gemeinsamen Geheimnis oder dem Passwort durch die eine Partei an die andere Partei, wodurch die andere Partei die eine Partei authentisieren kann.
Verfahren nach Anspruch 4, das des Weiteren folgenden Schritt umfasst: Erzeugen eines Sitzungsschlüssels als Funktion von mindestens entweder einer Kennung der einen Partei, eine Kennung der anderen Partei, m, g^y, dem gemeinsamen Geheimnis oder dem Passwort (328) durch die eine Partei.
Verfahren zur Kommunikation zwischen zwei Parteien, die ein gemeinsames Passwort besitzen, über ein Datennetzwerk unter Verwendung eines Diffie-Hellman-Schlüsselaustausches in Bezug auf eine bestimmte Gruppe zur Erzeugung eines gemeinsamen Geheimnisses g^xy, wobei g der beiden Parteien bekannte Gruppengenerator ist, x ein der einen Partei bekannter Index und y ein der anderen Partei bekannter Index ist, die Gruppe eine Gruppenoperation und eine inverse Gruppenoperation aufweist und das Verfahren folgende Schritte umfasst: Ausführen der inversen Gruppenoperation an m und der Funktion von mindestens dem Passwort, Extrahieren von g^x und Berechnen des gemeinsamen Geheimnisses g^xy durch die andere Partei also Reaktion auf das Erzeugen eines Parameters m (306) durch die eine Partei mittels Ausführung der Gruppenoperation an g^x und einer Funktion von mindestens dem Passwort und übertragen von m (308) an die andere Partei; dadurch gekennzeichnet, dass das Ausführen der inversen Gruppenoperation an m und der Funktion von mindestens dem Passwort das Entfernen der Randomisierung jedes Teils des mit der Funktion assoziierten Ergebnisses umfasst, der sich außerhalb der Gruppe befindet, wobei die Randomisierung bei der Erzeugung von m ausgeführt wurde.
Vorrichtung zur Verwendung gemäß einem Protokoll zur Kommunikation zwischen zwei Parteien, die ein gemeinsames Passwort besitzen, über ein Datennetzwerk unter Verwendung eines Diffie-Hellman-Schlüsselaustausches in Bezug auf eine bestimmte Gruppe zur Erzeugung eines gemeinsamen Geheimnisses g^xy, wobei g der beiden Parteien bekannte Gruppengenerator ist, x ein der einen Partei bekannter Index und y ein der anderen Partei bekannter Index ist, die Gruppe eine Gruppenoperation und eine inverse Gruppenoperation aufweist und die Vorrichtung zum Gebrauch durch die eine Partei bestimmt ist und Folgendes umfasst: mindestens einen Prozessor, der betriebsbereit ist: (i) zur Erzeugung eines Parameters m (306) durch Ausführen der Gruppenoperation an g^x und einer Funktion von mindestens dem Passwort und (ii) zur Übertragung von m (308) an die andere Partei, wodurch es der anderen Partei ermöglicht wird, die inverse Gruppenoperation an m und die Funktion von mindestens dem Passwort auszuführen, um g^x zu extrahieren und das gemeinsame Geheimnis g^xy zu berechnen (316); dadurch gekennzeichnet, dass: der mindestens eine Prozessor so konfiguriert ist, dass das Erzeugen von m das Randomisieren jedes Teils eines mit der Funktion assoziierten Ergebnisses umfasst, der außerhalb der Gruppe liegt, wobei es der anderen Partei ermöglicht wird, die Randomisierung zu entfernen.
Vorrichtung zur Verwendung gemäß einem Protokoll zur Kommunikation zwischen zwei Parteien, die ein gemeinsames Passwort besitzen, über ein Datennetzwerk unter Verwendung eines Diffie-Hellman-Schlüsselaustausches in Bezug auf eine bestimmte Gruppe zur Erzeugung eines gemeinsamen Geheimnisses g^xy, wobei g der beiden Parteien bekannte Gruppengenerator ist, x ein der einen Partei bekannter Index und y ein der anderen Partei bekannter Index ist, die Gruppe eine Gruppenoperation und eine inverse Gruppenoperation aufweist und die Vorrichtung zum Gebrauch durch die andere Partei bestimmt ist und Folgendes umfasst: mindestens einen Prozessor, der als Reaktion auf das Erzeugen eines Parameters in (306) durch Ausführen der Gruppenoperation an g^x und einer Funktion von mindestens dem Passwort durch die eine Partei für die andere Partei betriebsbereit ist und m (305) an die andere Partei überträgt: Ausführen des umgekehrten Gruppenbetriebs an m und der Funktion von mindestens dem Passwort; Extrahieren von g^x; und Berechnen des gemeinsamen Geheimnisses g^xy (316); dadurch gekennzeichnet, dass: der mindestens eine Prozessor so konfiguriert ist, dass das Ausführen der inversen Gruppenoperation in Bezug auf m und der Funktion von mindestens dem Passwort das Entfernen der Randomisierung jedes Teils des mit der Funktion assoziierten Ergebnisses umfasst, der sich außerhalb der Gruppe befindet, wobei die Randomisierung bei der Erzeugung von m ausgeführt wurde.