Diffie-Hellman-Schlüsselaustausch

Der Diffie-Hellman -Schlüsselaustausch ( DH -Schlüsselaustausch ) ^{[ Anm. 1 ]} ist ein mathematisches Verfahren zur sicheren Erzeugung eines symmetrischen kryptografischen Schlüssels über einen öffentlichen Kanal. Er war eines der ersten Protokolle , das von Ralph Merkle konzipiert und nach Whitfield Diffie und Martin Hellman benannt wurde . ^{[ 1 ]} DH ist eines der frühesten praktischen Beispiele für den Austausch öffentlicher Schlüssel im Bereich der Kryptographie. Die 1976 von Diffie und Hellman veröffentlichte Arbeit ist die erste öffentlich bekannte Veröffentlichung, die die Idee eines privaten Schlüssels und eines zugehörigen öffentlichen Schlüssels vorschlug.

Traditionell erforderte sichere verschlüsselte Kommunikation zwischen zwei Parteien den vorherigen Schlüsselaustausch über ein sicheres physisches Mittel, beispielsweise durch per Kurier transportierte Schlüssellisten auf Papier . Das Diffie-Hellman-Schlüsselaustauschverfahren ermöglicht es zwei Parteien, die einander nicht kennen, gemeinsam über einen unsicheren Kanal einen geheimen Schlüssel zu vereinbaren. Dieser Schlüssel kann dann zur Verschlüsselung nachfolgender Kommunikationen mit einem symmetrischen Verschlüsselungsverfahren verwendet werden .

Der Diffie-Hellman-Algorithmus wird zur Absicherung verschiedener Internetdienste eingesetzt . Eine im Oktober 2015 veröffentlichte Studie legt jedoch nahe, dass die damals für viele DH-Internetanwendungen verwendeten Parameter nicht ausreichten, um einen Angriff durch gut finanzierte Angreifer, wie beispielsweise die Sicherheitsdienste einiger Länder, zu verhindern. ^{[ 2 ]}

Das Schema wurde 1976 von Whitfield Diffie und Martin Hellman veröffentlicht ^{[ 3 ]} , doch 1997 wurde bekannt, dass James H. Ellis ^{[ 4 ]} , Clifford Cocks und Malcolm J. Williamson vom GCHQ , dem britischen Nachrichtendienst, bereits 1969 ^{[ 5 ]} gezeigt hatten , wie Public-Key-Kryptographie realisiert werden kann. ^{[ 6 ]}

Obwohl der Diffie-Hellman-Schlüsselaustausch selbst ein nicht authentifiziertes Schlüsselvereinbarungsprotokoll ist , bildet er die Grundlage für eine Vielzahl authentifizierter Protokolle und wird zur Gewährleistung der Vorwärtsgeheimhaltung in den ephemeren Modi von Transport Layer Security (TLS) (EDH oder DHE, abhängig von der verwendeten Verschlüsselungssuite) eingesetzt. Die Vorwärtsgeheimhaltung wird durch die Verwendung ephemerer Schlüssel erreicht: Die privaten Schlüssel werden nach Abschluss der Schlüsselvereinbarung verworfen und sind somit vor späterem Missbrauch geschützt. Ephemere Schlüssel sind praktisch, da die Erstellung von öffentlichen und privaten Schlüsselpaaren, die für den Diffie-Hellman-Austausch geeignet sind, rechentechnisch effizient ist.

Kurz darauf wurde diese Methode durch das RSA-Kryptosystem ergänzt , eine Implementierung der Public-Key-Kryptographie unter Verwendung asymmetrischer Algorithmen.

Das abgelaufene US-Patent 4200770 ^{[ 7 ]} aus dem Jahr 1977 beschreibt den mittlerweile gemeinfreien Algorithmus. Als Erfinder werden Hellman, Diffie und Merkle genannt.

Im Jahr 2006 schlug Hellman vor, den Algorithmus in Anerkennung von Ralph Merkles Beitrag zur Erfindung der Public-Key-Kryptographie Diffie-Hellman-Merkle-Schlüsselaustausch zu nennen (Hellman, 2006) und schrieb:

Das System ... ist seither als Diffie-Hellman-Schlüsselaustausch bekannt. Obwohl es erstmals in einer Arbeit von Diffie und mir beschrieben wurde, handelt es sich um ein Public-Key-System, ein von Merkle entwickeltes Konzept, und sollte daher, wenn es mit Namen in Verbindung gebracht werden soll, als „Diffie-Hellman-Merkle-Schlüsselaustausch“ bezeichnet werden. Ich hoffe, dieser kurze Beitrag kann dazu beitragen, Merkles gleichwertigen Beitrag zur Erfindung der Public-Key-Kryptographie zu würdigen. ^{[ 8 ]}

Der Diffie-Hellman-Schlüsselaustausch etabliert ein gemeinsames Geheimnis zwischen zwei Parteien, das für die verschlüsselte Kommunikation und den Datenaustausch über ein öffentliches Netzwerk verwendet werden kann. Eine Analogie veranschaulicht das Konzept des öffentlichen Schlüsselaustauschs, indem Farben anstelle sehr großer Zahlen verwendet werden:

Der Prozess beginnt damit, dass sich Alice und Bob öffentlich auf eine beliebige Ausgangsfarbe einigen, die nicht geheim gehalten werden muss. In diesem Beispiel ist es Gelb. Jeder wählt außerdem eine geheime Farbe – in diesem Fall Rot und Cyan. Der entscheidende Schritt ist, dass Alice und Bob jeweils ihre eigene geheime Farbe mit ihrer gemeinsamen Farbe mischen, wodurch orange-braune bzw. hellblaue Mischungen entstehen. Anschließend tauschen sie die beiden Mischungen öffentlich aus. Zum Schluss mischt jeder die vom Partner erhaltene Farbe mit seiner eigenen. Das Ergebnis ist eine endgültige Farbmischung (in diesem Fall Gelbbraun), die mit der endgültigen Farbmischung des Partners identisch ist.

Würde ein Dritter den Austausch mithören, wüsste er lediglich die gemeinsame Farbe (Gelb) und die ersten Mischfarben (Orange-Beige und Hellblau). Es wäre jedoch äußerst schwierig für ihn, die endgültige, geheime Farbe (Gelbbraun) zu ermitteln. Überträgt man die Analogie auf einen realen Austausch mit großen Zahlen anstelle von Farben, so ist diese Bestimmung rechenaufwändig; selbst für moderne Supercomputer ist sie in praktischer Zeit nicht durchführbar .

Die einfachste und ursprüngliche Implementierung ^{[ 3 ]} , später formalisiert als Finite-Field-Diffie-Hellman-Verfahren in RFC 7919 ^{[ 9 ]} , des Protokolls verwendet die multiplikative Gruppe der ganzen Zahlen modulo p , wobei p eine Primzahl und g eine primitive Wurzel modulo p ist . Um potenziellen Schwachstellen vorzubeugen, wird empfohlen, Primzahlen mit einer Länge von mindestens 2048 Bit zu verwenden. Dies erschwert es einem Angreifer, den diskreten Logarithmus zu berechnen und das gemeinsame Geheimnis zu kompromittieren. Diese beiden Werte werden so gewählt, dass das resultierende gemeinsame Geheimnis jeden Wert von 1 bis p − 1 annehmen kann . Hier ist ein Beispiel des Protokolls, wobei nicht-geheime Werte blau und geheime Werte rot dargestellt sind .

1. Alice und Bob einigen sich öffentlich darauf, einen Modulus p = 23 und eine Basis g = 5 (eine primitive Wurzel modulo 23) zu verwenden.
2. Alice wählt eine geheime ganze Zahl a = 4 und sendet dann an Bob A = g ^a mod p
   • A = 5 ⁴ mod 23 = 4 (In diesem Beispiel haben sowohl A als auch a den gleichen Wert 4, was aber normalerweise nicht der Fall ist)
3. Bob chooses a secret integer b = 3, then sends Alice B = g^b mod p
   • B = 5³ mod 23 = 10
4. Alice computes s = B^a mod p
   • s = 10⁴ mod 23 = 18
5. Bob computes s = A^b mod p
   • s = 4³ mod 23 = 18
6. Alice and Bob now share a secret (the number 18).

Both Alice and Bob have arrived at the same values because under mod p,

${\displaystyle {\color {Blue}A}^{\color {Red}{\boldsymbol {b}}}{\bmod {\color {Blue}p}}={\color {Blue}g}^{\color {Red}{\boldsymbol {ab}}}{\bmod {\color {Blue}p}}={\color {Blue}g}^{\color {Red}{\boldsymbol {ba}}}{\bmod {\color {Blue}p}}={\color {Blue}B}^{\color {Red}{\boldsymbol {a}}}{\bmod {\color {Blue}p}}}$

More specifically,

${\displaystyle ({\color {Blue}g}^{\color {Red}{\boldsymbol {a}}}{\bmod {\color {Blue}p}})^{\color {Red}{\boldsymbol {b}}}{\bmod {\color {Blue}p}}=({\color {Blue}g}^{\color {Red}{\boldsymbol {b}}}{\bmod {\color {Blue}p}})^{\color {Red}{\boldsymbol {a}}}{\bmod {\color {Blue}p}}}$

Only a and b are kept secret. All the other values – p, g, g^a mod p, and g^b mod p – are sent in the clear. The strength of the scheme comes from the fact that g^ab mod p = g^ba mod p take extremely long times to compute by any known classical algorithm just from the knowledge of p, g, g^a mod p, and g^b mod p. Such a function that is easy to compute but hard to invert is called a one-way function. Once Alice and Bob compute the shared secret they can use it as an encryption key, known only to them, for sending messages across the same open communications channel.

