Dieser Algorithmus bringt die NSA um den Verstand

Probleme der Verschlüsselungen

Neben der NSA, Diffie und Hellmann erkannten aber auch andere Wissenschaftler, dass mit der Verbreitung von Computern neue Möglichkeiten entstanden, um selbst komplizierte und aufwändige Codes und Berechnungen zu lösen. Dadurch wurden viele Systeme angreifbar: Algorithmen konnten unzählige Passwortkombinationen in einer hohen Geschwindigkeit ausprobieren, für die kein Mensch auf der Welt im Stande gewesen wäre. Kryptografie und auch die Krypto-Analyse entwickelten sich rasant weiter.

Lucifer als Sicherheitssystem für die individuelle Privatsphäre

Bereits 1973 warnte der deutsche Kryptograf Horst Feistel, dass Computer zukünftig die individuelle Privatsphäre gefährden würden. Die Schlussfolgerung: Computersysteme sollten ihre Inhalte verschlüsseln, um Unbefugten einen Zugang zu den Daten zu verwehren. Infolgedessen entwickelte Feistel einen komplexen Verschlüsselungsalgorithmus namens „Lucifer“, der die Welt jahrzehntelang schützen sollte. Allerdings wurde die NSA darauf aufmerksam und sicherte sich den Verschlüsselungsalgorithmus, um ihn unter Verschluss zu halten.

Wie funktioniert der Lucifer-Algorithmus?

Der Lucifer-Algorithmus teilt zuerst eine Nachricht in Blöcke auf. Diese werden unabhängig voneinander chiffriert. Gleichzeitig werden die einzelnen Blöcke immer wieder in die Hälfte geteilt, vermischt und sogar noch verschlüsselt. Der Algorithmus war so aufgebaut, dass sich dieser nur dann umkehren lässt, wenn jemand den Schlüssel kennt. Derjenige kann die Nachricht am Ende wieder entziffern.

Das US-Unternehmen „IBM“ spezifizierte den Algorithmus weiter, sodass auch erstmalig Bankautomaten abgesichert werden konnten, wenn diese Daten zum Bankgroßrechner schickten. Allerdings war das Vorgehen auch mit einem hohen Risiko verbunden, denn IBM musste darauf vertrauen, dass sich die Verschlüsselung nicht durch einen ausgeklügelten Trick knacken lässt. Ansonsten hätten Hacker zahlreiche Bankautomaten leeren können.

Sichere Verschlüsselungssysteme waren für das beginnende Elektronikzeitalter unumgänglich, sodass auch die US-Regierung die Relevanz erkannte. Daher suchte die Standardisierungsbehörde National Institute of Standards and Technology (NIST) (damals NBS, National Bureau of Standards) Anfang der 70er Jahre nach einem Verschlüsselungsalgorithmus, der hohe Sicherheitsanforderungen erfüllt. Allerdings blieben die Einsendungen zunächst aus. Der Grund dafür war offensichtlich: Es gab kaum Wissenschaftler, die außerhalb der NSA an den Themen forschten.

Lediglich das Lucifer-System erfüllte alle Voraussetzungen. Noch bevor der Algorithmus veröffentlicht wurde, machte die NSA dem verantwortlichen IBM-Mitarbeiter ein Angebot. Die NSA gab an, den Algorithmus gründlich zu prüfen und anschließend öffentlich die damit einhergehende Sicherheit zu garantieren. Im Gegenzug dafür sollte sich das Unternehmen verpflichten, den Lucifer-Code geheim zu halten und nur Verschlüsselungschips zu verkaufen. Spätestens jetzt war der Lucifer-Algorithmus eine Geheimsache, denn die betroffenen IBM-Mitarbeiter durften nicht mehr über ihre Arbeit sprechen.

Das damalige NBS gab im Jahr 1975 seine Empfehlung bekannt: Der auf Lucifer basierende „Data Encryption Standard (DES)“. Anstelle des Vorschlags von Feistel bei seinem Lucifer-Code (128 Bit – eine Schlüssellänge von einer Zeichenkette aus 128 Kombinationen von Nullen und Einsen), besaß der NBS-Schlüssel 56 Bit.

Die Schlüssellänge war nicht nur deutlich kürzer, sondern auch ungewöhnlich: Oftmals wurden in der Informatik nämlich Zweierpotenzen verwendet. Viele Wissenschaftler vermuteten daraufhin, dass die NSA die Schlüssellänge gekürzt habe, um bedeutsame Nachrichten entschlüsseln zu können.

Ist ein kurzer Schlüssel sicher genug?

Mittlerweile wurde bekannt, dass die NSA tatsächlich forderte, die Schlüssellänge von 64 auf 48 Bit zu reduzieren. Als Kompromiss einigte man sich auf einen 56-Bit-Schlüssel. Ziel sei es nach NSA-Angaben gewesen, ein Kryptografie-Niveau zu finden, welches die Privatsphäre von Einzelpersonen und Unternehmen gegenüber der Konkurrenz schützt. Zudem wollte die NSA sicherstellen, dass die Verschlüsselungen auch im Notfall geknackt werden können.

