Cryptography Reference
In-Depth Information
l∗
und
angefragten Klartexte und es sei
(
z
0
,z
1
)
,mit
z
0
,z
1
∈{
,dasvon
A
gelieferte Angebot. Die Angebotshälfte, die in einem Lauf tatsächlich verschlüsselt
wird, bezeichnen wir mit
z
. Wird die Funktion
F
:
0
,
1
}
|
z
0
|
=
|
z
1
|
l
als Chiffre verwen-
det, so haben die Antworten auf die Orakelanfragen, also die Chiffretexte, die folgende
Form, wobei
r
1
,...,r
q−
1
,r
q
∈{
l
{
0
,
1
}
→{
0
,
1
}
l
zufällig, unabhängig vom Rest des Laufes gewählte
0
,
1
}
Bitvektoren sind und
n
1
+
···
+
n
q
≤
n
gilt:
:
r
1
·
(
F
(
r
1
)
⊕ x
(0)
1
)
· ··· ·
(
F
(
r
1
+
2
l
(
n
1
−
1))
⊕ x
(
n
1
−
1)
x
1
)
1
.
x
i
:
r
i
·
x
(0)
i
x
(
n
i
−
1)
i
(
F
(
r
i
)
⊕
)
· ··· ·
(
F
(
r
i
+
2
l
(
n
i
−
1))
⊕
)
(5.4.3)
.
x
(0)
q−
1
x
(
n
q−
1
−
1)
q−
1
x
q−
1
:
r
q−
1
·
(
F
(
r
q−
1
)
⊕
)
· ··· ·
(
F
(
r
q−
1
+
2
l
(
n
q−
1
−
1))
⊕
)
z
(0)
)
z
(
n
q
−
1)
)
.
z
:
r
q
·
(
F
(
r
q
)
⊕
· ··· ·
(
F
(
r
q
+
2
l
(
n
q
−
1))
⊕
Die Tatsache, dass
z
zum Schluss aufgeführt ist, soll nicht bedeuten, dass das Angebot im-
mer zum Schluss unterbreitet wird. Wir bezeichnen die Bitvektoren
r
1
,...,r
q
als
initiale
Zähler
und
r
i
+
2
l
j
als
Zähler
(von
x
i
bzw.
z
).
Sind nun die Zähler von
z
verschieden von allen anderen auftretenden Zählern, dann
entspricht die Verschlüsselung von
z
derjenigen im Vernamsystem (one-time pad): Da
F
eine zufällig gewählte Funktion ist, sind die Funktionswerte für die Zähler von
z
zufällig
gewählte Bitvektoren der Länge
l
. Diese sind unabhänig gewählt von den Funktionswerten
für die anderen Zähler, da nach Annahme die Zähler von
z
nicht an anderer Stelle auftau-
chen. Insgesamt wird also
z
wie im Vernamsystem mit einem frischen, zufällig gewählten
Bitvektor der Länge
verschlüsselt, über den der Angreifer keinerlei Information hat.
Wir wissen bereits, dass diese Art der Verschlüsselung informationstheoretische Sicher-
heit bietet. Insbesondere ist die Verteilung der Chiffretexte für
z
=
z
0
und
z
=
z
1
gleich
(siehe Satz 3.4.1). Es ist also intuitiv zu erwarten, dass der
l
-Angreifer nicht zwischen
der Verschlüsselung von
z
=
z
0
und
z
=
z
1
unterscheiden kann.
Die Argumentation bricht zusammen, wenn ein Zähler von
z
auch an anderer Stelle
auftritt, d. h., wenn
i
mit
1
|
z
|
i<q
sowie
j<n
i
und
h<n
q
existieren mit
r
i
+
2
l
j
=
r
q
+
2
l
h
. Wir sprechen dann von einer
Kollision
. Da der Angreifer
x
(
j
)
i
kennt, kann
er dann auch leicht
F
(
r
i
+
2
l
j
)
aus dem Chiffretext zu
x
i
bestimmen. Damit ist dem
Angreifer aber auch
F
(
r
q
+
2
l
h
)
bekannt, also ein Teil des Schlüssels zur Verschlüsselung
von
z
, was bei geeigneter Konstruktion von
z
0
und
z
1
, den Angreifer in die Lage versetzt,
leicht zwischen der Verschlüsselung von
z
0
und
z
1
zu unterscheiden. Würde also mit
»nicht geringer« Wahrscheinlichkeit eine Kollision auftreten, dann hätte der Angreifer
gute Chancen, zwischen der Verschlüsselung von
z
0
und
z
1
unterscheiden zu können. (Da
dem Angreifer die initialen Zähler bekannt sind, kann er leicht eine Kollision erkennen.)
Glücklicherweise tauchen, bei geeigneter Wahl der Parameter, Kollisionen nur mit sehr
geringer Wahrscheinlichkeit auf.
Wir wollen die obige informelle Argumentation dafür, dass
Prob
≤
{
S
=1
1
/
2
gilt,
nun präzisieren. Dazu schätzen wir zunächst die Wahrscheinlichkeit dafür, dass eine Kol-
lision auftritt, nach oben ab.
}≈
