Cryptography Reference
In-Depth Information
Bei der Konstruktion von in der Praxis verwendeter Hashfunktionen wird - wie bei
der Konstruktion von Verschlüsselungsschemen - ein modularer Ansatz verfolgt. Man
setzt Hashfunktionen aus kleineren Bausteinen zuammen und reduziert die Sicherheit der
Hashfunktion auf die Sicherheit der Bausteine. Genauer werden wir dies in Abschnitt 8.4
studieren. Vorher müssen wir uns natürlich überlegen, was wir unter einer sicheren Hash-
funktion verstehen wollen.
8.2
Sicherheitsanforderungen an Hashfunktionen
Wenn wir von Szenarium 6 ausgehen, dann ist die erste offensichtliche Forderung an die
Sicherheit einer Hashfunktion, dass es für Eva »schwierig« sein sollte, zu gegebenen Daten,
also einem Bitvektor
x
, einen weiteren Bitvektor
x
zu gewinnen, für den
h
(
x
)=
h
(
x
)
gilt. Wenn wir
v
=
h
(
x
)
setzen, dann heißt dies, dass es schwierig sein soll, ein weiteres
Element, neben
x
,in
h
−
1
(
v
)
zu finden. In diesem Fall nennt man die Hashfunktion
zweites-Urbild-resistent
(
2nd preimage resistant
).
Eine stärkere Forderung, auf die wir uns in diesem Buch konzentrieren wollen, besagt,
dass es überhaupt nur »schwer« möglich sein soll, zwei verschiedene Bitvektoren
x
und
x
zu finden, so dass
h
(
x
)=
h
(
x
)
gilt. In diesem Fall spricht man von einer
kollisionsresis-
tenten
(
collision-resistent
) Hashfunktion. Ein Paar
(
x, x
)
mit
x
=
x
und
h
(
x
)=
h
(
x
)
nennt man eine
Kollision
für
h
.
Wie definiert man nun Kollisionsresistenz formal? Was soll insbesondere »schwer« in
der obigen, informellen Beschreibung bedeuten? Bisher haben wir »schwer« immer wie
folgt formalisiert: Jeder (ressourcenbeschränkte) Algorithmus erreicht sein Ziel, in unse-
rem Fall also das Ausgeben einer Kollision, nur mit »geringer« Wahrscheinlichkeit. Diese
Definition wäre allerdings völlig sinnlos. Zunächst ist festzustellen, dass jede Hashfunk-
tion eine Kollision besitzt, da nach Definition einer Hashfunktion der Definitionsbereich
größer als der Bildbereich ist. Also gibt es auch immer einen Algorithmus, der eine Kolli-
sion ausgibt: Ist nämlich
(
x, x
)
eine Kollision, so könnte ein solcher Algorithmus einfach
darin bestehen, das Paar
(
x, x
)
auszugeben.
Was wir mit Kollisionsresistenz eigentlich sagen wollen ist, dass es für uns (Menschen)
»schwer« ist, einen solchen Algorithmus zu finden. Für diese Intuition eine zufriedenstel-
lende mathematische Definition zu finden, ist allerdings noch nicht gelungen. Deshalb
behilft man sich wie folgt:
Statt eine einzelne Hashfunktion
h
zu betrachten, geht man zu einer Familie
h
k
}
k∈K
von Hashfunktionen mit Indexmenge
K
über. Dabei sollten die Hashfunktionen alle den-
selben Definitionsbereich besitzen. Typischerweise weisen Hashfunktionen in einer solchen
Familie auch dieselbe Struktur auf; sie unterscheiden sich z. B. lediglich durch ihren Initia-
lisierungsvektor. Kollisionsresistenz bedeutet nun, dass der Angreifer für ein gegebenes,
ihm bekanntes
k
keine Kollision für
h
k
finden können sollte. Da
k
dem Angreifer bekannt
ist, nennen wir
k
nicht »Schlüssel«, sondern »Index«. Ist die Indexmenge
K
sehr groß,
z. B.
{
=2
128
, so kann sich ein realistischer, ressourcenbeschränkter Angreifer lediglich
für einen Bruchteil der
k
|
K
|
K
eine Kollision für
h
k
merken. Wird nun ein
k
zufällig
aus
K
gewählt, so sollte also die Wahrscheinlichkeit, dass der Angreifer für dieses
k
ei-
ne Kollision für
h
k
ausgeben kann, sehr klein sein. Dies stimmt natürlich nur, wenn die
∈