Of course, much larger values of a, b, and p would be needed to make this example secure, since there are only 23 possible results of n mod 23. However, if p is a prime of at least 600 digits, then even the fastest modern computers using the fastest known algorithm cannot find a given only g, p and g^a mod p. Such a problem is called the discrete logarithm problem.^[2] The computation of g^a mod p is known as modular exponentiation and can be done efficiently even for large numbers. Note that g need not be large at all, and in practice is usually a small integer (like 2, 3, ...).

Die folgende Grafik zeigt, wer was weiß, wobei nicht-geheime Werte blau und geheime Werte rot dargestellt sind . Eve ist hier eine Lauscherin – sie beobachtet die Kommunikation zwischen Alice und Bob, verändert aber nicht deren Inhalt.

• g , öffentliche (primitive) Basis, bekannt Alice, Bob und Eve. g = 5
• p , öffentlicher (primer) Modulus, bekannt Alice, Bob und Eve. p = 23
• a , Alices privater Schlüssel, der nur Alice bekannt ist. a = 6
• b , Bobs privater Schlüssel, der nur Bob bekannt ist. b = 15
• A , Alices öffentlicher Schlüssel, bekannt für Alice, Bob und Eve. A = g ^a mod p = 8
• B , Bobs öffentlicher Schlüssel, bekannt für Alice, Bob und Eve. B = g ^b mod p = 19

Nun ist s der gemeinsame geheime Schlüssel, der sowohl Alice als auch Bob bekannt ist, nicht aber Eve. Es ist für Eve nicht hilfreich, AB zu berechnen , da dies gleich g ^{a + b} mod p ist .

Hinweis: Es sollte für Alice schwierig sein, Bobs privaten Schlüssel zu ermitteln, oder für Bob, Alices privaten Schlüssel zu ermitteln. Wenn es für Alice nicht schwierig ist, Bobs privaten Schlüssel zu ermitteln (oder umgekehrt), kann eine Lauscherin, Eve , einfach ihr eigenes privates/öffentliches Schlüsselpaar verwenden, Bobs öffentlichen Schlüssel in ihren privaten Schlüssel einsetzen, einen gefälschten gemeinsamen geheimen Schlüssel erzeugen und Bobs privaten Schlüssel ermitteln (und diesen verwenden, um den gemeinsamen geheimen Schlüssel zu ermitteln). Eve könnte versuchen, ein öffentliches/privates Schlüsselpaar zu wählen, das es ihr leicht macht, Bobs privaten Schlüssel zu ermitteln.

Hier folgt eine allgemeinere Beschreibung des Protokolls: ^{[ 10 ]}

1. Alice und Bob einigen sich auf eine natürliche Zahl n und ein erzeugendes Element g in der endlichen zyklischen Gruppe G der Ordnung n . (Dies geschieht üblicherweise lange vor dem Rest des Protokolls; es wird vorausgesetzt, dass g und n allen Angreifern bekannt sind.) Die Gruppe G wird multiplikativ geschrieben.
2. Alice wählt eine zufällige natürliche Zahl a mit 1 < a < n und sendet das Element g ^a aus G an Bob.
3. Bob wählt eine zufällige natürliche Zahl b mit 1 < b < n und sendet das Element g ^b aus G an Alice.
4. Alice berechnet das Element ( g ^b ) ^a = g ^ba von G.
5. Bob berechnet das Element ( g ^a ) ^b = g ^ab von G.

Sowohl Alice als auch Bob besitzen nun das Gruppenelement g ab = g ba , das als gemeinsamer geheimer Schlüssel dienen kann. Die Gruppe G erfüllt die notwendige Bedingung für sichere Kommunikation, solange kein effizienter Algorithmus zur Bestimmung von g ab  aus g , g  a  und g b existiert .

Das Diffie-Hellman-Protokoll mit elliptischen Kurven ist beispielsweise eine Variante, die ein Element von G als Punkt auf einer elliptischen Kurve anstatt als ganze Zahl modulo n darstellt. Es wurden auch Varianten mit hyperelliptischen Kurven vorgeschlagen. Der Schlüsselaustausch mittels supersingulärer Isogenie ist eine Diffie-Hellman-Variante, die als sicher gegenüber Quantencomputern konzipiert wurde , aber im Juli 2022 geknackt wurde. ^{[ 11 ]}

Die verwendeten Schlüssel können entweder ephemer oder statisch (langfristig) sein, aber auch eine Mischung aus beidem, sogenannte semistatische DH-Schlüssel. Diese Varianten weisen unterschiedliche Eigenschaften und somit unterschiedliche Anwendungsfälle auf. Einen Überblick über viele Varianten sowie Erläuterungen dazu finden sich beispielsweise in NIST SP 800-56A. ^{[ 12 ]} Eine grundlegende Liste:

1. ephemeral, ephemeral: Wird üblicherweise für Schlüsselvereinbarungen verwendet. Bietet Vorwärtsgeheimhaltung , aber keine Authentizität .
2. statisch, statisch: Erzeugt ein langfristiges, gemeinsames Geheimnis. Bietet keine Vorwärtsgeheimhaltung, sondern implizite Authentizität. Da die Schlüssel statisch sind, schützt dies beispielsweise nicht vor Replay-Angriffen .
3. Ephemere, statische Verschlüsselung: Beispielsweise verwendet in der ElGamal-Verschlüsselung oder im Integrated Encryption Scheme (IES) . Bei Verwendung im Schlüsselaustausch kann implizite einseitige Authentizität gewährleistet werden (die ephemere Seite kann die Authentizität der statischen Seite überprüfen). Es wird keine Vorwärtsgeheimhaltung geboten.

Es ist möglich, in einem Schlüsselaustausch sowohl temporäre als auch statische Schlüssel zu verwenden, um mehr Sicherheit zu gewährleisten, wie beispielsweise in NIST SP 800-56A gezeigt. Es ist aber auch möglich, diese in einem einzigen DH-Schlüsselaustausch zu kombinieren, der dann als Triple-DH (3-DH) bezeichnet wird.

Im Jahr 1997 wurde von Simon Blake-Wilson, Don Johnson und Alfred Menezes eine Art dreifacher DH vorgeschlagen ^{[ 13 ]} , der 2005 von C. Kudla und KG Paterson verbessert wurde ^{[ 14 ]} und dessen Sicherheit nachgewiesen wurde.

Die langfristigen geheimen Schlüssel von Alice und Bob werden mit a bzw. b bezeichnet , die öffentlichen Schlüssel mit A und B sowie die temporären Schlüsselpaare ( x , X ) und ( y , Y ). Das Protokoll lautet dann:

Triple-Diffie-Hellman-(3-DH)-Protokoll

Alice ( ) ${\displaystyle A=g^{a}}$		Bob ( ) ${\displaystyle B=g^{b}}$
${\displaystyle X=g^{x}}$	${\displaystyle X\rightarrow {}}$
	${\displaystyle {}\leftarrow Y}$	${\displaystyle Y=g^{y}}$
${\displaystyle K=\operatorname {KDF} \left(Y^{x},\,B^{x},\,Y^{a},\,X,\,Y,\,A,\,B\right)}$		${\displaystyle K=\operatorname {KDF} \left(X^{y},\,X^{b},\,A^{y},\,X,\,Y,\,A,\,B\right)}$

Die langfristigen öffentlichen Schlüssel müssen auf irgendeine Weise übertragen werden. Dies kann vorab über einen separaten, vertrauenswürdigen Kanal erfolgen, oder die öffentlichen Schlüssel können mithilfe eines partiellen Schlüsselaustauschs verschlüsselt werden, um die Anonymität zu wahren. Weitere Details hierzu sowie zu anderen Verbesserungen wie Seitenkanalschutz oder expliziter Schlüsselbestätigung sowie frühen Nachrichten und zusätzlicher Passwortauthentifizierung finden sich beispielsweise im US-Patent „Advanced modular handshake for key agreement and optional authentication“ ^{[ 15 ] .}

X3DH wurde ursprünglich als Teil des Double-Ratchet-Algorithmus vorgeschlagen , der im Signal-Protokoll verwendet wird . Das Protokoll bietet Vorwärtsgeheimhaltung und kryptografische Abstreitbarkeit. Es operiert auf einer elliptischen Kurve. ^{[ 16 ]}

Das Protokoll verwendet fünf öffentliche Schlüssel. Alice besitzt einen Identitätsschlüssel IK_{_A} und einen temporären Schlüssel EK_{_A} . Bob besitzt einen Identitätsschlüssel IK_{_B} , einen signierten Vorab-Schlüssel SPK_{_B} und einen Einmal-Vorab-Schlüssel OPK_{_B} . ^{[ 16 ]} Bob veröffentlicht zunächst seine drei Schlüssel auf einem Server, den Alice herunterlädt und dessen Signatur sie überprüft. Anschließend initiiert Alice den Austausch mit Bob. ^{[ 16 ]} Der OPK ist optional. ^{[ 16 ]}

Die Diffie-Hellman-Schlüsselvereinbarung ist nicht auf die Aushandlung eines von nur zwei Teilnehmern geteilten Schlüssels beschränkt. Beliebig viele Benutzer können an einer Vereinbarung teilnehmen, indem sie das Vereinbarungsprotokoll iterativ anwenden und Zwischenergebnisse austauschen (die selbst nicht geheim gehalten werden müssen). Beispielsweise könnten Alice, Bob und Carol wie folgt an einer Diffie-Hellman-Vereinbarung teilnehmen, wobei alle Operationen modulo p erfolgen :

