ECC - Elliptic Curve Cryptography (elliptische Kurven)

Krypto-Systeme und Verfahren auf Basis elliptische Kurven werden als ECC-Verfahren bezeichnet. ECC-Verfahren sind ein relativ junger Teil der asymmetrischen Kryptografie und gehören seit 1999 zu den NIST-Standards. Das sind aber keine eigenständigen kryptografischen Algorithmen, sondern sie basieren im Prinzip auf dem diskreten Logarithmus bei reellen Zahlen, wie man es von Diffie-Hellman und DSA kennt. Typische Anwendungsfälle sind der Schlüsselaustausch und Signaturverfahren.

Elliptische Kurven weisen eine äußerst komplexe Mathematik auf, die sich leider nicht ohne umfangreiche mathematische Kenntnisse verstehen und schon gar nicht einfach darstellen lässt. Grob gesagt basieren ECC-Verfahren auf Operationen mit Punkte-Paaren auf bestimmten elliptischen Kurven.
Trotz der Komplexität ist die Mathematik hinter den ECC-Verfahren ausreichend gut erforscht. Die meisten Kryptografen empfehlen die ECC-Verfahren bevorzugt einzusetzen.

Diffie-Hellmann mit elliptischen Kurven (ECDH) kann einfaches Diffie-Hellman praktisch ersetzen. ECDH hat den Vorteil, dass ein 256-Bit-Schlüssel genügt, um ein Sicherheitsniveau von 128 Bit zu erreichen. Genauso, wie ein 512-Bit-Schlüssel ein Sicherheitsniveau von 256 Bit hat. ECDH ist also deutlich schneller und effizienter als einfaches Diffie-Hellman.
Aktuelle Kryptobibliotheken enthalten Implementierungen von Diffie-Hellman mittels elliptischer Kurven (ECDH). Allerdings ist das noch nicht lange so, weshalb ECC-Verfahren noch nicht weit verbreitet sind. Das ist ein typisches Problem in der Kryptografie, dass sich neue Verfahren nur sehr langsam verbreiten. Auch dann, wenn sie tatsächlich und nachweisbar besser sind.

Warum ECC-Verfahren und elliptische Kurven?

Asymmetrische Verschlüsselung mit RSA hat das Problem, dass die erforderlichen Schlüssellängen, sehr lang und in Zukunft noch länger sein müssen, damit RSA sicher ist. Um mit RSA ein Sicherheitsniveau zu erreichen, dass einem symmetrischen Verfahren wie AES mit einer Schlüssellänge von 128 Bit entspricht, muss man bspw. bei RSA mit einer Schlüssellänge mit mehr als 3.000 Bit arbeiten. Da man bei symmetrischen Verfahren schon eine Schlüssellänge von 256 Bit empfiehlt, benötigt ein RSA-Schlüssel über 15.000 Bit. Auf der einen Seite sind diese Schlüssellängen nicht mehr handhabbar und gleichzeitig wirkt sich ein langer Schlüssel negativ auf die Dauer der Berechnung aus. Da hilft auch nicht mehr Rechenleistung. Es braucht Alternativen. Deshalb werden ECC-Verfahren empfohlen, die mit kürzeren Schlüsseln auskommen.

Standardisierung

Der Einsatz elliptischer Kurven setzt voraus, dass beide Kommunikationspartner die selbe Kurve unterstützten. Das heißt, man kann nicht einfach irgendeine Kurve einsetzen. Es muss eine bestimmte sein. Und im Prinzip will man gar nicht so viele Kurven einsetzen, weil jede Kurve implementiert werden muss. Aber prinzipiell kann jede elliptische Kurve verwendet werden, wenn man einen Kommunikationspartner findet, der diese Kurve unterstützt

Für ECC-Verfahren stehen diverse elliptische Kurven der NIST und Brainpool-Kurven vom BSI zur Auswahl. Für Signatur-Schlüssel gibt es auch Dan J. Bernsteins Curve 25519. Verschlüsselung ist aber noch nicht möglich.
Wegen Bedenken vieler Experten bezüglich der NIST- und Brainpool-Kurven soll Curve 25519 in Zukunft die bevorzugte elliptische Kurve sein.

Kritik an elliptischen Kurven

