Ruediger Weis, Stefan Lucks, Andreas Bogk
Am 23. Januar 2003 veröffentlichten Adi Shamir, einer der Entwickler des RSA Verfahrens zusammmen 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.
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 unauthorisierte Signaturen geleistet und in den meisten Systemen neben der aktuellen, auch die vergangene und zukünftige Kommunikation entschlüsselt werde.
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:
Das (Generalised) Number Field Sieve (GNFS) (deutsch: Zahlkörpersieb) besitzt eine heuristische asymptodische 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.
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 Implemenation 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."
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).
Das Kosten die Shamir und Tromer für TWIRL angeben sind bemerkenswert:
50 Millionen Euro erscheinen für Geheimdienste oder große kriminelle Organisationen keinesfalls prohibitiv.
Die Paare (r
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.
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
ist 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µ 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 mm² 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.
Man beachte weiterhin, dass die teuere Hardware nicht nach
einer Faktorisierung „verbraucht" ist, sondern eingesetzt werden kann, um
nacheinander mehrere Schlüssel zu „knacken". Und, vom Standpunkt der
Zukunftssicherheit, ist zu bedenken, dass Angriffe nicht schlechter werden,
aber man im Laufe der Zeit meistens noch weitere Verbesserungen findet.
In der heutigen Zeit gibt es unbestreitbar eine Menge Staaten und Organisationen,
für welche beispielsweise ein paar Millionen Euro zur Brechung einer
PKI 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.
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.
Parallelisierbarkeit und Wiedernutzbarkeit
Einige "mathematisch triviale" Gesichtspunkte wurde bisher in der
öffentlichen Diskussion vernachlässigt.
Das Verfarhen ist beliebig parallelisierbar - wer z.B. 12-mal so viele
Hardware baut (für 120 Millionen Euro), braucht nur einen Monat Zeit.
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, ...).
Literatur