1. Die Parteien einigen sich auf die Algorithmusparameter p und g .
2. Die Parteien generieren ihre privaten Schlüssel, die a , b und c genannt werden .
3. Alice berechnet g ^a mod p und sendet es an Bob.
4. Bob berechnet ( g ^a ) ^b mod p = g ^ab mod p und sendet es an Carol.
5. Carol berechnet ( g ^ab ) ^c mod p = g ^abc mod p und verwendet es als ihr Geheimnis.
6. Bob berechnet g ^b mod p und sendet es an Carol.
7. Carol berechnet ( g ^b ) ^c mod p = g ^bc mod p und sendet es an Alice.
8. Alice berechnet ( g ^bc ) ^a mod p = g ^bca mod p = g ^abc mod p und verwendet es als ihr Geheimnis.
9. Carol berechnet g ^c mod p und sendet es an Alice.
10. Alice berechnet ( g ^c ) ^a mod p = g ^ca mod p und sendet es an Bob.
11. Bob berechnet ( g ^ca ) ^b mod p = g ^cab mod p = g ^abc mod p und verwendet es als sein Geheimnis.

Ein Lauscher konnte g ^a mod p , g ^b mod p , g ^c mod p , g ^ab mod p , g ^ac mod p und g ^bc mod p sehen , kann aber keine Kombination davon verwenden, um g ^abc mod p effizient zu reproduzieren .

Um diesen Mechanismus auf größere Gruppen auszuweiten, müssen zwei Grundprinzipien befolgt werden:

• Ausgehend von einem "leeren" Schlüssel, der nur aus g besteht , wird das Geheimnis erzeugt, indem der aktuelle Wert einmalig mit dem privaten Exponenten jedes Teilnehmers potenziert wird, und zwar in beliebiger Reihenfolge (die erste solche Exponentiation ergibt den eigenen öffentlichen Schlüssel des Teilnehmers).
• Jeder Zwischenwert (nach Anwendung von bis zu N − 1 Exponenten, wobei N die Anzahl der Gruppenmitglieder ist) darf öffentlich bekannt gegeben werden, der Endwert (nach Anwendung aller N Exponenten) stellt jedoch das gemeinsame Geheimnis dar und darf daher niemals öffentlich preisgegeben werden. Jeder Benutzer muss sich daher seine Kopie des Geheimnisses durch Anwendung seines eigenen privaten Schlüssels als Letzter sichern (andernfalls könnte der letzte Teilnehmer den endgültigen Schlüssel nicht an den Empfänger weitergeben, da er ihn in das Geheimnis verwandelt hätte, das die Gruppe schützen möchte).

Diese Prinzipien lassen verschiedene Möglichkeiten offen, die Reihenfolge der Beiträge der Teilnehmer zu den Schlüsseln festzulegen. Die einfachste und naheliegendste Lösung besteht darin, die N Teilnehmer kreisförmig anzuordnen und die N Schlüssel im Kreis rotieren zu lassen, bis schließlich jeder Schlüssel von allen N Teilnehmern bearbeitet wurde (bis hin zum jeweiligen Besitzer) und jeder Teilnehmer zu N Schlüsseln beigetragen hat (bis hin zu seinem eigenen). Dies erfordert jedoch, dass jeder Teilnehmer N modulare Exponentiationen durchführt.

Durch die Wahl einer günstigeren Reihenfolge und unter Ausnutzung der Tatsache, dass Schlüssel dupliziert werden können, ist es möglich, die Anzahl der von jedem Teilnehmer durchgeführten modularen Exponentiationen auf log ₂ ( N ) + 1 zu reduzieren , indem man einen Divide-and-Conquer- Ansatz verwendet, der hier für acht Teilnehmer angegeben wird:

1. Die Teilnehmer A, B, C und D führen jeweils eine Exponentiation durch und erhalten g ^abcd ; dieser Wert wird an E, F, G und H gesendet. Im Gegenzug erhalten die Teilnehmer A, B, C und D g ^efgh .
2. Die Teilnehmer A und B führen jeweils eine Exponentiation durch und erhalten g ^efghab , das sie an C und D senden, während C und D dasselbe tun und g ^efghcd erhalten , das sie an A und B senden.
3. Teilnehmer A führt eine Exponentiation durch und erhält g ^efghcda , das er an B sendet; analog sendet B g ^efghcdb an A. C und D verfahren analog.
4. Teilnehmer A führt eine letzte Exponentiation durch und erhält das Geheimnis g ^efghcdba = g ^abcdefgh , während B das Gleiche tut und g ^efghcdab = g ^abcdefgh erhält ; C und D verfahren wiederum ähnlich.
5. Die Teilnehmer E bis H führen gleichzeitig die gleichen Operationen durch, wobei sie g ^abcd als Ausgangspunkt verwenden.

Sobald diese Operation abgeschlossen ist, besitzen alle Teilnehmer das Geheimnis g ^abcdefgh , aber jeder Teilnehmer hat nur vier modulare Exponentiationen durchgeführt, anstatt der acht, die sich aus einer einfachen kreisförmigen Anordnung ergeben würden.

