Klausurvorbereitung 5 – Feistelchiffren

Prinzipieller Aufbau:

feistel-chiffre-aufbau-allgemein

Vorteil: Gleiche Hardware für Verschlüsselung und Entschlüsselung

Nachteil: In jedem Schritt wird nur eine Hälfte verschlüsselt, die andere Hälfte geht ungefiltert durch. Als wichtigste Designkriterien haben wir Diffusion und Konfusion genannt. Hier wird in jeder Runde nur jeweils in der Hälfte Konfusion und Diffusion eingebracht, daher braucht man eine hohe Rundenanzahl.

Wichtig für die Prüfung: Rundenfunktion muss ausgewertet werden.

Anwendung: DES

data-encryption-standard-des-feistel-chiffre

Für Diffusion sorgt allgemein Transpositionen und Permutationen, bei DES in P und E.
Für Konfusion (Zerstören statistischer Zusammenhänge) sorgt alles, was Substitution macht (SubBytes bei AES).

5.1 Anwendung einer Feistel-Chiffre (Übung 5.1)

Betrachtet wird die Feistel-Chiffre

$\left( {{L_{i+1}},{R_{i+1}}} \right) = {E_{Ki}}\left( {{L_i},{R_i}} \right) = \left( {{R_i},{L_i} \oplus f\left( {{R_i},{K_i}} \right)} \right)$

mit einer Blocklänge $n = 6Bit$ , $f:\mathbb{Z}_2^3 \times \mathbb{Z}_2^3 \to \mathbb{Z}_2^3$ , $\left( {{R_i},{K_i}} \right) \mapsto S\left( {{R_i}} \right) \oplus {K_i}$ und einer Rundenzahl von $r = 2$ . Die verwendete S-Box $S:\mathbb{Z}_2^3 \to \mathbb{Z}_2^3$ ist in der nachfolgenden Tabelle dargestellt:

$\begin{array}{*{20}{c}}{Eingabe} &\vline & {000} & {001} & {010} & {011} & {100} & {101} & {110} & {111} \\ \hline{Ausgabe} &\vline & {101} & {010} & {111} & {001} & {110} & {100} & {000} & {011} \\ \end{array}$

Die Abbildung zur Erzeugung der Rundenschlüssel ${K_i}$ aus dem Schlüssel $K$ ist wie folgt definiert:

${K_i} = \left( {K+3 \cdot i} \right)\bmod 8,\quad i \in \left\{ {1,2} \right\}$ ,

wobei die Bitfolge $K$ als positive ganze Zahl interpretiert und ${K_i}$ nach der Berechnung in eine Bitfolge umgewandelt wird.

Entschlüsseln Sie den Chi-Textblock C=101001 mit dem Schlüssel K=011.
Verifizieren Sie das Ergebnis, indem Sie den in Teilaufgabe a) ermittelten Klartextblock mit dem Schlüssel K erneut verschlüsseln.

Lösung 5.1

Feistel-Chiffren sind so konstruiert, dass Ver- und Entschlüsselung prinzipiell mit der gleichen Funktion durchgeführt werden, wobei die Rundenschüssel bei der Entschlüsselung in umgekehrter Reihenfolge zu verwenden sind.

Die Entschlüsselungsfunktion lautet also:

$\left( {{R_i},{L_i}} \right) = \left( {{L_{i+1}},{R_{i+1}} \oplus f\left( {{L_{i+1}},{K_i}} \right)} \right)$

Wir berechnen zunächst die Rundenschlüssel mit der gegebenen Abbildung:

${K_1} = \left( {K+3 \cdot 1} \right)\bmod 8 = 3+3 = 6 = 110$

${K_2} = \left( {K+3 \cdot 2} \right)\bmod 8 = \left( {3+6} \right)\bmod 8 = 1 = 001$

Entschlüsselung:

$\left( {{R_2},{L_2}} \right) = \left( {{L_3},{R_3} \oplus f\left( {{L_3},{K_2}} \right)} \right) = \left( {101,001 \oplus \left( {100 \oplus 001} \right)} \right) = \left( {101,100} \right)$

$\left( {{R_1},{L_1}} \right) = \left( {{L_2},{R_2} \oplus f\left( {{L_2},{K_1}} \right)} \right) = \left( {100,101 \oplus \left( {110 \oplus 110} \right)} \right) = \left( {100,101} \right)$

