Cryptography Reference
In-Depth Information
h
(
k,k
)
}
(
k,k
)
∈
(
K,K
)
die unbeschränkte
l
-Hashfunktion, die definiert
ist durch
h
(
k,k
)
(
x
)=
h
k
(
h
k
(
x
))
für alle
x
H
=
2. Es sei
{
}
∗
. Schätzen Sie den Vorteil eines
∈{
0
,
1
H
möglichst gut durch die Vorteile geeignet konstruierter Angreifer
Angreifers auf
H
ab. Beweisen Sie Ihre Aussage.
3. Diskutieren Sie die Vor- und Nachteile der beiden oben betrachteten Konstruktionen
bzgl. Sicherheit und E
zienz.
Aufgabe
8.6.4 (Geburtstagsangriff)
.
In dieser Aufgabe wollen wir zeigen, dass man die
Annahme (8.3.1) tatsächlich ohne Einschränkung machen kann. Es seien dazu
l<L
und
h
:
H
auf
und
l
.
1. Bestimmen Sie die Wahrscheinlichkeit dafür, dass der Geburtstagsangreifer
Ge-
burstsfinder(
k
)
aus Abschnitt 8.3 keine Kollision für
h
(
=
h
k
) findet, in Abhän-
gikeit von der Größe der Mengen
|h
−
1
(
v
)
L
{
0
,
1
}
→{
0
,
1
}
l
.
2. Zeigen Sie, dass obige Wahrscheinlichkeit genau dann maximal ist, wenn für alle
v
|
,
v
∈{
0
,
1
}
l
die Mengen
h
−
1
(
v
)
gleich groß sind.
Hinweis: Ein recht elementarer Ansatz ist der folgende. Man zeigt, wenn nicht alle
Mengen
∈{
0
,
1
}
|
|
h
−
1
(
v
)
gleich groß sind, dass die Wahrscheinlichkeit aus 1. wächst, wenn
man ein Element aus einer zu großen Menge in eine zu kleine Menge verschiebt. Dar-
aus folgt dann die Behauptung. Ein alternativer Ansatz ist, die Wahrscheinlichkeit
aus 1. zu maximieren (mit Nebenbedingung), in dem man klassische Methoden der
Analysis verwendet (Gradient Null setzen, Definitheit der Hesse-Matrix untersuchen,
Randextrema ausschließen).
Aufgabe
8.6.5 (Sicherheit des Merkle-Damgård-Prinzips)
.
Schätzen Sie auf Basis von Fol-
gerung 8.4.1 die Unsicherheit von
|
|
H
durch diejenige von
C
im Sinne von Definition 8.2.3
ab.
Aufgabe
8.6.6 (Zweck des Auffüllens)
.
Es sei
f
eine
(
l,b
)
-Kompressionsfunktion und
u
∈
{
0
,
1
}
l
. Wir betrachten die Hashfunktion
h
(
x
)=
i
f
(
u, x
)=
f
(
f
(
...f
(
f
(
u, x
0
)
,x
1
)
,...,x
n−
2
)
,x
n−
1
)
b∗
. (Wir ignorieren hier die Tatsache, dass
h
nur für
für alle
x
=
x
0
...x
n−
1
∈{
0
,
1
}
b∗
definiert ist und somit formal keine Hashfunktion ist.) Diese Kon-
struktion hat den schwerwiegenden Nachteil, dass es im Allgemeinen nicht mehr möglich
ist, eine Kollision für
h
auf eine Kollision für
f
zurückzuführen. Um dies einzusehen,
nehmen wir einmal an, es gäbe einen Bitvektor
v ∈{
0
,
1
}
Eingaben
x
∈{
0
,
1
}
b
mit
f
(
u, v
)=
u
. Dann würde
b∗
gelten:
für jedes
x
∈{
0
,
1
}
h
(
vx
)=
i
f
(
u, vx
)=
i
f
(
f
(
u, v
)
,x
)=
i
f
(
u, x
)=
h
(
x
)
.
b∗
wäre
(
x, vx
)
eine Kollision für
h
.
2
Dass solche Kompressionsfunktionen vorstellbar sind, wollen wir in dieser Aufgabe
beweisen. Zeigen Sie dazu, dass man zu jeder Kompressionsfunktion
f
eine Kompressi-
onsfunktion
f
konstruieren kann, die folgende Bedingungen erfüllt:
1. Es gibt ein
v
mit
f
(
u, v
)=
u
.
Mit anderen Worten, für jedes
x
∈{
0
,
1
}
2 Dieser »Fixpunktangriff« wurde in [128] vorgeschlagen.
