Diffie-Hellman-Schlüsselaustausch

Zweck und Bedeutung

Der Diffie-Hellman-Merkle-Schlüsselaustausch (DHM-Protokoll) ist ein Verfahren zur Schlüsselvereinbarung. Zwei Kommunikationspartner können damit über eine öffentliche, abhörbare Leitung einen gemeinsamen geheimen Schlüssel berechnen, ohne ihn direkt zu übertragen. Dieser Schlüssel wird anschließend meist für ein symmetrisches Kryptosystem wie DES oder AES verwendet.

Das Verfahren löst damit das Schlüsseltauschproblem symmetrischer Verschlüsselung: Alice und Bob benötigen denselben geheimen Schlüssel, besitzen aber keinen sicheren Kanal für dessen Übergabe. Bei n Kommunikationspartnern wären für eine vollständige Kommunikation untereinander n·(n−1)/2 Schlüssel erforderlich; bei 50 Partnern sind das 1.225 Schlüssel.

Whitfield Diffie und Martin Hellman veröffentlichten das Verfahren 1976 unter der Bezeichnung „ax1x2“. Wichtige Vorarbeiten leistete Ralph Merkle mit dem Merkles Puzzle. 1997 wurde bekannt, dass Mitarbeiter des britischen GCHQ bereits in den 1970er-Jahren asymmetrische Verfahren entwickelt hatten. Varianten des DHM-Verfahrens werden unter anderem in IPsec, IPv6 und TLS eingesetzt.

Mathematische Grundlage

Die Sicherheit beruht auf der diskreten Exponentialfunktion als angenommener Einwegfunktion. Eine Einwegfunktion lässt sich in Polynomialzeit berechnen, ihre Umkehrung ist jedoch mit den bekannten Verfahren nicht schnell berechenbar. Für den DHM-Austausch gilt:

r = bˣ mod m.

Die Berechnung von r ist auch für große Exponenten effizient, etwa mit dem Square-and-Multiply-Verfahren. Die Umkehrung, also die Berechnung von x aus b, m und r, heißt diskreter Logarithmus. Für große Zahlen ist dafür bis heute kein effizienter Algorithmus bekannt; mathematisch ist allerdings nicht bewiesen, dass ein solcher Algorithmus niemals gefunden wird.

Die Berechnungen erfolgen in Gruppen. Eine Gruppe besitzt eine assoziative Verknüpfung, ein neutrales Element und inverse Elemente. Eine zyklische Gruppe wird durch die Potenzen eines Erzeugers oder Generators gebildet. Für eine Primzahl p bilden die Zahlen 1 bis p−1 mit der Multiplikation modulo p die prime Restklassengruppe Zₚ*; sie ist zyklisch. Ein Generator dieser Gruppe heißt Primitivwurzel modulo p.

Beispiel: In Z₁₃* ist 2 ein Generator, weil sich alle Zahlen von 1 bis 12 als Potenzen von 2 modulo 13 darstellen lassen. 3 erzeugt dagegen nur die Untergruppe {1, 3, 9}. Für eine Primzahl p gibt es genau φ(p−1) Primitivwurzeln modulo p. Für p = 13 gilt φ(12) = 4; die Primitivwurzeln sind 2, 6, 7 und 11.

Ablauf des Schlüsselaustauschs

Alice und Bob einigen sich öffentlich auf eine große Primzahl p und eine natürliche Zahl g < p. Idealerweise ist g ein Generator der Gruppe Zₚ*. Danach wählen sie geheim zufällige Zahlen a und b aus {1, …, p−1}.

• Alice berechnet ihren öffentlichen Schlüssel A = gᵃ mod p und sendet A an Bob.
• Bob berechnet seinen öffentlichen Schlüssel B = gᵇ mod p und sendet B an Alice.
• Alice berechnet K₁ = Bᵃ mod p.
• Bob berechnet K₂ = Aᵇ mod p.