Das Protokoll gilt als abhörsicher, wenn G und g geeignet gewählt werden. Insbesondere muss die Ordnung der Gruppe G groß sein, vor allem wenn dieselbe Gruppe für große Datenmengen verwendet wird. Der Angreifer muss das Diffie-Hellman-Problem lösen, um g ^ab zu erhalten . Dies gilt derzeit für Gruppen mit ausreichend großer Ordnung als schwierig. Ein effizienter Algorithmus zur Lösung des Problems des diskreten Logarithmus würde die Berechnung von a oder b und damit die Lösung des Diffie-Hellman-Problems vereinfachen und somit dieses und viele andere Public-Key-Kryptosysteme unsicher machen. Körper kleiner Charakteristik könnten weniger sicher sein. ^{[ 17 ]}

Die Ordnung von G sollte einen großen Primfaktor besitzen, um die Verwendung des Pohlig-Hellman-Algorithmus zur Bestimmung von a oder b zu verhindern . Aus diesem Grund wird manchmal eine Sophie-Germain-Primzahl q zur Berechnung von p = 2q + 1 verwendet , die als sichere Primzahl bezeichnet wird , da die Ordnung von G dann nur durch 2 und q teilbar ist . Manchmal wird g so gewählt, dass es die Untergruppe der Ordnung q von G erzeugt , anstatt G selbst , sodass das Legendre-Symbol von ga ^niemals das niedrigstwertige Bit von a preisgibt . Ein Protokoll, das eine solche Wahl verwendet, ist beispielsweise IKEv2 . ^{[ 18 ]}

Der Generator g ist oft eine kleine ganze Zahl wie beispielsweise 2. Aufgrund der zufälligen Selbstreduzierbarkeit des diskreten Logarithmusproblems ist ein kleines g genauso sicher wie jeder andere Generator derselben Gruppe.

Wenn Alice und Bob Zufallszahlengeneratoren verwenden , deren Ausgaben nicht völlig zufällig sind und bis zu einem gewissen Grad vorhergesagt werden können, dann ist das Abhören viel einfacher.

In der ursprünglichen Beschreibung bietet der Diffie-Hellman-Schlüsselaustausch allein keine Authentifizierung der Kommunikationspartner und ist anfällig für Man-in-the-Middle-Angriffe . Mallory (eine aktive Angreiferin, die einen solchen Angriff durchführt) kann zwei separate Schlüsselaustausche einrichten, einen mit Alice und einen mit Bob. Dadurch gibt sie sich gegenüber Bob als Alice aus und umgekehrt. Dies ermöglicht es ihr, die zwischen ihnen ausgetauschten Nachrichten zu entschlüsseln und anschließend wieder zu verschlüsseln. Mallory muss von Anfang an in der Mitte der Kommunikation sein und diese Position beibehalten, indem sie bei jeder Kommunikation zwischen Alice und Bob aktiv Nachrichten entschlüsselt und wieder verschlüsselt. Tritt sie erst auf, nachdem die Schlüssel generiert wurden und die verschlüsselte Konversation zwischen Alice und Bob bereits begonnen hat, kann der Angriff nicht erfolgreich sein. Ist sie abwesend, wird ihre vorherige Anwesenheit Alice und Bob bekannt. Sie wissen dann, dass ihre gesamte private Kommunikation von jemandem im Kanal abgefangen und entschlüsselt wurde. In den meisten Fällen hilft ihnen dies nicht, Mallorys privaten Schlüssel zu erhalten, selbst wenn sie für beide Schlüsselaustausche denselben Schlüssel verwendet hat.

Um diese Art von Angriff zu verhindern, ist in der Regel ein Verfahren zur gegenseitigen Authentifizierung der Kommunikationspartner erforderlich. Varianten des Diffie-Hellman-Algorithmus, wie beispielsweise das STS-Protokoll , können stattdessen verwendet werden, um solche Angriffe zu vermeiden.

Eine 2021 veröffentlichte CVE ( CVE-2002-20001 ) deckte eine Denial-of-Service-Attacke (DoS) gegen Protokollvarianten mit ephemeren Schlüsseln auf, den sogenannten D(HE)at-Angriff. ^{[ 19 ]} Dieser Angriff nutzt aus, dass der Diffie-Hellman-Schlüsselaustausch es Angreifern ermöglicht, beliebige Zahlen zu senden, die keine öffentlichen Schlüssel sind. Dies löst auf Seiten des Opfers aufwändige modulare Exponentiationsberechnungen aus. Eine weitere CVEs-Veröffentlichung enthüllte, dass die Implementierungen des Diffie-Hellman-Schlüsselaustauschs lange private Exponenten verwenden können ( CVE-2022-40735 ), was die modularen Exponentiationsberechnungen unnötig aufwändig macht ^{[ 20 ]} , oder dass unnötigerweise der öffentliche Schlüssel eines Gegenübers überprüft werden muss ( CVE-2024-41996 ), was einen ähnlichen Ressourcenbedarf wie die Schlüsselberechnung mit einem langen Exponenten hat. ^{[ 21 ]} Ein Angreifer kann beide Schwachstellen gleichzeitig ausnutzen.

