Diffie-Hellman/Sicherheit

Sicherheit

Diffie-Hellman-Problem

Computational-Diffie-Hellman-Problem (CDH)

Angenommen, die Lauscherin Eve erfährt an der unsicheren Leitung die Zahlen $p$, $g$, $A$ und $B$, aber nicht die diskreten Logarithmen $a$ von $A$ und $b$ von $B$ zur Basis $g$. Mit der Kenntnis von $a$ und $b$ wäre es für sie eine leichte Aufgabe, den Schlüssel $K=g^{ab}\ {\bmod {\ }}p$ zu bestimmen. Die Zahlen $a$ und $b$ herauszufinden ist jedoch sehr schwer, wenn die Zahlen $p$, $a$ und $b$ sehr groß sind, beispielsweise Zahlen mit mehreren hundert Stellen im Dezimalsystem. Aus dieser Problemstellung ergibt sich das Computational-Diffie-Hellman-Problem:

Wenn ein Element $g$ einer Gruppe und die Werte $A=g^{a}$ und $B=g^{b}$ gegeben sind, welchen Wert hat dann $K=g^{ab}$, mit $a,b$ unbekannt ?

Da dieses Problem in bestimmten Gruppen nur mit enormem Rechenaufwand zu lösen ist, kann ein Angreifer aus den beiden beim Diffie-Hellman-Merkle-Schlüsselaustausch übertragenen Nachrichten nicht den erzeugten Schlüssel berechnen.

Das Diffie-Hellman-Problem ist eng verwandt mit dem Diskreter-Logarithmus-Problem. Diskrete Logarithmen zu berechnen ist die einzige bekannte Methode, um das DHM-Verfahren zu brechen. Solange dies nicht in vertretbarer Zeit lösbar ist, ist es für einen Angreifer unmöglich, den geheimen Schlüssel zu bestimmen. Es ist allerdings nicht bewiesen, dass dies tatsächlich die einzige Methode ist, ob also jemand, der das Diffie-Hellman-Problem lösen könnte, auch diskrete Logarithmen effizient berechnen könnte. Ueli Maurer hat gezeigt, dass beide Probleme zumindest unter bestimmten Voraussetzungen äquivalent sind.

Decisional-Diffie-Hellman-Problem (DDH)

Soll es für einen Angreifer unmöglich sein, aus den öffentlich verfügbaren Informationen irgendwelche Informationen über den transportierten Schlüssel zu gewinnen, muss das Decisional-Diffie-Hellman-Problem (DDH) unangreifbar sein. Dieses Problem lässt sich folgendermaßen beschreiben:

Ein Angreifer erhält drei Zahlen: $A=g^{a}\ {\bmod {\ }}p$, $B=g^{b}\ {\bmod {\ }}p$ und $C=g^{c}\ {\bmod {\ }}p$. Dabei wurden entweder $a$, $b$ und $c$ zufällig und gleichverteilt in $\{0,...,p-2\}$ gewählt oder $c=ab\ {\bmod {\ }}p$ gesetzt. Im zweiten Fall heißt $(A,B,C)$ Diffie-Hellman-Tripel. Der Angreifer muss entscheiden, ob ein solches Tripel vorliegt oder nicht. Kann er das nicht, ist es ihm unmöglich, aus $g^{a}$ und $g^{b}$ Rückschlüsse auf $g^{ab}$ zu ziehen.

Das Problem besteht also darin, bei gegebenem $g^{a}\ {\bmod {\ }}p$, $g^{b}\ {\bmod {\ }}p$ und $g^{c}\ {\bmod {\ }}p$ zu entscheiden, ob $g^{c}=g^{ab}$ ist.

Wer das Computational-Diffie-Hellman-Problem lösen kann, ist offensichtlich auch dazu in der Lage, das Decisional-Diffie-Hellman-Problem zu lösen. Für den umgekehrten Fall ist das nicht klar.

Bei einer Auswahl von $g$ als Primitivwurzel kann das Decisional-Diffie-Hellman-Problem angegriffen werden. Dies liegt in folgendem Theorem begründet:

Sei $p$ eine Primzahl, sei $g$ eine Primitivwurzel modulo $p$ und seien $a,b\in \{0,...,p-2\}$. Dann ist $g^{ab}$ genau dann ein quadratischer Rest modulo $p$, wenn $g^{a}$ oder $g^{b}$ ein quadratischer Rest ist modulo $p$.

Das Theorem folgt daraus, dass eine Potenz von $g$ genau dann ein quadratischer Rest modulo $p$ ist, wenn der Exponent gerade ist.

Ein Angreifer kann also prüfen, ob das Kriterium aus diesem Theorem erfüllt ist. Er kann zwar nicht immer entscheiden, ob ein Diffie-Hellman-Tripel vorliegt, er antwortet aber zu 75 % richtig. Sein Vorteil gegenüber reinem Raten beträgt also 50 %.

Wahl der öffentlichen Zahlen

DHM-Primzahl p

Die Sicherheit des Verfahrens basiert nicht zuletzt auf der Länge der gewählten Zahlen. So muss die Primzahl $p$ dermaßen gewählt werden, dass diskrete Logarithmen modulo $p$ mit derzeit bekannten Methoden nicht (effizient genug) berechnet werden können. Je größer die verwendete Primzahl, desto sicherer das Verfahren, aber auch desto aufwendiger. Das Bundesamt für Sicherheit in der Informationstechnik empfiehlt im Fall eines Einsatzzeitraum[s] über das Jahr 2022 hinaus für $p$ eine Schlüssellänge von mindestens 3000 Bit (Stand 2017).

Die DHM-Primzahl $p$ muss zudem so gewählt werden, dass Algorithmen zur Berechnung des diskreten Logarithmus kein leichtes Spiel haben. So muss beispielsweise vermieden werden, dass $p-1$ nur kleine Primfaktoren hat. Ansonsten kann nämlich der Pohlig-Hellman-Algorithmus angewendet werden, der nicht von der Gruppenordnung, sondern vom größten Faktor der Gruppenordnung abhängt. Außerdem sollte $p$ für das Zahlkörpersieb möglichst ungeeignet sein. Dies ist der Fall, wenn es ein irreduzibles Polynom vom Grad 5 gibt, das sehr kleine Koeffizienten und eine Nullstelle ${\bmod {\ }}p$ hat.

„Generator“ g

Die Zahl $g$ sollte so gewählt werden, dass alle Zahlen zwischen $1$ und $p-1$ als Resultat der modularen Potenz $g^{a}\ {\bmod {\ }}p$ in Frage kommen. Erst dann ist es zu aufwändig, alle Zahlen durchzuprobieren (wenn darüber hinaus die Primzahl $p$ groß genug gewählt worden ist). Diese Eigenschaft erfüllt die Zahl $g$, wenn sie ein Primitivwurzel zum Modul $p$ ist, d. h. ein Erzeuger der Gruppe $\mathbb {Z} _{p}^{*}$. Wenn Alice und Bob beispielsweise $g=1$ wählen, so funktioniert das Verfahren zwar noch immer, doch der Schlüssel $K$ ist auf jeden Fall $1$, denn $1$ ist genau der Generator der Untergruppe von $\mathbb {Z} _{p}^{*}$ mit einem Element. Ähnlich unsicher ist das Verfahren, wenn Alice und Bob für $g$ einen Generator einer anderen kleinen Untergruppe wählen. Bei einem Generator einer großen Untergruppe ist das Verfahren sicherer, am besten wird ein Generator der ganzen Gruppe gewählt.

Wie im Abschnitt „Prime Restklassengruppe und Primitivwurzel“ gezeigt, lässt sich eine Primitivwurzel relativ leicht finden, wenn man die DHM-Primzahl als $p=2\times q+1$ mit einer Primzahl $q$ wählt. Wie jedoch im vorherigen Abschnitt gezeigt, kann das Decisional-Diffie-Hellman-Problem angegriffen werden, wenn man $g$ als Primitivwurzel wählt.

Verwendung fester Gruppen und Primzahlen

