Cryptography Reference
In-Depth Information
Das Schema HashMAC
[
H
,p,
M
]
wird
Hash-then-MAC-Schema
mit Basisschema
M
,
Füllfunktion
p
und Hashfamilie
genannt. Hash-then-MAC-Schemen basierend auf
unbeschränkten Hashfunktionen werden analog definiert.
H
Sicherheit des Hash-then-MAC-Schemas. Wir wollen nun - wie gewohnt - die
Sicherheit eines Hash-then-MAC-Schemas auf die Sicherheit seiner Bestandteile zurück-
führen, d. h., auf die Sicherheit des Basis-Authentifizierungsschemas sowie die Sicherheit
der Hashfamilie.
Für die Definition der Sicherheit des Basis-Authentifizierungsschemas greifen wir ein-
fach auf die Definitionen aus Abschnitt 9.2 zurück. Kollisionsresistenz für Familien von
Hashfunktionen wurde bereits in Abschnitt 8.2 definiert. Um die Sicherheit des Hash-
then-MAC-Schemas zu garantieren, reicht allerdings die schwache Kollisionsresistenz.
Bei der schwachen Kollisionsresistenz wird dem Kollisionsfinder
nicht
der Index
k
der betrachteten Hashfunktion
h
k
als Parameter übergeben (vgl. Definitionen 8.2.1 und
8.2.2), sondern lediglich das zugehörige Hashorakel
h
k
(
)
. Der Kollisionsfinder weiß also
nicht von vornherein, mit welcher Hashfunktion er es zu tun hat. Dies kann er nur durch
Anfragen an das Hashorakel herausfinden. Die Aufgabe des Kollisionsfinders bleibt aller-
dings unverändert: Er soll eine Kollision für die Funktion
h
k
ausgeben (obwohl er nicht
k
,
sondern nur das Orakel
h
k
(
·
)
gegeben hat). Dies stellt im Allgemeinen eine höhere Anfor-
derung an den Kollisionsfinder dar. Umgekehrt sinkt damit die Sicherheitsanforderung an
die Familie von Hashfunktionen, weshalb wir von schwacher Kollisionsresistenz sprechen.
Eine solche schwächere Anforderung an die Sicherheit von Familien von Hashfunktionen
ist natürlich wünschenswert, um insgesamt die Sicherheitsgarantien zu erhöhen. Aller-
dings sei auch erwähnt, dass in manchen Fällen die schwache Kollisionsresistenz keine
wirklich schwächere Anforderung an eine Familie darstellt als die (starke) Kollisionsresis-
tenz (siehe dazu Aufgabe 9.8.11).
Wir geben nun eine präzise Definition für die schwache Kollisionsresistenz an. Dazu
wiederholen wir im Wesentlichen die Definitionen aus Abschnitt 8.2 mit kleinen Ände-
rungen.
·
Definition 9.4.2 (Angreifer/Kollisionsfinder im Kontext der schwachen Kollisionsresis-
tenz). Es sei
h
k
}
k∈K
eine Familie von Hashfunktionen mit Hashbreite
l
.Ein
An-
greifer
oder
Kollisionsfinder
A
für
H
ist ein zufallsgesteuerter Algorithmus
A
(
H
:
D →
{
H
=
{
}
∗
, dessen Laufzeit durch eine Konstante nach oben beschränkt
ist, wobei
D
den Wertebereich der Hashfunktionen in
l
):
}
∗
×{
0
,
1
}
{
0
,
1
0
,
1
H
bezeichnet.
Definition 9.4.3 (Experiment und Vorteil für schwache Kollisionsresistenz). Es sei
A
ein
Angreifer für die Familie
H
=
{
h
k
}
k∈K
von Hashfunktionen mit Hashbreite
l
. Das zuge-
E
weak
A
E
weak
bezeichnen, ist der Algorithmus,
hörige
Experiment
,daswirmit
oder einfach
der gegeben ist durch:
E
weak
:
}
1.
Indexwahl
k
=
flip
(
K
)
2.
Kollisionsberechung
(
x
0
,x
1
)=
A
(
h
k
(
{
0
,
1
·
))
