Blockchiffre - Block cipher

In der Kryptographie , eine Blockchiffre ist ein deterministischer Algorithmus auf feste Länge Gruppen von Betrieb Bits , genannt Blöcken . Sie sind spezifizierte elementare Bestandteile beim Entwurf vieler kryptographischer Protokolle und werden häufig verwendet, um die Verschlüsselung großer Datenmengen, einschließlich Datenaustauschprotokollen , zu implementieren . Es verwendet Blöcke als unveränderliche Transformation.

Auch eine sichere Blockchiffre ist für die Verschlüsselung jeweils nur eines einzigen Datenblocks mit einem festen Schlüssel geeignet. Um die Sicherheitsziele Vertraulichkeit und Authentizität zu erreichen , wurde eine Vielzahl von Betriebsarten entwickelt , die eine wiederholte Verwendung auf sichere Weise ermöglichen . Blockchiffren können jedoch auch als Bausteine ​​in anderen kryptografischen Protokollen wie universellen Hash-Funktionen und Pseudozufallszahlengeneratoren vorkommen.

Definition

Eine Blockchiffre besteht aus zwei gepaarten Algorithmen , einer für die Verschlüsselung, E , und die andere für die Entschlüsselung, D . Beide Algorithmen akzeptieren zwei Eingaben: einen Eingabeblock der Größe n Bits und einen Schlüssel der Größe k Bits; und beide ergeben einen n- Bit-Ausgabeblock. Der Entschlüsselungsalgorithmus D ist als die Umkehrfunktion der Verschlüsselung definiert, dh D = E ^–1 . Formal wird eine Blockchiffre durch eine Verschlüsselungsfunktion spezifiziert

${\displaystyle E_{K}(P):=E(K,P):\{0,1\}^{k}\times \{0,1\}^{n}\rightarrow \{0,1 \}^{n},}$

die als Eingabe einen Schlüssel K mit der Bitlänge k (als Schlüsselgröße bezeichnet ) und eine Bitfolge P mit der Länge n (als Blockgröße bezeichnet ) annimmt und eine Zeichenfolge C mit n Bits zurückgibt . P heißt Klartext und C heißt Geheimtext . Für jedes K muss die Funktion E _K ( P ) eine invertierbare Abbildung auf {0,1} ^{n sein} . Die Umkehrung von E ist definiert als Funktion

${\displaystyle E_{K}^{-1}(C):=D_{K}(C)=D(K,C):\{0,1\}^{k}\times \{0,1 \}^{n}\rightarrow \{0,1\}^{n},}$

einen Schlüssel K und einen Geheimtext C nehmen , um einen Klartextwert P zurückzugeben , so dass

${\displaystyle \forall K:D_{K}(E_{K}(P))=P.}$

Beispielsweise könnte ein Blockchiffrier-Verschlüsselungsalgorithmus einen 128-Bit-Klartextblock als Eingabe verwenden und einen entsprechenden 128-Bit-Chiffriertextblock ausgeben. Die genaue Transformation wird über einen zweiten Eingang gesteuert – den geheimen Schlüssel. Die Entschlüsselung ist ähnlich: Der Entschlüsselungsalgorithmus nimmt in diesem Beispiel einen 128-Bit-Chiffretextblock zusammen mit dem geheimen Schlüssel und liefert den ursprünglichen 128-Bit-Klartextblock.

Für jeden Schlüssel K ist E _K eine Permutation (eine bijektive Abbildung) über den Satz von Eingabeblöcken. Jeder Schlüssel wählt eine Permutation aus der Menge möglicher Permutationen aus. ${\displaystyle (2^{n})!}$

Geschichte

Das moderne Design von Blockchiffren basiert auf dem Konzept einer iterierten Produktchiffre . In seiner wegweisenden Veröffentlichung von 1949, Communication Theory of Secrecy Systems , analysierte Claude Shannon Produktchiffren und schlug sie als Mittel zur effektiven Verbesserung der Sicherheit vor, indem einfache Operationen wie Substitutionen und Permutationen kombiniert wurden . Iterierte Produktchiffren führen die Verschlüsselung in mehreren Runden durch, von denen jede einen anderen Unterschlüssel verwendet, der vom ursprünglichen Schlüssel abgeleitet wird. Eine weit verbreitete Implementierung solcher Chiffren, die nach Horst Feistel als Feistel-Netzwerk bezeichnet wird , ist insbesondere in der DES- Chiffre implementiert . Viele andere Realisierungen von Blockchiffren, wie die AES , werden als Substitutions-Permutations-Netzwerke klassifiziert .

Die Wurzel aller kryptografischen Blockformate, die in den Standards des Payment Card Industry Data Security Standard (PCI DSS) und des American National Standards Institute (ANSI) verwendet werden, liegt im Atalla Key Block (AKB), der eine Schlüsselinnovation der Atalla Box war erstes Hardware-Sicherheitsmodul (HSM). Es wurde 1972 von Mohamed M. Atalla , Gründer der Atalla Corporation (heute Utimaco Atalla ) entwickelt und 1973 veröffentlicht. Der AKB war ein Schlüsselblock, der benötigt wird, um symmetrische Schlüssel oder PINs sicher mit anderen Akteuren der Bankenbranche auszutauschen . Dieser sichere Austausch erfolgt im AKB-Format. Die Atalla Box schützte seit 1998 über 90 % aller in Betrieb befindlichen Geldautomatennetze , und Atalla-Produkte sichern auch 2014 noch immer den Großteil der weltweiten Geldautomatentransaktionen.

