RSA-Schlüssel nicht so zufällig wie wünschenswert

Ein Team von Krypto-Spezialisten hat über 10 Millionen Public Keys untersucht und bei einigen der eingesammelten X.509-Zertifikate ernsthafte Probleme entdeckt. Denn einige Schlüssel waren bei Weitem nicht so zufällig, wie man sich das wünschen würde; über 12.000 ließen sich sogar einfach knacken.

Bei den 6.185.372 untersuchten X.509-Zertifikaten fanden die Forscher 266.729 öffentliche Schlüssel, deren Modulus mehrfach verwendet wurde. Der Modulus ist der zentrale Bestandteil des öffentlichen Schlüssels; ist er gleich, stimmt auch der geheime Schlüssel überein. In einem Extremfall wurde der gleiche Modulus 16.489 Mal vorgefunden. Konkret bedeutet dies: Jeder der Besitzer eines der 16.489 Zertifikate könnte die anderen 16.488 imitieren oder ausspionieren. Zwar merken die Forscher an, dass es durchaus nicht unüblich ist, dass man Schlüssel zum Beispiel für eine Zertifikatsverlängerung recycled. Allerdings sei ein beträchtlicher Teil dieser Schlüssel auf völlig unabhängige Eigentümer zurückzuführen.

Danach gingen die Forscher noch einen Schritt weiter und haben die gesammelten Moduli mit Hilfe des Euklidischen Algorithmus auf den Größten Gemeinsamen Teiler untersucht. Das ist zwar aufwendig, da man ja jeweils jeden Modulus mit allen anderen kombinieren muss, aber durchaus machbar. Und wenn man zwei Moduli findet, deren GGT größer als 1 ist, dann sind beide geknackt, da man damit das RSA zugrunde liegende mathematische Problem der Primzahl-Faktorisierung praktisch bereits erledigt hat. Genau das gelang der Forschergruppe mit 12.720 RSA-Schlüsseln (1024 Bit). Wo immer das möglich war, haben die Forscher die Besitzer dieser geknackten Schlüssel bereits benachrichtigt.

Auffällig ist, dass das Problem bei den ebenfalls untersuchten 5 Millionen OpenPGP-Keys in der Form nicht auftritt. Marcus Brinkmann, Mitarbeiter von g10 Code (der Firma hinter GnuPG) erklärte gegenüber heise Security, dass die wenigen redundanten OpenPGP-Schlüssel augenscheinlich bewusst wiederverwendet wurden. Auch sind alternative Krypto-Algorithmen die wie (EC)DSA und ElGamal auf den Diffie-Hellman-Verfahren beruhen, nicht betroffen. Daher rührt auch der Titel des Papers: Ron was wrong, Whit is right (PDF). Er bezieht sich auf Ron Rivest – dem R aus RSA, das sich gegen das von Whitfield Diffie mit Martin Hellman entwickelte Schlüsselaustauschverfahren durchsetzen konnte.

Eigentlich sollten bei der Schlüsselerstellung sowohl Moduli als auch Primzahl-Faktoren so zufällig gewählt sein, dass sie nicht doppelt vorkommen. Wenn das in solcher Häufigkeit vorkommt, deutet das auf ein Problem bei der Erzeugung von Zufallszahlen hin, wie auch der heisec-Artikel Gute Zahlen, schlechte Zahlen zum OpenSSL-Debakel bei Debian erläutert.

Laut Nadia Heninger, die offenbar parallel ähnliche Forschungen durchgeführt hat, stammen die schlechten Primfaktoren wahrscheinlich aus Routern, VPN-Gateways und anderen Embedded Geräten, die OpenSSL ohne eine adäquate Zufallsquelle zur Schlüsselgenerierung verwenden. Das reduziert die Gefahr, die von den redundanten Schlüsseln ausgeht, beträchtlich: "Der Schlüssel der Web-Site Ihrer Bank ist wahrscheinlich sicher" gibt Heninger Entwarnung. Trotzdem sollte man die Bedeutung der Untersuchungen nicht unterschätzen: "Das Paper leistet einen guten Beitrag zur Qualitätskontrolle der tatsächlichen Sicherheit von Krypto-Implementierungen" resümiert GPG-Mitentwickler Brinkmann; so wäre zum Beispiel das Debian-OpenSSL-Problem durch diese Arbeit gefunden worden. (ju)