<< . .

. 7
( : 33)



. . >>

3.2.5 Aufbau der Verschlüsselungsfunktion

Wir beschreiben nun, wie die Verschlüsselungsfunktion f k aus den Rundenfunk-
tionen : F16 — F16 ’ F16 und ˜ : F16 — F16 ’ F16 zusammengesetzt ist. Dabei
benutzen wir die Abkürzung

k i (x) = (x, k i ) bzw. ˜k N (x) = ˜ (x, k N )

und setzen
f k (x) = ˜ k N —¦ —¦···—¦ —¦ k1 (x + k0 ) .
k N’1 k2

Die nullte Rundenfunktion ist dabei die Addition des nullten Rundenschlüs-
sels k0 auf x. Diese Abbildung bezeichnen wir nicht n¤her mit einem Symbol.
Dann werden die regul¤ren Rundenfunktionen ki mit den Rundenschlüsseln
k1 , . . . , k N’1 angewendet und schließlich die modi¬zierte Abschlussrunde ˜k N
mit dem Rundenschlüssel k N .
Jede Runde wiederum ist aus vier (bei ˜ drei) Abbildungen zusammengesetzt “
auf diese Zusammensetzung gehen wir im n¤chsten Abschnitt ein, vorab halten
wir fest:
Die Verschlüsselungsfunktion f k ist das Produkt von N + 1 Rundenfunktionen

P—K ’ C
f: .
(x, k) ’ ˜k N —¦ —¦···—¦ —¦ k1 (x + k0 )
k N’1 k2

Bemerkung
Diese Struktur ist typisch für moderne symmetrische Verfahren. Eine einfach
strukturierte Routine “ die Rundenfunktion “ wird mehrfach mit variierenden
Rundenschlüsseln wiederholt. Durch geeignete Maßnahmen wird sichergestellt,
dass mit jeder Runde Diffusion und Konfusion zunehmen.


3.2.6 Die Rundenfunktionen

Bei vielen symmetrischen Verfahren weichen die erste und/oder die letzte Runde
von den anderen ab. In der Tat muss die erste und die letzte Aktion das Addie-
ren eines Rundenschlüssels sein. Aktionen vor der ersten bzw. nach der letzten
Addition des Rundenschlüssels, die nicht vom Schlüssel abh¤ngen, könnte ein
48 3 Block-Chiffren “ AES und DES

Angreifer, der das System kennt, rückg¤ngig machen. Sie würden also nicht zur
Sicherheit beitragen. Aber natürlich können solche Komponenten aus anderen
Gründen eingesetzt werden. Bei DES wurde etwa eine initiale Permutation einge-
setzt, die nichts zur Geheimhaltung beitrug “ wir kommen darauf noch zu spre-
chen.
Nun wenden wir uns den Runden ki , i = 1, . . . , N ’ 1 und ˜ k N zu. Jede Runde
k i besteht aus vier Abbildungen, die modi¬zierte Abschlussrunde ˜ k N nur aus
drei: Die regul¤ren Rundenfunktionen haben die Form:

(x, k i ) = Add-Round-Key Mix-Columns Shift-Rows(subByte(x)) , k i ,

und die Abschlussrunde hat das Aussehen:

˜ (x, k N ) = Add-Round-Key Shift-Rows subByte(x) , k N .

In der letzten Runde wird also schlicht die Abbildung Mix-Columns weggelas-
sen. Wir erl¤utern nun die einzelnen Abbildungen, aus denen die Rundenfunk-
tionen zusammengesetzt sind.

subByte (auch S-Box genannt) ist die folgende Abbildung:

subByte : F16 ’ F16 , (x1 , . . . , x16 ) ’ (SRD (x1 ), . . . , SRD (x16 ))

mit
Ax ’1 + t für x = 0
SRD : F ’ F , x ’ ,
für x = 0
t