Der Zahlkörpersieb- Algorithmus, der sich im Allgemeinen als der effektivste zur Lösung des Problems des diskreten Logarithmus erwiesen hat , besteht aus vier Rechenschritten. Die ersten drei Schritte hängen lediglich von der Ordnung der Gruppe G ab, nicht von der spezifischen Zahl, deren endlicher Logarithmus gesucht wird. ^{[ 22 ]} Es hat sich herausgestellt, dass ein Großteil des Internetverkehrs eine der wenigen Gruppen mit einer Ordnung von 1024 Bit oder weniger verwendet. ^{[ 2 ]} Durch die Vorberechnung der ersten drei Schritte des Zahlkörpersiebs für die häufigsten Gruppen muss ein Angreifer nur noch den letzten Schritt ausführen, der deutlich weniger Rechenaufwand erfordert, um einen bestimmten Logarithmus zu erhalten. Der Logjam- Angriff nutzte diese Schwachstelle, um verschiedene Internetdienste zu kompromittieren, die die Verwendung von Gruppen mit einer Ordnung von 512-Bit-Primzahlen (sogenannte Export-Grade-Gruppen) erlaubten . Die Angreifer benötigten mehrere tausend CPU-Kerne für eine Woche, um die Daten für eine einzige 512-Bit-Primzahl vorzuberechnen. Nachdem dies erledigt war, konnten einzelne Logarithmen in etwa einer Minute mit zwei 18-Kern-Intel-Xeon-CPUs gelöst werden. ^{[ 2 ]}

Nach Schätzungen der Autoren des Logjam-Angriffs würden die deutlich aufwendigeren Vorberechnungen zur Lösung des diskreten Logarithmusproblems für eine 1024-Bit-Primzahl etwa 100 Millionen US-Dollar kosten – ein Betrag, der im Budget eines großen nationalen Geheimdienstes wie der US-amerikanischen National Security Agency (NSA) liegt. Die Logjam-Autoren vermuten, dass die Vorberechnungen gegen weit verbreitete 1024-Bit-DH-Primzahlen den Behauptungen in durchgesickerten NSA-Dokumenten zugrunde liegen, wonach die NSA in der Lage sei, einen Großteil der aktuellen Kryptographie zu knacken. ^{[ 2 ]}

Um diese Schwachstellen zu vermeiden, empfehlen die Autoren von Logjam die Verwendung von elliptischer Kurvenkryptographie , für die kein vergleichbarer Angriff bekannt ist. Alternativ empfehlen sie, dass die Ordnung p der Diffie-Hellman-Gruppe mindestens 2048 Bit betragen sollte. Sie schätzen, dass die Vorberechnung für eine 2048-Bit-Primzahl 10⁹-mal schwieriger ist ^als für 1024-Bit-Primzahlen. ^{[ 2 ]}

Quantencomputer können Public-Key-Verschlüsselungsverfahren wie RSA, Diffie-Hellman-Verfahren für endliche Körper und Diffie-Hellman-Verfahren für elliptische Kurven mithilfe von Shors Algorithmus zur Lösung des Faktorisierungsproblems , des Problems des diskreten Logarithmus und des Periodenbestimmungsproblems knacken. Eine postquantenmechanische Variante des Diffie-Hellman-Algorithmus wurde 2023 vorgeschlagen und basiert auf einer Kombination des quantenresistenten CRYSTALS-Kyber-Protokolls sowie des älteren elliptischen Kurvenprotokolls X25519 .

Es wurden Public-Key-Verschlüsselungsverfahren auf Basis des Diffie-Hellman-Schlüsselaustauschs vorgeschlagen. Das erste dieser Verfahren ist die ElGamal-Verschlüsselung . Eine modernere Variante ist das Integrierte Verschlüsselungsschema .

Protokolle, die Vorwärtsgeheimhaltung gewährleisten, erzeugen für jede Sitzung neue Schlüsselpaare und verwerfen diese am Ende der Sitzung. Der Diffie-Hellman-Schlüsselaustausch ist aufgrund seiner schnellen Schlüsselerzeugung eine häufig gewählte Methode für solche Protokolle.

Wenn Alice und Bob ein gemeinsames Passwort verwenden, können sie zum Schutz vor Man-in-the-Middle-Angriffen ein passwortauthentifiziertes Schlüsselaustauschverfahren (PK) nach dem Diffie-Hellman-Algorithmus nutzen. Ein einfaches Verfahren besteht darin, den Hashwert von „s“ mit dem Passwort zu vergleichen, der an beiden Enden des Kanals unabhängig berechnet wird. Ein Vorteil dieser Verfahren ist, dass ein Angreifer in jeder Iteration nur ein bestimmtes Passwort mit dem anderen Teilnehmer testen kann. Dadurch bietet das System auch mit relativ schwachen Passwörtern eine gute Sicherheit. Dieser Ansatz ist in der ITU-T- Empfehlung X.1035 beschrieben , die im G.hn- Heimnetzwerkstandard Anwendung findet.

