Cryptography Reference
In-Depth Information
gelingt es in manchen Fällen, aus der Tatsache, dass eine Familie von Hashfunktionen
nicht stark kollisionsresistent ist, zu folgern, dass sie nicht schwach kollisionsresistent ist.
In dieser Aufgabe betrachten wir ein Beispiel dazu.
Es sei
f
eine
(
l,b
)
-Kompressionsfunktion,
p
eine MD-kompatible
(
r, b
)
-Füllfunktion
und
h
k
}
k∈{
0
,
1
}
l
mit
h
k
=
h
f,
k
die zugehörige Familie iterierter Hashfunktionen.
Wir nehmen an, dass ein Kollisionsfinder
A
auf
H
im Sinne von Definition 8.2.2 (starke
Kollisionsresistenz) gegeben ist. Wir nehmen weiter an, dass für die von diesem Kollisi-
onsfinder ausgegebenen Kollisionen der Form
(
x
0
,x
1
)
gilt, dass
x
0
und
x
1
gleiche Länge
haben. Konstruieren Sie aus diesem Kollisionsfinder einen Kollisionsfinder
A
auf
H
=
{
im
Sinne von Definition 9.4.3 (schwache Kollisionsresistenz), so dass der Vorteil von
A
durch
denjenigen von
A
beschränkt werden kann.
Hinweis zur Konstruktion von
A
: Zunächst wird
h
k
auf eine fest gewählte Nachricht
x
angewendet. Es sei
H
simuliert. Es sei
(
x
0
,x
1
)
das von
A
gelieferte Nachrichtenpaar. Ist
(
x
0
,x
1
)
eine Kollision für
h
IV
(
IV
=
h
k
(
x
)
.Dannwird
A
mit Eingabe
IV
·
)
, so kann daraus
eine Kollision für
h
k
(
)
konstruiert werden (siehe dazu auch Aufgabe 9.8.8).
Aufgabe
9.8.12 (Beweis von Aussage (9.7.2))
.
Beweisen Sie Aussage (9.7.2). Geben Sie
dazu, wie vor dieser Aussage angedeutet, eine geeignete bijektive Abbildung zwischen
den Läufen der betrachteten Ereignisse an.
Aufgabe
9.8.13 (Güte der Reduktion von Satz 9.7.1)
.
Schätzen Sie auf Basis von Satz 9.7.1
die Unsicherheit des Schemas
·
ab.
Aufgabe
9.8.14 (CCA-Sicherheit)
.
Zeigen Sie, dass für den Beweis von Satz 9.7.1 die
Annahme, dass eine Nachricht nur ein gültiges Etikett haben kann, notwendig ist. Kon-
struieren Sie dazu einen MAC gemäß der Definition aus Aufgabe 9.8.1, bei dem eine
Nachricht mehrere gültige Etiketten haben kann, und zeigen Sie, dass unter Benutzung
dieses MACs das Schema
S
CCA
durch diejenige von
S
CPA
und
M
S
CCA
keine CCA-Sicherheit bietet, indem Sie einen Angreifer
auf dieses Schema angeben, der einen großen Vorteil besitzt.
9.9
Anmerkungen und Hinweise
Die Ursprünge des Konzeptes der symmetrischen Authentifizierung werden im Lehrbuch
von Goldreich [81] kurz diskutiert. Die Definition der Sicherheit von MACs, die wir in
Abschnitt 9.2 kennengelernt haben, geht auf eine Arbeit von Bellare, Kilian und Rogaway
[20, 21] zurück und baut direkt auf dem Begriff der Sicherheit von digitalen Signaturen auf,
wie er von Goldwasser, Micali und Rivest geprägt wurde [87] (siehe auch Abschnitt 10.1).
In [18] wird die nach Definition 9.2.2 kurz diskutierte Variante des Sicherheitsbegriffs für
MACs betrachtet, in der dem Fälscher zusätzlich zum Etikettierorakel Zugriff auf ein Va-
lidierungsorakel gegeben wird. Die Beziehung zwischen diesem und dem ursprünglichen
Sicherheitsbegriff wird in [17] ausführlich untersucht (siehe auch Aufgabe 9.8.2). Ein
noch stärkerer Sicherheitsbegriff (
strong unforgeability
) wird in [23] eingeführt. Hier wird
verlangt, dass ein Fälscher nicht nur zu einer
neuen Nachricht
kein gültiges Etikett be-
stimmen kann, sondern, dass er nicht einmal ein
neues gültiges Etikett
zu einer Nachricht
bestimmen kann, zu der er bereits ein gültiges Etikett kennt. Diese zusätzliche Forderung
ist allerdings trivialerweise erfüllt für MACs mit deterministischem Etikettieralgorithmus,