wobei
⎞ ⎞
⎛ ⎛
1 1 1 1 1 0 0 0 0
0⎟ ⎟
⎜0 ⎜
1 1 1 1 1 0 1
⎟ ⎟
⎜ ⎜
0⎟ ⎟
⎜0 ⎜
0 1 1 1 1 1 1
⎟ ⎟
⎜ ⎜
1⎟ ⎟
⎜0 ⎜
0 0 1 1 1 1 0
⎟ ∈ GL(8, Z2 ), ⎟ ∈ F.
A=⎜ t=⎜
1⎟ ⎟
⎜1 ⎜
0 0 0 1 1 1 0
⎟ ⎟
⎜ ⎜
1⎟ ⎟
⎜1 ⎜
1 0 0 0 1 1 0
⎟ ⎟
⎜ ⎜
1⎠ ⎠
⎝1 ⎝
1 1 0 0 0 1 1
1 1 1 1 0 0 0 1 1

Dabei wird das Element x = a7 ±7 + a6 ±6 + · · · + a1 ± + a0 ∈ F als Spaltenvektor
(a7 , . . . , a1 , a0 )T aufgefasst.
Die Abbildung subByte ist die einzige nicht-lineare Abbildung in jeder Runde.
Die af¬ne Transformation x ’ Ax + t dient der Verkomplizierung der algebrai-
schen Struktur der sehr einfachen Abbildung x ’ x ’1 . Sie tr¤gt nichts zur Nicht-
linearit¤t bei. Aber sie bewirkt z. B., dass subByte keine Fixpunkte hat.
3.2 AES 49

Shift-Rows ist eine Abbildung
⎛ ⎞ ⎛ ⎞
x1 x5 x9 x13 x1 x5 x9 x13
⎜x x14 ⎟ ⎜ x2 ⎟
x6 x10 ⎟ ’ ⎜ x6 x10 x14
’ F4—4 , ⎜ 2 ⎟.
F4—4 ⎝ x3 x15 ⎠ ⎝ x11 x7 ⎠
x7 x11 x15 x3
x4 x8 x12 x16 x16 x4 x8 x12

Das Wort x1 , . . . , x16 wird spaltenweise in eine 4 — 4 Matrix eingetragen. Die Ab-
bildung besteht darin, die Zeilen zyklisch zu verschieben (daher der Begriff shift).
Man beachte, dass auch diese Abbildung komplette Bytes verschiebt. Es wird also
nur Diffusion auf Byte-Ebene erreicht, das allerdings sehr wirkungsvoll.
Wirkliche Diffusion wird nur in Kombination mit dem folgenden Schritt erzielt.
Mix-Columns benutzt den Ring R = F[X]/(X 4 + 1) aus dem Beispiel von Sei-
te 43. Wir fassen je vier Bytes “ genauer jede Spalte der eben beschriebenen Matrix
“ zu einem Element in R zusammen, z. B. die erste Spalte:

(x1 , x2 , x3 , x4 )T ’ y1 = x1 X 3 + x2 X 2 + x3 X + x4 ∈ R .


x1 x5 x9 x13
⎜ x x6 x10 x14 ⎟

Die Matrix ⎜ 2
⎝ x3 x7 x11 x15 ⎠ hat dann die Form (y1 , y2 , y3 , y4 ) ∈ R .
4

x4 x8 x12 x16
Mit dem aus dem Beispiel auf Seite 43 bekannten Polynom

c(X) = 03X 3 + X 2 + X + 02 ∈ R

setzt man

Mix-Columns : R4 ’ R4 ; (y1 , y2 , y3 , y4 ) ’ (c · y1 , c · y2 , c · y3 , c · y4 ) .

Das Element c ist invertierbar in R mit Inversem c’1 = 0BX 3 + 0DX 2 + 09X + 0E
wie schon im Beispiel auf Seite 43 erw¤hnt.
Die Abbildung Mix-Columns sorgt in Kombination mit Shift-Rows für Diffusion
auf Bit-Ebene.
In der Tat werden nach [8, 3.5] nur wenige Runden benötigt, um eine sehr gute
Diffusion zu erzielen.
Add-Round-Key addiert schließlich den Rundenschlüssel k i in der i-ten Runde

