Verwenden Sie RSA nicht mehr

Hallo% Benutzername%!

RSA ist der erste weit verbreitete asymmetrische Kryptografiealgorithmus, der in der Branche immer noch beliebt ist. Es ist auf den ersten Blick relativ einfach. RSA-Verschlüsselung und Signatur können auf einem Blatt Papier gezählt werden, was Studenten häufig in Laborarbeiten tun.
Aber es gibt einfach eine Vielzahl von Nuancen, ohne die selbst ein Kind Ihre RSA-Implementierung knacken kann.

Aus irgendeinem Grund denken die Leute immer noch, dass RSA ein guter Algorithmus ist. Tatsächlich ist der Spielraum für einen Schuss ins Bein bei der Implementierung von RSA jedoch extrem groß. Schwache Parameter sind schwer zu überprüfen, wenn nicht unmöglich. Und die schlechte Leistung des Algorithmus ermutigt Entwickler, riskante Methoden zu verwenden, um ihn zu verbessern.

Schlimmer noch, Polster-Orakel-Angriffe, die vor mehr als 20 Jahren erfunden wurden, sind bis heute relevant.
Selbst wenn es theoretisch möglich ist, RSA korrekt zu implementieren, ist eine solche „Leistung“ in der Praxis fast unmöglich zu erreichen. Und die seit Jahrzehnten ständig auftretenden Schwachstellen haben dies nur bestätigt.

Ein paar Worte zum RSA-Algorithmus

Wenn Sie wissen, wie RSA funktioniert, können Sie diesen Teil überspringen.

RSA ist ein Kryptosystem mit öffentlichem Schlüssel, das zwei Verwendungszwecke hat.

Die erste ist die Verschlüsselung, wenn Alice ihren öffentlichen Schlüssel veröffentlicht und Bob, der es weiß, eine Nachricht verschlüsseln kann, die nur Alice lesen kann, und sie mit ihrem privaten Schlüssel entschlüsselt.

Die zweite ist eine digitale Signatur, mit der Alice die Nachricht mit ihrem privaten Schlüssel signieren kann, sodass jeder diese Signatur mit seinem öffentlichen Schlüssel überprüfen kann.

Beide Algorithmen unterscheiden sich in unbedeutenden Details, daher werden wir sie einfach RSA nennen.

Um mit RSA arbeiten zu können, muss Alice zwei Primzahlen p und q auswählen, die zusammen eine Gruppe von Zahlen modulo N = pq bilden . Dann muss Alice einen offenen Exponenten e und einen geheimen Exponenten d so wählen, dass $$$ed = 1 \ mod (p-1) (q-1)$. Im Wesentlichen sollten e und d einfach sein.

Sobald diese Optionen ausgewählt sind, kann Bob Alice eine Nachricht M senden $$$C = M ^ e (mod \ N)$. Alice kann die Nachricht dann durch Rechnen entschlüsseln $$$M = C ^ d (mod \ N)$.
Die digitale Signatur ist genau das Gegenteil. Wenn Alice die Nachricht signieren möchte, berechnet sie die Signatur $$$S = M ^ d (mod \ N)$Bob kann dies überprüfen, indem er sicherstellt, dass die Nachricht angezeigt wird $$$M = S ^ e (mod \ N)$

Das ist alles, das ist die Hauptidee. Wir werden später zu Padding oracles zurückkehren, aber jetzt wollen wir sehen, was getan werden kann, wenn die RSA-Parameter falsch ausgewählt sind.

Anfang vom Ende

Damit RSA funktioniert, müssen Sie einige Parameter auswählen. Leider können scheinbar unschuldige Methoden ihrer Wahl die Sicherheit beeinträchtigen. Lassen Sie uns jeden einzelnen durchgehen und sehen, welche unangenehmen Überraschungen auf Sie warten.

Prime Generation

