<< . .

. 11
( : 33)



. . >>

Ein Signaturschema liefert Integrit¤t und Authentizit¤t, wie sie im n¤chsten Ka-
pitel beschrieben werden. Darüber hinaus können auch juristische Kategorien
wie

• Willenserkl¤rung,
• Unwiderru¬‚ichkeit,
• Rechtsverbindlichkeit

realisiert werden.

Wichtig ist dabei, eine unlösliche Verknüpfung zwischen den Teilnehmern T
und der zugehörigen öffentlichen Abbildung f T herzustellen. Beispielsweise
muss verhindert werden, dass ein Angreifer eine gef¤lschte Abbildung f T “
etwa auf eine Webseite “ plaziert, die für T™s Abbildung gehalten wird (man
vgl. hierzu auch das Problem mit dem Mann in der Mitte auf Seite 169). Das
ist ein nichttriviales, technisches Problem, das unter dem Stichwort Public-Key-
Infrastruktur behandelt wird.




Aufgaben
4.1 Führen Sie den Beweis des Satzes 4.4 in allen Details aus.

4.2 Bestimmen Sie die Laufzeit des üblichen Algorithmus für die Division mit
Rest.
80 4 Komplexit¤t und Einwegfunktionen

4.3 Komplexit¤t der Multiplikation

(a) Beschreiben Sie die Multiplikation zweier Bin¤r-Zahlen nach der bekannten
Methode aus der Grundschule.
(b) Bestimmen Sie die Komplexit¤t des Algorithmus in (a).
(c) Berechnen Sie 1100100 · 1010101 mit dem Algorithmus in (a).
(d) Es seien a, b ∈ N in der g-adischen Darstellung

n’1 n’1
mit n = 2ν
‘ ai g , ‘ bi g i
a= b=
i
i=0 i=0

gegeben. Wir setzen
n ’1 n ’1
2 2 n
‘ ‘ a n +i gi , sodass a = a L + a H g 2
ai gi und a H :=
a L :=
2
i=0 i=0
n n
und entsprechend b = bL + b H g 2 . Nun gilt a · b = u + vg 2 + wgn mit

u = a L bL , v = a L b H + a H b L = u + w ’ (a L ’ a H )(bL ’ b H ), w = a H bH .

Zeigen Sie, dass diese Methode von Karatsuba-Ofman eine Komplexit¤t von
O(nlog2 3 ) hat.

4.4 Beweisen Sie den Fundamentalsatz der Arithmetik 4.14.

4.5 Zeigen Sie, dass die Relation algorithmisch ¤quivalent von Seite 64 eine „qui-
valenzrelation ist.

4.6 Zeigen Sie, dass Kollisionsresistenz die im Text so genannte schw¤chere Form
der Kollisionsresistenz impliziert.

4.7 Für eine Hashfunktion h : P ’ Z2 soll eine Kollision mithilfe des Ge-
n

burtstagsparadoxons (siehe Aufgabe 2.2) konstruiert werden. Man spricht von
der Geburtstags-Attacke.
Wie viele Versuche braucht man, um mit Wahrscheinlichkeit ≈ 1/2 eine Kollision
zu ¬nden, wenn n = 64, n = 128 und n = 160 ist?
5 Symmetrische Authenti¬kation

Bei den bisher behandelten kryptogra¬schen Verfahren lag das Augenmerk auf
der Vertraulichkeit. Es werden Texte zwischen Sender und Empf¤nger ausge-
tauscht, deren Inhalt für Dritte nicht erkennbar sein soll. Aber wie schon in Ab-
schnitt 3.4.1 bemerkt, ist schlichte Verschlüsselung kein Garant für Authentizit¤t
und schon gar nicht für Integrit¤t. Als anschauliches Beispiel dient ein Formular:
Durch Verschlüsselung kann zwar der Inhalt verschleiert werden, aber die Stelle,
an der eine wichtige Information (etwa ein Geldbetrag oder eine Kontonummer)
steht, ist einem Angreifer bekannt. Er kann also versuchen zu manipulieren, evtl.
ohne genau zu wissen, welchen Effekt der Eingriff hat. Authenti¬kation stellt zwei-
erlei sicher:

