elikaski/ecc_attacksBekannte Angriffe auf die Elliptische-Kurven-Kryptografie
In den letzten Jahren ist die Kryptografie mit elliptischen Kurven aufgrund ihrer hohen Effizienz und starken Sicherheit beliebt geworden. Der Zweck dieses Artikels ist es, dieses Thema auf eine relativ klarere Weise darzustellen, als es heute im Internet existiert.
In diesem Artikel werde ich vorstellen, was elliptische Kurven sind, die grundlegenden Operationen, die auf ihnen ausgeführt werden können, und wie sie im kryptografischen Kontext verwendet werden können. Der Großteil dieses Artikels besteht aus Beispielen bekannter Angriffe auf fehlerhafte Implementierungen oder falsche Verwendungen. Im gesamten Artikel versuche ich, die Erklärung in einen intuitiven und allgemeinen Teil sowie einen mathematischen Teil, der ins Detail geht, zu trennen. Der Leser ist eingeladen, sich auf den Teil zu konzentrieren, der ihn an der jeweiligen Stelle interessiert, und die Teile zu überspringen, die weniger relevant sind.
Viel Spaß beim Lesen!
Im Allgemeinen ist eine elliptische Kurve eine Art gekrümmte Linie. Ein Beispiel dafür ist die Parabel, deren Gleichung die Form $𝑦 = 𝑎𝑥^2 + 𝑏𝑥 + 𝑐$ hat und so aussieht:
Im Kontext der Kryptografie ist es üblich, elliptische Kurven zu verwenden, deren Gleichung die Form
$𝑦^2 = 𝑥^3 + 𝑎𝑥 + 𝑏$
hat. Beispielsweise sieht eine elliptische Kurve, die zur Gleichung $𝑦^2 = 𝑥^3 − 3𝑥 + 3$ gehört, so aus:
Die Gleichung der Kurve definiert die Beziehung zwischen der 𝑥-Koordinate eines Punktes auf der Kurve und seiner 𝑦-Koordinate. In einem kryptografischen Kontext beschränken wir 𝑥, 𝑦, 𝑎, 𝑏 auf ganze Zahlen und beschränken die Berechnungen auf modulo einer großen Primzahl. Die Gleichung der elliptischen Kurve lautet also:
$𝑦^2 = 𝑥^3 + 𝑎𝑥 + 𝑏\ \ \ \ (mod\ 𝑝)$.
Das bedeutet, dass wir eine endliche Anzahl von Punkten auf der Kurve haben. In mathematischer Sprache wird die Kurve als über einem endlichen Körper der Ordnung 𝑝 definiert bezeichnet. Daher hat nicht unbedingt jede 𝑥-Koordinate einen entsprechenden Punkt auf der Kurve, weil die zugehörige 𝑦-Koordinate möglicherweise keine ganze Zahl ist.
Die Menge der Punkte auf der Kurve besteht aus Paaren ganzer Zahlen (𝑥, 𝑦), die die Gleichung der Kurve erfüllen. Zusätzlich zu diesen Punkten wird ein weiterer spezieller Punkt namens „Unendlich“ definiert, der mit 𝒪 bezeichnet wird. In mathematischer Sprache ist dieser Punkt das neutrale Element der Menge der Punkte auf der Kurve bezüglich der Additionsoperation, die wir im nächsten Abschnitt definieren werden. Die Anzahl der Punkte auf der Kurve (einschließlich des Punktes 𝒪) wird als „Ordnung der Kurve“ bezeichnet.
Eine weitere Beobachtung ist, dass elliptische Kurven symmetrisch zur X-Achse sind. Das bedeutet, dass wenn der Punkt 𝑃 = (𝑥, 𝑦) auf der Kurve liegt, dann liegt auch der Punkt −𝑃 = (𝑥, −𝑦) auf der Kurve. Tatsächlich werden diese Punkte als „inverse“ zueinander betrachtet (daher die Bezeichnung −𝑃 für den zweiten Punkt), und das Ergebnis der Additionsoperation zwischen ihnen ist als das neutrale Element 𝒪 definiert.
Ein Satz namens Satz von Hasse liefert eine Abschätzung für #𝐸, die Ordnung der Kurve, und ist von der Größenordnung Θ(𝑝). Genauer gilt:
$𝑝 + 1 − 2\sqrt𝑝 ≤ 𝐸 ≤ 𝑝 + 1 + 2\sqrt𝑝$
Wenn zwei Punkte auf der Kurve gegeben sind, kann zwischen ihnen eine Additionsoperation definiert werden, die zu einem dritten Punkt führt, der ebenfalls auf der Kurve liegt. Um diesen Punkt geometrisch zu finden, zeichnen wir eine Linie zwischen den beiden gegebenen Punkten und verlängern sie, bis sie die Kurve in einem dritten Punkt schneidet. Dieser Punkt wird in Bezug auf die 𝑋-Achse gespiegelt, und der resultierende Punkt ist als das Ergebnis der Addition definiert.
Hier ist ein Diagramm, das zeigt, wie bei gegebenen Punkten 𝑃 und 𝑄 der Punkt 𝑃 + 𝑄 gefunden werden kann:
Eine Frage, die sich aus dieser Beschreibung ergeben könnte, ist: Was passiert, wenn die Linie, die zwischen den beiden Punkten gezeichnet wird, die Kurve nicht erneut schneidet? In diesem Fall sagt man, dass die Linie die Kurve im „Unendlichen“ schneidet, und das Ergebnis der Addition ist der Punkt 𝒪. Beachte, dass dieser Fall eintritt, wenn die gezeichnete Linie vertikal ist, das heißt, wir versuchen, einen Punkt 𝑃 mit seinem inversen Punkt −𝑃 zu addieren:
Daraus ergeben sich zwei grundlegende Identitäten. Für jeden Punkt 𝑃 gilt:
𝑃 + 𝒪 = 𝑃
𝑃 + (−𝑃) = 𝒪
Eine weitere Frage, die sich aus der geometrischen Beschreibung ergibt, ist: Wie addieren wir einen Punkt zu sich selbst? Wir haben gesehen, dass wir, um zwei verschiedene Punkte 𝑃 und 𝑄 zu addieren, eine Linie zwischen ihnen zeichnen und den Schnittpunkt ihrer Verlängerung mit der Kurve betrachten. Intuitiv lassen wir 𝑃 konstant und betrachten die Linie, die entsteht, wenn wir 𝑄 „näher und näher“ an 𝑃 heranbewegen, bis 𝑄 mit 𝑃 verschmilzt. Was wir erhalten, ist eine Linie, die immer stärker „tangential“ zur Kurve im Punkt 𝑃 ist, und genau diese Linie betrachten wir, wenn wir 𝑃 zu sich selbst addieren wollen:
Um einen Punkt 𝑃 zu sich selbst zu addieren, zeichnen wir eine Tangente an die Kurve im Punkt 𝑃 und verlängern sie, bis sie die Kurve in einem zweiten Punkt schneidet. Dieser Punkt wird in Bezug auf die 𝑋-Achse gespiegelt, und der resultierende Punkt ist als das Ergebnis der Addition definiert. Es ist üblich, das Ergebnis der Addition als 𝑃 + 𝑃 = 2𝑃 zu bezeichnen. Wenn die Tangente die Kurve nicht in einem zweiten Punkt schneidet, sagt man wiederum, dass sie die Kurve im „Unendlichen“ schneidet, und das Ergebnis der Addition ist in diesem Fall der Punkt 𝒪.
Diese visuellen geometrischen Beschreibungen veranschaulichen die Funktionsweise der Punkteaddition gut und helfen uns, sie zu verstehen. Aber wie berechnen wir sie tatsächlich? Natürlich mit mathematischen Gleichungen!
Gegeben seien die Punkte $𝑃 = (𝑥_𝑃, 𝑦_𝑃)$ und $𝑄 = (𝑥_𝑄, 𝑦_𝑄)$. Das Ergebnis ihrer Addition ist der Punkt $𝑅 = (𝑥_𝑅, 𝑦_𝑅)$ mit:
$𝑥_𝑅 = 𝜆^2 − 𝑥_𝑃 − 𝑥_𝑄\ \ \ \ \ \ \ \ \ (mod\ 𝑝)$
$𝑦_𝑅 = 𝜆(𝑥_𝑃 − 𝑥_𝑅) − 𝑦_𝑃\ \ \ \ (mod\ 𝑝)$
Wobei 𝜆 als die Steigung der die Punkte verbindenden Linie definiert ist, wenn sie verschieden sind, und als die Steigung der Tangente an die Kurve im Punkt, wenn der Punkt zu sich selbst addiert wird. Formal:
$\displaystyle𝜆 = \frac{𝑦_𝑃 − 𝑦_𝑄}{𝑥_𝑃 − 𝑥_𝑄}\ \ \ \ \ (mod\ 𝑝)\ \ \ ;\ \ \ 𝑖𝑓 𝑃 ≠ 𝑄$
$\displaystyle𝜆 = \frac{3{𝑥_𝑃}^2 + 𝑎}{2𝑦_𝑃}\ \ \ \ (mod\ 𝑝)\ \ \ ;\ \ \ 𝑖𝑓 𝑃 = 𝑄$
Die mathematischen Berechnungen hinter der Punkteaddition sind für den Rest des Artikels nicht entscheidend. Dafür können wir die Punkteaddition als eine Blackbox betrachten, die zwei Punkte auf der Kurve erhält und einen dritten Punkt zurückgibt, der ebenfalls auf der Kurve liegt.
Wir haben gesehen, dass es möglich ist, einen Punkt 𝑃 zu sich selbst zu addieren, und wir haben den resultierenden Punkt mit 2𝑃 bezeichnet. Wenn wir den Punkt 𝑃 erneut zu diesem Ergebnis addieren, erreichen wir einen Punkt, der mit 3𝑃 bezeichnet wird, und so weiter. Auf diese Weise lässt sich die „Multiplikation“ eines Punktes mit einer Konstanten definieren, indem der Punkt wiederholt zu sich selbst addiert wird (ähnlich der Multiplikation zwischen Zahlen):
$𝑛𝑃 = 𝑃 + 𝑃 + ⋯ + 𝑃\ \ \ \ \ (n\ mal)$
Anscheinend müssen wir, um einen Punkt mit einer Zahl 𝑛 zu multiplizieren, 𝑛 Additionsoperationen zwischen Punkten durchführen. Das liegt daran, dass es bei einem gegebenen Startpunkt schwierig ist, im Voraus zu wissen, wo der „letzte“ Punkt landen wird, ohne ihn „Schritt für Schritt“ zu erreichen. Eine solche Berechnung wäre sehr ineffizient, da 𝑛 sehr groß sein könnte.
Zu diesem Zweck gibt es den Algorithmus Double And Add, bei dem wir vom Punkt 𝑃 ausgehen und dann für jedes Bit in der binären Darstellung von 𝑛 den aktuellen Punkt mit 2 multiplizieren (das heißt, er wird zu sich selbst addiert) und zum Ergebnis addieren, wenn der Bitwert 1 ist. Die Laufzeitkomplexität dieses Algorithmus ist 𝑂(log 𝑛), und er ermöglicht es, Punkte effizient mit sehr großen Zahlen zu multiplizieren.
Eine wichtige Eigenschaft der Punktmultiplikation, die wir später verwenden werden, ist, dass für jeden Punkt 𝑃 und jedes Zahlenpaar 𝑎, 𝑏 gilt:
$𝑏(𝑎𝑃) = (𝑏𝑎)𝑃 = (𝑎𝑏)𝑃 = 𝑎(𝑏𝑃)$
Intuitiv: Angenommen, wir starten vom Punkt 𝑃, machen 𝑎 Schritte von ihm aus und erreichen den Punkt 𝑎𝑃. Von diesem Punkt aus machen wir 𝑏 Schritte der „Größe“ 𝑎 und erreichen den Punkt 𝑏(𝑎𝑃). Alternativ könnten wir in einem anderen Szenario vom Punkt 𝑃 starten, 𝑏 Schritte mit ihm machen und den Punkt 𝑏𝑃 erreichen. Von diesem Punkt aus machen wir 𝑎 Schritte der „Größe“ 𝑏 und erreichen den Punkt 𝑎(𝑏𝑃).
In beiden Szenarien haben wir insgesamt die gleiche Anzahl von 𝑎𝑏 Schritten vom Punkt 𝑃 aus gemacht, also haben wir in beiden Szenarien denselben Endpunkt erreicht. Mathematisch gesehen ist die Multiplikation eines Punktes mit einer Konstanten assoziativ.
Wenn wir von einem Punkt 𝑃 ausgehen und ihn immer wieder zu sich selbst addieren, werden wir bei jedem solchen Schritt einen neuen Punkt auf der Kurve erreichen. Da es nur endlich viele Punkte auf der Kurve gibt, werden wir irgendwann wieder Punkte erreichen, die wir bereits erreicht haben, und wir befinden uns in einer Art Schleife oder einem „Kreis“. Genauer gesagt erreichen wir irgendwann den Punkt -𝑃, im nächsten Schritt den Punkt 𝒪 und im darauf folgenden Schritt wieder den Punkt 𝑃, von dem wir ausgegangen sind.
Der Punkt, der einen solchen „Kreis“ erzeugt, wird Generator genannt, weil der gesamte „Kreis“ aus ihm erzeugt werden kann, und es ist üblich, ihn mit dem Buchstaben 𝐺 zu bezeichnen. Die Anzahl der Punkte im „Kreis“ (einschließlich des Punktes 𝒪) wird als „Ordnung des Generators 𝐺“ bezeichnet und üblicherweise mit 𝑛 abgekürzt. Jeder Punkt auf der Kurve bildet eine Art „Kreis“. Mathematisch gesehen ist die Menge der Punkte auf diesem „Kreis“ eine zyklische Gruppe.
Eine interessante Eigenschaft, die sich daraus ergibt, ist, dass die Multiplikation eines Punktes 𝐺 mit seiner Ordnung 𝑛 den Punkt im Unendlichen ergibt:
𝑛𝐺 = 𝒪
„Gegeben seien Punkte 𝑃 und 𝑄 mit 𝑄 = 𝑥𝑃 für ein 𝑥; es ist schwer, 𝑥 zu finden.“
In Worten: Angenommen, jemand startet von einem bestimmten Startpunkt, macht eine bestimmte Anzahl von Schritten von ihm aus und erreicht einen Endpunkt. Wenn der Startpunkt und der Endpunkt gegeben sind, wie können wir wissen, wie viele Schritte er gemacht hat?
Die Antwort auf diese Frage ist nicht so intuitiv, denn es ist schwierig, im Voraus vorherzusagen, welche Punkte von einem Startpunkt aus durch Schritte erreicht werden. Eine naive Lösung wäre, selbst von 𝑃 zu starten, Schritt für Schritt vorwärts zu gehen und die Schritte zu zählen, bis wir 𝑄 erreichen. Die Komplexität dieser Lösung ist 𝑂(𝑥), und sie ist undurchführbar, wenn bekannt ist, dass 𝑥 eine große Zahl ist, zum Beispiel wenn 𝑥 256 Bit groß ist.
Dieses Problem wird als Problem des diskreten Logarithmus auf elliptischen Kurven (ECDLP) bezeichnet, und es ist ein schweres Problem. Aber wie schwer ist es?
In einem kryptografischen Kontext ist es üblich, die „Schwierigkeit von Problemen“ oder die „Stärke eines kryptografischen Systems“ mit einer Metrik namens Security Level zu messen. Bei dieser Metrik sagt man, dass ein Problem „𝑛 Bit Sicherheit“ hat, wenn der beste bekannte Angriff das Problem in $𝑂(2^𝑛)$ Schritten löst.
Derzeit löst der beste Algorithmus, der das ECDLP-Problem löst, dieses mit einer Komplexität von $𝑂(\sqrt n)$, wobei 𝑛 die Ordnung des Punktes 𝑃 ist, und zwar mithilfe eines Meet-In-The-Middle-Angriffs. Wenn ein Punkt mit einer ausreichend großen Ordnung gewählt wird, ist das Lösen undurchführbar, daher die Stärke des Problems.
Wenn wir zum Beispiel 𝑛 mit einer Größe von 256 Bit wählen, erhalten wir, dass das ECDLP-Problem eine Sicherheitsstufe von 128 Bit Sicherheit hat. Zum Vergleich: Um dieselbe Sicherheitsstufe von 128 Bit Sicherheit in der RSA-Verschlüsselung zu erreichen, die auf dem Problem der ganzzahligen Faktorisierung basiert, ist ein öffentlicher Schlüssel mit einer Größe von 3072 Bit erforderlich. Das macht die Verwendung elliptischer Kurven rechnerisch relativ effizienter.
Nach all dieser Einführung in die Welt der elliptischen Kurven werden wir uns ansehen, was man mit ihnen in einem kryptografischen Kontext machen kann. Wie wir wissen, basieren kryptografische Systeme üblicherweise auf einem „schweren Problem“, das schwer zu lösen ist. Zum Beispiel RSA mit dem von uns erwähnten Problem der Faktorisierung einer Zahl oder das Diffie-Hellman-Protokoll mit dem Problem des diskreten Logarithmus. Ein kryptografisches System, das auf dem ECDLP-Problem auf einer elliptischen Kurve basiert, gehört zur Familie der Elliptic Curve Cryptography, kurz ECC.
Beginnen wir mit einer Geschichte. Stellen Sie sich vor, Sie sind auf einer Party – ein Raum voller Menschen, in dem jeder mit jedem sprechen kann und jeder jeden hört. In diesem Raum sind auch Alice und Bob, die sich noch nie zuvor getroffen haben. Alice mag Bob und möchte ihn zu einem Date einladen. Alice ist ein wenig schüchtern, also möchte sie Bob diese geheime Nachricht sagen, ohne dass die anderen Partygäste sie hören. Alice und Bob haben vorher nichts abgestimmt, und alles, was Alice Bob sagt, wird von allen anderen Gästen auf der Party gehört. Wie kann Alice Bob die Nachricht übermitteln, ohne dass jemand anderes sie hört?
Wenn Sie mit „elliptischen Kurven“ geantwortet haben, dann haben Sie recht!
Alice wählt eine elliptische Kurve und einen Generator darin aus und teilt sie Bob mit. Konkret übergibt Alice Bob (und allen anderen im Raum) die beiden Kurvenparameter 𝑎, 𝑏, den Modulus 𝑝 und den Generator 𝐺. Zusätzlich wählt Alice einen Wert $𝑑_𝐴$ im Bereich $1 ≤ 𝑑_𝐴 ≤ 𝑛 − 1$, wobei 𝑛 die Ordnung von 𝐺 ist. Der Wert $𝑑_𝐴$ wird als Alices privater Schlüssel bezeichnet. Alice berechnet den Punkt $𝐴 = 𝑑_𝐴𝐺$, der als Alices öffentlicher Schlüssel bezeichnet wird, und teilt ihn Bob mit. Ebenso wählt Bob einen privaten Schlüssel $𝑑_𝐵$, berechnet den Punkt $𝐵 = 𝑑_𝐵𝐺$, der als Bobs öffentlicher Schlüssel bezeichnet wird, und teilt ihn Alice mit.
Alice nimmt Bobs öffentlichen Schlüssel, multipliziert diesen Punkt mit ihrem privaten Schlüssel und erreicht einen dritten Punkt $𝑃_𝐴 = 𝑑_𝐴𝐵$. Ebenso nimmt Bob Alices öffentlichen Schlüssel, multipliziert ihn mit seinem privaten Schlüssel und erreicht einen eigenen dritten Punkt $𝑃_𝐵 = 𝑑_𝐵𝐴$. Wenn wir die Punkte, die Alice und Bob getrennt erreicht haben, untersuchen, stellen wir fest, dass sie denselben Punkt erreicht haben! Diese Tatsache ergibt sich aus der Assoziativitätseigenschaft der Multiplikation eines Punktes mit einer Konstanten, die wir zuvor gesehen haben:
$𝑃_𝐴 = 𝑑_𝐴𝐵 = 𝑑_𝐴(𝑑_𝐵𝐺) = 𝑑_𝐵(𝑑_𝐴𝐺) = 𝑑_𝐵𝐴 = 𝑃_𝐵$
Am Ende des gesamten Prozesses haben Alice und Bob eine Übereinkunft über einen Punkt auf der Kurve erzielt, und in keiner Phase hat einer von ihnen diesen Punkt der anderen Person übermittelt. Die Informationen, die alle gehört haben, sind: 𝑎, 𝑏, 𝑝, 𝐺, 𝐴, 𝐵. Eine Person im Raum, die diese Informationen hört, kann den Punkt, auf den sich Alice und Bob geeinigt haben, nicht daraus ermitteln.
Das liegt daran, dass eine andere Person im Raum, die diesen Punkt finden wollte, entweder Alices privaten Schlüssel oder Bobs privaten Schlüssel kennen müsste, um 𝐵 oder 𝐴 damit zu multiplizieren. Um zum Beispiel Alices privaten Schlüssel zu finden, würde sie $𝐴 = 𝑑_𝐴𝐺$ betrachten, denn dies ist die einzige gesendete Information, die Alices privaten Schlüssel „enthält“. Bei gegebenem 𝐺 und $𝑑_𝐴𝐺$ ist das Finden von $𝑑_𝐴$ äquivalent zum Lösen des Problems des diskreten Logarithmus auf elliptischen Kurven, was, wie erwähnt, ein schweres Problem ist.
Dieses schöne Protokoll heißt: Elliptic Curve Diffie-Hellman (ECDH).
Wir sind noch nicht am Ende unserer Geschichte. Obwohl Alice und Bob sich auf einen gemeinsamen geheimen Punkt geeinigt haben, hat Alice Bob immer noch nicht zu dem Date eingeladen, das sie sich so sehr wünschte.
Nachdem sich die Parteien auf einen gemeinsamen geheimen Punkt geeinigt haben, können sie ihn als Verschlüsselungsschlüssel für jede Verschlüsselungsmethode verwenden, zum Beispiel AES, und von diesem Punkt an sicher über Verschlüsselung kommunizieren.
Es ist üblich, eine der 𝑥- oder 𝑦-Koordinaten des Punktes zu nehmen und zu verwenden. Um die Sicherheit zu wahren, wird empfohlen, den ausgewählten Wert zu hashen und nur das Hash-Ergebnis als Verschlüsselungsschlüssel zu verwenden. In der Praxis ist der Wert manchmal zu groß, um als Verschlüsselungsschlüssel verwendet zu werden. Wenn beispielsweise die verwendete Hashfunktion SHA-1 ist, beträgt ihre Ausgabelänge 160 Bit, während die AES-Verschlüsselung nur 128 Bit benötigt. In einem solchen Fall ist es üblich, nur 128 Bits von den 160 zu verwenden und den Rest zu verwerfen.
Wie auch immer, an diesem Punkt einigen sich Alice und Bob auf einen Verschlüsselungsschlüssel, und sie sind die Einzigen, die ihn kennen. Von diesem Punkt an kommunizieren sie über Verschlüsselung, und jeder, der im Raum mithört, kann nicht verstehen, was sie sagen.
Hier ist ein Diagramm des Protokolls:
Mit dem vereinbarten Schlüssel verschlüsselt Alice die Nachricht „Hey Bob, würdest du morgen Abend mit mir einen Kaffee trinken gehen?“ und übergibt die verschlüsselte Nachricht an Bob. Bob entschlüsselt die Nachricht mit dem Schlüssel, den auch er kennt. Alice hofft, dass Bob Ja sagt, aber das ist nicht Teil des Protokolls.
Im bekannten Diffie-Hellman-Protokoll (DH) übertragen die Parteien offen eine Primzahl 𝑝 und einen Generator 𝑔, der sich in der Gruppe befindet, die dem Wert 𝑝 entspricht. Alice erzeugt zufällig einen privaten Schlüssel 𝑎 und sendet offen ihren öffentlichen Schlüssel $𝐴 = 𝑔^𝑎\ \ \ \ (mod\ 𝑝)$. Ebenso erzeugt Bob zufällig einen privaten Schlüssel 𝑏 und sendet offen seinen öffentlichen Schlüssel $𝐵 = 𝑔^𝑏\ \ \ \ (mod\ 𝑝)$. Alice nimmt dann Bobs öffentlichen Schlüssel und potenziert ihn mit ihrem privaten Schlüssel, wodurch sie den Wert $𝐾 = 𝐵^𝑎 = (𝑔^𝑏)^𝑎 =𝑔^{𝑎𝑏}\ \ \ \ (mod\ 𝑝)$ berechnet. Auf die gleiche Weise berechnet Bob den Wert $𝐾 = 𝐴^𝑏 = (𝑔^𝑎)^𝑏 =𝑔^{𝑎𝑏}\ \ \ \ (mod\ 𝑝)$. Am Ende des Prozesses konnten Alice und Bob sich auf einen gemeinsamen Wert 𝐾 einigen, ohne ihn zwischen sich zu übertragen.
Ein Angreifer, der ihnen zuhört, kann 𝐾 bei den gesendeten Werten 𝑝, 𝑔, 𝐴, 𝐵 nicht finden. Dazu müsste er entweder Alices oder Bobs privaten Schlüssel finden. Um zum Beispiel Alices privaten Schlüssel zu berechnen, müsste er 𝑎 bei gegebenem 𝑔 und $𝑔^𝑎\ \ \ \ (mod\ 𝑝)$ finden, was ein schweres Problem ist. Dieses Problem wird als Problem des diskreten Logarithmus (DLP) bezeichnet.
Es gibt eine sehr deutliche Ähnlichkeit zwischen DH, das auf DLP basiert, und ECDH, das auf ECDLP basiert (sie sind im Grunde dasselbe, nur mit einem EC-Präfix). In beiden Protokollen können zwei miteinander sprechende Parteien einen gemeinsamen geheimen Wert vereinbaren, ohne dass sie vorher etwas abstimmen. Jeder, der die Nachrichten zwischen den Parteien mithört, wird die öffentlichen Informationen sehen, die sie zwischen sich austauschen, aber er wird nicht in der Lage sein, den geheimen Wert zu ermitteln, den sie gemeinsam haben.### Zweite Verwendung elliptischer Kurven – Signieren einer Nachricht
Um unsere Geschichte fortzusetzen, nehmen wir an, dass Alice und Bob sich zu ihrem Date trafen und einen schönen Abend miteinander verbrachten. Am nächsten Tag erhält Alice eine Nachricht mit dem Inhalt: „Hi Alice, hier ist Bob, ich hatte gestern eine tolle Zeit mit dir und würde dich gerne am Wochenende wiedersehen." Alice vermutet, dass nicht Bob die Nachricht gesendet hat, denn sie weiß, dass Bob gestern so viel Spaß mit ihr hatte, dass er nicht bis zum Wochenende warten wird, um sie zu treffen, sondern sie schon morgen treffen möchte! Wie kann Alice überprüfen, dass wirklich Bob die Nachricht geschrieben hat?
Wenn du mit „elliptische Kurven" geantwortet hast, liegst du schon wieder richtig!
Die Schwierigkeit des ECDLP-Problems kann auch zum Signieren von Nachrichten genutzt werden. Während ihres Dates einigten sich Alice und Bob auf eine elliptische Kurve und einen Generator 𝐺 darin. Bob erzeugte einen Wert $𝑑_𝐵$, genannt Bobs privater Schlüssel, und berechnete den Punkt $𝑃_𝐵 = 𝑑_𝐵𝐺$, genannt Bobs öffentlicher Schlüssel. Bob gab Alice seinen öffentlichen Schlüssel, damit sie damit später überprüfen kann, ob eine Nachricht, die sie erhält, tatsächlich von ihm signiert wurde.
Angenommen, Bob möchte eine bestimmte Nachricht 𝑚 signieren. Er berechnet den Wert $z = hash(m)$ mithilfe einer sicheren Hashfunktion und behält eine Anzahl von Bits aus dem Ergebnis, die der Bitlänge von n, der Ordnung des Generators 𝐺, entspricht. Bob erzeugt einen zufälligen Wert 𝑘 im Bereich $1 ≤ 𝑘 ≤ 𝑛 − 1$. Bob berechnet dann den Punkt $𝑘𝐺 = (𝑥_1, 𝑦_1)$, nimmt dessen 𝑥-Koordinate und berechnet $𝑟 = 𝑥1\ \ \ \ (mod\ n)$. Schließlich berechnet Bob den Wert $𝑠 = 𝑘^{−1}(𝑧 + 𝑟𝑑_𝐵)$.
Die Signatur der Nachricht 𝑚 ist definiert als das Paar der berechneten Werte 𝑟 und 𝑠.
Angenommen, Alice erhält eine bestimmte Nachricht 𝑚, und deren Signatur besteht aus einem Paar von Werten 𝑟 und 𝑠. Alice möchte sichergehen, dass tatsächlich Bob die Nachricht signiert hat. Alice berechnet den Wert $z = hash(m)$ auf dieselbe Weise wie Bob. Anschließend berechnet Alice die Werte $𝑢_1 = 𝑧𝑠^{−1}$ und $𝑢_2 = 𝑟𝑠^{−1}$. Schließlich verwendet Alice Bobs öffentlichen Schlüssel $𝑃_𝐵$ und berechnet den Punkt $𝑢_1𝐺 + 𝑢_2𝑃_𝐵 = (𝑥_1, 𝑦_1)$. Die Signatur wird als gültig betrachtet, wenn gilt $𝑟 ≡ 𝑥_1\ \ \ \ (mod\ n)$. Der Grund, warum dies korrekt ist, liegt darin, dass gilt:
$𝑢_1𝐺 + 𝑢_2𝑃_𝐵 = 𝑧𝑠^{−1}𝐺 + 𝑟𝑠^{−1}𝑃_𝐵 = 𝑠^{−1}(𝑧𝐺 + 𝑟𝑃_𝐵) = 𝑠^{−1}(𝑧𝐺 + 𝑟𝑑_𝐵𝐺) = 𝑠^{−1}(𝑧 + 𝑟𝑑_𝐵)𝐺 = 𝑘(𝑧 + 𝑟𝑑_𝐵)^{−1}(𝑧 + 𝑟𝑑_𝐵)𝐺 = 𝑘𝐺$
Wenn die Signatur gültig ist, sollte die 𝑥-Koordinate dieses Punktes tatsächlich 𝑟 sein, wie sie in der Nachrichtensignatur definiert ist. Es sei angemerkt, dass die Ordnung des Generators 𝐺, die mit dem Buchstaben 𝑛 bezeichnet wird, eine Primzahl sein sollte. Dies ist notwendig, damit die inversen Zahlen in den Signatur- und Verifikationsalgorithmen tatsächlich berechnet werden können.
Man kann sehen, dass nur die Person, die den privaten Schlüssel $𝑑_𝐵$ besitzt, eine gültige Signatur für den öffentlichen Schlüssel $𝑃_𝐵$ erzeugen kann. Ein Angreifer, der den Wert $𝑑_𝐵$ nicht besitzt, kann den Wert 𝑠, der zu $𝑃_𝐵$ in der Signatur gehört, nicht berechnen. Wenn der Angreifer eine Signatur erzeugen möchte, die zu einer bestimmten Nachricht passt, muss er das ECDLP-Problem lösen, also den privaten Schlüssel $𝑑_𝐵$ bei gegebenem $𝐺$ und $𝑃_𝐵 = 𝑑_𝐵𝐺$ finden, was ein schweres Problem ist.
Dieses Signaturprotokoll wird als Elliptic Curve Digital Signature Algorithm bezeichnet, kurz ECDSA. Das Protokoll stellt sicher, dass die signierten Nachrichten nicht verändert oder gefälscht wurden, und stellt außerdem sicher, dass die Person, die die Nachricht signiert hat, nicht abstreiten kann, sie erstellt zu haben.
Anders als beim ECDH-Protokoll, bei dem die Parteien vorab nichts abstimmen mussten, müssen die Parteien beim ECDSA-Protokoll vorab einen öffentlichen Schlüssel vereinbaren. Erst wenn jede Partei sicher weiß, dass der von ihr gehaltene öffentliche Schlüssel tatsächlich der Person gehört, mit der sie kommunizieren möchte, kann das Protokoll verwendet werden. Andernfalls ergibt die Überprüfung der Signatur mit dem öffentlichen Schlüssel, den jede Partei besitzt, keinen Sinn.
Zurück zu unserer Geschichte. Alice weiß sicher, dass der öffentliche Schlüssel $𝑃_𝐵$ in ihrem Besitz tatsächlich Bob gehört, weil Bob ihn ihr bei ihrem Date ausdrücklich gegeben hat. Alice versucht, die Nachricht damit zu verifizieren, und stellt fest, dass es keine Übereinstimmung gibt. Natürlich! Jemand anderes hat die Nachricht erstellt und signiert, genau wie Alice vermutet hatte.
Hier ist ein Diagramm des Protokolls:
Im ElGamal-Protokoll zum Signieren von Nachrichten einigen sich die Parteien auf eine große Primzahl 𝑝 und eine Generatorzahl 𝑔. Die signierende Partei erzeugt einen Wert 𝑑 im Bereich $1 ≤ 𝑑 < 𝑝 − 1$, den sogenannten privaten Schlüssel, berechnet den Wert $𝑦 = 𝑔^𝑑\ \ \ \ (mod\ p)$, den sogenannten öffentlichen Schlüssel, und veröffentlicht ihn.
Um eine bestimmte Nachricht zu signieren, berechnen sie den Wert $z = hash(m)$ und erzeugen einen zufälligen Wert 𝑘 im Bereich $1 ≤ 𝑘 < 𝑝 − 1$, der teilerfremd zu $(p-1)$ ist. Sie berechnen $𝑟 = 𝑔^𝑘\ \ \ \ (mod\ p)$ und $𝑠 = 𝑘^{−1}(𝑧 − 𝑑𝑟)\ \ \ \ (mod\ (p-1))$. Die Signatur der Nachricht m ist definiert als das Paar der berechneten Werte 𝑟 und 𝑠.
Die Partei, die eine bestimmte Nachricht 𝑚 erhalten hat, deren Signatur aus einem Paar von Werten 𝑟 und 𝑠 besteht, verwendet den öffentlichen Schlüssel 𝑦, um die Signatur zu überprüfen, indem sie die Werte $𝑢_1 = 𝑟^𝑠𝑦^𝑟$ und $𝑢_2 = 𝑔^𝑧$ berechnet. Die Signatur wird als gültig betrachtet, wenn $𝑢_1 = 𝑢_2$. Dies liegt daran, dass gemäß der Definition von 𝑠 gilt:
$𝑠 = 𝑘^{−1}(𝑧 − 𝑑𝑟)$, also $𝑘𝑠 = 𝑧 − 𝑑𝑟$, daher $𝑧 = 𝑘𝑠 + 𝑑𝑟$. Somit:
$𝑢_2 = 𝑔^𝑧 = 𝑔^{𝑘𝑠+𝑑𝑟} = 𝑔^{𝑘𝑠}𝑔^{𝑑𝑟} = (𝑔^𝑘)^𝑠(𝑔^𝑑)^𝑟 = 𝑟^𝑠𝑦^𝑟 = 𝑢_1$
Ein Angreifer kann ohne Kenntnis des privaten Schlüssels 𝑑 keine gültige Signatur für den öffentlichen Schlüssel 𝑦 erzeugen. Um aus dem öffentlichen Schlüssel den privaten Schlüssel zu erhalten, müsste der Angreifer das DLP-Problem lösen, was ein schwieriges Problem ist.
Auch hier gibt es eine deutliche Ähnlichkeit zwischen ECDSA, das auf ECDLP basiert, und ElGamal, das auf DLP basiert. In beiden Fällen müssen die Parteien vorab einen öffentlichen Schlüssel abstimmen, und es ist erforderlich, jedes Mal, wenn wir eine neue Nachricht signieren möchten, einen zufälligen Wert 𝑘 zu erzeugen. Auch in beiden Fällen kann ein Angreifer, der die Nachrichten zwischen den Parteien abhört, keine nützlichen Informationen ableiten, die es ihm ermöglichen würden, Signaturen zu fälschen.
Wir haben gesehen, wie elliptische Kurven in kryptografischen Systemen verwendet werden können, um einen geheimen Wert zu vereinbaren und Nachrichten zu signieren. Wie bei allem im Leben laufen die Dinge nicht immer wie geplant, wenn es darum geht, etwas in die Praxis umzusetzen. Im weiteren Verlauf dieses Artikels stelle ich verschiedene Möglichkeiten vor, auf ECC basierende kryptografische Systeme anzugreifen, die vom Benutzer falsch verwendet oder auf unsichere Weise implementiert wurden.
Natürlich habe ich diesen Teil in Angriffe auf ECDH und Angriffe auf ECDSA unterteilt. In beiden Fällen sagen wir, wir sind bei dem Angriff „erfolgreich", wenn wir den privaten Schlüssel einer der Parteien finden, und wir hören dann auf. Im Fall von ECDH reicht das aus, denn mit dem privaten Schlüssel kann man zum gemeinsamen geheimen Wert und all den Informationen gelangen, die später damit verschlüsselt werden. Im Fall von ECDSA reicht das ebenfalls aus, da der private Schlüssel verwendet werden kann, um Nachrichten nach Belieben zu signieren.
SageMath ist eine freie und quelloffene mathematische Software. Sie kann in fast derselben Syntax wie Python geschrieben und auch als Python-Bibliothek verwendet werden. Diese Bibliothek implementiert nützliche Funktionen, die für elliptische Kurven relevant sind, und ist daher sehr nützlich für die Berechnungen, die wir im Zusammenhang mit ECC durchführen müssen. Im Rahmen dieses Artikels stelle ich Codeausschnitte bereit, die mit dieser Bibliothek geschrieben sind. Ich habe festgestellt, dass die Installation am einfachsten auf dem Ubuntu-Betriebssystem, insbesondere Version 22.04, ist. Zur Installation genügt es, den folgenden Befehl auszuführen: sudo apt install sagemath.
Um eine Datei mit Code auszuführen, speichere die Datei mit der Erweiterung .sage und führe den Befehl sage file.sage aus.
Zusätzlich kann ein Interpreter verwendet werden, ähnlich dem Python-Interpreter, indem man den Befehl sage ausführt. Es ist auch möglich, .py-Dateien zu erstellen, in denen die Bibliothek sage.all importiert wird, und sie mit dem Befehl python3 file.py auszuführen. Beachte, dass beim Ausführen einer Datei mit dem Befehl sage die Schreibweise ^ als Potenz interpretiert wird, während sie bei der Ausführung mit python3 als xor interpretiert wird.
In diesem Artikel verwende ich hauptsächlich die folgenden Funktionen in SageMath:
E.gens() - Finden von Generatoren in der Kurve EG.order() - Berechnen der Ordnung des Generators Gn*G -Multiplikation des Generators G mit der Zahl nn.factor() - Faktorisieren der Zahl n in ihre Faktoren - die Funktion gibt eine Liste von Paaren (𝑝, 𝑒) zurück, sodass 𝑝 ein Primfaktor und 𝑒 sein Exponent ist, d.h. die Anzahl, wie oft 𝑝 in der Zerlegung von n vorkommtcrt - Lösen eines Gleichungssystems des chinesischen Restsatzes```python
import random
p = random_prime(2^32)
a = random.randrange(p)
b = random.randrange(p)
E = EllipticCurve(GF(p), [a,b])
G = E.gens()[0]
n = G.order()
private_key = random.randrange(n)
A = private_key * G
found_key = G.discrete_log(A)
assert found_key * G == A
assert private_key == found_key
print("success!")In diesem Codeausschnitt wählen wir die Parameter für die Kurve zufällig unter der Einschränkung, dass `𝑝` 32 Bit lang ist. Diese Einschränkung garantiert uns, dass die Anzahl der Punkte auf der Kurve $O(2^{32})$ beträgt und daher auch die Ordnung jedes Punktes auf ihr höchstens $O(2^{32})$ ist. Danach erstellen wir die Kurve, wählen einen Generator in ihr, erzeugen einen zufälligen privaten Schlüssel und berechnen den öffentlichen Schlüssel. Schließlich berechnen wir aus dem Generator und dem öffentlichen Schlüssel den diskreten Logarithmus, um den privaten Schlüssel zu finden, und verifizieren, dass der gefundene Schlüssel tatsächlich korrekt ist. Dieser Code benötigt höchstens ein paar Sekunden, um den privaten Schlüssel zu finden.
## Die Ordnung des Generators ist eine glatte Zahl
Wie bereits erwähnt, ist die Ordnung eines Generators definiert als die Anzahl der Punkte im "Kreis", der entsteht, wenn wir den Generatorpunkt immer wieder zu sich selbst addieren, und sie wird mit `𝑛` bezeichnet. Wenn `𝑛` eine zusammengesetzte Zahl ist, die in kleinere Primfaktoren zerlegt werden kann, dann ist es möglich, das ECDLP effizient zu lösen. Eine solche Zahl wird als glatte Zahl (Smooth Number) bezeichnet, und für die Zwecke dieses Artikels ist es eine Zahl, die in ausreichend viele Primfaktoren zerlegt werden kann, von denen jeder klein genug ist, damit unser Angriff funktioniert. Die formale Definition einer glatten Zahl ist etwas anders und für uns nicht relevant.
Intuitiv geschieht dies, indem jeder der Primfaktoren separat "angegriffen" wird. Gegeben seien ein Generatorpunkt `𝐺`, der einen sehr großen "Kreis" bildet, und ein Punkt `𝑃` im "Kreis", sodass `𝑃 = 𝑘𝐺`. Der große "Kreis" kann in mehrere kleine "Kreise" zerlegt werden, deren jeder die Größe eines Primfaktors von `𝑛` hat. In jedem kleinen "Kreis" können wir `G` und `P` auf andere entsprechende Punkte `G'` und `P'` abbilden, die sich im kleinen "Kreis" befinden und `𝑃′ = 𝑘′𝐺′` erfüllen. Da der "Kreis" klein ist, ist es relativ einfach, das Problem zu lösen und `𝑘′` zu finden. Schließlich können wir alle kleinen `𝑘′`, die wir gefunden haben, im ursprünglichen "Kreis" zu dem gewünschten `𝑘` kombinieren.
Der Algorithmus, der das von mir Beschriebene ausführt, wird Pohlig-Hellman-Algorithmus genannt. Seine Laufzeitkomplexität beträgt $O(\sqrt{p_{max}})$, wobei $p_{max}$ der größte Primfaktor bei der Zerlegung von `𝑛` ist. Das leuchtet auch ein, denn der "schwerste" Teil des Algorithmus ist das Lösen des ECDLP-Problems im größten "Kreis" unter den kleineren "Kreisen". Zum Beispiel könnte `n` eine 128-Bit-Zahl sein, die sich in Primfaktoren zerlegt, von denen der größte eine 30-Bit-Zahl ist. Der Algorithmus reduziert die Komplexität der Lösung des Problems von $2^{64}$ auf $2^{15}$, wodurch es von undurchführbar zu durchführbar wird.
Glücklicherweise implementiert die Funktion `discrete_log` von SageMath diesen Algorithmus. Um den Angriff auszuführen, kann man die Funktion einfach aufrufen:```python
p = 183740305291166889900894879302858411333
a = 13
b = 37
E = EllipticCurve(GF(p), [a,b])
G = E(123764810000715262449972298016641419881,
144640915410606177233842123838934486566)
n = G.order()
print("number of bits in n:", n.nbits())
print("n's factors:", n.factor())
print("number of bits in n's greatest factor:", n.factor()[-1][0].nbits())
import random
private_key = random.randrange(n)
A = private_key * G
print("Calculating discrete_log...")
found_key = G.discrete_log(A)
assert found_key * G == A
assert private_key == found_key
print("success!")
In diesem Codeausschnitt definieren wir eine elliptische Kurve und einen Generator darin und geben die Primfaktoren ihrer Ordnung aus. Die Ausgabe ist:``` number of bits in n: 128 n's factors: 2 * 3 * 13 * 101 * 211 * 21141581 * 38581057 * 60652309 * 2234328781 number of bits in n's greatest factor: 32 Calculating discrete_log... success!
Man kann sehen, dass die Ordnung des Generators zwar 128 Bit lang ist, sie sich aber in Primfaktoren zerlegen lässt, sodass der größte Primfaktor 32 Bit beträgt.
Danach wählen wir – genau wie beim vorherigen Angriff – einen zufälligen privaten Schlüssel, berechnen daraus einen öffentlichen Schlüssel, und berechnen dann anhand des Generators und des öffentlichen Schlüssels den privaten Schlüssel und verifizieren, dass er korrekt ist.
Obwohl wir fertig sind, haben wir noch nicht gesehen, wie die "kleinen" Kreise definiert sind, wie die Punkte `𝐺` und `𝑃` auf ihre entsprechenden Punkte `𝐺′` und `𝑃′` abgebildet werden und wie alle kleinen Lösungen zu einer großen Lösung kombiniert werden. Ich werde versuchen, es hier intuitiv zu erklären, denn der nächste Angriff basiert ebenfalls auf diesem Teil.
Angenommen, wir haben einen "Kreis" der Ordnung `3𝑥5𝑥7 = 105`, und sein Generator ist `𝐺`. Wir definieren einen Punkt `𝐺′ = (5𝑥7)𝐺 = 35𝐺` und betrachten den daraus erzeugten "Kreis". Wenn wir von `𝐺′` aus einen "Schritt" gehen, d.h. wir addieren `𝐺′` zu sich selbst, ist das so, als würden wir 35 Schritte vom Punkt `35𝐺` im ursprünglichen "Kreis" aus gehen, und wir erreichen den Punkt `2𝐺′ = 70𝐺`. Wenn wir einen weiteren "Schritt" gehen, erreichen wir den Punkt `3𝐺′ = 105𝐺 = 𝒪`, und wenn wir von dort einen weiteren "Schritt" gehen, erreichen wir den Punkt `4𝐺′ = 35𝐺 = 𝐺′`, also zurück zum Ausgangspunkt. Der von `G′` gebildete "Kreis" hat die Ordnung `3`, und das ist kein Zufall, denn auf einem "Kreis" der Ordnung `105` kann man genau `3` "Schritte" der Größe `35` machen. Ähnlich könnten wir einen "Kreis" der Ordnung `5` erzeugen, indem wir den Punkt `𝐺′ = (3𝑥7)𝐺 = 21𝐺` definieren, und einen Kreis der Ordnung `5`, indem wir `𝐺′ = (3𝑥5)𝐺 = 15𝐺` definieren.
Wenn wir es andersherum betrachten, wird es interessanter. Angenommen, wir sind im ursprünglichen "Kreis" `𝑛` Schritte vom Punkt `G` aus gegangen und haben den Punkt `𝑛𝐺` erreicht. Wenn wir auch im kleinen "Kreis" `𝑛` Schritte vom Punkt `𝐺′` aus gehen würden, erreichten wir den Punkt `𝑛′𝐺′` mit `𝑛 ≡ 𝑛′ (𝑚𝑜𝑑 3)`. Und warum ist das interessant? Weil die Ordnung von `𝐺′` viel kleiner ist als die Ordnung von `𝐺`, und wir daher bei gegebenem `𝐺′` und `𝑛′𝐺′` relativ leicht `𝑛′` finden können. Wenn wir das tun, und zwar auch für die beiden anderen Primfaktoren der Ordnung des "Kreises", nämlich `5` und `7`, erhalten wir die folgenden Werte:
𝑛 ≡ $𝑛'_1$ (𝑚𝑜𝑑 3)\
𝑛 ≡ $𝑛'_2$ (𝑚𝑜𝑑 5)\
𝑛 ≡ $𝑛'_3$ (𝑚𝑜𝑑 7)
Aus diesen drei Werten kann `𝑛` mithilfe des Chinesischen Restsatzes leicht bestimmt werden, und damit ist das ursprüngliche Problem gelöst.
## Die Ordnung des Generators ist fast eine glatte Zahl, und der private Schlüssel ist klein
Angenommen, wir erhalten – ähnlich wie beim vorherigen Angriff – eine Kurve, bei der sich die Ordnung des Generators in Primfaktoren zerlegen lässt, aber diesmal ist der größte Primfaktor zu groß, als dass es praktikabel wäre, ihr ECDLP zu lösen. Wenn die Generatorordnung zum Beispiel `256 bit` beträgt, der größte Primfaktor aber `128 bit` ist.
Der Pohlig-Hellman-Algorithmus benötigt etwa $O(2^{64})$ Operationen, um den privaten Schlüssel zu finden, was undurchführbar ist.
Wenn wir wissen, dass der verwendete private Schlüssel relativ klein ist, kann er trotzdem effizient gefunden werden.
Nehmen wir an, dass der private Schlüssel `64 bit` beträgt (statt `256 bit`). Wenn der öffentliche Schlüssel erzeugt wird, wird der Generator mit dem privaten Schlüssel multipliziert, und man erhält einen Punkt in dem "Kreis", den der Generator erzeugt. Obwohl der "Kreis" etwa $2^{256}$ Punkte umfasst, wird dieser Punkt irgendwo in die "ersten" $2^{64}$ Punkte "fallen". Es gibt keine "Interaktion" zwischen dem privaten Schlüssel und den Punkten im "Kreis", die größeren Werten entsprechen.
Es ist möglich, den Pohlig-Hellman-Algorithmus auszuführen, aber die zu großen "Kreise" zu "verwerfen", vorausgesetzt, dass das Produkt der Ordnungen der verbleibenden "Kreise" mindestens so groß ist wie die Länge des privaten Schlüssels. Wenn genügend kleine Primfaktoren gefunden werden, deren Produkt mindestens `64 bit` beträgt, dann reichen die entsprechenden "Kreise" aus, um denselben Angriff wie zuvor durchzuführen.
Wenn wir es vorher beim Schreiben von Code leicht hatten, müssen wir diesmal einiges selbst implementieren, denn die `discrete_log`-Funktion von SageMath weiß nicht, dass wir einige der Primfaktoren "verwerfen" möchten. Das folgende Code-Snippet erledigt das:```python
p = 88664572752015126127869404674421545790506871948117527783533589813159111825511
a = 13
b = 37
E = EllipticCurve(GF(p), [a,b])
G = E(19374976316789648652022260955836934561553454311144967863145605756652014623129,
68630819472054489323664324766002023315775509214344811025345735680440707888471)
n = G.order()
print("Number of bits in n:", n.nbits())
factors = n.factor()
print("n's factors:", factors)
PRIVATE_KEY_BIT_SIZE = 64
import random
private_key = random.randrange(2^PRIVATE_KEY_BIT_SIZE)
P = private_key * G
print("We know that the private key is", PRIVATE_KEY_BIT_SIZE, "bits long")
print("Lets find which of the factors of G's order are relevant for finding the private key")
# find factors needed such that the order is greater than the secret key size
count_factors_needed = 0
new_order = 1
for p, e in factors:
new_order *= p^e
count_factors_needed += 1
if new_order.nbits() >= PRIVATE_KEY_BIT_SIZE:
print("Found enough factors! The rest are not needed")
break
factors = factors[:count_factors_needed]
print("Considering these factors:", factors)
print("Calculating discrete log for each quotient group...")
subsolutions = []
subgroup = []
for p, e in factors:
quotient_n = (n // p ^ e)
G0 = quotient_n * G # G0's order is p^e
P0 = quotient_n * P
k = G0.discrete_log(P0)
subsolutions.append(k)
subgroup.append(p ^ e) # k the order of G0
print("Running CRT...")
found_key = crt(subsolutions, subgroup)
assert found_key * G == P
assert private_key == found_key
print("success!")
In diesem Codeausschnitt definieren wir eine elliptische Kurve und einen Generator darin und geben die Primfaktoren seiner Ordnung aus. Die Ausgabe ist:``` Number of bits in n: 256 n's factors: 2 * 3 * 29 * 2699 * 28751 * 831913766251 * 92996710252298530263979 * 84878782522781478604307230464271
Die Ordnung des Generators ist `256 bit` und zerfällt in mehrere Primfaktoren, sodass die beiden größten `77 bit` und `107 bit` betragen. Sie sind groß genug, sodass es unpraktisch wäre, ECDLP zu lösen. Dann wird ein privater Schlüssel von `64 bit` zufällig erzeugt und ein öffentlicher Schlüssel berechnet. Im nächsten Schritt "sammeln" wir genügend Primfaktoren, bis wir eine Ordnung mit einer Länge von mindestens `64 bit` erhalten. Die Ausgabe ist:```
We know that the private key is 64 bits long
Lets find which of the factors of G's order are relevant for finding the private key
Found enough factors! The rest are not needed
Considering these factors: [(2, 1), (3, 1), (29, 1), (2699, 1), (28751, 1), (831913766251, 1)]
Es ist zu erkennen, dass die beiden größten Faktoren redundant sind und der größte verbleibende Faktor 40 bit beträgt. Im nächsten Schritt berechnen wir für jeden der verbleibenden Faktoren die Punkte 𝐺′ und 𝑃′ wie zuvor erläutert und lösen für jeden von ihnen das ECDLP. Die Ergebnisse bzw. die Primfaktoren werden in den Listen subsolutions und subgroups gespeichert. Schließlich werden alle Ergebnisse mithilfe des Chinesischen Restsatzes zum privaten Schlüssel kombiniert, und wir verifizieren, dass dieser tatsächlich korrekt ist.
Bei der Betrachtung der Definition der Punktaddition auf elliptischen Kurven fällt eine interessante Eigenschaft auf: Bei der Punktaddition wird der Wert 𝑏 nicht verwendet, sondern nur die Werte 𝑎 und 𝑝. Das bedeutet, dass das Addieren von Punkten, die auf einer Kurve liegen, auch für eine andere Kurve sinnvoll sein kann, die sich von ihr nur durch den Wert 𝑏 unterscheidet. Dies gilt natürlich auch für die Multiplikation eines Punktes mit einer Zahl. Wenn der Benutzer nicht überprüft, dass der Punkt, den er von der anderen Partei als öffentlichen Schlüssel erhält, tatsächlich auf seiner Kurve liegt, setzt er sich einem Invalid-Curve-Angriff aus.
Angenommen, zwei Parteien haben sich auf eine elliptische Kurve $E_1$ geeinigt. Ein Angreifer kann eine bösartige Kurve $𝐸_2$ erzeugen, die dieselben Werte 𝑎 und 𝑝 wie $𝐸_1$ hat, aber einen anderen Wert 𝑏. Auf der Kurve $𝐸_2$ wählt der Angreifer einen Punkt 𝑃, dessen Ordnung klein ist, zum Beispiel 3. Natürlich wird der Punkt 𝑃 nicht auf $𝐸_1$ liegen, weil er einer Gleichung mit einem anderen 𝑏-Wert als dem von $𝐸_1$ genügt. Der Angreifer sendet den Punkt 𝑃 als seinen öffentlichen Schlüssel an den Benutzer. Nehmen wir an, der Benutzer macht sich nicht die Mühe zu überprüfen, ob der empfangene Punkt tatsächlich auf der Kurve $𝐸_1$ liegt, auf die sich die Parteien geeinigt haben. Der Benutzer nimmt den vom Angreifer erhaltenen öffentlichen Schlüssel, multipliziert ihn mit seinem privaten Schlüssel und gelangt zu einem Punkt, der der gemeinsame geheime Punkt sein sollte, wie wir es in der Definition des ECDH-Protokolls gesehen haben. Aus Sicht des Benutzers wird er die Multiplikationsoperation auf der Kurve $𝐸_1$ berechnen. Da der Punkt 𝑃 jedoch überhaupt nicht auf dieser, sondern auf $𝐸_2$ liegt, wird der Benutzer die Multiplikationsoperation tatsächlich auf der Kurve $𝐸_2$ berechnen. Später wird der Benutzer den gemeinsamen geheimen Punkt verwenden, um die Kommunikation mit dem Angreifer fortzusetzen. Nehmen wir an, die Parteien verwenden die 𝑥-Koordinate des Punktes als AES-Verschlüsselungsschlüssel. In diesem Fall wird der Benutzer eine Nachricht verschlüsseln und sie an den Angreifer senden.
Da die Ordnung von 𝑃 gleich 3 ist, gibt es für den Benutzer nur 3 mögliche gemeinsame Punkte, die er berechnen kann. Der Angreifer geht diese möglichen Punkte durch und findet heraus, welcher von ihnen dem Schlüssel entspricht, der die vom Benutzer gesendete verschlüsselte Nachricht erfolgreich entschlüsselt. Mit diesem Punkt und dem Ausgangspunkt 𝑃 kann der Angreifer den Rest der Division des privaten Schlüssels des Benutzers durch die Zahl 3 ableiten. Der Angreifer kann dem Benutzer weitere bösartige Punkte 𝑃 mit zunehmenden Ordnungen senden, zum Beispiel 5, 7 und so weiter. Auf diese Weise kann der Angreifer genügend Werte sammeln, die Reste von Divisionen des privaten Schlüssels des Benutzers durch kleine Zahlen darstellen. Schließlich kann der Angreifer den Chinesischen Restsatz verwenden, um den privaten Schlüssel des Benutzers zu berechnen, auf dieselbe Weise wie beim vorherigen Angriff.
Hier ist eine intuitivere Erklärung: Ein Angreifer kann dem Benutzer einen Punkt auf einem sehr kleinen „Kreis“ zur Verfügung stellen, zum Beispiel der Länge 2. Der Benutzer wird sich auf diesem „Kreis“ eine beliebige Anzahl von Schritten vorwärtsbewegen und den Zielpunkt erreichen. Der Angreifer kennt den Zielpunkt des Benutzers, der eine von 2 Möglichkeiten sein kann. Daher kann der Angreifer erkennen, ob der Benutzer eine gerade oder ungerade Anzahl von Schritten auf dem Kreis zurückgelegt hat. Der Angreifer kann dem Benutzer weitere Punkte auf „Kreisen“ der Längen 3, 5, 7 usw. zur Verfügung stellen. Bis der Angreifer genügend solcher Faktoren hat, von denen jeder wenig Informationen über die Anzahl der Schritte enthält, die der Benutzer zurückgelegt hat. Schließlich kann der Angreifer alle diese Werte zu der exakten Anzahl von Schritten kombinieren, die der Benutzer zurückgelegt hat – was seinem privaten Schlüssel entspricht.
Der folgende Code demonstriert den Angriff:```python from ecdsa.ecdsa import generator_128r1, curve_128r1 from Crypto.Util.number import long_to_bytes from Crypto.Util.Padding import pad, unpad from Crypto.Cipher import AES import random
curve = curve_128r1 G = generator_128r1 n = G.order() p = curve.p() a = curve.a()
private_key = random.randrange(n)
def encrypt_data(shared_point, message): if shared_point.is_zero(): x, y = 0, 0 else: x, y = shared_point.xy() key = long_to_bytes(int(x)).rjust(16, b"\x00") iv = long_to_bytes(int(y)).rjust(16, b"\x00") cipher = AES.new(key, AES.MODE_CBC, iv)
message = pad(message.encode(), 16)
return cipher.encrypt(message)
def decrypt_data(shared_point, enc_message): if shared_point.is_zero(): x, y = 0, 0 else: x, y = shared_point.xy() key = long_to_bytes(int(x)).rjust(16, b"\x00") iv = long_to_bytes(int(y)).rjust(16, b"\x00") cipher = AES.new(key, AES.MODE_CBC, iv)
decrypted = cipher.decrypt(enc_message)
return unpad(decrypted, 16)
def ECDH(A): # Send our public key to the other side # Have them reach the shared point and # Send us an encrypted message using the shared point as key
# This part takes place remotely and is unknown to the attacker
shared_point = private_key * A
message = "Inconceivable!"
return encrypt_data(shared_point, message)
def brute_force_encrypted_message(A, encrypted_message, max_order): # Returns n such that n*A matches the key used to encrypt the message for i in range(1, max_order): shared_point = i * A try: # If both padding is correct and all characters are ascii # Then it is probably the correct encryption key decrypted = decrypt_data(shared_point, encrypted_message) decrypted = decrypted.decode() return i except: continue raise Exception("Did not find a value for one of the encrypted messages")
def find_curves_with_small_subgroup(p, a, max_order): # Yield tuples of (order, point) such that the point is # on a curve with the same a & p values, but different b # and the point's order is <= max_order orders_found = set() b = 0 while True: b += 1 if b == p: # Ran out of b values break if (4a^3 + 27b^2) % p == 0: # Curve is singular continue
E = EllipticCurve(GF(p), [a, b])
for _ in range(100):
R = E.random_point()
n = R.order()
for f, e in n.factor():
if f in orders_found:
continue
if f > max_order:
break
# Create a point with order f
orders_found.add(f)
P = (n // f) * R
assert P.order() == f
yield (f, P)
subsolutions = [] subgroup = [] max_order = 10000 upto = 1 for order, A in find_curves_with_small_subgroup(p, a, max_order): upto *= order print("Found point with order", order, "so now can find keys of size up to", upto)
# Send this point as our public key and get an encrypted message from other side
encrypted_message = ECDH(A)
# Find the value n such that: private_key = n (mod order)
key_mod_order = brute_force_encrypted_message(A, encrypted_message, max_order)
# Save result to be used in CRT later
subsolutions.append(key_mod_order)
subgroup.append(order)
# Found enough values to calculate private key
if upto >= n:
break
print("Found enough values! Running CRT...") found_key = crt(subsolutions, subgroup) print("Found private key", found_key) assert private_key == found_key print("success!")
In diesem Codeausschnitt werden eine Kurve und ein Generator ausgewählt, der Benutzer erzeugt zufällig einen privaten Schlüssel und verwendet ihn für alle Anwendungen des ECDH-Protokolls. Die Funktion `find_curves_with_small_subgroup` findet Paare aus Punkten und Ordnungen, sodass die Ordnung jedes Punktes relativ klein ist und der Punkt auf einer Kurve liegt, die sich von der ursprünglichen Kurve nur durch den Wert von `𝑏` unterscheidet. Der Code erzeugt solche Paare, bis genügend Paare gefunden sind. Für jedes Paar wird der öffentliche Schlüssel an den Benutzer gesendet und eine verschlüsselte Nachricht von ihm empfangen.
Auf der verschlüsselten Nachricht wird eine Brute-Force-Suche durchgeführt, um den Wert des privaten Schlüssels des Benutzers modulo der aktuellen Ordnung zu finden. Alle diese Ergebnisse werden gespeichert, und schließlich verwenden wir den Chinesischen Restsatz, um den privaten Schlüssel des Benutzers zu berechnen und zu verifizieren, dass er korrekt ist. In diesem Fall haben die Parteien vereinbart, dass die Kommunikation über AES erfolgt, wobei der Verschlüsselungsschlüssel die `x`-Koordinate des gemeinsamen geheimen Punkts ist und der IV dessen `𝑦`-Koordinate ist.
Die Komplexität des Angriffs beträgt $𝑂(𝑛_{𝑚𝑎𝑥})$, wobei $𝑛_{𝑚𝑎𝑥}$ die größte Ordnung unter den Ordnungen der bösartigen Punkte ist. Das liegt daran, dass der „schwerste“ Teil des Angriffs die Brute-Force-Suche auf dem größten „Kreis“ unter den kleinen „Kreisen“ ist, und der Angreifer kann diesen Wert glücklicherweise fast vollständig kontrollieren. Daher ist dieser Angriff in Bezug auf die Komplexität relativ effizient. Wie bereits erwähnt, liegt die Wurzel des Problems in diesem Fall darin, dass der Benutzer nicht prüft, ob der Punkt, den er empfangen hat, überhaupt auf der Kurve liegt, mit der er arbeitet. Außerdem verwendet der Benutzer bei jeder neuen Verwendung von ECDH denselben privaten Schlüssel, was nicht so sicher ist.
## Die Kurve ist singulär
Eine der wichtigen Eigenschaften, die eine elliptische Kurve haben muss, um kryptographisch sicher zu sein, ist, dass sie nicht-singulär ist. Eine nicht-singuläre Kurve ist eine Kurve, bei der ein bestimmter Wert, die sogenannte „Diskriminante“ der Kurve, ungleich null ist. Dies gilt, wenn ihre Parameter `𝑎` und `𝑏` die Ungleichung erfüllen:
$4a^3 + 27b^2 ≠ 0$
Eine Kurve, die diese Ungleichung nicht erfüllt, hat einen „problematischen“ Punkt, der als `singular point` bezeichnet wird. Es gibt zwei Arten solcher Punkte: Knoten und Spitze. Ein Knotenpunkt existiert auf einer Kurve, die eine Art Schleife hat, die sich am Singularpunkt selbst schneidet, und durch diesen Punkt können zwei verschiedene Tangenten an die Kurve gelegt werden.
Ein Spitzenpunkt ist ein Punkt, an dem die Kurve „spitz“ ist, als ob zwei Linien aus ihm herauskommen, aber es gibt nur eine Tangente an die Kurve an diesem Punkt.
<img src="https://assets.kitploit.com/production/public/readmes/48932/a40d8ce67ecb97eeabe85b52937a8935bc917b622e02168d9047200ed54feafc.png" alt="Singular Elliptic Curves" width="500">
Bei einem Knotenpunkt gibt es eine doppelte Nullstelle, daher kann die Gleichung der Kurve geschrieben werden als:
$y^2 = (x-x_0)^2(x-x_1)\ \ \ \ (mod\ p)$
Die Kurve kann nach links „verschoben“ werden, indem man die Variable $x$ durch die Variable $(𝑥 + 𝑥_0)$ ersetzt und so die Form erhält:
$y^2 = x^2(x+x_0-x_1)\ \ \ \ (mod\ p)$
Nun liegt der Singularpunkt im Ursprung der Achsen. Der numerische Wert von $t = (x_0-x_1)$ kann verwendet werden, um eine Abbildung zwischen Punkten auf der Kurve und ganzen Zahlen zu erstellen, sodass die Additionsoperation zwischen Punkten auf der Kurve der Multiplikationsoperation zwischen Zahlen entspricht. Jedem Punkt `(𝑥, 𝑦)` ordnen wir die Zahl
$\frac{y+\sqrt{t}x}{y-\sqrt{t}x}$ zu. Insbesondere können wir einem Paar von Punkten `𝐺` und `𝑄` mit `𝑄 = 𝑛𝐺` Zahlen `𝑔` und `𝑞` zuordnen, sodass $𝑞 ≡ 𝑔^𝑛\ \ \ \ (mod\ p)$ gilt, und dies ist ein „normales“ DLP-Problem. Um diesen Prozess zu veranschaulichen, habe ich in den Referenzen am Ende des Artikels einen Link zu einem Beispiel mit kleinen Zahlen hinzugefügt. Bei der Abbildung, die wir durchgeführt haben, haben wir die Gleichungen der Geraden $y+\sqrt{t}x$ und $y-\sqrt{t}x$ verwendet, und diese sind die Geraden, die den beiden Tangenten entsprechen, die am Singularpunkt gezeichnet werden können (nachdem wir die Kurve „verschoben“ haben), was im Grunde der Grund ist, warum dieser Angriff verwendet werden kann.
Ein solches DLP-Problem kann mithilfe des Pohlig-Hellman-Algorithmus effizient gelöst werden, den wir bereits zuvor gesehen haben, da er auch auf ganze Zahlen anstelle von Punkten auf der Kurve angewendet werden kann. Im Zusammenhang mit Punkten haben wir gesehen, dass der Algorithmus nützlich ist, wenn die Ordnung des Generators eine glatte Zahl ist. Anders als ein „Kreis“ von Punkten auf einer Kurve, der eine beliebige Ordnung haben kann, ist die Ordnung im Körper der ganzen Zahlen modulo einer Primzahl `𝑝` gleich `𝑝 − 1`. Wenn `𝑝 − 1` eine glatte Zahl ist, löst der Algorithmus das DLP-Problem effizient und findet so den privaten Schlüssel `n`.
Der folgende Codeausschnitt tut genau das:```python
p = 102360775616927576983385464260307534406913988994641083488371841417601237589487
a = -3
b = 2
assert (4*a^3 + 27*b^2) % p == 0
Gx = 1777671135698746847568710125129424132255529153914112337834835240247819869964
Gy = 6786424314307625790108882554225666781375821855884993473586521771737454762217
Qx = 45541468695354471317248123146376609839909398850045396377931300808635064950836
Qy = 42191909885728105279718027025083923092282618497451601162405594991792376530066
x = GF(p)["x"].gen()
f = x^3 + a*x + b
roots = f.roots()
assert len(roots) == 2 # two roots, so one must be double
if roots[0][1] == 2:
double_root = roots[0][0]
single_root = roots[1][0]
else:
double_root = roots[1][0]
single_root = roots[0][0]
print("double root:", double_root)
print("single root:", single_root)
# map G and Q to the new "shifted" curve
Gx = (Gx - double_root)
Qx = (Qx - double_root)
# Transform G and Q into numbers g and q, such that q=g^n
t = double_root - single_root
t_sqrt = t.square_root()
def transform(x, y, t_sqrt):
return (y + t_sqrt * x) / (y - t_sqrt * x)
g = transform(Gx, Gy, t_sqrt)
q = transform(Qx, Qy, t_sqrt)
print("g:", g)
print("q:", q)
# Find the private key n
print("Factors of p-1:", factor(p-1))
print("Calculating discrete log for g and q...")
found_key = discrete_log(q, g)
print("Found private key:", found_key)
from Crypto.Util.number import long_to_bytes
print("The secret is:", long_to_bytes(found_key).decode())
In diesem Codeausschnitt definieren wir die Parameter einer elliptischen Kurve und verifizieren, dass sie tatsächlich singulär ist. Wir finden die Wurzeln des zur Kurve gehörenden Polynoms und identifizieren, welche davon die doppelte Wurzel ist. Wir verwenden die doppelte Wurzel, um die Kurve zu „verschieben", und erreichen die „verschobenen" Punkte 𝐺 und 𝑄. Dann berechnen wir $\sqrt{t}$ aus den gefundenen Wurzeln und verwenden es, um die Punkte 𝐺 und 𝑄 auf die Zahlen 𝑔 und 𝑞 abzubilden. Wir geben die Zerlegung von 𝑝 − 1 in seine Primfaktoren aus (um zu verifizieren, dass das DLP tatsächlich effizient gelöst werden kann). Schließlich berechnen wir das DLP und interpretieren das Ergebnis als Zeichenkette.
Die Ausgabe ist: ``` double root: 1 single root: 102360775616927576983385464260307534406913988994641083488371841417601237589485 g: 79308184675041981395063385790064051127319168083579208141274962436724168376607 q: 72551144069373709737718398534799929820619379063890479978458954196900267190559 Factors of p-1: 2 * 41 * 2422091127107 * 3224683479179 * 3224849279789 * 3269304069319
Dieses Mal habe ich eine Nachricht im privaten Schlüssel selbst versteckt. Es sei darauf hingewiesen, dass es sich um eine singuläre Kurve handelt und es daher in SageMath nicht möglich ist, sie auf normale Weise zu erstellen, Punkte darauf zu definieren und Operationen mit ihnen durchzuführen, wie wir es zuvor getan haben. In diesem Code habe ich die Koordinaten der Punkte als konstante Variablen definiert. Um den Punkt `𝑄` zu berechnen, habe ich den privaten Schlüssel selbst mit dem Generator multipliziert, wobei ich meine eigene Implementierung des Double And Add-Algorithmus verwendet habe.
## Die Kurve ist supersingulär
Gegeben eine elliptische Kurve modulo `𝑝` und einen Generator mit der Ordnung `𝑛`, ist der Einbettungsgrad der Kurve bezüglich des Generators definiert als die kleinste Zahl `k`, die die Gleichung $p^k ≡ 1\ \ \ \ (mod\ 𝑛)$ erfüllt. Mit bestimmten Transformationen kann das ECDLP-Problem auf ein DLP-Problem in einem Körper der Ordnung $𝑝^𝑘$ reduziert werden. Der Wert `𝑘` ist normalerweise eine sehr große Zahl (etwa so groß wie `𝑝` selbst), aber wenn er relativ klein ist (sagen wir, kleiner als `6`), wird die Kurve `supersingular` genannt, und es wird möglich, dieses DLP-Problem effizient zu lösen. Dieser Angriff wird MOV-Angriff genannt, benannt nach seinen drei Erfindern (Menezes-Okamoto-Vanstone).
Die Transformationen, die ich erwähnt habe, sind Funktionen, die zwei Punkte entgegennehmen und eine Zahl im Körper der komplexen Zahlen zurückgeben. Transformationen, die verwendet werden können, sind Weil-Paarung oder Tate-Paarung, und wir werden sie als Blackbox verwenden. Eine solche Transformation `𝑇` erfüllt die folgende Eigenschaft für jedes Paar von Punkten `𝑃`, `𝑄`:
$T(mP, nQ)=T(P,Q)^{mn}$
Wenn wir also zwei Punkte `𝐺` und `𝑄 = 𝑚𝐺` gegeben haben, können wir zufällig einen dritten Punkt `𝑅` wählen und die beiden Werte berechnen: \
$g = T(G, R)$ \
$q = T(Q, R)=T(mG,R)=T(G,R)^m=g^m$
Von hier aus können wir das DLP-Problem für `𝑔` und `𝑞` in einem Körper der Ordnung $p^k$ lösen und so den privaten Schlüssel `𝑚` finden. In den Referenzen am Ende des Artikels habe ich einen Link zu einer detaillierteren Erklärung der Mathematik hinter diesem Angriff eingefügt.
Der folgende Codeausschnitt führt diesen Angriff aus:```python
p = 682209701131405092329016993551
a = -35
b = 98
E = EllipticCurve(GF(p), [a, b])
G = E(516365702870683577608927237052,
524474557735717484100814381066)
# Find embedding degree k
Gn = G.order()
k = 1
while p^k % Gn != 1:
k += 1
print("Found k:", k)
# Select private key, and calculate public key Q
private_key = 5072587499125503347
Q = private_key * G
# Define new curve mod p^k and the points on it
Ek = EllipticCurve(GF(p ^ k), [a, b])
Gk = Ek(G)
Qk = Ek(Q)
Rk = Ek.random_point()
# Find a point T with order d such that d divides G's order
m = Rk.order()
d = gcd(m, Gn)
Tk = (m // d) * Rk
assert Tk.order() == d
assert (Gn*Tk).is_zero() # Point INFINITY
# Using T, pair G and Q to integers g and q such that q=g^n (mod p^k)
g = Gk.weil_pairing(Tk, Gn)
q = Qk.weil_pairing(Tk, Gn)
# Alternatively:
#g = Gk.tate_pairing(Tk, Gn, k)
#q = Qk.tate_pairing(Tk, Gn, k)
# Make sure the pairing did not break anything
assert g ^ private_key == q
print("Calculating private key...")
found_key = q.log(g)
assert found_key == private_key
print("success!")
from Crypto.Util.number import long_to_bytes
print("The private key is:", long_to_bytes(found_key).decode())
In diesem Codeausschnitt definieren wir eine Kurve und ihren Generator und berechnen ihren Einbettungsgrad, der in diesem Fall 2 ist, daher ist es praktikabel, den Angriff durchzuführen. Wir definieren eine Kurve, die mit der ursprünglichen Kurve identisch ist, außer dass die Berechnungen modulo $𝑝^𝑘$ statt modulo $𝑝$ durchgeführt werden. Die beiden Punkte 𝐺 und 𝑄 liegen ebenfalls auf der neuen Kurve. Dann finden wir einen dritten Punkt, dessen Ordnung 𝑛 teilt.
Mithilfe des dritten Punktes bilden wir die Punkte 𝐺 und 𝑄 auf die Zahlen 𝑔 und 𝑞 ab und berechnen für sie den diskreten Logarithmus. Schließlich verifizieren wir, dass das erhaltene Ergebnis tatsächlich korrekt ist.
Die Ausgabe ist:``` Found k: 2 Calculating private key... success! The private key is: Festivus
Aus rechnerischer Sicht gibt es heute Index-Calculus-Algorithmen, die das DLP-Problem relativ effizient lösen können, und zwar mit einer Komplexität von $e^{O((log\ p^k)^{1/3}(log\ log\ p^k)^{2/3})}$. Dieser Ausdruck mag einschüchternd wirken, aber im Vergleich zu ECDLP-Algorithmen, deren Komplexität $O(\sqrt{p})=e^{O(log\ p)}$ beträgt, erkennt man, dass es einfacher ist, das DLP-Problem zu lösen, vorausgesetzt, der Einbettungsgrad (engl. Embedding Degree, bezeichnet mit `𝑘`) ist tatsächlich klein.
## Die Kurve ist anomal
Wenn eine bestimmte Kurve die Eigenschaft hat, dass die Ordnung der Kurve (die Anzahl ihrer Punkte) exakt gleich dem Modul `𝑝` ist, dann nennt man sie eine `Anomalous Curve` und sie ist anfällig für einen Angriff namens Smart's Attack. Dieser Angriff nutzt `𝑝-adische Zahlen`. Eine solche Zahl lässt sich als Summe von Potenzen von `p` (positiven und negativen) mit Koeffizienten darstellen. Formal ist eine solche Zahl `s` eine Reihe der Form:
$s=\sum_{i = -k}^{\infty} a_{i}p^i = a_{-k}p^{-k} + \cdots + a_0 + a_1p + a_2p^2 + \cdots$
Wenn die Koeffizienten ganze Zahlen im Bereich $0 ≤ 𝑎_𝑖 < 𝑝$ sind und die Summe in Richtung der positiven Potenzen von `𝑝` unendlich sein kann. Bei solchen Zahlen „betrachten“ wir die Ziffern von rechts nach links statt von links nach rechts, und daher kann eine solche Reihe gegen einen bestimmten Wert konvergieren. Solche Zahlen gehören zu einem anderen Zahlensystem als dem, das wir kennen, und verhalten sich ganz anders als die „normalen“ mathematischen Regeln. Allein zu diesem Thema könnte ein eigener Artikel geschrieben werden, und für alle, die sich dafür interessieren, habe ich in den Referenzen am Ende des Artikels einen Link zu einem Video eingefügt, das es relativ anschaulich präsentiert.
In jedem Fall wird bei diesem Angriff aus der gegebenen Kurve eine neue Kurve erstellt, die über den p-adischen Zahlen definiert ist. Wenn zwei Punkte `𝐺` und `𝑄 = 𝑚𝐺` auf der ursprünglichen Kurve gegeben sind, bilden wir sie auf entsprechende Punkte der neuen Kurve ab. Aus den Koordinaten der erhaltenen Punkte lässt sich `𝑚` leicht berechnen.
Der folgende Code führt den Angriff aus:```python
def lift(P, E, p):
# lift point P from old curve to a new curve
Px, Py = map(ZZ, P.xy())
for point in E.lift_x(Px, all=True):
# take the matching one of the 2 points corresponding to this x on the p-adic curve
_, y = map(ZZ, point.xy())
if y % p == Py:
return point
p = 82880337306360052550952380657384418102169134986290141696988204552000561657747
a = 26413685284385555604181540288021678971301314378522544469879270355650843743231
b = 10017655579196313780863100027113686719855502076415017585743221280232958057095
E = EllipticCurve(GF(p), [a, b])
G = E(37991937053350834320678619330546903567320901767090609881924528835279022654346,
28947208718252880061735762506756351277969075978732800286053352115837132331595)
assert E.order() == p
private_key = 28153370716511608040616395150859085058202177279382452583684367923334520519740
P = private_key * G
# Lift the points to some new curve over p-adic numbers
E_adic = EllipticCurve(Qp(p), [a+p*13, b+p*37])
G = p * lift(G, E_adic, p)
P = p * lift(P, E_adic, p)
# Calculate discrete log
Gx, Gy = G.xy()
Px, Py = P.xy()
found_key = int(GF(p)((Px / Py) / (Gx / Gy)))
assert found_key == private_key
print("success!")
from Crypto.Util.number import long_to_bytes
print("The private key is:", long_to_bytes(found_key).decode())
In diesem Codeausschnitt wird eine Hebefunktion definiert, die einen Punkt auf der ursprünglichen Kurve empfängt und ihm einen Punkt auf der neuen Kurve zuordnet. Dann definieren wir eine elliptische Kurve und einen Generator darin und verifizieren, dass die Ordnung der Kurve tatsächlich p ist. Wir wählen einen privaten Schlüssel und berechnen den entsprechenden öffentlichen Schlüssel. Dann führen wir den Angriff durch. Wir definieren eine neue Kurve über den 𝑝-adischen Zahlen und bilden die ursprünglichen Punkte 𝐺 und 𝑃 mithilfe der Hebefunktion auf entsprechende Punkte in der neuen Kurve ab, indem wir sie mit 𝑝 multiplizieren.
Für jeden neuen Punkt berechnen wir das Verhältnis zwischen seiner 𝑥-Koordinate und seiner 𝑦-Koordinate. Der Quotient dieser beiden Werte ist die ECDLP-Lösung der ursprünglichen Punkte.
Die Ausgabe ist:``` success! The private key is: >>>>> Extraordinarily Nice <<<<<
Der Grund, warum diese Berechnung funktioniert, hängt mit der Tatsache zusammen, dass die Anzahl der Punkte auf der Kurve genau `𝑝` beträgt. Diese Eigenschaft ermöglicht es uns, mehrere Abbildungen durchzuführen, von denen die letzte Punkte auf einer Kurve über p-adischen Zahlen auf Zahlen modulo $p^2$ abbildet. Diese Abbildung hat die Eigenschaft, dass das Verhältnis zwischen dem Zahlenpaar, das den beiden ursprünglichen Punkten entspricht, genau das Ergebnis des Logarithmus der beiden Punkte ist. Wir werden all diese Abbildungen als Blackbox behandeln, aber am Ende des Artikels habe ich Verweise auf die relevanten mathematischen Erklärungen hinzugefügt.
# ECDSA-Angriffe
## Die Nachricht vor dem Signieren nicht hashen
Wir haben gesehen, dass beim Signieren einer Nachricht zuerst der Hash der Nachricht berechnet wird und die hohen Bits des Hashs bei der Signaturberechnung verwendet werden. Nehmen wir an, dass in einer Implementierung des Signierens und Verifizierens von Signaturen dieser Hash-Schritt übersprungen wird und stattdessen die Bits von der Nachricht selbst genommen werden, anstatt die hohen Bits des Hashs zu verwenden. In einer solchen Implementierung ist der einzige Teil der Nachricht, der ihre Signatur beeinflusst, der Anfang der Nachricht. Mit anderen Worten: Wenn wir eine Nachricht und ihre Signatur haben, können wir den Anfang der Nachricht beibehalten und den Rest ändern, und die Signatur bleibt gültig. Das ist ein wirklich einfacher Angriff.
Angenommen, Sie schreiben zum Beispiel die folgende Nachricht an Ihre Bank und signieren sie, ohne sie zu hashen:```
"Please transfer 1,000$ from my account to GitHub so that they can continue hosting awesome repositories"
Die Bank wird diese Nachricht erfolgreich verifizieren und die Aktion ausführen. Ein ... Angreifer ... könnte die folgende Nachricht erstellen:``` "Please transfer 1,000$ from my account to GitHub and 1,000,000$ to Eli Kaski"
Und verwenden Sie die Signatur, die Sie gerade erstellt haben. Die Signatur ist auch für diese Nachricht gültig, und die Bank wird die Aktion ausführen. Nicht gut (nun ja, kommt darauf an, für wen).
Der folgende Code demonstriert den Angriff:```python
from ecdsa import SigningKey, NIST256p
signing_key = SigningKey.generate(NIST256p)
verifying_key = signing_key.verifying_key
class MyHash:
def __init__(self, data):
self.data = data
def digest(self):
return self.data
# Sign the message and verify the signature
message = "Please transfer 1,000$ to GitHub"
signature = signing_key.sign(message.encode(), hashfunc=MyHash)
assert verifying_key.verify(signature, message.encode(), hashfunc=MyHash)
# Construct an evil message and verify the original message's signature is valid for it as well
evil_message = "Please transfer 1,000$ to GitHub and 1,000,000$ to Eli Kaski"
assert verifying_key.verify(signature, evil_message.encode(), hashfunc=MyHash)
print("success!")
In diesem Code-Snippet wird die Bibliothek ecdsa verwendet, zusammen mit einer bekannten Kurve. Wir definieren eine Klasse, die eine Hash-Funktion implementieren soll, dies aber nicht tut, und stattdessen die Nachricht unverändert lässt. Daher werden beim Signieren einer Nachricht nur die ersten Bits der ursprünglichen Nachricht verwendet, anstatt aus ihrem Hash. Anschließend wird die Nachricht signiert und erfolgreich verifiziert. Dann wird eine bösartige Nachricht erstellt, und der Code verifiziert, dass die Signatur der ursprünglichen Nachricht auch zur bösartigen Nachricht passt.
In einem solchen Szenario haben wir möglicherweise nicht den privaten Schlüssel erhalten, um unsere eigenen neuen Signaturen zu erzeugen, aber mit einer gegebenen Signatur können wir so viele Nachrichten signieren, wie wir möchten, vorausgesetzt, sie beginnen mit demselben Präfix.
k in verschiedenen SignaturenIm Rahmen des Nachrichtensignierungsprozesses ist der Benutzer verpflichtet, einen 𝑘-Wert zufällig zu erzeugen und ihn zum Signieren der Nachricht zu verwenden. Es ist sehr wichtig, in verschiedenen Signaturen unterschiedliche 𝑘-Werte zu verwenden. Andernfalls - wenn zwei signierte Nachrichten vorliegen, bei denen der Benutzer denselben Wert 𝑘 verwendet hat, anstatt ihn neu zu erzeugen - könnte ein Angreifer den privaten Schlüssel des Benutzers berechnen.
Wie erwähnt, sendet der Benutzer während der Nachrichtensignierung öffentlich $r=x_1\ \ \ \ (mod\ p)$ und $s=k^{-1}(z+rd_A)$. Angenommen, der Benutzer hat zwei verschiedene Nachrichten signiert, die $𝑧_1$ und $𝑧_2$ entsprechen, und öffentlich zwei Wertepaare $𝑟, 𝑠_1$ und $𝑟, 𝑠_2$ gesendet, d. h. in diesen beiden Signaturen denselben 𝑘-Wert verwendet. Wir stellen fest:
$s_1-s_2=k^{-1}(z_1+rd_A)-k^{-1}(z_2+rd_A)=k^{-1}(z_1+rd_A-z_2-rd_A)=k^{-1}(z_1-z_2)$
Daraus kann der Angreifer den Wert von 𝑘 ermitteln, indem er Folgendes berechnet:
$\displaystyle k=\frac {z_1-z_2}{s_1-s_2}$
Nachdem der Angreifer 𝑘 gefunden hat, kann er aus einer der Signaturen den privaten Schlüssel des Benutzers berechnen. Beachten Sie:
$r^{-1}(ks-z)=r^{-1}(kk^{-1}(z+rd_A)-z)=r^{-1}(z+rd_A-z)=r^{-1}rd_A=d_A$
Mit den Werten von 𝑟, 𝑠 und 𝑧 einer Nachricht und ihrer Signatur sowie dem Wert von 𝑘, den der Angreifer gefunden hat, kann der Angreifer $d_A=r^{-1}(ks-z)$ berechnen. Ab diesem Zeitpunkt kann der Angreifer jede beliebige Nachricht signieren, im Namen des Benutzers, dessen privaten Schlüssel er erlangt hat.
Das folgende Code-Snippet führt diesen Angriff aus:```python from ecdsa.ecdsa import curve_256, generator_256, Public_key, Private_key from Crypto.Util.number import bytes_to_long, long_to_bytes from hashlib import sha256 import random
curve = curve_256 generator = generator_256 n = generator.order()
secret_key = 6743529130774090927928101169617481154782309 public_key = Public_key(generator, generator * secret_key) private_key = Private_key(public_key, secret_key)
k = random.randrange(curve.p()) message1 = "Life is like a box of chocolates." message2 = "You never know what you're gonna get." z1 = bytes_to_long(sha256(message1.encode()).digest()) z2 = bytes_to_long(sha256(message2.encode()).digest())
signature1 = private_key.sign(z1, k) signature2 = private_key.sign(z2, k)
found_k = (z1 - z2) * inverse_mod(signature1.s - signature2.s, n) % n assert k == found_k
found_key = inverse_mod(signature1.r, n) * (found_k * signature1.s - z1) % n assert found_key == secret_key print("success!") print("The secret is:", long_to_bytes(found_key).decode())
In diesem Codeausschnitt wird die Bibliothek `ecdsa` zusammen mit einer bekannten Kurve verwendet. Wir definieren einen privaten Schlüssel und verwenden ihn, um zwei Nachrichten zu signieren. Der Wert von `𝑘` wird zufällig generiert, bleibt aber für die beiden Signaturen derselbe. Gegeben die beiden Nachrichten und ihre Signaturen, führt der Code die Berechnung durch, die wir gesehen haben, um `𝑘` zu finden. Schließlich verwenden wir den Wert von `𝑘`, den wir gefunden haben, um den privaten Schlüssel zu berechnen, wie wir gesehen haben. Die Ausgabe ist:```
Success!
The secret is: Mistakes were made
Es ist interessant festzustellen, dass dieser Angriff tatsächlich im Jahr 2010 eingesetzt wurde, als Sony seinen Signiermechanismus bei der PlayStation-Konsolensoftware unsicher implementierte. Sony verwendete einen statischen Wert von 𝑘 für seine Signaturen, was es Angreifern ermöglichte, Sonys privaten Schlüssel mithilfe der obigen Berechnung zu erhalten. Dies führte zu der Fähigkeit, beliebigen Code zu signieren und die PlayStation dazu zu bringen, ihn auszuführen. Später wurde diese Fähigkeit genutzt, um Raubkopien und inoffizielle Spiele auf der Konsole zu installieren.
k-WertenWenn der Benutzer 𝑘 auf eine unzureichend zufällige Weise wählt, kann der private Schlüssel gefunden werden. Wenn der Angreifer beispielsweise weiß, dass 𝑘 in einem sehr kleinen Wertebereich liegt oder einige Bytes von 𝑘 dem Angreifer bekannt sind, ist es möglich, durch einfache Brute-Force den privaten Schlüssel des Benutzers zu finden, sobald eine einzelne signierte Nachricht vorliegt. Der Angreifer führt die Berechnung aus dem vorherigen Angriff für die verschiedenen 𝑘-Werte aus, bis er den richtigen Wert erreicht und daraus den privaten Schlüssel erhält.
Um dieses Problem zu lösen, generieren Benutzer manchmal zufällig einen Wert, berechnen dessen Hash mit einer Hashfunktion und verwenden das Ergebnis als 𝑘. Diese Methode kann Probleme verursachen. Angenommen, die Ordnung des Generators 𝑛 beträgt 256 bit und die gewählte Hashfunktion ist SHA-1. Die Ausgabe dieser Funktion ist eine Zahl mit 160 bit. Bei Berechnungen modulo 𝑛 ist bekannt, dass der Wert von 𝑘 96 Nullen am Anfang enthält, was bedeutet, dass 𝑘 eine relativ kleine Zahl ist. In einer solchen Situation sagt man, dass die 𝑘-Werte biased sind, und wenn mehrere Nachrichten mit demselben privaten Schlüssel signiert werden, kann der private Schlüssel gefunden werden.
Der Angriff basiert auf einer algebraischen Struktur namens Gitter. Informell kann man sich ein Gitter als eine Menge von Vektoren in einem 𝑚-dimensionalen Raum vorstellen, die als Linearkombination von „Basis“-Vektoren mit ganzzahligen Koeffizienten ausgedrückt werden kann. Mathematisch gilt: Wenn $\{b_1,\dots,b_d\}$ die Basisvektoren über $ℝ^𝑚$ sind, dann ist das zugehörige Gitter $L=$ $\{\sum_{i=1}^d a_ib_i\mid a_i \in Z\}$. In dieser Struktur gibt es das bekannte Problem: Gegeben sei die Basis eines Gitters, finde den kürzesten Vektor, der im Gitter existiert. In diesem Zusammenhang ist ein „kurzer Vektor“ informell ein Vektor, dessen Elemente so nahe wie möglich bei null liegen. Dieses Problem wird als Problem des kürzesten Vektors (SVP) bezeichnet und gilt als NP-schwer. Es gibt Algorithmen, die ein ähnliches, aber einfacheres Problem lösen – das Finden eines kurzen Vektors, also eines Vektors, der relativ „nahe“ am kürzesten Vektor des Gitters liegt. Dieses Problem wird als Problem des nächsten Vektors (CVP) bezeichnet, und einer der Algorithmen, die es lösen, ist der Lenstra-Lenstra-Lovász-Algorithmus (LLL). Bei diesem Angriff verwenden wir diesen Algorithmus als Black Box.
Gegeben 𝑑 signierte Nachrichten ist es möglich, ein Gitter zu konstruieren, das den Vektor $(𝑘_1, \dots , 𝑘_𝑑)$ enthält, wobei jedes Element des Vektors ein 𝑘-Wert ist, der einer Signatur entspricht. Der LLL-Algorithmus findet eine Näherung an den kürzesten Vektor in diesem Gitter. Da die Werte von 𝑘 bekanntermaßen klein sind, besteht eine hohe Wahrscheinlichkeit, dass der vom Algorithmus gefundene kurze Vektor mindestens ein korrektes k-Element enthält. Sobald ein korrektes 𝑘 gefunden ist, kann der private Schlüssel wie im vorherigen Angriff berechnet werden.
Um dieses Gitter zu konstruieren, müssen seine Basisvektoren definiert werden. Ich habe in den Referenzen am Ende des Artikels einen Link zu einem Artikel eingefügt, der erklärt, wie diese Basisvektoren definiert werden. Technisch können die Basisvektoren des Gitters als Matrix dargestellt werden, wobei jede Zeile aus den Elementen eines Basisvektors besteht. Um die Genauigkeit des LLL-Algorithmus zu verbessern, wird empfohlen, dieser Matrix zwei Spalten hinzuzufügen, die Informationen über die erwartete Größe der 𝑘-Werte und das Verhältnis zwischen 𝑘 und 𝑛 enthalten. Diese Verbesserung wird ebenfalls in der von mir angehängten Referenz erläutert. Das folgende Code-Snippet demonstriert diesen Angriff:```python
from ecdsa.ecdsa import curve_256, generator_256, Public_key, Private_key
from Crypto.Util.number import bytes_to_long, long_to_bytes
from hashlib import sha1
import random
def build_matrix(signatures, bias, q): # M matrix should be: """ [ B 0 m'1 m'2 m'2 ... m'n 0 B/q r'1 r'2 r'3 ... r'n 0 0 0 0 q * I 0 0 ] where: m' = s^-1 * m r' = s^-1 * r """
# Construct the first 2 rows of M:
row1 = [bias, 0]
row2 = [0, bias / q]
for m, r, s in signatures:
row1.append((inverse_mod(s, q) * m) % q)
row2.append((inverse_mod(s, q) * r) % q)
top_rows = Matrix(QQ, [row1, row2])
# Construct the q*I block along with 2 columns of zeros
zero_cols = zero_matrix(QQ, len(signatures), 2)
qI = q * identity_matrix(QQ, len(signatures))
bottom_rows = block_matrix([[zero_cols, qI]])
# Combine all rows into one matrix
M = top_rows.stack(bottom_rows)
return M
def find_private_key(L, signatures, public_key): # Check if any valid k was found in L generator = public_key.generator q = generator.order() for row in L.rows(): for i in range(len(signatures)): m,r,s = signatures[i] # Skip the first two vector components we used to improve LLL possible_k = row[i+2] # LLL might have swapped the sign of the found short vectors for k in [possible_k, -possible_k]: d = inverse_mod(r,q)(ks-m) % q if d*generator == public_key.point: return d
curve = curve_256 generator = generator_256 q = int(generator_256.order())
secret_key = 1793056234309773077862125006843383726029262764680727851636 public_key = Public_key(generator, generator * secret_key) private_key = Private_key(public_key, secret_key)
messages_to_sign = [ "And then I go and spoil it all", "By saying somethin' stupid like", "I love you" ]
signatures = [] for message in messages_to_sign: message_hash = bytes_to_long(sha1(message.encode()).digest()) k = bytes_to_long(sha1(long_to_bytes(random.randrange(q))).digest()) signature = private_key.sign(message_hash, k) signatures.append((message_hash, signature.r, signature.s))
bias = 2^160 M = build_matrix(signatures, bias, q)
L = M.LLL()
found_key = find_private_key(L, signatures, public_key) assert found_key == secret_key print("success!") print("The secret is:", long_to_bytes(found_key).decode())
In diesem Codeausschnitt wird eine Standardkurve verwendet, ein privater Schlüssel wird ausgewählt und der zugehörige öffentliche Schlüssel wird daraus berechnet. Es werden 3 Nachrichten erstellt und mit 3 zufälligen `k`-Werten signiert, die aus der SHA-1-Hashfunktion resultieren. Dann erstellen wir die Matrix, die der Basis des Gitters entspricht, wie im Artikel erklärt, und führen den LLL-Algorithmus darauf aus. Danach gehen wir die Zeilen der resultierenden Matrix durch und prüfen, ob ein korrekter Wert eines beliebigen `𝑘` in einer von ihnen gefunden wird.
Die Prüfung wird durchgeführt, indem der private Schlüssel aus dem potenziellen `𝑘` berechnet wird, wie wir es beim vorherigen Angriff gesehen haben, und überprüft wird, ob der empfangene Schlüssel tatsächlich korrekt ist. Schließlich stellen wir sicher, dass der gefundene private Schlüssel tatsächlich korrekt ist. Die Ausgabe lautet:```
success!
The secret is: I am Jack's broken heart
Die Komplexität dieses Angriffs entspricht der Komplexität des LLL-Algorithmus, also $O(d^6\ \log^3B)$, wobei 𝐵 die Länge des Bias von 𝑘 angibt ($2^{160}$ in unserem Fall) und 𝑑 die Anzahl der signierten Nachrichten (3 in unserem Fall). Es stellt sich die Frage, wie viele signierte Nachrichten mindestens erforderlich sind, um den Angriff ausführen zu können. Die Antwort darauf ist $\displaystyle d=O(\frac {\log n}{\log n-\log B})$, wobei 𝑛 die Ordnung des Generators und 𝐵 der Bias ist. Eine Erklärung hierfür findet sich im zweiten Link der Referenzen, die ich zu diesem Thema am Ende des Artikels angefügt habe.
In der Praxis kann eine Variation dieses Angriffs auch dann ausgeführt werden, wenn die oberen Bits von 𝑘 bekannt sind, oder einfach beliebige Bits von 𝑘. Der Angriff kann sogar dann ausgeführt werden, wenn der Wert nur eines Bits bekannt ist, oder sogar wenn der Wert nur eines Bits mit einer Wahrscheinlichkeit von mehr als 50 % bekannt ist! Aber natürlich werden in diesen Fällen viele weitere signierte Nachrichten benötigt, um den Angriff durchzuführen.
Wir haben gesehen, dass beim Prozess der Signaturverifikation die signierende Partei das Wertepaar 𝑟 und 𝑠 an die verifizierende Partei sendet. In Browsern, die das HTTPS-Protokoll implementieren, ist es beispielsweise üblich, dieses Wertepaar in einem Zertifikat zu senden, das auch Daten über die Kurve enthalten kann, die von der signierenden Partei verwendet wurde. Die verifizierende Partei muss sicherstellen, dass die im Zertifikat gefundenen Kurvendaten mit der zuvor vereinbarten Kurve übereinstimmen. Ist das nicht der Fall, kann dies problematisch sein.
Angenommen, Alice hat auf einer bestimmten Kurve einen privaten Schlüssel $d_A$ und einen öffentlichen Schlüssel $𝑃_𝐴$, der dazu gehört, was bedeutet, dass $𝑃_𝐴 = 𝑑_𝐴𝐺$ für den Generator 𝐺 auf dieser Kurve gilt. Mit dem privaten Schlüssel $𝑑_𝐴$ kann Alice ihre Nachrichten signieren, wie wir in der Definition des ECDSA-Protokolls gesehen haben. Angenommen, die Partei, die die Signatur verifiziert, erhält den Generator 𝐺 ebenfalls vom Benutzer und überprüft nicht, ob der vom Benutzer empfangene Generator tatsächlich der vereinbarte Generator ist. Ein Angreifer kann als Generator den Punkt senden, der Alices öffentlicher Schlüssel ist, $𝐺^′ = 𝑃_𝐴$. Der Angreifer wählt als „gefälschten“ privaten Schlüssel den Wert $𝑑_𝐴^′ = 1$, und es ist klar, dass $𝑃_𝐴 = 𝑑_𝐴^′𝐺^′$ gilt. Das bedeutet, dass der Angreifer „beweisen“ kann, dass er den privaten Schlüssel besitzt, der zu Alices öffentlichem Schlüssel passt. Somit kann ein Angreifer eine beliebige Nachricht erstellen und dafür ein Wertepaar 𝑟 und 𝑠 auf übliche Weise mit $𝑑_𝐴^′$ berechnen, und die resultierende Signatur wird erfolgreich verifiziert.
Intuitiv beweist die signierende Partei beim Prozess der Signaturverifikation, dass sie tatsächlich der „Eigentümer“ des öffentlichen Schlüssels ist, der eigentlich ein „Zielpunkt“ auf der Kurve ist. Das liegt daran, dass nur der Unterzeichner weiß, wie viele Schritte vom Startpunkt zum Zielpunkt zu gehen sind. Wenn die verifizierende Partei nicht überprüft, ob der vom Benutzer empfangene Startpunkt tatsächlich der wahre Startpunkt ist, kann ein Angreifer entscheiden, dass der Startpunkt der Zielpunkt ist und dass die Anzahl der von dort aus zu gehenden Schritte null beträgt. Alle anderen Teile der Signaturverifikation bleiben gleich, und die Signatur wird erfolgreich verifiziert. Dieser Angriff wird Curveball genannt.
Dieser Angriff kann mit zusätzlichen Werten verallgemeinert werden. Der Angreifer wählt einen beliebigen Wert 𝑥 und berechnet $𝐺^′ = 𝑥𝑃_𝐴$. Der gefälschte private Schlüssel wird $𝑑'_𝐴 = 𝑥^{−1}\ \ \ \ (mod\ n)$ sein. Dann gilt offensichtlich $𝑑'_𝐴𝐺^′ = 𝑥^{−1}𝑥𝑃_𝐴 = 𝑃_𝐴$.
Der folgende Code demonstriert den Angriff:```python from ecdsa.ecdsa import generator_256 from Crypto.Util.number import bytes_to_long from hashlib import sha256 import random
def hash_message(message): return bytes_to_long(sha256(message.encode()).digest())
def verify(public_key, G, message, r, s): n = G.order() if r < 1 or r > n - 1 or s < 1 or s > n-1: return False hash = hash_message(message) u1 = (hash * inverse_mod(s, n)) % n u2 = (r * inverse_mod(s, n)) % n P = u1 * G + u2 * public_key return P.x() % n == r
def sign(private_key, G, message): n = G.order() k = random.randrange(n) hash = hash_message(message)
r = (k * G).x() % n
s = inverse_mod(k, n) * (hash + r * private_key) % n
return r, s
G = generator_256 n = G.order() private_key = random.randrange(n) public_key = private_key * G
message = "Let me be the one that shines with you" r, s = sign(private_key, G, message) assert verify(public_key, G, message, r, s)
x = random.randrange(n) fake_G = x * public_key fake_private_key = inverse_mod(x, n) assert fake_private_key != private_key assert fake_G != G
evil_message = "Where did I go wrong?" r, s = sign(fake_private_key, fake_G, evil_message) assert verify(public_key, fake_G, evil_message, r, s)
In diesem Codeausschnitt wählen wir einen bekannten Generator, einen privaten Schlüssel und einen öffentlichen Schlüssel. Wir signieren eine Nachricht und stellen sicher, dass sie erfolgreich verifiziert wird. Dann erstellen wir einen gefälschten privaten Schlüssel und einen gefälschten Generator, sodass beide zum ursprünglichen öffentlichen Schlüssel passen. Eine bösartige Nachricht wird mit dem gefälschten Schlüssel signiert, und schließlich wird die gefälschte Signatur erfolgreich mit dem ursprünglichen öffentlichen Schlüssel verifiziert. Das Problem mit diesem Code ist, dass der Verifikationsalgorithmus nicht überprüft, ob der Generator `𝐺` zum öffentlichen Schlüssel passt. Obwohl wir bei diesem Angriff den privaten Schlüssel des Benutzers nicht gefunden haben, kann ein Angreifer die fehlerhafte Implementierung der Signaturverifikation ausnutzen und eine Signatur erstellen, die erfolgreich verifiziert wird. Der Angreifer kann jedoch keine „echten“ Signaturen erstellen, die in einer korrekten Implementierung der Signaturverifikation tatsächlich erfolgreich verifiziert würden.
Es ist interessant festzustellen, dass dies eine echte Sicherheitslücke ist, die in der Windows-CryptoAPI-Architektur existierte. In der Funktion, die für die Verifizierung der Signatur eines Zertifikats zuständig ist, wurden die Parameter der Kurve nicht ausreichend überprüft, wenn sie im Zertifikat selbst enthalten waren. Insbesondere wurde nicht geprüft, ob der Generator tatsächlich der Generator ist, der zum öffentlichen Schlüssel gehört. Ein Angreifer konnte gefälschte Zertifikate erstellen, die als vertrauenswürdig galten, weil sie so aussahen, als wären sie von einer vertrauenswürdigen Zertifizierungsstelle signiert worden. Dies wurde erreicht, indem bösartige Kurvenfelder zum Zertifikat hinzugefügt und der Generator auf die von mir beschriebene Weise gewählt wurde. Die Sicherheitslücke wurde von der NSA-Organisation entdeckt, im Jahr 2020 behoben und erhielt die Nummer CVE-2020-0601.
# Fazit
## Übersicht über ECDH-Angriffe
| Problemtyp | Das Problem | Der Angriff | Wie der Angriff funktioniert | Angriffskomplexität |
| ------------- | ------------- | ------------- | ------------- | ------------- |
| Auswahl einer Kurve mit einem unsicheren Generator | Die Ordnung des Generators `n` ist zu klein | Baby-Step Giant-Step | Meet In The Middle | $𝑂(\sqrt n)$ |
| Auswahl einer Kurve mit einem unsicheren Generator | Die Ordnung des Generators `n` ist eine glatte Zahl | Pohlig-Hellman | Zerlegung von `𝑛` in Primfaktoren, separater Angriff auf jeden einzelnen und Kombination der Ergebnisse mithilfe des chinesischen Restsatzes | $O(\sqrt{p_{max}})$, wobei $p_{max}$ der größte Primfaktor in der Zerlegung von `𝑛` ist |
| Auswahl einer Kurve mit einem unsicheren Generator + Auswahl eines unsicheren privaten Schlüssels | Die Ordnung des Generators `n` ist fast eine glatte Zahl, und der private Schlüssel ist klein | Improved Pohlig-Hellman | Zerlegung von `𝑛` in Primfaktoren, Verwerfen von Faktoren, die zu groß sind, separater Angriff auf jeden einzelnen und Kombination der Ergebnisse mithilfe des chinesischen Restsatzes | $O(\sqrt{p_{max}})$, wobei $p_{max}$ der größte Primfaktor in der Zerlegung von `𝑛` ist |
| Fehlerhafte Implementierung von ECDH | Nicht überprüfen, ob ein Punkt auf der Kurve liegt | Invalid Curve Attack | Senden von Punkten mit kleinen Ordnungen auf bösartigen Kurven als öffentlicher Schlüssel, separater Angriff auf jeden einzelnen und Kombination der Ergebnisse mithilfe des chinesischen Restsatzes | $𝑂(𝑛_{𝑚𝑎𝑥})$, wobei $𝑛_{𝑚𝑎𝑥}$ die größte Ordnung unter den Ordnungen der bösartigen Punkte ist |
| Unsichere Auswahl von Kurvenparametern | Die Kurve ist singulär | Reduktion von ECDLP auf DLP | Abbildung von Punkten auf Zahlen in einer Weise, die die Addition von Punkten in die Multiplikation von ganzen Zahlen überführt | $O(\sqrt{p_{max}})$, wobei $p_{max}$ der größte Primfaktor in der Zerlegung von $(p-1)$ ist |
| Unsichere Auswahl von Kurvenparametern | Die Kurve ist supersingulär | Reduktion von ECDLP auf DLP | Abbildung von Punkten auf Zahlen in einer Weise, die die Addition von Punkten in die Multiplikation von ganzen Zahlen überführt | $e^{O((log\ p^k)^{1/3}(log\ log\ p^k)^{2/3})}$, wobei `k` der Einbettungsgrad bezüglich des Generators ist |
| Unsichere Auswahl von Kurvenparametern | Die Kurve ist anomal | Smart's Attack | Eine Reihe von Abbildungen zwischen Punkten auf einer Kurve und Punkten auf einer Kurve über `p-adischen` Zahlen und zurück zu ganzen Zahlen | $O(1)$ |
## Übersicht über ECDSA-Angriffe
| Problemtyp | Das Problem | Der Angriff | Wie der Angriff funktioniert | Angriffskomplexität |
| ------------- | ------------- | ------------- | ------------- | ------------- |
| Fehlerhafte Implementierung von Signatur und Verifikation | Die Nachricht wird vor dem Signieren nicht gehasht | Ausgehend von einer signierten Nachricht: Fälschen zusätzlicher Nachrichten, die zur selben Signatur passen | Das Nachrichtenpräfix unverändert lassen und den Rest davon modifizieren | $O(1)$ |
| Fehlerhafte Verwendung des Signaturalgorithmus | Wiederverwendung desselben Werts von `k` in verschiedenen Signaturen | Finden des privaten Schlüssels des Benutzers | Finden des Werts von `k` und Berechnen des privaten Schlüssels des Benutzers daraus | $O(1)$ |
| Fehlerhafte Verwendung des Signaturalgorithmus | Unsicheres Erzeugen von `k`-Werten | Ausgehend von mehreren signierten Nachrichten: Finden des privaten Schlüssels des Benutzers | Reduktion des Problems auf das Finden eines kurzen Vektors in einem Gitter, Finden des Werts von `k` und Berechnen des privaten Schlüssels des Benutzers daraus | $O(d^6\ \log^3B)$, wobei `B` der Bias von `k` ist und `d` die Anzahl der signierten Nachrichten ist |
| Fehlerhafte Implementierung der Verifikation | Nicht überprüfen, ob der Generator gültig ist | Fälschen von Signaturen, die erfolgreich verifiziert werden (Curveball) | Auswählen von gefälschtem Generator und privatem Schlüssel, die zum öffentlichen Schlüssel eines anderen Benutzers passen | $O(1)$ |
## Schutz vor diesen Angriffen
Es sollte beachtet werden, dass bei ECDH beide Parteien zu Beginn des Protokolls die Kurve vereinbaren müssen. Wenn ein Benutzer mit einem Angreifer kommuniziert und der Angreifer die Kurvenparameter bereitstellt, kann der Angreifer unsichere Parameter bereitstellen. Infolgedessen kann der Angreifer den privaten Schlüssel des Benutzers erlangen. Wenn der Benutzer immer denselben privaten Schlüssel verwendet, kann der Angreifer alle Gespräche zwischen diesem Benutzer und jedem anderen Benutzer entschlüsseln. Deshalb ist es sehr wichtig, unbekannten Benutzern nicht zu erlauben, die Kurvenparameter bereitzustellen, wenn ihnen nicht vertraut werden kann. Außerdem muss man sicherstellen, dass jeder von einem fremden Benutzer empfangene Punkt tatsächlich auf der vereinbarten Kurve liegt. Und natürlich sollte man sicherstellen, dass die ausgewählte Kurve selbst nicht anfällig für einen der bekannten Angriffe ist, die wir gesehen haben. Außerdem ist es besser, jedes Mal, wenn das ECDH-Protokoll verwendet wird, einen neuen privaten Schlüssel zu verwenden.
Ebenso muss bei ECDSA darauf geachtet werden, die Signatur- und Verifikationsalgorithmen ordnungsgemäß zu implementieren. Man sollte den Hash der Nachricht nicht überspringen, ebenso wenig die zufällige und sichere Erzeugung des `𝑘`-Werts bei jeder Verwendung des Protokolls. Und bei der Signaturverifikation sollte man natürlich, wenn der Generator vom Benutzer empfangen wird, sicherstellen, dass es tatsächlich derjenige ist, der zuvor vereinbart wurde.
## Referenzen
- In diesem Artikel habe ich Diagramme aus dem Buch Understanding Cryptography von Christof
paar verwendet:\
https://gnanavelrec.wordpress.com/wp-content/uploads/2019/06/2.understanding-cryptography-by-christof-paar-.pdf
- Eine Website, die veranschaulicht, wie kryptografische elliptische Kurven aussehen:\
https://graui.de/code/elliptic2/
- Detaillierte Erklärung der Additions- und Multiplikationsoperationen bei elliptischen Kurven:\
https://en.wikipedia.org/wiki/Elliptic_curve_point_multiplication
- Vorlesung zur Einführung in elliptische Kurven und Punktaddition - von Christof Paar:\
https://www.youtube.com/watch?v=vnpZXJL6QCQ
- Vorlesung über Generatoren, ECDLP, Schwierigkeit von Problemen, ECDH, Double And Add - von Christof Paar:\
https://www.youtube.com/watch?v=zTt4gvuQ6sY
- Erklärung des Sicherheitsniveaus verschiedener Verschlüsselungsalgorithmen:\
https://en.wikipedia.org/wiki/Security_level
- Erklärung von ECDH:\
https://en.wikipedia.org/wiki/Elliptic-curve_Diffie%E2%80%93Hellman
- Erklärung von ECDSA:\
https://en.wikipedia.org/wiki/Elliptic_Curve_Digital_Signature_Algorithm
- Erklärung von Signaturen mit ElGamal:\
https://en.wikipedia.org/wiki/ElGamal_signature_scheme
- Erklärung des chinesischen Restsatzes:\
https://en.wikipedia.org/wiki/Chinese_remainder_theorem
- Erklärung des Zusammenhangs zwischen der Diskriminante einer singulären Kurve und der Tatsache, dass sie eine doppelte Nullstelle hat:\
https://www.quora.com/For-an-elliptic-curve-in-the-form-Y-2-X-3+AX+B-why-is-4A-3+27B-2-neq-0-the-condition-for-non-singularity
- Ein Beispiel mit kleinen Zahlen für die Abbildung zwischen Punkten und Zahlen bei singulären Kurven:\
https://crypto.stackexchange.com/questions/61302/how-to-solve-this-ecdlp/61434#61434
- Erklärungen zu 𝑝-adischen Zahlen:\
https://en.wikipedia.org/wiki/P-adic_number \
https://www.youtube.com/watch?v=3gyHKCDq1YA
- Erklärung der Mathematik hinter dem MOV-Angriff:\
https://risencrypto.github.io/WeilMOV/
- Erklärungen der Mathematik hinter dem Smart's Attack (es ist ziemlich kompliziert, Sie wurden gewarnt):\
https://wstein.org/edu/2010/414/projects/novotney.pdf \
http://www.monnerat.info/publications/anomalous.pdf
- Erklärung des gitterbasierten Angriffs und des LLL-Algorithmus:\
https://forum.vac.dev/t/lattice-attacks-on-ecdsa/136 \
\
Der Angriff basiert auf Teil 4 eines Artikels von Joachim Breitner und Nadia Heninger:\
https://eprint.iacr.org/2019/023.pdf
- Erklärung des CVP-Problems:\
https://en.wikipedia.org/wiki/Lattice_problem#Closest_vector_problem_(CVP)
- Erklärung des LLL-Algorithmus:\
https://en.wikipedia.org/wiki/Lenstra%E2%80%93Lenstra%E2%80%93Lov%C3%A1sz_lattice_basis_reduction_algorithm