Die RSA-Sicherheit basiert auf der Tatsache, dass es schwierig ist , eine große Zahl N zu haben , die das Produkt zweier Primzahlen p und q ist , und N in Primfaktoren zu zerlegen, ohne p und q zu kennen. Die Entwickler sind für die Auswahl der Primzahlen verantwortlich, aus denen das RSA-Modul besteht. Dieser Prozess ist im Vergleich zur Schlüsselgenerierung für andere kryptografische Protokolle, bei denen es ausreicht, nur einige zufällige Bytes auszuwählen, äußerst langsam. Anstatt eine wirklich zufällige Primzahl zu generieren, versuchen Entwickler daher häufig, Zahlen mit einer bestimmten Form zu erstellen. Es endet fast immer schlecht. Es gibt viele Möglichkeiten, Primzahlen auszuwählen, so dass das Faktorisieren von N einfach ist. Zum Beispiel müssen p und q global eindeutig sein. Wenn p oder q jemals in anderen RSA-Modulen wiederverwendet werden , können beide Faktoren mithilfe des GCD-Algorithmus leicht berechnet werden. Schlechte Zufallszahlengeneratoren machen dieses Szenario ziemlich wahrscheinlich, und Studien haben gezeigt, dass ungefähr 1% des TLS-Verkehrs im Jahr 2012 einem solchen Angriff ausgesetzt war.

Darüber hinaus müssen p und q unabhängig voneinander ausgewählt werden. Wenn p und q ungefähr die Hälfte ihrer höchstwertigen Bits teilen, kann N unter Verwendung der Fermat-Methode berechnet werden. Selbst die Auswahl eines Algorithmus zum Testen der Einfachheit kann Auswirkungen auf die Sicherheit haben. Der wahrscheinlich am weitesten verbreitete Angriff ist die ROCA-Sicherheitsanfälligkeit in RSALib, von der viele Smartcards, vertrauenswürdige Plattformmodule und sogar Yubikey-Schlüssel betroffen waren. Hier werden beim Generieren von Schlüsseln nur Primzahlen einer bestimmten Form verwendet, um die Berechnungen zu beschleunigen. Die auf diese Weise erzeugten Primzahlen sind mit kniffligen Techniken in der Zahlentheorie trivial zu entdecken. Sobald ein schwaches System erkannt wurde, können die Angreifer aufgrund der speziellen algebraischen Eigenschaften von Primzahlen die Coppersmith-Methode verwenden, um N zu zerlegen .

Es sollte bedacht werden, dass in keinem dieser Fälle die Erzeugung von Primzahlen auf diese Weise eine offensichtliche Tatsache ist, die zu einem vollständigen Ausfall des Systems führt. Dies liegt daran, dass die unbedeutenden zahlentheoretischen Eigenschaften von Primzahlen einen signifikanten Einfluss auf die RSA-Sicherheit haben. Die Erwartung, dass ein gewöhnlicher Entwickler in diesem mathematischen Minenfeld navigiert, untergräbt die Sicherheit ernsthaft.

Geheimaussteller d

Da sich die Verwendung eines großen privaten Schlüssels negativ auf die Entschlüsselungs- und Signaturzeit auswirkt, haben Entwickler einen Anreiz, ein kleines d zu wählen, insbesondere bei Geräten mit geringem Stromverbrauch, wie z. B. Smartcards. Ein Angreifer kann jedoch den privaten Schlüssel wiederherstellen, wenn d kleiner als die Wurzel 4. Grades von N ist. Stattdessen sollten Entwickler einen großen Wert von d wählen, damit der chinesische Restsatz verwendet werden kann, um die Entschlüsselung zu beschleunigen. Die Komplexität dieses Ansatzes erhöht jedoch die Wahrscheinlichkeit geringfügiger Implementierungsfehler, die zur Schlüsselwiederherstellung führen können.

