Cryptography Reference
In-Depth Information
Bits. Die Anzahl der Anfragen an das Etikettierorakel schließt dabei die Anfrage ein, die
nötig ist, um festzustellen, ob das von
F
ausgegebene NE-Paar gültig ist. Es sei
insec
(
n, q, t,
M
)= sup
{
adv
MAC
(
F,
M
)
|
F
ist
(
n, q, t
)
-beschränkter Fälscher für
M}
.
Weiter sei
ε
≥
0
reell. Der MAC
M
heißt
(
n, q, t, ε
)
-unsicher,
wenn insec
(
n, q, t,
M
)
≥
ε
gilt. Er heißt
(
n, q, t, ε
)
-sicher,
wenn insec
(
n, q, t,S
)
≤ ε
gilt.
In der Praxis findet man vor allem MACs, die auf Block-Kryptosystemen basieren,
sowie MACs, die sich (iterierte) Hashfunktionen zunutze machen. Die erstere Klasse
von MACs wollen wir im folgenden Abschnitt studieren. Die letztere Klasse von MACs
untersuchen wir in den Abschnitten 9.4 bis 9.6. Zum Abschluss dieses Kapitels werden wir
uns noch, wie in Abschnitt 5.6 bereits erwähnt, überlegen, dass man mit Hilfe von MACs
leicht symmetrische Kryptoschemen konstruieren kann, die CCA-Sicherheit bieten.
9.3
Konstruktion von MACs aus Block-Kryptosystemen
In diesem Abschnitt werden wir zwei Konstruktionen für (sichere) MACs kennenlernen,
die auf Block-Kryptosystemen basieren. Wir beginnen zunächst mit einer sehr einfachen,
aber inezienten Variante, um uns dann den CBC-MAC anzusehen, auf dem auch in der
Praxis verwendete MACs basieren.
9.3.1
Eine einfache Konstruktion
s
ein
l
-Block-Krypto-
system für
l,s >
0
. Wir konstruieren daraus einen MAC, in dem wir einfach das Chif-
frierverfahren als Etikettieralgorithmus verwenden. Aus
l
,K,
l
,E,D
)
mit
K
Es sei im Folgenden
B
=(
{
0
,
1
}
{
0
,
1
}
⊆{
0
,
1
}
B
erhalten wir also den MAC
M
B
=(
K,T
)
mit
l
und
k
T
(
x, k
)=
E
(
x, k
)
für alle
x
∈{
0
,
1
}
∈
K.
Dieser MAC ist nur auf Bitvektoren der Länge
l
anwendbar. Wir werden die Konstruktion
später auf Nachrichten beliebiger Länge erweitern.
Wichtiger ist zunächst die Frage, ob bzw. warum
M
B
ein sicherer MAC ist, falls
B
ein sicheres Block-Kryptosystem ist? Die Intuition ist einfach: Falls
B
ein sicheres Block-
Kryptosystem ist, verhält sich
etwa wie eine zufällige Funktion (vgl. Abschnitt 4.8).
Bei einer solchen Funktion werden Funktionswerte für neue Nachrichten zufällig gewählt.
Nun ist aber die Aufgabe eines Fälschers für einen MAC gerade, ein gültiges Etikett,
in unserem Fall also einen Funktionswert, für eine neue Nachricht
x
zu berechnen. Um
ein solches Etikett zu bestimmen, kann der Fälscher, da sich
B
etwa wie eine zufällige
Funktion verhält, nur raten. Die Wahrscheinlichkeit, erfolgreich zu sein, ist also sehr
gering.
Diese Intuition spiegelt sich auch im Beweis des folgenden Satzes wider, in dem die
Sicherheit von
B
M
B
auf diejenige von
B
reduziert wird.