Beide erhalten denselben Sitzungsschlüssel, weil K₁ = (gᵇ)ᵃ mod p = gᵇᵃ mod p und K₂ = (gᵃ)ᵇ mod p = gᵃᵇ mod p gilt. Wegen ab = ba ist K₁ = K₂ = K.

Im Beispiel werden p = 13 und g = 2 gewählt. Alice verwendet a = 5, Bob b = 8. Daraus folgen A = 2⁵ mod 13 = 6 und B = 2⁸ mod 13 = 9. Alice berechnet 9⁵ mod 13 = 3, Bob 6⁸ mod 13 = 3. Der gemeinsame Schlüssel lautet also K = 3. Bei echten Anwendungen werden wesentlich größere Zahlen verwendet.

Die Farbmisch-Analogie beschreibt dasselbe Prinzip: Eine gemeinsame öffentliche Farbe wird mit je einer geheimen Farbe gemischt. Die ausgetauschten Mischungen werden anschließend jeweils mit der eigenen geheimen Farbe weitergemischt. Alice und Bob erhalten dieselbe Endfarbe, während Eve die geheimen Bestandteile nicht effizient zurückgewinnen kann.

Sicherheitsprobleme und Angriffe

Das Computational-Diffie-Hellman-Problem (CDH) fragt: Sind g, A = gᵃ und B = gᵇ gegeben, wie lässt sich K = gᵃᵇ berechnen, ohne a und b zu kennen? Das Problem gilt in geeigneten Gruppen als sehr aufwendig. Es ist eng mit dem diskreten Logarithmus verbunden, aber nicht bewiesen ist, dass beide Probleme vollständig gleichwertig sind.

Das Decisional-Diffie-Hellman-Problem (DDH) fragt, ob ein gegebenes Tripel (gᵃ, gᵇ, gᶜ) ein Diffie-Hellman-Tripel mit c = ab mod p ist oder zufällig erzeugt wurde. Wer CDH lösen kann, kann auch DDH lösen; die Umkehrung ist nicht klar. Bei Wahl einer Primitivwurzel kann DDH jedoch angegriffen werden: Ein Angreifer kann anhand quadratischer Reste in 75 % der Fälle richtig entscheiden und besitzt damit einen Vorteil von 50 % gegenüber reinem Raten.

Der grundlegende DHM-Austausch schützt nicht vor einem Man-in-the-Middle-Angriff. Mallory ersetzt die öffentlichen Nachrichten durch Z = gᶻ mod p. Alice und Mallory berechnen dann K_A = Aᶻ mod p, Mallory und Bob K_B = Bᶻ mod p. Mallory kennt beide Schlüssel, kann Nachrichten entschlüsseln, verändern und erneut verschlüsseln. Deshalb müssen die Nachrichten authentifiziert werden, etwa durch digitale Signaturen und Message Authentication Codes wie im Station-to-Station-Protokoll.

Seitenkanalangriffe greifen nicht die mathematische Idee, sondern ihre Implementierung an. Beim Zeitangriff werden Laufzeiten des Square-and-Multiply-Verfahrens gemessen, weil Multiplikationen länger dauern als Quadrierungen. Paul Kocher zeigte 1995, dass sich mit einigen Tausend Messungen Implementierungen mit 1024-Bit-Schlüsseln brechen lassen. Gegenmaßnahmen sind Blinding und eine eingabewertunabhängige Laufzeit. Beim Stromangriff wird der Stromverbrauch, beispielsweise mit einem Oszilloskop, analysiert. Dummy-Operationen und künstliches Stromrauschen können schützen.

Wahl der Parameter und feste Gruppen

Die Primzahl p muss so groß gewählt werden, dass diskrete Logarithmen mit bekannten Verfahren nicht effizient berechnet werden können. Das Bundesamt für Sicherheit in der Informationstechnik empfahl 2017 für Einsatzzeiträume über 2022 hinaus eine Schlüssellänge von mindestens 3000 Bit. Außerdem sollte p−1 nicht nur kleine Primfaktoren besitzen, da sonst der Pohlig-Hellman-Algorithmus eingesetzt werden kann. p sollte auch für das Zahlkörpersieb möglichst ungeeignet sein.

