Übungsblatt 2 - Arbeitsgruppe Kryptographie und Sicherheit

IKS
Institut für Kryptographie und Sicherheit
Jun.-Prof. Dr. D. Hofheinz
Institut für Kryptographie und Sicherheit
Stammvorlesung Sicherheit im Sommersemester 2013
Übungsblatt 2
Aufgabe 1. Wir wissen, dass die Blockchiffre (E, D) : {0, 1}8 × {0, 1}4 → {0, 1}4 bei Eingabe eines
festen Schlüssels K0 eine Eingabe M wie folgt auf eine Ausgabe C := E(K0 , M ) abbildet:
M
C
0000
1100
0001
1001
0010
1111
0011
0001
0100
0101
0101
0000
0110
0010
0111
0100
1000
1000
1001
1110
1010
1010
1011
0011
1100
1011
1101
1101
1110
0111
1111
0110
Verschlüsseln Sie die Klartexte M1 = 0100 1011 0100 0001 und M2 = 0100 1101 0100 0001 unter K0
in den Betriebsmodi Electronic Code Book (ECB), Cipher Block Chaining (CBC), Cipher Feedback
(CFB) und Output Feedback (OFB). Worauf sollte bei der Wahl eines Initialisierungsvektors IV in den
einzelnen Modi, falls vonnöten, geachtet werden? (Beispielsweise: Falls E ununterscheidbar von einer
Zufallsfunktion ist, wie sollte IV im CBC-Modus gewählt werden, um passive Sicherheit zu gewährleisten?)
Aufgabe 2. Betrachten wir die Entschlüsselung in den Betriebsmodi ECB, CBC, CFB und OFB.
N
(a) Sei i ∈
ein Index. Wie verhält sich die Entschlüsselung in den verschiedenen Modi, falls das
Chiffrat Ci durch Netzwerkfehler (beispielsweise in Form von Bitfehlern) verändert wurde?
(b) Welche Betriebsmodi-Entschlüsselungen lassen sich parallelisieren?
Aufgabe 3. Aus der Vorlesung ist bekannt, dass eine Blockchiffre im CBC-Modus IND-CPA-sicher ist,
wenn E : {0, 1}k × {0, 1}l → {0, 1}l , für k, l ∈ , ununterscheidbar von einer echt zufälligen Funktion ist
und der Initialisierungsvektor IV für jede Verschlüsselung neu gleichverteilt und zufällig gezogen wird.
Dies gilt allerdings nicht mehr, sobald IV fest und somit für jede Verschlüsselung gleich ist oder IV bei
jeder neuen Verschlüsselung um 1 schrittweise hochgezählt wird. Geben Sie für diese beiden Fälle jeweils
einen Angreifer an, der das IND-CPA-Spiel im ersten Fall für einen festen IV und im zweiten Fall für
einen inkrementierten IV mit Wahrscheinlichkeit 1 gewinnt.
N
Aufgabe 4. Wir erweitern unsere Blockchiffre-Definition aus der Vorlesung um eine zusätzliche Eingabe
T ∈ {0, 1}t mit t ∈ , die wir Tweak nennen. Sei ETWEAK , DTWEAK : {0, 1}k × {0, 1}t × {0, 1}l → {0, 1}l ,
k
für k, t, l ∈ . Weiterhin sei E, D : {0, 1} 2 × {0, 1}l → {0, 1}l eine “sichere” Blockchiffre (beispielsweise
AES) und PAD : {0, 1}∗ → {0, 1}l eine sogenannte Padding-Funktion, die Eingaben beliebiger aber fester
k
Länge deterministisch auf die Bitlänge l abbildet. Für einen Schlüssel K = (K1 , K2 ) ∈ ({0, 1} 2 )2 , einen
0
t
l
Index i ∈ , einen Tweak T := (T ||i) ∈ {0, 1} und einen Klartext M ∈ {0, 1} gelte
N
N
N
X := E(K2 , T 0 ),
ETWEAK (K, T, M ) := E(K1 , (M ⊕ PAD(X||i))) ⊕ PAD(X||i).
(Mit || bezeichnen wir die Konkatenation von (Bit-)Strings.) Die Entschlüsselung DTWEAK (K, T, M ) sei
entsprechend definiert, sodass immer DTWEAK (K, T, ETWEAK (K, T, M )) = M , für alle K, T, M , gilt. Ein
Betriebsmodus, der die oben gegebene Blockchiffre nutzt, wird XTS-Modus genannt und findet unter
anderem mit AES als “innere” Blockchiffre im “OS X Mountain Lion“-Betriebssystem (in der ”FileVault 2“Applikation) und im (Festplatten-)Datenverschlüsselungsverfahren TrueCrypt Anwendung. Dabei sieht
ein Chiffrat, mit Ti := (T 0 ||i), wie folgt aus:
(C1 , C2 , . . . ) = (ETWEAK (K, T1 , M1 ), ETWEAK (K, T2 , M2 ), . . . ).
Vorgeschlagen wurde eine Variante des hier dargestellten Verfahrens erstmals 2004 von Phillip Rogaway.
(a) Welche Vorteile hat dieses Verfahren gegenüber dem CBC-Modus, wenn wir als Anwendungszweck
Festplattenverschlüsselung anschauen? (Gibt es Nachteile?)
(b) Nehmen wir eine Variante des XTS-Verfahrens an, sodass X := T 0 gilt. (T 0 wird also nicht unter K2
verschlüsselt.) Was passiert, wenn Sie die zwei Chiffretexte C1 := ETWEAK (K, (T 0 ||1), PAD(T 0 ||1))
und C2 := ETWEAK (K, (T 0 ||2), PAD(T 0 ||2)) XOR-verknüpfen?
(c) Zusatzaufgabe. Schreiben Sie ein Programm (beispielsweise ein Pythonskript), das den XTSBetriebsmodus implementiert. (Hinweis: Für die ”innere“ Blockchiffre im XTS-Verfahren können
Sie zum Beispiel die AES-Implementierung aus PyCrypto (https://www.dlitz.net/software/
pycrypto) oder aus der Bibliothek Crypto++ (http://www.cryptopp.com) verwenden. Im AESFall würde l = 128 gelten. Als Padding-Funktion können Sie dann PAD(X||i) := 2i · X mod 2l
nutzen.)