Add-Round-Key : F16 — F16 ’ F16 , (x, k i ) ’ x + k i .

Insgesamt gilt also

(x, k i ) = Add-Round-Key Mix-Columns Shift-Rows(subByte(x)) , k i
= Mix-Columns Shift-Rows(subByte(x)) + k i .
50 3 Block-Chiffren “ AES und DES

Für die Endrunde gilt

˜ (x, k N ) = Add-Round-Key Shift-Rows subByte(x) , k N .
= Shift-Rows subByte(x) + k N .

Der Schritt Mix-Columns wird in der letzten Runde weggelassen, weil er ohne
Kenntnis des Schlüssels rückg¤ngig gemacht werden kann.
Man beachte, dass jede einzelne Funktion in jeder Runde invertierbar ist, sodass
also letztlich die Verschlüsselungsfunktion f k : P ’ C eine Bijektion ist und die
Entschlüsselungsfunktion gk existiert. Das Entschlüsseln erfolgt, indem die Run-
den mit den jeweiligen Inversen der oben de¬nierten Abbildungen rückw¤rts
durchlaufen werden. In [8, 3.7] wird darüber hinaus eine Alternative beschrie-
ben, die etwas leichter implementiert werden kann.


3.2.7 Rijndael

Das AES-Verfahren wurde von J. Daemen und V. Rijmen entwickelt und unter
dem Namen Rijndael veröffentlicht.
Das ursprüngliche Rijndael-Verfahren ist allgemeiner als das AES-Verfahren. Für
das Rijndael-Verfahren wurden mehrere mögliche Blockl¤ngen, n¤mlich alle Viel-
fachen von 16 zwischen 128 und 256 Bit vorgeschlagen. Da aber die Vorgaben bei
der Auswahl von AES sehr strikt waren, wurde nur die Rijndael-Varianten mit
den oben angegebenen Parametern ins Rennen geschickt; und es wurden auch
nur diese von der Kommission beurteilt.
Ausschlaggebend für die Wahl von AES waren am Ende die enorme Performance
und Flexibilit¤t des Rijndael-Verfahrens, so wurde AES etwa auch gegenüber dem
System Serpent bevorzugt, obwohl dessen Sicherheitsniveau höher eingesch¤tzt
wurde. Rijndael, und damit AES, bietet ef¬ziente Ver- und Entschlüsselung auf
8 Bit Architekturen, wie sie z. B. in Smartcards zum Einsatz kommen bis hin zu
schnellen 64 Bit Parallelrechnern. In dieser Hinsicht war es allen anderen Vor-
schl¤gen überlegen.


3.3 Feistel-Chiffren *
Bereits Mitte der sechziger Jahre wurde deutlich, dass beim Einsatz elektroni-
scher Rechenanlagen Sicherheitsprobleme bezüglich der Vertraulichkeit und Au-
thentizit¤t auftreten. Bald wurde klar, dass man diese Probleme am besten mit
den Methoden der Kryptogra¬e lösen kann.
Andererseits wusste man, dass die klassischen Verfahren selbst bei sehr großen
Schlüssell¤ngen keine ausreichende Sicherheit erzielen konnten. Außerdem schei-
tern sie bereits bei Known-Plain-Text-Angriffen. Bereits Shannon hatte wichtige
Kriterien aufgestellt, wie wir sie in Abschnitt 3.2.2 dargestellt haben.
3.3 Feistel-Chiffren * 51

Ende der sechziger Jahre wurde im Rahmen des Lucifer-Programms der Firma IBM
unter der Leitung von Horst Feistel und Walter Tuchman nach Alternativen ge-
sucht. Ein Ergebnis dieses Programms sind die Feistel-Chiffren. Wir werden die
Struktur der Feistel-Chiffren am Beispiel des DES vorstellen.
Viele bekannte Block-Chiffren haben diese Grundstruktur. Drei der fünf Vorschl¤-
ge, die es in die Endrunde für AES geschafft haben, sind Feistel-Chiffren.