Schaut man sich die tatsächlichen Rechenzeiten an, werden die Auswirkungen deutlich: Wenn man beispielsweise einen Schlüssel mit 128 Bit erraten möchte und nur weiß, dass dieser aus 128 Nullen und Einsen besteht, muss man alle Kombinationen durchprobieren.

Da es kumuliert 128 Zeichen mit zwei optionalen Werten gibt (0 oder 1), resultieren daraus 2 hoch 128 verschiedene Möglichkeiten. Die Anzahl der möglichen Kombinationen reduziert sich bei einer Länge von 127 Bit bereits um 50 %. Wenn man nun die Frage nach der Realisierbarkeit, ein derartig verschlüsseltes Passwort zu knacken, stellt, könnte man moderne Technologie heranziehen. Denn ein Computer mit einem 3 Ghz-Prozessor führt pro Sekunde rund drei Milliarden Rechnungen durch. Möchte dieser die 2 hoch 128 Möglichkeiten durchspielen, bräuchte er 10 hoch 21 Jahre. Dies ist vereinfacht gesagt ein Zeitraum, der deutlich länger als die Existenz unseres Universums ist.

Demgegenüber könnte eine 56-Bit-Verschlüsselung von den Computern bereits in 7,5 Jahren entschlüsselt werden – immer noch ein langer Zeitraum, doch die 128 Bit-Verschlüsselung kann somit ein signifikantes Mehr an Sicherheit gerieren.

Daraufhin gab es massive Beschwerden von Wissenschaftlern über die Schlüssellänge. Diese forderten eine Anpassung, unter anderem auch Diffie und Hellman. Aber es passierte nichts. Erst im Jahr 2000 wurde ein sichereres Verfahren namens AES eingesetzt und ersetzte das DES. Bis dahin bewiesen
Informatiker, dass sich die ursprüngliche DES-Verschlüsselung mit ausgeklügelten Tricks in nur 22 Stunden entschlüsseln lässt.

Schwachstellen der Verschlüsselungssysteme

Diffie grübelte nicht nur über die Schlüssellänge des DES-Standards, sondern er verwies auch ansonsten auf diverse Schwachstellen aller Verschlüsselungssysteme. Er stellte die Frage, wer den Schlüssel bereitstellt, wenn zwei Parteien geheime Informationen untereinander austauschen wollen. Daher wird eine
zentrale Anlaufstelle benötigt, die den Schlüssel bereitstellen kann.

In den 1970er Jahren war das zwar noch kein allzu großes Problem, da nur wenige Firmen und militärische Institutionen auf digitale Verschlüsselungsalgorithmen zurückgegriffen haben. Als die elektronische Kommunikation dann aber auch im privaten Raum an Relevanz gewann, konnte man davon ausgehen, dass eine solche Schlüsselverwaltung fast sicher Ziel von Angriffen werden würde.

Etablierung der Public-Key-Kryptografie

1975 fand Diffie dann tatsächlich die Lösung und veränderte damit die Kryptografie für immer. Dabei verstieß er gegen das Grundprinzip der Kryptografie und machte die Schlüssel öffentlich, anstatt sie nur zu verschlüsseln. An diesem Tag wurde die sogenannte „Public-Key-Kryptografie“ erfunden.

Diffie suchte jahrelang vergebens nach Wissenschaftlern, um sich über Verschlüsselungen auszutauschen – bis er auf Martin Hellman traf. Die beiden stritten kontrovers und suchten nach einer Methode, um elektronische Daten abzusichern. Diffies erreichte einen Durchbruch, indem er die Schüssel in zwei Bestandteile teilte. Demnach besitzt eine Person einen privaten und einen öffentlichen Schlüssel. Das Verfahren basierte auf sogenannten „Falltürfunktionen“. Diese bezeichnen mathematische Abbildungen, die sich nur ganz schwer wieder umkehren lassen, zumindest, solange man den privaten Schlüssel nicht besitzt. So ein Verfahren würde eine sichere Kommunikation und sogar Authentifizierungen ermöglichen.

Mit dem Fortschritt des elektronischen Zeitalters wurde die Bedeutung von Authentifizierungen immer größer, denn man musste beweisen, dass man auch die Person ist, die man vorgibt zu sein. Nach seinem Durchbruch wollte Diffie noch am gleichen Tag Hellman davon berichten, der das gigantische Potenzial sofort erkannte. In den darauffolgenden Monaten tüftelten die beiden Wissenschaftler weiter an der Idee und entwickelten ein kryptografisches Protokoll. Dieses veröffentlichten sie im Jahr 1976. Allerdings mussten die Wissenschaftler zunächst ein mathematisches Verfahren finden, welches diese Form der Verschlüsselung auch erlaubt. Sie benötigten eine Falltürfunktion, jedoch war die tatsächliche Existenz einer solchen noch nicht einmal bewiesen.

