DES

Binärcodes

Auf einem Rechner werden alle Daten als Bit-Folgen dargestellt (binär codiert). Der Data Encryption Standard (DES) verschlüsselt solche Bit-Folgen.

Eine der gebräuchlichsten Binärcodierungen ist ASCII (American Standard Code for Information Interchange). Im ASCII wird je ein Zeichen durch ein Byte (= 8 Bits) codiert.

Exercise 1: ASCII

Wie viele verschiedene Zeichen können mit ASCII codiert werden?

Solution

$2^8=256$

Der Data Encryption Standard (DES) verschlüsselt solche Bit-Folgen. Folgende Abbildung zeigt einen kleinen Auszug aus ASCII.

Exercise 2: Binäre Fingerübung

Verwandle folgendes Binärwort zurück:

01100110 01100101 01101001 01110011 1110100 01100101 01101100

Solution

feistel

Bei ASCII stellen wir fest, dass ein so codierter Text sich nun allerdings 8-mal so lang darstellt wie der ursprüngliche (uncodierte) Text. Man kann ihn kürzer darstellen, wenn man für je vier Bits eine Hexadezimalziffer schreibt. Denn vier Bits stellen genau die Zahlen von 0 bis 15 dar:

Der Deutsche Horst Feistel wurde am 30. Januar 1915 in Berlin geboren. 1934 emigrierte er nach Amerika. Wegen seiner kryptographischen Forschungen legte ihm die NSA (National Security Agency) immer wieder Steine in den Weg. Bei IBM in New York entwickelte er schliesslich in den siebziger Jahren das Prinzip der Feistel-Netzwerke, Grundlage einiger bedeutender Verschlüsselungsverfahren. Feistel starb 1990.

\begin{align*} 0000 &= 0\\ 0001 &= 1\\ 0010 &= 2\\ 0011 &= 3\\ \dots\\ 1101 &= 13\\ 1110 &= 14\\ 1111 &= 15 \end{align*}

Man verwendet dafür die Ziffern

0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F.

Um die unübersichtlichen Bit-Folgen eines ASCII-codierten Textes kürzer zu schreiben, stellt man jedes Byte durch zwei Hex-Ziffern dar, eine für die ersten und eine für die letzten vier Bits. Folgende Abbildung zeigt noch einmal den Ausschnitt aus ASCII. Für die hexadezimale Schreibweise benätigt man statt 8 nur zwei Ziffern.

Exercise 3: Hex zu Bin

Kannst du folgendes binärcodiertes, mit Hex-Ziffern dargestelltes Wort zurückwandeln?

6C 75 63 69 66 65 72

Solution

lucifer

Lucifer ist der Name eines Verschlüsselungsverfahrens, das Horst Feistel und Don Coppersmith 1973 im Thomas J. Watson Laboratory von IBM in New York entwickelten. Die NSA (National Security Agency) wurde gebeten, die Sicherheit der Lucifer-Verschlüsselung zu beurteilen. Die NSA scheint von der Sicherheit Lucifers beeindruckt gewesen zu sein: Sie bestand darauf, die Zahl der Schlüssel zu begrenzen (das Verfahren also künstlich unsicherer zu machen).

"Offenbar glaubte die NSA, eine solche Obergrenze würde im zivilen Gebrauch die Sicherheit gewährleisten, weil keine nichtmilitärische Organisation einen Computer besass, der leistungsfähig genug war, um jeden möglichen Schlüssel in einem vernünftigen Zeitraum zu prüfen. Die NSA selbst jedoch, die über die besten Computer der Welt verfügt, würde gerade noch in der Lage sein, in den verschlüsselten Nachrichtenverkehr einzubrechen." (aus: Simon Singh, Geheime Botschaften)

Eine Version von Lucifer mit beschränkter Schlüsselzahl wurde 1976 unter dem Namen Data Encryption Standard (DES) der offizielle amerikanische Verschlüsselungsstandard.