Die meisten Kryptografen sehen es so, dass an ECC-Verfahren kein Weg vorbei führt. Wenn da nicht die NSA wieder ihre Finger im Spiel hätte. Generell gelten die durch den Einfluss der NSA von der NIST spezifizierten Standards als kompromittiert. Der Grund ist, dass im Sinne ihrer Funktion die NSA nicht an verschlüsselten Verbindungen ohne Hintertüren oder Schwächen interessiert ist. Doch warum sollte man ein vermutlich schwaches Verfahren einsetzen?

Bei den ECC-Verfahren, die von der US-amerikanischen NIST standardisiert und mit der Hilfe der NSA entwickelt wurden, wird vermutet, dass die NSA die Standardisierungen zu ihren Gunsten beeinflusst hat.
Experten halten es für wahrscheinlich, dass sich die NSA irgendeinen Vorsprung gesichert hat, den sie bei Angriffen auf ECC-Verfahren zur Anwendung bringt.
Konkret wird vermutet, dass sich beispielsweise das ECC-Verfahren mit "secp{256,384,521}r1" leichter brechen lässt. Es enthält eine gezielte Vorgabe bestimmter Startwerte (Seeds) für die Verschlüsselung. In diesem Fall ist das ECC-Verfahren nicht vertrauenswürdig. Normalerweise sollten die Startwerte pseudozufällig sein, wie es bei "secp{256,384,521}k1" der Fall ist. Es gilt noch als sicher.
Von der modernen ECC-Variante Curve25519, die nicht von der NIST stammt, sind bisher keine Manipulationen bekannt.

Von den Standardkurven ist bekannt, dass für Angriffe nicht die Schwächen im Logarithmus der Kurve (elliptic-curve discrete-logarithm problem, ECDLP) am besten sind, sondern die Verschlüsselung selbst. Wenn ein Angreifer zum Beispiel spezielle Kurvenpunkte als Eingabe wählt, die Fehler in Implementierungen triggern, könnte der Angreifer an Informationen über die geheimen Schlüssel kommen.

Kryptografie auf Basis elliptischer Kurven steht also berechtigterweise in der Kritik. Man geht aber nicht davon aus, dass die Kurven möglicherweise mit Hintertüren erzeugt wurden, sondern sehr komplexe Rechenregeln aufweisen die man nicht richtig prüfen kann. Dadurch können Implementierungen anfällig für Fehler sein, die die NSA für die Entschlüsselung oder das Brechen der Verschlüsselung nutzen kann.

Curve25519 und Ed25519

Dan Bernstein hat im Jahr 2006 seine Curve25519 vorstellte. Es handelt sich um ein Diffie-Hellman-Verfahren auf Basis einer elliptischen Kurve, das man für den Austausch des geheimen Sitzungsschlüssels nutzen kann.
Diese Kurve arbeitet mit einer kurzen Kurvengleichung und mit Primzahlen, die man sich merken kann. So rechnet Curve25519 mit der Primzahl 2255-19. Durch diese Einfachheit können Fehler in der Anwendung verhindert werden.

Es hat bisher keine Standardisierung stattgefunden. Es gibt nur einen IETF-Draft. Und selbst dann, wenn der es zum Standard schafft kann es Jahre dauern, bis er in der Breite zur Anwendung kommt.
Nichts desto trotz ist diese Kurve schon in einigen Anwendungen im Gebrauch. Beispielsweise beim Anonymisierungsnetzwerk Tor, im mobilen Betriebssystem iOS von Apple und in verschiedenen Open-Source-Software-Projekten von GNUnet bis OpenSSH und GnuPG.

Parallel steht mit Ed25519 auch eine Alternative zu DSA und ECDSA für digitale Signaturen und somit für die Authentifizierung zur Verfügung. Ed25519 ist deutlich schneller als andere auf dem diskreten Logarithmus basierende Verfahren.

Wie sicher sind elliptische Kurven?

Außer dass die NSA ihre Finger mit im Spiel hat, gelten ECC-Implementierungen als äußerst kritisch. Beim Implementieren muss man äußerst sorgfältig vorgehen, um keine Fehler zu machen.
Gerade die Standard-Kurven der NIST oder bspw. auch des deutschen BSI sind anfällig gegen Seitenkanal-Angriffe auf der Basis von Timing- oder anderen Meta-Informationen.
Verschlüsselung auf Basis elliptischer Kurven ist nur dann sicher, wenn die verwendete Kurve sehr sorgfältig ausgesucht wurde.

Übersicht: ECC-Verfahren

Bei den meisten ECC-Verfahren handelt es sich um Algorithmen, die elliptische Kurven mit bekannten Verfahren kombinieren.

Übersicht: Asymmetrische Kryptografie