Krypto 2020 Aussichten für langfristige kryptographische Sicherheit

Ordnungsmerkmale

erschienen in: <kes> 2006^#5, Seite 74

Zusammenfassung: Krypto-Schlüsseln und -Algorithmen droht Gefahr durch die fortschreitende Entwicklung leistungsfähiger Hardware und neuer mathematischer Verfahren. Wie lange können die heutigen Verfahren noch halten, was sie versprechen? Und welche Alternativen zeichnen sich für die Zeit danach ab?

Autor: Von Johannes Buchmann, Erik Dahmen, Alexander May und Ulrich Vollmer, Darmstadt

Kryptographie ist ein Grundbaustein aller IT-Sicherheitslösungen. Aber wie lange sind die heute benutzten kryptographischen Verfahren noch sicher? Reicht diese Zeit, um zum Beispiel medizinische Daten lang genug geheim zu halten? Schon kurzfristig ließe sich bereits großer Schaden anrichten, wenn auch nur bestimmte Schlüssel gebrochen würden: Etwa bei den digitalen Signaturen, welche die Authentizität von automatischen Windows-Updates sichern.

Verbreitete Verfahren

In ihrer berühmten Arbeit aus dem Jahr 1978 stellten Rivest, Shamir und Adleman [8] das RSA Public-Key-Verschlüsselungs- und Signaturverfahren vor. RSA ist auch heute noch das in der Praxis meistverwendete Public-Key-System. Die Sicherheit von RSA beruht auf der Schwierigkeit, so genannte RSA-Moduln N=pq in ihre (großen) Primfaktoren p und q zu zerlegen. In ihrer Arbeit schlugen die Erfinder von RSA damals vor, für langfristige Sicherheit 200-stellige RSA-Moduln zu verwenden. Später veröffentlichte die Firma RSA Security eine Liste von RSA-Moduln wachsender Größe (RSA Challenge Numbers) und setzte Preise von insgesamt 635.000 US-$ für das Faktorisieren dieser Zahlen aus (siehe  www.rsasecurity.com/rsalabs/).

Im Jahr 2005, also 27 Jahre nach der Erfindung von RSA, gelang es Bahr, Boehm, Franke und Kleinjung von der Universität Bonn bereits innerhalb von fünf Monaten eine 200-stellige RSA-Challenge zu faktorisieren (640-Bit-RSA-Schlüssel) [5] – und damit die ursprüngliche Empfehlung langfristiger Sicherheit zu brechen. Dies belegt anschaulich die Fortschritte der letzten 30 Jahre bei der Faktorisierung von RSA-Moduln. Diese beruhen sowohl auf bahnbrechenden mathematischen Ideen, zum Beispiel der Entwicklung des Zahlkörpersiebs durch John Pollard, als auch auf bedeutenden Fortschritten in der Computer- und Implementierungstechnik.

Lenstra und Verheul [6] entwickelten 2000 eine Extrapolationsformel zur Voraussage der Sicherheit von RSA und anderen wichtigen kryptographischen Verfahren (vgl.  www.keylength.com). Dieser Formel zufolge muss man derzeit schon 850-stellige RSA-Moduln verwenden, um Sicherheit für die nächsten dreißig Jahre zu gewährleisten (entspr. ca. 3072-Bit-RSA-Schlüsseln).

Aber auch eine solche Extrapolationsformel ist keine Sicherheitsgarantie! Brillante mathematische Ideen könnten jederzeit dazu führen, dass das Lösen des Faktorisierungsproblems "leicht" und RSA damit generell unbrauchbar wird. So bewies beispielsweise Peter Shor 1996, dass ein Quantencomputer – ein neuer Computertyp, der die Gesetze der Quantenmechanik ausnutzt – große Zahlen sehr schnell faktorisieren könnte. Trotz intensiver Forschungsbemühungen ist es aber auch heute noch unklar, ob sich jemals hinreichend leistungsfähige Quantencomputer bauen lassen.

Analog zu RSA verläuft die Entwicklung bei Angriffen auf die meistverwendeten Public-Key-Alternativen: den Digital Signature Algorithm (DSA) und Elliptic Curve Cryptography (ECC), die beide auf der Schwierigkeit der Berechnung diskreter Logarithmen beruhen. Es gibt schon heute deutliche algorithmische Fortschritte und Quantencomputer würden diese Verfahren ebenfalls unsicher machen.

Wie steht es um die langfristige Sicherheit von so genannten Secret-Key-Verschlüsselungsverfahren? DES wurde 1977 als Data Encryption Standard eingeführt [3] – 21 Jahre später stellte die Electronic Frontier Foundation (EFF) den Spezialcomputer Deep Crack vor, der DES in 56 Stunden brechen konnte. Das Problem von DES war die zu kurz gewählte Schlüssellänge: Offenbar hatten seine Erfinder die rasante Entwicklung bei der Hardware nicht richtig einkalkuliert. Der DES-Nachfolger Advanced Encryption Standard (AES) [2] gilt heute als sicher, wenngleich interessante Angriffsversuche mit algebraischen Methoden existieren.

