5: Betriebsarten für Blockchiffren · Eik List, Jakob Wenzel Kryptographie(WS 16/17) Die Grenzen der Sicherheit Satz 21 (Angriff auf den Counter-Modus) Sei E: {0,1}n →{0,1}n eine

Eik List, Jakob Wenzel Kryptographie (WS 16/17)

5: Betriebsarten für Blockchiffren

–139– 5: Betriebsarten für Blockchiffren


5: Betriebsarten für Blockchiffren

Was wir bisher kennen Was wir wollen/brauchen

M E

K

Cnn

k

• Blockchiffre

• n-bit-Nachrichtenblock Mi,k-bit Schlüssel K

• DES: n = 64, AES: n = 128

• Was aber, wenn unsereNachrichten ≫ n Bits sind?

...

...

M1 M2 Mm

C1 C2 Cm

EK

n

n

n

n

n

n

k

• Betriebsart / Betriebsmodus

• m n-bit-NachrichtenblöckeM1, . . . , Mm, k-bit Schlüssel K

• Blockchiffre als Baustein



Blockchiffre Betriebsmodi

M E

K

Cnn

k

...

...

M1 M2 Mm

C1 C2 Cm

EK

n

n

n

n

n

n

k

In diesem Kapitel: Symmetrische Verschlüsselungsverfahren mit denfolgenden Eigenschaften:

• kurzer Schlüssel

• Blockchiffre als zentraler Baustein

• Verschlüsselung von Nachrichten variabler Länge

• Verschlüsselung multipler Nachrichten unter gleichem Schlüssel



Die Suche nach einer Sicherheitsdefinition

E : Verschlüsselungsverfahren für Nachrichten variabler Länge.

Der Angreifer kennt C = EK(M), aber weder K noch M .

Denkbare Sicherheitsdefinitionen:

• Message Recovery: Finde M .Zu schwach – partielle Information über M freuen den Angreifer

• Key Recovery: Finde K . Noch schwächer.

• Wir wollen: “Der Angreifer kann nicht einmal partielle Informationüber M erfahren . . . außer vielleicht der Länge |M |.”



5.1: Real or Random (RoR)

–143– 5: Betriebsarten für Blockchiffren 5.1: Real or Random (RoR)


5.1: Real or Random (RoR)

• Entweder ist C die Verschlüsselung einer vom Angreifergewählten Nachricht M (“real”), oder einer Sequenz vonZufallsbits (“random”).

• Kann der Angreifer nicht einmal zwischen “real” und “random”unterscheiden, dann kann er einem Chiffretext C erst recht nichtsNützliches entnehmen.

• Wir beschreiben das Angriffsmodell als ein Spiel.



“Real or Random” (RoR)-CPA-Angriffsmodell

Das RoR-CPA-Angriffsmodell für Betriebsmodi

• Initialisierungsphase:

◦ C wirft eine faire Münze: b$← {0, 1} und

wählt entweder einen SchlüsselK

$← {0, 1}k oder f$← F∗,∗

• Fragephase: Der Angreifer A stellt qverschiedene Klartextanfragen: M1, . . . , M q

◦ Fall b = 1: C antwortet mit Ci ← EK(M i)◦ Fall b = 0: C antwortet mit Zi ← f(M i)

• Ratephase:

◦ A gibt einen Tipp b′ ab◦ A gewinnt genau dann wenn b = b′

A

EK f

b = 1 b = 0C



Notation

• Sei M = M1, . . . , Mm mit Mi ∈ {0, 1}n.

• Wir bezeichnen Mi als den i-ten Nachrichtenblock.

• Sei C = C0,︸︷︷︸

optional

C1, . . . , Cm mit Ci ∈ {0, 1}n.

• Wir bezeichnen Ci als den i-ten Chiffretextblock.



5.2: Electronic Codebook (ECB)

–147– 5: Betriebsarten für Blockchiffren 5.2: Electronic Codebook (ECB)


