Skip to content

RSA und die schwachen Schlüssel, Teil 2: Die Schlüssel

Im ersten Teil haben Sie erfahren, wie RSA funktioniert. Werfen wir jetzt also einen Blick auf das aktuelle Problem: Die von Forschern entdeckten unsicheren Schlüssel.

Die Ergebnisse von Arjen K. Lenstra et al.

Das erste Paper stammt von Arjen K. Lenstra, James P. Hughes, Maxime Augier, Joppe W. Bos, Thorsten Kleinjung und Christophe Wachter. Sie haben im Internet rund 11,7 Millionen Public Keys gesammelt und untersucht:

  • 6.185.372 unterschiedliche X.509-Zertifikate, wie sie z.B. für SSL/TLS verwendet werden, von denen
    • 6.185.230 einen RSA-Public-Key (Modulus und Exponent) enthielten,
    • 141 einen DSA-Public-Key und
    • eins einen ECDSA-Schlüssel.
  • 5.481.332 PGP-Schlüssel, von denen
    • 2.546.752 einen ElGamal-Public-Key enthielten,
    • 2.536.959 einen DSA-Public-Key und
    • 397.621 einen RSA-Public-Key

Im folgenden werde ich nur auf die Ergebnisse der Analyse der RSA-Schlüssel eingehen. Ein öffentlicher RSA-Schlüssel besteht, wie Sie ja aus dem ersten Teil wissen, aus dem Exponenten c und dem Modulus n. Die Exponenten wurden nicht weiter untersucht, es gibt lediglich eine Liste der zehn am häufigsten verwendeten. Alle folgenden Untersuchungen konzentrierten sich auf die Moduli.

Zwei davon wurden nicht weiter untersucht, da sie auf die von 2006 bis 2008 von Debian erzeugten schwachen Schlüssel zurückzuführen waren und vollständig faktorisiert werden konnten. Weitere 30097 Moduli waren ebenfalls als schwache Debian-Schlüssel geblacklistet, wurden aber in die Untersuchungen einbezogen, da eine einfache Faktorisierung nicht möglich war.

266.729 potentiell unsichere Schlüssel in Zertifikaten

Die 6.185.230 X.509-Zertifikate mit RSA-Schlüssel wurden so in Cluster aufgeteilt, dass alle Zertifikate eines Clusters den gleichen RSA-Modulus verwendeten. Dabei wurden insgesamt 266.729 Zertifikate gefunden, deren RSA-Modulus mit dem eines anderen Zertifikats übereinstimmt. Je ein Cluster enthielt 16.489, 8.366, 6.351, 5.055, 3.586, 3.538 und 2.645 Zertifikate, gefolgt von 14 Clustern mit jeweils mehr als 1.000 Zertifikaten. Aber was bedeutet das, bzw. wie schlimm ist das? Nun, im Grunde bedeutet das schlicht und ergreifend, dass in so einem Cluster jeder Zertifikatsinhaber die geheimen Schlüssel aller anderen Zertifikatsinhaber berechnen kann, wie Sie gleich erkennen werden.

