Copacobana

Copacobana (Cost-Optimized Parallel Code Breaker) ist eine anwendungsspezifische parallele Rechnerarchitektur, bestehend aus Field Programmable Gate Arrays (FPGA). Das System wurde 2006 von zwei Arbeitsgruppen an den Universitäten Bochum und Kiel gebaut. Es stellt ein adäquates Zielsystem für jegliche parallelisierbare Anwendung mit geringem Speicher- und Kommunikationsbedarf dar.

Copacobana

Hintergrund

Die Kryptoanalyse ist ein wichtiges Instrument zur Bestimmung der Sicherheit der heutzutage verwendeten und offengelegten Kryptosysteme. Dabei sind die symmetrischen und asymmetrischen Chiffrierverfahren am weitesten verbreitet, obwohl sie durch die Brute-Force-Methode, einem Ausprobieren aller möglichen Schlüssel, grundsätzlich zu brechen sind. Daher wird die Sicherheit maßgeblich durch den benötigten Rechenaufwand zur Kryptoanalyse und den damit verbundenen monetären und zeitlichen Kosten bestimmt, sofern das Kryptosystem keine systematischen Schwächen birgt, die eine andere Form der Kryptoanalyse ausnutzen könnte.

Motivation

Für die Brute-Force-Methode wird in der Regel der PC als Standardarchitektur mit seinem Preis-Leistungs-Verhältnis herangezogen. Doch dieser Vergleich ist nur gerechtfertigt, wenn es kein System mit einem günstigeren Preis-Leistungs-Verhältnis, bezogen auf den Algorithmus der Kryptoanalyse, gibt. Hier zeigt sich die Technik programmierbarer logischer Schaltungen dem PC gegenüber als leistungsfähiger. So kann beispielsweise im Data Encryption Standard (DES) ein FPGA vom Typ Xilinx Spartan-3 1000 vierhundert Millionen Schlüssel pro Sekunde berechnen, wohingegen ein PC vom Typ Intel Pentium 4 mit 2 GHz für den ungefähr vierfachen Preis nur ca. zwei Millionen DES-Schlüssel pro Sekunde berechnen kann. Eine anwendungsspezifische integrierte Schaltung (ASIC) böte ab einer Stückzahl von ca. 10000 integrierter Schaltkreise ein noch besseres Preis-Leistungs-Verhältnis, doch müsste für jedes der zu analysierenden Kryptosysteme eigens ein neues System gebaut werden. Sowohl die erforderliche Stückzahl der Chips als auch die Baukosten pro Anwendungsfall relativieren den Preisvorteil derart, dass der FPGA-basierte Ansatz deutliche Vorzüge zeigt.

Hardware-Architektur

Die Entwicklung von Copacobana wurde unter konsequenter Ausschöpfung architektonischer sowie technischer Freiheiten vorgenommen, um das primäre Ziel des auf Kryptoanalyse bezogenen Preis-Leistungs-Verhältnisses und das sekundäre Ziel eines Kostenrahmens von 10.000 USD, zu erreichen. Auf diese Weise ist ein paralleler re-konfigurierbarer Computer, bestehend aus 120 FPGAs (Xilinx Spartan-3 1000), entstanden, bei dem aus Kostengründen auf Speicher und eine leistungsfähige Interkommunikation der FPGAs verzichtet wurde. Der Stromverbrauch beträgt unter Volllast etwa 600 W. Das Gerät ist in ein gängiges 19-Zoll-Rack montierbar und 3 HE hoch. Ferner existiert eine Spartan-3-5000- und eine Virtex-4-SX35-basierte Variante mit jeweils 128 FPGAs.

Anwendung

Copacobana berechnet eine vollständige Schlüsselsuche des Data Encryption Standards (56-Bit DES) mit einer Rate von 65 Milliarden DES-Schlüsseln pro Sekunde. Dies ergibt eine durchschnittliche Zeit von 6,4 und eine maximale Zeit von 12,8 Tagen zur Schlüsselsuche. Auch wenn aktuelle Kryptosysteme derart lange Schlüssellängen haben, dass auch mit Copacobana eine vollständige Schlüsselsuche außerhalb des Möglichen liegt, so dient es mittels reduzierter Schlüssellänge durch Extrapolation zur kostenbezogenen Sicherheitsbestimmung aktueller Kryptosysteme. Ferner werden schwache Verschlüsselungsverfahren (z. B. ePass) mit Copacobana gebrochen, die wegen der begrenzten Leistungsfähigkeit eingebetteter Systeme immer noch zum Einsatz kommen. Schließlich ist Copacobana generell einsatzfähig für alle parallelen Anwendungen, die durch einen geringen Speicher- und Kommunikationsbedarf charakterisiert sind. Unterdessen steht Copacobana in mehreren anwendungsoptimierten Versionen und Skalierungen zur Verfügung. So ist z. B. die Virtex-4 SX35 basierte Variante geeignet, um Elliptic Curve Cryptography oder die aus GSM bekannten Algorithmen A5/1 und /2 anzugreifen.

Ableger

2007 gründeten die Arbeitsgruppen der Universität Bochum und Kiel den Ableger („spin-off“) SciEngines GmbH, der sich mit dem Vertrieb und der Weiterentwicklung der Copacobana befasst.

Weblinks

• Offizielle Website (englisch)
• Website SciEngines GmbH (englisch)