Verschlüsselung

Übersicht

Kryptologie, Kryptografie, Kryptanalyse

In knappe Worte gefasst ist die Kryptologie die Wissenschaft von algorithmischen Methoden, die Informationen derart aufbereiten, so dass sie nur für authorisierte Personen verständlich werden. Die Kryptografie als Teilgebiet der Kryptologie umfasst die Verschlüsselung der Informationen während sich die Krypt(o)analyse mit dem Brechen der in der Kryptologie angewandten Methoden beschäftigt.

Die Aufgaben der Kryptografie

Im Zuge der Datenübertragung über öffentliche Kanäle kommt der Verschlüsselung der Informationen eine enorme Bedeutung zu. Sind es die Zugangsdaten zum Bankkonto, die vertrauliche Daten über Firmeninterna oder einfach nur die persönliche Email-Korrespondenz, in den meisten Fällen ist die Geheimhaltung der Informationen erwünscht.

Dieser Schutz der Daten vor unbefugter Verwendung durch Dritte definiert gleichzeitig zwei weitere Anforderungen an die Kryptografie. Zum Einen muss sie die Authentizität der Nachricht gewährleisten, d.h. sie muss Mechanismen anbieten, um zu überprüfen, ob eine Nachricht auch tatsächlich vom angegebenen Absender stammt. Und sie muss die Integrität der Daten - also ihre Unverfälschtheit - garantieren.

Digitale Signaturen garantieren die Verbindlichkeit, d.h. einem Absender wird das nachträgliche Leugnen seiner Urheberschaft unmöglich.

Historisches

Die ältesten bekannten Überlieferungen zu Geheimschriften datieren ca. 3000 Jahre zurück; dementsprechend vielgestaltig und umfangreich zeigt sich die Geschichte der Kryptografie (zum Vergleich: Schriften blicken auf 6000 jährige Evolution zurück).
Dies in wenigen Sätzen zu umreißen, ist nur möglich, indem wir einzig die (vermeintlich) markanten Ergeignisse erwähnen und beiläufigen aber keineswegs minder interessante Entwicklungen keinerlei Beachtung schenken.

Dem interessierten Leser möchte ich das Buch »Abenteuer Kryptologie« von Reinhard Wobst empfehlen.

Atbash

Die vielleicht älteste Verschlüsselungstechnik ist unter dem Namen »Atbash« überliefert, welcher jüdischen Ursprungs ist. Es handelt sich um ein einfaches Substitutionsverfahren, wobei als Schlüssel das Alphabet in umgekehrter Reihenfolge dient:

Im zu verschlüsselnden Text wird also jedes A durch ein Z, jedes B durch ein Y usw. ersetzt. WRV ORMFCURYVO DZVIV HXSDVI AF OVHVM ZYVI VRMUZXS AF VMGHXSOFVHHVOM.

In der Bibel unter Jeremia 25,26 wird die mit Atbash verschlüsselte Stadt Sheshak erwähnt. Dabei handelt es sich um die Stadt Babel.

Cäsar-Verfahren

Julius Cäsar war nachweislich der erste, der seine Nachrichten verschlüsselte. In seinem Briefwechsel mit Cicero verwendete er allerdings ein sehr einfaches Substitutionsverfahren, in dem er jeden Buchstaben des Klartextes um den im Alphabet drei Stellen folgenden Buchstaben ersetzte:

Obwohl diese Verfahren mit Atbash verwandt ist, taucht hier etwas Neues auf. Die Sicherheit bei Atbash und anderen alten Geheimschriften beruht darauf, dass das Verschlüsselungsverfahren geheim ist.

Prinzipiell nützt die Kenntnis des Verfahrens bei der Cäsar-Chiffrierung allein nichts. Erst mit dem Schlüssel (hier »Ersetze jeden Buchstaben durch seinen dritten Nachfolger«) kann der Klartext aus dem Geheimtext gewonnen werden.

Simples Durchprobieren der 25 möglichen Schlüssel würde allerdings schnell zum Brechen des Verfahrens führen.

