Diffie-Hellman-Merkle-Schlüsselaustausch

Diffie-Hellman-Merkle ist ein asymmetrisches, kryptografisches Verfahren, dass man für den Schlüsselaustausch bzw. die Schlüsselvereinbarung verwendet. In der Praxis sorgt es dafür, dass sich zwei oder mehr Kommunikationspartner auf einen gemeinsamen Sitzungsschlüssel einigen, den alle zum Ver- und Entschlüsseln verwenden können.
Das besondere an Diffie-Hellman-Merkle ist, dass nicht der geheime Sitzungsschlüssel, sondern nur das Ergebnis einer Rechenoperation übertragen wird. Bei dieser Rechenoperation geht man von der Annahme aus, dass Potenzieren von Zahlen leicht, aber den diskreten Logarithmus zu berechnen schwer ist. Solange die notwendige Rechenleistung fehlt und es keine Vereinfachung zum Lösen des Diskreten-Logarithmus-Problems gibt, so lange ist dieses Verfahren sicher.

Der Diffie-Hellman-Merkle-Schlüsselaustausch wurde von den drei Wissenschaftlern Diffie, Hellman und Merkle im Jahr 1976 veröffentlicht. Jahrzehnte später, nach der Veröffentlichung durch Diffie, Hellman und Merkle, wurde bekannt, dass bereits ein paar Jahre zuvor drei Wissenschaftler des britischen Geheimdienstes GCHQ das Prinzip dieses Verfahrens erfunden haben. Allerdings wurde dieses Verfahren aus Gründen der Geheimhaltung damals nicht öffentlich gemacht. Deshalb wird die Entdeckung des Prinzips, das im Diffie-Hellman-Merkle-Schlüsselaustausch angewendet wird, nicht den drei Wissenschaftlern des GCHQ zugeschrieben, sondern Diffie, Hellman und Merkle.
Häufig wird nur die Bezeichnung Diffie-Hellman verwendet. Der Name Merkle wird einfach weggelassen. Merkles Verdienst sollte aber nicht unerwähnt bleiben. Deshalb wird Diffie-Hellman hier vollständig mit Diffie-Hellman-Merkle benannt.

Der Diffie-Hellman-Merkle-Schlüsseltausch bildet die Grundlage für das Protokoll Secure Shell (SSH2, OpenSSH), IPSec und TLS mit Forward Secrecy und Perfect Forward Secrecy. Weil der Schlüsselaustausch eine Interaktion beider Parteien voraussetzt, kann es nicht bei der direkten Verschlüsselung von E-Mails eingesetzt werden. Bei der Transportverschlüsselung mit STARTTLS allerdings schon.

Warum Schlüsselaustausch nach Diffie-Hellman-Merkle?

Bei den typischen Schlüsselaustauschverfahren der modernen Kryptografie muss während der Aushandlung der Verschlüsselung zwischen zwei Kommunikationspartnern der geheime Sitzungsschlüssel ausgetauscht werden. Nur dann können beide Seiten die Daten ver- und entschlüsseln. Das Problem dabei ist, dass der geheime Sitzungsschlüssel bei der Übertragung durch einen Angreifer aufgezeichnet werden kann. Der Sitzungsschlüssel ist zwar verschlüsselt. Doch wenn der Angreifer irgendwann den geheimen Sitzungsschlüssel herausbekommt, dann kann er auch die verschlüsselten Daten entschlüsseln.
Die Besonderheit beim Diffie-Hellman-Merkle-Schlüsselaustausch ist die, dass der geheime Sitzungsschlüssel nicht übertragen wird, sondern nur das Ergebnis einer Rechenoperation, die keinen Rückschluss auf den Schlüssel zulässt.

Hinweis: Der Diffie-Hellman-Merkle-Schlüsselaustausch ist, um genau zu sein, kein Schlüsselaustauschverfahren. Denn zu keinem Zeitpunkt wird der geheime Sitzungsschlüssel zwischen den Kommunikationspartnern ausgetauscht. Viel eher wäre die Bezeichnung "Schlüsselvereinbarungsverfahren" (engl. key agreement) geeignet. Es hat sich allerdings eingebürgert von einem Schlüsselaustausch zu sprechen, auch wenn es nicht ganz korrekt ist. Wie so oft in der Kryptografie muss man auch bei der Benennung und Einordnung dieses Verfahrens eine Ungenauigkeit akzeptieren.

Wie funktioniert der Diffie-Hellman-Merkle-Schlüsselaustausch?

Den Diffie-Hellman-Schlüsselaustausch bezeichnet man häufig einfach nur als Diffie-Hellman-Verfahren.

In der folgenden Beschreibung ist von Alice und Bob die Rede. Beide stehen beispielhaft für zwei Kommunikationspartner, die ihre Kommunikation verschlüsseln wollen und den dazu notwendigen geheimen Sitzungsschlüssel zum Ver- und Entschlüsseln vorab austauschen müssen. Um den Sitzungsschlüssel vor einem Angreifer zu schützen, der eventuell die Kommunikation abhört oder aufzeichnet, in der Hoffnung den Sitzungsschlüssel abgreifen zu können, vereinbaren sie den Schlüsselaustausch nach Diffie-Hellman-Merkle.

Wie funktioniert der Diffie-Hellman-Merkle-Schlüsselaustausch?