Da die Erzeugung sicherer Primzahlen rechenaufwendig ist, verwenden viele Implementierungen eine feste Primzahl $p$. Einige Netzwerkprotokolle wie etwa Internet Key Exchange geben eine Liste von möglichen Gruppen und deren Primzahl vor.

Die Verwendung fester Gruppen und Primzahlen kann ein Angreifer ausnutzen, um einen Großteil der Berechnung zum Brechen des diskreten Logarithmus vorab durchzuführen und um mehrere Ziele gleichzeitig anzugreifen. Der Zahlkörpersieb-Algorithmus besteht aus vier Schritten, wobei die ersten drei Schritte lediglich die Primzahl $p$ benötigen. Ist $p$ bekannt, kann ein Angreifer somit den Großteil vorberechnen und die Ergebnisse für jeden auf $p$ basierenden Schlüsselaustausch wiederverwenden. Dadurch kann zum Beispiel der Logjam-Angriff in TLS, nach einer einwöchigen Vorberechnung, einen 512-Bit-DHM-Schlüsselaustausch in rund 70 Sekunden brechen.

Nach Schätzungen eines Forscherteams kann ein Angreifer mit Vorberechnung der 10 häufigsten 1024-Bit-Primzahlen den Netzwerkverkehr von 66 % der VPNs, 26 % der SSH-Server, 16 % der SMTP-Server und 24 % der HTTPS-Websites im Internet entschlüsseln. Die Forscher schätzen, dass der Rechenaufwand zum Brechen von 1024-Bit-Diffie-Hellman von einem staatlichen Angreifer wie der National Security Agency aufgebracht werden kann.

Man-in-the-Middle-Angriff

Der Diffie-Hellman-Merkle-Schlüsselaustausch ist nicht mehr sicher, wenn der Angreifer bei einem Man-in-the-Middle-Angriff Datenpakete verändern kann. Im Alice-und-Bob-Modell heißt ein solcher Angreifer, der aktiv in das Geschehen eingreifen kann, Mallory (von engl. malicious, dt. i. e. hinterhältig, heimtückisch). Mallory fängt bei einem Man-in-the-Middle-Angriff die von Alice und Bob gesendeten Nachrichten ab und sendet stattdessen jeweils seine eigene Nachricht

$Z=g^{z}\mod p$

weiter, die er aus einer beliebigen Zahl $z$ und den öffentlich bekannten Zahlen $g$ und $p$ berechnet.

Nach dem Schlüsselaustausch besitzen die beiden Kommunikationspartner Alice und Bob unterschiedliche Schlüssel $K_{A}$ und $K_{B}$. Im Prinzip wurde zweimal ein DHM-Schlüsselaustausch durchgeführt: einmal zwischen Alice und Angreifer Mallory und einmal zwischen Mallory und Bob. Dabei erlangt Mallory Kenntnis der beiden Schlüssel $K_{A}$ und $K_{B}$.

$K_{A}=Z^{a}{\bmod {p}}=(g^{z})^{a}{\bmod {p}}=(g^{a})^{z}{\bmod {p}}=A^{z}{\bmod {p}}$

$K_{B}=Z^{b}{\bmod {p}}=(g^{z})^{b}{\bmod {p}}=(g^{b})^{z}{\bmod {p}}=B^{z}{\bmod {p}}$

Da Alice und Bob im weiteren Verlauf davon ausgehen, mit dem jeweils Anderen zu kommunizieren, kann Mallory die folgende symmetrisch verschlüsselte Kommunikation abhören. Diese leitet er dazu weiterhin über sich selbst um. Daten von Alice entschlüsselt Mallory mit $K_{A}$ und verschlüsselt sie wieder mit $K_{B}$, bevor er sie an Bob weiterschickt. Dabei kann Mallory den Nachrichteninhalt sowohl lesen als auch unbemerkt verändern. Die gleiche Vorgehensweise wendet er auch für die Gegenrichtung an.

Um einen solchen Man-in-the-Middle-Angriff auszuschließen, müssen die ausgetauschten Nachrichten authentifiziert werden. Dazu wird ein Informationsvorsprung benötigt, der über einen authentifizierten Kanal erreicht wird.