Vorsorge für morgen

Ist die heutige Kryptographie angesichts ihrer wachsenden Bedeutung noch sicher genug? Die Erfahrung zeigt: Sorgfältig konzipierte und implementierte kryptographische Verfahren haben eine Lebensdauer von 5 bis 20 Jahren. Wer heute RSA, ECC oder AES zur kurzfristigen Absicherung verwendet, darf sich sicher fühlen. Und langfristige Verbindlichkeit lässt sich beispielsweise mit den von Jan Sönke Maseberg vorgeschlagenen multiplen Signaturen lösen [7].

Aber langfristige Vertraulichkeit können wir heute mit den genannten Verfahren nicht garantieren. Und was ist in 20 Jahren? Was kann man tun, wenn ein unerwarteter mathematischer Fortschritt ein wichtiges Kryptoverfahren plötzlich – quasi über Nacht – unsicher macht? Drei Dinge sind zur Vorbereitung nötig:

• ein Pool alternativer sicherer Kryptoverfahren,
• Infrastrukturen, die es ermöglichen, unsichere kryptographische Verfahren leicht gegen sichere auszutauschen und
• Verfahren, die langfristige Vertraulichkeit sicherstellen.

Diese Ziele verfolgen die Kryptoarbeitsgruppe der TU Darmstadt und der daraus entstandene Spin-off FlexSecure ( www.flexsecure.de) seit vielen Jahren. Die Trustcenter-Software FlexiTrust, die in der deutschen nationalen Root-Zertifizierungsstelle und in der deutschen Country-Signing-Zertifizierungsstelle verwendet wird, ist eine Infrastruktur, die den einfachen Austausch von Kryptographie möglich macht. Die Open-Source-Bibliothek FlexiProvider [4] stellt zudem eine Vielzahl unterschiedlicher kryptographischer Verfahren zur Verfügung und in jüngerer Zeit laufen intensive Forschungen zur "Post Quantum Cryptography": Kryptographie, die auch dann noch sicher bleibt, wenn es (leistungsfähige) Quantencomputer tatsächlich gibt.

Neue Probleme

Die Sicherheit der Public-Key-Kryptographie beruht traditionell auf der Schwierigkeit, bestimmte mathematische Probleme zu lösen. Heute diskutierte Alternativen zum Faktorisierungs- und Diskrete-Logarithmen-Problem sind: das Dekodierungsproblem, das Problem, kürzeste und nächste Gittervektoren zu berechnen, und das Problem, quadratische Gleichungen mit vielen Variablen zu lösen. Es wird vermutet, dass diese Probleme auch von Quantencomputern nicht effizient lösbar wären.

Wie sehen diese Alternativen näher aus? Verschlüsselung auf der Basis des Dekodierungsproblems wurde von McEliece erfunden. Der Hintergrund: Fehlerkorrigierende Codes dienen dazu, digitale Informationen so zu speichern, dass sie selbst dann noch vollständig lesbar bleiben, wenn einzelne Bits auf dem Speichermedium verändert werden. Diese Eigenschaft nutzen zum Beispiel CDs, sodass Informationen auf leicht verkratzten Datenträgern immer noch vollständig rekonstruierbar sind.

Bei der codebasierten Verschlüsselung werden Daten chiffriert, indem zu ihrer Kodierung mit einem öffentlich bekannten Code gezielt Fehler addiert werden, das heißt einzelne Bits werden verändert. Die Entschlüsselung erfordert die Kenntnis einer geeigneten Dekodierungsmethode, welche diese Fehler effizient zu entfernen vermag. Diese Methode ist der geheime Schlüssel – nur wer sie kennt, kann dechiffrieren. Codebasierte Public-Key-Verschlüsselung ist im Allgemeinen sehr effizient durchführbar. Derzeit wird daran geforscht, welche Codes dabei zu sicheren Verschlüsselungsverfahren führen.

Verschlüsselung auf der Grundlage von Gitterproblemen ist den codebasierten Verschlüsselungsverfahren sehr ähnlich. Gitter sind regelmäßige Strukturen von Punkten im Raum. Zum Beispiel bilden die Eckpunkte der Quadrate auf kariertem Papier ein zweidimensionales Gitter. In der Kryptographie verwendet man jedoch Gitter in viel höheren Dimensionen. Verschlüsselt wird nach dem folgenden Prinzip: Aus dem Klartext wird zunächst ein Gitterpunkt konstruiert und anschließend geringfügig verschoben, sodass er zwar kein Gitterpunkt mehr ist, aber in der Nähe eines solchen liegt. Wer ein Geheimnis über das Gitter kennt, kann den korrespondierenden Gitterpunkt in der Nähe finden und damit entschlüsseln. Ein besonders praktikables Gitterverschlüsselungsverfahren ist NTRU ( www.ntru.com).