Sie sagen, dass Sie normalerweise während der RSA-Initialisierung zuerst ein Modul generieren, einen festen offenen Exponenten verwenden und dann ein Geheimnis auswählen?
Ja, dies verhindert Angriffe mit einem kleinen geheimen Exponenten, wenn Sie immer einen der empfohlenen offenen Exponenten verwenden. E.
Leider setzt dies auch voraus, dass die Entwickler dies wirklich tun werden. In der realen Welt machen Entwickler oft seltsame Dinge, zum Beispiel wählen Sie zuerst d und betrachten dann e .

Offener Aussteller e

Wie beim geheimen Aussteller möchten Entwickler kleine offene Aussteller verwenden, um Verschlüsselung und Signaturüberprüfung zu sparen. Typischerweise werden in diesem Zusammenhang Fermat-Primzahlen verwendet, insbesondere e = 3, 17 und 65537.

Trotz der Tatsache, dass Kryptographen die Verwendung von 65537 empfehlen, wählen Entwickler häufig e = 3, was zu vielen Schwachstellen im RSA-Kryptosystem führt.


(Hier verwendeten die Entwickler e = 1, wodurch Klartext überhaupt nicht verschlüsselt wird.)

Wenn e = 3 oder eine ähnliche Größe ist, kann viel schief gehen. Kleine offene Exponenten werden oft mit anderen häufigen Fehlern kombiniert, die es einem Angreifer ermöglichen, bestimmte Chiffretexte oder Faktoren N zu entschlüsseln.

Beispielsweise ermöglicht ein Franklin-Reuters-Angriff einem Angreifer, zwei Nachrichten zu entschlüsseln, die über eine bekannte feste Entfernung verbunden sind. Mit anderen Worten, Alice schickt Bob nur "kaufen" oder "verkaufen". Diese Nachrichten werden einem bekannten Wert zugeordnet und ermöglichen es einem Angreifer, zu bestimmen, welche davon "Kaufen" und welche "Verkaufen" bedeuten, ohne die Nachricht zu entschlüsseln. Einige Angriffe mit kleinem e können sogar zur Schlüsselwiederherstellung führen.

Wenn der offene Exponent klein ist (nicht nur 3), kann ein Angreifer, der mehrere Bits des geheimen Schlüssels kennt, die verbleibenden Bits wiederherstellen und das Kryptosystem zerstören. Obwohl viele dieser e = 3-RSA-Angriffe durch Auffüllen behoben werden können, vergessen Entwickler, die den RSA selbst implementieren, häufig, ihn zu verwenden.

RSA-Signaturen sind auch für kleine öffentliche Aussteller anfällig. Im Jahr 2006 entdeckte Bleichenbacher einen Angriff , mit dem Angreifer in vielen RSA-Implementierungen, einschließlich der in Firefox und Chrome verwendeten, willkürliche Signaturen fälschen können. Dies bedeutet, dass jedes TLS-Zertifikat einer anfälligen Implementierung manipuliert werden kann. Dieser Angriff nutzt die Tatsache aus, dass viele Bibliotheken einen kleinen öffentlichen Exponenten verwenden und bei der Verarbeitung von RSA-Signaturen keine einfache Ausrichtungsprüfung durchführen. Bleichenbachers Angriff auf die Signatur ist so einfach, dass er in vielen Übungen in Kryptographiekursen enthalten ist.

Die Auswahl von Optionen ist eine schwierige Aufgabe

Allen diesen Angriffen auf Parameter ist gemeinsam, dass die Gesamtzahl der möglichen Varianten von Parametern viel größer ist als die Anzahl der sicheren Varianten.

Es wird davon ausgegangen, dass die Entwickler diesen komplexen Auswahlprozess selbst verwalten, da bei der Initialisierung alles außer dem offenen Exponenten generiert werden muss.
Es gibt keine einfachen Möglichkeiten, die Zuverlässigkeit von Parametern zu überprüfen . Stattdessen benötigen Entwickler eine seriöse mathematische Basis, deren Anwesenheit von normalen Mitarbeitern nicht erwartet werden sollte. Obwohl die Verwendung von RSA mit Ausrichtung Sie retten kann, wenn Sie die falschen Parameter haben, ziehen es viele dennoch vor, dies nicht zu tun.

