Freitag, 8. Juni 2012


Topthema

Donnerstag, 19. April 2007 | Topthema

About Security #101: Diffie-Hellman- Schlüsselaustausch

(Link zum Artikel: http://www.entwickler.de/php/kolumnen/035367)
  • Teilen
  • kommentieren
  • empfehlen
  • Bookmark and Share

Der Diffie-Hellman-Schl�sselaustausch 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.

  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^i 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^xund 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.

About Security: Die komplette Serie

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

Alice: kA = M^a mod p = g^ma mod p
Bob: kB = M^b mod p = g^mb mod p
Mallory: kA = A^m mod p = g^am mod p und kB = B^m mod p = g^bm mod p

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 Zahlenbeispiele
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 5^6 mod 23 = 8 = A
Meine Zahl: A=8
A=8 A=8
W�hlt geheime Zahl b=15
Berechnet 5^15 mod 23 = 19 = B
Meine Zahl: B=19
B=19 B=19
Berechnet 19^6 mod 23 = 2 = k Berechnet 8^15 mod 23 = 2 = k
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
5^6 mod 23 = 8 = A
Meine Zahl: A=8
A=8
W�hlt m=3
Berechnet M = 5^3 mod 23 = 10
F�lscht A=10
A=10
W�hlt geheime Zahl b=15
Berechnet 5^15 mod 23 = 19 = B
Meine Zahl: B=19
B=19
F�lscht B=10
B=10
Berechnet 10^6 mod 23 = 6
 
Berechnet 8^3 mod 23 = 6 (Schl�ssel mit Alice)
Berechnet 19^3 mod 23 = 5 (Schl�ssel mit Bob)
 
Berechnet 10^15 mod 23 = 5
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 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 geheime Schl�ssel k ist g^abc mod p.

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!

Carsten Eilers

Kommentare

Gravatar Gabber 25.05.2009
um 03:05 Uhr
"Um diesen Angriff zu verhindern, m�ssen die ausgetauschten Nachrichten durch eine digitale Signatur oder einen Message Authentication Code authentisiert werden. "

Genau dazu h�tte ich hier gerne mehr gelesen
#zitieren

Folgende Links könnten Sie auch interessieren