5.2: Electronic Codebook (ECB)

...

...

M1 M2 M3 Mm

C1 C2 C3 Cm

EEEEkkkk

n

n

n

n

n

n

n

n

KKKK

• 1 ≤ i ≤ m: Ci := EK(Mi)

• ECB ist einer von vier im Zusammenhang mit dem DES “offiziellstandardisierten” “Modes of Operation” (“Betriebsarten”).

• In vielen (schlechten!) DES- oder AES-basiertenKrypto-Produkten wird der ECB-Modus verwendet.

Der ECB-Modus ist unsicher! (Warum?)–148– 5: Betriebsarten für Blockchiffren 5.2: Electronic Codebook (ECB)


ECB-Verschlüsselung

Der Klartext: ECB-Verschlüsselung: Gute Verschlüsselung:



Folgerung

• Auch formal “standardkonforme” Kryptosysteme können unsichersein. “Electronic Codebook” klingt gut, taugt aber nicht viel.

• Man muss genau analysieren, ob ein Kryptosystem etwas taugtund ob es für die eigenen Sicherheitsanforderungen einegeeignete Lösung liefert. Dazu muss man selbst seine eigenenSicherheitsanforderungen kennen (“Bedrohungsanalyse”).



5.3: Cipher Block Chaining (CBC)

–151– 5: Betriebsarten für Blockchiffren 5.3: Cipher Block Chaining (CBC)


5.3: Cipher Block Chaining (CBC)

...

...

M1 M2 M3 Mm

C0 C1 C2 C3 Cm

EEEEkkkk

n

n

n

n

n

n

n

n

KKKK

• Wähle einen zufälligen Startwert C0

• 1 ≤ i ≤ m: Ci := EK(Mi ⊕ Ci−1).

• Chiffretext C = (C0, . . . , Cn).

Und wie entschlüsselt man (C0, . . . , Cn)?Was passiert, wenn C0 nicht zufälligt ist?



Eigenschaften des CBC-Modus

Satz 19 (Sicherheit (CBC-Modus))

Der CBC-Modus mit zufälligen Startwert ist RoR-CPA-sicher.

CBC-Modus ist ein selbstsynchronisierender Betriebsmodus (→ Tafel)

Sicherheitsproblem in der Praxis

CBC ist unsicher, falls . . .

• . . . der Angreifer Kontrolle/Kenntnis über den Startwert (IV) C0 hat.

• . . . ein schon zuvor verwendeter Startwert (IV) wiederverwendet wird.



5.4: Counter-Mode (Ctr)

–154– 5: Betriebsarten für Blockchiffren 5.4: Counter-Mode (Ctr)


5.4: Counter-Mode (Ctr)

...

1 2 3 m

M1 M2 M3 Mm

C1 C2 C3 Cm

EEEEkkkk

nnn n

n

n

n

n

n

n

n

n

KKKK

Einfacher Counter-Modus:

• 1 ≤ i ≤ m : Ci := Mi ⊕ EK(i)

• Chiffretext C = (C1, . . . , Cm).



Counter-Mode mit zufälligem Startwert

...

R R + 1 R + 2 R + m− 1

M1 M2 M3 Mm

C1 C2 C3 Cm

EEEEkkkk

nnn n

n

n

n

n

n

n

n

n

KKKK

• Wähle R zufällig

• 1 ≤ i ≤ m : Ci := Mi ⊕ EK((i− 1 + R) mod 2n)

• Chiffretext: (R, C1, . . . , Cm).

• Nebenbedingung: Zähler i− 1 + R dürfen sich nicht wiederholen



Satz 20 (Der Counter-Mode ist RoR-CPA-sicher)

Sei die Summe der Längen aller ver- bzw. entschlüsselten Nachrichten viel

kleiner als 2n/2 n-bit Blöcke. Dann gilt:

Der Counter-Modus mit zufälligem Startwert ist RoR-CPA-sicher,

