Rüdiger Weis <ruedi@cypherpunks.de> & Stefan Lucks <lucks@th.informatik.uni-mannheim.de>

Bigger is better!

Anmerkungen zur Schlüssellängendiskussion

In Amsterdam steigt weisser Rauch auf: Eine Forschergruppe meldet die erste (öffentlich bekannte) Faktorisierung eines 512-bit RSA-Schlüssels.

Kenner der Materie haben schon seit Jahren darauf hingewiesen, dass die Länge eines RSA-Schlüssels deutlich größer als 512 bit sein muss, um Sicherheit gegen Geheimdienste, Wirtschaftsspione und organisierte Kriminelle zu bieten. Dennoch immer noch ein grosser Teil des E-Commerce im Internet mit so kleinen Schlüsseln gesichert. Adi Shamir, einer der Erfinder des RSA-Systems, schätzt den Anteil der derart schwach geschützten E-Commerce Transaktionen auf 95 Prozent [Sham99].

Nach Bruce Schneier [Schn99] nutzen beispielsweise

noch 512-bit Schlüssel.

Es wäre nett, wenn wir diese Sammlung noch etwas erweitern könnten, also mailt uns bitte!

Mathematische Grundlagen

Die weitverbreitetsten Systeme für Kryptographie mit öffentlichen Schlüsseln basieren auf den beiden schon lange Zeit untersuchten zahlentheoretischen Problemen der Faktorisierung (FP) und des Diskreten Logarithmus Problems (DLP).

Beispiel für DLP-basierte Verfahren sind der amerikanische Signaturstandard DSA, die Diffie/Hellman Schlüsselvereinbarungsverfahren und das ElGamal Verschlüsselungsverfahren (in PGP ab Version 5.0 als Diffie/Hellman-Verfahren bezeichnet).

Zur Familie der faktorisierungsbasierten Verfahren gehört das beweisbar zum Faktorisierungsproblem äquivalente Rabin-Verfahren und das bekannteste Public Key-Verfahren für Verschlüsselung und Signaturen RSA, benannt nach seinen Erfindern Ron Rivest, Adi Shamir und Leonard Adleman [RSA78].

Im Folgenden konzentrieren wir uns auf das Faktorisierungsproblem (FP). Die vorherrschende wissenschaftliche Meinung ist, dass beide Probleme eng miteinander verknüpft sind, und dass ein Durchbruch bei der Lösung des einen Problems zu dramatischen Konsequenzen auch bei der Lösung des anderen Problems führen würde. In der Tat weisen die bisher bekannten Methoden diese beiden Probleme algorithmisch anzugehen, grosse Ähnlichkeiten auf. Bei den bisherigen Verfahren ist das DLP tendenziell ein wenig struppiger. (Das kann aber vielleicht auch daran liegen, dass das FP bekannter ist, und dass man mit Fortschritten auf dem Gebiet der Faktorisierung mehr Reputation gewinnt als mit Fortschritten auf dem Gebiet des diskreten Logarithmus.)

Das Faktorisierungsproblem basiert auf der Beobachtung, dass es einfach ist zwei ganze Zahlen zu multiplizieren (polynominaler Zeitaufwand), es allerdings bisher nicht gelungen, ist einen Algorithmus anzugeben, welcher in polynominaler Zeit die Faktoren einer hinreichend grossen Zahl bestimmen kann. Die Faktorisierung des Modulus eines öffentlichen RSA-Schlüssels ermöglicht die einfache Berechnung des geheimen Schlüssels. Hiermit können unauthorisierte Signaturen geleistet und in den meisten Systemen neben der aktuellen, auch die vergangene und zukünftige Kommunikation entschlüsselt werden.

Sieb-Algorithmen

Zur Bestimmung der Primfaktoren von grossen Zahlen hat die mathematische Forschung insbesondere zwei Algorithmen hervorgebracht, bei denen die Komplexität sehr viel langsamer zunimmt (subexponential) als die Menge der zu betrachteten Schlüssel. Bei den Algorithmen Quadratic Sieve und (Generalised) Number Field Sieve kann man im wesentlichen zwei grundlegende Schritte definieren:

Sieving Step

Beim Siebungsschritt wird eine große Zahl von Quadratzahlen mit bestimmten algebraischen Eigenschaften (smoothness) gesucht.