Die Veröffentlichung der DES-Chiffre durch das United States National Bureau of Standards (später das US National Institute of Standards and Technology , NIST) im Jahr 1977 war grundlegend für das öffentliche Verständnis des modernen Blockchiffrendesigns. Es beeinflusste auch die akademische Entwicklung kryptanalytischer Angriffe . Sowohl die differentielle als auch die lineare Kryptoanalyse sind aus Studien zum DES-Design hervorgegangen. Seit 2016 gibt es eine Palette von Angriffstechniken, gegen die eine Blockchiffre sicher sein muss, zusätzlich zur Robustheit gegen Brute-Force-Angriffe .

Entwurf

Iterierte Blockchiffren

Die meisten Blockchiffre - Algorithmen werden wie folgt klassifiziert iterierte Blockchiffren , die bedeuten , dass sie feste Größe Blöcke von Transformationsklartext in gleich große Blöcke von verschlüsseltem Text über die wiederholte Anwendung einer invertierbaren Transformation bekannt als die Rundenfunktion , wobei jede Iteration als A bezeichneten runde .

Üblicherweise nimmt die Rundenfunktion R verschiedene Rundenschlüssel K _i als zweite Eingabe, die vom Originalschlüssel abgeleitet werden:

${\displaystyle M_{i}=R_{K_{i}}(M_{i-1})}$

Wo ist der Klartext und der Geheimtext, wobei r die Anzahl der Runden ist. ${\displaystyle M_{0}}$${\displaystyle M_{r}}$

Häufig kommt zusätzlich ein Key-Bleaching zum Einsatz. Am Anfang und Ende werden die Daten mit Schlüsselmaterial modifiziert (oft mit XOR , aber auch einfache arithmetische Operationen wie Addieren und Subtrahieren werden verwendet):

${\displaystyle M_{0}=M\oplus K_{0}}$

${\displaystyle M_{i}=R_{K_{i}}(M_{i-1})\;;\;i=1\dots r}$

${\displaystyle C=M_{r}\oplus K_{r+1}}$

Bei einem der standardmäßigen iterierten Blockchiffre-Entwurfsschemata ist es ziemlich einfach, eine kryptographisch sichere Blockchiffre zu konstruieren, indem einfach eine große Anzahl von Runden verwendet wird. Dadurch wird die Verschlüsselung jedoch ineffizient. Somit ist Effizienz das wichtigste zusätzliche Designkriterium für professionelle Chiffren. Darüber hinaus ist eine gute Blockchiffre dazu ausgelegt, Seitenkanalangriffe zu vermeiden, wie etwa Verzweigungsvorhersage und eingabeabhängige Speicherzugriffe, die geheime Daten über den Cache-Zustand oder die Ausführungszeit preisgeben könnten. Darüber hinaus sollte die Verschlüsselung für kleine Hardware- und Softwareimplementierungen prägnant sein. Schließlich sollte die Chiffre leicht kryptanalysierbar sein, so dass gezeigt werden kann, auf wie viele Runden die Chiffre reduziert werden muss, damit die bestehenden kryptografischen Angriffe funktionieren – und dass umgekehrt gezeigt werden kann, dass die Anzahl der tatsächlichen Runden groß genug ist, um sich davor zu schützen.

Substitution-Permutationsnetzwerke

Eine Skizze eines Substitutions-Permutations-Netzwerks mit 3 Runden, das einen Klartextblock von 16 Bit in einen Geheimtextblock von 16 Bit verschlüsselt. Die S-Boxen sind die S _i , die P-Boxen sind die gleichen P und die runden Schlüssel sind die K _i .

Ein wichtiger Typ einer iterierten Blockchiffre, bekannt als Substitutions-Permutationsnetzwerk (SPN), nimmt einen Block des Klartexts und den Schlüssel als Eingaben und wendet mehrere abwechselnde Runden an, die aus einer Substitutionsstufe gefolgt von einer Permutationsstufe bestehen – um jeden Block von . zu erzeugen Chiffretext-Ausgabe. Die nichtlineare Substitutionsstufe mischt die Schlüsselbits mit denen des Klartextes, wodurch Shannons Verwirrung entsteht . Die lineare Permutationsstufe baut dann Redundanzen ab und erzeugt eine Diffusion .

Eine Substitutionsbox (S-Box) ersetzt einen kleinen Block von Eingangsbits durch einen anderen Block von Ausgangsbits. Diese Ersetzung muss eins zu eins sein , um die Invertibilität (daher die Entschlüsselung) zu gewährleisten. Eine sichere S-Box hat die Eigenschaft, dass die Änderung eines Eingangsbits im Durchschnitt etwa die Hälfte der Ausgangsbits ändert, was den sogenannten Lawineneffekt zeigt – dh sie hat die Eigenschaft, dass jedes Ausgangsbit von jedem Eingangsbit abhängt.

Eine Permutationsbox (P-Box) ist eine Permutation aller Bits: Sie nimmt die Ausgaben aller S-Boxen einer Runde, permutiert die Bits und speist sie in die S-Boxen der nächsten Runde ein. Eine gute P-Box hat die Eigenschaft, dass die Ausgangsbits einer beliebigen S-Box auf möglichst viele S-Box-Eingänge verteilt werden.

Bei jeder Runde wird der Rundenschlüssel (erhalten aus dem Schlüssel mit einigen einfachen Operationen, zum Beispiel unter Verwendung von S-Boxen und P-Boxen) unter Verwendung einer Gruppenoperation, typischerweise XOR , kombiniert .

Die Entschlüsselung erfolgt durch einfaches Umkehren des Prozesses (unter Verwendung der Umkehrungen der S-Boxen und P-Boxen und Anwenden der Rundenschlüssel in umgekehrter Reihenfolge).