Seitenkanalangriffe

Ein Seitenkanalangriff bezeichnet eine kryptoanalytische Methode, die die physische Implementierung eines Kryptosystems in einem Gerät (z. B. einer Chipkarte, eines Security-Tokens oder eines Hardware-Sicherheitsmoduls) oder in einer Software ausnutzt. Dabei wird nicht das kryptographische Verfahren selbst, sondern nur eine bestimmte Implementierung angegriffen. Das Prinzip beruht darauf, ein kryptographisches Gerät bei der Ausführung der kryptologischen Algorithmen zu beobachten und Korrelationen zwischen den beobachteten Daten und dem verwendeten Schlüssel zu finden.

Zeitangriff

Im Jahr 1995 veröffentlichte Paul Kocher eine neuartige Methode, mit der es ihm gelang, Implementierungen von Diffie-Hellman, RSA und DSA zu brechen: der Zeitangriff (timing attack).

Ziel des Zeitangriffs ist die diskrete Exponentialfunktion. Wenn eine Krypto-Implementierung $g^{a}\ {\bmod {\ }}p$ für irgendwelche größeren Zahlen $g$, $a$ und $p$ berechnet, dann geschieht dies fast immer mit dem Square-and-Multiply-Algorithmus. Bei diesem ist für jedes Bit von $a$ eine Aktion festgesetzt: Hat das gerade bearbeitete Bit den Wert $1$, dann ist diese Aktion eine Multiplikation, ansonsten eine Quadrierung. Da die Rechenzeiten für die Multiplikationen länger dauern als für die Quadrierungen, kann Eve aus Zeitmessungen Rückschlüsse auf die Zahl der Einsen in $a$ ziehen. Variiert er die Zahl $g$, reichen irgendwann die Informationen aus, um $a$ zu berechnen. Schon mit einigen Tausend Zeitmessungen lassen sich entsprechende Implementierungen mit 1024-Bit-Schlüsseln brechen.

Um solche Zeitangriffe zu verhindern, müssen jedoch bei der Implementierung lediglich Verzögerungen in den Ver- bzw.  Entschlüsselungsprozess eingebaut werden. Mit dem als Blinding genannten Verfahren wird zum Beispiel an einer Stelle des Verfahrens eine Zufallszahl eingerechnet, die an anderer Stelle wieder herausgerechnet wird. Eine andere Möglichkeit besteht darin, den Prozess so zu gestalten, dass er unabhängig vom Eingabewert immer gleich lange dauert.

Stromangriff

Bei einem Stromangriff misst ein Oszilloskop den Stromverbrauch eines Verfahrens.

Im Jahr 1998 stellten Paul Kocher, Joshua Jaffe und Benjamin Jun erstmals das Konzept des Stromangriffs vor. Bei Stromangriffen wird nicht nur die Verarbeitungszeit gemessen, sondern mit einem Oszilloskop auch der Stromverbrauch. Besonders Smartcards sind gegenüber Stromangriffen anfällig, da diese auf eine externe Stromversorgung angewiesen sind. Ein Angreifer misst die Ver- und Entschlüsselungsvorgänge und versucht bestimmte Stellen der Stromverbrauchskurve einzelnen Bestandteilen des Verfahrens zuzuordnen. Auch hier ist der Square-and-Multiply-Algorithmus ein geeignetes Ziel, da sich bei diesem Multiplikationen und Quadrierungen am Stromverbrauch oft gut unterscheiden lassen. Stromangriffe sind etwas aufwendiger in der Durchführung als Zeitangriffe, gelten jedoch als wirkungsvoller.

Als Gegenmaßnahme gegen Stromangriffe kann der Hersteller von Krypto-Modulen den Stromverbrauch verschleiern, indem er Dummy-Operationen in einen Ver- bzw.  Entschlüsselungsvorgang einbaut. Eine weitere Möglichkeit besteht darin, ein künstliches Stromrauschen zu erzeugen, das den eigentlichen Stromverbrauch überlagert.