Sicherheitslücke in Druckern: Über 300 Jahre alter Algorithmus knackt RSA-Keys

Drucker von Canon und Fujifilm erzeugen schwache RSA-Schlüssel, die sich mit dem Faktorisierungsalgorithmus von Fermat angreifen lassen.

Artikel von veröffentlicht am
An Internetverschlüsselung dachte Pierre de Fermat wohl noch nicht, als er vor über 300 Jahren einen Faktorisierungsalgorihtmus entwickelte.
An Internetverschlüsselung dachte Pierre de Fermat wohl noch nicht, als er vor über 300 Jahren einen Faktorisierungsalgorihtmus entwickelte. (Bild: François de Poilly)

Im Jahr 1643 hat der Mathematiker Pierre de Fermat einen Algorithmus beschrieben, mit dem sich in bestimmten Fällen die Primfaktoren einer großen Zahl schnell berechnen lassen. Voraussetzung dafür ist, dass die Primzahlen ähnlich groß sind.

Inhalt:
  1. Sicherheitslücke in Druckern: Über 300 Jahre alter Algorithmus knackt RSA-Keys
  2. Sicherheitslücke steckt in einer Bibliothek von Rambus

Das Verschlüsselungs- und Signaturverfahren RSA wiederum basiert darauf, dass die Primfaktorzerlegung von großen Zahlen schwierig ist - ein öffentlicher RSA-Schlüssel enthält einen Zahlenwert N, der das Produkt aus zwei großen Primzahlen p und q ist (N=p*q).

Der Autor dieses Textes hat versucht, mit Hilfe von Fermats Faktorisierungsalgorithmus RSA-Schlüssel aus öffentlich zugänglichen Datensätzen zu knacken. In einigen Fällen war dies erfolgreich, die Schlüssel gehörten zu TLS-Zertifikaten, deren Schlüssel von Druckern der Hersteller Fujifilm und Canon erzeugt wurden.

Algorithmus funktioniert bei zwei ähnlich großen Primzahlen

Bei korrekt erzeugten RSA-Schlüsseln scheitert Fermats Algorithmus natürlich. Wenn die beiden Primzahlen, mit denen ein RSA-Schlüssel erzeugt wurde, zufällig erzeugt wurden, unterscheiden sie sich prakisch immer bereits in den ersten Bits - und Fermats Algorithmus funktioniert nur effizient, wenn die beiden Zahlen ähnlich groß sind. Doch fehlerhafte Schlüsselerzeugungsroutinen können schwache Schlüssel erzeugen, die angreifbar sind.

Stellenmarkt
  1. R&D Software Engineer C++ (m/f/d)
    Hays AG, Sindelfingen
  2. Unix-Systemadministrator*in (m/w/d)
    IPB Internet Provider in Berlin GmbH, Berlin
Detailsuche

Fermats Faktorisierungsalgorithmus ist relativ einfach zu verstehen: Hat man eine große Zahl, die das Produkt zweier Primzahlen ist, so kann man die beiden Primzahlen als a+b und a-b definieren. Der Wert a ist dabei die Mitte zwischen den beiden Primzahlen - da große Primzahlen ungerade sind, gibt es immer einen ganzzahligen Wert in der Mitte. Der Wert b ist der Abstand von dieser Zahl in der Mitte zu den beiden Primzahlen.

Daraus ergibt sich N=(a+b)(a-b), dies lässt sich durch einfache algebraische Regeln zu b^2=a^2-N umformen.

Hacking & Security: Das umfassende Handbuch. 2. aktualisierte Auflage des IT-Standardwerks (Deutsch) Gebundene Ausgabe

Nun wird versucht, den Wert a zu raten. Wir erinnern uns: Dabei handelt es sich um die Mitte zwischen den beiden Primzahlen - und die ist bei ähnlich großen Primzahlen etwa gleich groß wie die Wurzel von N. Die Wurzel von N ist keine Ganzzahl, sie wird also zunächst gerundet.

Es wird versucht, die Mitte zwischen den Primzahlen zu erraten

