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 Schlüsselaustauschprotokoll. 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 schaltet 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 Diffie-Hellman-Schlüsselaustausch ist mit dem Elgamal-Verschlüsselungsverfahren eng verwandt. Die Implementierung mittels elliptischer Kurven ist als Elliptic Curve Diffie-Hellman (ECDH) bekannt.

Geschichte[Bearbeiten | Quelltext 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 | Quelltext bearbeiten]

Illustration des Diffie-Hellman-Schlüsselaustauschs anhand gemischter Farben
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 zyklische Gruppe primer Ordnung p und einen Erzeuger g dieser Gruppe. 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-1 \}. 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 Restklassengleichungen:

K \equiv B^a \equiv (g^b)^a \equiv g^{ba} \equiv g^{ab} \mod p
K \equiv A^b \equiv (g^a)^b \equiv g^{ab} \mod p

Beispiel[Bearbeiten | Quelltext 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 (meist Eve genannt) 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 | Quelltext bearbeiten]

Diffie-Hellman-Problem[Bearbeiten | Quelltext 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 K=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]

Rechenaufwand in der Praxis[Bearbeiten | Quelltext bearbeiten]

Die schnellste bekannte Methode zum Berechnen des diskreten Logarithmus in allgemeinen endlichen Körpern ist das Zahlkörpersieb. Wenn die Ordnung der von p erzeugten Gruppe nur kleine Faktoren besitzt, kann der schnellere Pohlig-Hellman-Algorithmus verwendet werden; dies kann durch die Wahl einer „sicheren“ Primzahl verhindert werden. Da die Erzeugung sicherer Primzahlen rechenaufwendig ist, verwenden viele Implementierungen eine feste Primzahl p.[3] Einige Netzwerkprotokolle wie etwa Internet Key Exchange geben eine Liste von möglichen Gruppen und deren Primzahl vor.

Die Verwendung fester Gruppen und Primzahlen kann ein Angreifer ausnutzen, um einen Großteil der Berechnung zum Brechen des diskreten Logarithmus vorab durchzuführen und um mehrere Ziele gleichzeitig anzugreifen. Der Zahlkörpersieb-Algorithmus besteht aus vier Schritten, wobei die ersten drei Schritte lediglich die Primzahl p benötigen. Ist p bekannt, kann ein Angreifer somit den Großteil vorberechnen und die Ergebnisse für jeden auf p basierenden Schlüsselaustausch wiederverwenden. Dadurch kann zum Beispiel der Logjam-Angriff in TLS, nach einer einwöchigen Vorberechnung, einen 512-bit Diffie-Hellman-Schlüsselaustausch in rund 70 Sekunden brechen.[3]

Nach Schätzungen eines Forscherteams kann ein Angreifer mit Vorberechnung der 10 häufigsten 1024-bit Primzahlen den Netzwerkverkehr von 66 % der VPNs, 26 % der SSH-Server, 16 % der SMTP-Server und 24 % der HTTPS-Websites im Internet entschlüsseln. Die Forscher schätzen, dass der Rechenaufwand zum Brechen von 1024-bit Diffie-Hellman von einem staatlichen Angreifer wie der National Security Agency aufgebracht werden kann.[3]

Man-in-the-Middle-Angriff[Bearbeiten | Quelltext bearbeiten]

Hauptartikel: Man-In-The-Middle-Angriff

Der Diffie-Hellman-Schlüsselaustausch ist nicht mehr sicher, wenn der Angreifer (im folgenden Beispiel heißt 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 stattdessen 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 wird ein Informationsvorsprung benötigt, der über einen authentifizierten Kanal erreicht wird.[4]

Andere Gruppen[Bearbeiten | Quelltext 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.[5]

Ephemeral Diffie-Hellman[Bearbeiten | Quelltext bearbeiten]

Im Zusammenhang des Verschlüsselungsprotokolls Transport Layer Security (TLS) bezeichnet Ephemeral Diffie-Hellman (englisch ephemeral: flüchtig) die Verwendung von Diffie-Hellman mit jeweils neuen Parametern für jede neue TLS-Sitzung. Bei statischem Diffie-Hellman werden für jede TLS-Sitzung dieselben Parameter wiederverwendet, die sich aus einem Public-Key-Zertifikat herleiten. In beiden Fällen wird derselbe Algorithmus verwendet und lediglich die Parameter unterscheiden sich.

Die Verwendung von Ephemeral Diffie-Hellman zur Aushandlung eines symmetrischen Sitzungsschlüssels bietet Forward Secrecy, im Gegensatz zur verschlüsselten Übertragung eines Sitzungsschlüssels mit einem Public-Key-Verschlüsselungsverfahren, zum Beispiel RSA.

Literatur[Bearbeiten | Quelltext bearbeiten]

Weblinks[Bearbeiten | Quelltext bearbeiten]

Einzelnachweise[Bearbeiten | Quelltext 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. a b c  David Adrian, Karthikeyan Bhargavan, Zakir Durumeric, Pierrick Gaudry, Matthew Green, J. Alex Halderman, Nadia Heninger, Drew Springall, Emmanuel Thomé, Luke Valenta, Benjamin VanderSloot, Eric Wustrow, Santiago Zanella-Béguelin, Paul Zimmermann: Imperfect Forward Secrecy: How Diffie-Hellman Fails in Practice. In: Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security. ACM, New York 2015, S. 5–17, doi:10.1145/2810103.2813707 (PDF-Datei).
  4. Shafi Goldwasser, Mihir Bellare: Lecture Notes on Cryptography. 2008, Abschnitt 11.1.5 und 11.2
  5. 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