Feistel-Chiffren

Viele Blockchiffren wie DES und Blowfish verwenden Strukturen, die als Feistel-Chiffren bekannt sind

Bei einer Feistel-Chiffre wird der zu verschlüsselnde Klartextblock in zwei gleich große Hälften geteilt. Die Rundungsfunktion wird mit einem Unterschlüssel auf eine Hälfte angewendet, und dann wird die Ausgabe mit der anderen Hälfte XOR-verknüpft. Anschließend werden die beiden Hälften getauscht.

Seien die Rundenfunktion bzw. die Unterschlüssel für die Runden . ${\displaystyle {\rm {F}}}$${\displaystyle K_{0},K_{1},\ldots ,K_{n}}$${\displaystyle 0,1,\ldots,n}$

Dann ist die Grundoperation wie folgt:

Teilen Sie den Klartextblock in zwei gleiche Teile ( , ) ${\displaystyle L_{0}}$${\displaystyle R_{0}}$

Berechnen Sie für jede Runde${\displaystyle i=0,1,\dots,n}$

${\displaystyle L_{i+1}=R_{i}\,}$

${\displaystyle R_{i+1}=L_{i}\oplus {\rm {F}}(R_{i},K_{i})}$.

Dann ist der Geheimtext . ${\displaystyle (R_{n+1},L_{n+1})}$

Die Entschlüsselung eines Geheimtextes erfolgt durch Berechnung von${\displaystyle (R_{n+1},L_{n+1})}$${\displaystyle i=n,n-1,\ldots,0}$

${\displaystyle R_{i}=L_{i+1}\,}$

${\displaystyle L_{i}=R_{i+1}\oplus {\rm {F}}(L_{i+1},K_{i})}$.

Dann ist wieder der Klartext. ${\displaystyle (L_{0},R_{0})}$

Ein Vorteil des Feistel-Modells gegenüber einem Substitutions-Permutations-Netzwerk besteht darin, dass die Rundenfunktion nicht invertierbar sein muss. ${\displaystyle {\rm {F}}}$

Lai-Massey-Chiffren

Das Lai-Massey-Schema. Die archetypische Chiffre, die es verwendet, ist IDEA .

Das Lai-Massey-Schema bietet ähnliche Sicherheitseigenschaften wie die Feistel-Struktur . Es hat auch den Vorteil, dass die Rundungsfunktion nicht invertierbar sein muss. Eine weitere Ähnlichkeit besteht darin, dass auch der Eingabeblock in zwei gleiche Teile geteilt wird. Die Rundungsfunktion wird jedoch auf die Differenz zwischen den beiden angewendet und das Ergebnis wird dann zu beiden Halbblöcken addiert. ${\displaystyle \mathrm{F}}$

Seien die Rundenfunktion und eine Halbrundenfunktion bzw. die Unterschlüssel für die Runden . ${\displaystyle \mathrm{F}}$${\displaystyle \mathrm{H}}$${\displaystyle K_{0},K_{1},\ldots ,K_{n}}$${\displaystyle 0,1,\ldots,n}$

Dann ist die Grundoperation wie folgt:

Teilen Sie den Klartextblock in zwei gleiche Teile ( , ) ${\displaystyle L_{0}}$${\displaystyle R_{0}}$

Berechnen Sie für jede Runde${\displaystyle i=0,1,\dots,n}$

wo und${\displaystyle T_{i}=\mathrm {F} (L_{i}'-R_{i}',K_{i})}$${\displaystyle (L_{0}',R_{0}')=\mathrm {H} (L_{0},R_{0})}$

Dann ist der Geheimtext . ${\displaystyle (L_{n+1},R_{n+1})=(L_{n+1}',R_{n+1}')}$

Die Entschlüsselung eines Geheimtextes erfolgt durch Berechnung von${\displaystyle (L_{n+1},R_{n+1})}$${\displaystyle i=n,n-1,\ldots,0}$

${\displaystyle (L_{i}',R_{i}')=\mathrm {H} ^{-1}(L_{i+1}'-T_{i},R_{i+1}'-T_ {ich})}$

wo und${\displaystyle T_{i}=\mathrm {F} (L_{i+1}'-R_{i+1}',K_{i})}$${\displaystyle (L_{n+1}',R_{n+1}')=\mathrm {H} ^{-1}(L_{n+1},R_{n+1})}$

Dann ist wieder der Klartext. ${\displaystyle (L_{0},R_{0})=(L_{0}',R_{0}')}$

Betrieb

ARX ​​(Addieren–Rotieren–XOR)

Viele moderne Blockchiffren und Hashes sind ARX- Algorithmen – ihre Rundungsfunktion umfasst nur drei Operationen: (A) modulare Addition, (R) Rotation mit festen Rotationsbeträgen und (X) XOR . Beispiele sind ChaCha20 , Speck , XXTEA und BLAKE . Viele Autoren zeichnen ein ARX-Netzwerk, eine Art Datenflussdiagramm , um eine solche Rundenfunktion zu veranschaulichen.

Diese ARX-Operationen sind beliebt, weil sie relativ schnell und kostengünstig in Hardware und Software sind, ihre Implementierung extrem einfach gestaltet werden kann und auch weil sie in konstanter Zeit ausgeführt werden und daher immun gegen Timing-Angriffe sind . Die Rotations-Kryptanalyse- Technik versucht, solche runden Funktionen anzugreifen.

Andere Operationen

