Blockverschlüsselung

aus Wikipedia, der freien Enzyklopädie
(Weitergeleitet von Blockchiffre)
Zur Navigation springen Zur Suche springen

Eine Blockverschlüsselung (auch Blockchiffre bzw. auf Englisch block cipher genannt) ist ein deterministisches Verschlüsselungsverfahren, bei dem ein Klartextblock, d. h. ein Klartextabschnitt fester Länge, auf einen Geheim- oder Schlüsseltextblock fester Länge abgebildet wird. Diese Abbildung wird dabei durch einen Schlüssel beeinflusst. Kennt man diesen, kann man aus dem Geheimtext wieder den Klartext berechnen. Ohne Kenntnis des Schlüssels ist dies hingegen praktisch unmöglich.

Im Gegensatz zu einer Stromchiffre kann eine Blockchiffre nur einen Block der gegebenen Länge verschlüsseln. Längere Texte werden auf ein Vielfaches der Blocklänge aufgefüllt und in Blöcke geteilt, und es wird ein Betriebsmodus gewählt, der festlegt, wie die Blockchiffre anzuwenden ist.

Blockchiffren werden auch als Bausteine zur Konstruktion weiterer kryptografischer Verfahren, z. B. kryptographischer Hashfunktionen, eingesetzt.

Anforderungen[Bearbeiten | Quelltext bearbeiten]

Bei der Verschlüsselung können zwei Ziele unterschieden werden: Durch Konfusion soll der Zusammenhang zwischen Geheim- und Klartext so komplex wie möglich gemacht werden. Diffusion soll die Information an einer Stelle des Klartextblocks über den gesamten Geheimtextblock verteilen; am Ende soll jedes Bit des Schlüsseltextblocks von jedem Bit des Klartextblocks abhängen. Wenn dieser geändert wird, soll sich jedes Schlüsseltextbit mit der Wahrscheinlichkeit 1/2 ändern, ohne erkennbares System. Es soll keine Möglichkeit geben, aus einem Schlüsseltext irgendwelche Informationen über den Klartext zu gewinnen.

Eine Blockchiffre soll vielen Angriffsszenarien widerstehen. Wenn etwa ein Angreifer beliebig viele mit dem gleichen Schlüssel erzeugte Paare von Klar- und Schlüsseltext vorliegen hat, soll es ihm dennoch nicht möglich sein, den Schlüssel zu ermitteln oder auf anderem Weg einen weiteren mit diesem Schlüssel erzeugten Schlüsseltext zu entziffern. Dies soll sogar dann noch gelten, wenn der Angreifer die Klartextblöcke frei wählen kann, also zu jedem von ihm konstruierten Block erfahren kann, welches der unter dem gegebenen Schlüssel zugehörige Schlüsseltextblock ist. Auch dann, wenn der Angreifer wahlweise einen Klar- oder Schlüsseltextblock frei wählen kann, soll es ihm unmöglich sein, den Schlüssel herauszufinden.

Geschichte[Bearbeiten | Quelltext bearbeiten]

Lucifer gilt als die erste zivil nutzbare Blockchiffre, sie wurde im Jahr 1971 von IBM auf der Grundlage von Horst Feistels kryptographischen Arbeiten entwickelt. Eine revidierte Version von Lucifer wurde vom National Bureau of Standards (NBS) der USA (woraus 1988 das National Institute of Standards and Technology, NIST hervorging) übernommen und zum DES (Data Encryption Standard) erklärt, nachdem Änderungen vom NBS selbst und vom Geheimdienst NSA am Algorithmus vorgenommen worden waren. Der DES wurde 1976 der Öffentlichkeit vorgestellt und fand eine weit verbreitete Anwendung.

Bereits Ende der 90er Jahre konnte DES aufgrund seiner geringen Schlüssellänge von 56 Bit durch Brute-Force-Angriffe gebrochen werden. Er wurde deshalb im Jahr 2001 nach einer fünfjährigen Ausschreibungsphase durch den AES (Advanced Encryption Standard) ersetzt. Der Auswahlprozess des AES wird weltweit von vielen Kryptographen wegen seiner offenen Gestaltung als vorbildlich angesehen. Der Algorithmus des AES war von Joan Daemen und Vincent Rijmen unter dem Namen Rijndael entwickelt worden.

Mathematische Beschreibung[Bearbeiten | Quelltext bearbeiten]

Eine Blockchiffre ist eine Funktion

,