wenn die Nebenbedingung eingehalten wird.



Die Grenzen der Sicherheit

Satz 21 (Angriff auf den Counter-Modus)

Sei E : {0, 1}n → {0, 1}n eine Permutation. Man nutze E im Counter-Modus.

Nach ≈ (2n/2) Aufrufen kann man den von E generierten Schlüsselstrom mitsignifikantem Vorteil von einem echten Strom von Zufallsbits unterscheiden.

Beweis-Idee: Geburtstagsparadoxon!

Folgerung:

Die Länge eines mit den Counter-Modus erzeugten Schlüsselstroms sollteimmer weit unter 2n/2 · n Bits liegen (für einen Schlüssel K ).

Beispiel DES: (n = 64)

232 · 64 bit = 232 · 8 byte = 25 GB = 32 GB.



5.5: Exkurs: Das Geburtstagsparadoxon

–159– 5: Betriebsarten für Blockchiffren 5.5: Geburtstagsparadoxon


5.5: Exkurs: Das Geburtstagsparadoxon

Wie wahrscheinlich ist es,dass von 23 Leuten aufeinem Fußballfeld (beideTeams und derSchiedsrichter) zwei amgleichen Tag Geburtstaghaben

Etwa 50.7 %. Überrascht?〈http://de.wikipedia.org/wiki/Geburtstagsparadoxon〉



Wie rechnet man das aus?

• n ≤ 365 Bälle, die jeweils zufällig in einen von365 Körben geworfen werden.

• Die Wahrscheinlichkeit pn, dass von n Bällen injedem Korb höchstens ein Ball ist:◦ p1 = (365/365) = 1◦ p2 = (364/365)◦ p3 = (364/365) ∗ (363/365)◦ p4 = (364/365) ∗ (363/365) ∗ (362/365)◦ . . .

pn =∏

0≤i<n

365− i

365.

• Die Wahrscheinlichkeit, dass in mindestenseinem Korb mehr als ein Ball liegt, ist natürlich1− pn, siehe Tabelle.

Anz. 1− pn

1 0.00002 0.00273 0.00824 0.0164...

...20 0.411421 0.443722 0.475723 0.507324 0.538325 0.568726 0.598227 0.626928 0.6545



Verallgemeinerung des Geburtstagsparadoxons

• k Körbe und (wie bisher) n ≤ k Bälle.

• Die Wahrscheinlichkeit, dass Bälle in verschiedenen Körbenlanden:

pn =∏

0≤i<n

k− i

k.

• Für “große” k erwartet man eine Kollision bei

n =

√π

2·√

k

• Es gilt√

π2≈ 1.25.

• Ist n = c ·√

π2∗√

k, dann sind c2 Kollisionen zu erwarten.



Anwendung des Geburtstagsparadoxons in derKryptographie

Sei f$← F∗,n eine n-Bit-Zufallsfunktion.

Frage: Nach wie vielen Anfragen an f ist mit einer Kollision zurechen?

Antwort: Nach ca. 1.25 ·√

2n ≈√

2n = 2n/2 Anfragen.

Folgerung: Die Länge eines mit dem Counter-Modus generiertenSchlüsselstroms sollte immer weit kleiner als 2n/2 · n Bitssein.



5.6: Cipher Feedback (CFB)

–164– 5: Betriebsarten für Blockchiffren 5.6: Cipher Feedback (CFB)


5.6: Cipher Feedback (CFB)

...

M1 M2 M3 Mm

C0

C1 C2 C3 Cm

EEEEkkkk

nnn n

n

n

n

n

n

n

n

n

KKKK

• Wähle einen zufälligen “Initialization-Vector” C0 (IV)

• 1 ≤ i ≤ m : Ci := EK(Ci−1)⊕Mi

Und wie entschlüsselt man (C0, . . . , Cn)?



Sicherheitseigenschaften des CFB-Modus

Sicherheit (CFB-Modus)