Diffie und Hellman waren nicht die ersten Wissenschaftler, die auf die Idee einer Public-Key-Kryptografie kamen. Auch der Doktorand Ralph Merkle von der University of California in Berkeley hatte einen ähnlichen Einfall. Bereits im Jahr 1975 hatte dieser seine Idee beim Fachjournal „Communications of the ACM“ eingereicht, allerdings lehnten die Gutachter die Public-Key-Kryptografie sofort ab. Der Grund dafür: Die Gutachter sahen ein Problem darin, dass ein Kryptosystem ohne eine sichere Übermittlung der Schlüssel funktionieren sollte. Als Merkles registrierte, dass Diffie und Hellman eine ähnliche Methode entwickelt hatten, nahm er sofort Kontakt auf. Anschließend schickte er den beiden Wissenschaftlern eine Kopie seines Manuskripts mit (dieses wurde drei Jahre später doch noch veröffentlicht). Diffie und Hellman arbeiteten fortan mit Merkle zusammen an der Public-Key-Kryptografie.

Umsetzung der Public-Key-Kryptografie

1976 fand Hellman dann tatsächlich eine mathematische Umsetzung, die sich für ihren Algorithmus (bzw. einen Teil davon) eignete. Getauft wurde die Innovation auf den Namen „Diffie-Hellman-Schlüsselaustausch“, den sie einige Monate später veröffentlichten. Jedoch hatten sich die beiden Wissenschaftler die Lösung ein wenig anders vorgestellt, denn Hellman hatte anstelle einer mathematischen Falltürfunktion eine Einwegfunktion gefunden.

Was ist eine Einwegfunktion?

Eine Einwegfunktion bezeichnet eine Abbildung, die sich nicht wieder umkehren lässt. Somit war das System nicht dafür geeignet, um verschlüsselte Nachrichten zu übertragen oder Inhalte umzuschreiben, aber zumindest konnte ein Schlüssel zwischen zwei Parteien sicher ausgetauscht werden.

Damit konnten Parteien, die bisherige symmetrische Verfahren wie beispielsweise Lucifer nutzen, nun ohne eine zentrale Schlüsselverwaltung miteinander kommunizieren. Um das Verfahren umzusetzen, benötigt man allerdings eine geeignete mathematische Funktion. Die mathematische Funktion sollte also einfach zu berechnen, aber dennoch schwer umzukehren sein. Hellman fand schließlich eine Methode auf der Basis von ganzzahligen Exponenten. Allerdings wächst die Berechnungsdauer exponentiell mit der Größe der gewählten Zahlen an. Ansonsten ließ sich der Algorithmus von Hellmann und Diffie zur Schlüsselgenerierung schnell ausführen und eignete sich damit für praktische Anwendungen.

Angriff der NSA auf die Forschungsfreiheit

Die Arbeiten von Diffie und Hellman verbreiteten sich dynamisch. Mathematiker wie Adi Shamir, Ron Rivest und Leonard Adleman analysierten die Forschungsideen und veröffentlichten 1977 erste Entwürfe, um tatsächliche Falltürfunktionen zu entwerfen. Damit konnte die Public-Key-Kryptografie doch noch realisiert und in die Praxis umgesetzt werden.

Mit einer Falltürfunktion können auf sichere Weise Schlüssel ausgetauscht und gleichzeitig Dateien signiert und Nachrichten verschlüsselt werden. Diese Methode wurde „RSA-Kryptosystem“ genannt und wird bis heute angewendet.

Selbstverständlich gingen die gravierenden Fortschritte nicht an der NSA vorbei. Zuerst hielt sich die Behörde zurück und agierte im Hintergrund. Die NSA wollte das alleinige Forschungsmonopol bei diesem Thema. Der Geheimdienst berief sich aber auch auf den ITAR-Code (International Traffic in Arms Regulations), dem US-amerikanischen Regelwerk zum Rüstungshandel. Daher zählten kryptografische Geräte und Datenschutzvorrichtungen als „Waffen“ und durften nicht einfach exportiert werden. Infolgedessen durfte auf Konferenzen oder in Fachartikeln nicht über Kryptosysteme gesprochen werden.

Diese Regelungen sorgten für einen Aufschrei der Wissenschaft: Forscher am MIT und Stanford tauschten sich mit den Vorgesetzten und Rechtsberatern der Universitäten aus. Die juristischen Experten konstatieren die rechtliche Bedenkenlosigkeit, die Forschungsergebnisse zu veröffentlichen – eine gewisse Unsicherheit blieb jedoch vorhanden. Daher stellte Hellman seine Ergebnisse auf einem Kongress selbst vor und bezog keine Studenten ein, um diese vor rechtlichen Nachteilen zu schützen.

Weitere Auseinandersetzungen zwischen der NSA und der Wissenschaft sollten in den nächsten Jahrzehnten folgen.

Die NSA heute

Die geleakten Dokumente von Snowden offenbaren, dass die Geheimdienstbehörde auch heute noch versucht, verschlüsselte Informationen abzugreifen. Zudem baut die NSA mit dem Utah Data Center eines der weltweit größten Datenzentren. Dieses soll Schätzungen zufolge so viel Speicherplatz umfassen, um zu jeder Person auf der Erde rund ein Gigabyte an Information zu sichern. Diese Art „Festplatte“ speichert aber nicht nur Audio- und Testmaterial, sondern auch Bilder und Videos.