RVAR INEVNAGR QRF PNRFNE-IRESNUERAF VFG EBG13 (EBGNGVBA HZ 13 CBFVGVBARA). QVR NAJRAQHAT QRF IRESNUERAF NHS QRA TRURVZGRKG SHRUEG JVRQRE LHZ XYNEGRKG.

Das Vigenère-Verfahren

Dieses Verfahren geht auf den franzäsischen Diplomaten Blaise de Vigenère (1523 bis 1596) zurück. Hierbei handelt es sich um ein verändertes Cäsar-Verfahren. Beim ursprünglichen Cäsar-Verfahren wird mit einem Geheimtextalphabet gearbeitet, bei dem Vigenère-Verfahren mit mehreren, die wiederholt angewandt werden.

Cäsar verwendete eine einmalige Verschiebung der Buchstaben seiner Klartexte um 3 Positionen. Das Vigenère-Verfahren verwendet hingegen ein Schlüsselwort, das in Wiederholungen unter den Klartext geschrieben wird. Jeder Buchstabe des Klartextes wird nun um die durch den unter ihm stehenden Buchstaben des Schlüssels verschoben. Lautet der Schlüssel bspw. »GEHEIM«, so würde jeder siebte Klartextbuchstabe um denselben Wert rotiert. Die Buchstaben an den Positionen x+1 (also der 1., 7., 14.,...) würden um 6 Positionen (Position von G im Alphabet) verschoben werden, die an den Positionen x+2 bzw. x+4 um 4 Positionen (E) usw.:

Das Vigenère-Verfahren ist also eine mehrfache Anwendung der Cäsar-Chiffrierung. So verzwickt der Geheimtext auch erscheint, so einfach ist das Verfahren mit Hilfe von Computern zu brechen. Immerhin überstand das Verfahren fast 300 Jahre lang jeder Kryptanalyse (gebrochen 1854 durch Mr. Charles Babbage). Für einen erfolgreichen Angriff auf das Verfahren ist einzig die Kenntnis der Sprache des Klartextes notwendig (und ein hinreichend umfangreicher Geheimtext). Zunächst bestimmte Babbage die verwendete Schlüssellänge. Hierzu suchte er im Geheimtext nach sich wiederholenden Zeichenfolgen (mit mindestens 3 Zeichen). Mit der Annahme, dass gleiche Geheimtextzeichenfolgen durch gleiche Klartextpassagen erzeugt wurden (was mit längeren Zeichenfolgen immer wahrscheinlicher wird), beschreibt der Abstand der Zeichenfolgen ein Vielfaches der Schlüssellänge. Aus mehreren solcher Abstände kann letztlich die wahrscheinliche Schlüssellänge berechnet werden. Mit bekannter Länge können die Buchstaben des Geheimtextes, die durch die gleiche Substitution ersetzt wurden, in Mengen eingeteilt werden. Auf diesen Mengen erfolgt letztlich eine Häufigkeitsanalyse der Buchstaben (E ist bspw. im Deutschen der mit Abstand häufigste Vokal).

Enigma

Die Enigma wurde im zweiten Weltkrieg von der deutschen Wehrmacht zur Verschlüsselung ihrer Funksprüche verwendet. Dabei handelte es sich um eine Maschine mit 3 oder 4 Scheiben (Rotoren). Auf beiden Flächen der Scheiben waren je 26 Schleifkontakte angebracht, die die Buchstaben des Alphabets repräsentierten. Jeder Kontakt auf der linken Seite eines Rotors war mit genau einem Kontakt auf der rechten Seite verbunden, wobei die interne Verdrahtung bei den verschiedenen Scheiben differierte. Eine Chiffierung erfolgte durch Anlegen einer Spannung an einem der linken Schleifkontakte. Je nach Stellung der Rotoren zueinander und der Auswahl der Rotoren selbst lag auf der rechten Seite die Spannung an einem anderen Kontakt an. Nach jedem Schritt der Verschlüsselung wurde zunächst der Eingangsrotor um eine Position weiter rotiert. Nach einer vollen Umrundung (26 Schritte) rückte der zweite Rotor eine Position weiter. Vollendete dieser eine Umdrehung, änderte sich die Stellung des dritten Rotors...

