Diffie-Hellman-Schlüsselaustausch

aus Wikipedia, der freien Enzyklopädie
(Weitergeleitet von Elliptic Curve Diffie-Hellman)
Wechseln zu: Navigation, Suche

Der Diffie-Hellman-Schlüsselaustausch oder Diffie-Hellman-Merkle-Schlüsselaustausch ist ein Protokoll aus dem Bereich der Kryptografie. Mit ihm erzeugen zwei Kommunikationspartner einen geheimen Schlüssel, den nur diese beiden kennen. Dieser Schlüssel wird üblicherweise verwendet, um verschlüsselte Nachrichten mittels eines symmetrischen Kryptosystems zu übertragen.

Beim Diffie-Hellman-Schlüsselaustausch senden sich beide Kommunikationspartner über einen unsicheren Kanal jeweils eine Nachricht zu. Das Problem, aus diesen beiden Nachrichten den geheimen Schlüssel zu berechnen, wird als Diffie-Hellman-Problem bezeichnet. Von diesem nimmt man an, dass es praktisch nicht lösbar ist. Deshalb kann jemand, der beide Nachrichten mithört, daraus im Allgemeinen nicht den geheimen Schlüssel berechnen. Der Diffie-Hellman-Schlüsselaustausch ist jedoch nicht mehr sicher, wenn sich ein Angreifer zwischen die beiden Kommunikationspartner schalten und Nachrichten verändern kann. Diese Lücke schließen Protokolle wie das Station-to-Station-Protokoll, indem sie zusätzlich digitale Signaturen und Message Authentication Codes verwenden.

Der langen Tradition von Streichlisten und Codebüchern setzte das Diffie-Hellman-Verfahren ein Ende. Noch während des Zweiten Weltkrieges mussten die Benutzer der ausgeklügelten Verschlüsselungsmaschinen (zum Beispiel die Enigma) Codebücher mit sich führen, um für jeden einzelnen Tag des Jahres zu wissen, welchen Schlüssel der Absender verwendet. Wurde ein solches Codebuch geraubt, war die Verschlüsselung hinfällig. Besonders beim Militär war die Zuteilung und der Transport solcher hochgeheimer Codebücher stets das größte Sorgenkind.

Der Diffie-Hellman-Schlüsselaustausch zählt zur Klasse der Schlüsselaustauschprotokolle und bildet die Grundlage des Elgamal-Verschlüsselungsverfahrens.

Die Implementierung mittels elliptischer Kurven ist als Elliptic Curve Diffie-Hellman (ECDH) bekannt.

Geschichte[Bearbeiten]

Der Algorithmus wurde von Martin Hellman gemeinsam mit Whitfield Diffie und Ralph Merkle an der Stanford-Universität (Kalifornien) entwickelt und 1976 veröffentlicht.[1]

Wie erst 1997 bekannt wurde, hatte das britische Government Communications Headquarters (GCHQ) schon in den 1960er Jahren den Auftrag erteilt, zur Vermeidung der hohen Kosten bei der damals üblichen Schlüsselverteilung einen anderen Weg für die Schlüsselverteilung zu finden. Die hierzu von James H. Ellis, Clifford Cocks und Malcolm J. Williamson geäußerten Ideen ähnelten dem Diffie-Hellman-Verfahren. Das GCHQ hat einerseits wegen der Geheimhaltung, andererseits wegen des für die Briten aus Sicht der frühen 1970er Jahre fraglichen Nutzens nie ein Patent beantragt.

Funktionsweise[Bearbeiten]

Prinzip des Diffie-Hellman-Schlüsselaustauschs

