[Chaos CD][Datenschleuder] [81]
  [Chaos CD]
  [Datenschleuder] [81] 1024 bit RSA Keys reichen nicht mehr
[ -- ] [ ++ ] [Suchen]  

 

1024 bit RSA Keys reichen nicht mehr

Am 23. Januar 2003 veröffentlichten Adi Shamir, einer der Entwickler des RSA Verfahrens zusammen mit Eran Tromer einen technischen Report über Spezialhardware zur Faktorisierung von grossen Zahlen. Aufhorchen liess insbesondere die Einschätzung, dass mit einem Einsatz von ungefähr 10 Millionen Euro RSA Schlüssel der Länge 1024 bit in unter einem Jahr brechbar sind.

Mathematische Grundlage

RSA, das am weitesten verbreitete Systeme für Kryptographie mit öffentlichen Schlüsseln, basiert auf dem schon lange Zeit untersuchten zahlentheoretischen Problem der Faktorisierung. Es ist benannt nach seinen Erfindern Ron Rivest, Adi Shamir und Leonard Adleman [RSA78].

Das Faktorisierunsproblem basiert auf der Tatsache, dass es sehr einfach ist, zwei ganze Zahlen zu multiplizieren (polynomineller Zeitaufwand), es allerdings bisher nicht gelungen ist, einen Algorithmus anzugeben, welcher in polynomineller Zeit die Faktoren einer hinreichend grossen Zahl bestimmen kann.

Gelingt es, die Faktorisierung des Modulus eines öffentlichen RSA-Schlüssels zu finden, ist daraus die Berechnung des geheimen Schlüssels sehr einfach möglich. Damit ist das RSA-Verfahren gebrochen: Es können unautorisierte Signaturen geleistet und in den meisten Systemen neben der aktuellen, auch die vergangene und zukünftige Kommunikation entschlüsselt werde.

Faktorisierungs-Algorithmen

Zur Bestimmung der Primfaktoren von grossen Zahlen hat die mathematische Forschung der letzten zehn Jahre Algorithmen hervorgebracht, bei denen die Komplexität sehr viel langsamer zunimmt (subexponential) als die Menge der zu betrachtenden Schlüssel.