Es handelt sich um ein angepasstes Vigenère-Verfahren mit fast unendlich langen Geheimwort (genauer »Anzahl der Buchstaben« hoch »Anzahl der Rotoren«: 17576 bei 3 Rotoren) Das Schlüsselwort entspricht dabei der Anfangsstellung der Rotoren.

Die Enigma galt als sehr sicher. Sie war es aber nicht. Erst 1975 wurde es öffentlich, dass britische und polnischen Mathematiker deutsche Funksprüche im zweiten Weltkrieg entschlüsseln konnten. Dies geschah mit Hilfe einer der ersten Rechenmaschinen, die extra dafür hergestellt wurde.

Weiterentwicklungen der Enigma waren lange nach dem zweiten Weltkrieg noch in Gebrauch und auch heute basiert das crypt(1) Kommando unter einigen UNIX'en auf diesem Algorithmus (Linux crypt verwendet das DES-Verfahren). Gerade durch das Aufkommen schneller Computer wurde es notwendig, neue und sicherere Verschlüsselungsverfahren zu finden.

Moderne Verfahren

»Moderne Verfahren« ist natürlich ein dehnbarer Begriff. Die nachfolgend vorgestellten Algorithmen sind in dem Sinne »modern«, als dass zum jetzigen Zeitpunkt kein Programm bekannt ist, das einen Angriff auf ein solches Verfahren ermöglicht. Allerdings steht und fällt die Sicherheit eines solchen Verfahrens oft mit der verwendeten Schlüssellänge, da die Leistung heutiger Rechner(verbunde) den Brute-Force-Angriffen in endlicher Zeit zum Erfolg verhelfen.

Symmetrische Verfahren

Die so genannten »symmetrischen Verfahren« verwenden zum Ver- und Entschüsseln jeweils den gleichen Schlüssel. Die Symmetrie bezieht sich i.d.R. allein auf den Schlüssel, da für Chiffrierung und Dechiffrierung bis auf wenige Ausnahem stets verschiedene Verfahren zum Einsatz gelangen (eine Ausnahme ist das oben erähnte ROT13). Unter Linux werden symmetrische Verfahren durch das Kommando mcrypt(1) realisiert.

Nachfolgend benennen wir die wichtigsten Vertreter symmetrische Verfahren.

Lucifer

Bei Lucifer handelt es sich um den ersten veröffentlichen Algorithmus (Veröffentlichung 1973 in der Zeitschrift Scientific American), der die Blockchiffrierung verwendete. Nach seinem Erfinder Horst Feistel (1970, IBM) werden derartige Verfahren auch als Feistelnetzwerke bezeichnet.

Die »einfachen« Blockchiffrierungen unterteilen den (bitweisen) Eingabestrom in gleichgroße Blöcke. Jeder Block wird separat mit dem gleichen Verfahren verschlüsselt. In Feistels Verfahren wird nun ein solcher Block in zwei Hälften unterteilt. Jeder Hälfte wird für sich mit einer vom Schlüssel und dem aktuellen Durchlauf abhägigen Funktion verschlüsselt und anschließend mit der jeweils anderen Hälfte verknüpft. Das Verfahren wiederholt sich für den neu entstandenen Block, wobei sich für jeden Durchlauf die Verschlüsselungsfunktion ändert.

Block- Schlüssellänge betragen beim Lucifer-Verfahren jeweils 128 Bit.

DES und DES3

Eine erste Ausschreibung des US-Wirtschaftsministeriums zum Entwurf eines sicheren Verschlüsselungsverfahren brachte zwar enorme Resonanz aber keinen brauchbaren Algorithmus hervor. Erst die wiederholte Ausschreibung im Folgejahr gewann ein Team von IBM mit einer Weiterentwicklung des Lucifer-Verfahrens.