Zwei Kommunikationspartner (in der Abbildung sind dies Alice und Bob) wollen über ein unsicheres Medium, etwa eine Kabel- oder Funkverbindung, verschlüsselt kommunizieren. Dazu soll ein symmetrisches Kryptosystem eingesetzt werden, für das beide jedoch zunächst einen gemeinsamen geheimen Schlüssel benötigen. Über den Diffie-Hellman-Schlüsselaustausch gelangen sie beide zu einem solchen Schlüssel.

  1. Die Kommunikationspartner einigen sich zunächst auf eine Primzahl p und eine Primitivwurzel g modulo p mit 2 \le g \le p-2. Diese Parameter brauchen nicht geheim zu bleiben und können daher auch über ein unsicheres Medium übertragen werden.
  2. Beide Kommunikationspartner erzeugen jeweils eine geheimzuhaltende Zufallszahl a bzw. b aus der Menge \{ 1, \ldots, p-2 \}. a und b werden nicht übertragen, bleiben also dem jeweiligen Kommunikationspartner, aber auch potenziellen Lauschern, unbekannt.
  3. Die Kommunikationspartner berechnen A = g^a \bmod p bzw. B = g^b \bmod p. Nun werden A und B über das unsichere Medium übertragen.
  4. Die Kommunikationspartner berechnen nun K = B^a \bmod p bzw. K = A^b \bmod p. Das Ergebnis K ist für beide Partner gleich und kann als Schlüssel für die weitere Kommunikation verwendet werden.

Dass beide Kommunikationspartner denselben Wert für K berechnen, zeigen die folgenden beiden Gleichungen:

K = B^a \bmod p = (g^b \bmod p )^a \bmod p = g^{ba} \bmod p = g^{ab} \bmod p
K = A^b \bmod p = (g^a \bmod p )^b \bmod p = g^{ab} \bmod p

Beispiel[Bearbeiten]

Die Kommunikationspartner seien Alice und Bob. Das Beispiel benutzt sehr kleine Zahlen. In der tatsächlichen Anwendung werden Zahlen mit mehreren hundert Stellen benutzt.

  1. Alice und Bob einigen sich auf p = 13 und g = 2.
  2. Alice wählt die Zufallszahl a = 5. Bob wählt die Zufallszahl b = 8.
  3. Alice berechnet A = g^a \bmod p = 6 und sendet A an Bob.
  4. Bob berechnet B = g^b \bmod p = 9 und sendet B an Alice.
  5. Alice berechnet K = B^a \bmod p =3.
  6. Bob berechnet K = A^b \bmod p =3.
  7. Beide erhalten das gleiche Ergebnis K = 3.

Ein eventuell vorhandener Lauscher könnte zwar die Zahlen 13, 2, 6 und 9 mithören, das eigentliche gemeinsame Geheimnis von Alice und Bob K = 3 bleibt ihm aber verborgen. K = 3 kann als Schlüssel für die nachfolgende Kommunikation verwendet werden.

Sicherheit[Bearbeiten]

Diffie-Hellman-Problem[Bearbeiten]

Als (Computational-)Diffie-Hellman-Problem bezeichnet man die folgende Aufgabenstellung:

Wenn ein Element g einer Gruppe und die Werte A=g^a und B=g^b gegeben sind, welchen Wert hat dann g^{ab}, mit a,b unbekannt ?

Da dieses Problem in bestimmten Gruppen nur mit enormem Rechenaufwand zu lösen ist, kann ein Angreifer aus den beiden beim Diffie-Hellman-Schlüsselaustausch übertragenen Nachrichten nicht den erzeugten Schlüssel berechnen.

Eine Variante des obigen Suchproblems ist das Decisional-Diffie-Hellman-Problem. Bei diesem Problem muss g^{ab} nicht berechnet werden, sondern (gegeben dieselben Gruppenelemente) lediglich entschieden werden, ob es sich bei einem gegebenen Element um g^{ab} oder um ein zufällig gewähltes Gruppenelement handelt. Ist dieses Problem schwer, so hat ein Angreifer, der eine Übertragung belauscht hat, keinerlei Information über den ausgetauschten Schlüssel. Das ist eine stärkere Sicherheitseigenschaft, als den Schlüssel nicht berechnen zu können.

