Cryptography Reference
In-Depth Information
Definition 9.2.1 (Fälscher für symmetrisches Authentifizierungsverfahren). Ein
Fäl-
scher für einen
(
D,l
)
-MAC
ist ein zufallsgesteuerter Algorithmus
l
):
D
l
,
F
(
h
:
D
→{
0
,
1
}
×{
0
,
1
}
(9.2.1)
dem ein Etikettierorakel
h
zur Verfügung steht und dessen Laufzeit durch eine Konstante
nach oben beschränkt ist. Eine Berechnung eines solchen Fälschers heißt
zulässig,
wenn
für die Ausgabe
(
x, t
)
gilt, dass das Etikettierorakel
h
nicht auf
x
angewendet wurde. Sie
heißt
erfolgreich
,wenn
h
(
x
)=
t
gilt.
Der Vorteil eines Fälschers wird in üblicher Weise mit Hilfe eines Experiments definiert.
Definition 9.2.2 (Experiment und Vorteil). Es sei
M
=(
K,T
)
ein
(
D,l
)
-MAC und
E
F
,
F
ein Fälscher für
M
. Das zugehörige
Experiment
,daswirmit
E
F
oder einfach
E
bezeichnen, ist der Algorithmus, der gegeben ist durch:
E
:
}
1.
Schlüsselwahl
k
=
flip
(
K
)
2.
Berechung eines Nachrichten-Etikett-Paares
(
x, t
)=
F
(
T
(
·,k
))
3.
Auswertung
falls die Berechnug von
F
erfolgreich und zulässig war, dann gib
1
,sonst
0
zurück.
{
0
,
1
Der Vorteil adv
MAC
(
F,
M
)
von
F
bzgl.
M
ist definiert durch
)=Prob
E
F
=1
.
adv
MAC
(
F,
M
Statt dem Fälscher in der obigen Definition lediglich Zugriff auf ein Etikettierorakel
zu geben, könnte man ihm zusätzlich Zugriff auf ein Validierungsorakel
V
(
,k
)
geben,
an welches
F
beliebige NE-Paare
(
x
,t
)
,mit
x
∈ D
, schicken darf, um deren Gültigkeit
festzustellen. Dabei gibt
V
(
x
,t
,k
)
das Bit
1
(»gültig«) aus, falls
T
(
x
,k
)=
t
gilt, und
0
sonst. Eine Berechnung von
F
würden wir auch dann noch als zulässig bezeichnen, wenn
F
das Validierungsorakel auf das von
F
ausgegebene NE-Paar
(
x, t
)
anwenden würde.
Die Annahme, dass einem Fälscher ein solches Orakel zu Verfügung steht, ist genauso
realistisch, wie die Annahme, dass ein Fälscher Zugriff auf ein Etikettierorakel besitzt. In
Aufgabe 9.8.2 soll aber gezeigt werden, dass, zumindest für die Klasse von MACs, die wir
hier betrachten und die üblicherweise in der Praxis eingesetzt werden, Validierungsorakel
einem Fälscher keinen wesentlichen zusätzlichen Vorteil verschaffen, so dass wir guten
Gewissens bei Definition 9.2.2 bleiben können.
Die Sicherheit eines MACs quantifizieren wir nun wie üblich.
·
,
·
Definition 9.2.3 (
(
n, q, t
)
-beschränkt,
(
n, q, t, ε
)
-sicher). Es seien
n
,
q
,
t
natürliche Zah-
len,
F
ein Fälscher für einen
(
D,l
)
-MAC
M
. Der Fälscher
F
ist
(
n, q, t
)
-beschränkt bzgl.
M
E
F
höchstens
q
Anfragen an das Etikettierorakel gestellt werden, mit insgesamt höchstens
n
, wenn die Laufzeit des zugehörigen Experiments
E
F
durch
t
beschränkt ist, in