• Zum einen soll eine Nachricht nicht auf dem Weg vom Sender zum Emp-
f¤nger unbemerkt ver¤ndert werden können “ Stichwort Integrit¤t.

• Zum anderen soll es gewiss sein, dass eine erhaltene Nachricht wirklich
vom vorgeblichen Sender stammt “ Stichwort Authentizit¤t.

Wir besprechen in diesem Kapitel symmetrische Authenti¬kationssysteme. Hier-
bei ist zwischen den Teilnehmern ein vorheriger Schlüsselaustausch nötig. In Ka-
pitel 12 werden wir asymmetrische Systeme kennenlernen “ ein vorheriger Schlüs-
selaustausch erübrigt sich dann.
Beim sogenannten MAC, das ein sehr weit verbreitetes symmetrisches Authenti-
¬kationssystem ist, wird zu einem Text N eine Prüfsumme S erzeugt. Der Sender
schickt das Paar (N , S) an den Empf¤nger, und dieser prüft mithilfe des gehei-
men Schlüssels k, ob die Nachricht N auf dem Weg verf¤lscht worden ist und ob
sie tats¤chlich vom vorgeblichen Sender stammt.
Der Satz von Gilbert-Williams-Sloane besagt, dass bei jedem Authenti¬kationssys-
tem die Betrugswahrscheinlichkeit p größer gleich 1/ |K| ist, wobei K die Schlüs-
selmenge des Systems ist. Wir werden ein Authenti¬kationssystem perfekt nen-
nen, falls die Betrugswahrscheinlichkeit p so klein wie möglich ist.
Um schließlich perfekte Authenti¬kationssysteme angeben zu können, machen
wir einen kleinen Aus¬‚ug in die Geometrie. Die perfekten Authenti¬kationssys-
teme lassen sich n¤mlich geometrisch als sogenannte Netze charakterisieren.


5.1 Message Authentication Code

Symmetrische Authenti¬kation wird in der Praxis fast ausschließlich mit Messa-
ge Authentication Codes, kurz MAC, durchgeführt.
82 5 Symmetrische Authenti¬kation

5.1.1 Das Prinzip des MAC

Die Idee ist einfach: Gegeben seien Mengen P, K und S und eine Abbildung

± : P—K ’ S.

Dann ist
(P, P — S, K, f ) mit f (x, k) := (x, ±(x, k))
ein Kryptosystem, da die Abbildung f k = f ( . , k) : P ’ P — S offenbar injektiv
ist “ vgl. die De¬nition auf Seite 9.
Von der Abbildung ± verlangen wir noch zweierlei:
Für k = k aus K gelte stets ±k = ±k .