Mit auf 56 Bit reduziertem Schlüssel wurde das Verfahren 1977 vom U.S. National Bureau of Standards als Data Encryption Standard (DES) genormt. Der Grund der Reduzierung ist bis heute ungeklärt und steter Kritikpunkt an dem Verfahren, da hier der Einfluss und eine Hintertür der NSA (National Security Agency) vermutet wird, die die Entwicklungsunterlagen des Kernstücks von DES lange Zeit unter Verschluss hielt.

1997 fanden 14000 über das Internet verbundene Rechner den Schlüssel zu einer mittels DES verschlüsselten Nachricht mit Hilfe eines Brute-Force-Angriffs. Im Jahr darauf demonstrierte die Electronic Frontier Foundation einen 25000$ teure Spezialhardware, die jeden DES-Schlüssel binnen dreier Tage brechen konnte. Spätesten ab diesem Zeitpunkt galt DES als unsicher, wobei die Unsicherheit einzig durch den zu kleinen Schlüsselraum resultiert. Mit heutige Technik dürfte ein DES-Schlüssel binnen weniger Minuten zu finden sein...

Heute werden in kritischen Bereichen deshalb Weiterentwilckungen von DES eingesetzt. Wichtigster Vertreter ist TripleDES (DES3), der den DES-Algorithmus dreifach anwendet mit einem auf 112 Bit erweiteren Schlüssel.

AES

Der Advanced Encryption Standards (AES) resultierte aus einer vom US National Institute for Standards and Technology (NIST) initiierten Ausschreibung (1977) zur Ablösung von DES als amerikanischen Standard. 2001 wurde das auf einen Kryptologie-Algorithmus von Rijndael zurückgehende Verfahren offiziell als Nachfolger von DES bestätigt.

Im Unterschied zu DES unterstützt das neue Verfahren wahlweise Schlüssellängen von 128, 192 oder 256 Bit, so dass Brute-Force-Angriffe auch lange Sicht hin unwahrscheinlich werden. Außerdem unterliegt das Verfahren keinerlei Lizenzbestimmungen und kann von jedem implementiert werden.

Asymmetrische Verfahren

Ein offensichtlicher Nachteil symmetrischer Verfahren besteht im Austausch des Geheimwortes, der oft ungesichert erfolgt und damit eine potentiell Gefahrenquelle darstellt.

Eine Lösung hierfür bieten die so genannten Public-Key-Verfahren, die zwei Paare von Schlüssel verwenden. Der eine öffentliche Schlüssel dient zur Chiffrierung der Nachricht und nur mit dem zugehörigen privaten Schlüssel lässt sich aus der Nachricht wieder der Klartext gewinnen. Alle Verfahren nach diesem Schema werden als asymmetrisch bezeichnet.

Das Prinzip der Public-Key-Verfahren beruht auf mathematische Einwegfunktionen. Ein oft bemütes Beispiel ist die Faktorisierung. Angenommen, Sie multiplizierten zwei relativ große Primzahlen miteinander. Die Rechnung dürfte relativ schnell vonstatten gehen. Nähmen Sie jetzt jedoch ein beliebiges Resultat eines Primzahlenmultiplikation her und versuchten ohne Kenntnis der beiden Faktoren dieselbigen zu berechnen, dann müssten Sie trotz Computerhilfe vermutlich recht viel Zeit investieren. Sind die Faktoren nur groß genug, würden Sie an der Faktorisierung letztlich scheitern. Und genau solche Berechnungsvorschriften, wo die »Hinrechnung« einfach, die »Rückrechnung« allerdings schier unmöglich ist, werden zur Schlüsselerzeugung für asymmetrische Verfahren eingesetzt.

RSA

Das von Rivest, Shamir und Adleman entwickelte RSA-Verfahren ist wohl der bekannteste Vertreter asymmetrischer Verfahren und ein Beispiel der Anwendung der Faktorierung zur Erzeugung der Schlüssel.

