Spezialarchitekturen zur Kryptanalyse von RSA und DL-Verfahren sowie Algorithmik für das allgemeine Zahlkörpersieb
Zusammenfassung der Projektergebnisse
In diesem Forschungsprojektes wurde .die Entwicklung einer technologisch realistischen und kostengünstigen Spezialmaschine zur Fakt orisier ung von 1024-Bit-Zahlen auf Basis des allgemeinen Zahlenkörpersiebs (GNFS) angestrebt. Hierbei wurde - basierend auf dem gegebenen Förderungsrahmen durch die DFG - die Optimierung der Kofaktorisierung mit der Elliptischen Kurvenmethode (ECM) ausgewählt. 2.1 Ergebnisse aus diesem Forschungsprojekt Wie im Antrag beschrieben, hegt eine vielversprechende Beschleunigungsmöglichkeit des GNFS in der massiven Parallelisierung und Optimierung des ECM-Verfahrens. Bei der Lösung eines parallelen Berechnungsproblems wird in der Regel das beste Kosten-Leistungsverhältnis pro Chip durch die Verwendung von Spezialhardware erreicht. Daher wurde in diesem Projekt unter maßgeblicher Beteiligung der wissenschaftlichen Mitarbeiter Jan Pelzl und Tim Güneysu ein Clustersystems auf Basis von rekonfigurierbaren Hardwarechips (FPGAs) entwickelt, auf welches die ECM in einem hohen Parallelisierungsgrad ausgeführt werden kann. Die Architektur des Clusters wurde dabei mit besonderem Augenmerk auf ein optimales Kosten-Leistungsverhältnis für allgemeine kryptanalytische Applikationen entworfen, daher wurde er unter dem Namen COPACOBANA (Cost Optimized PArdllel COde Breaker) auch für andere kryptographischen Probleme international bekannt [13, 12, 6]. Die Entwicklung der Hardware erfolgte in enger Kooperation mit dem Lehrstuhl für technische Informatik der Christian Albrechts Universität zu Kiel. Die flexible Rekonfigurierbarkeit der Hardwarechips in diesem Cluster erlaubt es, die COPACOBANA-Architektur neben der ECM auch für weitere kryptanalytische Zwecke einzusetzen, wie beispielsweise der erschöpfenden Schlüsselsuche in (schwachen) symmetrische Kryptosystemen. Ein mittelbares Ergebnis der Entwicklung der COPACOBANA in Zusammenhang mit diesem Forschungsprojekt war die vollständige Kompromittierung des (ehemaligen) weltweiten Verschlüsselungsstandards DES (FIPS 46-3: Data Encryption Standard), welcher mit Hilfe dieser Maschine bei einer finanziellen Aufwendung von weniger als €10.000 durchschnittlich in etwa einer Woche gebrochen werden kann [13, 12]. Auf Basis dieser Erkenntnis wurden auch effiziente Angriffe auf praktische Sicherheitssysteme möglich, beispielsweise Attacken auf DES-basierte Security Tokens, wie sie in manchen (internationalen) noch immer Bankensystemen eingesetzt werden [7], Auch konnte gezeigt werden, wie der COPACOBANACluster erfolgreich zum Angriff auf den maschinenlesbaren, elektronischen Reisepass eingesetzt werden kann [15]. ' Der für dieses Forschungsvorhaben realisierte CO PAC OB ANA-Cluster wurde mit Hardwarechips (Virtex-4 FPGAs) ausgestattet, die insbesondere die arithmetischen Operation der ECM durch spezifische Arithmetikkerne (DSP48 Blöcke) innerhalb den FPGAs beschleunigen können. Implementierungen aus der Literatur setzten hier bislang ausschheßlich auf die Implementierung der modularen Addition und Multiplikation in rekonfigurierbarer Logik der FPGAs anstatt von dedizierten Arithmetikkernen, was mit wesentlich höherem Resourcenverbrauch bei schlechterer Systemleistung verbunden war. Diese Technik auf Basis von dedizierten Arithmetikkernen konnte ebenfalls zur Beschleunigung der Grundarithmetik für Elliptische Kurven Kryptosysteme (ECC) eingesetzt werden, insbesondere für Hochgeschwindigkeitssysteme zur Generierung und Verifikation von digitalen Signaturen mit elliptischen Kurven, was somit als weiteres, mittelbares Ergebnis in diesem Forschungsprojekt gezählt werden kann [8]. Bei der Implementierung der ECM hatte Hans-Christian Röpke besonderen Anteil, der die Architektur in einer Hardwarebeschreibungssprache (VHDL) für die COPACOBANA-Plattform realisiert hat. Die COPACOBANA-Architektur mit der ECM Implementierung wurde sowohl in den Transactions on Computers [6] wie auch separat auf einem internationalen Kongress für rekonfigurbare System publiziert [11]. Die Entwicklung der COPACOBANA, das verwendete Clusterframework, Clustersystemcontroller, sowie kryptographischen Implementierungen für diese Plattform wurde dabei durch mehrere Studien- und Diplomarbeiten an der Ruhr-Univers ität Bochum unterstützt [17, 14, 18, 22, 16, 3]. 2.2 Ausblick und weitere Anwendungen Mit der COPACOBANA wurde ein universelles Clustersystemen auf Basis von FPGAHardwarechips entwickelt, welches eine optimale Plattform für par alle lisierbare Anwendungen darstellt, die nur ein Mindestmaß an Interkommunikation und Speicher benötigen. Daher kann die ursprünglich mit Fokus auf die parallele Ausführung der ECM entwickelte COPACOBANA ebenfalls für weitere kryptographische und nicht-kryptographische Anwendungen eingesetzt werden. Mögliche Folgeprojekte im Zusammenhang mit der COPACOBANA könnten daher - neben kryptanalytischen Apphkationen - ebenfalls im Bereich der Bioinformatik (z.B. DNS Sequenzierung) liegen.
Projektbezogene Publikationen (Auswahl)
-
S. Kumar, C. Paar, J. Pelzl, G. Pfeiffer, and M. Schimmler. Breaking Ciphers with COPACOBANA ' A Cost-Optimized Parallel Code Breaker. In Proceedings of CHES, pages 101-118. LNCS, 2006.
-
T. Güneysu and C. Paar. Breaking Legacy Banking Standards with Special-Purpose Hardware. In Proceedings of Financial Cryptography. LNCS, 2008.
-
T. Güneysu and C. Paar. Breaking Legacy Banking Standards with Special-Purpose Hardware. In Proceedings of Financial Cryptography. LNCS, 2008.
-
T. Güneysu and C. Paar. Ultra High Performance ECC over NIST Primes on Commercial FPGAs. In Proceedings of CHES, volume 5154, pages 62-78. LNCS, 2008.
-
T. Güneysu, C Paar, and J. Pelzl. Special-purpose hardware for solving the elliptic curve discrete logarithm problem. ACM Trans. Reconfigurable Technol. Syst., 1(2):1-21, 2008.
-
T. Güneysu, C Paar, J. Pelzl, G. Pfeiffer, M. Schimmler, and C. Schleiffer. Parallel Computing with Low-Cost FPGAs; A Framework for COPACOBANA. In ParaFPGA Symposioum, LNI, Jülich, Germany, September 4 - 7 2007.
-
T. Güneysu, C. Paar, G. Pfeiffer, and M. Schimmler. Enhancing COPACOBANA for advanced applications in cryptography and cryptanalysis. In Field Programmable Logic and Applications, pages 675-678, 2008.
-
T. Güneysu, T. Kasper, M. Novotny, C. Paar, and A. Rupp. Cryptanalysis with COPACOBANA. IEEE Trans. Comput, 57(11):1498-1513, Nov. 2008.