Andere Operationen, die häufig in Blockchiffren verwendet werden, umfassen datenabhängige Rotationen wie in RC5 und RC6 , eine als Nachschlagetabelle implementierte Substitutionsbox wie in Data Encryption Standard und Advanced Encryption Standard , eine Permutationsbox und Multiplikation wie in IDEA .

Betriebsarten

Unsichere Verschlüsselung eines Bildes als Ergebnis der Codierung im elektronischen Codebuch (ECB)-Modus.

Eine Blockchiffre selbst erlaubt die Verschlüsselung nur eines einzelnen Datenblocks der Blocklänge der Chiffre. Für eine Nachricht mit variabler Länge müssen die Daten zuerst in separate Chiffrierblöcke partitioniert werden. Im einfachsten Fall, dem sogenannten Electronic Codebook (ECB)-Modus, wird eine Nachricht zunächst in einzelne Blöcke der Blockgröße der Chiffre aufgeteilt (evtl. den letzten Block mit Padding- Bits erweitern), und dann wird jeder Block unabhängig verschlüsselt und entschlüsselt. Ein solches naives Verfahren ist jedoch im Allgemeinen unsicher, da gleiche Klartextblöcke immer gleiche Geheimtextblöcke (für denselben Schlüssel) erzeugen, sodass Muster in der Klartextnachricht in der Geheimtextausgabe offensichtlich werden.

Um diese Einschränkung zu überwinden, wurden mehrere sogenannte Blockchiffre-Betriebsmodi entwickelt und in nationalen Empfehlungen wie NIST 800-38A und BSI TR-02102 und internationalen Standards wie ISO/IEC 10116 spezifiziert . Das allgemeine Konzept besteht darin, eine Randomisierung der Klartextdaten basierend auf einem zusätzlichen Eingabewert, häufig als Initialisierungsvektor bezeichnet , zu verwenden, um eine so genannte probabilistische Verschlüsselung zu erzeugen . Im populären Cipher Block Chaining (CBC)-Modus muss für eine sichere Verschlüsselung der zusammen mit der Klartextnachricht übergebene Initialisierungsvektor ein zufälliger oder pseudozufälliger Wert sein, der in einer Exklusiv-Oder- Weise zum ersten Klartextblock hinzugefügt wird es wird verschlüsselt. Der resultierende Chiffretextblock wird dann als neuer Initialisierungsvektor für den nächsten Klartextblock verwendet. Im Cipher-Feedback- (CFB)-Modus, der eine selbstsynchronisierende Stromchiffre emuliert , wird der Initialisierungsvektor zuerst verschlüsselt und dann dem Klartextblock hinzugefügt. Der Output-Feedback- (OFB)-Modus verschlüsselt wiederholt den Initialisierungsvektor, um einen Schlüsselstrom für die Emulation einer synchronen Stromchiffre zu erzeugen . Der neuere Zähler- (CTR)-Modus erzeugt in ähnlicher Weise einen Schlüsselstrom, hat jedoch den Vorteil, dass nur eindeutige und keine (Pseudo-)Zufallswerte als Initialisierungsvektoren benötigt werden; die benötigte Zufälligkeit wird intern abgeleitet, indem der Initialisierungsvektor als Blockzähler verwendet wird und dieser Zähler für jeden Block verschlüsselt wird.

Aus sicherheitstheoretischer Sicht müssen Betriebsarten eine sogenannte semantische Sicherheit bieten . Informell bedeutet dies, dass man bei einem bestimmten Geheimtext unter einem unbekannten Schlüssel praktisch keine Informationen aus dem Geheimtext (außer der Länge der Nachricht) über das ableiten kann, was man ohne den Geheimtext gewusst hätte. Es hat sich gezeigt, dass alle oben diskutierten Modi, mit Ausnahme des ECB-Modus, diese Eigenschaft bei sogenannten Chosed-Plaintext-Attacken bereitstellen .

Polsterung

Einige Modi wie der CBC-Modus arbeiten nur mit vollständigen Klartextblöcken. Das einfache Erweitern des letzten Blocks einer Nachricht mit Null-Bits reicht nicht aus, da es einem Empfänger nicht ermöglicht, Nachrichten, die sich nur in der Menge der Füllbits unterscheiden, leicht zu unterscheiden. Noch wichtiger ist, dass eine so einfache Lösung zu sehr effizienten Padding-Orakel-Angriffen führt . Daher wird ein geeignetes Padding-Schema benötigt, um den letzten Klartextblock auf die Blockgröße der Chiffre zu erweitern. Während viele gängige Schemata, die in Standards und in der Literatur beschrieben sind, sich als anfällig für Padding-Orakel-Angriffe erwiesen haben, ist eine Lösung, die ein Ein-Bit hinzufügt und dann den letzten Block um Null-Bits erweitert, standardisiert als "Padding-Methode 2" in ISO /IEC 9797-1, hat sich gegen diese Angriffe als sicher erwiesen.

Kryptoanalyse

Brute-Force-Angriffe

Diese Eigenschaft führt zu einer quadratischen Verschlechterung der Sicherheit der Chiffre und muss bei der Auswahl einer Blockgröße berücksichtigt werden. Es gibt jedoch einen Kompromiss, da große Blockgrößen dazu führen können, dass der Algorithmus ineffizient arbeitet. Frühere Blockchiffren wie der DES haben typischerweise eine 64-Bit-Blockgröße gewählt, während neuere Designs wie der AES Blockgrößen von 128 Bit oder mehr unterstützen, wobei einige Verschlüsselungen eine Reihe unterschiedlicher Blockgrößen unterstützen.

Differentielle Kryptoanalyse

