URL dieser Newsmeldung:

Wie angekündigt geht es in dieser Folge um den schon mehrmals erwähnten Diffie-Hellman-Schlüsselaustausch. Das Verfahren wurde von Whitfield Diffie und Martin E. Hellman 1976 in ihrem Paper "New Directions in Cryptography" (PDF) vorgestellt, der ersten Arbeit über asymmetrische Kryptographie. 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.

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
3. Bob wählt eine geheime Zahl b < p und sendet Alice
   A und B müssen nicht geheim bleiben, können also über eine unsichere Verbindung übertragen werden.
4. Alice berechnet (und kann danach a löschen).
5. Bob berechnet (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 darstellen lassen.

k und k' sind identisch, denn es gilt , 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, und . Welchen Wert hat ?
Dazu muss er diskrete Logarithmen berechnen können: Er benötigt das x aus (oder das y aus ). 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.

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

Alice:
Bob:
Mallory:	und

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

1) Diffie-Hellman-Schlüsselaustausch mit Lauscher

Alice	Eve	Bob
Lass uns p=23 nehmen.
	p=23	p=23
		Einverstanden. Und g=5.
g=5	g=5
Wählt geheime Zahl a=6 Berechnet Meine Zahl: A=8
	A=8	A=8
		Wählt geheime Zahl b=15 Berechnet Meine Zahl: B=19
B=19	B=19
Berechnet		Berechnet
	k=???

2) Diffie-Hellman-Schlüsselaustausch mit Man-in-the-Middle

Alice	Mallory	Bob
Lass uns p=23 nehmen.
	p=23	p=23
		Einverstanden. Und g=5.
g=5	g=5
Wählt geheime Zahl a=6 Meine Zahl: A=8
	A=8
	Wählt m=3 Berechnet Fälscht A=10
		A=10
		Wählt geheime Zahl b=15 Berechnet Meine Zahl: B=19
	B=19
	Fälscht B=10
B=10
Berechnet	Berechnet (Schlüssel mit Alice) Berechnet (Schlüssel mit Bob)	Berechnet

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, Alice, Bob und Carol, beschrieben. Entsprechend kann es auch auf mehr Partner erweitert werden.

1. Alice wählt a und sendet Bob
2. Bob wählt b und sendet Carol
3. Carol wählt c und sendet Alice
4. Alice sendet Bob
5. Bob sendet Carol
6. Carol sendet Alice
7. Alice berechnet
8. Bob berechnet
9. Carol berechnet

Der geheime Schlüssel k ist .

In der nächsten Folge werden die schon mehrmals erwähnten Hashfunktionen vorgestellt.

Carsten Eilers