Verschlüsselung mit Elliptischen Kurven angekratzt

Forscher der Schweizer Eidgenössischen Technischen Hochschule Lausanne (EPFL) ist es gelungen, eine 112-Bit-Verschlüsselung auf Basis von elliptischen Kurven (ECCp-112) zu knacken. Sie berechneten den zu einem öffentlichen Schlüssel gehörenden geheimen Schlüssel durch Lösen des diskreten Logarithmusproblems für elliptische Kurven, das bei 112 Bit langen Zahlen die Komplexität 2⁶⁰ aufweist. Bei dem geknackten ECC-System handelt es sich um den durch den Standard secp112r1 definierten Parametersatz. Es liegt somit bereits am unteren Ende der Spezifikationen für ECC-Kryptosysteme.

Die Berechnung benötigte rund ein halbes Jahr auf dem EPFL-Cluster aus rund 200 Playstation 3, der bereits der Berechnung der MD5-Kollision zur Erstellung eines gefälschten SSL-Herausgeberzertifikates von RapidSSL diente. Der auf den Cell-Prozessor der PS3 ausgelegte ECC-Code wurde während des Zeitraumes mehrfach optimiert. Nach Angaben der Wissenschaftler hätte die Berechnung lediglich dreieinhalb Monate gedauert, wenn von Beginn an der nun aktuelle Code gelaufen wäre. Der vorige Rekord wurde 2002 auf einem verteilten Cluster aus rund 10.000 PCs innerhalb von 549 Tagen aufgestellt. Damals knackten Wissenschaftler der US-Universität von Notre Dame einen Schlüssel des drei Bit kürzeren ECCp-109.

Dr. Arjen Lenstra, der an dem EPFL-Projekt beteiligt war, erklärte gegenüber heise Security, dass allerdings kaum eine Gefahr für in der Praxis eingesetzte EC-Kryptosysteme bestehe. Die schwächsten anzutreffenden Verschlüsselungen basierten auf ECC mit 160 Bit. Künftige Entwicklungen müssten ohnehin auf ECC mit mindestens 224 Bit setzen, so Lenstra. Laut NIST-Vorgaben muss ECCp-160, das in seiner Verschlüsselungsstärke mit RSA-1024 vergleichbar ist, für den Erhalt einer FIPS-Zertifizierung nach 2010 ohnehin gegen eine stärkere Variante ausgetauscht werden.

Siehe dazu auch:

• PlayStation 3 computing breaks 2^60 barrier, 112-bit prime ECDLP solved, Veröffentlichung der EPFL-Wissenschaftler

(cr)