Lineare Kryptoanalyse

Die lineare Kryptoanalyse ist eine Form der Kryptoanalyse, die auf der Suche nach affinen Annäherungen an die Aktion einer Chiffre basiert. Die lineare Kryptoanalyse ist einer der beiden am häufigsten verwendeten Angriffe auf Blockchiffren; der andere ist die differenzielle Kryptoanalyse .

Die Entdeckung wird Mitsuru Matsui zugeschrieben , der die Technik zuerst auf die FEAL- Chiffre anwandte (Matsui und Yamagishi, 1992).

Integrale Kryptoanalyse

Integrale Kryptoanalyse ist ein kryptanalytischer Angriff, der insbesondere auf Blockchiffren anwendbar ist, die auf Substitutions-Permutations-Netzwerken basieren. Im Gegensatz zur differenziellen Kryptoanalyse, die Paare ausgewählter Klartexte mit einer festen XOR-Differenz verwendet, verwendet die integrale Kryptoanalyse Mengen oder sogar Multimengen ausgewählter Klartexte, von denen ein Teil konstant gehalten wird und ein anderer Teil durch alle Möglichkeiten variiert. Zum Beispiel könnte ein Angriff 256 ausgewählte Klartexte verwenden, die alle bis auf 8 ihrer Bits gleich sind, sich aber alle in diesen 8 Bits unterscheiden. Ein solcher Satz hat notwendigerweise eine XOR-Summe von 0, und die XOR-Summen der entsprechenden Sätze von Chiffretexten liefern Informationen über die Operation des Chiffre. Dieser Kontrast zwischen den Unterschieden von Textpaaren und den Summen größerer Textmengen inspirierte den Namen "Integrale Kryptoanalyse", der die Terminologie der Infinitesimalrechnung entlehnt.

Andere Techniken

Die Entwicklung des Bumerang-Angriffs ermöglichte es, differenzielle Kryptoanalysetechniken auf viele Verschlüsselungen anzuwenden, die zuvor als sicher gegen differenzielle Angriffe galten

Neben linearer und differenzieller Kryptoanalyse gibt es einen wachsenden Katalog von Angriffen: abgeschnittene differenzielle Kryptoanalyse , partielle differenzielle Kryptoanalyse, integrale Kryptoanalyse , die quadratische und integrale Angriffe umfasst, Slide-Attacken , Bumerang-Angriffe , der XSL-Angriff , unmögliche differenzielle Kryptoanalyse und algebraische Angriffe . Damit ein neues Blockchiffre-Design glaubwürdig ist, muss es den Nachweis der Sicherheit gegen bekannte Angriffe erbringen.

Nachweisbare Sicherheit

Wenn eine Blockchiffre in einem bestimmten Betriebsmodus verwendet wird , sollte der resultierende Algorithmus idealerweise ungefähr so ​​sicher sein wie die Blockchiffre selbst. ECB (oben diskutiert) fehlt diese Eigenschaft nachdrücklich: Unabhängig davon, wie sicher die zugrunde liegende Blockchiffre ist, kann der ECB-Modus leicht angegriffen werden. Andererseits kann der CBC-Modus unter der Annahme, dass die zugrunde liegende Blockchiffre ebenfalls sicher ist, als sicher nachgewiesen werden. Beachten Sie jedoch, dass für solche Aussagen formale mathematische Definitionen erforderlich sind, was es bedeutet, dass ein Verschlüsselungsalgorithmus oder eine Blockchiffre "sicher" ist. In diesem Abschnitt werden zwei allgemeine Begriffe dafür beschrieben, welche Eigenschaften eine Blockchiffre haben sollte. Jedes entspricht einem mathematischen Modell, das verwendet werden kann, um Eigenschaften von Algorithmen höherer Ebene, wie beispielsweise CBC, zu beweisen.

Diese allgemeine Herangehensweise an die Kryptographie – der Nachweis, dass Algorithmen auf höherer Ebene (wie CBC) unter explizit festgelegten Annahmen bezüglich ihrer Komponenten (wie einer Blockchiffre) sicher sind – wird als beweisbare Sicherheit bezeichnet .

Standardmodell

Informell ist eine Blockchiffre im Standardmodell sicher, wenn ein Angreifer den Unterschied zwischen der Blockchiffre (ausgestattet mit einem zufälligen Schlüssel) und einer zufälligen Permutation nicht erkennen kann.

Um etwas genauer zu sein, sei E eine n- Bit-Blockchiffre. Wir stellen uns folgendes Spiel vor:

1. Die Person, die das Spiel ausführt, wirft eine Münze.
   • Landet die Münze auf Kopf, wählt er einen zufälligen Schlüssel K und definiert die Funktion f = E _K .
   • Wenn die Münze auf Zahl landet, wählt er eine zufällige Permutation π auf der Menge von n- Bit-Strings und definiert die Funktion f = π .
2. Der Angreifer wählt einen n- Bit-String X und die Person, die das Spiel ausführt , teilt ihm den Wert von f ( X ) mit.
3. Schritt 2 wird insgesamt q mal wiederholt . (Jede dieser q Interaktionen ist eine Abfrage .)
4. Der Angreifer errät, wie die Münze gelandet ist. Er gewinnt, wenn seine Vermutung richtig ist.

Der Angreifer, den wir als Algorithmus modellieren können, wird als Gegner bezeichnet . Die Funktion f (die der Gegner abfragen konnte) heißt Orakel .