Für jedes k ∈ K sei ±k eine kollisionsresistente Hashfunktion (hier ist impli-

zit vorausgesetzt, dass |S| < |P|).
Sender und Empf¤nger gehen nun wie folgt vor:
Vor der Kommunikation einigen sie sich auf den gemeinsamen, geheimen
Schlüssel k ∈ K.
Um den Klartext N ∈ P zu authenti¬zieren, berechnet der Sender den Wert
S := ±(N , k), den eigentlichen MAC, und verschickt f (N , k) = (N , S).
Der Empf¤nger erh¤lt (N , S ) und überprüft mit seinem Schlüssel k, ob die
Bedingung
±(N , k) = S
erfüllt ist.
Ist diese Bedingung erfüllt, so nennt man die Nachricht (N , S ) gültig, sonst
ungültig “ unabh¤ngig davon, ob (N , S ) gleich (N , S) ist oder nicht. Folglich
kann (N , S) auf dem Weg zum Empf¤nger manipuliert worden sein und den-
noch erkennt der Empf¤nger das erhaltene (N , S ) als gültig an.
Bei einer gültigen Nachricht sind im folgenden Sinne Integrit¤t und Authentizi-
t¤t sichergestellt: Die Authentizit¤t wird dadurch gew¤hrleistet, dass außer dem
Empf¤nger nur der Sender den vereinbarten Schlüssel kennt. Die Integrit¤t be-
ruht wesentlich auf der Kollisionsresistenz der Hashfunktion ±k ; diese stellt si-
cher, dass es nicht möglich ist, zu einem gültigen S eine weitere Nachricht N zu
¬nden, für die (N , S) als gültig akzeptiert wird.
Man erkennt, dass das geschilderte Verfahren so keinerlei Geheimhaltung bietet.
Der Klartext N wird unverschlüsselt vom Sender an den Empf¤nger übermit-
telt. Wir werden daher in diesem Kapitel nicht vom Geheimtext, sondern von der
Nachricht sprechen. Beim MAC ist die Nachricht f (N , k) = (N , S).
Wir können aber auch Geheimhaltung erreichen. Dazu verschlüssele man den
Klartext N vor oder nach der Anwendung von ± mit einem symmetrischen Ver-
fahren. Folglich können wir N als Klartext oder auch als verschlüsselten Text
5.1 Message Authentication Code 83

auffassen, je nachdem, ob eine Verschlüsselung stattgefunden hat oder nicht. Um
Verwirrung zu vermeiden, sprechen wir in diesem Kapitel bei N nicht von einem
Klartext, sondern von einem Datensatz.

Bemerkung
Nicht nur das System wird MAC genannt, auch der Wert S = ±(N , k) wird oft
als MAC bezeichnet.


5.1.2 Ein Beispiel und Varianten
Der vom NIST standardisierte CMAC ist von der Bauart wie im folgenden Bei-
spiel beschrieben.

Beispiel
Es sei (An , An , K, f ) eine symmetrische Blockchiffre über dem Alphabet A der
Blockl¤nge n wie etwa AES. Die Kommunikationspartner w¤hlen einen gemein-
samen, geheimen Schlüssel k ∈ K. Auf einen Datensatz N ∈ A— , wobei A— die
Halbgruppe der Strings über dem Alphabet A bezeichnet, beliebiger L¤nge wen-
den sie den CBC-Modus aus Abschnitt 3.4.2 mit Initialisierungsblock C0 an. Sie
zerlegen also N in Wörter Ni ∈ An , i ∈ {1, . . . , r}, der L¤nge n, sodass gilt
N = N1 N2 · · · Nr . Das letzte Wort muss evtl. durch Padding aufgefüllt werden.
Dann wird rekursiv gerechnet:

Ci := f (Ni + Ci’1 , k) für i ∈ {1, . . . , r} .

Die Abbildung ± ist durch ±(N , k) := Cr de¬niert. Soll der MAC eine L¤nge
kleiner als n haben, wird einfach abgeschnitten.
In der Praxis wird h¤u¬g C0 = 0 gew¤hlt und das letzte Wort Nr des Datensatzes
maskiert, d. h., es gibt einen weiteren geheimen Schlüssel (der oft aus k gewonnen
wird), mit dem Nr vor der Anwendung von f verschlüsselt wird.

Benutzt man AES als unterliegende Blockchiffre, so betr¤gt die maximale L¤n-
ge eines MAC 128 Bit. Das scheint den Angaben aus Abschnitt 4.4.2 auf S. 78
zu widersprechen. Dort hatten wir festgehalten, dass ein Hashwert mindestens
die L¤nge 160 haben sollte, um Kollisionsresistenz sicherzustellen. Im gegebenen
Kontext können wir aber mit kleineren Werten auskommen, weil die Kommuni-
kationspartner ja den Schlüssel wechseln können.
In der Praxis legen die Kommunikationspartner fest, welche Anzahl von ungülti-
gen Nachrichten sie tolerieren wollen, bis sie einen neuen Schlüssel austauschen.
Der Erhalt einer ungültigen Nachricht wird dabei als Betrugsversuch ausgelegt.

