Cryptography Reference
In-Depth Information
Der Intuition folgend, dass, wenn G eine zufällige Funktion ist, F ein gültiges Etikett für
eine neue Nachricht nur raten kann, erhält man auch leicht:
)=Prob S
=1
PRF
U
fail PRF ( U,
B
b =0
1
2 l
.
(9.3.2)
Der Beweis von (9.3.2) soll in Aufgabe 9.8.3 geführt werden.
Insgesamt erhalten wir:
)+ 1
2 l
adv MAC ( F,
M B )
adv PRF ( U,
B
.
Aus dem PRF/PRP-Switching Lemma folgt damit:
)+ q
·
( q
1)
+ 1
2 l
adv MAC ( F,
M B )
adv ( U,
B
.
2 l +1
Man überzeugt sich schließlich noch leicht davon, dass U ( q,t + c
·
l
·
q
·
log( q )) -beschrän kt
ist, für eine kleine Konstante c (siehe Aufgabe 9.8.3).
M B kann
aber leicht auf Nachrichten x = x 0 ···x n− 1 mit beliebig vielen l -Blöcken x 0 ,...,x n− 1
{
Wie erwähnt ist
M B auf Nachrichten der Länge l beschränkt. Der MAC
l
M B auf jeden
der Blöcke x i anzuwenden. Das resultierende Etikett für x ist also T ( x 0 ,k ) ...T ( x n− 1 ,k ) .
Allerdings muss man dieses Schema noch durch drei zusätzliche Komponenten in jedem
Block ergänzen, um einen sicheren MAC zu erhalten:
1. Man muss verhindern, dass Nachrichten unbemerkt umgeordnet werden können.
Deshalb hängt man vor jeden Block x i noch einen Zähler i .
2. Man muss verhindern, dass das Ende einer Nachricht unbemerkt abgeschnitten wer-
den kann. Dies erreicht man zum Beispiel dadurch, dass man jeden Block durch die
Länge l von x ergänzt.
3. Schließlich muss man noch verhindern, dass Blöcke aus verschiedenen Nachrichten
kombiniert werden können. Deshalb erzeugt man vor der Berechnung des Etiketts
zu x zufällig einen Identifikator r und hängt diesen vor jeden Block.
Insgesamt wird eine Nachricht x deshalb in Blöcke x 0 ,...,x n− 1 der Länge l/ 4 zerlegt;
wir gehen davon aus, dass l durch 4 teilbar ist. (Falls nötig, wird x mit Nullen aufgefüllt.)
Statt ein Etikett zu jedem x i zu berechnen, wird nun ein Etikett t i für jeden Block der
Form r
0 , 1
}
erweitert werden. Die Idee ist, den Etikettieralgorithmus T von
x i berechnet, wobei r , l und i die oben erwähnten Komponenten sind,
die alle die Länge l/ 4 haben sollen. (Wir gehen davon aus, dass Nachrichten eine Länge
< 2 l/ 4 besitzen, damit deren Länge durch l/ 4 Bits dargestellt werden kann.) Das Etikett
zu x ist nun r
l ·
·
i
·
t n− 1 , enthält also neben den Etiketten t i auch den Identifikator r .
Man beachte, dass dieser MAC einen zufallsgesteuerten Etikettieralgorithmus verwen-
det. Es ist deshalb nötig, einen Validierungsalgorithmus anzugeben. Dies ist aber leicht
möglich (siehe Aufgabe 9.8.1 und 9.8.4).
Man kann nun zeigen, dass der so konstruierte MAC tatsächlich sicher ist, falls dies
für
·
t 1 ···
M B gilt (siehe Aufgabe 9.8.4). Allerdings ist dieser MAC äußerst inezient, da eine
 
Search WWH ::




Custom Search