Das Diffie-Hellman-Problem ist eng verwandt mit dem Diskreter-Logarithmus-Problem. Wer diskrete Logarithmen berechnen kann, kann auch das Diffie-Hellman-Problem lösen. Es ist keine Möglichkeit bekannt, das Diffie-Hellman-Problem zu lösen, ohne diskrete Logarithmen zu berechnen. Ueli Maurer hat gezeigt, dass beide Probleme unter bestimmten Voraussetzungen äquivalent sind.[2]

Man-in-the-Middle-Angriff[Bearbeiten]

Der Diffie-Hellman-Schlüsselaustausch ist nicht mehr sicher, wenn der Angreifer (im folgenden Beispiel: die Angreiferin „Mallory“) bei einem Man-In-The-Middle-Angriff Datenpakete verändern kann. Der Angreifer fängt dann die von Alice und Bob gesendeten Nachrichten ab und sendet statt dessen jeweils seine eigene Nachricht

Z = g^z \mod p

weiter, die er aus einer beliebigen Zahl z und den öffentlich bekannten Zahlen g und p berechnet.

Man-in-the-Middle-Angriff

Nach dem Schlüsselaustausch besitzen die beiden Kommunikationspartner Alice und Bob unterschiedliche Schlüssel K_A und K_B. Im Prinzip wurde zweimal ein Diffie-Hellman-Schlüsselaustausch durchgeführt: einmal zwischen Alice und der Angreiferin Mallory und einmal zwischen Mallory und Bob. Dabei erlangt Mallory Kenntnis der beiden Schlüssel K_A und K_B.

K_A = Z^a \bmod p = (g^z)^a \bmod p = (g^a)^z \bmod p = A^z \bmod p
K_B = Z^b \bmod p = (g^z)^b \bmod p = (g^b)^z \bmod p = B^z \bmod p

Da Alice und Bob im weiteren Verlauf davon ausgehen, mit dem jeweils Anderen zu kommunizieren, kann Mallory die folgende symmetrisch verschlüsselte Kommunikation abhören. Diese leitet sie dazu weiterhin über sich selbst um. Daten von Alice entschlüsselt Mallory mit K_A und verschlüsselt sie wieder mit K_B, bevor sie sie an Bob weiterschickt. Dabei kann Mallory den Nachrichteninhalt sowohl lesen als auch unbemerkt verändern. Die gleiche Vorgehensweise wendet sie auch für die Gegenrichtung an.

Um einen solchen Man-In-The-Middle-Angriff auszuschließen, müssen die ausgetauschten Nachrichten authentifiziert werden. Dazu verwendet man digitale Signaturen.[3]

Andere Gruppen[Bearbeiten]

Für den Diffie-Hellman-Schlüsselaustausch können neben den primen Restklassengruppen (\mathbb{Z} / p \mathbb{Z} )^\times auch andere Gruppen verwendet werden. Es sind alle Gruppen geeignet, in denen man Potenzen effizient berechnen kann und das Diffie-Hellman-Problem schwer zu lösen ist, beispielsweise Gruppen auf bestimmten elliptischen Kurven.[4]

Literatur[Bearbeiten]

Weblinks[Bearbeiten]

Einzelnachweise[Bearbeiten]

  1.  Diffie, W. and Hellman, M. E.: New Directions in Cryptography. In: IEEE Transactions on Information Theory. 22, Nr. 6, 1976, S. 644–654 (PDF).
  2. Ueli Maurer: Towards the equivalence of breaking the Diffie-Hellman protocol and computing discrete logarithms. In: Advances in Cryptology – Crypto '94. Springer-Verlag, 1994, S. 271–281.
  3. Shafi Goldwasser, Mihir Bellare: Lecture Notes on Cryptography. 2008, Abschnitt 11.5
  4. Alfred J. Menezes, Paul C. van Oorschot, Scott A. Vanstone: Handbook of Applied Cryptography. CRC Press, 1996, ISBN 0-8493-8523-7, S. 515–517