Bemerkung
Das NIST hat neben CMAC noch zwei weitere Betriebsmodi zur Authenti¬kation
standardisiert “ CCM und GCM. Diese beiden Verfahren gew¤hrleisten außer
Authenti¬kation auch noch Geheimhaltung.
84 5 Symmetrische Authenti¬kation

5.2 Der Satz von Gilbert-MacWilliams-Sloane
Wie im obigen Beispiel gezeigt wurde, kann jedes Kryptosystem auch zur Au-
thenti¬kation eingesetzt werden. Wir nennen ein Kryptosystem (P, C, K, f ), das
zu diesem Zweck eingesetzt wird, ein Authenti¬kationssystem.

Bemerkung
Bei einem Kryptosystem muss es schwierig sein, x aus f (x, k) zu bestimmen. Bei
einem Authenti¬kationssystem hingegen muss es schwierig sein, f (x, k) zu be-
stimmen. Immer vorausgesetzt, dass man den Schlüssel k nicht kennt.

Ist (P, C, K, f ) ein Authenti¬kationssystem, so betrachten wir für einen Geheimtext
c ∈ C die Menge K(c) aller Schlüssel, für die es einen Klartext x ∈ P gibt, sodass
x mit k verschlüsselt gerade c ergibt:

K(c) := {k ∈ K ; ∃ x ∈ P : f (x, k) = c} .

Ein Authenti¬kationssystem (P, C, K, f ) heißt kartesisch, wenn für jedes c ∈ C
gilt
f ’1 (c) = {x} — K(c) mit x ∈ P .

Das bedeutet, dass es zu jedem c ∈ C genau ein x ∈ P gibt mit f (x, k) = c für
eine Auswahl von k ∈ K. Das de¬niert eine Abbildung:

fˆ : C ’ P , c ’ x ,

wobei x das eben zu c erkl¤rte, eindeutig bestimmte Element ist.

Beispiel
Bei einem MAC gilt
c = f (x, k) = (x, ±(x, k)) ,

sodass jeder MAC kartesisch ist. Die Abbildung fˆ ist einfach die Projektion auf
die erste Koordinate.

Es seien P := {a, b}, K := {1, . . . , 6} und C := {m1 , m2 , m3 }. Untenstehen-
de Tabelle beschreibt f : P — K ’ C. Ist der benutzte Schlüssel k und soll
x ∈ P gesendet werden, so muss in der Spalte k nach x gesucht werden.
Die Zeilennummer m j ist die zu senden-
de Nachricht, f (x, k) = m j . Die Tabelle
123456
zeigt sofort, dass ein Authenti¬kationssys-
m1 a b a b - -
tem vorliegt, denn für jedes k ∈ K ist die
m2 b a - - a b
Abbildung f k := f ( . , k) : P ’ C injek-
m3 - - b a b a
tiv. Dieses System ist nicht kartesisch. Vgl.
dazu Aufgabe 5.1.
5.2 Der Satz von Gilbert-MacWilliams-Sloane 85

5.2.1 Möglichkeiten zum Betrug
Gegeben ist ein Authenti¬kationssystem (P, K, C, f ). Die Betrugswahrschein-
lichkeit p ist die Wahrscheinlichkeit, mit der ein Angreifer eine als gültig an-
zuerkennende Nachricht einspielen kann. Wir unterscheiden zwei Typen von Be-
trugsversuchen, die einem Angreifer zur Verfügung stehen.
• Substitution: Eine Nachricht wird abgefangen und durch eine eigene er-
setzt.

• Impersonation: Eine eigene Nachricht wird eingespielt.
Natürlich gilt für die Betrugswahrscheinlichkeit p ≥ |K| , weil ein Angreifer ver-
1

