Wie lange würde es dauern, eine 1024-Bit-OpenPGP-verschlüsselte E-Mail zu beschädigen?

9

Für WPA gibt es Taschenrechner, um die Zeit zu bestimmen, die zum Knacken einer Passphrase benötigt wird, aber ich habe nichts für OpenPGP gefunden.

Wie lange würde es dauern, eine 1024-Bit-OpenPGP-verschlüsselte E-Mail zu brechen (abhängig von der CPU-Leistung)?

Ich interessiere mich auch für andere Schlüsselgrößen wie 2048 und 4096.

Kelmat
quelle

Antworten:

7

Während die Antwort von @Jens Erat ziemlich umfassend war, habe ich nachgeforscht, wie man RSA (den Algorithmus hinter OpenPGP) bricht, also wollte ich sagen:

Ich werde mit der Norm brechen und die TL geben; DR zuerst: Es ist unmöglich für Sie, diesen Schlüssel zu brechen. Wenn wir dies realistisch betrachten, gibt es für Sie keine Möglichkeit, eine 1024-Bit-Ganzzahl zu faktorisieren. Ihre bestmögliche Wette wäre der Versuch, einen anderen Teil der Sicherheitskette zu durchbrechen (z. B. den Desktop, auf dem der Empfänger seine E-Mails abruft).

Betrachten wir mögliche Strategien, wenn der Realismus aus dem Weg ist:

  • Blindes Raten / Brute Forcing. Mit einer 1024-Bit-Semiprime besteht kaum eine Chance, dass dies jemals funktionieren wird. Es wäre besser, wenn Sie Ihre Zeit zufällig nutzen und versuchen, Lotterienummern zu erraten.

  • Regenbogentabelle generieren. Nehmen Sie das Rätselraten aus dem Factoring heraus, indem Sie jede Primzahl unter 2 ^ 1024 nehmen und mit jeder anderen Primzahl multiplizieren und das Ergebnis in einer Tabelle speichern. Dann müssten Sie nur noch das richtige Paar suchen. Wie Sie sich vorstellen können, ist auch dies unmöglich. Dies würde x beinhalten! Paare für x Anzahl von Primzahlen. Durch die Prime-Zählfunktion , Sie suchen bei etwa 2,95 * 10 ^ 307 Primzahlen - zum Vergleich, es wird geschätzt , dass die Zahl der Atome im Universum obserable auf der Größenordnung von 10 ^ 83 ist, so dass selbst wenn wir könnten Lassen Sie jedes Atom zwei Primzahlen und ihr Produkt so speichern, dass unser Computer es indizieren könnte. Es wäre unmöglich.

  • Verwenden Sie das Feldsieb für allgemeine Nummern . Das GNFS ist die beste Wahl, um eine große Semiprime zu berücksichtigen. Es wurde von Kleinjung und seinem Team verwendet, um RSA-768, eine 768-Bit-Semiprime, zu faktorisieren. Leider hat sein Team über drei Jahre gebraucht, um dies zu erreichen, und es ist um Größenordnungen kleiner als die Zahlen, die Sie berücksichtigen möchten. Selbst wenn Sie Millionen von Dollar (pro Tag) für die Vermietung der besten Supercomputer mit voller Kapazität ausgeben würden, wäre es nahezu unmöglich, die Anzahl zu berücksichtigen. Der erste Schritt von GNFS besteht darin, genügend "Beziehungen" zu finden, mit denen die Teilprobleme gelöst werden können. Dies kann sehr lange dauern.

Ihr letzter Ausweg ist die Verwendung eines Quantencomputers, mit dem Sie die Zahlen in einer realisierbaren Zeitspanne faktorisieren können. Leider müssen diese noch bis zu einem nützlichen Punkt entwickelt werden. Daher können wir derzeit keine Semiprimes mit 1024 Bit und mehr (und damit die darauf basierenden Algorithmen) faktorisieren.

ahjohnston25
quelle
20

Zunächst gehe ich davon aus, dass Sie von RSA 1024-Bit-Verschlüsselung sprechen.

Im Allgemeinen ist das Thema viel zu kompliziert, um eine einfache Nummer anzugeben.

tl; dr : Das Knacken einer OpenPGP-verschlüsselten Nachricht auf einer einzelnen CPU ist nicht möglich und dauert wahrscheinlich selbst bei großen Computerclustern Jahre. Unbekannte (der Öffentlichkeit) mathematische Mängel könnten dies jedoch um eine Größenordnung ändern, wie dies Quantencomputer zu einem späteren Zeitpunkt tun könnten (weit entfernt vom Standpunkt des "Internetzeitalters").

Die etwas längere Version:

Knacken der asymmetrischen Verschlüsselung (RSA 1024-Bit-Schlüssel)

Dies gilt neben RSA 1024-Bit-Schlüsseln auch für größere Schlüsselgrößen. Größere Schlüssel bieten mehr Sicherheit (in Form von Rechenleistung, um sie zu knacken), aber denken Sie daran, dass die Sicherheit nicht linear mit der Schlüsselgröße zunimmt.

Es gibt einen schönen Beitrag im Information Security Stack Exchange: "Wie kann man die Zeit abschätzen, die zum Knacken der RSA-Verschlüsselung benötigt wird?" Dies schließt nicht mit einer Schätzung wie "Mit einem Core i7-Modell xy können Sie einen RSA 1024-Bit-Schlüssel in geschätzten z Stunden knacken" ab, aber die Antworten stimmen überein mit "RSA 1024-Bit-Schlüssel können nicht von Einzelpersonen geknackt werden mit normalerweise verfügbarer Rechenleistung (dh einer Handvoll High-End-Maschinen) in angemessener Zeit.

