Dipl.-Inform. Carsten Eilers

Das britische 'Government Communications Headquarters' (GCHQ) behauptete 1997, schon davor das RSA- und Diffie-Hellman-Verfahren erfunden, aber geheim gehalten zu haben. Das ist durchaus plausibel, die Ehre gebührt aber üblicherweise dem, der etwas zuerst veröffentlicht. Siehe dazu auch Bruce Schneiers Crypto-Gram Newsletter vom 15. Mai 1998.

Das Prinzip des Diffie-Hellman-Schlüsselaustauschs besteht darin, dass sich die Kommunikationspartner über eine unsichere Verbindung je eine Nachricht zusenden, aus denen sie dann einen gemeinsamen Schlüssel berechnen können. Ein Dritter, der die Nachrichten belauscht, ist dazu nicht in der Lage. Das Verfahren ist allerdings unsicher, wenn der Dritte als Man-in-the-Middle die Nachrichten manipulieren kann.

Die mathematische Beschreibung

Im Folgenden wird von zwei Kommunikationspartnern ausgegangen, den traditionellen Alice und Bob.

1. Alice und Bob einigen sich auf eine Primzahl p und eine Primitivwurzel (*) g mod p mit 1 < g < p-1.
   p und g müssen nicht geheim bleiben, können also über eine unsichere Verbindung übertragen werden. Außerdem können sie vorab vereinbart und immer wieder verwendet werden.
2. Alice wählt eine geheime Zahl a < p und sendet Bob A = g^a mod p
3. Bob wählt eine geheime Zahl b < p und sendet Alice B = g^b mod p
   A und B müssen nicht geheim bleiben, können also über eine unsichere Verbindung übertragen werden.
4. Alice berechnet k = B^a mod p (und kann danach a löschen).
5. Bob berechnet k' = A^b mod p (und kann danach b löschen).

(*) g ist eine Primitivwurzel von p, wenn sich alle Zahlen von 1 bis p-1 als Reste der Form gⁱ mod p darstellen lassen.

k und k' sind identisch, denn es gilt
k = g^ba mod p = g^ab mod p = k'
und können als Sitzungsschlüssel für ein symmetrisches Verfahren verwendet werden.

Ein lauschender Angreifer (üblicherweise Eve genannt) kennt zwar p, g, A und B, aber um den Schlüssel k zu ermitteln muss er das so genannte Diffie-Hellman-Problem lösen:

Bekannt sind g, g^x und g^y.
Welchen Wert hat g^xy?

Dazu muss er diskrete Logarithmen berechnen können:
Er benötigt das x aus g^x mod p (oder das y aus g^y mod p).

Dies ist ein mathematisch hartes Problem und ähnlich schwer wie die Faktorisierung.

Die Sicherheit des Verfahrens hängt entscheidend von der Größe von p ab. Außerdem sollte (p-1)/2 ebenfalls eine Primzahl sein. g kann beliebig groß gewählt werden, es muss nur eine Primitivwurzel modulo p sein. Es spricht nichts dagegen, das kleinstmögliche g zu wählen.

Ein Man-in-the-Middle-Angriff

Kann der Angreifer Mallory als Man-in-the-Middle die ausgetauschten Nachrichten manipulieren, kann er den Schlüsselaustausch unterlaufen: Er fängt die Nachrichten ab und sendet seinen eigenen Wert M = g^m mod p mit einem beliebigen m statt A und B. Es findet also je ein Schlüsselaustausch zwischen Alice und Mallory und zwischen Mallory und Bob statt – ohne dass Alice und Bob etwas von Mallory wissen. Damit ergeben sich folgende Schlüssel:

Mallory fängt danach die symmetrisch verschlüsselten Daten ab, entschlüsselt sie mit dem zum jeweiligen Absender gehörenden Schlüssel und verschlüsselt sie vor dem Weiterleiten mit dem zum Empfänger gehörenden Schlüssel. Dabei kann er die entschlüsselten Daten beliebig manipulieren.

Um diesen Angriff zu verhindern, müssen die ausgetauschten Nachrichten durch eine digitale Signatur oder einen Message Authentication Code authentisiert werden.

Zwei Zahlen-Beispiele

Das Verfahren ist mit Zahlen leichter zu verstehen, daher nun zwei Beispiele für den Diffie-Hellman-Schlüsselaustausch. Einmal mit einem nur lauschenden Angreifer, einmal mit einem die Nachrichten auch manipulierenden Man-in-the-Middle.

Diffie-Hellman-Schlüsselaustausch mit Lauscher

Diffie-Hellman-Schlüsselaustausch mit Nachrichten manipulierenden Man-in-the-Middle

Diffie-Hellman-Schlüsselaustausch mit mehr als 2 Partnern

Das Protokoll lässt sich auch so erweitern, dass mehr als 2 Kommunikationspartner einen Schlüssel austauschen können. Im Folgenden wird das Verfahren für drei Partner beschrieben: Alice, Bob und Carol. Entsprechend kann es auch auf mehr Partner erweitert werden.

1. Alice wählt a und sendet Bob A = g^a mod p
2. Bob wählt b und sendet Carol B = g^b mod p
3. Carol wählt c und sendet Alice C = g^c mod p
4. Alice sendet Bob C' = C^a mod p
5. Bob sendet Carol A' = A^b mod p
6. Carol sendet Alice B' = B^c mod p
7. Alice berechnet k = B' ^a mod p
8. Bob berechnet k = C' ^b mod p
9. Carol berechnet k = A' ^c mod p

Der gemeinsame geheime Schlüssel k ist g^abc mod p.

In der nächsten Folge wird eine Anwendung des Diffie-Hellman-Schlüsselaustauschs vorgestellt: SSL/TLS mit Perfect Forward Secrecy.

Carsten Eilers