suchen kann, den Schlüssel zu erraten. Tats¤chlich ist die Situation viel schlechter.
Das ist der Inhalt des folgenden Satzes.
Satz 5.1 (Gilbert, MacWilliams, Sloane)
Es sei (P, C, K, f ) ein (nicht notwendig kartesisches) Anthenti¬kationssystem mit gleich-
verteilter Schlüsselwahl. Für die Betrugswahrscheinlichkeit p gilt
1
p≥ .
|K|

Beweis. Bei der Impersonation hat der Angreifer mit der Nachricht c ∈ C Erfolg,
wenn der benutzte Schlüssel in K(c) liegt. Für die Betrugswahrscheinlichkeit gilt
demnach für jedes c ∈ C:
|K(c)|
p≥ .
|K|
Bei der Substitution sei c ∈ C die beobachtete gültige Nachricht. Daher muss der
Schlüssel in K(c) liegen, und wir erhalten die Absch¤tzung
1
p≥ .
|K(c)|
Wir kombinieren die beiden Resultate zu
|K(c)| 1 1
p2 ≥ · = ,
|K| |K(c)| |K|
und der Satz ist bewiesen.
Ein Authenti¬kationssystem (P, K, C, f ) heißt perfekt, wenn die Betrugswahr-
scheinlichkeit p minimal ist, d. h. wenn p = 1/ |K|.
Bevor wir Beispiele von perfekten Authenti¬kationssystemen angeben, ziehen
wir aus dem Beweis des Satzes von Gilbert, MacWilliams und Sloane einige Fol-
gerungen.
Korollar 5.2
In einem perfekten, kartesischen Authenti¬kationssystem (P, C, K, f ) gilt:
86 5 Symmetrische Authenti¬kation

(a) Für alle c ∈ C ist |K(c)| = |K|.
(b) Für alle x ∈ P gilt | f ({x} — K)| = |K|.
(c) Für c, c ∈ C mit c = c gilt
falls fˆ(c) = fˆ(c )
0,
K(c) © K(c ) =
falls fˆ(c) = fˆ(c ).
1,

Beweis. (a) Es sei c ∈ C. W¤re |K(c)| > |K|, so folgte
|K(c)| 1
= p,
>
|K| |K|
und eine Impersonation mit c w¤re mit größerer Wahrscheinlichkeit erfolgreich,
als vorausgesetzt.
W¤re |K(c)| < |K|, so folgte
1 1
> = p,
|K(c)| |K|
und eine Substitution bei beobachtetem c w¤re mit größerer Wahrscheinlichkeit
erfolgreich, als angenommen. Daher muss Gleichheit gelten.
(b) Mit (a) gilt
|K|
| f ({x} — K)| = |K| für alle c ∈ C mit fˆ(c) = x ,
=
|K(c)|
denn je |K(c)| Elemente von K werden auf ein c abgebildet.
(c) Es seien x = fˆ(c) und x = fˆ(c ). Im Fall x = x erh¤lt man wegen f ’1 (c) ©
f ’1 (c ) = … und weil das System kartesisch ist sofort die Behauptung.
Es sei nun x = x . Der Fall m := |K(c) © K(c )| > 1 würde einen Substitutionsan-
griff mit
1
m
p≥ >
|K(c)| |K|
ermöglichen “ ein Widerspruch zur Voraussetzung. Daher gilt m ¤ 1. Die Abbil-
dung
K(c) ’ C , k ’ f (x , k)
ist injektiv. Ansonsten g¤be es zwei k1 , k2 ∈ K(c) mit c := f (x , k1 ) = f (x , k2 ),
und es würde k i ∈ K(c) © K(c ) folgen, mit einem Widerspruch wie eben. Mit (b)
folgt:
f ({x } — K(c)) = |K(c)| = |K| = f ({x } — K) ,
und somit f ({x } — K(c)) = f ({x } — K). Das bedeutet K(c) © K(c ) = …, also
m = 1.

