PGP
|
|
|
|
Die
Sicherheit des kryptologischen Verfahrens PGP
|
|
Warum
soll ein Computer in der nahen Zukunft nicht fix mal alle IDEA-Schlüssel
durchprobieren können? > Weil ein Computer aus prinzipiellen Gründen diese Leistungsfähigkeit nicht haben wird. |
|
Nach dem
heutigen Stand der physikalischen Forschung, der sich natürlich ändern
kann, ist die Signalübertragung in jedem denkbaren Computersystem durch
die Lichtgeschwindigkeit begrenzt.
Angenommen das Hochleistungscomputersystem zum Schlüsseltest hat eine maximale Ausdehnung von 0,3 mm, in der die elektronische oder lichtgeleitete Informationsübertragung erfolgt, dann kann es maximal 1 000 000 000 000 Operationen (1012) in jeder Sekunde ausführen, weil es sonst kleiner sein müsste. In 317 Jahren, also 10 003 759 200 Sekunden ist dieses System in der Lage 10 003 759 200 000 000 000 000 Operationen auszuführen. Diese bescheidene Leistungsfähigkeit von immerhin 1022 Operationen, die in diesen 317 Jahren ausführbar sind, ermöglicht natürlich nicht die Überprüfung von 1022 verschiedenen IDEA-Schlüsseln, weil ein Schlüsseltest sich nicht in einem Taktzyklus erledigen lässt. Aber selbst wenn dies möglich wäre, ist die große Anzahl der möglichen IDEA-Schlüssel von 1038 dann nur zu 0,000 000 000 000 000 029 Prozent durchsucht. Also wird ein einzelner IDEA-Schlüssel auch dann nicht gefunden werden, wenn man "viele" solcher Computersysteme parallel an die Arbeit setzt.
Dieses Argument basiert auf empirischen Annahmen und kann deshalb auch durch die Erfahrung widerlegt werden. Es ist aber sicherlich empirisch falsch, Computersystemen eine "in Zukunft beliebig große Leistungsfähigkeit" zu unterstellen. |
Für die Verlässlichkeit von PGP ist das Public-Key-Verfahren (RSA) von entscheidender Bedeutung, weil eine zuverlässige Bindung zwischen einer Person und der Fähigkeit zur Entschlüsselung oder zur Signatur von Informationen bestehen muss.
Auf der sicheren Funktionsfähigkeit des Public-Key-Verfahrens basiert:
die Vertraulichkeit der Nachricht, da der IDEA-Schlüssel nur vom wirklichen Adressaten der Nachricht angewendet werden darf, und
die Authentizität der Nachricht, so dass eine verlässliche digitale Signatur von Dokumenten möglich ist, und eine vorliegende Information daraufhin überprüft werden kann, ob sie wirklich von einer bestimmten Person stammt oder nicht.
Wird eine Nachricht mit einem IDEA-Schlüssel verschlüsselt, so muss dieser Schlüssel an den Adressaten zusammen mit der verschlüsselten Nachricht übermittelt werden, aber in einer Weise, dass nur diese Person den Schlüssel wiedergewinnen kann und damit in der Lage ist, die Nachricht zu entschlüsseln. Hierzu wird der IDEA-Schlüssel (Session-Key) selbst noch einmal verschlüsselt und zwar mit dem öffentlichen RSA-Schlüssel (Public-Key) des Adressaten. Zu diesem öffentlichen Schlüssel gehört ein Gegenstück, der geheime Schlüssel (Secret-Key), der ausschließlich im Besitz des Adressaten sein darf, damit nur er oder sie in der Lage ist, durch Anwendung des Secret-Keys den IDEA-Schlüssel wiederzugewinnen, den man zur Entschlüsselung der eigentlichen Nachricht braucht.
Die Authentizität der Nachricht ist also nur zu gewährleisten, wenn das Schlüsselpaar (Public-Key, Secret-Key) verlässlich einer bestimmten Person zugeordnet werden kann, und zwar auch dann, wenn man die betreffende Person gar nicht kennt. Für die Gültigkeit einer digitalen Signatur ist die Sicherheit wesentlich, dass nur die fragliche Person selbst in der Lage war, eine Information durch die Anwendung ihres Secret-Keys zu erzeugen und diese Person damit für den Inhalt der Nachricht auch verantwortlich ist. Die Urheberschaft einer Information kann auch nur dann gegenüber anderen nachgewiesen werden, und damit das geistige Eigentum einer Person geschützt werden, wenn es niemand anderem möglich ist, eine Information zu erzeugen, die zu dem Public-Key einer Person passt.
Die praktische Anwendung des RSA-Verfahrens basiert auf der Verwendung dreier sehr großer Zahlen (e,d,n), wenn auch bei der computertechnischen Implementierung des RSA-Verfahrens eine dieser Zahlen klein gewählt wird, ohne dass dadurch die Sicherheit des Verfahrens eingeschränkt wird. Zwei dieser Zahlen, der öffentliche Schlüssel e und die Modulzahl n werden verwendet, um eine Nachricht zu verschlüsseln. Dabei wird prinzipiell die zu verschlüsselnde Nachricht auch als große Zahl aufgefasst, mit e potenziert und von diesem Ergebnis wird so lange die Modulzahl n subtrahiert, bis es kleiner als n ist, d.h. es wird der Rest modulo n bestimmt. Das Ergebnis ist das Kryptogramm, die für den Empfänger verschlüsselte Nachricht. Beim Empfänger wird derselbe Vorgang als Entschlüsselung des Kryptogramms wiederholt, wobei das Kryptogramm als sehr lange Zahl mit dem geheimen Schlüssel d potenziert wird und durch die Restwertbildung mittels der Modulzahl wunderbarerweise wieder der ursprüngliche Klartext entsteht. Von den drei verwendeten Zahlen ist also nur die Zahl d, der geheime Schlüssel, wirklich geheim zu halten, das Verfahren, die öffentlich bekannten Zahlen e und n, aber auch das Kryptogramm selbst, sind kein Geheimnis und dürfen gefahrlos von jedermann analysiert werden.
Das RSA-Verfahren funktioniert allerdings nur dann, wenn die drei Zahlen (e,d,n) in "geeigneter Weise" zusammenpassen. Dass dies gewährleistet ist, ergibt sich aus der Erzeugung des Schlüsselpaars, einem Verfahren, das auch ein Rezept für das Knacken des RSA-Verfahrens liefert (Faktorisierungsproblem).
Zur Erzeugung eines Schlüsselpaars ist es erforderlich, zwei sehr große
Primzahlen p und q zu finden, die als Produkt die Modulzahl ergeben:
n = p*q)
Aus diesen Primzahlen, die zum Schluss weggeschmissen werden, können sehr schnell die zwei interessanten Zahlen e und d ermittelt werden, die das eigentliche Schlüsselpaar bilden.
Ein Angreifer kennt nun die Modulzahl n, also p*q, und braucht bloß ermitteln,
aus welchen beiden Primzahlen n zusammengesetzt ist, d.h. er oder sie
muss n faktorisieren, dann ist die Ermittlung des geheimen Schlüssels eine Sache
von Sekunden. Erfreulicherweise ist aber das
Faktorisierungsproblem bei sehr langen Zahlen mit mehreren hundert
Dezimalstellen eine Aufgabe, die extrem viel Arbeit verursacht und damit zu den
praktisch unlösbaren Problemen zählt.
Die Sicherheit des RSA-Verfahrens beruht also darauf, dass es praktisch unmöglich ist, die Modulzahl n zu faktorisieren, also aus der Kenntnis der öffentlichen Modulzahl auf die beiden Primzahlen p und q zu schließen, aus denen sich der geheime Schlüssel gewinnen lässt.
Die bisherige Geschichte der Faktorisierung
70-stellige Zahlen werden heute (1998) in 10 Stunden auf einer Workstation faktorisiert.
100-stellige Zahlen werden in 1 Jahr auf einer Workstation faktorisiert.
129-stellige Zahlen :
Im August 1977 stellte Martin Gardner den Lesern der Zeitschrift "Scientific American" die Aufgabe die Zahl
114 381 625 757 888 867 669 235 779 967 146 612 010 218 296 721 242 362 562 561 842 935 706 935 245 733 897 830 597 123 563 958 705 058 989 075 147 599 290 026 879 543 541
zu faktorisieren!16 Jahre später im April 1994 präsentierten Paul Leyland (Uni Oxford), Michael Graff (Uni Iowa) und Derek Atkins (MIT) die Faktoren. Dabei wurden etwa 600 freiwillige Internet-Benutzer mitbeschäftigt, die nachts auf Ihren Workstations ein Faktorisierungsprogramm laufen ließen, das von K. Lenstra (Bell Labs, Morristown, New Jersey) stammte.
140-stellige Zahl: ist 1996 die kleinste noch nicht faktorisierte Zahl
140-stellige Zahlen werden in einem großen Rechnernetz in 5 Jahren faktorisiert
160-stellige Zahlen:
Experten erwarten 1996 eine Faktorisierung in etwa fünf Jahren unter Verwendung der Methode der Zahlkörpersiebe.
200-stellige Zahlen: Die Faktorisierungszeit wird 1998 auf 52 000 000 Jahre geschätzt.
Die minimale Schlüssellänge von 1024 Bit garantiert also, dass die RSA-Modulzahl mindestens 309 Dezimalstellen lang ist und damit für die nächste Zukunft als sicher angesehen werden kann, solange die Faktorisierung von Zahlen keine drastischen Fortschritte macht. Viele PGP-Schlüssel werden heute bereits mit einer Länge von 2048 Bit zertifiziert, was 617 Dezimalstellen entspricht.
Da die Faktorisierung der Modulzahl bei entsprechender Schlüssellänge aussichtslos ist, richten sich die bisher bekannten Angriffe auf das RSA-Verfahren gegen die Implementierung des Algorithmus (timing-attack) bzw. sie setzen voraus, dass der Angreifer in der Lage ist, dem potentiellen Opfer eine selbst gewählte Nachricht zur Signatur vorzulegen (chosen-ciphertext-attack). Diese beiden Formen des Angriffs werden z. B. von W. Unruh beschrieben, so dass ich darauf nicht weiter eingehen möchte.
Um sich vor solcherlei Angriffen zu schützen, sollte man möglichst vermeiden, ein Dokument zu signieren, das beliebige versteckte Daten enthalten kann, z. B. ein fremdes Textverarbeitungsdokument, das je nach Typ erheblich mehr Informationen (zur Formatierung) enthalten kann, als im Klartext zu sehen sind. Der chosen-ciphertext-Angriff basiert nämlich darauf, dass ein Angreifer in der Lage ist, eine Menge von ihm geschickt gewählter Zufallsdaten in die Nachricht einzuschmuggeln, deren Verschlüsselung zusammen mit dem Dokument durch den Secret-Key einer Entschlüsselung des Kryptogramms gleichkommt. Den Secret-Key erhält der Angreifer aber auch dann nicht, wenn sein Angriff auf eine verschlüsselte Nachricht Erfolg hat.
Zweifellos haben die Mathematiker in den vergangenen Jahren große Fortschritte bei der Faktorisierung großer Zahlen gemacht, die J. Buchmann ausführlich in seinem Artikel in Scientific American, Juni 1996 (bzw. Spektrum der Wissenschaft, September 1996) beschreibt. Durch die massive Nutzung neuerer Computertechnologie wurden gänzlich neue Verfahren zur Faktorisierung entwickelt, die sich wesentlich von den herkömmlichen Methoden unterscheiden.
So entwickelte bereits 1985 W. Lenstra das Verfahren der Elliptischen Kurven, mit dem auf der Basis heutiger Workstationtechnologie innerhalb von drei Wochen 30-stellige Faktoren gefunden werden können. Dieses Verfahren hat den Vorteil, dass es auch dann zum Ziel führt, wenn die zu faktorisierende Zahl mehrere tausend Dezimalstellen hat. Ist also die RSA-Zahl aus einem kleinen und einem großen Faktor zusammengesetzt, so kann der kleinere Faktor mit dieser Methode in akzeptabler Zeit gefunden werden. Es ist deshalb wesentlich, dass bei der Erzeugung von RSA-Schlüsseln zwei etwa gleich große Primzahlen geeigneter Länge verwendet werden, um eine schnelle Faktorisierung zu verhindern.
Ein anderes Verfahren, das quadratische Sieb, erfordert zur Faktorisierung einer großen Zahl die Lösung eines linearen Gleichungssystems mit einer riesigen Menge von linearen Gleichungen. Mit dieser Methode gelang es 1993 eine 120-stellige RSA-Zahl zu faktorisieren, wobei 252222 Gleichungen mit 245810 Unbekannten gelöst werden mussten. Diese Arbeit, die auf einem einzigen Rechner etwa 50 Jahre in Anspruch genommen hätte, konnte parallelisiert und so in wesentlich kürzerer Zeit erledigt werden. Mit der auf einem ähnlichen Prinzip aufbauenden Methode des Zahlkörpersiebs, die erheblich schneller arbeitet als das quadratische Sieb, konnte 1996 erfolgreich eine 130-stellige Zahl in ihre Faktoren zerlegt werden.
Betrachtet man den Fortschritt in der Faktorisierung innerhalb der letzten zehn Jahre, so ist damit zu rechnen, dass in naher Zukunft 150-stellige Zahlen faktorisierbar sind, auch wenn heute kein bekannter Algorithmus in der Lage wäre, diese Arbeit in vernünftiger Zeit zu leisten. Möglicherweise findet man aber auch einen gänzlich neuen Algorithmus, der heute sichere RSA-Schlüssel dann völlig wertlos macht. Es gilt also, die Entwicklungen auf dem Gebiet der Faktorisierung genau zu beobachten und bei der Bewertung von RSA-Schlüssellängen zu berücksichtigen.
Die Integrität oder Echtheit einer Nachricht, also die Sicherheit. dass das erhaltene Dokument beim Transport über Datennetze nicht verändert worden ist, hängt vom Hash-Verfahren MD5 ab, mit dem ein Fingerprint des Dokumentes erzeugt wird.
Ein Fingerprint ist
eine große Zahl (bei MD5 eine 39-stellige Dezimalzahl), die eindeutig zu einer
Nachricht passt. Der Fingerprint wird durch eine sog. Einwegfunktion (Hash-Verfahren)
aus der Nachricht errechnet, so dass sichergestellt ist, dass die Veränderung
eines einzigen Bits in der Nachricht zu einem gänzlich anderen Ergebnis führt.
Auf diese Weise kann eine (auch minimale) Veränderung der Nachricht sicher
erkannt werden. Gleichzeitig muss durch das Hash-Verfahren ausgeschlossen sein,
dass man vom Fingerprint auf die Nachricht zurückschließen kann. Die Berechnung
der Einwegfunktion ist nicht umkehrbar! Das bedeutet aber auch, dass es nicht
möglich ist, eine andere Nachricht so zu konstruieren (als Fälschung), dass sie
denselben Fingerprint wie das Original ergibt, weil es 1038
verschiedene Hashwerte gibt und die Anwendung des Hash-Verfahrens einen dieser
Werte liefert, der nicht vorher bestimmbar ist. Es ist zwar möglich, dass ein
anderer Text zufällig denselben Fingerprint (Hashwert) liefert, denn die Menge
der Hashwerte ist zwar groß, aber begrenzt. Eine solche Kollision ist aber nicht
absichtlich herzustellen, weil man dann 1038 Varianten testen müsste.
Die Einwegfunktion liefert im Idealfall keinen Ansatzpunkt dafür, durch eine
geeignete Wahl der Fälschung das erwünschte Ergebnis zu erreichen.
Und die Wahrscheinlichkeit, dass zwei beliebige Texte denselben Hashwert haben
ist nur :
0,000 000 000 000 000 000 000 000 000 000 000 000 029 Prozent (1/2128)
Der Geburtstags-Angriff auf MD5
Wieviele Personen sind erforderlich, damit die Wahrscheinlichkeit, dass zwei von ihnen am gleichen Tag Geburtstag haben, 50 Prozent beträgt ?
Die falsche Antwort lautet: 365/2 = 182 Personen.
In Wirklichkeit sind es erheblich weniger, nämlich 23, so dass übertragen auf die Fälschung einer digitalen Unterschrift daraus ein Vorteil erwächst. Wenn der Angreifer nicht ein bestimmtes Dokument fälschen will, sondern sich darauf beschränkt, dem potentiellen Opfer ein Dokument zur Unterschrift vorzulegen, zu dem er, nein sie, eine entsprechende Fälschung gefunden hat, die den gleichen MD5-Fingerprint aufweist, so ist eine Fälschung der digitalen Signatur mit einem solchen "geeigneten Pärchen" (gutartiges und bösartiges Dokument) möglich.
Die Anzahl solcher Fälschungspärchen, die man durchprobieren muss, um ein funktionierendes zu finden, ist nun nicht mehr 2127 (170 141 183 460 469 231 731 687 303 715 884 105 728) sondern "bloß noch" 264 (18 446 744 073 709 551 616) also 1019 Dokumentenpaare. Ein geeignetes Dokumentenpärchen zu finden ist immer noch "verdammt viel Arbeit", kann aber nicht grundsätzlich (vgl. die Argumentation zum Erraten des IDEA-Schlüssels) ausgeschlossen werden.
Begründung
Bei N verschiedenen Dokumenten (gutartige und bösartige zusammen) gibt es N(N-1)/2 Paare, wobei die Wahrscheinlichkeit, dass eines dieser Dokumente mit einem anderen Dokument denselben MD5-Hashwert teilt 1/K beträgt, unter der Annahme, dass es insgesamt K = 2128 verschiedene Hashwerte gibt.
Nach oben abgeschätzt muss man die Hälfte von N2 Pärchen durchprobieren. Wenn die Wahrscheinlichkeit für eine Kollision 50 Prozent betragen soll, dann folgt:
(N2 * 1/K) / 2 = 0,5
also N = sqrt(K) = 264
Unter den 18 446 744 073 709 551 616 verschiedenen Pärchen sollte also mit großer Wahrscheinlichkeit eines sein, das zur Fälschung der digitalen Signatur geeignet ist.
FAZIT
Bei der Verwendung einer geeignet großen Schlüssellänge ist ein Angriff auf die kryptologischen Verfahren, die PGP verwendet, praktisch aussichtslos.
Diese "theoretische Sicherheit" muss ständig an den aktuellen Ergebnissen der kryptologischen Forschung gemessen werden.
Quellen:
PGP-Org
BMWI
Senderek
|
| ||||||
