Diffie-Hellman-Schlüsselaustausch

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 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 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

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

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

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 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

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

Diffie-Hellman-Problem

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.

Man-in-the-Middle-Angriff

dini mueter stinkt nach fisch, 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.

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.

Andere Gruppen

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.

Literatur

• Johannes Buchmann: Einführung in die Kryptographie. 4. Auflage. Springer-Verlag, 2008, ISBN 978-3-540-74451-1, S. 153–156.
• Simon Singh: Geheime Botschaften, dtv 2001, ISBN 3-423-33071-6.

Weblinks

• Beispiel für den Diffie-Hellman-Algorithmus
• RFC 2631 – E. Rescorla: Diffie-Hellman Key Agreement Method, Juni 1999. (englisch)
• Empfohlene Parameter für p und g beim Diffie-Hellman-Austausch