$= P$

Zur Verschlüsselung werden die Rundenschlüssel in umgekehrter Reihenfolge verwendet:

$P = \left( {101,100} \right) = \left( {{L_1},{R_1}} \right)$

$\left( {{L_2},{R_2}} \right) = \left( {{R_1},{L_1} \oplus f\left( {{R_1},{K_1}} \right)} \right) = \left( {100,101 \oplus \left( {110 \oplus 110} \right)} \right) = \left( {100,101} \right)$

$\left( {{L_3},{R_3}} \right) = \left( {{R_2},{L_2} \oplus f\left( {{R_2},{K_2}} \right)} \right) = \left( {101,100 \oplus \left( {100 \oplus 001} \right)} \right) = \left( {101,001} \right)$

$= C$

Achtung: S-Box nicht vergessen!

5.2 Überprüfung einer S-Box (Übung 5.2, Prüfung FT2009, Aufgabe 3a)

Gegeben sei eine S-Box $S:\mathbb{Z}_2^4 \to \mathbb{Z}_2^4$ , die die nachfolgend dargestellten Ersetzungen durchführt:

sbox-blockchiffre-geeignet-linear

Bewerten Sie, ob diese S-Box für den Einsatz in einer Blockchiffre geeignet ist. Begründen Sie Ihre Antwort.
Gegeben sei nun die folgende S-Box:

sbox-blockchiffre-geeignet-linear

Bewerten Sie, ob diese S-Box dazu geeignet ist, um in einer Blockchiffre Konfusion und Diffusion zu erreichen. Begründen Sie Ihre Antwort.

Lösung 5.2

Ersetzt man die Bitwerte durch die Zahlen im dezimalen Zahlensystem, so erhält man:
sbox-blockchiffre-geeignet-linear-losung
Es gilt also $x \mapsto 3x\bmod 16$ . Die S-Box ist linear und für den Einsatz in einer Blockchiffre ungeeignet.

Analog zu Teilaufgabe a) gilt hier $x \mapsto 7x\bmod 16$ . Auch diese S-Box ist daher ungeeignet.

5.3 DES-Schlüssel Validierung (Übung 5.3)

Welche der nachfolgenden Zahlenfolgen sind geeignete DES-Schlüssel?

0x313457979BCBFDF1
0x3F2BA10FFE3752C88315B103
0xA4DC228645319D22
0xA4D92386FE014513

Lösung 5.3

Die beiden Kriterien für einen DES-Schlüssel sind zum einen die vorgeschriebene Länge von 64 Bit und zum anderen die Berücksichtigung der Paritätsbits. Es ist sinnvoll, die zu prüfenden Ziffernfolgen in die Binärdarstellung umzuwandeln und die Bits byteweise anzuordnen.

0x313457979BCBFDF1 ist ein gültiger DES-Schlüssel:

0×31 = 00110001
0×34 = 00110100
0×57 = 01010111
0×97 = 10010111
0x9B = 10011011
0xCB = 10101011
0xFD = 11111101
0xF1 = 11110001

0x3F2BA10FFE3752C88315B103 ist kein gültiger DES-Schlüssel, da die Ziffernfolge zu lang ist.

0xA4DC228645319D22 ist kein gültiger DES-Schlüssel (Parity-Bedingung in der 3. und 7. Zeile):

0xA4 = 10100100
0xDC = 11011100
0×22 = 00100010
0×86 = 10000110
0×45 = 01000101
0×31 = 00110001
0x9D = 10011101
0×22 = 00100010

0xA4D92386FE014513 ist ein gültiger DES-Schlüssel:

0xA4 = 10100100
0xD9 = 11011001
0×23 = 00100011
0×86 = 10000110
0xFE = 11111110
0×01 = 00000001
0×45 = 01000101
0×13 = 00010011

5.4 Schwache DES-Schlüssel (Übung 5.4)

Ein DES-Schlüssel K wird als schwach bezeichnet, wenn DES_K eine Involution ist. Geben Sie vier schwache Schlüssel für DES an.

Lösung 5.4