Bemerkung
Die Vereinfachungen der Beweise in diesem Abschnitt verdanken wir Herrn Bert-
ram Poettering.
5.3 Beweisbar perfekte Systeme * 87

5.3 Beweisbar perfekte Systeme *
Um Beispiele für perfekte Authentikationssysteme angeben zu können, holen wir
etwas aus. Wir führen den Begriff der af¬nen Ebene eine, den wir auch in Kapitel 13
noch brauchen werden.

5.3.1 De¬nition af¬ner Ebenen
Es sei A eine Menge, und G sei eine Menge von Teilmengen von A, d. h. G ⊆
Pot(A). Das Paar (A, G) heißt af¬ne Ebene, falls |G| ≥ 2 für alle G ∈ G und die
folgenden drei Bedingungen erfüllt sind:
(A1) Zu je zwei Elementen a, b ∈ A mit a = b existiert genau ein G ∈ G mit
a, b ∈ G; wir schreiben a, b für dieses G.

(A2) (Parallelenaxiom) Zu G ∈ G und a ∈ A \ G existiert genau ein G ∈ G mit
a ∈ G und G © G = ….

(A3) Es gibt drei Punkte a, b, c ∈ A mit c ∈ a, b.
Die Menge A nennt man die Punktmenge und die Menge G die Geradenmenge
der af¬nen Ebene (A, G). Wir benutzen für a ∈ G für ein G ∈ G geometrische
Sprechweisen wie der Punkt a liegt auf der Geraden G oder die Gerade G geht durch
den Punkt a usw.

5.3.2 Die af¬ne Ebene AG(2, F)

Es sei F2 der (gewöhnliche) zweidimensionale F-Vektorraum über dem Körper
F. Wir setzen A := F2 und

G := a + F b ; a, b ∈ F2 , b = 0 .

Dabei ist F b := {» b ; » ∈ F} der von b erzeugte Untervektorraum von F2 .
Für F = R ist (A, G) schlicht die Anschauungsebene mit Punkten und Geraden
in der üblichen Interpretation. Man beachte, dass auch in (A, G) die Geraden Ne-
benklassen von Untervektorr¤umen in F2 sind, wie man das von der Anschau-
ungsebene kennt.
Für F = R scheint es klar zu sein, dass (A, G) eine af¬ne Ebene ist, wir zeigen
dass dies für ein beliebiges F erfüllt ist “ mit den bisherigen Bezeichnungen gilt:

Lemma 5.3
Es ist (A, G) eine af¬ne Ebene.

Beweis. (A1) Es seien a, b ∈ A mit a = b gegeben. Dann ist G = a + F (b ’ a) ∈ G,
und wegen 0, 1 ∈ F gilt a, b ∈ G. Es sei H = c + F d eine weitere Gerade, die a
und b enth¤lt, etwa a = c + » d, b = c + μ d mit », μ ∈ F. Dann gilt zum einen
b ’ a ∈ F d, also F (b ’ a) = F d, und zum anderen a + F d = c + F d. Wir fassen
zusammen: H = a + F (b ’ a) = G = a, b.
88 5 Symmetrische Authenti¬kation

(A2) Es seien G = c + F b ∈ G und a ∈ A \ G. Wir setzen G := a + F b. Wegen a ∈
G sind die Nebenklassen G und G des Untervektorraums F b disjunkt, folglich
gilt G © G = ….
Ist nun G eine weitere Gerade mit G © G = … durch a, so können wir
G = a + F d mit einem d = 0 setzen. Die Gleichung a + » d = c + μ b hat dann
keine Lösung (», μ) ∈ F2 . Daher können die Vektoren b, d ∈ F2 nicht linear un-
abh¤ngig sein. Es folgt F b = F d und damit G = G .
(A3) Die drei Punkte a := (0, 0), b := (1, 0), c := (0, 1) erfüllen die gewünschte
Bedingung.

<< . .

. 11
( : 33)



. . >>