Der CFB-Modus ist RoR-CPA-sicher, falls Startwerte nicht wiederverwendetwerden.

• Der CFB-Modus ist unsicher, falls ein Startwert mehrfach

verwendet wird. (Warum?)

• CFB-Modus ist ein selbstsynchronisierender Betriebsmodus(→ Tafel)



5.7: Output Feedback (OFB)

–167– 5: Betriebsarten für Blockchiffren 5.7: Output Feedback (OFB)


5.7: Output Feedback (OFB)

...

M1 M2 M3 Mm

C0

C1 C2 C3 Cm

EEEEkkkk

nnn n

n

n

n

n

n

n

n

n

KKKK

• Wähle einen zufälligen “Initialization-Vector” C0 (IV)

• X0 = C0

• 1 ≤ i ≤ m : Xi = EK(Xi−1) und Ci := Xi ⊕Mi



Sicherheitseigenschaften des OFB-Modus

Satz 22 (Sicherheit (OFB-Modus))

Der OFB Modus ist RoR-sicher, falls IV nicht mehrfach verwendet wird.

OFB-Modus ist ein kein selbstsynchronisierender Betriebsmodus.Warum?



5.8: Fehlende Authentizität

–170– 5: Betriebsarten für Blockchiffren 5.8: Fehlende Authentizität


5.8: Fehlende Authentizität

• Viele Laien gehen unbewusst von der Annahme aus, dass Daten,die (durch gute Verschlüsselung) sicher vor Mithörern sind, auchsicher vor Veränderungen sind, zumindest sicher vor gezieltenVeränderungen.

→ Kryptographie sollte man nur einsetzen, wenn man zuvoreine Bedrohungsanalyse gemacht hat. Sonst kann es sein,dass man hervorragende Schutzmaßnahmen einsetzt, dieüberhaupt nicht vor den tatsächlichen Gefahren schützen.

Als Ausweg bietet sich der Einsatz kryptographischer “MessageAuthentication Codes” (MACs) an (demnächst mehr dazu).



Fehlende Authentizität kann sogar die Vertraulichkeitgefährden

• Drahtlos: Verschlüsseltes Datenpaket D = (EK(H), EK(M)),bestehend aus Header H und Nutzdaten M .

• Gateway: Entschlüssele D und leite den Klartext (H, M)(drahtgebunden) an die in H angegebene IP-Adresse.

• Keine Überprüfung der Authentizität durch das Gateway. Vielleichtkann der Empfänger erkennen, wenn M manipuliert wurde – dasist nicht das Problem des Gateways!

• Eve◦ hat D′ = (EK(H), EK(M)) abgehört und will M wissen,◦ weiß (oder vermutet), dass D an die Adresse B gerichtet ist

(eigene Adresse E),◦ addiert deshalb B−E zur Adresse im Header◦ und schickt das manipulierte Datenpaket D′ an das Gateway.

• Das Gateway entschlüsselt D′ und leitet den Klartext an dieAdresse E von Eve.



5.9: Schlussbemerkungen

–173– 5: Betriebsarten für Blockchiffren 5.9: Schlussbemerkungen


5.9: Schlussbemerkungen

Sie sollten

• die Sicherheit von Standard-Betriebsarten einschätzen können(insbesondere Counter und CBC), mit Begründungen und

• in der Lage sein, diese Kenntnisse auch auf andere, Ihnen nochunbekannte Betriebsarten anwenden zu können.

Denken Sie immer daran:Auch formal “standardkonforme” Krypto-Implementationenwie der ECB-Modus können unsicher sein . . . und sind es ofttatsächlich.

–174– 5: Betriebsarten für Blockchiffren 5.9: Schlussbemerkungen

Documents

5: Betriebsarten für Blockchiffren · Eik List, Jakob Wenzel Kryptographie(WS 16/17) Die Grenzen der Sicherheit Satz 21 (Angriff auf den Counter-Modus) Sei E: {0,1}n →{0,1}n eine