Diesen Schritt kann man mit praktisch beliebig vielen Rechnern parallel ausführen. Die Kommunikation zwischen den parallel arbeitenden Rechnern ist minimal. Am Anfang wird jedem Rechner von einer "Zentrale" der Suchraum vorgegeben, in dem dieser Rechner nach geeigneten Relationen suchen soll.

Gefundene Relationen - die sind relativ selten, deshalb ist der Rechenaufwand eben hoch - werden an die Zentrale gemeldet. Die Kommunikation zwischen den beteiligten Rechnern kann z.B. über das Internet per EMail erfolgen.

Shamirs blinkender Zylinder

Mit Hilfe des von Adi Shamir vorgestellten optoelektronischen TWINKLE Gerätes kann dieser Schritt womöglich nochmals erheblich beschleunigt werden.

Das TWINKLE (The Weizmann INstitute Key Locating Engine) besteht aus einem Zylinder von gerade mal 25 cm Länge mit einem LEDs-Array. Das LED-Array befindet sich auf einem GaA-Wafer. Das System arbeitet mit einer sehr hohen Taktrate von 10 GHz. Die genauen Einzelheiten findet man in [Sham99] und nach vorhersschender Meinung sind alle Designschritte zwar Arbeit, aber nicht übertrieben kompliziert.

Mit diesen Geräten kann man dann für ca. 5.000$ eine Siebungsrate von 100-1000 Athlons erreichen. Und noch mal zur Erinnerung: man ist dabei n-mal so schnell, wenn man n TWINKLEs nebeneinander stellt. (rw)

Matrix Reduction Step

Hat die Zentrale genug Relationen gesammelt, geht sie zum zweiten Schritt über: Anhand der Relationen wird ein lineares Gleichungssystem aufgestellt und gelöst. Das Gleichungssystem ist dünn besetzt (d.h. die überwiegende Mehrzahl aller Koeffizienten sind gleich Null), aber extrem gross (in der Praxis mehrere Millionen Zeilen und Spalten). Man kennt bisher keine gute Methode, diesen Schritt gut zu parallelisieren. Daher wurde er wurde in der Regel von einem einzigen Supercomputer bewältigt.

Quadratisches Sieb (Quadratic Sieve)

Die schnellsten Varianten des Quadratischen Siebs besitzen besitzten eine heuristische asymptotische Laufzeit von