Die Diskussion, 1024-Bit-Schlüssel mit viel mehr Rechenleistung zu brechen, wurde nur aus akademischer Sicht betrachtet:

Ich habe kürzlich erfahren, dass die Auswahl der Parameter für eine 1024-Bit-Zahlenfaktorisierung begonnen hat (das ist der "kluge" Teil); Das Sieben ist technisch machbar (es ist teuer und erfordert jahrelange Rechenzeit in vielen Universitätsclustern), aber im Moment weiß niemand, wie der lineare Reduktionsteil für eine 1024-Bit-Ganzzahl ausgeführt wird. Erwarten Sie also keine baldige 1024-Bit-Unterbrechung.

Dies gilt wahrscheinlich auch für große, gut finanzierte Institutionen mit viel Rechenleistung wie die NSA.

Die Dinge könnten sich schnell ändern, wenn

  • Jemand findet einen mathematischen Fehler, der die Komplexität von RSA um Größenordnungen verringert (einige Institutionen wie die NSA beschäftigen eine große Anzahl großer Mathematiker), oder
  • Quantencomputer funktionieren endlich und werden leistungsfähig genug und in der Lage, bestimmte Algorithmen auszuführen. Wird in den nächsten Jahren nicht erwartet.

Für DSA / ElGamal sieht das etwas anders aus. Ein DSA-Schlüssel mit der gleichen Größe wie ein RSA-Schlüssel bietet mehr Sicherheit, gleichzeitig ist DSA jedoch anfälliger für schlechte Zufallszahlen (vergleiche mit dem Fehler des Debian-Zufallszahlengenerators ). Die Kryptografie mit elliptischen Kurven, die derzeit für OpenPGP verfügbar ist, hat noch keine bekannten Angriffe für die unterstützten Algorithmen und wird allgemein als sicher angesehen. Insbesondere bei den von NIST empfohlenen Kurven bestehen jedoch noch Zweifel (NIST hat den Ruf verloren, einen gebrochenen Zufall zu erstellen Zahlengenerator ein Standard) und einige Implementierungs-Nitpicks.

Die symmetrische Verschlüsselung knacken

OpenPGP verwendet eine Hybridverschlüsselung, sodass die Nachricht mit symmetrischer Verschlüsselung und einem zufälligen symmetrischen Schlüssel (in OpenPGP, häufig als "Sitzungsschlüssel" bezeichnet) verschlüsselt wird. Dieser Sitzungsschlüssel wird erneut mit dem asymmetrischen Verschlüsselungsalgorithmus verschlüsselt, z. RSA.

Wenn Sie den symmetrischen Verschlüsselungsschlüssel einer Nachricht knacken können, können Sie die Nachricht auch lesen (im Gegensatz zum Knacken des asymmetrischen Schlüssels, bei dem Sie alle mit diesem Schlüssel verschlüsselten Nachrichten lesen können).

Anders als bei sehr frühen Versionen von PGP (die einen von Zimmermann selbst entwickelten symmetrischen Verschlüsselungsalgorithmus namens BassOmatic verwendeten , der als defekt gilt), haben alle für OpenPGP definierten symmetrischen Algorithmen keine relevanten bekannten Angriffe.

Sofern sich niemand für die Verwendung einer symmetrischen Verschlüsselung entschieden hat (was tatsächlich möglich ist!), Sollte das Unterbrechen einer Nachricht mithilfe des symmetrischen Verschlüsselungsalgorithmus derzeit nicht als machbar angesehen werden.

Jens Erat
quelle
Ich muss fragen ... ist die Rechtschreibfehler von "asymmetrisch" beabsichtigt?
David Z
Nein, natürlich nicht; Weder war "copmuting". Vielen Dank, dass Sie mich benachrichtigt haben.
Jens Erat
Es gibt keinen "DES-Schlüssel mit der gleichen Größe wie ein RSA-Schlüssel". DES verwendet 56-Bit-Schlüssel, Punkt . Es wird nur mit 56-Bit-Schlüsseln definiert. Sie können DES nicht mit einer anderen Schlüsselgröße ausführen. Es ist auch nicht anfällig für schlechte Zufallszahlen, da DES zu keinem Zeitpunkt im Algorithmus Zufallszahlen verwendet (und auch kein anderes Blockverschlüsselungsprimitiv). Bestimmte Verwendungen davon können einen zufälligen Aspekt beinhalten (z. B. muss eine IV für den CBC-Modus zufällig sein), aber DES selbst ist vollständig deterministisch. DES wird auch nicht mehr verwendet (Triple DES wird gelegentlich verwendet, DES selbst jedoch nie). Sind Sie sicher, dass Sie über DES sprechen wollten?
cpast
Natürlich wollte ich nicht . DES mit DSA zu verwechseln, hätte nicht passieren dürfen. DES, PGP, RSA, NSA, DSA: Wir brauchen weniger Akronyme mit drei Buchstaben!
Jens Erat
Die meisten 1024-Bit-OpenPGP-Schlüssel (im Gegensatz zu SSL / TLS-Schlüsseln) sind DSA und nicht RSA. Ich finde online jede Menge Diskussionen über das Knacken von 1024-Bit-RSA, aber wenig über das Knacken von 1024-Bit-DSA.
Plugwash