======== Newsgroups: de.comp.security Subject: Re: PGP: Wirklich sicher und effizient? From: ub99@rz.uni-karlsruhe.de (Gabor Fischer) Date: 7 Dec 1995 09:09:30 +0100 Matthias Stiesch aka wrote: > Wie sicher ist PGP wirklich? Die kurze Antwort ist, es gibt kein oeffentlich bekanntes Verfahren PGP in irgendeiner vernuenftigen Zeit zu knacken, auch wenn man extrem leistungsfaehige Spezialhardware verwendet. Die lange Antwort ist natuerlich etwas komplizierter. Die Sicherheit der Verschluesselung von PGP ist das Minimum der Sicherheit der Verfahren RSA und IDEA. Es gibt keinen bekannten Angriff auf IDEA, der besser ist als Brute Force, also das Ausprobieren aller moeglichen Schluessel. IDEA hat eine Schluessellaenge von 128 Bit. Der beste oeffentlich bekannte Angriff gegen IDEA ist es also, alle 2^128 Schluessel nacheinander auszuprobieren. Das sind etwa 3.4*10^38 Schluessel. Wenn man einen Spezialchip baut, der eine Milliarde Schluessel in der Sekunde ausprobieren kann, und eine Milliarde dieser Chips parallel arbeiten laesst, dann braucht man zum Ausprobieren aller Schluessel 3.4*10^20 Sekunden bzw. 10^13 Jahre. Das Universum ist nur ca. 10^10 Jahre alt. Wenn man einen Chip baut, der eine Billion Schluessel in der Sekunde ausprobieren kann (was absolut utopisch ist) und eine Billion von diesen Chips baut (was wegen der verwendeten Siliziummenge noch utopischer ist), dann braeuchte man "nur" noch etwa 10 Millionen Jahre dafuer. Die Sicherheit von RSA baut darauf auf, dass es extrem schwierig ist, eine grosse Zahl zu faktorisieren (d. h. in seine Primfaktoren zu zerlegen). Um aus einem oeffentlichen RSA-Schluessel den privaten Schluessel zu ermitteln muss man den Modulus faktorisieren. Es gibt einige Fixpunkte, um den Aufwand abzuschaetzen. Ein 384 Bit PGP-Schluessel wurde dieses Jahr von einem kleinen Team faktorisiert. Sie benutzten etwa 50 Workstations mit einer Gesamtrechenleistung von 1300 MIPS (MIPS = Million Instructions Per Second) und eine MasPar dazu. Sie brauchten vier Monate. Etwas frueher wurde das RSA-129 Raetsel geloest. Dabei handelte es sich um eine Zahl mit 129 Dezimalstellen (426 Bit), die die drei Erfinder von RSA als oeffentliche Herausforderung veroeffentlicht hatten. Dazu wurden mehrere hundert Computer im Internet verwendet, die in Zeiten geringer Auslastung an dem Problem arbeiteten. Das ganze dauerte etwa acht Monate, der aufgebrachte Rechenlaufwand wird auf etwa 4000 MIPS-Jahre geschaetzt. Ein MIPS-Jahr entspricht dem Rechenaufwand, den ein 1-MIPS Computer erbringt, wenn er ein Jahr lang pausenlos arbeitet. Der Aufwand fuer die Faktorisierung von langen Zahlen steigt exponentiell, konservative Schaetzungen gehen davon aus, dass der Aufwand sich alle 13 Bits verdoppelt. Ausgehend von dieser Schaetzung braeuchte man fuer die Faktorisierung einer 512 Bit Zahl einen Rechenaufwand von 256000 MIPS- Jahren, fuer die Faktorisierung einer 1024 Bit Zahl einen Rechenaufwand von 2.8*10^17 MIPS-Jahren und fuer die Faktorisierung einer 2048 Bit Zahl einen Rechenaufwand von 8.5*10^40 MIPS-Jahren. Das ist eine um Groessenordnungen groessere Rechenleistung als die aller derzeit verfuegbaren Computer der Erde zusammengenommen. Natuerlich ist damit zu rechnen, dass Faktorisierungsverfahren in Zukunft besser werden. Es gibt verschiedene Schaetzungen dazu, auf die ich jetzt nicht naeher eingehen will, aber selbst die pessimistischsten sagen aus dass ein 2048 Bit Schluessell mit hoher Wahrscheinlichkeit fuer unsere Lebenszeit sicher ist. Diese Betrachtungen gehen von oeffentlich bekannten Verfahren aus. Es ist aber sehr wahrscheinlich dass Geheimdienste ueber bessere Verfahren zur Faktorisierung verfuegen und effektivere Angriffe gegen IDEA kennen. Sie haben einen grossen Wissens- und Erfahrungsvorsprung gegenueber der Oeffentlichkeit. Wie gut ihre Verfahren wirklich sind, darueber kann man nur spekulieren. @------------------------------------------+--------------------------@ | Gabor Fischer | Encrypted mail preferred.| | Internet: | PGP Public Key available | | Fidonet: <2:2471/2559.5> | upon request. | +------------------------------------------+--------------------------+ | Key fingerprint = 1A 16 64 D3 D2 C1 5E 0E 7D E7 D5 9E FF 86 D1 1B | @---------------------------------------------------------------------@ ======== Newsgroups: de.comp.security Subject: Re: PGP: Wirklich sicher und effizient? From: harald@manowar.ka.sub.org (Harald Weidner) Date: 11 Dec 1995 23:47:32 +0100 In article <5zREe$JqvmB@rz.uni-karlsruhe.de>, Gabor Fischer wrote: >Die Sicherheit von RSA baut darauf auf, dass es extrem schwierig ist, eine >grosse Zahl zu faktorisieren (d. h. in seine Primfaktoren zu zerlegen). Um >aus einem oeffentlichen RSA-Schluessel den privaten Schluessel zu >ermitteln muss man den Modulus faktorisieren. Das ist nicht ganz korrekt. Die Sicherheit von RSA beruht auf den fol- genden drei Problemen der Zahlentheorie, für die noch keine vernünftigen Lösungen existieren. Sobald eines dieser Probleme gelöst ist, wird RSA (und damit PGP) unbrauchbar. (1) Das Faktorisierungsproblem, das Du angesprochen hast. (2) Das diskrete Logarithmus-Problem: Es besagt, dass es einfach ist, zu bekanntem x, a und n ein y zu berechnen, so daß y = a^x mod n gilt; es gibt jedoch keinen vernünftigen Algorithmus, mit dem sich aus gegebenem y, a und n das x berechnen läßt. (3) Das diskrete Wurzel-Problem: Zu gegebenem x, a und n ist es einfach, ein y zu berechnen, so daß y = x^a mod n gilt; aus gegebem y, a und n das x zu berechnen, ist dagegen schwierig, falls n keine Primzahl ist. Man betrachte die folgenden Szeniarien: (a) Ein Angreifer fängt ein Chiffrat c ab, das mit RSA aus einer Nach- richt m und einem öffentlichen Schlüssel (e,n) generiert wurde. Es gilt c = m^e mod n. Das Problem, daraus m zu entschlüsseln, ent- spricht genau dem diskreten Logarithmusproblem. (b) Ein Angreifer kennt den öffentlichen Schlüssel eines Teilnehmers (e,n) und möchte daraus den privaten d ermitteln. Er wählt eine (bzw. beliebig viele) Nachrichten m und chiffriert sie mit dem Schlüssel. Es gilt m = c^d mod n. Das Problem, aus dieser Glei- chung d zu erhalten, ist äquivalent zum diskreten Wurzelproblem. (c) Der Empfänger einer signierten Nachricht m mit Signatur s möchte den geheimen Schlüssel des Signierenden herausfinden. Es gilt s = m^d mod n, und das Herausfinden von d entspricht dem diskreten Logarithmusproblem. (d) Ein Angreifer möchte zu einer selbsterstellten Nachricht m eine Signatur s fälschen, die einem Teilnehmer mit öffentlichem Schlüs- sel (e,n) untergeschoben werden soll. Es gilt m = s^e mod n. Das Herausfinden von s ist äquivalent zum diskreten Wurzelproblem. Tschau, Harald -- Harald Weidner harald@manowar.ka.sub.org The world is a stage +49 721 25597 Harald.Weidner@ira.uka.de Where we all can play Stephanienstr. 21 uk8u@rz.uni-karlsruhe.de Another fine reason 76133 Karlsruhe Heavy@irc To live