Auffüllen von Oracle-Angriffen

Wie oben erläutert, funktioniert die sofortige Verwendung von RSA nicht ganz. Beispielsweise werden mit dem in der Einführung beschriebenen RSA-Schema identische Chiffretexte erstellt, wenn derselbe Klartext jemals mehr als einmal verschlüsselt wurde. Dies ist ein Problem, da ein Angreifer den Inhalt einer Nachricht aus dem Kontext lernen kann, ohne sie entschlüsseln zu können. Aus diesem Grund müssen wir Nachrichten mit einigen zufälligen Bytes ausrichten. Leider ist das am weitesten verbreitete Ausrichtungsschema, PKCS # 1 v1.5, häufig anfällig für den sogenannten Padding-Orakel-Angriff.

Der erste Angriff auf PKCS # 1 v1.5 wurde bereits 1998 von Daniel Bleikhanbacher entdeckt. Trotz der Tatsache, dass sie über 20 Jahre alt ist, ist sie auch heute noch für viele Systeme relevant. Moderne Versionen dieses Angriffs enthalten häufig ein zusätzliches Orakel, das etwas komplizierter ist als das ursprünglich von Bleikhanbacher beschriebene, z. B. die Serverantwortzeit oder die Ausführung eines Protokoll-Downgrades in TLS. Ein besonders schockierendes Beispiel war der ROBOT- Angriff, der so schrecklich war, dass ein Forscherteam Nachrichten mit geheimen Facebook- und PayPal-Schlüsseln signieren konnte. Einige könnten argumentieren, dass dies nicht wirklich die Schuld von RSA ist - grundlegende Mathematik ist in Ordnung, die Leute haben vor Jahrzehnten einen wichtigen Standard durcheinander gebracht. Tatsache ist, dass wir bereits seit 1998 ein Standard-Ausrichtungsschema mit strengen Sicherheitsnachweisen hatten, OAEP. Aber fast niemand benutzt es. Selbst wenn dies geschieht, ist es allgemein bekannt, dass OAEP schwierig zu implementieren ist und häufig anfällig für einen Manager-Angriff ist, bei dem es sich um einen weiteren Orakelangriff handelt, mit dem Klartext wiederhergestellt werden kann.

Das grundlegende Problem hierbei ist, dass bei Verwendung von RSA eine Ausrichtung erforderlich ist und diese zusätzliche Komplexität einen großen Spielraum für Angriffe auf das Kryptosystem eröffnet. Die Tatsache, dass eine Information, „ob die Nachricht richtig ausgerichtet wurde“, einen so großen Einfluss auf die Sicherheit haben kann, dass die Entwicklung sicherer Bibliotheken praktisch unmöglich ist. TLS 1.3 unterstützt RSA nicht mehr, sodass wir in Zukunft weniger solcher Angriffe erwarten können.

Während Entwickler RSA weiterhin in ihren eigenen Anwendungen verwenden, werden Padding Oracle-Angriffe weiterhin auftreten.

Was zu tun ist?

Menschen bevorzugen häufig die Verwendung von RSA, weil sie es konzeptionell einfacher finden als das verschlungene DSA-Protokoll oder die Kryptographie mit elliptischen Kurven (ECC). Obwohl RSA intuitiver ist, fehlt ihm wirklich der Schutz vor dem Narren.

Zuallererst ist ein häufiges Missverständnis, dass die Ellipse sehr gefährlich ist, weil die Wahl einer schlechten Kurve alles zunichte machen kann. Die Kurvenauswahl hat zwar einen großen Einfluss auf die Sicherheit, aber einer der Vorteile der Verwendung von ECC besteht darin, dass die Parameterauswahl öffentlich erfolgen kann. Kryptografen treffen die Auswahl der Parameter für Sie, sodass Entwickler nur zufällige Datenbytes generieren müssen, um sie als Schlüssel zu verwenden. Entwickler können theoretisch eine ECC-Implementierung mit schrecklichen Parametern erstellen und können nicht nach falschen Kurvenpunkten suchen, dies ist jedoch normalerweise nicht der Fall. Die wahrscheinliche Erklärung ist, dass die Mathematik hinter ECC so komplex ist, dass nur sehr wenige Menschen sich sicher genug fühlen, sie umzusetzen. Mit anderen Worten, diese Angst zwingt die Menschen dazu, Bibliotheken zu benutzen, die von Kryptographen erstellt wurden, die sich mit ihren Sachen auskennen. RSA hingegen ist so einfach, dass es in einer Stunde (schlecht) implementiert werden kann.

