f f f f K0 K1 K2 K3 L R L R

Universität Karlsruhe (TH)
Lösungen zu Übungsblatt 5
Institut für Kryptographie und Sicherheit
Willi Geiselmann (Vorlesung)
Marius Hillenbrand (Übung)
Signale, Codes und Chiffren II
Sommersemester 2009
Übung vom 6. Juni 2009
Aufgabe 1: FEAL4-Kryptoanalyse
Die leicht vereinfachte Version des FEAL4 soll durch lineare Kryptoanalyse gebrochen werden:
L
R
K0
f
K1
f
K2
f
K3
f
L
R
Die f -Funktion und die S-Boxen (Si (a, b) := rot2((a + b + i) mod 256) sind gegenüber dem Original nicht
verändert:
0
0
S0
1
2
3
1
S1
2
S0
3
S1
K: Byte
0
1
Der Ausgangspunkt um lineare Approximationen für die f -Funktion zu finden ist das jeweils letzte Bit
der Addition der 4 S-Boxen, bei dem gegenüber allen anderen Bit kein Übertrag auftreten kann. Die
ersten beiden S-Boxen liefern die Gleichungen:
• F [2] = B[0] + F [8] und
• F [10] = 1 + B[0] + B[8] + K[0] + B[16] + B[24] + K[8] (hier geht auch der Schlüssel mit ein!),
wobei F [i] das i-te Ausgabebit von f ist; B[i] und K[i] entsprechend das i-te Eingabe- bzw. Schlüsselbit.
(a) Gib die Gleichungen an, die die beiden anderen S-Boxen liefern.
(b) Gib die 3-Runden Charakteristiken an, die sich durch die Gleichung zur ersten und dritten S-Box
ergeben.
(c) Beschreibe das Vorgehen der linearen Kryptoanalyse, das die vier Charakteristiken verwendet.
(d) Bei wievielen Klartext/Chiffrat-Paaren erwartest du einen Erfolg der Analyse?
Empirisch funktioniert der Angriff bei etwa 15 Paaren problemlos. Wie erklärt sich der Unterschied
zu dem geschätzten Wert (falls er abweicht)?
Lösung zu Aufgabe 1:
Bei der linearen Kryptoanalyse werden Teile einer Chiffre mit Hilfe sogenannter linearer Charakteristiken
angenähert. Eine lineare Charakteristik gibt an, daß die Parität einer bestimmten Menge von Eingabebits
und Ausgabebits mit einer bestimmten Wahrscheinlichkeit p gerade ist.
Wenn wir z.B. die im FEAL benutzte S-Box S0(A,B) betrachten, stellen wir fest, daß die Parität der
Eingabebits A[0], B[0] und des Ausgabebits S[2] immer gerade ist. Oder bei der S-Box S1(A,B) ist die
Parität der selben Bits (A[0], B[0], S[2]) immer ungerade.
Die Charakteristiken werden für die ersten drei Runden aufgestellt. Dann wird für den Teilschlüssel der
letzten Runde vollständig gesucht nach Kandidaten, bei denen die linearen Approximationen korrekt auftreten. Das gleiche macht man mit einer Charakteristik für die letzten drei Runden mit dem Teilschlüssel
der ersten Runde. Die verbleibenden Schlüsselbits kann man dann leicht mit vollständiger Suche finden.
(a) Die genannten zwei Beziehungen können verwendet werden, um lineare Approximationen für die
gesamte Funktion F := f (B, k) anzugeben:
• Für S0 oben (Byteposition 0): F [2] = B[0] + F [8] (d.h. gerade Parität zwischen den drei
genannten Bits)
• Für S1 an Byteposition 1: F [10] = 1 + B[0] + B[8] + K[0] + B[16] + B[24] + K[8] (d.h. ungerade
Parität zwischen den genannten Bits. Hier geht auch der Schlüssel mit ein!)
• Für S0 an Byteposition 2: F [18] = F [8] + B[16] + B[24] + K[8]
• Für S1 an Byteposition 3: F [26] = 1 + F [16] + B[24].
(b) Diese 4 Charakteristiken für f können zu Charakteristiken für die ersten 3 Runden erweitert werden.
Da alle beteiligten Charakteristiken deterministisch (d.h. Parität gerade entweder mit Wahrscheinlichkeit 0 oder 1) sind, ist die entstehende Charakteristik auch deterministisch.
Für die erste Gleichung ergibt sich, daß die Parität über die Eingabebits L[0], L[2], L[8], R[0], sowie
die Ausgabebits nach der dritten Runde L3 [2], L3 [8] und R3 [0] immer gleich 0 ist.
Die dritte Gleichung dehnt sich zu einer deterministischen Charakteristik aus: Die Parität über die
Eingabebits L[8], L[16], L[18], L[24], R[16], R[24], sowie die Ausgabebits L3 [8], L3 [18], R3 [16], R3 [24]
ist immer konstant (jedoch im Gegensatz zur ersten Drei-Runden-Charakteristik schlüsselabhängig).
(c) Dies kann genutzt werden, um jetzt eine vollständige Suche nach dem Teilschlüssel K3 durchzuführen:
Für alle Möglichkeiten für K3 werden die gesammelten Chiffrate teilweise entschlüsselt. Dann wird
überprüft, ob für alle Paare (Klartext, teilweise entschlüsseltes Chiffrat) die angegebene Parität
gleich ist. Wenn nein, kann dieser Wert für K3 ausgeschlossen werden. Wenn ja, ist ein Kandidat
für K3 gefunden (der mit Hilfe der anderen 3 deterministischen Charakteristiken genauer überprüft
werden kann).
Wenn nach der Anwendung aller Charakteristiken für die ersten drei Runden einige Kandidaten für
K3 übrig sind, kann eine ähnliche Attacke gegen K0 erfolgen: Nun werden die letzten drei Runden
linear approximiert und für K0 eine vollständige Suche durchgeführt.
K1 und K2 können dann aus den teilweise verschlüsselten Klartexten und den teilweise entschlüsselten Chiffraten berechnet werden.
(d) Angenommen, K 0 ∈ {0, 1}16 ist ein falsch geschätzter Rundenschlüssel. Dann ist die (idealisierte)
Wahrscheinlichkeit, daß trotzdem eine Charakteristik für n Klartext-/Chiffrat-Paare konstant ist,
(1/2)n−1 (bzw. (1/2)n , daß die Charakteristik immer den richtigen“ Wert hat, falls die konkrete
”
Parität nicht schlüsselabhängig und damit bekannt ist).
Damit ergibt sich folgende Abschätzung der Erfolgswahrscheinlichkeit eines wie geschildert durchgeführten Angriffs auf den ersten Rundenschlüssel von FEAL-4 mittels der zwei Charakteristiken
aus Aufgabenteil (b):
P r[Angriff auf ersten Rundenschlüssel erfolgreich]
=P r[Jedes falsche K’ erfüllt wenigstens eine Charakteristik nicht]
Y
16
= (1 − 2−2n ) = (1 − 2−n )2 −1
K0
16
≥(1 − 2−n )2
≥ 1 − 216 · 2−2n
=1 − 216−2n .
Hierbei wurde die Ungleichung von Bernoulli benutzt. Analog ergibt sich, daß die Erfolgswahrscheinlichkeit für einen Angriff auf den vierten Rundenschlüssel mindestens 1 − 216−2n ist. (Sind
erster und vierter Rundenschlüssel gefunden, können die restlichen Rundenschlüssel durch zwei
vollständige Suchen der Größe jeweils 216 bestimmt werden.)
Insgesamt ist der Angriff auf beide Rundenschlüssel schon für n = 12 mit einer Wahrscheinlichkeit
von > 99% erfolgreich. Dies deckt sich in etwa mit der in der Aufgabenstellung angegeben Größe
n = 15.
Aufgabe 2: Vollständige S-Boxen
Eine wichtige Eigenschaft, die man von einer guten S-Box fordert, ist die der Vollständigkeit. Eine Funktion f : GF (2)n → GF (2)m heißt vollständig, wenn jedes Bit des Outputs von jedem Bit des Inputs
abhängt, d.h. wenn es für jedes j mit 0 ≤ j < m und jedes i mit 0 ≤ i < n zumindest eine Belegung des
Inputs mit der Eigenschaft gibt, daß sich bei einer Änderung des i-ten Inputbits auch das j-te Outputbit
ändert.
(a) Zeige, daß es keine bijektive Substitution der Länge 2 gibt, die auch vollständig ist.
(b) Zeige weiterhin, daß für eine Länge > 1 eine vollständige, bijektive Substitution keine lineare Abbildung sein kann.
Input Output
000
111
001
001
010
010
(c) Betrachte folgende S-Box: 011
011
100
100
101
101
110
110
111
000
Ist diese Substitution vollständig und ist sie für kryptographische Zwecke geeignet?
Lösung zu Aufgabe 2:
(a) Sei S eine bijektive, vollständige Substitution der Länge 2. Seien a0 und a1 die Eingabebits und
b0 und b1 die Ausgabebits von S. Aufgrund der Bijektivität von S ergeben sich folgende mögliche
Verteilungen von b0 :
a0
0
0
1
1
a1
0
1
0
1
(1)
b0
0
0
1
1
(2)
b0
1
1
0
0
(3)
b0
0
1
0
1
(4)
b0
1
0
1
0
(5)
b0
0
1
1
0
(6)
b0
1
0
0
1
(1)
Da S nach Voraussetzung auch vollständig ist, fallen die Möglichkeiten b0
(2)
(3)
(4)
b0 sind unabhängig von a1 , und b0 und b0 sind unabhängig von a0 .)
(5)
(4)
bis b0
(1)
weg. ( b0
und
(6)
Da S bijektiv ist, muß im Falle b0 = b0 bzw. b0 = b0 die Verteilung von b1 einer der Verteilungen
(1)
(4)
b0 bis b0 entsprechen. Dies aber ist ein Widerspruch zur angenommenen Vollständigkeit von S!
(b) Angenommen S(x) = A · x für x ∈ 0, 1n (mit n ≥ 2) und A ∈ GLn (IF2 ). Bezeichne ei den i-ten
Einheitsvektor des IF2 -Vektorraums F2n . Für beliebige i, j ∈ 1, . . . , n folgt nach Vollständigkeitsvoraussetzung, daß ein xi,j existiert, sodaß sich die Vektoren A · xi,j und A · (xi,j + ei ) im j-ten Bit
unterscheiden, d.h., daß im Vektor A · (xi,j + xi,j + ei ) = A · ei an der j-ten Stelle eine 1 steht.
Da i und j beliebig waren, folgt A · ei = (1, . . . , 1)> für alle i. Wegen n ≥ 2 widerspricht dies der
Bijektivität von S.
(c) Wir geben für beliebige 1 ≤ i, j ≤ 3 eine konkrete Wahl eines Eingabevektors x an, sodaß Ändern
des i-ten Bits von x eine Änderung im j-ten Bit von S(x) zur Folge hat.
• Falls i = j: Wähle x mit Hamming-Gewicht 1 und xi = 0.
• Falls i 6= j: Wähle x = (0, 0, 0).
Die betrachtete Substitution ist also vollständig, aber offensichtlich nicht für kryptographische
Zwecke geeignet. (Für x ∈
/ {(0, 0, 0), (1, 1, 1)} ist S(x) = x.) Vollständigkeit allein kann also noch
kein hinreichendes Kriterium für eine gute S-Box sein.
Aufgabe 3: Kryptoanalyse
Gegeben sei E : GF (2)l × GF (2)n 7→ GF (2)n eine Blocksubstitution und C = E(K, M ), wobei M einen
n-Bit Klartextblock, K einen l-Bit Schlüssel und C den resultierende n-Bit Chiffretextblock bezeichnet.
Sei ferner C = (c0 , . . . , cn−1 ) mit
ci = fi (k0 , . . . , kl−1 , m0 , . . . , mn−1 )
für 0 ≤ i < n. Nun seien die Koeffizienten c0 bis cr−1 des Chiffretextblockes von den Schlüsselbits ks bis
kl−1 unabhängig, d.h. für 0 ≤ i < r gilt
ci = fi (k0 , . . . , ks−1 , m0 , . . . , mn−1 ).
Wie läßt sich diese Form der Unvollständigkeit für eine known-plaintext-attack bei vollständigem Durchsuchen des Schlüsselraumes ausnutzen?
Lösung zu Aufgabe 3:
Für einen known-plaintext-Angriff stehen Paare M, E(K, M ) zur Verfügung. Bei vollständiger Suche
über alle möglichen Schlüssel K ∈ {0, 1}l kann nun ausgenutzt werden, daß die ersten r Bits vom Chiffrat E(K, M ) nur von den ersten s Bits von K abhängen. Genauer kann in einem ersten Schritt eine
vollständige Suche über die ersten s Bits (k0 , . . . , ks−1 ) von K durchgeführt werden; die Richtigkeit einer
Schätzung (k0 , . . . , ks−1 ) kann überprüft werden, indem man die Gleichungen
E(K, M )i = fi (k0 , . . . , ks−1 , m0 , . . . , mn−1 )
(1)
für alle Bits 0 ≤ i < r und alle Paare M, E(K, M ) verifiziert. In einem zweiten Schritt können dann die
restlichen l − s Bits von K mit “herkömmlicher” vollständiger Suche gefunden werden.
Gehen wir idealisierend davon aus, daß nach dem gerade beschriebenen ersten Schritt nur ein Kandidat
für die ersten s Bits von K alle Gleichungen (1) erfüllt, reduziert man so den Aufwand einer vollständigen
Suche nach K von 2l auf max{2s , 2l−s } Schritte.