Zuerst halten wir mal fest, was jeder Zertifikatsinhaber weiß:
Er kennt den Modulus n (und damit p und q, aus denen n gebildet wurde), seinen geheimen Exponenten d und seinen öffentlichen Exponenten c. Die Exponenten sind in diesem Fall aber irrelevant. Betrachten wir, was passiert, wenn ein Zertifikatsinhaber einen anderen Schlüssel (c',n) findet, der den gleichen Modulus n wie sein Schlüssel verwendet.

Dazu werfen wir einen Blick auf die Beschreibung von RSA im ersten Teil, konkret die Schlüsselerzeugung.
Der Zertifikatsinhaber (den wir jetzt wohl ruhig Angreifer nennen dürfen) kennt n = p * q und damit auch φ(n) = (p-1) * (q-1) sowie den öffentlichen Exponenten c' seines Opfers. Was ihm noch fehlt, ist dessen geheimer Exponent d'. Und der wird laut Schritt 4 der Schlüsselerzeugung wie folgt berechnet:

Berechne d' aus p, q und c' als multiplikatives Inverses von c' modulo φ(n), also c' * d' ≡ 1 mod φ(n).
Dazu wird der erweiterte euklidische Algorithmus verwendet.

Der Angreifer muss also nur genau den Schritt durchführen, den er zuvor zur Berechnung seines eigenen privaten Exponenten durchgeführt hat, nur diesmal mit dem öffentlichen Exponenten seines Opfers statt seines eigenen. Und schon kennt er den geheimen Schlüssel seines Opfers.

Wieso "potentiell unsichere" Schlüssel?

Mit "potentiell unsicher" möchte ich diese Schlüssel von den noch folgenden komplett gebrochenen Schlüsseln abgrenzen. Die "potentiell unsicheren" Schlüssel können nur von Zertifikatsinhabern gebrochen werden, die den gleichen Modulus wie das Opfer verwenden (was im schlimmsten Fall des Clusters mit 16.489 Mitgliedern immer noch 16.488 mögliche Opfer ergibt, falls einer der Zertifikatsinhaber bösartig ist).

Es gibt aber eine weitere Einschränkung: Viele der potentiell unsicheren Zertifikate waren erneuerte Zertifikate oder ergaben sich aus "other types of unsuspicious recycling of the same key material by its supposedly legal owner.". Aber es blieben auch viele Zertifikate übrig, bei denen anscheinend voneinander unabhängige Zertifikats-Inhaber den gleichen Modulus verwenden. In wie vielen Fälle diese gemeinsamen Moduli Absicht waren, konnte nicht festgestellt werden und wurde auch nicht weiter untersucht.

12.720 gebrochene Schlüssel

Außer die Moduli in Gruppen einzuteilen, haben die Forscher auch weitere Untersuchungen angestellt. Und zwar wurden die Moduli mit Hilfe des erweiterten euklidischen Algorithmus auf den größten gemeinsamen Teiler untersucht. Werden zwei Moduli gefunden, deren ggT größer als 1 ist, sind beide zugehörigen Schlüssel gebrochen, da die Moduli in ihre Primfaktoren zerlegt werden können:

  • Es gibt zwei Schlüssel mit Modulus
    n = p * q   bzw.   n' = p' * q'
  • p, q, p' und q' sind bekanntlich Primzahlen, d.h. sie sind nur durch sich selbst und 1 teilbar.
  • Wenn ggT(n,n') = r ist, dann muss r mit p oder q sowie mit p' oder q' identisch sein.
    Nehmen wir mal an, es gilt r=p=p'
  • Dann ergibt sich
    n = r * q   und   n' = r * q'
  • Und damit erhält man
    q = n / r   und   q' = n' / r
  • Aus den nun bekannten Primfaktoren und den öffentlichen Exponenten c und c' lassen sich dann wie oben zu sehen ist die geheimen Exponenten d und d' berechnen.

Das ganze mal mit einem Zahlenbeispiel:

  • Benutzer A wählt die Primzahlen p = 5 und q = 3 und berechnet daraus sein n = 5 * 3 = 15
    Benutzer B wählt unabhängig davon und ohne von A zu wissen die Primzahlen p' = 5 und q' = 17 und berechnet daraus sein n' = 5 * 17 = 85
  • Der Angreifer berechnet ggt(n,n') = 5 und kennt damit einen der Primfaktoren: p = p' = 5
  • Der Angreifer weiß nun, dass n = 15 = 5 * q und n' = 85 = 5 * q' ist,
    daraus berechnet er q = 15 / 5 = 3 und q' = 85 / 5 = 17
  • Da er auch die öffentlichen Exponenten c und c' kennt, kann er daraus und aus den soeben berechneten Primfaktoren die zugehörigen geheimen Exponenten d und d' berechnen.
  • Und da er nun beide geheimen Schlüssel kennt, kann er Nachrichten an die Benutzer A und B entschlüsseln sowie ihre Signatur unter beliebigen Nachrichten fälschen.

Das klingt nicht nur schlimm, sondern das ist schlimm, denn für die betroffenen Benutzer sind ihre Schlüssel damit vollkommen nutzlos. Arjen K. Lenstra und seine Kollegen haben 12.720 RSA-Schlüssel mit einer heute noch üblichen Länge von 1024 Bits gefunden, die sie so brechen konnten.

In der nächsten Folge werden die weiteren Forschungsergebnisse untersucht, außerdem gibt es eine Einschätzung der sich daraus ergebenden Gefährdung.

Carsten Eilers


Übersicht über alle Artikel zum Thema

RSA und die schwachen Schlüssel, Teil 1: Einführung in RSA
RSA und die schwachen Schlüssel, Teil 2: Die Schlüssel
RSA und die schwachen Schlüssel, Teil 3: Die Gefahren

Trackbacks

Dipl.-Inform. Carsten Eilers am : SSL - Der nächste Nagel im Sarg?

Vorschau anzeigen
Es gibt mal wieder schlechte Nachrichten über SSL. Diesmal wurde mal keine Zertifizierungsstelle gehackt, stattdessen haben Forscher festgestellt, dass die Prüfung von Zertifikaten in anderer Software als Webbrowsern ziemlich mangelhaft