4096 bit RSA gebrochen?
Mein Schreck war groß, als ich bei Fefe las, dass ein OpenPGP Key mit 4096 bit RSA faktorisiert worden sei. Kann das überhaupt sein? Ist die Kryptokalypse da?
Zuerst einmal die gute Nachricht: Es stellte sich heraus, dass jemand die Schlüssel auf den Keyservern mit einem weiteren Subkey versehen hatte. Und dieser Subkey hat die leicht zu findenden Primfaktoren 3 * 7 * 11 * … Dieser Subkey ist mit einer ungültigen (kopierten) Signatur an den Hauptschlüssel angepappt worden, so dass praktisch jede Implementation diesen Key nicht akzeptieren sollte.
Warum macht man so was? Zum einen besteht natürlich immer die Hoffnung, dass jemand doch den falschen Schlüssel benutzt und so Geheimnisse direkt für den Angreifer verschlüsselt. Natürlich in guten Glauben nur den gewünschten Partner zu erreichen. Zum anderen ist da ein Spieltrieb: Man kann halt zeigen, dass man es kann.
Hinter den Kulissen
Aber der eigentlich interessante Teil ist, was man dort versucht hat und welche Gefahren dieses Verfahren birgt. Es geht darum, die ca. zwei Millionen Schlüssel auf den Keyservern als Gesamtheit zu untersuchen.
In der Hoffnung zwei Schlüssel mit zufällig gleichem Primfaktor zu finden, vergleicht man paarweise die Schlüssel miteinander. Man bildet jeweils den größten gemeinsamen Teiler und hofft auf das große Los.
Bei 2 Mio. Schlüsseln sind das 2 Trillionen zu untersuchende Paare. Klingt viel? Mit einem Aufbau, der bei 2 GHz je ein Schlüsselpaar vergleichen kann, dauert es nur ein paar Minuten.
Es stimmt, aktuell gibt es keinen Prozessor, der in einem Taktzyklus eine ggT-Operation auf Langzahlen ausführen kann. Allerdings habe ich in der Schätzung auch alle Schlüssel unabhängig von ihrer Länge erfasst. Das würde man natürlich nicht tun, sondern gruppieren. Außerdem kann man das Verfahren bequem parallelisieren. Oder anders gesagt. Mit etwas Vorbereitung durchsucht man den kompletten Bestand der Keyserver in ein paar Tagen auf zufällige Übereinstimmungen der Primfaktoren.
Soweit so schlecht. Aber wie wahrscheinlich ist es, überhaupt Erfolg zu haben?
Unter der Annahme, die Primzahlen würden zufällig ausgewählt werden, kann man unter 10631 Zahlen wählen. Das ist im Vergleich zu den 2 Trillionen Paaren mehr als gigantisch. Die Wahrscheinlichkeit, einen Treffer zu landen ist also praktisch Null.
Ist der Zufallszahlengenerator aber nicht in Ordnung oder korreliert er zwischen verschiedenen Systemen (z.B. über eine gemeinsame Zeit initialisiert), dann steigen die Chancen ganz erheblich.
Und deswegen versucht man es halt.
Und manchmal findet man da sehr seltsame Dinge.
Ich glaube übrigens nicht dass es sich hier um einen bösartig hochgeladenen Key handelt. Ich gehe davon aus dass es schlicht irgendeine Form von Fehler ist. Es handelt sich um einen Key der überwiegend mit dem echten Subkey von hpa übereinstimmt, nur ein paar Bytes sind anders. Würde jemand einen echten Angriff versuchen würde man eher einen Key mit eigenen Primzahlen angeben, keinen offensichtlich kaputten Key. Mein Tipp wäre dass bei irgendeiner Art von Fehler - Netzwerkverbindungsabbruch, Software-Shutdown im ungünstigen Moment o.ä. - ein Keyserver einen Key fehlerhaft importiert. Anschließend wird er aufgrund des Gossip-Protokolls auf alle anderen Keyserver verteilt.
Mein Blogeintrag zum Thema:
https://blog.hboeck.de/archives/872-About-the-supposed-factoring-of-a-4096-bit-RSA-key.html
1 Kommentare