Bei dem für praxisrelevante Schlüssellänge nach dem bisherigen Stand der Forschung mächtigsten Angriff, dem (Generalised) Number Field Sieve, kann man im wesentlichen zwei grundlegende Schritte unterscheiden:

  • Siebungsschritt
  • Beim Siebungsschritt wird eine große Zahl von Quadratzahlen mit bestimmten algebraischen Eigenschaften (smoothness) gesucht. Allgemeiner spricht man davon, dass bestimmte "Relationen gesammelt" werden. Dieser Schritt ist hochgradig parallelisierbar.
  • Matrix-Reduktion
  • Im zweiten Hauptschritt werden Abhängigkeiten in einer sehr grossen Matrix (in der Praxis mehrere Millionen Zeilen und Spalten) gesucht. Das (Generalised) Number Field Sieve (GNFS) (deutsch: Zahlkörpersieb) besitzt eine heuristische asymptotische Laufzeit von O( exp(1,92+O(1))-(ln(n))^1/3 - (ln(ln(n))^2/3 ). Hier bildet für hinreichend grosse Zahlen ln(n)^1/3 den bestimmenden Faktor.

Aktuelle Verbesserungen

Da es in den letzten zehn Jahren kaum algorithmische Verbesserungen gab, haben sich Forscher intensiv damit beschäftigt, wie man die vorhandenen Algorithmen - insbesondere das Zahlkörpersieb - besonders effizient implementieren kann. Untersucht wurde der Einsatz dedizierter Spezialhardware, für den Siebungschritte und und die Matrix-Reduktion.

1999 schlug Adi Shamir [Sham99] TWINKLE vor, ein optoelektronisches Gerät, das den Siebungsschritt erheblich beschleunigen kann. Allerdings galt Shamirs Abschätzung der Kosten für TWINKLE als wenig realistisch.

Ende 2001 veröffentlichte D.J. Bernstein [Bern2001] einen neuartigen Ansatz zur effizienten Implementation der Matrix-Reduktion vor. Bernsteins eigener Analyse zufolge war es mit seinem Ansatz erheblich schneller möglich, den Matrix-Schritt durchzuführen, als mit bisher gängigen Ansätzen. Dies lag zwar zum Teil auch daran, dass Bernstein ein anderes Kostenmaß benutzte, als andere Forscher zuvor, dennoch ermöglichte Bernsteins Ansatz signifikante Verbesserungen bei der Faktorisierung großer ganzer Zahlen, und sie regte viele Experten dazu an, die Verwendung längere Schlüssel zu empfehlen (u.a. [Weis03]).

Ausführlich analysiert und verbessert wurde die Bernstein'sche Spezialhardware von Lenstra, Shamir, Tomlinson und Tromer auf der Asiacrypt 2002 [LSTT02].

Bei der Faktorisierung mittels GNFS von bis zu 512 bit RSA-Moduli hatte sich stets gezeigt, dass der Siebungsschritt den Gesamt-Rechenaufwand dominiert. Die Autoren von [LSTT02] kommen zu dem Schluss, dass dies auch für größere RSA-Moduli gilt: "... the security of RSA relies exclusively on the hardness of the relation collection step of the number field sieve." Es bleibt die Frage, wie teuer der Siebungsschritt zum Beispiel für RSA-Moduli der Größe 1024-bit ist.

TWIRL

Auf der PKC Konferenz 2003 präsentierten Geiselmann und Steinwandt [GS03] einen Ansatz, der sich an die von Bernstein vorgeschlagene Hardware für die Matrix-Reduktion anlehnte. Im Januar 2003 schliesslich verbreiteten Shamir und Tromer vom Weizmann Institut in Israel einen Artikel (als "preliminary draft") über das Internet, der die Gedanken von Geiselmann und Steinwandt aufgriff und eine verbesserte Konstruktion präsentierte: TWIRL (The Weizmann Institute Relation Locator).

Die Kosten, die Shamir und Tromer für TWIRL angeben sind bemerkenswert:

  • TWIRL-basierte Hardware für nur 10 Millionen Euro erlaubt es, den Siebungsschritt für eine 1024-bit Zahl in einem Jahr durchzuführen (und damit die Zahl zu faktorisieren, s.o.)..
  • Zur Faktorisierung eines 512-bit Modulus reichen TWIRL-basierte Hardware für nur 10.000 Euro und weniger als 10 Minuten Zeit.

Diese Angaben sind natürlich mit Vorsicht zu genießen. Shamir und Tromer haben eine theoretische Konstruktion präsentiert, aber (noch) kein TWIRL-Gerät tatsächlich gebaut. Darauf weisen sie in ihrer Arbeit selbst ausdrücklich hin.

Einige mathematische Details

Eine Instanz eines "Sieb-Problems" besteht aus einer ganzen Zahl R, einem Schwellwert T und Paaren (ri,pi), wobei pi eine kleine Primzahl ist. Im Zusammenhang mit dem Faktorisieren von 1024-bit Zahlen können die ''kleinen'' pi grösser als 108 werden.

Die Paare (ri,pi) definieren Mengen Pi={a | a mod pi = ri}. Diese Mengen bezeichnet man als "Progressionen". Beim "Sieb-Problem" geht es darum, möglichst viele Werte a zu finden, die in vielen Progressionen liegen. Genauer, es geht darum, möglichst viele Werte a zu finden mit \sum_{i: a \in Pi} log(pi) > T.

Zum Faktorisieren mit dem Zahlkörpersieb muss man mehr als 1010 derartiger Instanzen von Sieb-Problemen lösen. Grob vereinfacht kann man Geräte wie TWIRL als Spezialhardware auffassen, die dazu dient, die Summen \sum{i: a \in Pi} log(pi) besonders effizient (d.h., unter Einsatz von möglichst wenig Chipfläche) zu berechnen.

Noch mehr Details

Die obigen Angaben zu Zeit und Kosten für eine Faktorisierung (bzw. für den Siebungsschritt) beziehen sich auf die "beste" zur Zeit bekannte Variante des Zahlkörpersiebs, die sogenannte large prime variant. TWIRL ist aber gar nicht in der Lage, alle erforderlichen Arbeitsschritte effizient durchzuführen, insbesondere nicht die sogenannte Co-Faktor Zerlegung. Wie man diesen Teilschritt mit Spezialhardware effizient durchführen und in die TWIRL Hardware integrieren kann, ist noch unbekannt. Allerdings geht es auch ohne Co-Faktor Zerlegung. Wenn das reine Zahlkörpersieb einsetzt, statt der large prime Variant, verschlechtert das Preis-Leistungsverhältnis für TWIRL. TWIRL-basierte Hardware für 50 Millionen US-$ erlaubt es, eine 1024-bit Zahl in einem Jahr zu faktorisieren. 50 Millionen Euro erscheinen für Geheimdienste oder große kriminelle Organisationen keinesfalls prohibitiv.

Erste Analyse der benötigten Hardware

Das bereits vor einiger Zeit ebenfalls von Adi Shamir veröffentlichte TWINKLE-Design [Sham99] für den Siebungsschritt basiert auf einer vergleichsweise aufwendige Chipfertigungstechnologie. Für die Multiplikation werden analoge optische Komponenten auf dem Chip eingesetzt. Dies scheint eine Fertigung in Gallium-Arsenid-Technologie vorauszusetzten, die nur an wenigen Produktionsstandorten beherrscht wird.

Weiterhin benötigt eine TWINKLE-Implementierung für 512-Bit-Keys einen kompletten Wafer mit 30cm Durchmesser. Ein einziger Fehler auf dem Wafer macht den Chip unbrauchbar. Da die Ausbeute komplett fehlerfreier Wafer sehr niedrig ist, steigen die Kosten sehr stark. Als praktische Faustregel gilt, daß die Kosten für einen Chip durch die rasch ansteigende Fehlerwahrscheinlichkeit kubisch mit der Chipfläche steigen.

Dem gegenüber steht mit TWIRL ein Design, daß sich vollständig in klassischer, Silizium-basierter VLSI-Technologie realisieren läßt. Die wichtigsten Komponenten sind hintereinandergeschaltete Digital-Addierer, DRAM, Multiplexer und kleine Prozessoren. Der erforderliche DRAM-Produktionsprozeß, Shamir und Tromer gehen von 0.13 micro Strukturgröße aus, wird mittlerweile von allen wichtigen Halbleiterproduzenten weltweit beherrscht.

Ein weiterer großer Vorteil ist die enorme Reduktion der Fläche für einen einzelnen Sieb-Chip. Die Autoren geben eine Größe von 1423 qmm; pro Chip für eine Schlüsselgröße von 1024 Bit an, womit pro Wafer 44 Chips produziert werden können. Bei einem einzelnen Fehler pro Wafer bleiben damit immer noch 43 funktionsfähige Chips übrig. Weitere Kostensenkung läßt sich durch die von den Autoren beschriebene Fehlertoleranz des Designs erreichen.

TWIRL erscheint mithin als ein realistisch implementierbares Design.

Parallelisierbarkeit und Wiedernutzbarkeit

Einige "mathematisch triviale" Gesichtspunkte wurde bisher in der öffentlichen Diskussion vernachlässigt.

  • Das Verfarhen ist beliebig parallelisierbar. Dies bedeutet, dass wer beispielsweise 12-mal so viele Hardware verwendet (für 120 Millionen Euro), braucht nur einen Monat Zeit.
  • Die teure Hardware ist nicht nach einer Faktorisierung "verbraucht". Sie kann eingesetzt werden um nacheinander mehrere Schlüssel zu "knacken".
Weiterhin ist zu bedenken, dass Angriffe nicht schlechter werden, aber man im Laufe der Zeit meistens noch weitere Verbesserungen findet.

Konsequenzen und Empfehlungen

Wenn sich die Einschätzungen von Shamir und Tromer auch nur ansatzweise bestätigen, sollten überall dort, wo Public-Key Kryptographie mit 1024-bit RSA-Schlüsseln eingesetzt wird, diese Schlüssel ausgetauscht werden. Betroffen ist der Einsatz vieler Standard-Sicherheitssoftware-Pakete (SSL, SSH, PGP, ...).

Die Alternativen zu RSA wie Diskrete Logarithmus basierte Systeme (DSA, El Gamal), insbesondere auch solche über Elliptischen Kurven, sollte angesichts der neuen Erkenntnisse intensiver untersucht werden.

In der heutigen Zeit gibt es unbestreitbar eine Menge Staaten und Organisationen, für welche beispielsweise ein paar Millionen Euro zur Brechung von wichtigen Schlüsseln eine lohnende Investition darstellen. Zudem leben wir in einer Weltlage in der selbst "befreundete" Staaten im bemerkenswerten Umfang Wirtschaftsspionage betreiben. Es dürfte unstreitbar sein, dass speziell die US-amerikanische NSA über einen umfangreichen Etat und eigene Hardwareentwicklung verfügt.

Konkret empfehlen wir,

  • 1024-bit Schlüssel baldmöglichst zu wechseln und
  • Schlüssel von mindestens 2048 bit einzusetzen.

Bemerkenswert ist, dass für die geplante TCPA/Palladium überwachungshardware ("Fritz-Chip") 2048-bit RSA Schlüssel verwendet werden.

In vielen Anwendungen (z.B. bei der E-Mail-Verschlüsselung) auf einem PC, ist der Zeitaufwand für die Public-Key Verschlüsselung unbedeutend, und der Einsatz von Schlüsseln, die deutlich länger als 2048 bit sind, empfehlenswert [WeLu99]. So erlauben die für die Verschlüsselung von E-Mail oft genutzten Programme PGP und der vom Bundeswirtschaftsministerium geförderte GNU Privacy Guard (GPG) Schlüssel, die bis zu 4096 bit lang sein können.

Literatur

  • [Bern01] Bernstein, D.J. Circuits for integer factorization, manuscript, November 2001, http://cr.yp.to/papers.html
  • [GS03] Geiselmann, W., Steinwand, R.: A dedicated Sieving Hardware. Public Key Cryptography Conference (PKC) 2003, Springer LNCS 2567, 254-266.
  • [GPG00] GNU Privacy Guard, www.gnupg.org
  • [LSTT02] Lenstra, A., Shamir, A., Tomlinson, J., Tromer, E., Analysis of Bernstein's Factorization Circuit, Proc. of Asiacrypt 2002, LNCS 2501 pp. 1-26, Springer Verlag, 2002.
  • [RSA78] Rivest, R., Shamir, A., Adleman, L.: A method for obtaining digital signatures and public-key cryptosystems, Communications of the ACM, 21(2), pp. 120-126, Februar 1978.
  • [Sham99] Shamir, A.: TWINKLE, www.jya.com/twinkle.eps
  • [ShTr03] Adi Shamir, Eran Tromer, Factoring Large Numbers with the TWIRL Device, http://www.wisdom.weizmann.ac.il/~tromer/papers/twirl.pdf, 2003.
  • [WeLu99] Weis, R., Lucks, S.: Bigger is better! Anmerkungen zur Schlüssellängendiskussion, CCC Datenschleuder #68/69, 1999.
  • [WLG99] Weis, R., Lucks, S., Geyer, W., Stand der Faktorisierungsforschung, DuD03/00, 2000.
  • [Weis02] Weis, R., "Spezialhardware bedroht möglicherweise RSA-Sicherheit", Heise News 05.03.2002, http://www.heise.de/newsticker/data/wst-05.03.02-002/

 

 

  [Chaos CD]
  [Datenschleuder] [81] Die Gedanke sind frei
[ -- ] [ ++ ] [Suchen]