Neue Signaturen

Die Verwendung des Problems des Lösens quadratischer Gleichungssysteme eignet sich als Basis besonders gut zur Konstruktion von effizienten Signaturverfahren. So bietet beispielsweise das SFlash-Verfahren um ein Vielfaches kürze Signaturen als RSA bei heutzutage gleichem Sicherheitslevel.

Besondere Beachtung bei zukünftigen Signaturen verdient auch das Merkle-Verfahren: Es wurde von Ralph Merkle bereits 1979 in seiner Dissertation angedeutet und 1989 publiziert. Im Gegensatz zu allen anderen Signaturverfahren beruht seine Sicherheit nicht darauf, dass ein zahlentheoretisches, algebraisches oder geometrisches Problem schwer lösbar ist. Benötigt wird ausschließlich, was andere Signaturverfahren ebenfalls voraussetzen: eine sichere kryptographische Hash-Funktion und ein sicherer Pseudozufallszahlengenerator. Jede neue Hash-Funktion führt somit zu einem neuen Signaturalgorithmus, wodurch das Merkle-Verfahren das Potenzial hat, das Problem der langfristigen Verfügbarkeit digitaler Signaturverfahren zu lösen.

Merkle verwendet in seiner Konstruktion so genannte Einmal-Signaturen: Dabei benötigt jede neue Signatur einen neuen Signierschlüssel und einen neuen Verifikationsschlüssel. Die Idee von Merkle ist es, die Gültigkeit vieler Verifikationsschlüssel mittels eines Hash-Baums auf die Gültigkeit eines einzelnen öffentlichen Schlüssels zurückzuführen (Details siehe Kasten). Im Merkle-Verfahren muss man bei der Schlüsselerzeugung eine Maximalzahl möglicher Signaturen festlegen, was lange wie ein gravierender Nachteil aussah. In [1] wurde aber eine Variante des Merkle-Verfahrens vorgestellt, die es ermöglicht, äußerst effizient mit einem einzigen Schlüsselpaar bis zu 2⁴⁰ Signaturen zu erzeugen und zu verifizieren.

Fazit

Ungelöst bleibt aus Sicht der heutigen Kryptographie das Problem der langfristigen Vertraulichkeit: Ein praktikables Verfahren, das die Vertraulichkeit einer verschlüsselten Nachricht über einen sehr langen Zeitraum sicherstellt, ist derzeit nicht bekannt. Einen Ausweg kann hier möglicherweise die Quantenkryptographie liefern: Sie ermöglicht Verfahren zum Schlüsselaustausch, deren Sicherheit auf der Gültigkeit der Gesetze der Quantenmechanik beruhen. Jedoch sind bekannte Verfahren der Quantenkryptographie derzeit noch sehr ineffizient und es ist unklar, welche kryptographischen Funktionen damit realisiert werden können.

Wie lautet die Bilanz? Die heutige Kryptographie liefert gute Werkzeuge, um kurzfristige und mittelfristige Sicherheit zu gewährleisten. Anwendungen können diese Werkzeuge ruhigen Gewissens verwenden, solange sie in der Lage sind, unsichere Komponenten schnell gegen Alternativen auszutauschen.

Um IT-Sicherheit auch für die Zukunft zu garantieren, müssen wir ein Portfolio sicherer kryptographischer Funktionen vorbereiten. Es benötigt Verfahren, die sowohl für die Welt der allgegenwärtigen (weniger leistungsfähigen) Computer geeignet sind als auch dann sicher bleiben, wenn es leistungsfähige Quantencomputer gibt. Einige viel versprechende Kandidaten für ein solches Portfolio wurden in diesem Artikel vorgestellt; diese müssen jedoch noch sorgfältig erforscht und für die Praxis aufbereitet werden. Die Frage nach einem Verfahren zur Sicherung langfristiger Vertraulichkeit bleibt ein wichtiges offenes Problem, auf das sich zukünftige Forschung fokussieren sollte.

Prof. Dr. Johannes Buchmann ist Professor für Informatik und Mathematik sowie Vizepräsident der TU Darmstadt. Prof. Dr. Alexander May ist Juniorprofessor, Dr. Ulrich Vollmer und Dipl.-Math. Erik Dahmen sind Mitarbeiter am Fachbereich Informatik – Kryptographie und Computeralgebra der TU Darmstadt.

zurück zum Inhalt
© SecuMedia-Verlags-GmbH, 55205 Ingelheim (DE),
<kes> 2006^#5, Seite 74