Beachten Sie, dass ein Gegner trivialerweise eine Gewinnchance von 50% erzielen kann, indem er einfach zufällig errät (oder sogar beispielsweise immer "Kopf errät"). Daher bezeichne P _E ( A ) die Wahrscheinlichkeit, dass der Gegner A dieses Spiel gegen E gewinnt , und definiere den Vorteil von A als 2( P _E ( A ) − 1/2). Daraus folgt, dass, wenn A zufällig rät, sein Vorteil 0 ist; gewinnt dagegen A immer, so ist sein Vorteil 1. Die Blockchiffre E ist eine Pseudo-Zufallspermutation (PRP), wenn kein Gegner einen Vorteil deutlich größer 0 hat, wenn vorgegebene Einschränkungen für q und dessen Laufzeit gegeben sind . Wenn Gegner in Schritt 2 oben die Möglichkeit haben, f ⁻¹ ( X ) anstelle von f ( X ) zu lernen (aber immer noch nur kleine Vorteile haben), dann ist E eine starke PRP (SPRP). Ein Gegner ist nicht adaptiv, wenn er alle q- Werte für X wählt, bevor das Spiel beginnt (das heißt, er verwendet keine Informationen aus vorherigen Abfragen, um jedes X zu wählen, während es geht).

Diese Definitionen haben sich für die Analyse verschiedener Betriebsmodi als nützlich erwiesen. Zum Beispiel kann man ein ähnliches Spiel definieren, um die Sicherheit eines auf Blockchiffren basierenden Verschlüsselungsalgorithmus zu messen, und dann versuchen (durch ein Reduktionsargument zu zeigen ), dass die Wahrscheinlichkeit, dass ein Gegner dieses neue Spiel gewinnt, nicht viel größer ist als P _E ( A ) für ein A . (Die Reduktion stellt typischerweise Grenzen für q und die Laufzeit von A bereit .) Wenn P _E ( A ) für alle relevanten A klein ist , dann hat kein Angreifer eine signifikante Wahrscheinlichkeit, das neue Spiel zu gewinnen. Dies formalisiert die Idee, dass der übergeordnete Algorithmus die Sicherheit der Blockchiffre erbt.

Ideales Chiffriermodell

Praktische Auswertung

Blockchiffren können in der Praxis nach mehreren Kriterien bewertet werden. Häufige Faktoren sind:

• Schlüsselparameter, wie die Schlüsselgröße und die Blockgröße, die beide eine obere Grenze für die Sicherheit der Chiffre darstellen.
• Das geschätzte Sicherheitsniveau , das auf dem Vertrauen basiert, das in das Blockchiffren-Design gewonnen wurde, nachdem es im Laufe der Zeit großen Anstrengungen in der Kryptoanalyse weitgehend standgehalten hat, der mathematischen Solidität des Designs und der Existenz praktischer oder zertifizierender Angriffe.
• Die Komplexität der Chiffre und ihre Eignung zur Implementierung in Hardware oder Software . Hardware-Implementierungen können die Komplexität in Bezug auf Gate-Anzahl oder Energieverbrauch messen , die wichtige Parameter für ressourcenbeschränkte Geräte sind.
• Die Chiffre Leistung in Bezug auf die Verarbeitung Durchsatz auf verschiedenen Plattformen, einschließlich der Speicheranforderungen.
• Die Kosten der Chiffre, die sich auf Lizenzanforderungen beziehen, die aufgrund von Rechten an geistigem Eigentum gelten können .
• Die Flexibilität der Chiffre, einschließlich ihrer Fähigkeit, mehrere Schlüsselgrößen und Blocklängen zu unterstützen.

Bemerkenswerte Blockchiffren

Luzifer / DES

Lucifer gilt allgemein als die erste zivile Blockchiffre, die in den 1970er Jahren bei IBM auf der Grundlage von Arbeiten von Horst Feistel entwickelt wurde . Eine überarbeitete Version des Algorithmus wurde als Federal Information Processing Standard der US-Regierung übernommen : FIPS PUB 46 Data Encryption Standard (DES). Es wurde vom US National Bureau of Standards (NBS) nach einer öffentlichen Aufforderung zur Einreichung von Einreichungen und einigen internen Änderungen durch NBS (und möglicherweise die NSA ) ausgewählt. DES wurde 1976 öffentlich veröffentlicht und ist weit verbreitet.

DES wurde unter anderem entwickelt, um einem bestimmten kryptanalytischen Angriff zu widerstehen, der der NSA bekannt ist und von IBM wiederentdeckt wurde, obwohl er öffentlich unbekannt war, bis er Ende der 1980er Jahre wiederentdeckt und von Eli Biham und Adi Shamir veröffentlicht wurde. Die Technik wird als differenzielle Kryptanalyse bezeichnet und bleibt einer der wenigen allgemeinen Angriffe gegen Blockchiffren; Lineare Kryptanalyse ist eine andere, die vor ihrer Veröffentlichung durch Mitsuru Matsui möglicherweise sogar der NSA unbekannt war . DES führte zu einer großen Menge anderer Arbeiten und Veröffentlichungen in Kryptographie und Kryptoanalyse in der offenen Community und inspirierte viele neue Verschlüsselungsdesigns.