Ein Beispiel für ein solches Protokoll ist das Secure Remote Password-Protokoll .

Es ist auch möglich, das Diffie-Hellman-Verfahren als Teil einer Public-Key-Infrastruktur (PKI) zu verwenden . Dadurch kann Bob eine Nachricht so verschlüsseln, dass nur Alice sie entschlüsseln kann. Vorher ist keine Kommunikation zwischen ihnen erforderlich, außer dass Bob Alices öffentlichen Schlüssel kennt. Alices öffentlicher Schlüssel ist . Um ihr eine Nachricht zu senden, wählt Bob ein zufälliges b und sendet Alice die unverschlüsselte Nachricht zusammen mit der mit dem symmetrischen Schlüssel verschlüsselten Nachricht . Nur Alice kann den symmetrischen Schlüssel bestimmen und somit die Nachricht entschlüsseln, da nur sie den privaten Schlüssel besitzt . Ein vorab vereinbarter öffentlicher Schlüssel verhindert außerdem Man-in-the-Middle-Angriffe. ${\displaystyle (g^{a}{\bmod {p}},g,p)}$${\displaystyle g^{b}{\bmod {p}}}$${\displaystyle (g^{a})^{b}{\bmod {p}}}$

In der Praxis wird das Diffie-Hellman-Verfahren nicht auf diese Weise eingesetzt; RSA ist der dominierende Public-Key-Algorithmus. Dies liegt vor allem an historischen und kommerziellen Gründen: RSA Security gründete eine Zertifizierungsstelle für die Schlüsselsignatur, aus der VeriSign hervorging. Wie bereits erläutert, kann das Diffie-Hellman-Verfahren nicht direkt zur Signierung von Zertifikaten verwendet werden. Die Signaturalgorithmen ElGamal und DSA sind jedoch mathematisch damit verwandt, ebenso wie MQV , STS und die IKE- Komponente der IPsec -Protokollfamilie zur Sicherung der Internetkommunikation .

• Diffie-Hellman- Schlüsselaustausch auf elliptischen Kurven
• Supersingulärer Isogenie-Schlüsselaustausch
• Vorwärtsgeheimhaltung
• Diffie-Hellman-Problem
• Modulare Exponentiation
• Denial-of-Service-Angriff
• Post-Quanten-Extended-Diffie-Hellman-Verfahren
• Akkumulator (Kryptographie)

• Gollman, Dieter (2011). Computersicherheit (2. Aufl.). West Sussex, England: John Wiley & Sons, Ltd. ISBN 978-0470741153Die
• Williamson, Malcolm J. (21. Januar 1974). Nicht-geheime Verschlüsselung mit einem endlichen Körper (PDF) (Technischer Bericht). Communications Electronics Security Group. Archiviert (PDF) vom Original am 23.03.2017 . Abgerufen am 22.03.2017 .
• Williamson, Malcolm J. (10. August 1976). Gedanken zur kostengünstigeren Verschlüsselung nicht-geheimer Daten (PDF) (Technischer Bericht). Communications Electronics Security Group. Archiviert (PDF) vom Original am 19. Juli 2004. Abgerufen am 25. August 2015 .
• Die Geschichte der nicht-geheimen Verschlüsselung JH Ellis 1987 (28K PDF-Datei) ( HTML-Version )
• Die ersten zehn Jahre der Public-Key-Kryptographie, Whitfield Diffie, Proceedings of the IEEE, Bd. 76, Nr. 5, Mai 1988, S. 560–577 (1,9 MB PDF-Datei)
• Menezes, Alfred ; van Oorschot, Paul ; Vanstone, Scott (1997). Handbuch der angewandten Kryptographie. Boca Raton, Florida: CRC Press. ISBN 0-8493-8523-7( Online verfügbar )
• Singh, Simon (1999) Das Codebuch: Die Entwicklung der Geheimhaltung von Maria Stuart bis zur Quantenkryptographie. New York: Doubleday. ISBN 0-385-49531-5
• Ein Überblick über die Public-Key-Kryptographie. Martin E. Hellman, IEEE Communications Magazine, Mai 2002, S. 42–49. (123 kB PDF-Datei)

• Oral-History-Interview mit Martin Hellman , Charles Babbage Institute , Universität von Minnesota. Der führende Kryptographie-Experte Martin Hellman erörtert die Umstände und grundlegenden Erkenntnisse seiner Erfindung der Public-Key-Kryptographie mit seinen Mitarbeitern Whitfield Diffie und Ralph Merkle an der Stanford University Mitte der 1970er Jahre.
• RFC  2631 – Diffie–Hellman-Schlüsselübereinstimmungsverfahren . E. Rescorla. Juni 1999.
• RFC  3526 – Weitere modulare exponentielle (MODP) Diffie-Hellman-Gruppen für den Internet-Schlüsselaustausch (IKE) . T. Kivinen, M. Kojo, SSH Communications Security. Mai 2003.