Zweitens erfordert jede Schlüsselübereinstimmung, die auf dem Diffie-Hellman-Algorithmus oder dem Signaturschema basiert (einschließlich Optionen für elliptische Kurven), keine Ausrichtung und ist daher vollständig resistent gegen Padding Oracle-Angriffe. Dies ist ein großer Sieg, da die RSA seit langem versucht, diese Klasse von Schwachstellen zu vermeiden.

Wir empfehlen die Verwendung von Curve25519 für den Schlüsselaustausch und ed25519 für digitale Signaturen. Die Verschlüsselung sollte mit dem ECIES-Protokoll durchgeführt werden, das den ECC-Schlüsselaustausch mit einem symmetrischen Verschlüsselungsalgorithmus kombiniert. Curve25519 wurde entwickelt, um Angriffsklassen, die anderen Kurven passieren könnten, vollständig zu verhindern, und es ist auch sehr schnell. Darüber hinaus ist es in vielen Bibliotheken implementiert, beispielsweise in libsodium, das mit einer einfach zu lesenden Dokumentation ausgestattet ist und in den meisten Sprachen verfügbar ist.

Verwenden Sie RSA nicht mehr. Im Ernst.

(Twilio verwendet immer noch RSA-Schlüssel)


(Travis CI verwendet immer noch 1024-Bit-Schlüssel und erlaubt nicht, diese zu ersetzen.)

RSA war ein wichtiger Meilenstein in der Entwicklung sicherer Kommunikation, aber die letzten zwei Jahrzehnte der kryptografischen Forschung haben es überholt. Algorithmen für elliptische Kurven sowohl für den Schlüsselaustausch als auch für digitale Signaturen wurden bereits 2005 standardisiert und seitdem in Bibliotheken wie libsodium integriert, die intuitiv und missbrauchsresistent sind. Die Tatsache, dass RSA heute noch weit verbreitet ist, weist sowohl auf einen Fehler von Kryptographen aufgrund einer unzureichenden Beschreibung der mit RSA verbundenen Risiken als auch von Entwicklern hin, die ihre Fähigkeit zur erfolgreichen Bereitstellung überschätzen. Die Sicherheitsgemeinschaft sollte anfangen, dies als Herdenproblem zu betrachten. Obwohl einige von uns möglicherweise in der Lage sind, den äußerst gefährlichen Prozess der Einrichtung oder Implementierung von RSA zu steuern, machen Ausnahmen den Entwicklern klar, dass RSA in gewisser Weise immer noch relevant ist. Trotz der vielen Vorbehalte und Warnungen bei StackExchange und GitHub README glauben nur sehr wenige Menschen, dass sie die RSA ruinieren werden, und handeln daher weiterhin rücksichtslos. Letztendlich werden Ihre Benutzer dafür bezahlen. Deshalb müssen wir uns alle einig sein, dass die Verwendung von RSA im Jahr 2019 völlig inakzeptabel ist. Keine Ausnahmen.

Originalartikel in Englisch.

VirgilSecurity, Inc. Entwickelt ein Open Source-Entwickler-freundliches SDK und Datenschutzdienste. Wir ermöglichen Entwicklern, vorhandene Algorithmen mit minimalem Sicherheitsrisiko zu verwenden.

PS Ich empfehle, dass Sie auch über das Einbetten einer Hintertür in den öffentlichen RSA-Schlüssel lesen.