3.3.1 Die Struktur der Feistel-Chiffren

Den Ausgangspunkt für eine Feistel-Chiffre bilden:
eine Block-Chiffre B = (Z2 , Z2 , K, f , g), n ∈ N, mit einer geeigneten
n n

Schlüsselmenge K,
N ∈ N,

• eine Schlüsselmenge K und
eine injektive Abbildung ¦ : K ’ K N .

Die N-Runden Feistel-Chiffre F über B ist dann de¬niert durch

F = (Z2n , Z2n , K, f˜, g) ,
˜
2 2

wobei f˜ im Folgenden de¬niert wird: Zu k ∈ K setzen wir ¦(k) := (k1 , . . . , k N )
und erhalten wie schon beim AES die Rundenschlüssel k1 , . . . , k N ∈ K.
Jeden Block x ∈ Z2n schreiben wir als x = (L0 , R0 ) mit L0 , R0 ∈ Z2 . Es ist also L0
n
2
die linke H¤lfte und R0 die rechte H¤lfte, des Wortes x. Wir setzen jetzt rekursiv

(Li , Ri ) := (Ri’1 , Li’1 + f (Ri’1 , k i )), i ∈ {1, . . . , N},

und schließlich
f˜ : Z2n — K ’ Z2n , (x, k) ’ (R N , L N ) .
2 2

Aus der De¬nition ist unmittelbar klar, dass gilt

(Ri’1 , Li’1 ) = (Li , Ri + f (Li , k i )), i ∈ {1, . . . , N} .

Daher ist die Abbildung f˜k umkehrbar. Um die Umkehrung für ein y auszurech-
nen, benutzt man dieselbe Rekursion, aber mit dem Schlüsseltupel (k N , . . . , k1 ).
Man benutzt also die Rundenschlüssel in umgekehrter Reihenfolge.
Die der Feistel-Chiffre zugrunde liegende Block-Chiffre B nennt man die interne
Block-Chiffre. Die Sicherheit von F h¤ngt entscheidend von der Wahl von B ab.


3.3.2 DES
Der Data Encryption Standard (kurz DES) ist eine 16 Runden Feistel-Chiffre auf
Z64 mit K = Z56 . Eine Besonderheit ist die initiale Permutation IP. Sie wird vor
2 2
52 3 Block-Chiffren “ AES und DES

Beginn der ersten Runde auf das Klartextwort angewendet. Am Schluss, nach-
dem alle Runden durchlaufen sind, wird die inverse Permutation IP’1 ange-
wendet und das Ergebnis ausgegeben. Da IP fest gew¤hlt ist und vor der ersten
Schlüsseladditon angewendet wird, hat IP keine kryptogra¬sche Bedeutung. Die
Permutation IP verlangsamt Software-Implementierungen von DES im Vergleich
zu Hardware-Implementierungen. Dadurch werden die Kosten für möglicher-
weise erfolgreiche Angriffe erhöht. Das ist wohl der eigentliche Grund für diese
Besonderheit. Mit heutigen Rechnern spielt das keine große Rolle mehr.
Als interne Block-Chiffre w¤hlt man beim DES das Kryptosystem

B = (Z32 , Z32 , Z48 , f , g) mit f (x, k) = π S E(x) + k .
2 2 2

Dabei sind die Abbildungen E, S und π wie folgt de¬niert:

Expansion ist eine Abbildung E : Z32 ’ Z48 . Die Vorschrift wird oft durch eine
2 2
Tabelle beschrieben. Die Tabelle wird zeilenweise ausgelesen, zuerst wird das 32-
te Bit, dann das erste, das zweite usw. ausgegeben:

32 1 2 3 4 5
4 5 6 7 8 9
8 9 10 11 12 13
12 13 14 15 16 17
16 17 18 19 20 21
20 21 22 23 24 25
24 25 26 27 28 29
28 29 30 31 32 1