Vorab wird die Schlüssellänge fest gelegt. Je länger dieser ist, desto sicherer ist das Verfahren. Allerdings wird es auch langsamer, weshalb bspw. die Secure Shell 1024 Bit als Voreinstellung vorschlägt (ssh-keygen). Dieser Wert gilt als sicher und stellt bei heutige Rechengeschwindigkeit noch keine Bremse dar.

Die gewählte Schlüssellänge beeinflusst die Länge der beiden zu erzeugenden Primzahlen p und q. Jede muss mindestens halb so lang wie die Schlüssellänge sein. Die Erzeugung solcher Primzahlen wird per Zufallsgenerator mit anschließendem Primzahltest vorgenommen. Einige Testverfahren erreichen Trefferraten von nahezu 100%, d.h. nur in ganz ganz seltenen Fällen verkennt ein solches Verfahren eine Nicht-Primzahl als Primzahl.

Eine weitere kleine Primzahl > 1, an die als einzige Bedingung gestellt wird, dass sie zu p-1 und q-1 teilerfremd ist, dient als Exponent e.

Der private Schlüssel d berechnet sich aus

Der öffentliche Schlüssel besteht aus dem Exponenten e und dem Produkt der beiden Primzahlen pq

Zur Verschlüsselung wird der Klartext in Abschnitte unterteilt, die um eins kürzer sind als die Schlüssellänge. Ggf. muss der letzte Block aufgefült werden. Die Bitfolge eines Blocks wird als Zahl k interpretiert. Der Geheimtextblock ist der Rest der Teilung von k^e durch pq.

Die Rückgewinnung des Klartextes erfolgt über die blockweise Zerlegung des Geheimtextes. Der Klartextblock ist der Rest der Teilung von c^d durch pq (c bezeichnet den Geheimtextblock)..

Hier lässt sich ein entscheidender Nachteil der Public-Key-Verfahren erahnen. Diese sind im Vergleich zu dem symmetrischen Verfahren sehr langsam. In der Praxis wird daher häfig mit einer Kombination aus beiden Verfahren gearbeitet. Der Sitzungsschlüssel wird hierzu per asymmetrischen Verfahren chiffriert und zwischen den Partnern ausgetauscht. Anschließend erfolgt die Verschlüsselung nach einem symmetrischen Verfahren mit dem zuvor getauschten Schlüssel. Genau dieses Vorgehen realisiert die Secure Shell.

EIGamal

Der nach seinem Erfinder Taher ElGamal benannten Algorithmus verwendet ein anderes zahlentheoretisches Problem, die Berechnung des diskreten Logarithmus modulo einer »großen« Primzahl.

EIGamal soll uns hier nicht weiter beschäftigen. In Zusammenhang mit OpenSSL werden Sie mit Digital Signature Algorithm (DSA) eine Weiterentwicklung des Verfahrens kennen lernen.

OpenSSL

OpenSSL ist eine freie Implementierung der Protokolle Secure Socket Layer (SSL) und Transport Layer Security (TLS). Das Paket umfasst kryptografische Algorithmen zum Erzeugen von Schlüsseln und Zertifikaten sowie zur Verschlüsselung. Sämtliche Eigenschaften sind in einem einzigen Programm openssl implementiert. Das Programm wird hierzu i.d.R. mit nachfolgendem Kommando aufgerufen:

Der folgende Abschnitt beschreibt nur die wichtigsten Anwendungsszenarien mit den gebräuchlichen Optionen.

Erzeugen von Schüsseln

OpenSSl beherrscht die Erzeugung von RSA-, DH- und DSA-Schlüsseln.

RSA-Schlüssel

Erzeugung: Hierzu müssen Sie das Kommando genrsa bemühen. Wenn Sie das so einfach versuchen, wird der erzeugte Schlüssel (mit einer Schlüssellänge von 512 Bit) auf der Konsole ausgegeben. Allerdings sollten Sie es vielleicht doch nicht so einfach machen...

