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.
N E U ! Security aktuell
Täglich aktuelle Security-Infos!
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.
- 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. - Alice wählt eine geheime Zahl
a < p und sendet Bob
- 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. - Alice berechnet
(und kann danach a löschen).
- 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.
- Alice wählt a und sendet Bob

- Bob wählt b und sendet Carol

- Carol wählt c und sendet Alice

- Alice sendet Bob

- Bob sendet Carol

- Carol sendet Alice

- Alice berechnet

- Bob berechnet

- Carol berechnet

Der geheime Schlüssel k ist
.
In der nächsten Folge werden die schon mehrmals erwähnten Hashfunktionen vorgestellt.
Wenn Sie Fragen oder Themenvorschläge haben, können Sie diese gerne an die angegebene E-Mail-Adresse senden oder im Security-Forum einbringen!



und
(Schlüssel mit Alice)
(Schlüssel mit Bob)















Kommentare