Cryptography Reference
In-Depth Information
Unterscheider haben lediglich einen geringen Vorteil, dann kann es auch keinen guten
Angreifer auf das R-CTR-Kryptoschema geben, d. h. der Vorteil von
A
muss ebenfalls
klein sein. Mit anderen Worten führen wir einen in der Kryptographie klassischen
Reduk-
tionsbeweis
: Die Sicherheit der einen kryptographischen Primitive wird auf die Sicherheit
der anderen reduziert. Man spricht, wie bereits in Abschnitt 1.2 erwähnt, in diesem Zu-
sammenhang auch von
beweisbarer Sicherheit
. Der folgende Satz fasst die Aussage, die
wir beweisen wollen, präzise.
Satz 5.4.1.
Es existiert eine (kleine) Konstante
c
, so dass für alle
t, n, q, l >
0
,
l
-Block-
Kryptosysteme
B
,
(
n, q, t
)
-beschränkten
l
-Angreifer
A
auf
S
=
R-CTR-
B
ein
(
n, t
+
c
·
(
q ·
log(
q
)
· l
+
n · l
))
-beschränkter
l
-Unterscheider
U
existiert mit
)+
2
qn
+
n
2
2
l
adv
(
A,
S
)
≤
2
·
adv
(
U,
B
.
(5.4.1)
Bevor wir diesen Satz beweisen, stellen wir zunächst fest, dass aus diesem Satz direkt
folgt, dass die Unsicherheit von R-CTR-
B
beschränkt ist durch diejenige von
B
. Genauer
gilt:
Folgerung 5.4.1.
Es existiert eine (kleine) Konstante
c
, so dass für alle
t, n, q, l >
0
und
l
-Block-Kryptosysteme
B
gilt:
)+
2
qn
+
n
2
2
l
insec
(
n, q, t,
R-CTR-
B
)
≤
2
·
insec
(
n, t
+
c
·
(
q
·
log(
q
)
·
l
+
n
·
l
)
,
B
.
Setzen wir die Blocklänge
l
auf
128 = 2
7
Bits, die maximale Laufzeit
t
auf
2
60
Re-
chenschritte und erlauben etwa eine Milliarde Orakelanfragen im Umfang von insgesamt
maximal einem Terabyte, d. h.,
q
=2
30
und
n
=2
43
/l
=2
36
, so erhalten wir folgende
Abschätzung, für eine Konstante
c
=10
:
)+
1
2
55
insec
(2
36
,
2
30
,
2
60
,
R-CTR-
insec
(2
36
,
2
61
,
B
)
≤
2
·
B
.
Wäre für das Block-Kryptosystem
, z. B. AES, die erschöpfende Schlüsselsuche (siehe
Abschnitt 4.3) der beste mögliche Angriff, mit dem man
B
von einer zufälligen Per-
mutation unterscheiden könnte, und könnte man in einem Rechenschritt einen Schlüssel
testen, so wäre insec
(2
36
,
2
61
,
B
1
2
67
: Dabei gehen wir davon aus, dass sich ein Angrei-
fer maximal
2
36
Klartexte mit dem Verschlüsselungsorakel verschlüsseln lässt und dann
durch maximal
2
61
Schlüssel läuft, um einen Schlüssel zu finden, mit dem die gegebenen
Chiffretexte zu den jeweiligen Klartexten entschlüsselt werden. Es sei bemerkt, dass für
in der Praxis eingesetzte Block-Kryptosysteme schon wenige Klartext-Chiffretext-Paare
ausreichen (deutlich weniger als
2
36
,eher
<
10
), um den verwendeten Schlüssel eindeutig
zu bestimmen. Mit insec
(2
36
,
2
61
,
B
)
≈
1
2
67
B
)
≈
würdesichinsgesamteingutesMaßanSi-
cherheit für das R-CTR-
-Kryptoschema ergeben. Wie bereits in Abschnitt 4.7 erwähnt,
ist allerdings für kein in der Praxis eingesetztes Kryptosystem eine konkrete Schranke für
dessen Unsicherheit insec
(
n, q,B
)
bekannt. Trotzdem zeigt Folgerung 5.4.1, dass die R-
CTR-Betriebsart prinzipiell sicher ist. Die Unsicherheit kann höchstens vom verwendeten
Kryptosystem herrühren.
B