DES hat eine Blockgröße von 64 Bit und eine Schlüsselgröße von 56 Bit. 64-Bit-Blöcke wurden nach DES in Blockchiffrendesigns üblich. Die Schlüssellänge hing von mehreren Faktoren ab, einschließlich staatlicher Regulierung. Viele Beobachter in den 1970er Jahren kommentierten, dass die für DES verwendete Schlüssellänge von 56 Bit zu kurz war. Im Laufe der Zeit wurde seine Unzulänglichkeit offensichtlich, insbesondere nachdem 1998 von der Electronic Frontier Foundation eine Spezialmaschine zum Brechen von DES demonstriert wurde . Eine Erweiterung von DES, Triple DES , verschlüsselt jeden Block dreifach mit entweder zwei unabhängigen Schlüsseln (112-Bit-Schlüssel und 80-Bit-Sicherheit) oder drei unabhängigen Schlüsseln (168-Bit-Schlüssel und 112-Bit-Sicherheit). Es wurde weithin als Ersatz angenommen. Ab 2011 gilt die Drei-Schlüssel-Version noch als sicher, obwohl die Standards des National Institute of Standards and Technology (NIST) die Verwendung der Zwei-Schlüssel-Version in neuen Anwendungen aufgrund ihrer 80-Bit-Sicherheitsstufe nicht mehr zulassen.

IDEE

Der International Data Encryption Algorithm ( IDEA ) ist eine Blockchiffre , die von James Massey von der ETH Zürich und Xuejia Lai entwickelt wurde ; es wurde erstmals 1991 als beabsichtigter Ersatz für DES beschrieben.

IDEA arbeitet mit 64-Bit- Blöcken unter Verwendung eines 128-Bit-Schlüssels und besteht aus einer Reihe von acht identischen Transformationen (einer Runde ) und einer Ausgabetransformation (der halben Runde ). Die Verfahren zur Verschlüsselung und Entschlüsselung sind ähnlich. IDEA erhält einen Großteil seiner Sicherheit durch Verschachteln von Operationen aus verschiedenen Gruppen – modulare Addition und Multiplikation und bitweises Exklusiv-Oder (XOR) – die in gewisser Weise algebraisch "inkompatibel" sind.

Die Designer analysierten IDEA, um seine Stärke gegenüber der differentiellen Kryptoanalyse zu messen, und kamen zu dem Schluss, dass es unter bestimmten Annahmen immun ist. Es wurden keine erfolgreichen linearen oder algebraischen Schwächen berichtet. Ab 2012 kann der beste Angriff, der für alle Schlüssel gilt, volle 8,5-Runden-IDEA mit einem Narrow-Bicliques-Angriff brechen, der etwa viermal schneller als Brute-Force ist.

RC5

Eine Runde (zwei Halbrunden) der RC5-Blockchiffre

RC5 ist eine 1994 von Ronald Rivest entwickelte Blockchiffre, die im Gegensatz zu vielen anderen Chiffren eine variable Blockgröße (32, 64 oder 128 Bit), Schlüsselgröße (0 bis 2040 Bit) und Anzahl der Runden (0 bis 255) hat. Die ursprünglich vorgeschlagene Parameterauswahl war eine Blockgröße von 64 Bit, ein 128-Bit-Schlüssel und 12 Runden.

Ein Schlüsselmerkmal von RC5 ist die Verwendung von datenabhängigen Rotationen; Eines der Ziele von RC5 war es, die Untersuchung und Bewertung solcher Operationen als kryptographisches Primitiv anzuregen. RC5 besteht auch aus einer Reihe modularer Ergänzungen und XORs. Die allgemeine Struktur des Algorithmus ist ein Feistel- ähnliches Netzwerk. Die Verschlüsselungs- und Entschlüsselungsroutinen können in wenigen Codezeilen spezifiziert werden. Der Schlüsselplan ist jedoch komplexer und erweitert den Schlüssel mit einer im Wesentlichen Einwegfunktion mit den binären Erweiterungen von e und dem Goldenen Schnitt als Quellen für " nichts im Ärmel Zahlen ". Die verlockende Einfachheit des Algorithmus zusammen mit der Neuheit der datenabhängigen Rotationen hat RC5 zu einem attraktiven Studienobjekt für Kryptoanalytiker gemacht.

12-Runden-RC5 (mit 64-Bit-Blöcken) ist anfällig für einen differenziellen Angriff mit 2 ⁴⁴ ausgewählten Klartexten. Als ausreichenden Schutz werden 18–20 Runden empfohlen.

Rijndael / AES

Die von den belgischen Kryptographen Joan Daemen und Vincent Rijmen entwickelte Rijndael- Chiffre war eines der konkurrierenden Designs, um DES zu ersetzen. Es gewann den 5-jährigen öffentlichen Wettbewerb , um AES (Advanced Encryption Standard) zu werden.

AES wurde 2001 von NIST übernommen und hat eine feste Blockgröße von 128 Bit und eine Schlüsselgröße von 128, 192 oder 256 Bit, während Rijndael mit Block- und Schlüsselgrößen in einem beliebigen Vielfachen von 32 Bit mit einem Minimum von 128 . angegeben werden kann Bits. Die Blockgröße hat maximal 256 Bit, aber die Schlüsselgröße hat kein theoretisches Maximum. AES arbeitet mit einer 4×4- Spalten- Matrix größerer Ordnung von Bytes, die als Zustand bezeichnet wird (Versionen von Rijndael mit einer größeren Blockgröße haben zusätzliche Spalten im Zustand).

Kugelfisch

Blowfish ist eine Blockchiffre, die 1993 von Bruce Schneier entwickelt wurde und in einer Vielzahl von Verschlüsselungssammlungen und Verschlüsselungsprodukten enthalten ist. Blowfish hat eine 64-Bit-Blockgröße und eine variable Schlüssellänge von 1 Bit bis zu 448 Bit. Es ist eine 16-Runden- Feistel-Chiffre und verwendet große schlüsselabhängige S-Boxen . Bemerkenswerte Merkmale des Designs sind die schlüsselabhängigen S-Boxen und ein hochkomplexer Schlüsselplan .