Die Bits 4 und 4 + 1 werden also doppelt eingetragen, sodass aus 32 Eingangs-
bits dann 48 Ausgangsbits werden.

S-Box ist eine nicht-lineare Abbildung

S : (Z6 )8 ’ (Z4 )8 ; (x1 , . . . , x8 ) ’ (S1 (x1 ), . . . , S8 (x8 )).
2
2

Dabei gilt natürlich xi ∈ Z6 . Die Abbildungen Si : Z6 ’ Z4 wurden ursprüng-
2
2 2
lich als S-Boxen bezeichnet. Sie sind durch Tabellen beschrieben. Bei der Veröf-
fentlichung wurden sie zwar angegeben, aber nicht motiviert. Experimente zeig-
ten sp¤ter, dass sich bei Ver¤nderungen der S-Boxen die Anf¤lligkeit des Verfah-
rens für die differentielle Kryptoanalyse erhöhte. So stellte sich zwar heraus, dass
die S-Boxen gut gew¤hlt waren, aber es wurde nicht klar, warum man sie so ge-
w¤hlt hat und auch nicht, wie man sie gefunden hat.
Wir geben exemplarisch die übliche Beschreibung der ersten S-Box S1 als Tabelle
an. Wenn b1 b2 b3 b4 b5 b6 das Eingangwort ist, so ¬ndet man das Ausgangswort als
Bin¤rdarstellung der Zahl aus der Zeile b1 b6 und der Spalte b2 b3 b4 b5 als Bin¤rzahl
gelesen.
3.4 Betriebsmodi * 53

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
00 14 4 13 1 2 15 11 8 3 10 6 12 5 9 0 7
01 0 15 7 4 14 2 13 1 10 6 12 11 9 5 3 8
10 4 1 14 8 13 6 2 11 15 12 9 7 3 10 5 0
11 15 12 8 2 4 9 1 7 5 11 3 14 10 0 6 13

Beispiel
Es sei b1 b2 b3 b4 b5 b6 = 011011. Wegen b1 b6 ist die Zeile 01 und wegen b2 b3 b4 b5 =
1101 die Spalte 13 = (1101)2 (im Dualsystem) zu betrachten. Am Schnittpunkt
dieser Zeile und Spalte steht die Zahl 5. Wegen 5 = (0101)2 gilt somit

x = 011011 ’ S1 (x) = 0101 .

Permutation vertauscht die Reihenfolge der Bits eines Wortes

π : Z32 ’ Z32 , (x1 , . . . , x32 ) ’ (xπ (1) , . . . , xπ (32) )
2 2

mit einer Permutation π auf der Menge {1, . . . , 32}, die ebenfalls durch eine
Tabelle gegeben ist.
16 7 20 21 29 12 28 17 1 15 23 26 5 18 31 10
2 8 24 14 32 27 3 9 19 13 30 6 22 11 4 25
Die Permutation π lautet in der aus der linearen Algebra vertrauten Zyklen-
Darstellung

= (1, 16, 10, 15, 31, 4, 21, 32, 25, 19, 24, 9)
π
(2, 7, 28, 6, 12, 26, 13, 5, 29, 22, 27, 30, 11, 23, 3, 20, 14, 18, 8, 17) .
Es gilt also
π(x1 · · · x32 ) = x16 x7 x20 x21 · · · x4 x25 .
Das bedeutet, dass das 16. Bit an die 1. Stelle wandert, das 10. an die 16. Stelle
usw., bis schließlich das 25. an die letzte Stelle geht.
Diese Abbildung soll die Output-Bits einer S-Box in der folgenden Runde auf
mehrere S-Boxen verteilen.