die einen Klartextblock auf einen Schlüsseltextblock abbildet, mit dem Schlüssel als Parameter. Für jeden möglichen Schlüssel muss die Verschlüsselungsfunktion injektiv sein, da genau dann eine Entschlüsselungsfunktion existiert, die zu jedem Schlüsseltext wieder den Klartext berechnet:

Dies ist gleichbedeutend zu der Aussage, dass die Entschlüsselungsfunktion linksinvers zur Verschlüsselungsfunktion ist.

Meist ist , und die Ver- und Entschlüsselungsfunktionen sind dann für jeden Schlüssel aus S bijektiv. Heute verwendet man außerdem meist Bitblockchiffren, die auf Blöcken mit b Bit arbeiten: .

Eine bijektive Abbildung von auf ist eine Permutation von Elementen. Es gibt folglich eine extrem große Zahl () verschiedener Abbildungen (siehe Fakultät).

Durch den Schlüssel einer Blockchiffre wird von den möglichen bijektiven Abbildungen genau eine ausgewählt. Da die Schlüssellänge typischer Blockchiffren weit geringer als Bits ist, wird durch die Gesamtheit aller Schlüssel nur ein kleiner Teil aller möglichen Abbildungen erfasst. Bereits bei einer Blockgröße von nur 8 Bit wäre ein 1684 Bit langer Schlüssel nötig, um alle Permutationen zu realisieren.

Entwurfsprinzipien[Bearbeiten | Quelltext bearbeiten]

Produktchiffre[Bearbeiten | Quelltext bearbeiten]

Alle modernen Blockchiffren wie AES oder DES sind als iterierte Blockchiffren (Produktchiffren) konzipiert. Das bedeutet, dass die Verarbeitung der Eingabe in mehreren aufeinanderfolgenden Runden erfolgt, die gleich aufgebaut sind (Rundenfunktion).

Die Schwierigkeit, eine Blockchiffre zu entwickeln, liegt darin, eine umkehrbare Transformation zu finden, welche den kryptographischen Anforderungen (Konfusion und Diffusion) gerecht wird, und mit wenig Aufwand implementierbar ist. Darum versucht man meist nicht, eine komplexe Funktion zu finden, die den Text in einem einzigen Schritt verschlüsselt, sondern beschränkt sich auf eine relativ einfach aufgebaute Rundenfunktion. Erst deren mehrfache Anwendung ergibt eine ausreichend komplexe Verschlüsselungsfunktion.

Da die aufeinanderfolgenden Runden nicht exakt gleich arbeiten sollten (siehe Meet-in-the-middle-Angriff), berechnet man üblicherweise aus dem Benutzerschlüssel mehrere verschiedene Rundenschlüssel, und in jeder Runde wird ein anderer davon mit dem Datenblock verknüpft, entweder als zweite Eingabe in die Rundenfunktion:

,

oder zwischen den Anwendungen der Rundenfunktion, z. B. durch bitweise XOR-Verknüpfung:

mit . Dabei ist die Rundenfunktion, der Klartext, der Benutzerschlüssel und die Schlüsseleinteilungsfunktion.

Feistelchiffre[Bearbeiten | Quelltext bearbeiten]

Allgemeine Struktur eines Feistelchiffre

Feistelchiffre, auch als Feistelnetzwerk bezeichnet, ist eine allgemeine Struktur, mit der Blockchiffren realisiert werden können. Horst Feistel, der im Jahr 1970 bei IBM an der Chiffre Lucifer arbeitete, gilt als Erfinder. Ein Klartextblock wird in zwei Teile geteilt und in mehreren Runden verarbeitet. In jeder Runde wird ein Blockteil zusammen mit einem Rundenschlüssel in die Rundenfunktion eingegeben und deren Ausgabe mit dem anderen Blockteil verknüpft. Feistelnetzwerke ermöglichen eine Entschlüsselung, ohne dass die Umkehrung der Rundenfunktion berechnet werden muss. Viele Chiffren, zum Beispiel DES, Twofish und Blowfish, sind als Feistelnetzwerke aufgebaut.

Lai-Massey-Chiffre[Bearbeiten | Quelltext bearbeiten]

Ähnlich wie beim Feistelnetzwerk nutzt man eine Rundenfunktion auf eine Weise, dass deren Umkehrung zum Entschlüsseln nicht berechnet werden muss. Der Datenblock wird in zwei Hälften geteilt. In jeder Runde verknüpft man beide Hälften miteinander, gibt das Ergebnis in die Rundenfunktion ein und verknüpft dann deren Ausgabe mit jeder der Blockhälften:

.

Das geschieht so, dass ist und man somit bei Wiederholung der Operation wieder die gleiche Eingabe in erhält. So ist es leicht, die Runde rückgängig zu machen. Am einfachsten geht das, indem man für und jeweils das bitweise XOR einsetzt. Eine weitere Möglichkeit ist, für die Subtraktion zu verwenden, und für beim Verschlüsseln die Addition und beim Entschlüsseln die Subtraktion (oder umgekehrt), jeweils modulo , wobei die Wortbreite in Bit ist.

Damit sich die aufeinanderfolgenden Runden beim Verschlüsseln nicht gegenseitig aufheben, muss der Datenblock zwischen den Runden mit einer weiteren Operation modifiziert werden. Dazu werden häufig die Bits einer Blockhälfte permutiert (z. B. durch Bitrotation).

Beispiele für Lai-Massey-Chiffren sind IDEA und IDEA NXT

Substitutions-Permutations-Netzwerk[Bearbeiten | Quelltext bearbeiten]

Ein Substitutions-Permutations-Netzwerk (SPN) ist eine Abfolge von Runden gleichen Aufbaus (Produktchiffre). In jeder Runde wird zuerst der Rundenschlüssel mit dem Datenblock verknüpft. Dann wird eine n×n S-Box auf den Datenblock angewendet, der dazu in Teile von n Bit geteilt wird, die für sich substituiert werden. Danach werden die Bits des Datenblocks permutiert, so dass die Ausgabe einer S-Box sich in der nächsten Runde auf mehrere S-Boxen und schließlich über den ganzen Datenblock verteilt. Oft wird diese Permutation durch eine komplexere Operation ersetzt, wie z. B. bei Serpent und AES, um die Diffusion zu beschleunigen.

Kryptographische Betriebsmodi[Bearbeiten | Quelltext bearbeiten]

Ein kryptographischer Betriebsmodus legt fest, wie sich die Verschlüsselung mehrerer Klartextblöcke vollzieht, indem er definiert, in welcher Art der Verschlüsselungsalgorithmus auf den Datenstrom angewandt wird.[1] Je nach den Anforderungen der Anwendung variiert die Fehleranfälligkeit und Sicherheit. Der internationale Standard ISO 10116 definiert für blockorientierte Verschlüsselungsalgorithmen vier verschiedenen Betriebsarten: Electronic Code Book (ECB), Cipher Block Chaining (CBC), Cipher Feedback (CFB) und Output Feedback (OFB).

Einige neuere Blockverschlüsselungen, wie z. B. Threefish, nehmen eine zusätzliche Eingabe, den sogenannten Tweak, entgegen, der die Abbildung des Klartextes auf den Schlüsseltext beeinflusst. Auf englisch nennt man sie tweakable block ciphers; eine deutsche Übersetzung hat sich bisher nicht verbreitet. Bei Änderung des Tweak ändert sich die Permutation der Blockwerte, ebenso wie bei Änderung des Schlüssels. Während aber letztere oft aufwändig ist, weil viele Chiffren eine komplexe Schlüsseleinteilung durchführen (ein extremes Beispiel ist Blowfish), ist die Änderung des Tweak einfach und verursacht nur minimalen Aufwand.

Dadurch werden weitere Betriebsmodi möglich. So kann man ECB derart modifizieren, dass jeder Block mit einem anderen Tweak (aber gleichem Schlüssel) verschlüsselt wird. Der Tweak muss nicht geheim gehalten werden, und man kann dafür z. B. einfach die laufende Nummer des Blocks verwenden. Dadurch werden gleiche Klartextblöcke nicht mehr auf gleiche Schlüsseltextblöcke abgebildet.

Bekannte Blockchiffren[Bearbeiten | Quelltext bearbeiten]

Einige bekannte Blockchiffren sind:

Camellia RC2 DES 3DES AES IDEA
FEAL RC5 RC6 Serpent Blowfish Twofish
Skipjack CAST MARS TEA XTEA SEED

Weblinks[Bearbeiten | Quelltext bearbeiten]

Einzelnachweise[Bearbeiten | Quelltext bearbeiten]

  1. Bruce Schneier: Applied Cryptography. Protocols, Algorithms and Source Code in C. 2. Auflage. John Wiley & Sons, New York 1996, ISBN 0-471-11709-9, S. 206–208.