Er wurde als Allzweckalgorithmus entwickelt, der als Alternative zum alternden DES gedacht ist und frei von den Problemen und Einschränkungen anderer Algorithmen ist. Zum Zeitpunkt der Veröffentlichung von Blowfish waren viele andere Designs proprietär, mit Patenten belastet oder waren Geschäfts- und Regierungsgeheimnisse. Schneier hat erklärt: "Blowfish ist nicht patentiert und wird es in allen Ländern bleiben. Der Algorithmus wird hiermit gemeinfrei und kann von jedem frei verwendet werden." Gleiches gilt für Twofish , einen Nachfolgealgorithmus von Schneier.

Verallgemeinerungen

Optimierbare Blockchiffren

M. Liskov, R. Rivest und D. Wagner haben eine verallgemeinerte Version von Blockchiffren beschrieben, die als "tweakable" Blockchiffren bezeichnet werden. Eine änderbare Blockchiffre akzeptiert eine zweite Eingabe, die als Tweak bezeichnet wird, zusammen mit ihrer üblichen Klartext- oder Geheimtexteingabe. Der Tweak wählt zusammen mit dem Schlüssel die von der Chiffre berechnete Permutation aus. Wenn das Ändern von Tweaks ausreichend leicht ist (im Vergleich zu einem normalerweise ziemlich teuren Tasteneinrichtungsvorgang), dann werden einige interessante neue Betriebsmodi möglich. Der Artikel zur Festplattenverschlüsselungstheorie beschreibt einige dieser Modi.

Formaterhaltende Verschlüsselung

Blockchiffren arbeiten traditionell über ein binäres Alphabet . Das heißt, sowohl die Eingabe als auch die Ausgabe sind binäre Zeichenfolgen, die aus n Nullen und Einsen bestehen. In manchen Situationen möchte man jedoch möglicherweise eine Blockchiffre haben, die über ein anderes Alphabet funktioniert; Beispielsweise könnte das Verschlüsseln von 16-stelligen Kreditkartennummern so, dass der Chiffretext auch eine 16-stellige Zahl ist, das Hinzufügen einer Verschlüsselungsschicht zu Legacy-Software erleichtern. Dies ist ein Beispiel für eine formaterhaltende Verschlüsselung . Allgemeiner gesagt erfordert eine formaterhaltende Verschlüsselung eine verschlüsselte Permutation in einer endlichen Sprache . Dies macht formaterhaltende Verschlüsselungsschemata zu einer natürlichen Verallgemeinerung von (einstellbaren) Blockchiffren. Im Gegensatz dazu sind herkömmliche Verschlüsselungsverfahren wie CBC keine Permutationen, da derselbe Klartext in mehrere verschiedene Geheimtexte verschlüsseln kann, selbst wenn ein fester Schlüssel verwendet wird.

Beziehung zu anderen kryptografischen Primitiven

Blockchiffren können verwendet werden, um andere kryptografische Primitive zu erstellen, wie z. B. die folgenden. Damit diese anderen Primitiven kryptographisch sicher sind, muss darauf geachtet werden, dass sie richtig erstellt werden.

• Stromchiffren können mit Blockchiffren erstellt werden. OFB-Modus und CTR-Modus sind Blockmodi, die eine Blockchiffre in eine Stromchiffre umwandeln.
• Kryptografische Hashfunktionen können mit Blockchiffren erstellt werden. Beschreibungen einiger solcher Methoden finden Sie unter Einweg-Kompressionsfunktion . Die Verfahren ähneln den Blockchiffre-Betriebsarten, die üblicherweise für die Verschlüsselung verwendet werden.
• Kryptographisch sichere Pseudozufallszahlengeneratoren (CSPRNGs) können unter Verwendung von Blockchiffren erstellt werden.
• Sichere pseudozufällige Permutationen von endlichen Mengen beliebiger Größe können mit Blockchiffren konstruiert werden; siehe Formaterhaltende Verschlüsselung .
• Eine öffentlich bekannte unvorhersehbare Permutation in Kombination mit Key Whitening reicht aus, um eine Blockchiffre zu konstruieren – wie die Single-Key Even-Mansour-Chiffre , vielleicht die einfachste nachweislich sichere Blockchiffre.
• Message Authentication Codes (MACs) werden oft aus Blockchiffren erstellt. CBC-MAC , OMAC und PMAC sind solche MACs.
• Die authentifizierte Verschlüsselung basiert ebenfalls auf Blockchiffren. Es bedeutet, gleichzeitig zu verschlüsseln und MAC. Das heißt, sowohl Vertraulichkeit als auch Authentifizierung zu gewährleisten . CCM , EAX , GCM und OCB sind solche authentifizierten Verschlüsselungsmodi.

So wie Blockchiffren verwendet werden können, um Hashfunktionen zu erstellen, können Hashfunktionen verwendet werden, um Blockchiffren zu erstellen. Beispiele für solche Blockchiffren sind SHACAL , BEAR und LION .

Siehe auch

• Zusammenfassung der Verschlüsselungssicherheit
• Themen der Kryptographie

Verweise

Weiterlesen

• Knudsen, Lars R.; Robshaw, Matthew (2011). Der Blockchiffre-Begleiter . Springer. ISBN 9783642173417.

Externe Links

• Eine Liste vieler symmetrischer Algorithmen, von denen die meisten Blockchiffren sind.
• Die Blockchiffre-Lounge
• Was ist eine Blockchiffre? von RSA- FAQ
• Blockchiffre basierend auf Goldsequenzen und Chaotic Logistic Tent System