Symmetrische Authentifizierungsverfahren - Moderne Kryptographie - page 216

ii. Überprüfe, ob Kollision vorliegt.
falls v ∈{v | es gibt ein x mit ( x ,v ) ∈ S}

Bestimme x , so dass ( x ,v )

∈ S .

gib ( x, x ) zurück
sonst
gib ( x, x ) zurück

E M

Wie im Fall von F und F kann auch hier eine Bijektion zwischen den Läufen von

F und
E wea C in offensichtlicher Weise angegeben werden. Es gibt also eine direkte Korrespondenz
zwischen den Läufen. Wir zeigen nun:

E M Lemma 9.4.2. Ist in einem Lauf α von

F die Berechnung von F zulässig, aber die
Berechnung von F im korrespondierenden Lauf α von E F ist nicht zulässig, dann liefert
C im zu α korrespondierenden Lauf von E weak

C

eine Kollision.

Beweis. Wir nehmen an, dass ( x, t ) im Lauf α von F ausgegeben wird und die Be-
rechnung von F in diesem Lauf zulässig ist, d. h., x wurde in diesem Lauf nicht an das
Etikettierorakel übergeben. Es bezeichne ( k h ,k m ) den vom Etikettierorakel in α verwen-
deten Schlüssel.
Im korrespondierenden Lauf α von E F gibt F das NE-Paar ( x ,t ) mit x = p ( h k m ( x ))

zurück. Wenn die Berechnung von F in diesem Lauf nicht zulässig ist, dann muss in
dieser Berechnung für eine Nachricht x ,dievon F an sein Etikettierorakel T ( , ( k h ,k m ))

übergeben wurde, der Wert x = p ( h k h ( x )) ,dervon F an sein Etikettierorakel T ( ·,k m )
übergeben wurde, mit x übereinstimmen.
Es sei nun x eine beliebige Nachricht dieser Art. Zunächst gilt h k h ( x )= h k h ( x ) ,da p
injektiv ist. Andererseits kann nicht x = x gelten, denn sonst wäre die Berechnung von
F nicht zulässig gewesen. Also ist ( x, x ) eine Kollision für h k h . Der Kollisionsfinder C
gibt aber im zu α korrespondierenden Lauf gerade ein solches Paar zurück.

·

AusdenbeidenvorangehendenLemmaserhaltenwirnunfolgendenSatz.

M = HashMAC [ H ,p,M ] ein Hash-then-MAC-Schema gemäß De-
finition 9.4.1. Es sei weiterhin F

Satz 9.4.1. Es sei

M

ein Fälscher für und es seien F und C wie oben

definiert. Dann gilt:

adv MAC ( F , M ) ≤ adv MAC ( F, M )+ adv weakColl ( C, H ) . (9.4.1)

E M
F

EZ die Berechnung von F

Beweis. Es sei das Ereignis, dass in einem Lauf von

E M
F

erfolgreich und zulässig ist. Formal ist EZ also eine Teilmenge von Läufen von .Es

E F zulässig ist. sei weiter Z das Ereignis, dass die Berechnung von F in einem Lauf von

E M
F

E M
F

Formal interpretieren wir Z als Teilmenge der Läufe von

, die einen Lauf in

E F

enthält genau dann, wenn der korrespondierende Lauf in zulässig ist.

Offensichtlich gilt nun:

adv MAC ( F , M )=Prob {EZ}

=Prob +Prob EZ ∩ Z

{EZ ∩ Z }