3.4 Betriebsmodi *
In vielen Anwendungen ist der Klartext sehr lang, im Allgemeinen sehr viel l¤n-
ger als die Blockl¤nge n der Chiffre. Es müssen somit viele Blöcke mit demselben
Schlüssel chiffriert werden.
In diesem kurzen Abschnitt beschreiben wir die vier gebr¤uchlichsten Verfahren.
Sie wurden kurz nach der Einführung von DES standardisiert.
Es sei eine Block-Chiffre (P, C, K, f , g) der Blockl¤nge n gegeben.
Für alle Unterabschnitte wird der Klartext N in Blöcke xi der L¤nge n eingeteilt,
also N = (x1 , . . . , xr ) mit r ∈ N und xi ∈ P.
Da die L¤nge von x im Allgemeinen kein Vielfaches von n ist, muss der letzte
Block xr evtl. durch Padding aufgefüllt werden.
54 3 Block-Chiffren “ AES und DES

3.4.1 Electronic Codebook Mode “ ECB
Beim ECB-Modus wird einfach jeder Block für sich verschlüsselt. Es gilt also
C = (c1 , . . . , cr ) := ( f (x1 , k), . . . , f (xr , k)) .
Dieses Verfahren kann man als eine Substitutions-Chiffre mit riesigem Alphabet
P auffassen. Daher werden Strukturen aus dem Klartext im Geheimtext sicht-
bar und erleichtern unter Umst¤nden die Kryptoanalyse. Die übliche statistische
Analyse, wie sie in Kapitel 1 beschrieben wurde, wird einzig durch die Größe des
Alphabets “ durchaus erheblich “ erschwert.
Der ECB-Modus eröffnet einem Angreifer weitere Manipulationsmöglichkeiten,
auch wenn er den Geheimtext nicht entschlüsseln kann. Durch die Ver¤nderung
einzelner Blöcke des Geheimtexts kann ein Angreifer etwa gezielt einen Block des
Geheimtexts ver¤ndern, obwohl er nicht genau weiß, was er tut.
Statt einer blinden „nderung kann er versuchen, einen ihm bekannten Geheim-
textblock einzufügen oder vorhandene Blöcke durch solche zu ersetzen “ im Sin-
ne eines Known-Plain-Text-Angriffs. Schließlich ist es möglich, Blöcke zu vertau-
schen. All dies ist nur dann eine Bedrohung, wenn es unbemerkt bleibt. Zwei der
anderen Betriebsmodi haben zum Ziel, genau das zu verhindern, n¤mlich, dass
eine Manipulation nicht wahrgenommen wird.
Bemerkung
Der ECB-Modus kann auch bei Verfahren angewendet werden, bei denen der
Geheimtext eine andere Blockl¤nge hat als der Klartext.

3.4.2 Cipher Block Chaining Mode “ CBC
Der CBC-Modus enth¤lt eine Art Rückkopplung bei der Verschlüsselung, die
Manipulationen an Blöcken im Geheimtext aufdeckt. Vor der Verschlüsselung ei-
nes Blocks wird der eben verschlüsselte Block addiert. Beim ersten Block wird ein
beliebiger Initialisierungsblock c0 ∈ C benutzt. Formal sieht das wie folgt aus:
ci := f (xi + ci’1 , k) für i ∈ {1, . . . , r} .
Bei der Entschlüsselung rechnet man
mi := ci’1 + g(ci , k) für i ∈ {1, . . . , r} .
Man veri¬ziert mühelos, dass dadurch der Geheimtext entschlüsselt wird, d. h.,
es gilt mi = xi .
Verschiedene Initialisierungsblöcke liefern verschiedene Geheimtexte. Wichtiger
ist, dass im Allgemeinen gleiche Klartextblöcke verschieden verschlüsselt wer-
den, sodass statistische Angriffe erschwert werden. Ver¤nderungen im Geheim-
text, wie das Einfügen oder Ersetzen von Geheimtextblöcken, zerstören im All-
gemeinen den folgenden Block und können dadurch entdeckt werden. Anderer-
seits zerstören Übertragungsfehler höchsten den folgenden Block, der Rest kann
fehlerfrei entschlüsselt werden.
3.4 Betriebsmodi * 55

Wenn es nicht auf jeden Block ankommt, können sogar verschiedene Initialisie-

<< . .

. 7
( : 33)



. . >>