...denn nach obigen Schema erscheint der Schlüssel unverschlüsselt. D.h. jeder, der ihn in die Finger bekäme, könnte ihn auch verwenden. Besser also, Sie verschlüsseln den Schlüssel, indem Sie die Option -des3 verwenden. Sie werden nun nach einer Passphrase gefragt, die zur Chiffrierung mit dem TripleDES-Verfahren verwendet wird.

Des Weiteren gilt eine Schlüssellänge von 512 Bit nicht mehr als zeitgemäß. Zwar wird kaum eine Privatperson über ausreichend Rechenkapazität verfügen, um einen solchen Schlüssen anzugreifen, aber für Rechnerverbünde oder Großrechner liegt das wohl im Bereich des Möglichen. Geben Sie einfach einen höheren Wert am Ende der Optionsliste an und Sie brauchen sich über die Sicherheit fortan keine Gedanken mehr zu machen.

Mit der Option -out leiten wir die Ausgabe in eine Datei um, so dass sich letztlich folgender Aufruf ergibt:

OpenSSL arbeitet intern mit einem Zufallsgenerator, der bei jedem Aufruf initialisiert wird. Wie jeder Zufallsgenerator arbeitet auch dieser nicht wirklich zufällig sondern könnte unter Umständen identische Zahlenfolgen liefern. Misstrauische Naturen sollten daher selbst die Initialisierung in die Hand nehmen. Hierzu leiten Sie die Ausgabe aus /dev/random in eine Datei um:

Klimbern Sie heftig auf der Tastatur herum und wackeln Sie an der Maus. Wenn Sie nach einigen Sekunden mittels [Ctrl]-[C] die Generierung abbrechen, wird das Ergebnis wirklich zufällig sein. Die entstandene Datei können Sie mit der Option -rand random.bin bei der Schlüsselerzeugung verwenden.

Einen RSA-Schlüssel erkennen Sie am typischen Beginn:

Überprüfung des Schlüssels: Hierzu verwenden Sie das Kommando rsa mit der Option -check. Die Eingabedatei geben Sie mittels -in RSA-Datei an, -noout unterdrückt die Ausgabe des Schlüssels:

DSA-Schlüssel

Erzeugung: Ein Schlüssel nach dem Digital Signature Algorithm wird in zwei Schritten erzeugt. Zunächst benötigen wir die passenden Parameter. Da deren Erzeugung ein extrem rechenintensiver Vorgang ist und die Parameter oft mehrfach verwendet werden, werden sie separat erzeugt. Wiederum können Sie die Werte für die Schlüssellänge und die Ausgabedatei angeben:

Die Erzeugung des eigentlichen Schlüssels mit dem Kommando gendsa geht dann relativ flott vonstatten. Geben Sie mindestens den Namen der zuvor erzeugten Parameterdatei an:

Notorische Sicherheitsfanatiker können wieder das oben (RSA) erwähnte Verfahren der Zufallszahlengenerierung einsetzen.

GNU Privacy Guard

Einleitung

GnuPG ist eine freie Implementierung der OpenPGP-Spezifikation (RFC 2440) und vollständig kompatibel zu PGP 5.x (Privat Good Privacy) der Firma NAI. GnuPG ist ein Programm zum Verschlüsseln und Signieren digitaler Daten, wobei es sowohl asymmetrische (Public-Key) als auch symmetrische Verfahren unterstützt.

Das Verschlüsseln und Signieren erfolgt dennoch fast ausschließlich mittels Public-Key-Verfahren (Signieren sogar immer). Eine Nachricht verschlüsselt der Sender mit dem öffenlichen Schlüssel des Empfängers und einzig der Empfänger vermag die Nachricht mit Hilfe seines privaten Schlüssels in Klartext zu verwandeln. Das Signieren von Nachrichten verläuft genau anders herum. Der Unterzeichner verwendet hierzu seinen privaten Schlüssel und ein Empfänger kann mittels des öffenlichen Schlüssels des Absenders die Echtheit der Signatur überprüfen.

Vorbereitungen

Symmetrisches Verschlüsseln

Erzeugung und Schlüsseln

Textkonsole

GUI: gpa (GNU Privacy Assistant)