Teil 3: Grundlagen der Kryptographie 2

Vorlesung Informationssicherheit
Thema 3: Grundlagen der Kryptographie II
Robert Baumgartl
12. Mai 2016
1 / 109
Zufallszahlen
Wozu?
I
(Monte-Carlo-)Simulation, Statistik
I
randomisierte Algorithmen
I
Spiele
I
Kryptografie
Zufallszahlen – durch einen echten zufälligen Prozess
generiert (Rauschen, atomare Zerfallsprozesse, . . . )
Pseudozufallszahlen – Folgen von Zahlen, die wie
Zufallszahlen aussehen (, aber durch einen deterministischen
Prozess generiert werden)
2 / 109
Güte von Zufallszahlen
Anforderungen:
1. Gleichverteilung
2. lange bzw. keine Periode
3. Unabhängigkeit
4. effizient ermittelbar
Kryptografisch sichere Zufallszahlen dürfen zusätzlich nicht
vorhersehbar sein.
Prüfung der Güte erfolgt mittels Tests, z.B.:
wahrscheinlichkeitstheoretisch
χ2 -Test1
Kolmogorov-Smirnov-Test
1
empirisch
Gleichverteilungstest
Serientest
sprich: „Tschih-Quadrat-Test“
3 / 109
χ2 -Test
Beispiel2 : 2 gekoppelte Würfel
Augen s
2
3
4
5
6
7
8
9
10
11
12
Wkt. ps
1
36
2
36
3
36
4
36
5
36
6
36
5
36
4
36
3
36
2
36
1
36
Experiment mit n = 144 Würfen
gezählt Ys
2
4
10
12
22
29
21
15
14
9
6
erwartet (nps )
4
8
12
16
20
24
20
16
12
8
4
I
Maß für die „Abweichung“ der Würfelwerte vom „richtigen“
Verhalten:
V = (Y2 − np2 )2 + (Y3 − np3 )2 + · · · + (Y12 − np12 )2
I
2
unausgewogen, da (z. B.) Fehler in Y7 aufgrund p7 > p2 viel
stärker gewichtet als Fehler in Y2
D. E. Knuth: The Art of Computer Programming. Vol. 2, 1998, S. 42ff
4 / 109
χ2 -Test, fortgesetzt
Beispiel: 2 gekoppelte Würfel und Verallgemeinerung
I
Normierung mit erwarteter Anzahl:
V =
(Y3 − np3 )2
(Y12 − np12 )2
(Y2 − np2 )2
+
+ ··· +
np2
np3
np12
Allgemein gilt:
V =
k
X
(Ys − nps )2
s=1
nps
k
1X
=
n
s=1
Ys2
ps
−n
V wird nun in der Tabelle der Quantile der χ2 -Verteilung aufgesucht:
I
Freiheitsgrade ν („nü“) = k − 1 (Anzahl Kategorien - 1)
I
Tabelleneintrag x in Zeile ν: „V ist kleiner oder gleich x mit
Wahrscheinlichkeit p.“
5 / 109
χ2 -Test, fortgesetzt
Tabelle der Quantile der χ2 -Verteilung
Freiheits-
p
grade
1%
5%
25%
50%
75%
95%
99%
ν =1
0.00
0.00
0.11
0.45
1.32
3.84
6.63
ν =2
0.02
0.10
0.58
1.39
2.77
5.99
9.21
ν =3
0.11
0.35
1.21
2.37
4.11
7.81
11.34
ν =4
0.30
0.71
1.92
3.36
5.39
9.49
13.28
ν =5
0.55
1.15
2.68
4.35
6.63
11.07
15.09
ν =6
0.87
1.64
3.46
5.35
7.84
12.59
16.81
ν =7
1.24
2.17
4.26
6.35
9.04
14.07
18.48
ν =8
1.65
2.73
5.07
7.34
10.22
15.51
20.09
ν =9
2.09
3.33
5.90
8.34
11.39
16.92
21.67
ν = 10
2.56
3.94
6.74
9.34
12.55
18.31
23.21
ν = 11
3.05
2.82
7.54
10.34
13.70
19.68
24.73
ν = 12
3.57
5.23
8.44
11.34
14.85
21.03
26.22
Für das Beispiel gilt V ≈ 7.15, ν = 10 . Abzulesen: V ≤ 9.34 mit 50%iger Wkt., V ≤ 6.74 mit 25%iger Wkt.
Fazit: V = 7.15 tritt in rund einem Drittel aller Fälle auf; Würfel sind o.k.!
6 / 109
Lineare Kongruenzgeneratoren
Berechnung einer Zufallsfolge mittels
zi+1 = (azi + b) mod m
(m prim, Initialisierungswert z0 mit 0 < z0 < m; a, b Parameter)
Beispiel: a = 6, b = 0, m = 13, z0 = 2
i
zi
0
2
1
12
2
7
3
3
4
5
5
4
6
11
7
1
8
6
9
10
10
8
11
9
12
2
...
...
I
generiert volle Periode (auch für m = 231 − 1, a = 16807 u. a.)
I
zi = 0 nicht erreichbar (warum?)
I
keine volle Periode z. B. für m = 13, a = 5, b = 0, z0 = 1
I
effiziente Berechnung, gutes statistisches Verhalten
I
ungeeignet für kryptografische Zwecke, da vorhersehbar
(vgl. James Reeds: “Cracking” a Random Number Generator.
Cryptologia Vol. 1, No. 1, 1977, S. 20–26)
7 / 109
Linear rückgekoppelte Schieberegister
Prinzip
Rückkopplungsfunktion
bn bn−1
...
b3
b2
b1
Zufallsbit
Abbildung: Rückgekoppeltes Schieberegister mit n Bit Länge
Arbeitsweise:
I
Ausgabe des Bits b1 als neues Zufallsbit
I
gleichzeitig Verknüpfung der Bits bi miteinander (z. B.
mittels ⊕) in Rückkopplungsfunktion
I
Ergebnis der Verknüpfung wird bn , alle anderen Bits eine
Stelle nach rechts
8 / 109
Linear rückgekoppeltes Schieberegister
Beispiel
XOR
b4
b3
b2
b1
ZB
I
sog. linear feedback shift register
(LFSR)
I
n = 4 Bit; Init: z0 = 1111
I
hier: maximale Periode (2n − 1)
I
Ergebnis darf nie 0 sein
i
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
b
1111
0111
1011
0101
1010
1101
0110
0011
1001
0100
0010
0001
1000
1100
1110
1111
usw.
ZB
1
1
1
1
0
1
0
1
1
0
0
1
0
0
0
9 / 109
Einwegfunktionen
. . . sind ein wichtiger Baustein kryptografischer Verfahren
I
Bestimmung von f (x) aus x leicht (vorwärts)
I
Bestimmung von x aus gegebenem f (x) extrem schwer,
d. h. nur mit allen zur Verfügung stehenden Rechnern der
Welt in hunderten von Jahren
Beispiele:
I
Suche einer Telefonnummer zu gegebenem Namen im
Telefonbuch ist einfach
I
Suche eines Namens zu gegebener Telefonnummer im
Telefonbuch ist schwierig
I
Multiplikation zweier (großer) Primzahlen ist einfach
I
Zerlegung des Produktes in zwei Primzahlfaktoren ist
extrem aufwändig (→ Faktorisierungsverfahren)
10 / 109
Einwegfunktionen, contd.
Es gibt
I
keinen Beweis für die Existenz von und
I
keine systematischen Konstruktionsverfahren für
Einwegfunktionen.
Einwegfunktion mit Hintertür:
I
mit Kenntnis eines Zusatzschlüssels wird die Ermittlung
von x aus f (x) einfach.
11 / 109
Einweg-Hashfunktionen
. . . sind Einwegfunktionen, die zu gegebenen Daten variabler
Länge einen Funktionswert konstanter, meist kurzer Länge (→
„Fingerabdruck“, kryptografischer Hash, Message Digest)
ermitteln.
I
I
I
Hash H(m) zu gegebenen Daten m ist leicht zu ermitteln
(effizient zu berechnen).
Zu vorgegebenem Hash eine passende Eingabe zu
konstruieren ist hingegen (extrem) schwer
(m = H −1 (H(m))).
Änderung eines Bits in der Eingabe sollte im Mittel die
Hälfte der Bits in der Ausgabe ändern.
Anwendung:
I Integritätssicherung von Dateien
I Digitales Signieren
I Authentifizierung
12 / 109
Kryptografische Hashverfahren
Beispiele
Verfahren
MD2
MD4
MD5
SHA-1
SHA-256
SHA-512
SHA-3
Jahr
1988
1990
1991
1995
2004
2004
2012
gebrochen?
X3
X
X4
X5
-
Hashlänge
[Bit]
128
128
128
160
256
512
226-512
Blockgröße
[Bit]
128
512
512
512
512
1024
576-1152
Es ist ebenfalls möglich, Blockchiffren als kryptografische Hashes
einzusetzen.
3
4
5
Knudsen, Mathiassen: Preimage and Collision Attacks on MD2, 2005
Praktikumsaufgabe
Stevens, Karpman, Peyrin: Freestart Collision for full SHA-1, 2015
13 / 109
Angriffe gegen Hashfunktionen
Kollisionen
I
Kollision: Für zwei Nachrichten m1 und m2 wird ein- und
derselbe Hash erzeugt, also H(m1 ) = H(m2 )
I
in der Softwaretechnik z. B. durch Überlauflisten
behandelt, unkritisch
I
bei kryptografischen Hashes gefährlich; erste Stufe zum
„Brechen“ des Hashverfahrens
I
Kollisionsfreiheit ist unmöglich (unendlich viele
verschiedene Nachrichten werden auf 2Hashlänge
verschiedene Hashwerte abgebildet)
I
stattdessen: Kollisionsresistenz gefordert
14 / 109
Angriffe gegen Hashfunktionen
Kollisionsresistenz
Schwache Kollisionsresistenz
I
Zu einer Nachricht m und deren gegebenen Hashwert
H(m) ist es praktisch unmöglich, eine zweite Nachricht m0
zu finden, die den gleichen Hashwert H(m0 ) = H(m) hat.
Starke Kollisionsresistenz
I
Es ist praktisch unmöglich, zwei Nachrichten m und m0 zu
finden, die den gleichen Hashwert H(m) = H(m0 )
aufweisen.
15 / 109
Angriffe gegen Hashfunktionen
Brute-Force-Angriff gegen schwache Kollisionsresistenz
gegeben: Nachricht m mit Hashwert H(m)
gesucht: Nachricht m0 mit H(m0 ) = H(m)
1:
2:
3:
4:
5:
6:
7:
8:
I
START
zufällige Generierung m0
Ermittlung H(m0 )
if H(m0 ) = H(m) then
STOP {Kollision gefunden}
else
GOTO 2
end if
bei einer Hashlänge von n Bit ist die Wkt. einer Kollision
bei jeder Iteration 2−n
im Mittel 2n Iterationen bis zur
Kollision nötig
16 / 109
Angriffe gegen Hashfunktionen
Brute-Force-Angriff gegen schwache Kollisionsresistenz
Start
zufällige Auswahl m0
Berechnung H(m0 )
H(m0 ) =
H(m) ?
yes
Kollision gefunden
Stop
17 / 109
Angriffe gegen Hashfunktionen
Geburtstagsangriff
Geburtstagsparadoxon:
Wie viele Personen müssen sich in einem Raum befinden,
damit die Wahrscheinlichkeit, dass jemand mit mir am
gleichen Tag Geburtstag6 hat größer ist als 50%?
I
253
Wieviele Personen müssen sich in einem Raum befinden,
damit die Wkt., dass zwei von Ihnen am gleichen Tag
Geburtstag haben, größer ist als 50%?
I
6
23
6. September
18 / 109
Angriffe gegen Hashfunktionen
Geburtstagsangriff
Geburtstagsparadoxon:
Wie viele Personen müssen sich in einem Raum befinden,
damit die Wahrscheinlichkeit, dass jemand mit mir am
gleichen Tag Geburtstag6 hat größer ist als 50%?
I
253
Wieviele Personen müssen sich in einem Raum befinden,
damit die Wkt., dass zwei von Ihnen am gleichen Tag
Geburtstag haben, größer ist als 50%?
I
6
23
6. September
19 / 109
Angriffe gegen Hashfunktionen
Geburtstagsangriff
Geburtstagsparadoxon:
Wie viele Personen müssen sich in einem Raum befinden,
damit die Wahrscheinlichkeit, dass jemand mit mir am
gleichen Tag Geburtstag6 hat größer ist als 50%?
I
253
Wieviele Personen müssen sich in einem Raum befinden,
damit die Wkt., dass zwei von Ihnen am gleichen Tag
Geburtstag haben, größer ist als 50%?
I
6
23
6. September
20 / 109
Geburtstagsparadoxon
Beweisskizze
I
Wkt., dass man an einem bestimmten Tag im Jahr
1
Geburtstag hat: 365
I
Wkt., dass man an einem bestimmten Tag im Jahr nicht
364
Geburtstag hat: 365
I
Wkt., dass man an zwei bestimmten Tagen im Jahr nicht
Geburtstag hat: 363
365
Voraussetzung: Geburtstage in der Gruppe sind unabhängig
und gleichverteilt
I
Eine Gruppe von zwei Personen enthält mit
364
keine zwei Personen mit dem
Wahrscheinlichkeit 365
gleichen Geburtstag, da die zweite Person genau an
einem Tag keinen Geburtstag haben kann.
21 / 109
Geburtstagsparadoxon
Beweisskizze, Fortsetzung
I
Eine Gruppe von drei Personen enthält mit
364 363
Wahrscheinlichkeit 365
· 365 keine zwei Personen mit dem
gleichen Geburtstag, da die dritte Person (und nur diese)
an zwei Tagen keinen Geburtstag haben darf.
I
Eine Gruppe von n Personen enthält mit Wkt.
366−n
364 363
365 · 365 · . . . · 365 keine 2 Personen gleichen
Geburtstags.
I
Eine Gruppe von n Personen enthält mit Wkt.
363
366−n
pn = 1 − 364
365 · 365 · . . . · 365 2 Personen gleichen
Geburtstags.
p23 ≈ 0, 5072
In einer Gruppe von (mindestens) 23 Personen ist die
Wahrscheinlichkeit, dass 2 Personen am gleichen Tag
Geburtstag haben, größer als 50%.
22 / 109
Angriffe gegen Hashfunktionen
Zurück zum Planet...Geburtstagsangriff
I
Der Angreifer möchte zwei Nachrichten M und M 0 finden,
so dass gilt: H(M) = H(M 0 ).
I
Er kann dann M dem Kommunikationspartner zeigen, den
(gemeinsamen) Hash H(M) signieren lassen und dann M
durch M 0 ersetzen
Aus dem Geburtstagsparadoxon folgt:
I
Es ist sehr schwer, zu einer gegebenen Nachricht mit
Hash einen zweiten Hash zu finden, der mit ihrem eigenen
Hashwert kollidiert.
I
Es ist leichter, eine Kollision zu erzeugen, wenn beide
Nachricht variabel sind!
I
Die Anzahl zu prüfender Hashes reduziert sich um die
Wurzel!
23 / 109
Geburtstagsangriff
Beispiel und Fazit
I
Gegeben sei eine kryptografisch sichere Hashfunktion.
I
(hypothetische) Hashlänge 64 Bit (k = 64)
I
Brute-Force-Angriff eines gegebenen Hashes erfordert das
Prüfen von 264 Hashwerten (≈ 1.892 · 1019 )
I
Rechner, der in der Sekunde 1.000.000 Hashes generiert,
benötigt dafür etwa 600.000 Jahre
I
Ein Geburtstagsangriff auf diese Hashfunktion erfordert
das Prüfen von 2k /2 = 232 Hashes
I
Obiger Rechner benötigt dafür etwa 71 Minuten7 !
Fazit: Ist ein Geburtstagsangriff auf die Hashfunktion zu
erwarten, so muss die Länge des generierten Hashes im
Vergleich zum ausschließlich drohenden Brute-Force-Angriff
verdoppelt werden.
7
Ein analoger Angriff auf SHA-1 benötigt 2.79 Urknallperioden (á 13.75 Mrd. Jahre)
24 / 109
Hashing en Detail: MD5
Idee: Kompression
I
(mehrfache) Iteration einer sog. Kompressionsfunktion
I
I
I
Eingabe: Daten fester Länge
Resultat: Daten fester Länge (kürzer als Eingabe)
Beispiel: Kompression bei MD5: Eingabe H (128 Bit), B
(512 Bit), Resultat 128 Bit
Nachricht M
512
Init 128
H0
C
512
128
H1
C
...
... 128
512
C
Pad
128
C
128
Hn = h(M)
Abbildung: Merkle-Damgård-Verfahren
25 / 109
Merkle-Damgård-Schema
1. M wird aufgefüllt (Padding) mit
I
I
I
1 Bit mit Wert 1,
variable Anzahl 0-Bits,
64 Bit, in denen die Länge von M (in Bits) kodiert ist,
so dass die Länge der resultierenden Nachricht M 0 ein
Vielfaches von 512 Bit beträgt
Pad =
1 0
0
...
0
Länge (64 Bit)
Abbildung: Padding im Merkle-Damgård-Verfahren
2. M 0 wird in 512 Bit lange Blöcke B1 , B2 , . . . Bn aufgeteilt
3. H0 = IV (Initial Value)
4. Hi = C(Hi−1 , Bi ) ∀i = 1, . . . , n
5. Hn = H(M), der gesuchte Hashwert von M.
26 / 109
Merkle-Damgård-Schema
Anmerkungen:
I
maximale Länge der Nachricht 264 Bit= 2 EiB (ExbiByte) =
2048 PiB (PebiByte)
I
lineare Komplexität des Verfahrens
I
die meisten kryptografischen Hashverfahren nutzen diese
Technik (unterscheiden sich in C)
Satz (Merkle/Damgård, 1989): Wenn die Kompressionsfunktion
C keine Kollisionen verursacht, dann auch nicht das nach
obigem Verfahren konstruierte Hashverfahren.
27 / 109
„Message Digest“ MD5
I
Ronald Rivest, 1991
I
beschrieben im RFC 1321
I
nutzt das Merkle-Damgård-Schema
I
sehr populär (Zertifikate, Integritätsprüfungen, . . . )
I
Linux: Kommando md5sum
I
seit 2004 sind Kollisionen publiziert → unsicher
Ablauf:
I
relativ komplexe Kompressionsfunktion
I
für jeden der Blöcke Bi werden 4 Iterationen („Runden“)
ausgeführt
I
jede Runde besteht aus 16 Operationen
28 / 109
Eine Operation in MD5
16mal
Hi , 128 Bit
A
B
modulare Addition +
N
j-ter Teilblock von Bi
(32 Bit)
C
D
C
D
+
Konstante
32 Bit
+
Linksrotation
«s
+
A
B
29 / 109
Nichtlineare Funktionen N
F (X , Y , Z ) = (X ∧ Y ) ∨ ((¬X ) ∧ Z )
G(X , Y , Z ) = (X ∧ Z ) ∨ (Y ∧ (¬Z ))
H(X , Y , Z ) = X ⊕ Y ⊕ Z
I(X , Y , Z ) = Y ⊕ (X ∨ (¬Z ))
I
in jeder Runde wird eine andere Funktion genutzt
30 / 109
Anwendung: Message Authentication Codes (MAC)
I
= spezieller Hash, der von Eingabedaten und einem
zusätzlichen geheimen Schlüssel abhängt
I
somit nur für Besitzer des Schlüssels generier- bzw.
prüfbar
I
mittels Blockchiffre im CBC- oder CFB-Modus oder aus
Hashfunktion implementierbar
I
Beispiel: HMAC (RFC 2104) → TLS, IPsec
Zweck:
I
Sicherung der Integrität von Nachrichten
I
Authentisierung der Nachricht
I
Nichtabstreitbarkeit der Nachricht
31 / 109
Message Authentication Codes (MAC)
Prinzip
1. Alice und Bob tauschen (geheimen) Schlüssel aus
2. Alice generiert Nachricht, ermittelt MAC aus Nachricht und
Schlüssel
3. Nachricht und MAC werden an Bob übertragen
4. Bob berechnet MAC aus Nachricht und Schlüssel
5. Stimmen errechnete und übertragene MAC überein, ist die
Nachricht authentisch und muss von Alice stammen, da
nur diese den Schlüssel besitzt.
32 / 109
Message Authentication Codes (MAC)
Realisierung mittels Hashfunktion
I
Secret Prefix MAC: MACk (x) = h(k k x)
I
I
I
gefährlich, weil MAC einer verlängerten Nachricht x aus
MACk (x) ohne Kenntnis von k ermittelt werden kann:
h(k kx1 x2 . . . xn+1 ) = h (h(k ||x1 x2 . . . xn )||xn+1 )
Secret Suffix MAC: MACk (x) = h(x k k )
I
I
gefährlich, wenn Mallory Kollisionen erzeugen kann, d. h. ,
h(x) = h(y ) mit x 6= y
damit:
MACk (x) = h(x k k ) = h(y k k ) = MACk (y )
I
I
Mallory könnte x durch y ersetzen
HMACk (x) = h [(k + ⊕ opad) k h[(k + ⊕ ipad) k x]]
I
I
zweifaches Hashen beseitigt Nachteile
trotzdem effizient, da Nachricht x nur einmal gehasht
33 / 109
A hash-based message authentication code which does not show the security weakness described above is the HMAC construction proposed by Mihir Bellare, Ran
HMAC (RFC2104)
Canetti and Hugo Krawczyk in 1996. The scheme consists of an inner and outer
Struktur, grafisch
hash and is visualized in Figure 12.2.
Fig. 12.2 HMAC construction
(Abb.:Christof Paar und Jan Pelzl. Understanding Cryptography.
Springer, 2010, S. 324)
The MAC computation starts with expanding the symmetric key k with zeros on
34 / 109
Anwendungsbeispiel: Hashcash
Idee:
I
zur Autorisierung soll ein Nutzer ‘etwas’ Rechenzeit
aufwenden und diesen Aufwand nachweisen
I
Nutzung Hashfunktion; Ergebnis muss bestimmte
Merkmale aufweisen
I
Beispiel: „Generiere einen SHA1-Hash über einem
zufällligen Datum, dessen erste 20 Bits alle den Wert Null
haben!“ → es müssen ca. 220 Hashes ermittelt werden
Anwendung:
I
Abwehr von Spam
I
Mining-Funktion in Cryptowährungen (z. B. Bitcoin)
35 / 109
Signaturen (Unterschriften)
. . . dienen dem Beweis der Echtheit, der Urheberschaft oder
dem Einverständnis mit dem Inhalt eines Dokumentes.
Eigenschaften:
I
authentisch - überzeugt den Empfänger, dass der
Unterzeichner willentlich unterschrieben hat
I
fälschungssicher - beweist, dass der Unterzeichner (und
kein anderer) das Dokument unterzeichnete
I
nicht wiederverwendbar - kann in kein anderes Dokument
„übertragen“ werden
I
Unterschriebenes Dokument kann nicht mehr verändert
werden.
I
nicht rücknehmbar - Unterzeichner kann Unterschrift nicht
leugnen.
36 / 109
Digitale Signaturen
Verschlüsselung von Dokumenten weist viele dieser
Anforderungen auf → Nutzung kryptografischer Techniken zur
Signierung digitaler Dokumente
Verschiedene Verfahren:
I
symmetrische Verschlüsselung und Vermittlung
I
mittels Public-Key-Kryptographie
I
mittels Public-Key-Kryptographie und Einweg-Hashfunktion
37 / 109
Signieren mit symmetrischen Kryptosystemen und
Vermittler
Voraussetzungen:
I
Vermittler (Trent), dem vertraut wird
I
Schlüssel KA für Komm. Alice ↔ Trent und KB für Bob ↔
Trent
Protokoll:
1. Alice verschlüsselt M an Bob mit KA und schickt sie an
Trent.
2. Trent entschlüsselt M mittels KA .
3. Trent verschlüsselt M zusammen mit einer Nachricht, dass
M von Alice stammt, mit KB
4. Trent sendet C = KB (M) an Bob.
5. Bob entschlüsselt C mit KB . Er kann M lesen und ist
sicher, dass diese von Alice stammt.
38 / 109
Signieren mit Public-Key-Kryptographie
1. Alice verschlüsselt M mit ihrem privaten (!) Schlüssel DKA
(unterzeichnet): C = DKA (M)
2. Alice schickt Chiffrat C an Bob
3. Bob entschlüsselt C mit Alice’ öffentlichen Schlüssel EKA ,
was die Echtheit von M beweist
Vorteil im Vergleich zum symmetrischen Verfahren:
I
kein Vermittler erforderlich
I
auch nicht im Streitfall
Probleme:
I
Sicherung der Authentizität des öffentlichen Schlüssels
von Alice EKA
I
Zeitbedarf bei langen Dokumenten
39 / 109
Signieren mit Public-Key-Kryptographie und
Einweg-Hashfunktion
Idee: Signierung eines Einweg-Hashes über das Dokument
anstatt des Dokumentes selbst (→ effizient).
Protokoll:
1. Alice berechnet den Einweg-Hash W1 zum
entsprechenden Dokument M: W1 = H(M).
2. Alice verschlüsselt W1 mit ihrem privaten Schlüssel DKA :
C = DKA (W1 ) = DKA (H(M)) (Signatur).
3. Alice sendet C und M an Bob.
4. Bob ermittelt den Einweg-Hash W2 zum empfangenen
Dokument M.
5. Bob entschlüsselt W1 = EKA (C) mit Alice’ öffentlichem
Schlüssel
6. Bob prüft, ob W1 = W2 gilt. Wenn ja, dann ist die
Unterschrift von Alice unter M gültig.
40 / 109
Vorteile des Signierens mit Public-Key-Kryptographie
und Einweg-Hashfunktion
1. großer Geschwindigkeitsgewinn bei gleicher Sicherheit
(Voraussetzung: sichere Hashfunktion)
2. Unterschrift und Dokument können getrennt gespeichert
werden.
3. Möglichkeit, das Dokument selbst (noch) geheim zu
halten; Offenlegung erst bei Prüfung der Unterschrift nötig
→ urheberrechtliches Schützen
41 / 109
Nutzung von Zeitstempeln
I
Wenn signiertes Dokument nur einmal genutzt werden darf
(Scheck, Gutschein, . . . ) muss Mehrfachverwendung
unterbunden werden
I
Lösung: Datum und Zeit der Unterschrift an Dokument
anhängen, gemeinsam unterschreiben
42 / 109
Nutzung von Zeitstempeln
I
Wenn signiertes Dokument nur einmal genutzt werden darf
(Scheck, Gutschein, . . . ) muss Mehrfachverwendung
unterbunden werden
I
Lösung: Datum und Zeit der Unterschrift an Dokument
anhängen, gemeinsam unterschreiben
43 / 109
Mehrfachsignatur
Problem: Alice und Bob wollen beide ein- und dasselbe
Dokument signieren (z. B. einen Vertrag)
Möglichkeiten:
a) Alice und Bob unterschreiben verschiedene Kopien des
Dokuments (unhandlich)
b) Erst unterzeichnet Alice, dann unterzeichnet Bob das von
Alice unterzeichnete Dokument. (→ Signaturprüfung von
Alice muss immer erst Signaturprüfung von Bob
vorangehen - unelegant)
c) Alice und Bob unterschreiben separat den Hashwert des
Dokuments (→ Unterschriften einzeln prüfbar)
44 / 109
Digitale Signaturen mit Verschlüsselung
Kombination von Signierung und Verschlüsselung:
1. Alice unterschreibt ihre Nachricht M mit ihrem privaten
Schlüssel: SA (M) mit SA = DKA
2. Alice verschlüsselt die unterzeichnete Nachricht mit Bobs
öffentlichem Schlüssel: C = EKB (SA (M))
3. Alice schickt C an Bob
4. Bob entschlüsselt C mit seinem privaten Schlüssel
DKB : DKB (EKB (SA (M)))
5. Bob prüft die Gültigkeit mit Alice’ öffentlichen Schlüssel
und erhält die Klartextnachricht:
VA (DKB (EKB (SA (M)))) = M mit VA = EKA
45 / 109
Anmerkungen
Günstig, vor der Verschlüsselung zu signieren:
I
Unterschrift kann nicht durch einen Gegner entfernt
werden.
I
Man sieht, was man unterschreibt!
I
Keine kryptanalytischen Angriffe möglich.
Es können für Signierung und Verschlüsselung
unterschiedliche Schlüsselpaare verwendet werden.
46 / 109
Erneutes Senden als Empfangsbestätigung
1. Alice unterschreibt M mit ihrem privaten Schlüssel,
verschlüsselt anschließend mit Bobs öffentlichem
Schlüssel und sendet das Chiffrat an Bob:
C = EKB (SA (M))
2. Bob entschlüsselt mit seinem privaten Schlüssel, überprüft
Alice’ Signatur mit deren öffentlichen Schlüssel und stellt
M damit wieder her: VA (DKB (EKB (SA (M)))) = M.
3. Bob unterschreibt seinerseits M mit seinem privaten
Schlüssel SB , chiffriert anschließend mit Alice’ öffentlichen
Schlüssel und schickt die Nachricht als
Empfangsbestätigung zurück: C2 = EKA (SB (M))
4. Alice entschlüsselt mit Ihrem privaten Schlüssel und prüft
wiederum Bobs Signatur mit seinem öffentlichen
Schlüssel. Stimmt die entschlüsselte mit der
ursprünglichen Nachricht überein, weiß sie, dass Bob die
Nachricht erhalten hat.
47 / 109
Erneutes Senden als Empfangsbestätigung
Rücksendeangriff
Protokoll ist unsicher, wenn für Verschlüsselung und Signierung
der gleiche Algorithmus eingesetzt wird (Vx = Ex , Sx = Dx )!
1. Alice signiert und verschlüsselt (wie gehabt):
C = EKB (DKA (M))
2. Mallory zeichnet C auf, sendet sie (etwas später) an Bob
und behauptet, C sei von ihm.
3. Bob dechiffriert die Nachricht mit seinem privaten
Schlüssel und versucht anschließend, mit Mallorys
öffentlichem Schlüssel die (von Alice stammende)
Unterschrift zu prüfen.
EKM (DKB (EKB (DKA (M)))) = EKM (DKA (M))
48 / 109
Erneutes Senden als Empfangsbestätigung
Rücksendeangriff und dessen Abwehr
4. Obwohl die Unterschrift nicht verifiziert werden kann,
schickt Bob (automatisiert?) gemäß dem Protokoll eine
Empfangsbestätigung an Mallory
C2 = EKM (DKB (EKM (DKA (M))))
5. Mallory muß nun:
I
I
I
I
mit seinem privaten Schlüssel DKM entschlüsseln
mit Bobs öffentlichen Schlüssel EKB entschlüsseln
erneut mit seinem privaten Schlüssel entschlüsseln
mit Alice’ öffentlichen Schlüssel EKA entschlüsseln
. . . und schon kann er M lesen!
Lehre:
Verschiedene Schlüssel oder verschiedene Algorithmen für
Signierung und Verschlüsselung einsetzen! Nicht automatisch
bestätigen und signieren!
49 / 109
Authentifizierung (oder Authentifikation)
2 Rollen:
I
Partei, die Identität nachweisen will (Beweisender,
„Prover“)
I
Partei, die Identität prüfen will (Verifizierender, „Verifier“)
Unterscheidung von
I
einseitiger Authentifikation (z. B. gegenüber Rechner) und
I
gegenseitiger Authentifikation.
Nutzung von
I
charakteristischen Eigenschaften
I
Besitz
I
Wissen
50 / 109
Authentifizierung mittels Passwort
Naive Implementierung
Alice
{A, P}
P0
P = P0
gespeichertes
Passwort
Zugang gewährt
Anmerkungen:
I
Passwort muss erzeugt/vergeben werden
I
Identität A muss mit übermittelt werden
I
Abspeicherung des Passwortes P0 im Klartext
51 / 109
Authentifizierung mittels Passwort
Nutzung einer kryptografischen Hashfunktion
Alice
{A, P}
h(P0 )
h(P) = h(P0 )
gespeicherter
Passworthash
Zugang gewährt
Anmerkungen:
I
Passwort nicht mehr im Klartext abgelegt → kann nicht
gestohlen werden!
I
Problem: schlechte Passworte
52 / 109
Mögliche Angriffe auf den Vorgang der
Authentifizierung
I
Ausspähen des Passwortes
I
Social Engineering
I
Erraten des Passwortes
I
Wörterbuchangriff
I
Brute Force
53 / 109
Social Engineering
„Hallo, ich bin der freundliche Mann vom
Rechenzentrum. Ich möchte die Virensoftware auf
Ihrem Rechner aktualisieren und benötige dazu Ihr
Nutzerkennzeichen und Passwort.“
Verwandte Themen:
I
„Dumpster Diving“ – Auswertung von Papierkörben,
Abfallbehältern
I
„Tailgating“ – einer berechtigten Person in sensitive
Bereiche folgen
I
„Shoulder Surfing“ – Ablesen/Abfilmen von Passworten bei
der Eingabe
Johnny Long: No Tech Hacking: A Guide to Social Engineering,
Dumpster Diving and Shoulder Surfing. Syngress, 2008
54 / 109
Erraten des Passwortes
Ein legendärer Einbruch im Lawrence Berkeley National
Laboratory, Kalifornien:
LBL> telnet elxsi
Elxsi at LBL
login: root
password: root
incorrect passwort, try again
login: guest
password: guest
incorrect passwort, try again
login: uucp
password: uucp
WELCOME TO THE ELXSI COMPUTER AT LBL
(Clifford Stoll: Kuckucksei. Fischer, 1991)
I
bei gut gewarteten Systemen heute nahezu aussichtslos
55 / 109
Automatisiertes Erraten des Passwortes
Linux-PC, Authentifizierungs-Logfile /var/log/auth.log, Ausschnitt
Apr
Apr
Apr
Apr
Apr
Apr
Apr
Apr
Apr
Apr
Apr
Apr
Apr
Apr
Apr
Apr
Apr
Apr
Apr
Apr
Apr
Apr
Apr
Apr
Apr
Apr
Apr
Apr
Apr
Apr
Apr
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
5
14:44:35
14:44:39
14:44:43
14:44:44
14:44:46
14:44:47
14:44:49
14:44:51
14:44:53
14:44:54
14:44:56
14:44:58
14:45:00
14:45:01
14:45:03
14:45:05
14:45:07
14:45:10
14:45:11
14:45:13
14:45:15
14:45:17
14:45:21
14:45:24
14:45:27
14:45:31
14:45:32
14:45:34
14:45:35
14:45:37
14:45:39
idir
idir
idir
idir
idir
idir
idir
idir
idir
idir
idir
idir
idir
idir
idir
idir
idir
idir
idir
idir
idir
idir
idir
idir
idir
idir
idir
idir
idir
idir
idir
sshd[14612]:
sshd[14620]:
sshd[14630]:
sshd[14640]:
sshd[14640]:
sshd[14648]:
sshd[14648]:
sshd[14656]:
sshd[14656]:
sshd[14666]:
sshd[14666]:
sshd[14674]:
sshd[14674]:
sshd[14684]:
sshd[14684]:
sshd[14692]:
sshd[14692]:
sshd[14702]:
sshd[14710]:
sshd[14710]:
sshd[14718]:
sshd[14718]:
sshd[14728]:
sshd[14736]:
sshd[14746]:
sshd[14754]:
sshd[14762]:
sshd[14762]:
sshd[14770]:
sshd[14770]:
sshd[14780]:
Failed password for invalid user admin from 93.99.106.4 port 40799 ssh2
Failed password for root from 93.99.106.4 port 42116 ssh2
Failed password for root from 93.99.106.4 port 43885 ssh2
Invalid user test from 93.99.106.4
Failed password for invalid user test from 93.99.106.4 port 45676 ssh2
Invalid user test from 93.99.106.4
Failed password for invalid user test from 93.99.106.4 port 47395 ssh2
Invalid user webmaster from 93.99.106.4
Failed password for invalid user webmaster from 93.99.106.4 port 48814 ssh2
Invalid user user from 93.99.106.4
Failed password for invalid user user from 93.99.106.4 port 50581 ssh2
Invalid user username from 93.99.106.4
Failed password for invalid user username from 93.99.106.4 port 51972 ssh2
Invalid user username from 93.99.106.4
Failed password for invalid user username from 93.99.106.4 port 53530 ssh2
Invalid user user from 93.99.106.4
Failed password for invalid user user from 93.99.106.4 port 55065 ssh2
Failed password for root from 93.99.106.4 port 56829 ssh2
Invalid user admin from 93.99.106.4
Failed password for invalid user admin from 93.99.106.4 port 60192 ssh2
Invalid user test from 93.99.106.4
Failed password for invalid user test from 93.99.106.4 port 33440 ssh2
Failed password for root from 93.99.106.4 port 35208 ssh2
Failed password for root from 93.99.106.4 port 36679 ssh2
Failed password for root from 93.99.106.4 port 38334 ssh2
Failed password for root from 93.99.106.4 port 39667 ssh2
Invalid user danny from 93.99.106.4
Failed password for invalid user danny from 93.99.106.4 port 41516 ssh2
Invalid user sharon from 93.99.106.4
Failed password for invalid user sharon from 93.99.106.4 port 42957 ssh2
Invalid user aron from 93.99.106.4
56 / 109
Wörterbuchangriff (Dictionary Attack)
Idee:
I Offline-Generierung einer Liste aus Einträgen mit
I
I
potentielles Passwort
potentielles Passwort, verschlüsselt
I
alle möglichen Worte, Namen, Bezeichner usw. mittels der
Einwegfunktion des Betriebssystems verschlüsseln
I
Diebstahl der Passwortdatei
I
Vergleich der verschlüsselten Wortliste mit den Hashes
aus der Passwortdatei
I
Bei Übereinstimmung ist das unverschlüsselte Passwort
der entsprechende Eintrag aus der Wortliste
→ Werkzeug john (Praktikum)
57 / 109
Erschwerung des Wörterbuchangriffes mittels Salz
I
Passwort wird vor Verschlüsselung mit einer Zufallszahl
konkateniert (dem Salz)
I
Salz wird mit in der (geheimen) Passwortdatei gespeichert
I
bei genügend großer Anzahl möglicher Hash-Werte wird
ein Wörterbuchangriff unmöglich
I
Mallory müßte zu jedem Wort alle möglichen Salz-Werte
durchprobieren
I
erschwert nur Wörterbuchangriff, kein Brute-Force-Attack
Beispiel: crypt() im POSIX
58 / 109
Weitere Gegenmaßnahmen gegen Wörterbuchangriff
I
möglichst keine Hinweise auf Länge des PW (’*’ u. ä.) in
der Eingabemaske
I
möglichst kein Hinweis, ob NKZ gültig
I
Verzögerung nach jedem erfolglosen Anmeldeversuch
periodisches Erneuern der Passworte:
I
+ gecrackte PW werden automatisch ausgetauscht
− Nutzer müssen periodisch neue PW lernen
59 / 109
Anforderungen an gute Passworte
I
möglichst lang
I
gesamten Zeichenvorrat nutzen (sonst resultiert eine
signifikante Verkleinerung des Schlüsselraums →
Brute-Force-Angriff vereinfacht)
I
keine Namen, Worte (auch nicht rückwärts)
I
regelmäßig wechseln
I
computergenerierte Passworte: geringe Akzeptanz
(werden aufgeschrieben) → Standard FIPS PUB 181
(http://www.itl.nist.gov/fipspubs/fip181.htm)
I
proaktive PW-Checker prüfen gewähltes PW auf
Mindestanforderungen
60 / 109
Dauer von Brute-Force-Angriffen
in Abhängigkeit vom Schlüsselraum
4 Byte
5 Byte
6 Byte
7 Byte
8 Byte
Kleinbuchstaben (26)
0.5 s
12 s
5 min
2.2 h
2.4 d
Kleinbuchst.+Ziffern (36)
1.7 s
1 min
36 min
22 h
33 d
alphanum. Zeichen (62)
15 s
15 min
16 h
41 d
6.9 a
druckbare Zeichen (95)
1.4 min
2.1 h
8.5 d
2.2 a
210 a
ASCII-Zeichen (128)
4.5 min
9.5 h
51 d
18 a
2300 a
8-Bit-Zeichen (256)
1.2 h
13 d
8.9 a
2300 a
580.000 a
Tabelle: vgl. Bruce Schneier: Angewandte Kryptographie, Pearson,
2006, S.201
I
zugrundegelegt wurde eine Geschwindigkeit von
1.000.000 Schlüsselberechnungen pro Sekunde
61 / 109
Welche Knackgeschwindigkeit ist realistisch?
Stefan Arbeiter, Matthias Deeg: Bunte Rechenknechte. In: c’t 06/2009, S. 204ff
I
I
abhängig vom gewählten Verschlüsselungsverfahren
System 1 - 4 Prozessoren á 6 Cores (Intel Dunnington) @
2.5 GHz (HP-PC, ca. 18.000 US-$)
I
I
ermittelt ca. 1.2 Milliarden NTLM-Hashes pro Sekunde
System 2 - Intel Core 2 Quad, Nvidia GeForce GTX 280
(„Gamer-PC“, ca. 800 EUR)
I
I
I
CPU ca. 200 Millionen Hashes/s
GPU ca. 720 Millionen Hashes/s (CUDA8 nutzender
Passwortknacker)
P
0.9 Milliarden NTLM-Hashes pro Sekunde
8
Compute Unified Device Architecture, eine API zur Nutzung der Shader-Prozessoren aktueller Grafikkarten für
wissenschaftliche Berechnungen
62 / 109
Professionelle Knack-Hardware
a) „Deep Crack“
I
I
I
1998, 250.000 US-$, EFF9
1536 Kryptoprozessoren
88 Milliarden DES-Schlüssel pro Sekunde
b) COPACOBANA
I
I
I
2006, 10.000 US-$, Unis Bochum und Kiel
120 XILINX Spartan3-1000 FPGA
65 Milliarden DES-Schlüssel pro Sekunde
c) distributed.net
I
verteiltes Rechnen; Nutzbarmachung von idle-Time auf
Internet-Hosts
d) es ist davon auszugehen, dass Geheimdiensten weit
teurere Systeme zur Verfügung stehen
9
Electronic Frontier Foundation, eine Nichtregierungsorganisation der Vereinigten Staaten
63 / 109
Regenbogentabellen
Motivation
Brute-Force-Angriff auf ein Passwort:
I
sehr viel Rechenzeit, kaum Speicher
Wörterbuchangriff
I
sehr viel Speicherplatz, kaum Rechenzeit
Idee: kompaktere Datenstruktur als Wörterbuch, dafür
größerer, aber vertretbarer Suchaufwand
(„Time-Memory-Tradeoff“)
Voraussetzungen:
I
Hashfunktion H (bildet Passworte auf Hashes ab)
I
Reduktionsfunktion R, bildet Hashes auf (potentielle)
Passworte ab (keine Inverse von H!)
Beispiel für R für ZK der Länge n Bit:
ZK = (Bit 63. . . 0 des Hashes + Position in Tabelle) mod 2n
64 / 109
Regenbogentabellen
Ermittlung
I
beginnend mit einem Element des Schlüsselraums (potentielles
Passwort) Nacheinanderausführung von H und R
I
es entstehen Ketten von Passworten und Hashes (ca. 10.000
Elemente lang)
I
nur das erste und letzte Passwort jeder Kette wird gespeichert;
diese bilden die Regenbogentabelle
I
es werden so viele Ketten gebildet, bis 99.9% aller möglichen
Passworte erfasst sind
I
Tabelle wird nach den jeweils letzten Passworten sortiert
65 / 109
Regenbogentabellen
armel
xqjkx
wurtl
H
H
H
0xbf1ffd. . .
0x365023. . .
0xadb661. . .
R
R
R
bmgfs
xphkp
dvniw
H
H
H
0x21cd0e. . .
0x432045. . .
0xfdb21b. . .
R
R
R
ybtos
jbprb
jglkw
H
H
H
0xa8a258. . .
0xa31303. . .
0x072195. . .
R
R
R
lfslf
imest
qkmbr
66 / 109
Regenbogentabellen
Knacken eines Hashes (Finden des zugehörigen Passwortes)
1. Hash wird alternierend der Reduktions- und der
Hashfunktion unterworfen, bis er ein Passwort generiert,
das in der zweiten Spalte der Regenbogentabelle
vorkommt.
2. Dann wird die zugehörige Anfangszeichenkette reduziert
und gehasht, bis der Eingangshash wieder erzeugt wurde.
3. Das Resultat der vorgangegangenen Reduktionsfunktion
ist das gesuchte Passwort.
67 / 109
bcrypt
Problem: Zur Authentifizierung genutzte Hashingverfahren
(MD5, Blowfish, SHA) wurden entwickelt, um effizient
berechnet zu werden. → gut für Brute-Force-Angriff!
Idee: spezielles Hashverfahren, das besonders langsam
arbeitet, um Brute-Force-Angriff zu verlangsamen.
Lösung:
I
bcrypt10
I
128 Bit Salz
I
konfigurierbare Iterationsanzahl (→
Berechnungsgeschwindigkeit adaptierbar)
10
Niels Provos und David Mazières. “A Future-Adaptable Password Scheme”. In: Proceedings of the 1999
USENIX Annual Technical Conference, FREENIX Track. 1999, S. 81–91.
68 / 109
Exkurs: “Forgot your Password?”
I
viele (webbasierte) Dienste erfordern Authentifizierung
(Webmail, . . . )
I
im Falle eines verlorenen Passwortes wird eine
‘persönliche’ Frage vereinbart, deren korrekte
Beantwortung das Passwort zurücksetzt oder dem
Eigentümer per Mail zustellt
Beispiele:
I
I
I
I
“What is your mother’s maiden name?”
“What is your dog’s name?”
Diese Informationen sind insbesondere bei Prominenten
bzw. Netizens leicht recherchierbar!
Literatur: Herbert H. Thompson: How I Stole Someone’s
Identity. Scientific American, August, 2008
http://www.sciam.com/article.cfm?id=anatomy-of-a-social-hack
69 / 109
Exkurs: “Forgot your Password?”
Beispiel: Sarah Palin
I
Yahoo-Account von Vizepräsidentschaftskandidatin Sarah
Palin
I
Passwort wurde durch Unbekannte zurückgesetzt
(09/2008)
‘Sicherheits’fragen:
I
I
I
I
I
ZIP code
date of birth
“Where did you meet your husband?” → auf der Webseite
steht, dass sie ihren Mann seit Highschool-Zeiten kennt
und welche Highschool sie besuchte
Recherche dauerte ca. 45 Minuten
Quelle: http://www.itworld.com/security/55185/sarah-palingoes-way-paris-hilton
70 / 109
Rätsel
Welche der folgenden Fragen taugen nicht für das Rücksetzen
eines Passwortes? Können sie die folgenden Fragen für eine
fremde Person (z. B. mich) mit wenig Aufwand recherchieren?
Welche Ansätze für Recherchen gibt es?
1. What is my mother’s maiden name?
2. What was the brand of my first car?
3. What is the name of my best friend?
4. In which city did I grow up?
5. What was the lastname of my kindergarden teacher?
6. What is my favourite movie?
7. What is my dog’s name?
71 / 109
Challenge-Response-Verfahren
oder: „Wer über die Brücke des Todes will gehen, der muß drei mal Rede und Antwort stehen. Dann darf er die andere Seite
sehen.“
= Authentifizierung auf der Basis gemeinsamen Wissens
1. Server stellt eine Aufgabe (Challenge))
2. Nutzer (bzw. ein Stellvertreterprozeß) löst die Aufgabe
(antwortet; Response)
3. Lösung korrekt → Login erlaubt
Beispiel: Kopierschutz in alten Computerspielen.
I
Zu Beginn Frage, etwa: “Was steht im Handbuch auf
S.412, dritte Zeile, 2. Wort?”
I
richtiger Begriff → Spiel startet
I
falscher Begriff → Abbruch
72 / 109
Challenge-Response zur Authentifizierung
Ablauf:
1. Alice schickt Bob (dem Host) ihr Nutzerkennzeichen
2. Bob sendet eine Zufallszahl („Nonce“ - (random) number,
used once) an Alice ≡ Challenge
3. Alice verschlüsselt die Nonce mit dem Hash ihres
Passworts und schickt das Chiffrat an Bob ≡ Response
4. Bob verschlüsselt die Nonce ebenfalls mit Alice’
Passwort-Hash
5. ist das Chiffrat gleich der Antwort von Alice, so wird
Zugang gewährt
73 / 109
Beispiel: Authentifizierung in Windows
I
Authentifizierungsprotokoll NTLM - NT Lan Manager
I
Nachfolger des (unsicheren) LM-Authentifizierungsverfahrens
I
ursprünglich proprietär, daher reverse-engineered
I
mittlerweile durch Microsoft offengelegt
Grobablauf:
1. Client (Nutzer) schickt das NKZ mittels sog. Type-1-Nachricht an
den Server
2. Server (Host) antwortet mit einer Type-2-Nachricht, die u. a. eine
8 Byte lange Nonce enthält
3. Client verschlüsselt die Nonce mit dem Hash seines Passwortes
als Schlüssel, schickt Chiffrat als Type-3-Nachricht an Server
4. Server verschlüsselt ebenfalls Nonce mit Passworthash und
gewährt bei Identität beider Chiffrate Zugang zum System
Literatur: http://davenport.sourceforge.net/ntlm.html
74 / 109
Sicherheit von NTLM
Stellen
6
6
8
8
8
11
Zeichenraum
A-Za-z0-9
A-Za-z0-9, 22 SZ
A-Za-z0-9
A-Za-z0-9, 22 SZ
A-Za-z0-9, alle SZ
A-Za-z
Dauer
1 min
6 min
2 d, 17 h
33 d
82 d
270 a
Tabelle: Maximale Dauer der Ermittlung von NTLM-Passworten
mittels „Distributed Password Recovery“ (ElcomSoft)
22 SZ = typische Sonderzeichen, d.h.
_@#$&+-=%*"~!?.,:;()<>
I genutztes System: AMD Athlon X2 4850e, 2 Nvidia
GeForce 9800 GTX
Quelle: Stefan Arbeiter, Matthias Deeg: Bunte Rechenknechte.
In: c’t 06/2009, S. 205
I
75 / 109
Authentifizierung mit physischen Objekten
I
I
Schlüssel
Chipkarten
I
I
passiv – “Stored Value Cards”, z.B. Telefonkarten
aktiv – “Smart Cards”, ausgerüstet mit 8-Bit-CPU, Scratch
RAM, ROM, EEPROM
Server
PC
1. Challenge an Smart Card
3. Response an Server
Smart
Card
2. Smart Card errechnet Antwort
Abbildung: Nutzung einer Smartcard zur Authentifizierung
76 / 109
Smartcards
I
Smartcards können aktualisiert werden, z.B. bei Bruch des
verwendeten Kryptografie-Verfahrens
I
Problem: Verlust, Diebstahl
I
Power Analysis Attack, um Key zu ermitteln
I
Diebstahl eröffnet neue Angriffsvektoren; Tamper
Resistance nötig
77 / 109
Authentifizierung mittels biometrischer Merkmale
Idee: Erkennung/Authentikation einer Person anhand
individueller physischer Merkmale.
I
Gesichtsmerkmale (z. B. bei direkter
Mensch-Mensch-Authentikation)
I
Fingerabdrücke (wahrscheinlich einzigartig innerhalb der
gesamten Bevölkerung)
I
Geometrie der Hand (Form, Länge, Dicke der Finger)
I
Blutgefäße der Retina (ebenfalls einzigartig)
I
Unterschrift
I
Sprache
Probleme: False-Match, False-Nonmatch
78 / 109
Authentifizierung mit Public-Key-Kryptografie
Alternative: Public-Key-Kryptografie
1. Host sendet Alice einen Zufallsstring Z
2. Alice chiffriert Z mit ihrem privaten Schlüssel und schickt
das Chiffrat mit ihrem Namen an den Host
3. Host ruft Alice’ öffentlichen Schlüssel aus seiner
Datenbank und dechiffriert Nachricht
4. Stimmt Dechiffrat mit ursprünglichen String Z überein, so
erhält Alice Zugang zum System
79 / 109
Protokolle zum Schlüsselaustausch
Überblick
I
Austausch mittels symmetrischer Kryptografie
I
Austausch mittels Public-Key-Kryptografie
I
Beispiel: Diffie-Hellman-Protokoll
80 / 109
Schlüsselaustausch mit symmetrischer Kryptografie
Voraussetzungen: Vertrauenswürdige Instanz (Key Distribution
Center - KDC, aka Trent), sowohl Alice als auch Bob besitzen
Schlüssel zur Kommunikation mit Trent
Protokoll:
I Alice bittet Trent um Generierung eines Sitzungsschlüssels
zur Kommunikation mit Bob
I Trent generiert zufälligen Sitzungsschlüssel, generiert 2
Kopien, verschlüsselt eine mit Alice’ und eine mit Bobs
Schlüssel
I Trent schickt beide (verschlüsselte) Kopien an Alice
I Alice dechiffriert ihre Kopie des Sitzungsschlüssels
I Alice schickt Bob dessen (verschlüsselte) Kopie
I Bob dechiffriert seine Kopie des Sitzungsschlüssels
I Alice und Bob kommunizieren mittels des
Sitzungsschlüssels
81 / 109
Schlüsselaustausch mittels Public-Key-Kryptografie
. . . wie bereits unter „hybride Kryptosysteme“ diskutiert:
1. Alice bezieht Bobs öffentlichen Schlüssel aus dem KDC
2. Alice generiert einen zufälligen Sitzungsschlüssel und
verschlüsselt diesen mit Bobs öffentlichem Schlüssel
3. Alice sendet das Chiffrat an Bob
4. Bob dechiffriert die empfangene Nachricht mit seinem
privaten Schlüssel
5. Beide kommunizieren mit Hilfe des Sitzungsschlüssels
82 / 109
Man-in-the-Middle-Attack
Ablauf
1. Alice sendet Bob ihren öffentlichen Schlüssel
2. Mallory fängt diesen Schlüssel ab und schickt stattdessen
seinen eigenen öffentlichen Schlüssel an Bob
3. Bob sendet seinen öffentlichen Schlüssel an Alice
4. Mallory fängt auch diesen ab und schickt stattdessen
seinen öffentlichen Schlüssel an Alice
5. Sendet Alice eine mit Bobs11 öffentlichem Schlüssel
verschlüsselte Nachricht an Bob, fängt Mallory diese ab
und
I
I
I
I
I
I
11
entschlüsselt sie mit seinem privaten Schlüssel,
liest sie,
chiffriert sie mit Bobs öffentlichem Schlüssel und
schickt sie weiter an Bob.
Analog geht Mallory in der Rückrichtung (Bob → Alice) vor
Weder Alice noch Bob können diesen Angriff entdecken
d. h. , Mallorys
83 / 109
Das Interlock-Protokoll (Rivest/Shamir, 1984)
. . . erschwert oder vereitelt den Man-in-the-Middle-Attack
1. Alice sendet Bob ihren öffentlichen Schlüssel KA .
2. Bob sendet Alice seinen öffentlichen Schlüssel KB .
3. Alice chiffriert ihre Nachricht M1 mit KB und schickt die
Hälfte der verschlüsselten Nachricht an Bob.
4. Bob chiffriert seine Nachricht M2 mit KA und schickt die
Hälfte der verschlüsselten Nachricht an Alice.
5. Alice schickt die zweite Hälfte an Bob.
6. Bob fügt beide Hälften zusammen und dechiffriert. Danach
schickt er Alice seine zweite Hälfte.
7. Alice setzt Bobs zweite Nachricht zusammen und
dechriffriert.
84 / 109
Analyse des Interlock-Protokolls
I
Mallory kann nicht dechiffrieren, weil er nur eine halbe
Nachricht hat
I
er muss aber mit seinem privaten Schlüssel dechiffrieren,
um anschließend mit Bobs öffentlichem Schlüssel zu
chiffrieren
I
er muss eine andere Nachricht erfinden, und die Hälfte
davon an Bob schicken (und zurück an Alice)
Wenn Alice und Bob ihre Nachrichten vorher absprechen12 ,
können sie mit dem Interlock-Protokoll die Authentizität ihrer
jeweiligen öffentlichen Schlüssel prüfen und Mallory entlarven.
12
Dafür ist aber ein sicherer Kanal notwendig.
85 / 109
Schlüsselaustausch mit digitaler Signatur
Idee:
I
Trent signiert die öffentlichen Schlüssel von Bob und Alice
I
Beim Schlüsselerhalt prüfen Alice und Bob Trents Signatur
I
→ Mallory kann nicht mehr in deren jeweilige Rolle
schlüpfen!
86 / 109
Schlüsselaustausch mittels Diffie-Hellman-Protokoll
1. Bob und Alice einigen sich auf eine große Primzahl n und
eine Zahl g.
2. Alice wählt eine (große) zufällige Zahl x (Alice’ geheimer
Schlüssel) und berechnet X = g x mod n (Alice’ öffentlicher
Schlüssel).
3. Alice sendet X an Bob.
4. Bob wählt eine (große) zufällige Zahl y (Bobs geheimer
Schlüssel) und berechnet Y = g y mod n (Bobs öffentlicher
Schlüssel).
5. Bob sendet Y an Alice.
6. Alice berechnet
k = Y x mod n = (g y mod n)x mod n = g xy mod n, den
geheimen Sitzungsschlüssel.
7. Bob berechnet
k = X y mod n = (g x mod n)y mod n = g xy mod n.
87 / 109
Anmerkungen zum Diffie-Hellman-Protokoll
I
I
g muss primitiv modulo n sein, d.h. es muss stets ein a
geben, so dass g a ≡ b mod n ∀ 1 ≤ b < n.
Eve kann X und Y abfangen, es nützt ihr aber nichts, sie
kann g xy mod n nicht aus g x mod n und g y mod n
berechnen.
Beispiel:
Alice
g = 4,
Bob
n = 11
x =3
y =4
X = 43 mod 11 = 9
Y = 44 mod 11 = 3
X =9→B
A←Y =3
Yx
k=
mod n
3
= 3 mod 11 = 5
k = X y mod n
= 94 mod 11 = 5
88 / 109
Authentifizierung und Schlüsselaustausch
Überblick
Ziel: Alice und Bob wollen sich gegenseitig authentifizieren und
sicher miteinander kommunizieren (→ Schlüsselaustausch)
I
Wide-Mouthed-Frog (Breitmaulfrosch)
I
Needham-Schroeder-Protokoll
I
Kerberos
89 / 109
Wide-Mouthed-Frog (1989)
I
Voraussetzung: Alice und Bob benötigen geheimen
Schlüssel zur Kommunikation mit Trent
Ablauf13 :
1. Alice konkateniert einen Zeitstempel TA , Bobs Namen und
einen zufälligen Sitzungsschlüssel KAB und chiffriert alles
mit dem Schlüssel KAT für Trent-Alice. Sie sendet ihren
Namen und das Chiffrat an Trent:
A, {TA , B, KAB }KAT → Trent
2. Trent dechiffriert die Nachricht. Dann konkateniert er einen
weiteren Zeitstempel TT , Alice’ Namen und den
Sitzungsschlüssel KAB . Alles wird mit dem Schlüssel KBT
für Trent-Bob chiffriert und an Bob geschickt:
{TT , A, KAB }KBT → Bob
13
Michael Burrows, Martin Abadi und Roger Needham. A Logic of Authentication. Techn. Ber. SRC-RR-39. Palo
Alto, CA: Digital Equipment Corporation Systems Research Center, Feb. 1989.
90 / 109
Wide-Mouthed-Frog-Protokoll
Grafische Veranschaulichung
Trent
1.
A, {TA , B, KAB }KAT
Alice
2.
{TT , A, KAB }KBT
Bob
91 / 109
Wide-Mouthed-Frog
Anmerkungen
I
keine direkte Authentifizierung von A und B
I
sehr simpel; nur zwei Nachrichten sind notwendig
I
Alice muss in der Lage sein, einen sehr guten
Sitzungsschlüssel zu generieren (Zufallszahlen sind
schwierig zu generieren!) – Bob vertraut Alice
dahingehend
I
Zeitstempel verhindern (bzw. erschweren) Replay-Attacke
I
erfordert eng synchronisierte Uhren
I
zustandbehaftetes Protokoll: Was tut Trent, wenn Bob nicht
antwortet?
92 / 109
Needham-Schroeder-Protokoll (1978)
Voraussetzungen:
I symmetrisch, Trent benötigt
I Alice und Bob verfügen über geheime Schlüssel KAT
bzw. KBT , um mit Trent zu kommunizieren.
Ablauf14 :
1. Alice generiert eine Zufallszahl NA und schickt diese mit
ihrem und Bobs Namen an Trent:
(A, B, NA ) → Trent
2. Trent generiert einen zufälligen Sitzungsschlüssel KAB für
Alice und Bob.
3. Trent chiffriert mit KBT eine Nachricht (für Bob), die KAB
und Alice’ Namen enthält.
KBT (KAB , A)
14
Roger M. Needham und Michael D. Schroeder. “Using Encryption for Authentication in Large Networks of
Computers”. In: Communications of the ACM 21.12 (Dez. 1978), S. 993–999.
93 / 109
Needham-Schroeder-Protokoll
Teil 2
4. Trent chiffriert NA , Bobs Namen, KAB und das eben
generierte Chiffrat mit KAT und schickt dieses an Alice.
KAT (NA , B, KAB , KBT (KAB , A)) → Alice
5. Alice entschlüsselt die Nachricht, extrahiert KAB und prüft,
ob NA der in Schritt 1 generierten Zufallszahl entspricht.
6. Falls ja, so schickt sie die für Bob bestimmte Subnachricht
an diesen
KBT (KAB , A) → Bob
7. Bob dechiffriert die Nachricht und extrahiert KAB . Dann
generiert er eine zweite Zufallszahl NB , chiffriert diese mit
KAB und schickt die Nachricht an Alice.
KAB (NB ) → Alice
94 / 109
Needham-Schroeder-Protokoll
Teil 3
8. Alice dechriffriert die Nachricht mittels KAB . Sie generiert
NB − 1, chiffriert diese Zahl mit KAB und sendet das
Chiffrat an Bob:
KAB (NB − 1) → Bob
9. Bob dechiffriert diese Nachricht und prüft, dass NB − 1
gesendet wurde.
95 / 109
Needham-Schroeder-Protokoll
Grafische Veranschaulichung
Trent
1. A, B, NA
2.
{NA , B, KAB , {KAB , A}KBT }KAT
3. {K , A}
AB
KBT
4.
Alice
5.
{NB }KAB
Bob
{NB − 1}KAB
96 / 109
Needham-Schroeder-Protokoll
Diskussion
I
Zufallszahlen (Nonces) NA , NB dienen der Verhinderung
von Replay-Angriffen: Mallory zeichnet Nachrichten auf
und versucht damit (später) die Integrität des
Datenverkehrs zu unterwandern
I
Hier: Mallory könnte durch Aufzeichnung und Replay der
Nachrichten 2 und 3 die Kommunikationspartner zwingen,
einen alten (kompromittierten) Schlüssel KAB
weiterzuverwenden
Resultat des Algorithmus
I
Generierung eines geeigneten Schlüssels durch Trent
I
Verteilung des Schlüssels zwischen Alice und Bob
I
Alice authentifiziert sich gegenüber Bob durch Nachricht 5
(Challenge-Response)
97 / 109
Needham-Schroeder-Protokoll
Schwäche: kompromittierter Schlüssel erlaubt Replay-Attacke
I
Bob hat keine Möglichkeit zu testen, ob der Schlüssel KAB
frisch generiert wurde
I
wenn Mallory in den Besitz irgendeines alten Schlüssels
0 kommt, kann er Nachricht 3 aufzeichnen und später
KAB
wieder Bob vorspielen (Replay-Attacke)
I
Bob generiert die Nonce NB , verschlüsselt sie mit dem
0 und schickt sie an Alice
empfangenen KAB
I
0 ,
Mallory fängt diese Nachricht ab, entschlüsselt sie mit KAB
0
berechnet NB − 1 und schickt das Ergebnis mit KAB
verschlüsselt wieder an Bob
I
fortan ist Mallory gegenüber Bob als Alice
authentifiziert!
→ Needham-Schroeder-Protokoll als fehlerhaft angesehen →
Zeitstempel/Gültigkeitsintervall für Schlüssel nötig → Kerberos
98 / 109
Kerberos
Überblick
I
Protokoll zur Authentifizierung in TCP/IP-basierten Netzen
I
Ziel: Einrichtung sicherer Kommunikationskanäle zwischen
einem Client und beliebigen Servern in einem verteilten
System
I
Weiterentwicklung des Needham-Schroeder-Protokolls
I
basierend auf symmetrischer Verschlüsselung
I
erfordert vertrauenswürdige Instanz (Trent)
I
jeder Teilnehmer besitzt geheimen Schlüssel zur
Kommunikation mit Trent
I
Identitätsbeweis = Kenntnis des Schlüssels
I
Versionen 4 und 5 (RFC 4120)
99 / 109
Wer ist Kerberos (auch „Cerberus“) eigentlich?
I
ein-, drei- oder fünfzigköpfiger Hund, der den Hades, die
Unterwelt in der griechischen Mythologie, bewacht
„Auch den Kerberos sah ich, mit bissigen Zähnen bewaffnet
Böse rollt er die Augen, den Schlund des Hades bewachend.
Wagt es einer der Toten an ihm vorbei sich zu schleichen,
So schlägt er die Zähne tief und schmerzhaft ins Fleisch der Entfliehenden
Und schleppt sie zurück unter Qualen,
Der böse, der bissige Wächter.“
(Odyssee)
Abbildung: Kerberos, gezeichnet von Pearson Scott Foresman
100 / 109
Von Needham-Schroeder zu Kerberos
Basisprotokoll
Idee: Aufnahme eines Zeitstempels, um Replay-Attacken
effektiver zu bekämpfen.
Ablauf15 :
1. Alice sendet an Trent eine Nachricht mit ihrer und Bobs
Identität:
(A, B) → Trent
2. Trent generiert einen Sitzungsschlüssel KAB .
3. Trent generiert eine Nachricht mit Zeitstempel TT ,
Geltungsdauer L, KAB und Alice’ Identität und chiffriert
diese mit Bobs Schlüssel KBT .
KBT (TT , L, KAB , A)
15
Jennifer G. Steiner, Clifford Neuman und Jeffrey I. Schiller. “Kerberos: An Authentication Service for Open
Network Systems”. In: Proceedings of the USENIX Winter Conference. Dallas, TX, Feb. 1988, S. 191–202.
101 / 109
Kerberos
Basisprotokoll, contd.
4. Trent generiert eine analoge Nachricht, jedoch mit Bobs
Identität, die er mit Alice’ Schlüssel KAT chiffriert.
KAT (TT , L, KAB , B)
5. Trent schickt beide Nachrichten an Alice.
KBT (TT , L, KAB , A), KAT (TT , L, KAB , B) → Alice
6. Alice generiert eine Nachricht mit ihrer Identität und einem
Zeitstempel und verschlüsselt diese mit KAB .
KAB (TA , A)
7. Alice schickt diese und Trents Nachricht an Bob.
KAB (TA , A), KBT (TT , L, KAB , A) → Bob
102 / 109
Kerberos
Basisprotokoll, contd.
8. Bob generiert eine Nachricht mit dem von Alice
empfangenen Zeitstempel TA + 1 , chiffriert diese mit KAB
und schickt sie an Alice.
KAB (TA + 1) → Alice
I
jeder Empfänger prüft die erhaltenen Zeitstempel auf
Aktualität → Replay-Attacken wirkungslos
I
viele Varianten existieren; ggf. werden Nonces
hinzugenommen
I
Voraussetzung: Alice, Bob und Trent haben sichere und
synchronisierte Uhren!
103 / 109
Basisprotokoll bei Kerberos
Grafische Veranschaulichung
Trent
1.
A, B
2.
{TT , L, KAB , B}KAT , {TT , L, KAB , A}KBT
3.
{TT , L, KAB , A}KBT , {TA , A}KAB
Alice
4.
Bob
{TA + 1}KAB
104 / 109
Tickets und Authentikatoren
Kerberos unterscheidet zwei Formen der Legitimation:
Ticket
I
durch Kerberos erzeugt
I
zur sicheren Übertragung der Identität eines
dienstanfordernden Clients c an einen Server s
I
mit geheimem Schlüssel Ks des Servers verschlüsselt
I
besitzt Geltungsdauer, innerhalb derer der Client Anfragen
an den Server stellen kann
Authentikator
I
zusätzliche Legitimation
I
durch Client erzeugt
I
wird dem Server gemeinsam mit Ticket präsentiert
105 / 109
Struktur eines Tickets
Tc,s = s, {c, a, v , Kc,s } Ks
mit
Symbol
Bedeutung
s
Server
c
Client
a
IP-Adresse des Clients
v
Geltungsdauer des Tickets
Kx,y
Kx
{m}Kx
Sitzungsschlüssel für x und y
geheimer Schlüssel von x
Nachricht m, mit Kx verschlüsselt
106 / 109
Struktur eines Authentikators
Ac,s = {c, t, Schlüssel} Kc,s
mit
Symbol
Bedeutung
c
Client
t
Zeitstempel
Kx,y
Schlüssel
Sitzungsschlüssel für x und y
weiterer (optionaler )Sitzungsschlüssel
107 / 109
Kerberos
Überblick Authentifizierungsschritte
Authentication Server
Ticket Granting Server
Kerberos
3: Anforderung
Serverticket
TGS
2: TGT
4: Serverticket
1: Anforderung TGT
Client
Server
5: Dienstanforderung
108 / 109
Was haben wir gelernt?
1. Kryptografische Hashes
2. Signaturen
3. Schlüsselaustauschprotokolle
4. Authentifizierung
5. Schlüsselaustausch und Authentifizierung
6. einige Formen von Angriffen
I
I
I
I
I
Brute Force
Replay-Attacke
Man-in-the-Middle-Attack
Social Engineering
Wörterbuchangriff
7. Authentifizierung und Schlüsselaustausch
I
I
I
Wide-Mouthed-Frog
Needham-Schroeder-Protokoll
Kerberos
109 / 109