Der Generator g sollte eine große Untergruppe, möglichst die gesamte Gruppe Zₚ*, erzeugen. Bei g = 1 wäre der Schlüssel immer K = 1. Ein Generator einer kleinen Untergruppe ist ebenfalls unsicher. Wird p = 2q + 1 mit einer Primzahl q gewählt, lässt sich eine Primitivwurzel besonders einfach testen; zugleich kann die Wahl einer Primitivwurzel das DDH-Problem angreifbar machen. Eine Untergruppe von Primzahlordnung q gilt nach heutiger Auffassung als geeigneter.

Feste Gruppen und Primzahlen ermöglichen Vorberechnungen. Beim Zahlkörpersieb können die ersten drei von vier Schritten allein für das bekannte p durchgeführt und später wiederverwendet werden. Der Logjam-Angriff konnte dadurch nach einer einwöchigen Vorberechnung einen 512-Bit-DHM-Austausch in etwa 70 Sekunden brechen. Nach Schätzungen konnten mit Vorberechnungen für die zehn häufigsten 1024-Bit-Primzahlen 66 % der VPNs, 26 % der SSH-Server, 16 % der SMTP-Server und 24 % der HTTPS-Websites angegriffen werden.

ECDH, kurzlebige Schlüssel und IPsec

Beim Elliptic Curve Diffie-Hellman (ECDH) werden die Multiplikation und Exponentiation des ursprünglichen Verfahrens durch Punktaddition und Skalarmultiplikation auf elliptischen Kurven ersetzt. Eine elliptische Kurve hat beispielsweise die Form y² = x³ + ax + b mit 4a³ + 27b² ≠ 0. Sie enthält zusätzlich den Punkt im Unendlichen O. Aus zwei Punkten P und Q wird P + Q geometrisch durch eine Gerade, den dritten Schnittpunkt R und die Spiegelung an der x-Achse bestimmt. Das n-fache Addieren von P heißt nP.

Die Schwierigkeit, aus P und Q den Wert k mit Q = kP zu bestimmen, heißt ECDLP. Bei geeigneter Kurvenwahl wird dieses Problem als schwer angenommen. ECDH verwendet Kurven über endlichen Körpern wie GF(p) oder GF(2ⁿ). Der Vorteil sind bei gleicher Sicherheit kleinere Gruppen und dadurch kürzere Schlüssel, Signaturen und Rechenzeiten. Im Artikel wird als Vergleich genannt, dass 1.024 Bit bei klassischen DL-Verfahren ungefähr 200 Bit bei elliptischen Kurven entsprechen können; die Rechenzeitersparnis wird meist mit dem Faktor 10 angegeben.

Ephemeral Diffie-Hellman verwendet in TLS für jede Sitzung neue Parameter. Dadurch entsteht Forward Secrecy: Wird ein langfristiger Schlüssel später bekannt, lassen sich frühere Sitzungen nicht ohne Weiteres entschlüsseln. Beim statischen Diffie-Hellman werden dieselben, aus einem Public-Key-Zertifikat abgeleiteten Parameter wiederverwendet.

Für IPsec-IKE sind mehrere DH-Gruppen standardisiert. Beispiele sind Gruppe 1 mit 768 Bit, Gruppe 2 mit 1024 Bit, Gruppe 5 mit 1536 Bit, Gruppe 14 mit 2048 Bit, Gruppe 15 mit 3072 Bit, Gruppe 16 mit 4096 Bit sowie elliptische Gruppen 19 mit 256 Bit, 20 mit 384 Bit und 21 mit 521 Bit. Weitere Gruppen verwenden unter anderem brainpoolP256r1, brainpoolP384r1, brainpoolP512r1, Curve25519 und Curve448.