O(exp((1+O(1)) *ln(n)^(1/2) *ln(ln(n))^(1/2))

Für hinreichend grosse Zahlen bildet ln(n)^(1/2) den bestimmenden Faktor.

Zahlkörper Sieb ((Generalised) Number field sieve)

Das (Generalised) Number field sieve 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, was eine signifikante Verbesserung gegenüber dem QS darstellt. Das bedeutet, dass eine Schlüsselverlängerung um 100bit ungefähr eine Vervierzigfachung und eine Verlängerung von 200bit ungefähr eine Verelfhundertfachung der Laufzeit mit sich bringt.

Bis zu einer Länge bis ungefähr 365 bit ist das QS wegen seiner Einfachheit sogar schneller als das GNFS.

Faktorisierungsfortschritte

Im RSA Laboratories Bulletin Nr. 10 vom 8. März 1999 schrieb Scott Conti aus Anlass der Faktorisierung von RSA-140: "We conclude that it is likely that we willse a 512-bit factorisation within the next couple of years". [Cont99]  

"In einigen Jahren" ist bei der Faktorisierung offensichtlich auf Wochen zusammen geschrumpft.

 

RSAZahl

Faktorisierung

MIPS-Jahre

Algortihmus

RSA-100

April 1991

7

Quadratische Sieb

RSA-110

April 1992

75

Quadratische Sieb

RSA-120

Juni 1993

830

Quadratische Sieb

RSA-129

April 1994

5000

Quadratiische Sieb

RSA-130

April 1996

1000

Zahlkörper Sieb

RSA-140

Februar 1999

2000

Zahlkörper Sieb

RSA-155

August 1999

8000

Zahlkörper Sieb

e

 

Die Faktorisierung vom RSA-155

 Am 22. August 1999 veröffentlichte eine Forschergruppe koordiniert von Herman te Riele vom CWI Amsterdam die Faktorisierung der 512 bit Zahl RSA-155. RSA-155 stammt aus der "RSA Challange List" der Firma RSA inc.

Für den Siebungs-Schritt wurden 35.7 CPU-Jahre verwendet. Hierfür wurden folgende Rechner verwendet:

160 * 175-400 MHz SGI und Sun workstations

8 * 250 MHz SGI Origin 2000 processors

120 * 300-450 MHz Pentium II PCs

4 * 500 MHz Digital/Compaq boxes

Dieser Aufwand war ungefähr äquivalent zu 8000 MIPS Jahren. 124.722.179 Relationen wurden gesammelt.

Nochmal: diesen Schritt kann man praktisch beliebig parallelisieren. Insbesondere, wenn Geheimdienste oder andere Mächte des Bösen einen grösseren Hardwareetat haben, kann man mit Spezialhardware (vgl. das optoelektronische TWINKLE-Device) die Sache fast beliebig beschleunigen.

Die resultierende Matrix hatte 6.699.191 Zeilen und 6.711.336 Spalten. Abgearbeitet wurde die Matix in etwa 224 CPU Stunden mit einem Hauptspeicherbedarf von 2 Gbytes auf einer Cray C916 des SARA Amsterdam Academic Computer Center. Die komplette Faktorisierung dauerte vom 17. März bis zum 22. August.

Schlüssel länger als 512-bit

Viele Leute erzählen, der Hauptspeicher sei für längerer Schlüssel das Bottleneck.... Da haben wir allerdings einige Zweifel. Selbst ungepatched wird der neue Linux-Kernel 4 GB Hauptspeicher unterstützten. Und schauen wir mal auf die weiteren Komplexitätszahlen der RSA Labs [RSAB99]. Nach deren Ausführungen braucht man zur Faktorisierung eine 768 bit Zahl ungefähr 80 mal mehr Hauptspeicher. 80 mal 2 G sind 160 GB. Für ein paar Milliönchen müsse es doch für Firmen, die schon mal eben 4 Mrd für Spionagesateliten und ähnliches Spielzeug übrig haben, nicht unmöglich sein. Selbst der 1.800-fache Speicheraufwand für 1024er Schlüssel lässt einen nicht wirklich gut schlafen!

Empfehlungen

Wie lange sollten also die Schlüssel für Public-Key-Verfahren sein? Wie immer gibt es unterschiedliche Empfehlungen unseriöse (von Behörden und Banken) und seriöse (von den netten Hackern von nebenan).

Peinliches vom BSI

Und wieder mal ein Blick auf das BSI. Die Nachfolgeorganisation der militärischen "Zentralstelle für das Chiffrierwesen" steht nicht nur personell, sondern auch organisatorisch in der Tradition der deutschen Geheimdienste. So landen nach glaubhaften Informationen immer wieder verschlüsselte Datenträger nach Polizeiüberfällen auf Hacker und Linke in der Abteilung VI des BSI. Einigermassen seltsam auch die Empfehlungspolitik.

Das Bundesamt für Sicherheit in der Informationstechnik, äusserte in der Veröffentlichung über "Geeignete Kryptoalgorithmen gemäß § 17 (2) SigV (Stand 1999)" vom 29. Mai 1999: "Für den Zeitraum bis Ende 2000 reicht eine Minimallänge von 768 Bit aus" [BSI99].

Das Signaturgesetz und die Signaturverordnung (SigV) soll rechtlich bindende (digitale) Unterschriften regeln. Deshalb ist ein "Sicherheitsabstand" bei der Wahl der PK-Parameter besonders wichtig. Diese Empfehlung baldmöglichst - also insbesondere vor dem Dezember 2000, wenn sie ohnehin obsolet wird - sollte umgehend revidierert werden.

Übrigens: Was macht eigentlich die Supercomputer beim BSI den ganzen Tag?

Und vom ZKA: HBCI...

Unsere lieben Banken wollen uns mit dem Homebanking-Standard HBCI beglücken. Eine Schlüssellänge von 768bit für einen neuen Standard zu verwenden ist schon wirklich keine Idee. Man kann die Sache aber noch schlimmer machen. Man baut einfach noch folgende Schwäche in den Standard:

[HBCI99, S.15]

"VI.3.1.3.

Schlüsselgenerierung

4. Der Zielwert für N ist 768, wobei eine aus der Suche nach starken Primzahlen resultierende Unterschreitung dieses Wertes um maximal 60 Bit zulässig ist."

... falscher Ansatz...

Die Verwendung von "starken Primzahlen" bringt seit der Entdeckung der neueren Siebverfahren "nicht mehr ausreichend begründet und daher verzichtbar" [BSI99]. Das zeigt zwar, dass die massgeblichen Leute bei den Banken scheinbar auf dan Wissenstand Mitte der Achtiziger verharren, wäre aber noch nicht tragisch.

... dumm umgesetzt!

Richtig dumm wird es aber dann, wenn man bei der Suche nach "starken Primzahlen" den Schlüssel um 60bit verkürzen darf. Ist eine unbekannte Primzahlverknappung eingetreten?

Um es unpolemisch zu formulieren: ein Standard, welcher 708bit Schlüssel zuläßt ist nicht akzeptabel. (Nicht mal nach dem BSI.)

RSA Laboratories

Die der Aussage von RSA Laboratories: "A team of researchers wins 512-bit challenge reconfirming RSA's recommendation for using 768-bit keys as the minimum for achieving reliable security." [RSAL99], dass also auch 768bit Schlüssel weiterverwendet werden können, dürfte nicht frei von finanziellen Überlegungen der Pateninhaber sein.

US Militär

Das Defensive Message System (DMS) des US-Militärs verwendet innerhalb der FORTEZZA-Karten eine Schlüsselläng von 1024 bit [WeLu98]. Das DMS wird allerdings nach unseren Informationen nicht für höhere Geheimhaltungsstufen verwendet.

Unsere Empfehlungen

Die Rechner auf unseren Schreibtischen und in unseren Hosentaschen werden immer schneller. Der technische Fortschritt ist hier ausnahmsweise auf der richtigen Seite. Jedes zusätzliche Schlüsselbit kostet nur recht wenig beim Verschlüsseln, kryptoanalytische Angriffe werden allerdings drastisch teurer.

Die Rechenzeit bei längeren Schlüsseln steigt kubisch an. Das bedeutet, dass man für Operationen mit einem 2048-bit Schüssel das 8-fache und bei einem 4096-bit Schlüssel das 64-fache an Zeit braucht, wie bei einem 1024-bit Key.

Wir empfehlen für neu erzeugte Schlüssel eine Mindestlänge von 2048 bit.

1024 bit Schlüssel können bei mittlere Sicherheitsanforderungen weiterverwendet werden. Ob wir wirklich weiterhin unser PGP/GPG-Web of Trust mit nur 1024 bit (DAS-Signatueren) aufbauen sollten, sollte dringend noch mal diskutiert werde!

Bei kürzeren Schlüsseln besteht unserer Meinung nach Handlungsbedarf. Bei weniger als 768 bit sollte in jedem Fall ein sofortiger Schlüsselwechsel eingeleitet werden

Falls keine Echtzeitnotwendigkeit (PGP/GPG für E-Mail), besteht, bietet sich durchaus die Verwendung von Schlüsseln mit der Maximallänge (4096bit) an.

(Gegen 4096-bit dürften selbst die vom US-Geheimdienst gefangenen gehaltenen Alien machtlos sein. Theoretische Physiker bleiben aufgefordert die für einen Angriff nötige Anzahl von Paralleluniversen auszurechnen!-)

This lady uses a 4096bit Public Key

Another reason why OPGP is cooler than S/MIME

Neben der hierarschischen Zertifizierungsstruktur, der schlechteren Erweiterbarkeit, der Verwendung von proprietaeren Algorithmen von unklarer Sicherheit und lächerlicher 40 bit Schlüssellänge bei S/MIME bietet Open PGP auch hinsichtlich der unterstützten Länge von öffentlichen Schlüsseln Vorteile.

Der Open PGP Standard [OPGP98] schreibt eine Unterstützung von Schlüssellängen von bis zu 4096 bit vor. Sowohl die aktuellen PGP-Versionen, wie auch das inzwischen in der Version 1.0 vorliegende GNU-Programm GNU Privacy Guard verwalten 4096 bit Schlüssel. Allerdings bleibt zu beachten, dass die aktuellen PGP-Versionen in der DLP-Variante als Signaturverfahren DSA und somit einen 1024 bit Schlüssel verwenden.

 Auch in der neusten Internet-RFC Ausgabe zu S/MIME vom Juni 1999 [RFC2633] wird eine Unterstützung von längeren Schlüsseln als SHOULD-Option vorgesehen:

"Creating keys longer than 1024 bits may cause some older S/MIME receiving agents to not be able to verify signatures, but gives better security and is therefore valuable. A receiving agent SHOULD be able to verify signatures with keys of any size over 512 bits." [RFC2633]

 Man beachte also, dass Schlüssellängen über 1024 bit wegen der Optionalität zu Interoperabilitätsproblemen selbst unter standardkonformen S/MIME Implementierungen führen können. [WeGe99]

Nur die Show ist real

Rein wissenschaftlich muss man feststellen, dass bis auf einige interessante Verbesserungen bei der Polynomauswahl und der Schnelligkeit der konkreten Ausführung nur wenige Monate nach der Faktorisierung von RSA-140, alle Parameter im vorausgesagten Bereich liegen.

Die durchaus beachtliche Leistung der Forscher um H. te Riele aus Amsterdam besteht, abgesehen von der Organisierung von enorm viel Rechenleistung, im algorithmischen Fein-Tuning", das heisst , in der Abstimmung einzelner Parameter aufeinander, um ein bekanntes Verfahren, das Zahlkörper Sieb, noch etwas effizienter ausführen zu können, als es bisher gelungen ist. Weitere Fortschritte auf diesem Gebiet sind zu erwarten.

Trotzdem muss man der Amsterdamer Gruppe einen grossen Dank aussprechen, denn nur durch solche öffentlichkeitswirksame Aktionen kann offensichtlich die nötige Sensibilisierung gegenüber wissenschaftlich längst bekannten kryptographischen Schwächen hergestellt werden. Oder um mit den Worten von Bruce Schneier [Schn99] zu schliessen:

"It's tiring when people don't listen to cryptographers when they say that something is insecure, waiting instead for someone to actually demonstrate the insecurity."

 

Literatur

[BLP94] Buhler, J., Lenstra, Pommerance, "The developement of the number field sieve", Springer LNCS 1554, 1994.

[Cont99] Conti, S., "The Faktorization of RSA-140", RSA Laboratories BulletinNr. 10, 8. März 1999

[Schn99] Crypto-Gram, 15. Sept 1999, http://www.counterpane.com/crypto-gram-9909.html

[HBCI99] Home Banking Computer Interface, Version 2.1 1 vom 02.03.1999, Teil B Sicherheit, http://www.hbci-zka.de/download/HBCI21b.pdf

[Riel99a] H. te Riele, "Factorization of a 512-bits RSA key using the Number Field Sieve", August 22 1999. Available from http://dbs.cwi.nl:8080/cwwwi/owa/cwwwi.print_projects?ID=12

[Riel99b] H. te Riele, "Security of E-commerce threatened by 512-bit number factorization", CWI press release, August 26 1999.

[RSA78] Rivest, R., Shamir, A., Adleman, L., "A methode for obtaining digital signatures and public-key cryptosystems", Communications of the ACM, 21(2), pp. 120-126, Feb 19978.

[RSAL99] RSA Laboratoritites, http://www.rsasecurity.com/rasalabs/

[BSI99] BSI, Geeignete Kryptoalgorithmen gemäß § 17 (2) SigV (Stand 1999), http://www.bsi.de/aufgaben/projekte/pbdigsig/download/kryptalg.pdf

[RFC 2633] Ramsdell, B., S/MIME Version 3 Message Specificationm , Juni 1999.

[Sham99] Shamir, A., "TWINKLE", www.jya.com/twinkle.eps

[WeLu98] Weis, R.., Lucks, S. "KEA", DuD10/98.

[WLG99] Weis, R., Lucks, S, Geyer, W., "Stand der Faktorisierungsforschung und nötige Konsequenzen für minimale Schlüssellängen", submitted to Datenschutz und Datensicherheit, Vieweg, 1999.

[WeGe99] Weis, R., Geyer, W., "Open PGP vs. S/MIME", Interner Diskussionsbeitrag, Universität Mannheim, 1999.