Übungsblatt 2 mit Lösungsvorschlägen

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?)
Lösungsvorschlag zu Aufgabe 1. Eine mögliche Verschlüsselung (mit zufällig und gleichverteilt
gewählten Initialisierungsvektoren im CBC-, CFB- und OFB-Modus und ohne Initialisierungsvektor im
ECB-Modus) könnte wie folgt aussehen:
ECB
CBC
CFB
OFB
M1 = 0100 1011 0100 0001
(ECB)
C1
= 0101 0011 0101 1001
(CBC)
IV1
:= 1000
(CBC)
C1
= 1011 1100 1000 1110
(CFB)
IV1
:= 0100
(CFB)
C1
= 0001 0010 1011 0010
(OFB)
IV1
:= 1100
(OFB)
C1
= 1111 1000 0101 1000
M2 = 0100 1101 0100 0001
(ECB)
C2
= 0101 1101 0101 1001
(CBC)
IV2
:= 0011
(CBC)
C2
= 0100 1110 1010 0011
(CFB)
IV2
:= 0010
(CFB)
C2
= 1011 1110 0011 0000
(OFB)
IV2
:= 1011
(OFB)
C2
= 0111 1100 1101 1111
Eine notwendige Bedingung, um passive Sicherheit im CBC-Modus zu gewährleisten, ist die zufällige
und gleichverteilte Wahl des Initialisierungsvektors bei jeder Neuverschlüsselung. (Um sich gegen aktive
Angreifer abzusichern, müssen jedoch andere Maßnahmen ergriffen werden.)
Es scheint, dass in den Modi CFB und OFB der Initialisierungsvektor ebenso bei jeder Neuverschlüsselung zufällig und gleichverteilt gezogen werden sollte, um passive Sicherheit zu garantieren. (Für
eine Sicherheitsanalyse im CFB-Fall siehe beispielsweise die Veröffentlichung von Fougue, Martinet und
Poupard unter http://www.iacr.org/archive/fse2003/28870382/28870382.pdf.)
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?
Lösungsvorschlag zu Aufgabe 2.
(a) Im ECB-Modus wäre Mi nicht effizient von Zufall zu unterscheiden. (Wir nehmen (im Folgenden)
an, dass die Verschlüsselungsfunktion nicht effizient von einer Zufallsfunktion unterschieden werden
kann.) Im CBC-Modus würden Bitfehler sich derart auswirken, dass Mi von Zufall nicht effizient
zu unterscheiden wäre und Mi+1 die Bitfehler genau an den Stellen hätte, an dem bei Ci Bitfehler
auftraten. Im CFB-Modus hätte Mi Bitfehler an Bitfehlerstellen von Ci ; Mi+1 dagegen sähe zufällig
aus. Im OFB-Modus hätte Mi Bitfehler an Bitfehlerstellen von Ci ; Mi+1 bliebe unverändert.
(b) Die Entschlüsselungen im ECB-, CBC- und CFB-Modus 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
Lösungsvorschlag zu Aufgabe 3. Wir betrachten zuerst den Fall 1, in dem ein Initialisierungsvektor
IV ∈ {0, 1}l fest für alle Verschlüsselungen gewählt wird. Sei A(1) ein Angreifer, der das IND-CPA-Spiel
durchführt. Dabei werden die Nachrichten mit einer Blockchiffre E(K, ·) : {0, 1}k × {0, 1}l → {0, 1}l , für
k, l ∈ und Schlüssel K, im CBC-Modus verschlüsselt. Sei ECBC (K, IV, ·) : {0, 1}k × {0, 1}l × {0, 1}ml →
{0, 1}l ×{0, 1}ml , für m ∈ , ein Orakel, das Verschlüsselungen E(K, ·) unter zufälligem K mit festem IV
im CBC-Modus bereitstellt. (Für M = M1 M2 . . . Mm gilt ECBC (K, IV, M ) := (IV, C1 , C2 , . . . , Cm ) :=
(IV, E(K, M1 ⊕ IV ), E(K, M2 ⊕ C1 ), . . . , E(K, Mm ⊕ Cm−1 )).) A(1) agiert wie folgt:
N
N
1. A(1) erhält im Folgenden Zugriff auf ein ECBC (K, IV, ·)-Orakel.
2. A(1) wählt zwei Nachrichten M (1) := 0l 6= M (2) beliebig (aber gleicher Länge).
3. A(1) erhält C ∗ := ECBC (K, IV, M (b) ) = (IV, E(K, M (b) ⊕ IV )), für gleichverteiltes b ∈ {1, 2}.
4. A(1) erfragt C (1) := ECBC (K, IV, M (1) ) = (IV, E(K, 0l ⊕ IV )) = (IV, E(K, IV )).
5. Falls C ∗ = C (1) gilt, gibt A(1) den Wert 1 aus, ansonsten den Wert 2.
A(1) gewinnt das IND-CPA-Spiel im Fall 1 mit Wahrscheinlichkeit 1. Daraus folgt, dass ein Schema
im CBC-Modus, bei dem der Initialisierungsvektor IV bei jeder (neuen) Verschlüsselung derselbe (und
somit fest) ist, IND-CPA-unsicher ist.
Betrachten wir Fall 2, in dem ein Initialisierungsvektor IV ∈ {0, 1}l bei jeder neuen Verschlüsselung
um 1 schrittweise hochgezählt wird. Sei A(2) ein Angreifer, der das IND-CPA-Spiel durchführt. Dabei
werden die Nachrichten wie oben mit einer Blockchiffre E(K, ·) : {0, 1}k × {0, 1}l → {0, 1}l , für k, l ∈
und Schlüssel K, im CBC-Modus verschlüsselt. Sei ECBC (K, ·, ·) : {0, 1}k × {0, 1}l × {0, 1}ml →
{0, 1}l × {0, 1}ml , für m ∈ , ein Orakel, das Verschlüsselungen E(K, ·) unter zufälligem K und mit
Initialisierungsvektor IV im CBC-Modus bereitstellt.
N
N
1. A(2) erhält im Folgenden Zugriff auf ein ECBC (K, IV (i) , ·)-Orakel. Dabei nehmen wir an, dass IV (i)
für i ∈ beim i-ten ECBC -Aufruf benutzt wird. Zudem gilt IV (i+1) := IV (i) + 1.
N
2. A(2) erfragt für M (1) := 0l die Verschlüsselung C (1) := ECBC (K, IV (1) , M (1) ) = (IV (1) , E(K, 0l ⊕
IV (1) )) = (IV (1) , E(K, IV (1) )).
3. A(2) setzt M (2) := IV (1) ⊕ IV (2) und wählt M (3) 6= M (2) beliebig, sodass jedoch |M (2) | = |M (3) |
gilt. (Wir wissen, dass IV (2) = IV (1) + 1 gilt.)
4. A(2) erhält C ∗ := ECBC (K, IV (2) , M (b) ) = (IV (2) , E(K, M (b) ⊕IV (2) )), für gleichverteiltes b ∈ {2, 3}.
(1)
5. Falls C2∗ = C2
den Wert 3.
(1)
(1)
für C ∗ = (C1∗ , C2∗ ) und C (1) = (C1 , C2 ) gilt, gibt A(2) den Wert 2 aus, ansonsten
A(2) gewinnt das IND-CPA-Spiel im Fall 2 mit Wahrscheinlichkeit 1. Daraus folgt, dass ein Schema im
CBC-Modus, bei dem der Initialisierungsvektor IV bei jeder neuen Verschlüsselung um 1 schrittweise
hochgezählt wird, IND-CPA-unsicher ist.
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.)
Lösungsvorschlag zu Aufgabe 4. XTS steht für XEX Tweakable Block Cipher with Ciphertext
Stealing. Das XEX-Tweakable-Block-Chiffren-Verfahren wurde, wie oben erwähnt, von Rogaway 2004
vorgeschlagen. Zusätzlich kommt im XTS-Modus die Cipher-Text-Stealing-Methode zum Einsatz. (Diese
werden wir hier nicht erläutern, sodern als Beispiel im Pythonskript unten implementieren.)
(a) Festplatten sind in Sektoren eingeteilt, deren Größe überlicherweise 512 Byte, 2048 Byte oder
4096 Byte beträgt. Diese Sektoren beinhalten Blöcke; überlicherweise mit einer Byte-Länge von
512 Byte für Nutzdaten. Nehmen wir eine XTS-Blocklänge von 16 Byte an, passen somit 32
XTS-Chiffretextblöcke in einen Block und dadurch mindestens 32 XTS-Chiffretextblöcke in einen
Sektor. Wird blockweise auf die Festplatte geschrieben und gelesen, muss bei einer Änderung
eines Klartextblocks nur ein XTS-Block neu berechnet werden; wohingegen im CBC-Modus alle
Chiffretextblöcke ab der Änderung neu berechnet werden müssen.
Als ein Nachteil könnte die XTS-Schlüssellänge k angesehen werden, wobei die innere Blockchiffre
eine Schlüssellänge von k/2 besitzt. (Im AES-Fall wären dies mindestens 128 Bit; somit benötigen
wir mindestens einen 256-Bit-XTS-Schlüssel.)
(b) Würde X = T 0 gelten, ergäbe die XOR-Verknüpfung von C1 := ETWEAK (K, (T 0 ||1), PAD(T 0 ||1))
und C2 := ETWEAK (K, (T 0 ||2), PAD(T 0 ||2))
ETWEAK (K, (T 0 ||1), PAD(T 0 ||1)) ⊕ ETWEAK (K, (T 0 ||2), PAD(T 0 ||2))
= E(K1 , PAD(T 0 ||1) ⊕ PAD(T 0 ||1)) ⊕ (T 0 ||1) ⊕ E(K1 , PAD(T 0 ||2) ⊕ PAD(T 0 ||2)) ⊕ (T 0 ||2)
= E(K1 , 0) ⊕ (T 0 ||1) ⊕ E(K1 , 0) ⊕ (T 0 ||2)
= (T 0 ||1) ⊕ (T 0 ||2).
Somit erhalten wir einen nicht-trivialen Zusammenhang von (den von uns gewählten Werten) (T 0 ||1)
und (T 0 ||2) und könnten ETWEAK von einer Zufallsfunktion unterscheiden.
(c) Folgendes Pythonskript verschlüsselt Klartexte im XTS-AES-Modus:
from Crypto.Cipher import AES
from Crypto import Random
# string xor
def strxor(x,y):
return ’’.join(chr(ord(a) ^ ord(b)) for a,b in zip(x,y))
# Pad a bit string X and i to bit length AES.block_size
def PAD(X,i):
h = ""
for x in X:
h = h + str(ord(x))
return str((int(h)*2^i) % 2^AES.block_size).rjust(16)
# Since |T| == AES.block_size, we need only one AES function call in ECB mode
def E(K,T):
return (AES.new(K, AES.MODE_ECB)).encrypt(T)
# Since |T| == AES.block_size, we need only one AES function call in ECB mode
def D(K,C):
return (AES.new(K, AES.MODE_ECB)).decrypt(C)
# Tweakable block cipher
def E_TWEAK(K,T,i,M):
K1 = K[:16]
K2 = K[16:]
X = E(K2,T)
#X = T
ENC = E(K1,strxor(M,PAD(X,i)))
return strxor(ENC,PAD(X,i))
# Tweakable block cipher encryption
def D_TWEAK(K,T,i,C):
K1 = K[0:16]
K2 = K[16:]
X = E(K2,T)
#X = T
return strxor(D(K1,strxor(C,PAD(X,i))),PAD(X,i))
# Read random key
K = Random.new().read(32)
# Read random tweak
T = Random.new().read(AES.block_size)
# Plain text
M = ["Wir erweitern un","sere Blockchiffr","e-Definition aus",
" der Vorlesung u","m eine zusaetzli","che Eingabe ..."]
# Encryption with "ciphertext stealing"
i=1
C=[]
for m in M:
if len(m)==16:
C.append(E_TWEAK(K,T,i,m))
else:
C.append(C[i-2][:len(m)])
C[i-2]=E_TWEAK(K,T,i,m+C[i-2][len(m):])
i+=1
# Decryption with "ciphertext stealing"
i=1
M=[]
for c in C:
if len(c)==16:
M.append(D_TWEAK(K,T,i,c))
else:
M[i-2] = D_TWEAK(K,T,i,C[i-2])
M.append(D_TWEAK(K,T,i-1,c+M[i-2][len(c):]))
tmp = M[i-2]
M[i-2] = M[i-1]
M[i-1] = tmp[:len(c)]
i+=1
print "".join(C)
print "".join(M)