Zuerst müssen sich Alice und Bob auf eine große Primzahl p und eine natürliche Zahl g, die ein Generator aus Gruppe Z(p) sein sollte, einigen. Die Zahl g kann aber auch einen Wert kleiner p annehmen. Beide Werte dürfen bekannt sein und können deshalb über einen unsicheren Kanal übertragen werden. Weil Alice die Kommunikation zu Bob aufbaut, legt typischerweise Alice die Zahlen p und g fest. Diese Vorgehensweise kann in der Praxis auch anders erfolgen. Für dieses Beispiel wählt Alice p = 11 und g = 7.

Alice erzeugt nun zusätzlich eine Zufallszahl a, die kleiner als die gewählte Primzahl p sein muss (1 ... p - 1). Für dieses Beispiel wählen wir a = 3. Dann stellt Alice folgende Rechnung auf.

Anschließend überträgt Alice die Zahlen p und g, sowie das Ergebnis A an Bob.

Bob erzeugt sich ebenfalls eine Zufallszahl b, die kleiner als die gewählte Primzahl p ist (1 ... p -1). Für dieses Beispiel wählen wir b = 6. Dann stellt Bob folgende Rechnung auf.

Anschließend überträgt Bob das Ergebnis B an Alice.

Alice berechnet nun den Schlüssel K1, auch Geheimnis (Secret) genannt.

Bob berechnet den Schlüssel K2, auch Geheimnis (Secret) genannt.

Beide kommen auf das gleiche Ergebnis und haben so einen gemeinsamen geheimen Schlüssel. Dieser Schlüssel kann zum Beispiel in einem symmetrischen Verfahren als temporärer Sitzungsschlüssel genutzt werden.

Der Angreifer kennt nur p und g. Außerdem A und B, da beide Werte übertragen werden. Allerdings kann er den Schlüssel K nur berechnen, wenn er a und b hat. Da diese Werte nicht übertragen werden, muss der Angreifer sich den Schlüssel anders berechnen, was bei einer ausreichend großen Primzahl fast unmöglich ist.
Dieses Verfahren beruht darauf, dass es mit wenig Rechenleistung möglich ist, die Potenz gx mod p zu errechnen. Aber der umgekehrte Weg von gx auf x zu schließen ist sehr schwierig (diskreter Logarithmus).

Diffie-Hellman-Merkle und Perfect Forward Secrecy

Grundsätzlich muss man zwischen Forward Secrecy (gleiche Parameter über die gesamte Sitzung) und Perfect Forward Secrecy (regelmäßige Parameteränderung während der Sitzung) unterscheiden.
Auf Diffie-Hellman bezogen bedeutet das, dass Diffie-Hellman mit statischen Parametern aus dem Zertifikat, nur Forward Secrecy aber kein Perfect Forward Secrecy ist. Der Grund ist, aus dem öffentlichen und privaten Schlüssel können die Parameter und der Sitzungsschlüssel hergeleitet werden.
Wenn Diffie-Hellman mit temporären Parametern arbeitet (ephemeral = flüchtig), dann bietet es Perfect Forward Secrecy und ist somit sicherer. Dabei muss man berücksichtigen, dass die regelmäßige Erzeugung neuer temporärer Parameter Rechenleistung kostet und deshalb bei Server-Betreibern nicht so beliebt ist.

Wie sicher ist Diffie-Hellman-Merkle?

Bei Diffie-Hellman-Merkle und auch anderen Diskreter-Logarithmus-Verfahren ist nicht die vollständige Schlüsselsuche die effektivste Angriffsmethode. Es gibt Algorithmen zur Berechnung des diskreten Logarithmus. Der Aufwand ist sehr groß, aber immer noch schneller, als die vollständige Schlüsselsuche. Das ist jedoch nicht weiter schlimm. Je größer g, x und y sind, desto größer der Sicherheitsgewinn und desto sicherer das Verfahren. Eine Schlüssellänge von 1.024 gilt als Minimum. Empfohlen wird häufig 2.048 Bit oder mehr.
Ein weiterer Schwachpunkt ist ein möglicher Man-in-the-Middle-Angriff, der sich durch den Einsatz einer Public-Key-Infrastruktur verhindern lässt. Besonders fatal ist das, weil der Angreifer an den Schlüssel kommen kann. Die Gefahr kann man reduzieren, in dem die Kommunikationspartner mit wechselnden Schlüsseln arbeiten. Gelangt der Angreifer an einen der Schlüssel kann er nur einen Teil der Kommunikation entschlüsseln.

Man-in-the-Middle beim Diffie-Hellman-Verfahren

Das Prinzip des Diffie-Hellman-Merkle-Schlüsselaustauschs ist zwar von mathematischer Seite her einigermaßen sicher, hat aber einen anderen Schwachpunkt. Der Diffie-Hellman-Schlüsselaustausch ist dann nicht mehr sicher, wenn sich ein Angreifer zwischen die beiden Kommunikationspartner als Man-in-the-Middle schaltet und Nachrichten verändern kann.

Man-in-the-Middle bei Diffie-Hellman-Merkle-Schlüsselaustausch

Der Angreifer fängt dazu die von Alice und Bob gesendeten Nachrichten ab und sendet statt dessen jeweils seine eigenen Nachrichten. In dem Fall die Nachrichten mit den Zahlen zum Berechnen des Schlüssels. Hier setzt der Angreifer eigene Werte für die zufällige Zahl und die öffentlich bekannten Zahlen p und g ein.
Um einen solchen Man-in-the-Middle-Angriff auszuschließen, müssen die ausgetauschten Nachrichten authentifiziert werden. Dazu bedarf es eines funktionierenden und vertrauenswürdigen Authentifizierungsverfahrens mit digitalen Signaturen und Message Authentication Codes.

Übersicht: Asymmetrische Kryptografie