Die gerundete Wurzel von N dient somit als erster geratener Wert für a. Mittels der bereits genannten Formel b^2=N-a^2 lässt sich errechnen, ob das korrekte a geraten wurde: Wenn b^2 das Quadrat einer Ganzzahl ist, wurde a richtig geraten. Falls nicht, wird der geratene Wert um eins erhöht und das Ganze wiederholt. Das kann beliebig oft wiederholt werden, je länger, desto höher die Chance, die Zahl zu faktorisieren. Bei verwundbaren Schlüsseln funktioniert das meist bei sehr wenigen Versuchen, letztendlich habe ich nach 100 Versuchen abgebrochen.

Hat man a richtig geraten, ist der Rest einfach: Man kennt nun b^2. Daraus lässt sich b berechnen und daraus die Primzahlen p und q. Wenn man die beiden Primzahlen kennt, lässt sich der gesamte private RSA-Schlüssel berechnen.

Dass es theoretisch schwache RSA-Schlüssel geben könnte, die mit diesem Algorithmus knackbar sind, ist nichts Neues. Doch nach meiner Kenntnis wurden bislang keine solchen Schlüssel gefunden, die real genutzt wurden.

Bitte aktivieren Sie Javascript.
Oder nutzen Sie das Golem-pur-Angebot
und lesen Golem.de
  • ohne Werbung
  • mit ausgeschaltetem Javascript
  • mit RSS-Volltext-Feed
Sicherheitslücke steckt in einer Bibliothek von Rambus 
  1. 1
  2. 2
  3.  


minnime 05. Apr 2022 / Themenstart

Selbst der Internetexplorer kann das darstellen, nicht das Excapte aber das MathML als...

bigpanda 18. Mär 2022 / Themenstart

Einfach Mal schauen welche Texte Hanno Böck sonst so verfasst hat. Für mich ist der Name...

Kommentieren



Aktuell auf der Startseite von Golem.de
Ebay-Kleinanzeigen
Im Chat mit den Phishing-Betrügern

Wenn man bestimmte Anzeigen in Kleinanzeigenportalen aufgibt, hat man sofort einen Betrüger an der Backe. Die Polizei kann kaum etwas dagegen tun.
Ein Bericht von Friedhelm Greis

Ebay-Kleinanzeigen: Im Chat mit den Phishing-Betrügern
Artikel
  1. Straftatbestand: Wenn Sexting zur Kinderpornografie wird
    Straftatbestand
    Wenn Sexting zur Kinderpornografie wird

    Der Straftatbestand Kinderpornografie umfasst auch Sexting unter Jugendlichen und betrifft ganze Schülerchats. Offenbar wissen viele gar nicht, wann sie strafbar handeln.

  2. Marvel: She-Hulk startet im August bei Disney+
    Marvel
    She-Hulk startet im August bei Disney+

    Die neun Episoden von She-Hulk wird es exklusiv nur bei Disney+ geben. Außerdem hat die Produktion einer weiteren Marvel-Serie begonnen.

  3. Spotify for Work: Unternehmen können Mitarbeitern Spotify-Abo schenken
    Spotify for Work
    Unternehmen können Mitarbeitern Spotify-Abo schenken

    Für Unternehmen bietet Spotify die Möglichkeit, die gesamte Belegschaft mit einem kostenlosen Spotify-Premium-Abo zu versorgen.

Du willst dich mit Golem.de beruflich verändern oder weiterbilden?
Zum Stellenmarkt
Zur Akademie
Zum Coaching
  • Schnäppchen, Rabatte und Top-Angebote
    Die besten Deals des Tages
    Daily Deals • Cyber Week: Bis zu 87€ Rabatt auf SSDs • PNY RTX 3080 12GB günstig wie nie: 974€ • Razer Basilisk V3 Gaming-Maus 44,99€ • PS5-Controller + Samsung SSD 1TB 176,58€ • MindStar (u. a. MSI RTX 3090 24GB Suprim X 1.790€) • Gigabyte Waterforce Mainboard günstig wie nie: 464,29€ [Werbung]
    •  /