Symmetrische Authentifizierungsverfahren - Moderne Kryptographie - page 228

gezeigt werden, dass dies dem Fälscher keinen wesentlichen zusätzlichen Vorteil verschafft,
zumindest nicht im Fall deterministischer Etikettierverfahren. Genauer:
a) Es sei F ein Fälscher mit Zugriff auf ein Etikettier- und Validierungsorakel. Wir
sagen, dass F ( n, q, q ,t ) -beschränkt ist, falls F ( n, q, t ) -beschränkt ist im Sinne von
Definition 9.2.3 und zudem höchstens q Anfragen an sein Validierungsorakel stellt.
Reduzieren Sie nun die Sicherheit eines MACs im neue Sinne, auf die Sicherheit im
ursprünglichen Sinne. Konstruieren Sie dazu zu einem Fälscher F mit Zugriff auf ein
Validierungsorakel einen Fälscher F im üblichen Sinne (d. h. F besitzt keinen Zugriff
auf ein Validierungsorakel), so dass der Vorteil von F möglichst gut durch denjenigen
von F abgeschätzt werden kann und so dass F einen ähnlichen Ressourcenverbrauch
hat wie F . Hinweis: Die Abschätzung wird entscheidend von q abhängen.
b) Betrachten Sie die verallgemeinerte Definition von MACs aus Aufgabe 9.8.1. Konstru-
ieren Sie einen MAC (gemäß dieser Definition), der i) im Sinne von Definition 9.2.2
sicher ist, d. h., jeder geeignet ressourcenbeschränkte Fälscher hat nur einen geringen
Vorteil, aber ii) unsicher ist bzgl. Fälscher, die Zugriff auf ein Etikettier- und Validie-
rungsorakel haben, d. h. es gibt einen solchen Fälscher, der einen großen Vorteil besitzt.
Hinweis: Konstruieren Sie ausgehend von einem sicheren MAC im Sinne von Defini-
tion 9.2.2, einen MAC, bei dem Nachrichten mehrere gültige Etiketten (bzgl. eines
Schlüssels) haben können. Konstruieren Sie den Validierungsalgorithmus zu diesem
MAC so, dass dieser Informationen über den verwendeten Schlüssel preisgibt.
Aufgabe 9.8.3 (Beweis von Satz 9.3.1) . Vervollständigen Sie den Beweis von Satz 9.3.1,
d. h., zeigen Sie, dass U ( q,t + c

log( q )) -beschränkt ist für eine kleine Konstante c
und dass (9.3.2) gilt. Überlegen Sie auch, warum in (9.3.2) nicht Gleichheit gilt.
Aufgabe 9.8.4 (MAC für Nachrichten beliebiger Länge) . Es sei

· l · q ·

M base ein MAC für Nach-

richten der Länge l .
a) Geben Sie zunächst eine präzise Definition für das am Ende von Abschnitt 9.3.1
skizzierte symmetrische Authentifizierungsschema, nennen wir es M , zur Authentifi-

zierung beliebig langer Nachrichten auf Basis von M base an.

b) Zeigen Sie, dass M sicher ist, falls M base sicher ist. Beschränken Sie dazu den Vorteil

eines Fälschers F für M durch den Vorteil eines aus F geeignet konstruierten Fälschers

F für

M base .
Hinweis: Es sei

EZ M das Ereignis, dass in einem Lauf von

E F eine 1 ausgegeben wird.

E F , dass in zwei verschiedenen
Anfragen an das Etikettierorakel, derselbe Identifikator r gewählt wurde, sowie das
Ereignis

Betrachten Sie zudem das Ereignis R über Läufen von

EZ B ,dassdievon F ausgegebene Nachricht einen Block enthält, der nicht
zuvor an das Etikettierorakel des Basissche ma s gesch ickt wurde. S ch ätzen Sie nun die
Wahrscheinlichkeiten für

EZ M ∩ R ,

EZ M ∩ R ∩ EZ B und EZ M ∩ R ∩ EZ B ab, wobei

M base aus F konstruieren sollten.
c) Überlegen Sie sich Alternativen zur Konstruktion aus Teilaufgabe a). Kann zum Bei-
spiel das Abschneiden am Ende einer Nachricht auch anders/besser verhindert werden
als dadurch, dass man jeden Block durch die Länge der Nachricht ergänzt? Beweisen
Sie die Sicherheit Ihrer Konstruktion(en) analog zu Teilaufgabe b).
Aufgabe 9.8.5 (CBC-MAC bei Ausgabe aller Blöcke) . Zeigen Sie, dass der CBC-MAC
unsicher ist, falls nicht nur der letzte berechnete Block ausgegeben wird, sondern alle

Sie für die letztere Abschätzung einen Fälscher auf