© Liashko/Shutterstock.com
Teil 1: Wie sicher sind symmetrische Verfahren noch?

Kryptografie im NSA-Zeitalter


Die NSA kann manche Verschlüsselungen brechen und nimmt Einfluss auf die Entwicklung von Kryptografiestandards. Wem, oder besser: welchen Verfahren ist noch zu trauen? Und wie setzt man sie sicher ein?

Seit der Veröffentlichung der von Edward Snowden geleakten NSA-Daten ist die Verunsicherung groß: Wo hat die NSA überall die Finger im Spiel? Was ist noch sicher? Welchen Protokollen kann man noch vertrauen? Ich werde versuchen, diese Fragen in einer kleinen Artikelserie zu beantworten. Los geht es mit symmetrischer Verschlüsselung, bei der zum Ver- und Entschlüsseln der gleiche Schlüssel verwendet wird (Abb. 1). Ein symmetrisches Verschlüsselungssystem können Sie sich als undurchsichtigen Kasten mit einem Schloss vorstellen, für das es zwei gleiche Schlüssel gibt. Als erstes symmetrisches System stelle ich ein Verfahren vor, dass Sie keinesfalls mehr verwenden sollten: DES.

eilers_krypto_1.tif_fmt1.jpgAbb. 1: Symmetrische Verschlüsselung

DES, der Data Encryption Standard

DES ist alt, aus IT-Sicht sogar uralt: Der Algorithmus des DES-Verfahrens wurde erstmals am 15. Januar 1977 in „Specification for the Data Encryption Standard; Federal Information Processing Standards Publication 46“ (FIPS PUB 46) veröffentlicht. Die erste Version ist leider nicht mehr online verfügbar, sondern nur aktualisierte Fassungen: FIPS PUB 46-2 [1] und FIPS PUB 46-3 [3].

Das Alter ist aber nicht das Problem von DES. Das in der nächsten Folge vorgestellte asymmetrische RSA-Verfahren ist nur ein Jahr jünger und, einen ausreichend langen Schlüssel vorausgesetzt, immer noch sicher. Das Problem von DES ist der Schlüssel, genauer: seine Länge (oder aus heutiger Sicht: Kürze), die nicht geändert werden kann.

DES verwendet einen 56 Bit langen Schlüssel und verschlüsselt Blöcke von 64 Bit Länge. Der Schlüssel wird um acht Paritätsbits auf 64 Bit erweitert, die Paritätsbits werden für den Algorithmus jedoch nicht verwendet. Der DES-Algorithmus (Abb. 2) besteht aus:

  • einer kryptographisch bedeutungslosen Eingangspermutation IP (Initial Permutation), die unter anderem den Klartextblock in die beiden 32-Bit-Blöcke L0 und R0 zerlegt

  • 16 Iterationsrunden, in denen die eigentliche Verschlüsselung erfolgt

  • einer zur Eingangspermutation inversen Ausgangspermutation IP-1, vor deren Ausführung die Ergebnisse der 16. Iterationsrunde, L16 und R16, nochmals vertauscht werden

Aus dem Schlüssel werden die 16 Teilschlüssel K1 bis K16 erzeugt, einer für jede Iterationsrunde.

eilers_krypto_2.tif_fmt1.jpgAbb. 2: Der DES-Algorithmus im Überblick

Die Iterationsrunden

Die Iterationsrunden entsprechen den Runden eines so genannten Feistel-Netzwerks. Die für die Entschlüsselung notwendige Vertauschung erfolgt nach der 16. Iterationsrunde, der DES-Algorithmus kann also unverändert sowohl zur Ver- als auch Entschlüsselung genutzt werden. Die zum Entschlüsseln notwendige Umkehrung der Reihenfolge der Iterationen erfolgt durch die Umkehrung der Reihenfolge der Teilschlüssel Ki.

Jede Iterationsrunde i erhält als Eingabe die beiden Blöcke Li-1 und Ri-1. Die Verschlüsselungsfunktion f verwendet den geheimen Schlüssel Ki, um aus dem gegebenen Block Ri-1 einen (Geheimtext-)block f(Ri-1,Ki) zu erzeugen. Die eigentliche Verschlüsselung erfolgt dann, indem die beiden Halbblöcke vertauscht und Li-1 mit f(Ri-1,Ki) XOR-verknüpft wird:

Li := Ri-1

Ri := Li-1 f(Ri-1,Ki)

Grafisch lässt sich das Ganze wie in der linken Hälfte von Abbildung 3 darstellen. Für die Entschlüsselung muss dieser Prozess umgekehrt werden. Das Ergebnis von Runde i ist wie oben zu sehen:

Li := Ri-1

Ri := Li-1 f(Ri-1,Ki)

Zum Entschlüsseln werden Li und Ri getauscht, außerdem wird der Rundenindex i rückwärts statt vorwärts gezählt. Führt man die Runde erneut durch, so ergibt sich:

Li =: Ri-1

Li-1⊕ f(Ri-1,Ki) ⊕ f(Li,Ki) =

Li-1⊕ f(Li,Ki) ⊕ f(Li,Ki) =: Li-1

Grafisch lässt sich das wie in der rechten Hälfte von Abbildung 3 darstellen.

eilers_krypto_3.tif_fmt1.jpgAbb. 3: Ver- und Entschlüsselung in den Iterationsrunden des DES-Algorithmus

Die Verschlüsselungsfunktion

Die Verschlüsselungsfunktion sehen Sie in Abbildung 4. Der 32-Bit-Block Ri-1 wird durch die Expansionspermutation E auf 48 Bit erweitert. Während eine Permutation einzelne Eingabewerte vertauscht, ohne ihre Werte oder Gesamtzahl zu verändern, kommen bei einer Expansionspermutation manche Eingabewerte mehrfach in der Ausgabe vor.

Danach wird der 48 Bit lange Teilschlüssel Ki bitweise modulo 2 hinzuaddiert.

Die Summe wird in acht 6-Bit-Blöcke aufgeteilt, mit denen jeweils ein 4-Bit-Wert aus einer der Substitutionsboxen S1 bis S8 (S-Boxen, substitution box) ausgewählt wird. Diese Substitutionsboxen ordnen Werten von 6-Bit-Blöcken Werte von 4-Bit-Blöcken zu und sorgen so für Nichtlinearität.

Die sich ergebenden acht 4-Bit-Werte werden zu einem 32-Bit-Wert zusammengefasst. Auf das Ergebnis wird die Permutation P angewendet, die dann das Ergebnis liefert. P mischt die Ausgaben der acht Substitutionsboxen, damit in der nächsten Runde die Ausgabe jeder Substitutionsbox in mehrere Substitutionsboxen eingeht.

eilers_krypto_4.tif_fmt1.jpgAbb. 4: Die Verschlüsselungsfunktion des DES-Algorithmus

Die Teilschlüsselerzeugung

Die Erzeugung der Teilschlüssel sehen Sie in Abbildung 5. Eine permutierende Auswahlfunktion PC-1 (PC = permuted choice) wählt aus dem 64-Bit-Schlüssel 56 Bits aus und teilt sie auf die beiden 28-Bit-Blöcke C0 und D0 auf. Ci und Di (i = 1, ..., 16) werden erzeugt, indem die Bits in Ci-1 und Di-1 abhängig von i um ein oder zwei Stellen nach links rotiert werden (zyklischer Linksshift LSi). Die Teilschlüssel Ki werden dann gebildet, indem Ci und Di verbunden und daraus durch die permutierende Auswahlfunktion PC-2 48 Bits ausgewählt werden.

eilers_krypto_5.tif_fmt1.jpgAbb. 5: Die Erzeugung der Teilschlüssel des DES-Algorithmus

Die S-Boxen

Jede S-Box ist eine Tabelle mit vier Zeilen und sechzehn Spalten. Wenn die Eingabe aus den 6 Bits b1, ..., b6 besteht, bestimmt die aus b1 und b2 gebildete Zahl (2 Bits = 4 Werte) die Tabellenzeile, die aus b3 bis b6 gebildete Zahl die Tabellenspalte. Die Zahl in der entsprechenden Zeile...

headline from sands settings