Sind die Rundenschlüssel K1 bis K16 gleich, dann ist die Reihenfolge der Anwendung für Ver- und Entschlüsselung ebenfalls identisch. In diesem Falle ist DES_K ganz klar eine Involution. Die sechzehn Rundenschlüssel sind identisch, wenn die Register C und D, a) ausschließlich Nullen oder b) ausschließlich Einsen, enthalten, da eine Rotation der jeweils resultierenden Bitstrings keine Veränderung bewirkt. Auf Grund dieser Überlegungen können vier schwache DES-Schlüssel leicht berechnet werden, indem die Inverse Funktion zu “Permuted Choice 1” auf die vier möglichen Kombinationen dieser Registerinhalte von C und D angewandt wird:

schwache-data-encryption-schlussel

5.5 Fiktive Blockchiffre EASYPERM (Übung 5.7)

Gegenstand der Betrachtung sei die fiktive Blockchiffre „EASYPERM“, deren Verschlüsselungsfunktion wie folgt definiert ist:

${E_K}:\mathbb{Z}_2^4 \to \mathbb{Z}_2^4,\quad {b_1}{b_2}{b_3}{b_4} \mapsto {b_{K\left( 1 \right)}}{b_{K\left( 2 \right)}}{b_{K\left( 3 \right)}}{b_{K\left( 4 \right)}}$

Der Schlüsselraum ist somit $\mathcal{K} = {S_4}$ , aus dem der Schlüssel

$K = \left( {\begin{array}{*{20}{c}} 1 & 2 & 3 & 4 \\ 3 & 4 & 1 & 2 \\ \end{array} } \right)$

gewählt wird.

Verschlüsseln Sie den Klartext P=0xA1B3 im ECB-Modus.
Entschlüsseln Sie den im CBC-Modus verschlüsselten Geheimtext C=0xA3701
Verschlüsseln Sie den Klartext P=0xA1B3 im CFB-Modus (IV=1010).

Lösung 5.5

Der gewählte Schlüssel bewirkt einen zyklischen Linksshift um zwei Stellen. Bei nochmaliger Anwendung von EK ist die ursprüngliche Reihenfolge wiederhergestellt. Das bedeutet, Ver- und Entschlüsselungsfunktion von „EASYPERM” sind identisch (Involution).

Der Klartext P = 0xA1B3 = 1010000110110011 wird im ECB-Modus verschlüsselt, d. h. die Verschlüsselungsfunktion wird der Reihe nach auf alle Blöcke angewendet.

Geheimtext: 1010010011101100 = 0xA4EC

Aus dem gegebenen Geheimtext C = 0xA3701 folgt unmittelbar C₀ = 0xA = 1010 = IV. Damit werden nun die Klartextblöcke ermittelt:

${P_1} = {C_0} \oplus {E_K}\left( {{C_1}} \right) = 1010 \oplus 1100 = 0110$

${P_2} = {C_1} \oplus {E_K}\left( {{C_2}} \right) = 0011 \oplus 1101 = 1110$

${P_3} = {C_2} \oplus {E_K}\left( {{C_3}} \right) = 0111 \oplus 0000 = 0111$

${P_4} = {C_3} \oplus {E_K}\left( {{C_4}} \right) = 0000 \oplus 0100 = 0100$

Der Klartext lautet also 0100111001110100 = 0x6E74.

Beim Verschlüsseln im CFB-Modus wird die Verschlüsselungsfunktion zunächst auf den Initialisierungsvektor IV angewendet: E_K(IV) = 1010. Die Geheimtextblöcke werden dann mit der aus der Vorlesung bekannten Formel erzeugt:
${C_1} = {P_1} \oplus {E_K}\left( {IV} \right) = 1010 \oplus 1010 = 0000$

${C_2} = {P_2} \oplus {E_k}\left( {{C_1}} \right) = 0001 \oplus 0000 = 0001$

${C_3} = {P_3} \oplus {E_k}\left( {{C_2}} \right) = 1011 \oplus 0100 = 1111$

${C_4} = {P_4} \oplus {E_k}\left( {{C_3}} \right) = 0011 \oplus 1111 = 1100$

Der Geheimtext lautet also 0000000111111100 = 0x01FC.

5.6 Triple DES (Klausur WT2010 1.8)

Trifft folgende Aussage zu?
Wird der Data Encryption Standard (DES) mit drei verschiedenen Schlüsseln als TDES verwendet, genügt diese Blockchiffre auch heute noch den Sicherheitsanforderungen.

Lösung 5.6

Dies trifft zu. Eine derartige Verschlüsselung wird z.B. bei Geldautomaten benutzt.

Mathematical Engineering