Dez	Hex	Okt	Zeichen	Dez	Hex	Okt	Zeichen
0	0x00	000	NUL	32	0x20	040	SP
1	0x01	001	SOH	33	0x21	041	!
2	0x02	002	STX	34	0x22	042	"
3	0x03	003	ETX	35	0x23	043	#
4	0x04	004	EOT	36	0x24	044	$
5	0x05	005	ENQ	37	0x25	045	%
6	0x06	006	ACK	38	0x26	046	&
7	0x07	007	BEL	39	0x27	047	'
8	0x08	010	BS	40	0x28	050	(
9	0x09	011	TAB	41	0x29	051	)
10	0x0A	012	LF	42	0x2A	052	*
11	0x0B	013	VT	43	0x2B	053	+
12	0x0C	014	FF	44	0x2C	054	,
13	0x0D	015	CR	45	0x2D	055	-
14	0x0E	016	SO	46	0x2E	056	.
15	0x0F	017	SI	47	0x2F	057	/
16	0x10	020	DLE	48	0x30	060	0
17	0x11	021	DC1	49	0x31	061	1
18	0x12	022	DC2	50	0x32	062	2
19	0x13	023	DC3	51	0x33	063	3
-----	------	-----	---------	-----	------	-----	---------
20	0x14	024	DC4	52	0x34	064	4
21	0x15	025	NAK	53	0x35	065	5
22	0x16	026	SYN	54	0x36	066	6
23	0x17	027	ETB	55	0x37	067	7
24	0x18	030	CAN	56	0x38	070	8
25	0x19	031	EM	57	0x39	071	9
26	0x1A	032	SUB	58	0x3A	072	:
27	0x1B	033	ESC	59	0x3B	073	;
28	0x1C	034	FS	60	0x3C	074	<
29	0x1D	035	GS	61	0x3D	075	=
30	0x1E	036	RS	62	0x3E	076	>
31	0x1F	037	US	63	0x3F	077	?
-----	------	-----	---------	-----	------	-----	---------
64	0x40	100	@	96	0x60	140	`
65	0x41	101	A	97	0x61	141	a
66	0x42	102	B	98	0x62	142	b
67	0x43	103	C	99	0x63	143	c
68	0x44	104	D	100	0x64	144	d
69	0x45	105	E	101	0x65	145	e
70	0x46	106	F	102	0x66	146	f
71	0x47	107	G	103	0x67	147	g
72	0x48	110	H	104	0x68	150	h
73	0x49	111	I	105	0x69	151	i
74	0x4A	112	J	106	0x6A	152	j
75	0x4B	113	K	107	0x6B	153	k
76	0x4C	114	L	108	0x6C	154	l
77	0x4D	115	M	109	0x6D	155	m
78	0x4E	116	N	110	0x6E	156	n
79	0x4F	117	O	111	0x6F	157	o
80	0x50	120	P	112	0x70	160	p
81	0x51	121	Q	113	0x71	161	q
82	0x52	122	R	114	0x72	162	r
83	0x53	123	S	115	0x73	163	s
84	0x54	124	T	116	0x74	164	t
85	0x55	125	U	117	0x75	165	u
86	0x56	126	V	118	0x76	166	v
87	0x57	127	W	119	0x77	167	w
88	0x58	130	X	120	0x78	170	x
89	0x59	131	Y	121	0x79	171	y
90	0x5A	132	Z	122	0x7A	172	z
91	0x5B	133	[	123	0x7B	173	{
92	0x5C	134	\	124	0x7C	174
93	0x5D	135	]	125	0x7D	175

Erste DES Schicht

DES ist eine Block-Chiffre. Bei einer Block-Chiffre wird zum Verschlüsseln einer Nachricht diese in mehrere Blöcke gleicher Länge aufgeteilt. Jeder Block wird nach dem gleichen Prinzip verschlüsselt. Beim DES ist die Länge der Blöcke 64 Bits = 8 Bytes. Für die Sicherheit einer Block-Chiffre ist eine relativ grosse Blocklänge notwendig. Enthält der letzte Block der zu verschlüsselnden Nachricht weniger als 64 Bit, so füllt man ihn mit irgendwelchen Dummy-Bits auf.Wir haben z.B. vorhin den ASCII-Code für das Leerzeichen verwendet (00100000). Beim Verschlüsseln von Bit-Folgen im DES verwendet man verschiedene Standard-Operationen, die wir jetzt behandeln. DES arbeitet mit Blöcken von je 64 Bits = 8 Bytes. Um den Überblick nicht zu verlieren, nehmen wir hier aber immer nur 1 Byte.

Die XOR-Operation verknüpft zwei Bits nach folgenden Regeln:

0 \text{XOR} 0 = 0, 0 \text{XOR} 1 = 1, 1 \text{XOR} 0 = 1, 1 \text{XOR} 1 = 0

oder kurz:

XOR	0	1
0	0	1
1	1	0

Bei zwei Bit-Folgen gleicher Länge wendet man XOR auf jede Position einzeln an. Das Ergebnis ist wieder eine Bit-Folge.

Exercise 4: XOR

Bestimme das Ergebnis der XOR-Operation.

01000101\oplus00110011

Solution

$01110110$

Eine andere wichtige Manipulation von Bit-Folgen ist, die Positionen der einzelnen Bits zu vertauschen. Eine Permutation wird einfach durch Aufzählen der neuen Positionen angegeben: Dies ist die Permutation

( \;2\; 3\; 1\; 8\; 5\; 4\; 6\; 7\; )

Example 1

Die 8-Bit-Folge

1 0 0 1 1 0 1 0

wird abgebildet auf

0 1 0 0 1 1 0 1

Exercise 5: Permutation

Gib die durch $(\;4\; 5\; 2\; 3\; 1\; 6\; 8\; 7\;)$ permutierte Folge von $10010100$ an.

Solution

$10001100$

Der DES verwendet insgesamt drei verschiedene Permutationen, welche mit IP, PI und P bezeichnet werden. IP und PI permutieren 64-Bit-Folgen, P permutiert 32-Bit-Folgen. Ausserdem verwendet DES noch Varianten von Permutationen (E, PC1, PC2), die wir später besprechen werden.

Wie eine Zwiebel ist der DES aus mehreren Schichten aufgebaut. Wir schauen uns die erste Schicht jetzt an:

DES besteht aus einer Anfangsphase, einer mittleren Phase mit 16 Runden (Nummer 0 bis 15) und einer Endphase.
Die Anfangsphase besteht aus einer Permutation der gesamten Folge.
In den Runden werden linke und rechte Hälfte der Bit-Folge getrennt behandelt.

Jede Runde besteht aus einer Vertauschung von linker und rechter Hälfte, einer Manipulation der rechten Hälfte im F-Modul und einer XOR-Operation der manipulierten rechten mit der linken Hälfte.

Jede Runde verwendet ihren eigenen Schlüssel.

Die mittlere Phase wird mit einer Vertauschung von linker und rechter Hälfte abgeschlossen.
Die Endphase besteht aus einer abschliessenden Permutation der gesamten Folge.

Wie entschlüsselt man eine DES-verschlüsselte Nachricht? Das kann man herausbekommen, ohne das F-Modul näher zu kennen. Man muss dazu aber wissen, wie man Permutationen und XOR-Operationen rückgängig macht.

Zuerst kümmern wir uns um Permutationen. Ist b eine Bit-Folge und P eine Permutation, so bezeichnet P(b) die Bit-Folge, die aus b durch Anwendung der Permutation P entsteht.

Definition 1

Die Permutation $P_2$ heisst Inverse zur Permutation $P_1$ , wenn für jede Bit-Folge $b$ gilt:

P_2(P_1(b)) = b.

Wendet man also nach einer Permutation ihre Inverse an, so bleiben alle Positionen unverändert.

Example 2

Es sei

P_1 = ( \;2\; 3\; 1\; 8\; 5\; 4\; 6\; 7\;).

Dann ist

P_2 = ( \;3\; 1\; 2\; 6\; 5\; 7\; 8\; 4\;)

die Inverse von $P_1$ , denn $P_2$ nach $P_1$ angewendet lässt alle Positionen unverändert.

Exercise 6: Inverse Permutation

Gib die Inverse der Permutation

(\;1\;2\;6\;7\;4\;5\;8\;3\;)

Solution

$P_2=(1\quad2\quad8\quad5\quad6\quad3\quad4\quad7)$

Im DES ist die End-Permutation PI die Inverse zur Anfangspermutation IP.

Und jetzt kümmern wir uns darum, wie man die XOR-Operation rückgängig macht. Wie rekonstruiert man b1 aus b2 XOR b1 und b2?

Exercise 7: Inverse XOR

Angenommen, man kennt

b_2=11101001

und

b_2\oplus b_1=10111010

Bestimme $b_1$ .

Solution

$b_1=(b_2\oplus b_2)\oplus b_1=b_2\oplus(b_2\oplus b_1)=01010011$

Aus der Übung erkennen wir: $b_1$ ergibt sich aus $b_2$ und $b_2\oplus b_1$ durch eine weitere XOR-Operation:

b_1=b_2\oplus(b_2\oplus b_1)

Zum Verschlüsseln verwendet DES insgesamt 16 Schlüssel, je einen pro Runde.

Nach dieser Vorbereitung sollte das Entschlüsseln auch gelingen, wenn mehrere Runden durchgeführt werden. Eventuell hilft auch die formale algorithmische Beschreibung weiter.

$r(b)$ bezeichnet die rechte Hälfte einer 64-Bit-Folge $b$ ,
$l(b)$ bezeichnet die linke Hälfte,
$b_1b_2$ bezeichnet das Aneinanderhängen zweier Bit-Folgen $b_1$ und $b_2$ .

Die Zuordnung

b := r(b)l(b)

beschreibt also das Vertauschen von linker und rechter Hälfte.

Mit $F(b,i)$ bezeichnen wir das Ergebnis des F-Moduls bei Anwendung auf die 32-Bit-Folge $b$ in Runde $i$ .

input: 64-Bit-Folge b 
output: DES-Verschluesselung

c := IP(b)   {Anfangspermutation}
fuer i = 0,1,...,15    {Runden}
    c1 := r(c)
    c2 := l(c) XOR F(c1,i)
    c := c1c2
c := r(c)l(c)   {abschliessende Vertauschung}
c := PI(c)  {Endpermutation}

F-Modul und S-Module

Eine Verschlüsselung ist dann besonders gut, wenn jedes Bit des Schlüssels und jedes Bit des Originaltextes "gleich starken" Einfluss auf jedes Bit des Ergebnisses haben. Dafür sorgt im DES der 16-fache Einsatz des F-Moduls, die zweite Schicht der DES-Zwiebel.

Wir untersuchen jetzt die Funktionsweise des F-Moduls. Es führt folgende Operationen aus:

Erweiternde Permutation der 32-Bit-Folge auf eine 48-Bit-Folge.
XOR-Operation mit einem 48-Bit-Schlüssel
Reduktion von je 6 Bit auf 4 Bit mit Hilfe der S-Module S1 bis S8.
Abschliessende Permutation.

Eine erweiternde Permutation bildet Bit-Folgen $b_1$ auf Bit-Folgen $b_2$ grösserer Länge ab. Im Gegensatz zu gewöhnlichen Permutationen werden nun einige Positionen in $b_1$ auf mehrere Positionen in $b_2$ abgebildet. Zur Notation

Example 3

Dies ist die erweiternde Permutation

(\; 1,3\; 2\; 4,6\; 5\; ).

Die 4-Bit-Folge

1001

wird damit abgebildet auf

101010.

Die im F-Modul verwendete erweiternde Permutation E ist in der Tabelle ebenso angegeben wie die abschliessende Permutation P. Die S-Module bilden die dritte Schicht im DES. Sie verarbeiten 6-Bit-Folgen unter Verwendung von Substitutionen.

Definition 2: Substitution

Eine Substitution bildet jede Bit-Folge einer bestimmten Länge wieder auf eine Bit-Folge derselben Länge ab.

Substitutionen gibt man am Besten in Form einer Tabelle an:

Die Substitution ist fundamental verschieden von einer Permutation. Sie beruht nämlich nicht darauf, die Bits innerhalb der Bit-Folgen zu vertauschen.

Und so arbeiten die S-Module im DES:

Jedes S-Modul verwendet 4 verschiedene Substitutionen auf Bit-Folgen der Länge 4. Jede Zeile der Tabelle repräsentiert eine solche Substitution.
Verarbeitet werden 6-Bit-Folgen
Anfangs- und Endbit der 6-Bit-Folge bestimmen, welche Substitution angewendet wird.
Die mittleren 4 Bit werden mittels dieser Substitution auf eine 4-Bit-Folge abgebildet.

DES Schlüssel

DES lässt nur Schlüssel mit bestimmter Parität zu.

Definition 3: Parität

Ist die Zahl der Einsen in einer Bit-Folge ungerade, so ist die Parität der Bit-Folge 1, andernfalls ist die Parität 0.

Exercise 8: Parität

Gib die Parität der Bit-Folge $0010011$ an.

Solution

Parität 1

Im DES verwendet der Benutzer eine von ihm gewählte (geheime) 64-Bit-Folge als Schlüssel. Diese muss er dem Empfänger, der ja entschlüsseln soll, auch mitteilen. Aus Sicherheitsgründen sollte der Schlüssel selbst wieder verschlüsselt weitergegeben werden. Eine fehlerbehaftete Übertragung des Schlüssels sollte vom Empfänger erkannt werden können. Deshalb gibt es im DES die folgende Konvention:

Es sind nur Schlüssel zugelassen, bei welchen jedes Byte Parität 1 hat.

Exercise 9: Richtig oder falsch?

Was erreicht man damit? Sind die folgenden Aussagen richtig oder falsch?

a) Fehler von einem Bit pro Byte werden immer erkannt.

b) Fehler von einem Bit pro Byte werden nur manchmal erkannt.

c) Fehler von mehreren Bit pro Byte werden immer erkannt.

d) Fehler von mehreren Bit pro Byte werden nur manchmal erkannt.

e) Fehler von einem Bit pro Byte können korrigiert werden.

Solution

a) $\checkmark$ und d) $\checkmark$

DES erzeugt aus dem 64-Bit-Schlüssel sechzehn 48-Bit-Schlüssel unter Verwendung von Linksverschiebungen und verringernden Permutationen.

Definition 4

Die Permutation $(\;n\; 1\; 2\; \dots \;n-1\;)$ heisst Linksverschiebung um 1. Die Permutation $(\; n-1\; n\; 1\; 2\; \dots \;n-2\;)$ heisst Linksverschiebung um 2.

Definition 5

Eine vermindernde Permutation bildet Bit-Folgen $b_1$ auf Bit-Folgen $b_2$ kleinerer Länge ab. Im Gegensatz zu gewöhnlichen Permutationen werden nun einige Positionen in $b_1$ ignoriert.

Example 4

Eine vermindernde Permutation von 6 Bit auf 4 Bit ist

(\;-\;2\;1\;-\;4\;3\;)

Dadurch wird $101001$ auf $1010$ abgebildet.

Die im DES zur Schlüsselgenerierung verwendeten vermindernden Permutationen PC1 und PC2 sind in der Tabelle angegeben. PC1 bildet 64-Bit-Folgen auf 56-Bit-Folgen ab, PC2 bildet 56-Bit-Folgen auf 48-Bit-Folgen ab.

Sicherheit

Welche Bausteine des DES tragen wie zu dessen Sicherheit bei? Diese Frage wollen wir hier in ganz groben Zügen beantworten.

Bei einem statistischen Angriff versucht man, aus der Häufigkeit von Mustern in der verschlüsselten Nachricht auf den entschlüsselten Text zu schliessen. Es macht solche Angriffe aufgrund der grossen Blockgrösse von 64 Bit praktisch unmöglich.

Bedeutung der Blocklänge

Stelle dir vor, eine Nachricht wird in ASCII codiert. Auf die resultierende Bit-Folge wird eine Block-Chiffre mit nur der Länge 8 angewendet. Diese Nachricht kannst du dann so knacken:

Du teilst die verschlüsselte Nachricht in Blöcke zu je 8 Bit ein.
Du erstellst eine Tabelle, in welcher gezählt wird, wie häufig jede der 256 möglichen 8-Bit-Folgen vorkommt.
Die Tabelle vergleichst Du mit den durchschnittlichen Häufigkeiten der Buchstaben und Zeichen in deutschen Texten.
Die häufigste 8-Bit-Folge entspricht dann wohl dem 'e', die zweithäufigste dem 'n' usw.
Nach etwas Ausprobieren bist du am Ziel.

Exercise 10: Block lang genug?

Warum kann eine Blocklänge von 64 als sicher gegen statistische Angriffe angesehen werden? Welche Aussagen sind richtig?

a) 64 Bit entsprechen 8 ASCII-codierten Zeichen

b) Es gibt $256^8$ ( $\approx 2 \cdot 10^{19}$ ) verschiedene Bit-Folgen der Länge 64.

c) Kommt im unverschlüsselten Text ein Wort aus 8 Buchstaben (oder mehr) öfter vor, so wiederholt sich im verschlüsselten Text eine 64-Bit-Folge genauso oft.

d) Kommt im unverschlüsselten Text ein Wort aus 8 Buchstaben (oder mehr) öfter vor, so wiederholt sich auch im verschlüsselten Text eine 64-Bit-Folge, aber im Schnitt nur rund ein Achtel so oft.

e) Selbst wenn im verschlüsselten Text eine 64-Bit-Folge häufiger vorkommt, ist es sehr schwer, ihr das richtige Wort aus dem unverschlüsselten Text zuzuordnen.

f) Wenn ich eine 64-Bit-Folge im verschlüsselten Text geknackt habe, so kenne ich die 8 Zeichen des Wortes. Damit finde ich dann alle Stellen im verschlüsselten Text, die diesen 8 Zeichen entsprechen.

Solution

nur c) $\ding{55}$ ist falsch

Manche Chiffren sind leicht zu knacken, wenn man die Verschlüsselungen einiger weniger Blöcke kennt ('lineare' Chiffren). Dass dies im DES nicht möglich ist, wird durch die S-Module und die 16 Runden erreicht. Sie machen DES zu einer hochgradig nichtlinearen Chiffre. Eine Chiffre für Bit-Folgen der Länge $n$ heisst linear, falls sich die verschlüsselte Bit-Folge $b_2$ aus $b_1$ über eine Vorschrift

b_2 = \B{A} \cdot b_1 + \vec{c}

mit einer festen Matrix $\B{A}$ und einem festen Vektor $\vec{c}$ ergibt. Die arithmetischen Operationen sind dabei modulo 2 zu verstehen. Um das Konzept der linearen Chiffren zu verstehen, braucht man etwas mathematische Vorbildung. Bei einer linearen Chiffre reicht es, wenn man für einen Satz von $n+1$ Bit-Folgen, welche eine Basis enthalten, die jeweiligen verschlüsselten Folgen kennt. Daraus kann man nämlich $\B{A}$ vollständig rekonstruieren.

Zum Abschluss besprechen wir noch den wohl naheliegendsten Angriff. Man spricht von einem Brute-Force-Angriff auf eine Chiffre, wenn man einfach versucht, alle möglichen Schlüssel durchzuprobieren. Brute Force ist bis jetzt die erfolgreichste Angriffstaktik gegen DES.

Exercise 11: DES Schlüsselraum

Wie viele verschiedene Schlüssel gibt es im DES?

Solution

$2^{56}\approx10^{17}$

Nachdem schon PCs heutzutage um die $10^{10}$ Rechenoperationen in der Sekunde leisten können, ist es möglich, mit vielen PCs (und einige Tagen Rechenzeit) einen erfolgreichen Brute-Force-Angriff auf den DES zu fahren. Man behilft sich deshalb mit dem Triple DES.

Beim Triple DES wird zur Verschlüsselung der DES 3-fach hintereinander angewendet, und zwar zuerst mit einem ersten Schlüssel, dann mit einem zweiten und schliesslich nochmals mit dem ersten.

Exercise 12: Attack DES?

Wieviele Möglichkeiten muss man bei einem Brute-Force-Angriff jetzt in Betracht ziehen? Gib die richtige Grössenordnung an! (Exponent $e$ in $10^e$ )

Solution

ungefähr $10^{34}$

Exercise 13: Double-DES ist nicht double

Wieso nicht Double-DES?

Solution

Double DES ist auf einen Meet in the Middle Angriff ähnlich anfällig wie DES.

Tatsächlich ist Triple DES eine heute häufig verwendete Chiffre.

Exercise 14: Schwache Schlüssel

Das DES besitzt vier sog. "schwache Schlüssel". Dies sind 64-Bit-Schlüssel, aus denen DES bei der Erzeugung der sechzehn 48-Bit-Schlüssel sechzehn Mal denselben Schlüssel generiert. Finde die vier schwachen Schlüssel.

Hinweis: Alle Bytes der schwachen Schlüssel haben Parität 0. Es sind also eigentlich gar keine zugelassenen Schlüssel.

Solution

Für die vier Schlüssel $0101010101010101$ , $FEFEFEFEFEFEFEFE$ , $1F1F1F1F1F1F1F1F$ und $E0E0E0E0E0E0E0E0$ gilt $E_k(E_k(m))=m$

Exercise 15: Triple DES

Bei Triple DES werden der erste und der dritte Schlüssel identisch gewählt.

a) Welchen Grund mag diese Einschränkung haben?

b) In nicht zu ferner Zukunft schafft man es vielleicht, das für einen Brute-Force Angriff auf das gewöhnliche DES notwendige Ausprobieren aller Schlüssel in einer Stunde durchzuführen. Wie lange braucht man dann (in Jahren) für einen Brute-Force-Angriff auf Triple DES?

Solution

Die Schlüssel sollen nicht zu lang werden. Für einen Angriff braucht man immerhin noch $\frac{10^{17}}{24\cdot365}\approx11\cdot 10^{18}$

Exercise 16: Vermindernde Permutationen

Eine vermindernde Permutation führt zu einem Informationsverlust, da zwei unterschiedliche Bit-Folgen auf das selbe Ergebnis abgebildet werden können.

a) Gib für die vermindernde Permutation $(\;-\; 2\; 4\; 1\; 3\; -\;)$ zwei 6-Bit-Folgen an, die auf dasselbe Ergebnis abgebildet werden.

b) Ergibt sich diese Problematik auch bei erweiternden Permutationen?

c) Das DES ist nur sinnvoll, wenn verschiedene Bit-Folgen auch verschieden verschlüsselt werden (warum eigentlich?). Erläutere, warum dies tatsächlich so ist, obwohl im DES vermindernde Permutationen eingesetzt werden.

Solution

a) $100010$ zu $0010$ und $100011$ zu $0010$

b) $\ding{55}$ nein

c) Man könnte bei der Verschlüsselung die Änderung des Ciphertextes beobachten. Man muss nur zwei Klartexte mit fixer Differenz (im Sinne von XOR) wählen und dann entsprechend der Differenz der Chiffrentexte können den Schlüsseln verschiedene Wahrscheinlichkeiten zugeordnet werden. Bei genügend vielen Analysen wird sich ein Schlüssel als der wahrscheinlichste herauskristallisieren.

Die obigen Übungen stammen von der Site MathePrisma DES. Diese führt auch durch ein schönes Lernmodul.