Formale Aspekte der Software-Sicherheit und Kryptographie ... · Gibt es eine andere Methode, den Text zu entschl usseln? Barbara K onig \Form. Asp. der Software-Sicherheit und Kryptographie"

$Page 1: Formale Aspekte der Software-Sicherheit und Kryptographie ... · Gibt es eine andere Methode, den Text zu entschl usseln? Barbara K onig \Form. Asp. der Software-Sicherheit und Kryptographie"$
Organisatorisches Einfuhrung Kryptographie Kryptographische Protokolle Verifikation von kryptographischen Protokollen

Vorlesung “Formale Aspekte derSoftware-Sicherheit und Kryptographie”

Sommersemester 2019Universitat Duisburg-Essen

Prof. Barbara KonigUbungsleitung: Richard Eggert

Barbara Konig “Form. Asp. der Software-Sicherheit und Kryptographie” 1


Das heutige Programm:

Organisatorisches

VorstellungAblauf der Vorlesung und der UbungenEinordnung & PrufungLiteratur & Folien

Einfuhrung und Motivation: “Formale Aspekte derSoftware-Sicherheit und Kryptographie”

Inhalt der Vorlesung



Vorstellung

Dozentin: Prof. Barbara Konig

Raum LF 264

E-Mail: barbara [email protected]

Sprechstunde nach Vereinbarung

Ubungsleitung:

Richard Eggert, M.Sc.

Raum LF 263

E-Mail: [email protected]

Web-Seite:https://www.uni-due.de/theoinf/teaching/ss2019 ssk.php



Vorlesungstermine

Termine:

Mittwoch, 8:30–10:00, Raum LE 120

Donnerstag, 12:15–13:45, Raum LE 120

In der Regel wird jeden zweiten Donnerstag statt derVorlesung eine Ubung stattfinden.

Die erste Ubung findet am Donnerstag, den 2.5., statt.

Weitere Ubungstermine: siehe Webseite

Das Ubungsblatt wird in der Woche vor der Ubung auf derWebseite bereitgestellt, das erste Blatt am Mittwoch, den24.4. Bitte bereiten Sie sich mit Hilfe des Ubungsblattes aufdie Ubung vor!



Ubung und Hausaufgaben

Bonusregelung:

Das Ubungsblatt wird spatestens am Mittwoch in derVorwoche der Ubung auf der Webseite bereitgestellt.Verteilt uber das Semester gibt es drei Testat-Blatter.Die Losungen zu den Testatblattern werden in derdarauffolgenden Woche am Mittwoch in der Vorlesung bzw.bis spatestens 14:00 Uhr im Buro von Herrn Eggert (LF 263)abgegeben.Die anderen Blatter werden nicht korrigiert, aber naturlich inder Ubung besprochen.Es gibt eine Bonusregelung: der Bonus (eine Notenstufebesser in der Prufung, z.B. 1,7 statt 2,0) wird erzielt, wenn

50 % der Testat-Punkte erzielt,alle Testat-Blatter bearbeitet wurdenund mindestens einmal eine Aufgabe an der Tafelvorgerechnet wurde.

Gruppenabgabe ist nicht erlaubt.Barbara Konig “Form. Asp. der Software-Sicherheit und Kryptographie” 5


Einordnung

Diese Vorlesung ist folgendermaßen eingeordnet . . .

MAI

Informatik fur den Anwendungsbereich

Katalog “Verteilte, Verlassliche Systeme”

Stundenzahl: 4 SWS (3V + 1U), 6 Credits



Einordnung

Voraussetzungen

Fur diese Veranstaltung sollten Sie vorher moglichst die folgendenVorlesungen gehort haben:

Berechenbarkeit und Komplexitathttps://www.uni-due.de/theoinf/teaching/ws201819 beko.php

Wahrscheinlichkeitstheorie und Statistik

Logikhttps://www.uni-due.de/theoinf/teaching/ws201819 logik.php

. . . oder aquivalente Veranstaltungen.

Das wird keine Komplexitatstheorie-Veranstaltung, aber wirbenotigen einige Grundlagen aus der Komplexitatstheorie. Gleichesgilt fur die Wahrscheinlichkeitstheorie und Logik. Die Grundlagenwerden auch noch einmal kurz wiederholt.



Prufung

Diese Vorlesung wird mundlich gepruft. Der Prufungstermin istvoraussichtlich der 18./19. Juli.



Literatur

John Talbot, Dominic Welsh: Complexity and Cryptography –An Introduction. Cambridge, 2006.

Christos H. Papadimitriou: Computational Complexity.Addison Wesley, 1994.

Oded Goldreich: Foundations of Cryptography (Basic Tools).Cambridge University Press, 2001.

Oded Goldreich: Foundations of Cryptography (BasicApplications). Cambridge University Press, 2004.



Literatur

William Stallings: Cryptography and Network Security:Principles and Practice. Prentice-Hall, 2003.

Martın Abadi: Security Protocols: Principles and Calculi –Tutorial Notes. FOSAD 2006/07 Tutorial Lectures, Springer,2007, p. 1-23.http://users.soe.ucsc.edu/~abadi/Papers/fosad-protocols.pdf

Martın Abadi: Security Protocols and their Properties. 20thInternational Summer School on Foundations of SecureComputation, IOS Press, 2000, p. 39-60.http://users.soe.ucsc.edu/~abadi/Papers/nato.ps



Literatur

Bruno Blanchet: Using Horn Clauses for Analyzing SecurityProtocols. Formal Models and Techniques for AnalyzingSecurity Protocols. IOS Press, 2010.http://prosecco.gforge.inria.fr/personal/bblanche/publications/

BlanchetBook09.html

Martın Abadi and Bruno Blanchet: Analyzing SecurityProtocols with Secrecy Types and Logic Programs. Journal ofthe ACM, 52(1):102-146, 2005.http://prosecco.gforge.inria.fr/personal/bblanche/publications/

AbadiBlanchetPOPL02.html



Folien

Folien werden

im Web bereitgestellt und

regelmaßig aktualisiert.

Die Folien werden sehr ahnlich zu den Folien aus demSommersemester 2018 sein (erhaltlich uberhttp://www.ti.inf.uni-due.de/teaching/ss2018/ssk/).




Inhalt

Kryptographie

Kryptographische Protokolle

Verifikation von kryptographischen Protokollen




Kryptographie ist . . .

die Wissenschaft von der Verschlusselung von Informationen.

Kryptographie ist inzwischen fur sicheren Nachrichtenaustausch(Online-Bezahlungssysteme, Online-Banking, etc.) unverzichtbargeworden.

Ein Teil der Informatik ist der Entwurf von sicherenVerschlusselungssystemen und die Analyse existierenderVerschlusselungssysteme. Dabei mochte man moglichstweitreichende Garantien uber deren Sicherheit erhalten.




Kryptographische Protokolle . . .

sind Protokolle, die Nachrichten nach bestimmten – vorherfestgelegten Regeln – austauschen und dabei kryptographischeVerfahren verwenden (hauptsachlich zum Verschlusseln, aber auchzum Signieren von Nachrichten).

Solche Protokolle sind sehr fehleranfallig. Beispielsweise sindzahlreiche falsche Authentifizierungsprotokolle im Umlauf.



Motivation: Entschlusselung

Wir beginnen mit einigen motivierenden Beispielen. Als erstesentschlusseln wir einen Text, von dem wir wissen, dass er durchPermutation von Buchstaben verschlusselt wurde. Ein solchesVerfahren nennt man auch monoalphabetische Verschlusselung.

Monoalphabetische Verschlusselung

Sei A die Menge aller 26 Buchstaben des Alphabets und seiπ : A → A eine beliebige bijektive Abbildung.Dann wird ein Wort m0 . . .mn ∈ A∗ dadurch verschlusselt, dassjeder Buchstabe mi durch π(mi ) ersetzt wird.




Wir haben nun einen (langeren) Text abgefangen, der auf dieseWeise verschlusselt wurde, die Permutation π (= der Schlussel) istjedoch nicht bekannt. Wie kann dieser Text entschlusselt werden?

DPGASUPF UPQ ZQRTGSIQXTAOP

ZQRTGSIQXTAOEYAP JPQLXAQPF KPQUPF HFGPQGPOVG OF UOP ZVXEEOEYAPF HFU

DSUPQFPF JPQLXAQPF. UOPEP POFGPOVHFI ZSQQPETSFUOPQG OD KPEPFGVOYAPF

DOG UPQ HFGPQGPOVHFI OF ERDDPGQOEYAP HFU XERDDPGQOEYAP JPQLXAQPF.

DPGASUPF UPQ ZVXEEOEYAPF ZQRTGSIQXTAOP: ESVXFIP LHPQ UOP ZQRTGSIQXTAOP

FSYA ZPOFP PVPZGQSFOEYAPF QPYAFPQ POFIPEPGNG KHQUPF, PQEPGNGP DXF CPO

UPQ JPQEYAVHPEEPVHFI (NH UOPEPQ NPOG UOP POFNOIP XFKPFUHFI UPQ

ZQRTGSIQXTAOP) ODDPQ JSVVEGXPFUOIP CHYAEGXCPF SUPQ

CHYAEGXCPFIQHTTPF. ESVYAP JPQLXAQPF EOFU APHGP JPQXVGPG HFU HFEOYAPQ.

[...]

Vollstandiger Text unterwww.ti.inf.uni-due.de/fileadmin/public/teaching/ssk/misc/krypto-1.txt




Wieviele mogliche Schlussel gibt es? Kann man alle dieseSchlussel durchprobieren?

Gibt es eine andere Methode, den Text zu entschlusseln?




Ein durch monoalphabetische Verschlusselung kodierter Text kannim Allgemeinen einfach durch

Haufigkeitsanalyse von Buchstaben und

Suche nach bekannten Wortern

entschlusselt werden.

Dabei wird insbesondere ausgenutzt, dass “e” der bei weitemhaufigste Buchstabe im Deutschen ist, dass dreibuchstabigeWorter mit einem “e” in der Mitte im Allgemeinen Artikel sind(der, den, dem, . . . ), usw.




Eine solche Entschlusselung ist sehr schon in der Kurzgeschichte“The Gold Bug” (dt. “Der Goldkafer”) von Edgar Allan Poebeschrieben.

In Englisch unter:http://etext.lib.virginia.edu/toc/modeng/public/PoeGold.html

In Deutsch unter:http://gutenberg.spiegel.de/buch/der-goldkafer-2271/1




Haufigkeit der Buchstaben im Deutschen:

Platz Buchstabe Haufigkeit Platz Buchstabe Haufigkeit

1. E 17,40 % 15. O 02,51 %2. N 09,78 % 16. B 01,89 %3. I 07,55 % 17. W 01,89 %4. S 07,27 % 18. F 01,66 %5. R 07,00 % 19. K 01,21 %6. A 06,51 % 20. Z 01,13 %7. T 06,15 % 21. P 00,79 %8. D 05,08 % 22. V 00,67 %9. H 04,76 % 23. ß 00,31 %

10. U 04,35 % 24. J 00,27 %11. L 03,44 % 25. Y 00,04 %12. C 03,06 % 26. X 00,03 %13. G 03,01 % 27. Q 00,02 %14. M 02,53 %




Bemerkungen:

Ein gutes Verschlusselungsverfahren muss nicht nur sicherstellen,dass es Falle gibt, in denen ein Text nicht entschlusselt werdenkann.Es muss daruber hinaus garantieren, dass

das Entschlusseln eines Textes immer schwer ist

und dass es auch nicht moglich ist, den Ursprungstext miteiner bestimmten Wahrscheinlichkeit zu ermitteln.

Dem Entschlussler stehen randomisierte Verfahren zur Verfugung,die Wahrscheinlichkeitsverteilungen ausnutzen konnen. EinKryptosystem muss solchen Angriffen standhalten!

Um die Sicherheit eines Kryptosystems zu analysieren, benotigtman Wahrscheinlichkeitsrechnung.



Motivation: Schlusselaustausch

Eine weitere Fallstudie: Schlusselaustausch

Angenommen, wir haben ein hinreichend sicheres Kryptosystem.Zwei Partner konnen sicher miteinander kommunizieren, wenn sieeinen gemeinsamen geheimen Schlussel vereinbart haben.

Wir betrachten nun ein offenes System mit n Teilnehmern:

Wieviele Schlussel mussen ausgetauscht werden, damit jeder mitjedem sicher kommunizieren kann?




Antwort: es mussen(n

2

)= n(n−1)

2 Schlussel ausgetauscht werden!Das ist ein großer Verwaltungsaufwand, selbst wenn man einezentrale Stelle zur Schlusselverteilung hat.




Losung des Schlusselaustausch-Problems:

Man verwendet sogenannte asymmetrischeVerschlusselungsverfahren. Dabei gibt es Schlusselpaare bestehendaus

einem offentlichen Schlussel, der nur zur Verschlusselung,jedoch nicht zur Entschlusselung verwendet werden kann

und einem privaten Schlussel, der zum Entschlusseln dient.

Jeder Teilnehmer erzeugt sein eigenes Schlusselpaar und gibt nurden offentlichen Schlussel bekannt. Demnach werden nur nSchlusselpaare benotigt. Außerdem konnen die offentlichenSchlussel ohne Bedenken uber das Netz verschickt werden, ohnedass die Kommunikationspartner sich personlich treffen mussen.




Analogie:

Die Geheimnisse werden in Kisten verschickt, die mit einemSchloss verschlossen werden konnen.

Jeder Partner hat seinen eigenen (privaten) Schlussel und eineunbegrenzte Anzahl dazu passender Schlosser. Die Schlosserentsprechen den offentlichen Schlusseln.

Die Schlosser konnen beliebig an die Kommunikationspartnerverteilt werden und dienen dazu, die Kisten vor demVersenden zu verschließen.

Das ist System ist sicher, wenn man durch den Besitz einesSchlosses nicht herausfinden kann, wie der dazugehorigeSchlussel aussieht.




Verschlusselungsverfahren, die auf dem Prinzip von privaten undoffentlichen Schlusseln beruhen, nennt man asymmetrisch.

Bei klassischen symmetrischen Verfahren teilen sich jeweils zweiPartner einen Schlussel. In der Analogie bedeutet das, dass diebeiden Kommunikationspartner jeweils eine Kopie desselbenSchlussels haben. Die Kopien mussen jedoch zunachstausgetauscht werden! Dies kann wiederum mit Hilfe einesasymmetrischen Verfahrens passieren.



Motivation: Authentifizierungs-Protokolle

Eine wichtiges (Teil-)Problem bei Protokollen ist es, einenNachweis zu fuhren, dass der entsprechendeKommunikationspartner auch derjenige ist, fur den er sich ausgibt.Die Fuhrung dieses Nachweises nennt man Authentifizierung.

Szenario: es gibt zwei Kommunikationspartner Alice und Bob.Außerdem gibt es den bosartigen Eindringling Eve, die alleNachrichten abfangen kann und neue Nachrichten produzierenkann. Sie kann jedoch keine Nachrichten entschlusseln, wenn sieden passenden Schlussel nicht besitzt. Eve mochte sich Alicegegenuber als Bob ausgeben (und sie dazu uberreden, ihr1.000 EUR zu uberweisen . . . )




Angenommen, die Parteien benutzen eine Variante desNeedham-Schroeder-Protokolls.

Dabei wird symmetrische Verschlusselung eingesetzt und derSchlusselaustausch findet uber einen Server statt. (Es gibt aucheine asymmetrische Variante.)

Das Protokoll benutzt sogenannte Nonces:

Nonce (number used once)

Zufallige Zahlen oder Bit-Kombinationen, die nur einmalverwendet werden und die garantieren sollen, dass eine Nachrichtfrisch und neu erzeugt ist. Sie sollen verhindern, dass eine alteNachricht als Replay geschickt wird.




Konventionen:

Ein symmetrischer Schlussel der Form KAB wird fur dieVerschlusselung von Nachrichten zwischen A und B verwendet.

Mit MK bezeichnen wir eine Nachricht M, die mit dem SchlusselK verschlusselt ist. Nur derjenige, der K besitzt, kann dieNachricht M lesen.




Needham-Schroeder-Protokoll (fehlerhaft)

1 A→ S : A,B,NA

2 S → A: NA,KAB , KAB ,AKBSKAS

3 A→ B: KAB ,AKBS

4 B → A: NBKAB

5 A→ B: NB − 1KAB




Graphische Darstellung:

S

5. NB − 1KAB

4. NBKAB

2. NA,KAB , KAB ,AKBSKAS

1. A,B ,NA

3. KAB ,AKBS

A B




Erlauterung der einzelnen Schritte:

1. A→ S : A,B,NA

Alice fordert beim (vertrauenswurdigen) Server einenSitzungsschlussel fur die Kommunikation mit Bob an. Sie schickteinen Nonce NA mit, um sicherzugehen, dass die Antwort sichwirklich auf ihre Anforderung bezieht. Diese Nachricht istunverschlusselt.




2. S → A: NA,KAB , KAB ,AKBSKAS

Der Server schickt den Sitzungsschlussel KAB an Alice. Dieser wirdmit Hilfe von KAS (dem gemeinsamen Schlussel von Alice und demServer) verschlusselt. Der Server fugt auch den Nonce NA hinzu,um Alice gegenuber zu beweisen, dass die Nachricht die Antwortauf Alice’ Anfrage war.Des weiteren wird eine fur Bob bestimmte Nachricht mitgeschickt:KAB ,AKBS

. Damit wird Bob mitgeteilt, wie der Sitzungsschlussellautet und wer (A = Alice) mit ihm kommunizieren will.




3. A→ B: KAB ,AKBS

Alice entschlusselt die Nachricht des Servers und schickt dieenthaltene Nachricht KAB ,AKBS

an Bob weiter. Sie selbst kannmit diesem Teil der Nachricht nichts anfangen, nur Bob kann sieentschlusseln.




4. B → A: NBKAB

Bob entschlusselt die erhaltene Nachricht und stellt fest, dass Alicemit ihm kommunizieren mochte. Außerdem erhalt er dadurch denSitzungsschlussel KAB . Da Bob dem Server vertraut, kann er davonausgehen, dass der Sitzungsschlussel KAB ansonsten nur Alicemitgeteilt wurde.Er mochte jetzt jedoch noch testen, ob seinKommunikationspartner tatsachlich Alice ist. Dazu generiert ereine “Testnachricht”, die den Nonce NB enthalt und mit KAB

verschlusselt ist.




5. A→ B: NB − 1KAB

Alice weist sich Bob gegenuber aus, indem sie die Nachrichtentschlusselt und den Nonce um eins dekrementiert. Damit kannBob feststellen, dass sein Gegenuber den entsprechenden Schlusselbesitzt und daher Alice ist.

Leider ist das Protokoll so fehlerhaft und kann von Eve angegriffenwerden. Warum?




Szenario: Alice mochte eine Verbindung mit Bob aufbauen. Evehort mit und fangt geeignete Nachrichten ab bzw. modifiziert sie.Damit gelingt es ihr, sich Alice gegenuber als Bob auszugeben.

Angriff

1 A→ S : A,B,NA

E ersetzt diese Nachricht durch: A,E ,NA

2 S → A: NA,KAE , KAE ,AKESKAS

3 A→ B: KAE ,AKES

Eve fangt diese Nachricht ab und erhalt damit denSitzungsschlussel KAE .

4 E → A: NBKAE

5 A→ B: NB − 1KAE

Eve fangt auch diese Nachricht ab. Alice ist jetzt uberzeugtmit Bob zu kommunizieren, spricht aber mit Eve!




Das Problem kann unter anderem dadurch gelost werden, indemder Server in die zweite Nachricht den Namen desKommunikationspartners (B = Bob) einfugt:

Needham-Schroeder-Protokoll

1 A→ S : A,B,NA

2 S → A: NA,B,KAB , KAB ,AKBSKAS

3 A→ B: KAB ,AKBS

4 B → A: NBKAB

5 A→ B: NB − 1KAB

Damit erkennt Alice, wenn sie die NachrichtNA,E ,KAE , KAE ,AKES

KASerhalt, dass dies die falsche

Nachricht sein muss.




Die fehlerhafte Variante des Needham-Schroeder-Protokolls, wiewir sie betrachtet haben, wurde so nie benutzt.

Im Netzwerkauthentifizierungsprotokoll Kerberos wurde jedoch dasNeedham-Schroeder-Protokoll mit asymmetrischer Verschlusselungverwendet, das einen ahnlichen Fehler enthielt. (Die Variante mitasymmetrischer Verschlusselung ist etwas komplizierter, daherbetrachten wir sie im Moment nicht.)

Dieser Fehler wurde erst im Jahr 1995 – 17 Jahre nach derEntwicklung des Protokolls – entdeckt!




Ein anderes Problem besteht darin, dass Eve die dritte Nachrichtspater wieder einspielen kann. Falls Eve bis dahin in den Besitz vonKAB gekommen ist, kann sie sich diesmal fur Alice ausgeben.

Losung: Zeitstempel in der dritten Nachricht

Solche Angriffe nennt man man-in-the-middle attacks.Ahnliche Probleme gibt es auch bei der sogenannten SMBreflection attack und bei vielen anderen bekannten Angriffen aufSicherheitsprotokolle. (SMB = Server Message Block: Protokollzum Sharing von Dateien, Druckern, etc. in einem Netzwerk; wirdvor allem unter Windows benutzt).



Motivation: Informationssicherheit

Mit der zunehmenden Vernetzung von Computern wird dieInformationssicherheit immer wichtiger. Daten mussen gegenuberDritten, d.h., vor moglichen Angreifern geschutzt werden.

Im Englischen: security (im Gegensatz zum allgemeineren Begriffsafety, der sich auf die Abwesenheit von Fehlern oder den Schutzvor Fehlern in der Software bezieht).




Bei Informationssicherheit sind unter anderem folgende Aspekterelevant:

Vertraulichkeit

Daten durfen lediglich von autorisierten Benutzern gelesen bzw.modifiziert werden, dies gilt sowohl beim Zugriff auf gespeicherteDaten wie auch wahrend der Datenubertragung.

Integritat

Daten durfen nicht unbemerkt verandert werden, bzw. es mussenalle Anderungen nachvollziehbar sein.

Authentizitat/Authentifizierung

Echtheit und Glaubwurdigkeit einer Person oder eines Dienstesmussen uberprufbar sein.




Zurechenbarkeit (engl. accountability)

Eine durchgefuhrte Handlung kann einem Kommunikationspartnereindeutig zugeordnet werden.

Verbindlichkeit/Nichtabstreitbarkeit (engl. non-repudiation)

Verbindlichkeit erfordert, dass kein unzulassiges Abstreitendurchgefuhrter Handlungen moglich ist. Sie ist unter anderemwichtig beim elektronischen Abschluss von Vertragen und kanndurch digitale Signaturen erreicht werden.




Einige der oben genannte Ziele kann man durch den Einsatz vonVerschlusselungsverfahren erreichen.

Wie wir am Beispiel des Needham-Schroeder-Protokolls gesehenhaben, ist es aber auch sehr wichtig, dass nicht nur diekryptographischen Verfahren, sondern auch die eingesetztenProtokolle korrekt und nicht angreifbar sind.

In beiden Fallen ist es wichtig zu definieren, was es uberhauptbedeutet, ein Verschlusselungsverfahren oder Protokoll erfolgreichanzugreifen und zu analysieren, dass die eingesetzten Verfahrenkorrekt sind.




Kyptographie

Grundlagen der Kryptographie

Spezielle Verschlusselungsverfahren (historischeVerschlusselungsverfahren, One-Time-Pad, BlockchiffreDES/AES, RSA)

Bedingungen an die Sicherheit von Kryptosystemen(randomisierte Komplexitatsklassen, Einwegfunktionen,Falltur-Funktionen)




Kyptographische Protokolle

Digitale Unterschriften

Zero-Knowledge-Proofs: Wie uberzeuge ich meinen Partnerdavon, dass ich ein Geheimnis kenne, ohne das Geheimnis zuverraten?

Secure Multi-Party Computations: Gemeinsame Berechnungeines Ergebnisses durch mehrere Teilnehmer, ohne dass dieeinzelnen Parameter bekanntgegeben werden mussen.

Blockchain: Dezentrale Buchhaltung, Grundlage von Bitcoin.




Verifikation von kyptographischen Protokollen

Eindringlingsmodell nach Dolev-Yao

Sicherheitslucken in kryptographischen Protokollen

Verifikation kryptographischer Protokolle (mitProzesskalkulen, Resolution, Model-Checking)



Ver- und Entschlusselung

Wir beschreiben jetzt formal, was es bedeutet, eine Nachricht zuverschlusseln und zu entschlusseln.

Komponenten eines Kryptosystems (Definition)

M: eine Menge von moglichen Nachrichten

CM: eine Menge von verschlusselten Nachrichten

Ke : eine Menge von Schlusseln, die zum Verschlusselnverwendet werden

Kd : eine Menge von Schlusseln, die zum Entschlusselnverwendet werden

K ⊆ Ke × Kd : eine Menge von gultigen Schlusselpaaren

Eine Verschlusselungsfunktion E : M × Ke → CM

Eine Entschlusselungsfunktion D : CM × Kd → M




Hinweis: E steht fur “encryption” und D fur “decryption”.

Sei (e, d) ∈ K ein Schlusselpaar. Die Ver- undEntschlusselungsfunktionen mussen folgende Eigenschaft haben:

Fur alle m ∈ M gilt D(E (m, e), d) = m.




Symmetrisches Kryptosystem

Bei einem symmetrischen Kryptosystem gilt Ke = Kd und fur ein(e, d) ∈ K gilt immer e = d . D.h., es wird derselbe Schlussel zumVer- und Entschlusseln benutzt.Sowohl Alice, als auch Bob mussen zur Kommunikation diesenSchlussel kennen.

Alice Bob

(e, e) (e, e)




Asymmetrisches Kryptosystem

Bei einem asymmetrischen Kryptosystem gilt fur ein (e, d) ∈ Knormalerweise e 6= d . D.h., es werden verschiedene Schlussel zumVer- und Entschlusseln benutzt.Wenn Alice eine Nachricht an Bob schickt, dann reicht es aus,wenn Alice e kennt. Dieser Schlussel wird auch der offentlicheSchlussel von Bob genannt. Daneben kennt Bob noch seinenprivaten Schlussel d .

Alice

e

Bob

(e, d)




Sicherheitsaspekte: die bisherigen Definitionen sagen nichts uberdie Sicherheit der Kryptosysteme.

Im Fall der symmetrischen Verschlusselung sollte es einfach sein, maus E (m, e) zu bestimmen, wenn man d = e kennt. Ohne Kenntnisdes Schlussels sollte die Bestimmung von m schwierig sein.

Ebenso sollte es im Fall des asymmetrischen Verschlusselungeinfach sein, m aus E (m, e) zu bestimmen, wenn man d kennt. DieBestimmung von m sollte jedoch schwierig sein, wenn man nur ekennt.

Wir werden im weiteren Verlauf der Vorlesung klaren, was genaumit “schwierig” gemeint ist.



Historische Verschlusselungsverfahren

Wir betrachten zunachst einige einfache symmetrischeVerschlusselungsverfahren.

Caesar-Verschlusselung

Bei der Caesar-Verschlusselung (nach Julius Caesar) wird jederBuchstabe durch den Buchstaben ersetzt, der drei Stellen weiterim Alphabet vorkommt. (Statt drei kann auch ein andererZahlenwert verwendet.)

Beispiel: aus “CAESAR” wird “FDHVDU”

Spezialfall der monoalphabetische Verschlusselung, der durchHaufigkeitsanalyse sehr leicht entschlusselt werden kann.




Monoalphabetische Verschlusselung

Gegeben ist eine Permutation π : A → A des Alphabetes und jederBuchstabe a der Nachricht wird durch sein Bild π(a) ersetzt.(Siehe Beispiel im Einfuhrungsteil.)

Auch die monoalphabetische Verschlusselung kann durchHaufigkeitsanalysen einfach entschlusselt werden.




Vigenere-Verschlusselung

Bei der Vigenere-Verschlusselung (nach Blaise de Vigenere, 16.Jhdt.) wird ein Schlussel e = e0 . . . em−1 ∈ A∗ uber dem Alphabetgegeben. Eine Abbildung z : A → N0 ordnet jedem Buchstabeneinen Zahlenwert zu (z(A) = 0, . . . , z(Z) = 25).

Dann werden die Buchstaben des zu verschlusselnden Textesm = m0 . . .mn ∈ A∗ der Reihe nach verschlusselt, indem derZahlenwert des jeweils nachsten Buchstabens des Schlusselsaddiert und und das Ergebnis modulo 26 genommen wird.

Insbesondere gilt fur den verschlusselten Text c = c0 . . . cn ∈ A∗,dass

ci = z−1((z(mi ) + z(ei mod m)) mod 26)




Beispiel: e = CAESAR, wobei z(C) = 2, z(A) = 0, z(E) = 4,z(S) = 19, z(R) = 18

DASISTDERGEHEIMTEXT

+ CAESARCAESARCAESARC

FAWBSLFEVZEZGIQMEPV




Bei der Vigenere-Verschlusselung nutzt eine Haufigkeitsanalyseuber den gesamten Text wenig.

Entschlussselungsverfahren:

Zunachst muss die Lange des Schlussels e ermittelt werden.Das kann man machen, indem man verschiedene Langen kausprobiert und die Haufigkeitsverteilung der Buchstabenermittelt, deren Stelle kongruent zu einem festen i modulo kist.Manchmal kann die Lange auch durch das periodischeAuftreten bestimmter Zeichenfolgen im Text bestimmtwerden.

Sobald die Lange k gefunden wurde, kann dann der Schlussel,Stelle fur Stelle, mit Hilfe der Haufigkeitsanalyse ermitteltwerden.




Ein besonderer Fall ergibt sich jedoch, wenn der Schlussel genau solang ist wie der zu verschlusselnde Text.

One-Time-Pad

Beim One-Time-Pad wird ein Text mit einem zufallig gewahltemSchlussel gleicher Lange verknupft.Die Verknupfung kann wie beim Vigenere-Schlussel passieren.Alternativ konnen auch zwei Bitstrings durch ⊕ (xor) verknupftwerden.

Voraussetzungen:

der Einmalschlussel muss geheim bleiben,

der Einmalschlussel muss zufallig gewahlt sein und

der Einmalschlussel darf nur einmal verwendet werden.




Der One-Time-Pad wurde so von Geheimdiensten im20. Jahrhundert verwendet. Dabei wurde zunachst der Schlusselausgetauscht, beispielsweise kann er auf Papier oder in digitalerForm einem Agenten mitgegeben werden.

Claude Shannon hat gezeigt, dass der One-Time-Padinformationstheoretisch sicher ist und damit ein perfektesVerschlusselungsverfahren darstellt. Insbesondere hat er gezeigt,dass

Die Kenntnis des verschlusselten Textes keine zusatzlichenInformationen uber den Inhalt der Nachricht liefert.

bzw.

Jeder Nachrichteninhalt hat die gleiche Wahrscheinlich-keit, unabhangig davon, ob man den verschlusselten Textkennt.



Wahrscheinlichkeitrechnung

Um dieses (nicht sehr schwierige) Ergebnis formalisieren undbeweisen zu konnen, benotigt man (diskrete)Wahrscheinlichkeitstheorie.

Wahrscheinlichkeitsraum (Definition)

Ein Wahrscheinlichkeitsraum besteht aus

einer Ergebnismenge Ω, bestehend aus denElementarereignissen, und

einer Funktion P : Ω→ R, die jedem Elementarereignis eineWahrscheinlichkeit zuordnet.

Dabei muss gelten:

Fur jedes x ∈ Ω gilt 0 ≤ P(x) ≤ 1. (Die Wahrscheinlichkeitfur ein Elementarereignis liegt zwischen 0 und 1.)∑x∈Ω

P(x) = 1. (Die Summe aller Wahrscheinlichkeiten ist 1.)



Wahrscheinlichkeitsrechnung

Falls Ω endlich ist und alle Elementarereignisse in Ω gleichwahrscheinlich sind, so gilt

P(x) =1

|Ω|fur jedes x ∈ Ω

Beispiel: Wurfeln mit einem fairen Wurfel. Dann giltΩ = 1, 2, 3, 4, 5, 6 und P(x) = 1

6 fur alle x ∈ Ω.

Diese Annahme, dass alle Elementarereignisse gleich wahrscheinlichsind, gilt jedoch nicht immer. (Beispiel: manipulierter Wurfel)




Das Wurfeln einer 1 oder 6 bezeichnet man als(zusammengesetztes) Ereignis, im Unterschied zuElementarereignissen.

Ereignis, Wahrscheinlichkeit eines Ereignisses (Definition)

Wir betrachten einen Wahrscheinlichkeitsraum, bestehend aus Ωund P : Ω→ R. Eine Menge E ⊆ Ω heißt Ereignis. DieWahrscheinlichkeit des Ereignisses E wird folgendermaßenberechnet:

P(E ) =∑x∈E

P(x)

Beispiel: Ereignis E = 1, 6 mit

P(E ) = P(1, 6) = P(1) + P(6) =1

6+

1

6=

1

3




Bemerkung: Fur unsere Zwecke konnen wir alle Teilmengen von Ωals Ereignisse ansehen. Im allgemeinen Fall (insb. fur nicht-diskreteWahrscheinlichkeitsraume) beschrankt man sich auf die Ereignisse,die Elemente einer Ereignisalgebra (oder σ-Algebra) sind.

Rechnen mit Wahrscheinlichkeiten (Satz)

Seien A,B ⊆ Ω Ereignisse:

P(Ω\A) = 1− P(A)

P(A ∪ B) = P(A) + P(B)− P(A ∩ B)

P(∅) = 0

Insbesondere folgt daraus P(A ∪ B) = P(A) + P(B), fallsA ∩ B = ∅, d.h., falls A und B disjunkte Ereignisse sind.




Unabhangigkeit von Ereignissen (Definition)

Zwei Ereignisse A,B ⊆ Ω heißen unabhangig, falls gilt:

P(A ∩ B) = P(A) · P(B)

Beispiel Wurfel:

Die Ereignisse A = 1, 3, 5 (Ergebnis ungerade) undB = 2, 4, 6 (Ergebnis gerade) sind nicht unabhangig. Es gilt:

P(A ∩ B) = P(∅) = 0 6= 1

4=

1

2· 1

2= P(A) · P(B)

Die Ereignisse 1, 3, 5 (Ergebnis ungerade) und 1, 2, 3, 4(Ergebnis kleiner gleich vier) sind unabhangig. Es gilt:

P(A ∩ B) = P(1, 3) =1

3=

1

2· 2

3= P(A) · P(B)




Bedingte Wahrscheinlichkeit (Definition)

Die bedingte Wahrscheinlichkeit ist definiert durch

P(A | B) =P(A ∩ B)

P(B),

falls P(B) 6= 0.

Die Wahrscheinlichkeit P(A | B) ist intuitiv die Wahrscheinlichkeit,dass das Ereignis A eintritt, unter der Bedingung, dass man bereitsweiß, dass das Ereignis B eintritt.

Sprechweise: Wahrscheinlichkeit von A, vorausgesetzt B.




Beispiel Wurfel: A = 1, 3, 5 (Ergebnis ist ungerade) undB = 1, 2, 3 (Ergebnis ist kleiner gleich drei).

Dann gilt:

P(A | B) =P(A ∩ B)

P(B)=

P(1, 3)P(1, 2, 3)

=2

3

Unabhangigkeit und bedingte Wahrscheinlichkeit (Satz)

Zwei (nicht-leere) Ereignisse A,B sind unabhangig genau dann,wenn:

P(A | B) = P(A) und P(B | A) = P(B)

D.h., die Kenntnis, dass das Ereignis B eintreten wird, andert dieWahrscheinlichkeit von A nicht.




Zufallsvariable (Definition)

Eine Zufallsvariable ist eine Abbildung X : Ω→ S .Sei y ∈ S . Man definiert:

P(X (ω) = y) = P(ω ∈ Ω | X (ω) = y)

Analog werden P(X (ω) ≤ y), P(X (ω) ≥ y), P(X (ω) ∈ R) (furR ⊆ S), etc. definiert. (Im ersten und zweiten Fall muss einepartielle Ordnung ≤ auf S definiert sein.)

Bemerkungen:

Trotz des Namens hat eine Zufallsvariable mit einer Variablenrelativ wenig zu tun. Es handelt sich einfach um eine Funktion.

Manchmal schreibt man statt P(X (ω) = y) einfach nurP(X = y).




Sei S eine endliche Menge. Eine Zufallsvariable X : Ω→ S heißtgleichverteilt, falls

P(X (ω) = s) =1

|S |fur alle s ∈ S

Bemerkungen:

Die Ereignismenge Ω muss hier nicht notwendigerweiseendlich sein.

Es gibt noch weitere (diskrete)Wahrscheinlichkeitsverteilungen: geometrische Verteilung,Binomialverteilung, Poisson-Verteilung




Wir wenden nun die Wahrscheinlichkeitstheorie auf denOne-Time-Pad an. Wir nehmen an, dass die Menge der(verschlusselten) Nachrichten aus allen Bitstrings der Lange nbesteht: M = CM = 0, 1n. Genauso ist Ke = Kd = 0, 1n und

E (m, e) = m ⊕ e D(c , d) = c ⊕ d

Die Menge der Elementarereignisse Ω sieht wie folgt aus:

Ω = M × Ke = 0, 1n × 0, 1n

D.h. Elementarereignisse sind Paare von Nachrichten undSchlusseln. Die Nachrichten sind nicht alle gleich wahrscheinlich,fur die Schlussel gilt dies jedoch.




Wir betrachten folgende Zufallsvariable:

msg : Ω→ M, msg(m, e) = m(Projektion auf die erste Komponente)

E : Ω→ CM(die bereits vorher definierte Verschlusselungsfunktion)

Wir setzen pm = P(msg = m) (die Wahrscheinlichkeit dafur, dassNachricht m verschickt wird).




Nach Shannon muss ein perfektes Kryptosystem folgendeEigenschaft erfullen:

Perfektes Kryptosystem

Die Wahrscheinlichkeit, dass eine Nachricht m geschickt wird, istgleich der bedingten Wahrscheinlichkeit, dass m geschickt wird,vorausgesetzt dass die Kodierung c bekannt ist.

Fur den One-Time-Pad bedeutet das fur feste m, c ∈ 0, 1n:

P(msg = m | E = c) = P(msg = m) (∗)

Oder (etwas informeller):

P(m wurde geschickt | c wurde empfangen) = P(m wurde geschickt)




Beweis: Wir zeigen nun, dass der One-Time-Pad dieEigenschaft (*) erfullt.

Es gilt, dass

P(msg = m | E = c) =P(msg = m ∧ E = c)

P(E = c)

Es gilt:P(msg = m ∧ E = c) = P((m, e ′) | e ′ ∈ Ke ,E (m, e ′) = c). Eskann nur einen Schlussel e ′ = c ⊕m geben, der m zu cverschlusselt. Also handelt es sich bei der Menge um einElementarereignis und es gilt:

P((m, c ⊕m)) = pm ·1

2n

Die letzte Beziehung gilt, da m und der Schlussel unabhangigvoneinander gewahlt werden.




Außerdem gilt:

P(E = c) =∑m′∈M

P(msg = m′ ∧ E = c)

=∑m′∈M

pm′ ·1

2n=

1

2n·∑m′∈M

pm′ =1

2n· 1 =

1

2n

Zusammengefasst:

P(msg = m | E = c) =pm · 1

2n

12n

= pm = P(msg = m)

und damit ist der One-Time-Pad ein perfektes Kryptosystem.



Symmetrische Verschlusselung: DES und AES

Wir betrachten nun moderne symmetrischeVerschlusselungsverfahren.

Alice Bob

(e, e) (e, e)




Die zwei wichtigsten symmetrischen Verschlusselungsverfahrensind:

DES (Data Encryption Standard): war ab 1976 lange Zeit derde-facto-Standard fur symmetrische Verschlusselungsverfahrenund wird immer noch in großem Maßstab eingesetzt.Allerdings ist die Schlussellange (56 Bit) heute zu kurz undnur noch die Variante Triple DES gilt als sicher.

AES (Advanced Encryption Standard): 2002 wurde bei einemWettbewerb des US-amerikanischen NIST (National Instituteof Standards and Technology) das Kryptosystem Rijndael alsNachfolger fur DES ausgewahlt.




Sowohl DES als auch AES sind Blockchiffre, die nach folgendemPrinzip funktionieren:

Eine Nachricht wird in Blocke der Lange n Bits(typischerweise n = 128, 192, 256) aufgespalten und jederBlock wird einzeln verschlusselt. Wir konnen also imFolgenden davon ausgehen, dass M = 0, 1n

Es gibt einen symmetrischen Schlussel der Lange `(typischerweise ` = 128, 256). D.h., Ke = Kd = 0, 1`.Ein Block der Lange n wird durch die Verschlusselung wiederzu einem Block der Lange n, d.h., CM = 0, 1n.

Aus der gleichen Lange von Nachricht und verschlusseltem Textkann man schließen, dass die Verschlusselungsfunktion fur einenfesten Schlussel bijektiv sein muss.




Die Verschlusselungsfunktion E : 0, 1n × 0, 1` → 0, 1n wirdwie folgt realisiert: eine Nachricht m ∈ 0, 1n wird mit einemSchlussel e ∈ 0, 1` in k Runden verschlusselt. Zu Beginn giltm0 = m, man bestimmt mi+1 durch

mi+1 = Ei (mi , ei ),

wobei ei der Schlussel der i-ten Runde ist. Der Rundenschlussel eiwird mit Hilfe eines festgelegten Verfahrens aus e berechnet.




Die Verschlusselungsfunktion Ei wird durch Aneinanderreihungverschiedener Transformationen berechnet, wobei eineTransformation folgendes sein kann:

xor-Verknupfung des zu verschlusselnden Textes mit demRundenschlussel (AddRoundKey)

Jedes Byte der Nachricht wird durch ein anderes Bytesubstituiert (diese Substitionen werden in sogenanntenS-Boxen tabelliert). (SubBytes)

Die Bytes der Nachricht werden tabellarisch angeordnet und(spalten- oder zeilenweise) permutiert. (ShiftRows)

Die Bytes der Nachricht werden untereinander auf bestimmteWeise mit xor verknupft. (MixColumns)

Die in Klammern angegebenen englischen Bezeichnungen stammenaus AES.




Bemerkungen:

Ahnliche Operationen wie sie zur Verschlusselung einerNachricht verwendet werden, konnen auch dazu benutztwerden, die Rundenschlussel aus dem Schlussel (bzw. ausTeilen der bisher verschlusselten Nachricht) zu gewinnen.

Bei AES stellt man sich ein Byte auch als Polynom uber demzweielementigen Korper, bestehend aus den Elementen 0, 1,vor. D.h.

b7b6 . . . b0 ∈ 0, 18 entspricht b7x7 + b6x

6 + · · ·+ b0

Dann kann xor durch Addition solcher Polynom und S-Boxendurch Bildung des multiplikativen Inversen (bezuglichMultiplikation modulo eines irreduziblen Polynoms m(x)),gefolgt von einer affinen Transformation, beschrieben werden.




AES benutzt genau eine S-Box, die folgendermaßen funktioniert:

S-Box bei AES (Teil 1)

Fasse das zu substituierende Byte als Polynom p(x) vomGrad 7 uber dem Korper 0, 1 auf.

Bestimme das Inverse q(x) von p(x) modulom(x) = x8 + x4 + x3 + x + 1.D.h., es muss p(x) · q(x) mod m(x) = 1 gelten.




S-Box bei AES (Teil 2)

Angenommen q(x) = c7x7 + c6x

6 + · · ·+ c0. Dann bestimmedas Ergebnis-Byte d7d6 . . . d0 durch folgende affineTransformation:

d0

d1

d2

d3

d4

d5

d6

d7

=

1 0 0 0 1 1 1 11 1 0 0 0 1 1 11 1 1 0 0 0 1 11 1 1 1 0 0 0 11 1 1 1 1 0 0 00 1 1 1 1 1 0 00 0 1 1 1 1 1 00 0 0 1 1 1 1 1

·

c0

c1

c2

c3

c4

c5

c6

c7

+

11000110




Beispiel:

Zu substituierendes Byte: 00110011, entspricht x5 + x4 + x + 1

Inverses: 01101100, entspricht x6 + x5 + x3 + x2

Test: (x5 + x4 + x + 1) · (x6 + x5 + x3 + x2) = x11 + x10 + x8 +x7 + x10 + x9 + x7 + x6 + x7 + x6 + x4 + x3 + x6 + x5 + x3 + x2 =x11 + x9 + x8 + x7 + x6 + x5 + x4 + x2

x11+x9+x8+x7+x6+x5+x4 +x2 ÷ x8 + x4 + x3 + x + 1x11 +x7+x6 +x4+x3 = x3 + x + 1

x9+x8 +x5 +x3+x2 Rest: 1x9 +x5+x4 +x2+x

x8 +x4+x3 +xx8 +x4+x3 +x+1

1




Affine Transformation:

1 0 0 0 1 1 1 11 1 0 0 0 1 1 11 1 1 0 0 0 1 11 1 1 1 0 0 0 11 1 1 1 1 0 0 00 1 1 1 1 1 0 00 0 1 1 1 1 1 00 0 0 1 1 1 1 1

·

00110110

+

11000110

=

11000011

Ergebnis: 11000011 (Vektoren werden von unten nach obengelesen!), entspricht x7 + x6 + x + 1




Bemerkungen:

Die Substitution mittels einer S-Box entspricht einermonoalphabetischen Verschlusselung.

Das Inverse zu einem Polynom kann mit Hilfe des euklidischenAlgorithmus berechnet werden. (Dazu spater mehr bei RSA.)

Zur Entschlusselung gibt es eine inverse S-Box, die dazu daist, die Substitution wieder ruckgangig zu machen.

Die gesamte S-Box ist tabelliert. Siehehttp://en.wikipedia.org/wiki/Rijndael S-box.D.h., in der Praxis muss das Inverse nicht berechnet werden.Durch die algebraische Darstellung kann aber dasKryptosystem besser analysiert werden, um zu zeigen, dass esgegen bestimmte Arten von Angriffen geschutzt ist.




AES S-Box| 0 1 2 3 4 5 6 7 8 9 a b c d e f

---|--|--|--|--|--|--|--|--|--|--|--|--|--|--|--|--|

00 |63 7c 77 7b f2 6b 6f c5 30 01 67 2b fe d7 ab 76

10 |ca 82 c9 7d fa 59 47 f0 ad d4 a2 af 9c a4 72 c0

20 |b7 fd 93 26 36 3f f7 cc 34 a5 e5 f1 71 d8 31 15

30 |04 c7 23 c3 18 96 05 9a 07 12 80 e2 eb 27 b2 75

40 |09 83 2c 1a 1b 6e 5a a0 52 3b d6 b3 29 e3 2f 84

50 |53 d1 00 ed 20 fc b1 5b 6a cb be 39 4a 4c 58 cf

60 |d0 ef aa fb 43 4d 33 85 45 f9 02 7f 50 3c 9f a8

70 |51 a3 40 8f 92 9d 38 f5 bc b6 da 21 10 ff f3 d2

80 |cd 0c 13 ec 5f 97 44 17 c4 a7 7e 3d 64 5d 19 73

90 |60 81 4f dc 22 2a 90 88 46 ee b8 14 de 5e 0b db

a0 |e0 32 3a 0a 49 06 24 5c c2 d3 ac 62 91 95 e4 79

b0 |e7 c8 37 6d 8d d5 4e a9 6c 56 f4 ea 65 7a ae 08

c0 |ba 78 25 2e 1c a6 b4 c6 e8 dd 74 1f 4b bd 8b 8a

d0 |70 3e b5 66 48 03 f6 0e 61 35 57 b9 86 c1 1d 9e

e0 |e1 f8 98 11 69 d9 8e 94 9b 1e 87 e9 ce 55 28 df

f0 |8c a1 89 0d bf e6 42 68 41 99 2d 0f b0 54 bb 16




Kriterien bei symmetrischen Verschlusselungsverfahren (informell):

Konfusion

Der Zusammenhang zwischen Schlussel und verschlusseltem Textsollte so komplex wie moglich sein.

Diffusion

Jedes Bit der verschlusselten Nachricht sollte von jedem Bit derursprunglichen Nachricht auf moglichst komplexe Weise abhangigsein. Insbesondere sollte sich der verschlusselte Text vollstandigandern, sobald ein Bit der ursprunglichen Nachricht verandert wird.



Asymmetrische Verschlusselung

Wir betrachten nun asymmetrische Verschlusselungsverfahren:

Alice

e

Bob

(e, d)




Geschichte:

1976: Diffie-Hellman-SchlusselaustauschprotokollBeschreibt wie Alice und Bob einen geheimen Schlussel uberein offenes Netzwerk austauschen konnen.

1977: RSA (benannt nach Rivest, Shamir, Adleman)Asymmetrisches Verschlusselungsverfahren (mit Verwendungoffentlicher Schlussel)

Erst viel spater wurde bekannt, dass ganz ahnliche Verfahrenbereits 1973 von Williamson, Cock und Ellis beim GHCQ(Government Communications Headquarters, Teil desbritischen Geheimdiensts) entwickelt wurden.



Asymmetrische Verschlusselung: RSA

Fur RSA benotigen wir Voraussetzungen aus der Zahlentheorie: dieEulersche ϕ-Funktion, der Satz von Euler-Fermat und dereuklidische Algorithmus.

Eulersche ϕ-Funktion

Die Eulersche ϕ-Funktion ϕ : N0 → N0 ist folgendermaßendefiniert:

ϕ(n) mit n ∈ N0 ist die Anzahl der Zahlen zwischen 1 und n,die zu n teilerfremd sind.

ϕ(n) = |m ∈ N0 | 1 ≤ m ≤ n und ggT (m, n) = 1|




Beispiele (Eulersche ϕ-Funktion):

n ϕ(n) n ϕ(n)

0 0 7 61 1 8 42 1 9 63 2 10 44 2 11 105 4 12 46 2 13 12

Fur eine Primzahl p gilt ϕ(pk) = pk − pk−1, insbesondereϕ(p) = p − 1.

Fur zwei Zahlen m, n ∈ N0 mit ggT (m, n) = 1 giltϕ(m · n) = ϕ(m) · ϕ(n).




Satz von Euler-Fermat

Fur zwei Zahlen m, n ∈ Z mit ggT (m, n) = 1 gilt:

mϕ(n) mod n = 1




Losen diophantischer Gleichungen

Gegeben seien a, b, c ∈ Z. Wir suchen Losungen x , y ∈ Z derGleichung

a · x + b · y = c

Diese Gleichung hat genau dann eine Losung, wenn ggT (a, b) | c .

Losungen fur solche Gleichungen konnen mit Hilfe des erweiterteneuklidischen Algorithmus bestimmt werden. Dieser bestimmt nichtnur ggT (a, b), sondern auch Werte fur x und y .




1. Schritt: Schlusselerzeugung

Bob generiert zwei große Primzahlen p, q mit p 6= q und setztn = p · q.

Bob bestimmt ϕ(n)(in diesem Fall gilt ϕ(n) = (p − 1) · (q − 1)).

Bob bestimmt d , e ∈ 0, . . . , ϕ(n)− 1 mit(d · e) mod ϕ(n) = 1(d.h., d , e sind modulo ϕ(n) zueinander invers)

(e, n) ist der offentliche Schlussel, den Bob bekanntgibt.

(d , n) ist der private Schlussel, den Bob geheimhalt.




2. Schritt: Verschlusselung

Alice will eine Nachricht M an Bob verschlusseln. Sie kodiertdiese Nachricht als eine Zahl m ∈ 0, . . . , n − 1 (z.B. durchBinarkodierung).

Alice rechnet c = me mod n und schickt c an Bob.

3. Schritt: Entschlusselung

Bob empfangt c.

Er rechnet m = cd mod n und erhalt damit wieder dieursprungliche Nachricht.




Rechenbeispiel RSA

p = 5, q = 11, n = 5 · 11 = 55

ϕ(n) = (p − 1) · (q − 1) = 4 · 10 = 40

Wahle e = 3 und berechne das Inverse d = 27:

Lose 3 · x + 40 · y = 1, dies ergibt Losungen x = −13, y = 1

Das ergibt d = x mod 40 = (−13) mod 40 = 27

Nachricht m = 9 soll ubertragen werden. Alice berechnet dieKodierung c = 93 mod 55 = 729 mod 55 = 14.

Code c = 14 kommt an. Bob rechnet

1427 mod 55 = (143 mod 55)9 mod 55

= (2744 mod 55)9 mod 55 = 499 mod 55

= (493 mod 55)3 mod 55 = (117649 mod 55)3 mod 55

= 43 mod 55 = 64 mod 55 = 9 = m




Warum funktioniert RSA?

Korrektheit: Warum erhalt Bob wieder die ursprungliche Nachricht?

Das kann mit dem Satz von Euler-Fermat nachgewiesen werden.

Es gilt (e · d mod ϕ(n)) = 1 und damit gibt es eine Zahl z ∈ Z mite · d = z · ϕ(n) + 1. Also ergibt sich beim Verschlusseln undanschließenden Entschlusseln:

(me mod n)d mod n = me·d mod n = mz·ϕ(n)+1 mod n

= (m · (mϕ(n))z) mod n = m · 1z mod n = m mod n = m

Diese Argumentation funktioniert nicht, falls m, n nicht teilerfremdsind. In diesem Fall kann man aber mit Hilfe des ChinesischenRestsatzes nachweisen, dass man trotzdem das richtige Ergebniserhalt.




Warum funktioniert RSA? (Fortsetzung)

Sicherheit: Warum ist es fur andere schwierig, die Nachricht zuentschlusseln?

Das liegt (im Wesentlichen) daran, dass man d nur dann leicht ause berechnen kann, wenn man ϕ(n) kennt. Um ϕ(n) zu berechnen,musste man die Primfaktorzerlegung von großen Zahlen (ca.1024–2048 Bits) bestimmen, was sehr schwer ist.

Wir werden uns das noch genauer ansehen und uns uberlegen,welche Voraussetzungen erfullt sein mussen, damit RSA sicher ist.




Weitere Bemerkungen:

Auch bei einer sinnvollen Implementierung der Potenzierungbei der Ver- und Entschlusselung ist RSA kein sehr effizientesVerfahren.

Daher wird im Allgemeinen RSA nur zum Schlusselaustauschverwendet. Sobald ein geheimer Sitzungsschlussel vereinbartist, kann ein symmetrisches Verschlusselungsverfahren (z.B.AES) verwendet werden.



Sicherheit von Kryptosystemen

Bisher ist noch nicht klar, warum die bisher vorgestelltenKryptosysteme sicher sind. Wir wissen noch nicht einmal, was“sicher” uberhaupt bedeutet.

Wir betrachten zunachst einmal, welche Arten von Angriffen aufein Kryptosystem moglich sind:

Ciphertext-only attack

Nur die verschlusselte Nachricht oder mehrere verschlusselteNachrichten sind bekannt. (Je mehr Nachrichten bekannt sind,desto besser.)

Known-plaintext attack

Nicht nur eine verschlusselte Nachricht, sondern auch diedazugehorige unverschlusselte Nachricht sind bekannt.Das Ziel ist es, den verwendeten Schlussel zu ermitteln.




Chosen-plaintext attack

Der Angreifer hat die Moglichkeit, dem Verschlusseler einebestimmte Nachricht unterzuschrieben, die verschlusselt wird.

Beispiel: Im 2. Weltkrieg wurden von den Alliierten bestimmteBereiche des Meeres vermint, damit die Kryptoanalytiker inBletchley Park Nachrichten mit dem Wort “Minen” abfangenkonnten, um damit den Code der Enigma zu entschlusseln.

Chosen-ciphertext attack

Der Angreifer hat die Moglichkeit eine unter einem unbekanntenSchlussel verschlusselte Nachricht zu wahlen und die dazugehorigeentschlusselte Nachricht zu erhalten.

Dies ist beispielsweise moglich, wenn ein Schlussel auch zumSignieren verwendet wird.




Wir betrachten hier nicht die folgenden Arten von Angriffen (dieaber in der Praxis auch sehr wichtig sind!):

Side channel attack

Angriff auf eine bestimmte physikalische Implementierung einesKryptosystems, indem das kryptographische Gerat wahrend derVerschlusselung beobachtet wird.

Beispiel: aus der Laufzeit des Verschlusselungsalgorithmus konnenRuckschlusse auf die Schlussellange gezogen werden (sogenanntetiming attack).




Bei fruheren Verschlusselungsverfahren setzte man oft darauf, dassder Angreifer das Verschlusselungsverfahren nicht kannte (Securityby Obscurity).

Heute fordert man, dass ein Verschlusselungsverfahren auch dannsicher sein muss, wenn der Algorithmus bekannt ist. (Der Schlusselselbst muss naturlich unbekannt sein.) Um diese Sicherheit zugewahrleisten, muss ein Kryptosystem einer mathematischenAnalyse unterzogen werden.

Der Begriff “schwierig zu entschlusseln” wird heutzutageinsbesondere mit Mitteln der Komplexitatstheorie definiert unduntersucht.



Wiederholung Komplexitatstheorie

Daher nun eine kurze Wiederholung der wichtigstenkomplexitatstheoretischen Begriffe.

Kurze Vorausschau: leider wird sich herausstellen, dass der BegriffNP-hart bzw. NP-vollstandig nicht ausreichend sein wird, um einKryptosystem als “schwierig zu entschlusseln” zu klassifizieren. Wirmussen daher im Laufe der Vorlesung auf andere Begriffeausweichen.




Wir definieren zunachst die Klasse aller Sprachen, die von einerdeterministischen Turingmaschine mit Zeitbeschrankung akzeptiertwerden konnen.

Zeitbeschrankte det. TM und akz. Sprachen (Definition)

Sei f : N0 → N0 eine (totale) Funktion. Die Klasse TIME(f (n))besteht aus allen Sprachen A, fur die es eine deterministischeMehrband-Turingmaschine M gibt mit A = T (M) undtimeM(x) ≤ f (|x |) fur alle Worter x .

Dabei gibt timeM(x) die Anzahl der Rechenschritte von M beiEingabe x an.

Das heißt, die Anzahl der Schritte der Turingmaschine istbeschrankt und die Beschrankung ist abhangig von der Lange derEingabe.




definieren, die von deterministischen Turingmaschinen mitpolynomialer Laufzeitbeschrankung erkannt werden.

Komplexitatsklasse P (Definition)

P = A | es gibt eine det. Turingmaschine M und ein

Polynom p mit T (M) = A und timeM(x) ≤ p(|x |)=

⋃p Polynom

TIME(p(n))

Intuitiv umfasst P alle Probleme, fur die effiziente Algorithmenexistieren.




Analog zur Komplexitatsklasse P kann man auch eine Klasse FPvon Funktionen definieren, die in polynomieller Zeit berechnetwerde konnen.

Funktionsklasse FP

FP ist die Klasse aller Funktionen der Form f : Σ∗ → Σ∗, fur die eseine deterministische Turingmaschine M und ein Polynom p gibt,so dass

M berechnet die Funktion f und

timeM(x) ≤ p(|x |) fur alle Worter x ∈ Σ∗.




Ahnlich wie bei deterministischen Turingmaschinen kann man auchzeitbeschrankte nichtdeterministische Turingmaschinen und diedazugehorigen Sprachklassen definieren.

Zeitbeschrankte nichtdet. TM und akz. Sprachen (Definition)

Sei f : N0 → N0 eine (totale) Funktion. Die Klasse NTIME(f (n))besteht aus allen Sprachen A, fur die es eine nichtdeterministischeMehrband-Turingmaschine M gibt mit A = T (M) undntimeM(x) ≤ f (|x |) fur alle Worter x .

Dabei gilt

ntimeM(x) =

minLange akzeptierender

Rechnungen von M auf x falls x ∈ T (M)0 falls x 6∈ T (M)




Komplexitatsklasse NP (Definition)

NP =⋃

p Polynom

NTIME(p(n))

Offensichtlich gilt P ⊆ NP.

Aber gilt auch P 6= NP? P 6= NP-Problem (ungelost)




Analog zum Begriff der Reduzierbarkeit in derBerechenbarkeitstheorie definieren wir nun den Begriff derpolynomialen Reduzierbarkeit.

Polynomiale Reduzierbarkeit (Definition)

Gegeben seien Sprachen A ⊆ Σ∗, B ⊆ Γ∗. Dann heißt A auf Bpolynomial reduzierbar (in Zeichen A ≤p B), falls es eine totaleund mit polynomialer Laufzeit (deterministisch) berechenbareFunktion f : Σ∗ → Γ∗ gibt, so dass fur alle x ∈ Σ∗ gilt:

x ∈ A ⇐⇒ f (x) ∈ B.




Anschaulich bedeutet Reduktion, dass wir mit Hilfe von f aus einerMaschine MB fur das Problem B immer eine Maschine MA fur dasProblem A konstruieren konnen. Dabei hat dieVorverarbeitungsfunktion f polynomielle Laufzeit.

Nein

Ja

MA

f MBx f (x)




NP-hart, NP-vollstandig (Definition)

Eine Sprache A heißt NP-hart, falls fur alle Sprachen L ∈ NP gilt:L ≤p A.Eine Sprache A heißt NP-vollstandig, falls A NP-hart ist undA ∈ NP gilt.

Das bedeutet: eine NP-vollstandige Sprache ist mindestens soschwierig wie jedes andere Problem in NP.




Beispiel: Erfullbarkeitsproblem SAT

Eingabe: eine aussagenlogische Formel F

Ausgabe: Hat F eine erfullende Belegung? Das heißt, gibt eseine Belegung der atomaren Aussagen mit 0 bzw. 1, so dass Funter dieser Belegung den Wert 1 hat?

SAT ist das klassische Beispiel fur ein NP-vollstandiges Problem.




Sobald man von einer NP-vollstandigen Sprache (wie beispielsweiseSAT) zeigen konnte, dass sie in P (nicht) enthalten ist, ware dasP 6= NP-Problem gelost.

NP-Vollstandigkeit und P

Sei A NP-vollstandig. Dann gilt

A ∈ P ⇐⇒ P = NP

Bemerkung: Daraus folgt unmittelbar, dass auchA 6∈ P ⇐⇒ P 6= NP fur jedes NP-vollstandige Problem A gilt.




Neben NP ist oft auch die Klasse aller Komplemente vonNP-Problemen interessant.

Komplexitatsklasse co-NP (Definition)

Die Komplexitatsklasse co-NP enthalt genau die Sprachen, derenKomplement in NP liegt.

SAT = F | F ist eine erfullbare aussagenlogische Formel

liegt in NP; das Komplement von SAT, namlich

UNSAT = F | F ist eine unerfullbare aussagenlogische Formel

liegt per Definition in co-NP.

Ebenso liegt das Gultigkeitsproblem in co-NP.

Man weiß weder, ob NP ⊆ co-NP, noch ob co-NP ⊆ NP. Es giltjedoch P ⊆ NP ∩ co-NP.



Kryptographie und die Komplexitatsklasse NP

Wir machen nun einen ersten Versuch, um den Begriff der“Schwierigkeit” fur das Entschlusseln von Kryptosystemen zudefinieren. Wir betrachten ein asymmetrischesVerschlusselungsverfahren, bei dem der offentliche Schlusselbekannt ist.

Die Verschlusselungsfunktion E : M × Ke → CM und dieEntschlusselungsfunktion D : CM × Kd → M liegen in FP.

Jede Funktion D ′ : CM × Ke → M mit E (D ′(c , e), e) = c furalle c ∈ CM, e ∈ Ke liegt nicht in FP.

Bemerkung: Falls die Verschlusselung eindeutig ruckgangiggemacht werden kann, konnte man hier auch D ′(E (m, e), e) = mfur alle m ∈ M fordern.

Aber vielleicht ist die Forderung, dass D ′ nicht in FP liegt, nochetwas zu schwach . . .




Entschlusselungsproblem liegt in NP (Satz)

Wir betrachten ein asymmetrisches Kryptosystem, fur das gilt:

M,CM ⊆ Σ∗

Die Verschlusselungsfunktion E : M × Ke → CM liegt in FP.

Falls E (m, e) = c gilt, so ist m hochstens polynomiell großerals c (D.h., p(|c |) ≥ |m| fur ein Polynom p.)

Dann liegt die Sprache

LE = (m′, c , e) | ∃u ∈ Σ∗ : E (m′u, e) = c

in NP.

Intuition: Mit LE kann man entscheiden, ob m′ Prafix einerNachricht ist, die mit e zu c verschlusselt wird.




Beweis:

Die nichtdeterministische Turingmaschine, die LE entscheidet, ratu und uberpruft, ob E (m′u, e) = c.

Da hochstens p(|c |) Zeichen geraten mussen und E in Polynomzeitberechenbar ist, arbeitet die Turingmaschine in polynomiellerZeit.




Bemerkungen:

Die Forderung, dass m hochstens polynomiell großer ist als c,ist sehr naturlich. Normalerweise sind Codeworter genausolang oder langer als die dazugehorigen Nachrichten.

Wenn LE in Polynomzeit berechenbar ware, dann konnte manD ′ einfach berechnen: seien c und e gegeben.

Setze m0 = ε.Angenommen mi ∈ Σi und wir wissen, dass mi einAnfangsstuck der gesuchten Nachricht m ist. Dannbestimme mi+1, durch Abfragen “(mia, c , e) ∈ LE?” furjedes a ∈ Σ. Falls eine solche Abfrage erfolgreich ist,setze mi+1 = mia.Falls eine Nachricht mn nicht mehr verlangert werdenkann, dann setze D ′(c , e) = m. (Die Iteration terminiert,da |m| beschrankt ist.)




Andererseits: wenn D ′ in FP lage (und außerdemVerschlusselung eindeutig ruckgangig gemacht werden kann),dann liegt LE in P: man muss – gegeben ein Tupel (m′, c , e) –D ′(c , e) bestimmen und uberprufen, ob m′ ein Prafix vonD ′(c , e) ist.

D.h., die Berechnung von LE und D ′ ist “gleich schwierig”. Dasich Begriffe wie NP-Vollstandigkeit nur auf Sprachen beziehen,nicht auf Funktionen, ist es gunstiger mit demEntscheidungsproblem, namlich LE , zu arbeiten.




Um die Berechnung von D ′ so schwierig wie moglich zu machen,konnte man jetzt folgendes fordern:

Mogliche Forderung an Kryptosysteme

Fur ein asymmetrisches Kryptosystem mit VerschlusselungsfunktionE muss die Sprache LE NP-vollstandig sein.

Kann man dann – unter der Voraussetzung, dass P 6= NP –wirklich schließen, dass das Kryptosystem sicher ist?




Selbst wenn P 6= NP gelten wurde, reicht diese Forderung nichtaus. Dafur gibt es zwei Grunde:

NP-Vollstandigkeit und Kryptographie

Wir mussen miteinbeziehen, dass der Angreifer auchrandomisierte Berechnungen durchfuhren kann.

Die Funktion D ′ muss fur jedes Element schwer zu berechnensein. Die NP-Vollstandigkeit von LE garantiert nur, dass esElemente gibt, fur die D ′ schwer zu berechnen ist (worst-casevs. average-case).




Bemerkungen:

Fur SAT ist bekannt, dass es nur relativ wenige Formeln gibt,fur die es wirklich schwer ist, nachzuweisen, dass sieunerfullbar sind bzw. eine erfullende Belegung zu finden.Daher sind Werkzeuge fur SAT (sogenannte SAT-Solver) sehrerfolgreich.

Das bedeutet auch, dass SAT ungeeignet ist als Problem, dasals Grundlage fur ein Kryptosystem dienen soll.




Man hat versucht, Kryptosysteme auf NP-vollstandigenProblemen aufzubauen, beispielsweise auf SUBSET-SUM(Merkle und Hellman):

SUBSET-SUM

Eingabe: eine endliche Menge A ⊆ N0 und t ∈ N0

Ausgabe: gibt es eine Teilmenge A′ ⊆ A, deren Summegenau t ist? D.h., gilt

∑a∈A′ a = t?

Leider hat sich inzwischen herausgestellt, dass es docheffiziente Losungsverfahren fur die in dem Kryptosystemverwendeten Instanzen von SUBSET-SUM gibt.




Interessanterweise sind nach derzeitigem Kenntnisstand Problemebesser geeignet, von denen

nicht bekannt ist, ob sie in P liegen und

die auch nicht als NP-vollstandig bekannt sind.

Dazu gehoren insbesondere:

Faktorisierung

Diskreter Logarithmus

Wir werden beide Probleme und die dazugehorigen Funktionenspater noch genauer betrachten.



Randomisierung

Wir betrachten zunachst randomisierte Berechnungen. Eineinteressante Feststellung ist, dass Randomisierung beiBerechnungen helfen kann!

Dazu zunachst ein einfaches Beispiel: Berechnung von π



Randomisierung

Bestimme Zufallspunkte in einem Quadrat und uberprufe, ob sieinnerhalb des eingeschriebenen Kreises liegen:



Randomisierung

Randomisierte Berechnung von π

Wahle zufallig Punkte (x , y) in einem Quadrat mitSeitenlange 1. D.h., x , y ∈ [0, 1].

Bestimme, ob (x , y) innerhalb des Kreises mit Radius r = 12

liegt, der in das Quadrat einbeschrieben ist. Teste dazu, ob(x − 1

2 )2 + (y − 12 )2 ≤ r2 = 1

4 .

Sei n die Gesamtanzahl der Punkte und k die Zahl der Punkteinnerhalb des Kreises. Dann gilt fur die Flache F des Kreises:F = r2π = π

4 und F ≈ kn . Dadurch erhalten wir eine

Naherung fur π.



Randomisierung

Bemerkungen:

Um π wirklich genau berechnen zu konnen, benotigt maneinen guten Zufallszahlengenerator!

Eine andere (klassischere) Moglichkeit, π zu berechnen, ist esden Grenzwert einer Reihe zu bestimmen.

Ein weiteres Beispiel fur ein Problem, bei dem Randomisierunghelfen kann, ist das Sortierproblem: fur eine feste Eingabe hatQuick-Sort eine erwartete Laufzeit von O(n log n), wenn dasPivotelement zufallig gewahlt wird. (Gegenuber einerworst-case-Laufzeit von O(n2) im deterministischen Fall.)



Probabilistische Turingmaschinen

Klassische Turingmaschinen konnen im Allgemeinen keineZufallszahlen erzeugen. Daher betrachten wir nun probabilistischeTuringmaschinen.

Turingmaschine (Definition)

Eine (deterministische) Turingmaschine M ist ein 7-TupelM = (Z ,Σ, Γ, δ, z0,,E ), wobei

Z die endliche Menge der Zustande,

Σ das Eingabealphabet,

Γ mit Γ ⊃ Σ das Arbeitsalphabet oder Bandalphabet,

δ : Z × Γ→ Z × Γ× L,R,N die Uberfuhrungsfunktion,

z0 ∈ Z der Startzustand,

∈ Γ\Σ das Leerzeichen oder Blank und

E ⊆ Z die Menge der Endzustande ist.




Klassische Turingmaschinen haben intuitiv folgendes Aussehen:

e i n g a b e

Automat mitendlich vielenZustanden

Signal furEndzustand

bewegen und Zeichen uberschreibenKopf kann sich nach links und rechts




Bei probabilistischen Turingmaschinen erhalt die Maschine zusatz-lich ein Band mit Zufallsbits, auf dem sie sich beliebig bewegen darf.Diese Bits beeinflussen die Zustandsubergange.

e i n g a b e

Automat mitendlich vielenZustanden

Signal furEndzustand

bewegen und Zeichen uberschreibenKopf kann sich nach links und rechts

0 1 1 0 0 1 0 Band mit ZufallsbitsCoin-Tossing Tape




Nach der Wiederholung von herkommlichen Turingmaschinenfuhren wir nun probabilistische Turingmaschinen ein. Dabeimodifizieren wir die Definition leicht.

Probabilistische Turingmaschine (Definition)

Eine probabilistische Turingmaschine M ist ein 7-TupelM = (Z ,Σ, Γ, δ, z0,,E ), wobei alle Komponenten mit Ausnahmevon δ wie bei einer herkommlichen Turingmaschine definiert sind.Die Uberfuhrungsfunktion δ hat folgendes Aussehen:

δ : Z × Γ× 0, 1 → Z × Γ× L,R,N × L,R,N




Dabei hatδ(z , a, b) = (z ′, c , x , y)

mit z , z ′ ∈ Z , a, c ∈ Γ, b ∈ 0, 1, x , y ∈ L,R,N folgendeBedeutung:

Wenn die Turingmaschine im Zustand z ist, a auf dem Ar-beitsband liest und das Bit b auf dem Band mit Zufallsbitssteht, dannwechselt sie in den Zustand z ′, schreibt ein c , geht auf demArbeitsband in die Richtung x und auf dem Zufallsbit-Bandin die Richtung y .

Wir gehen davon aus, dass der Turingmaschine zu Beginn derBerechnung entsprechende Zufallsbits bereitgestellt werden.




Laufzeitbeschrankung von probabilistischen Turingmaschinen

Wir sagen, dass eine probabilistische Turingmaschine halt, wenn sieauf jeder Eingabe – unabhangig von den verwendeten Zufallsbits –halt, d.h., einen Endzustand erreicht.

Außerdem hat eine probabilistische Turingmaschine einepolynomiale Laufzeit, wenn sie auf jeder Eingabe x – unabhangigvon den verwendeten Zufallsbits – hochstens p(|x |) Schritte macht,wobei p ein Polynom ist.




Wir betrachten die verwendeten Zufallsbit-Folgen alsElementarereignisse. Falls die Turingmaschine auf einem festenWort der Lange n arbeitet, ist die Menge der Elementarereignissewie folgt definiert:

Ω = 0, 1p(n)

Mehr Zufallsbits werden in p(n) Schritten nicht benotigt. Jedesdieser Elementarereignisse ist gleich wahrscheinlich.




Die Tatsache, ob eine Maschine M ein Wort x der Lange nakzeptiert (d.h. am Ende der Berechnung 1 aufs Band schreibt),wird durch eine Zufallsvariable

aM(x) : Ω→ 0, 1

beschrieben. Fur b ∈ Ω gilt aM(x)(b) = 1 genau dann, wenn Mdas Wort x unter Verwendung der Zufallsbits b akzeptiert.

Die Laufzeit einer Maschine M auf einem Wort x ist ebenfalls eineZufallsvariable

tM(x) : Ω→ N0.

Fur b ∈ Ω gibt tM(x)(b) die Anzahl der Schritte an, die dieBerechnung auf x mit den Zufallsbits b in Anspruch nimmt.




Bemerkung:

Probabilistische Turingmaschinen sind nur eine Moglichkeit, denBegriff der randomisierten Berechnung prazise zu fassen.

Wie das oft in der Berechenbarkeitstheorie der Fall ist, gibt es auchandere analoge Berechnungsmodelle.



Probabilistische Komplexitatsklassen

Wir konnen nun die erste probabilistische Komplexitatsklassedefinieren.

Komplexitatsklasse RP (Randomized polynomial time)

Eine Sprache L ⊆ Σ∗ gehort zu der Klasse RP genau dann, wennes eine probabilistische Turingmaschine M mit polynomialerLaufzeit gibt, so dass fur jede Eingabe x ∈ Σ∗ gilt:

1 falls x ∈ L, dann gilt P(M akzeptiert x) = P(aM(x) = 1) ≥ 12 .

2 falls x 6∈ L, dann gilt P(M akzeptiert x) = P(aM(x) = 1) = 0.




Frage: Kann man auch eine hohere Wahrscheinlichkeit als 12

erhalten, wenn das Wort in der Sprache liegt?

Antwort: Ja! Man muss die Maschine nur mehrmals (mit jeweilsanderen Zufallsbits) laufen lassen. Sei M ′ die Maschine, die Mk-mal ausfuhrt und akzeptiert, sobald M einmal akzeptiert. Da diejeweils verwendeten Zufallsbits unabhangig voneinander sind, giltfur x ∈ L:

P(M ′ akzeptiert x nicht) ≤(

1

2

)k

und damit

P(M ′ akzeptiert x) ≥ 1−(

1

2

)k




Wir wollen nun mit Wahrscheinlichkeit großer gleich p akzeptieren.Es gilt

p ≤ 1−(

1

2

)k

⇐⇒ 1

1− p≤ 2k ⇐⇒ k ≥ log2

1

1− p

Dann reicht es, die Maschine M log21

1−p = − log2(1− p)-mallaufen zu lassen. Das ist fur eine feste Wahrscheinlichkeit p nur einkonstanter Faktor.




Beispiel: wir betrachten ganzzahlige Polynome mit n Variablen,d.h., Polynome uber den Variablen x1, . . . , xn, bei denen alleKoeffizienten ganzzahlig sind.

Gegeben sei nun ein solches ganzzahliges Polynom p, dargestelltdurch einen arithmetischen Ausdruck.

Dieses Polynom ist nicht notwendigerweise in ausmultiplizierterForm, d.h., als Summe von Termen der Form a · x i11 · · · · · x inn ,gegeben! Beispielsweise wird es als Produkt von Summenp(x) = (x1 + x2) · (x3 + x4) · · · · · (x2n−1 + x2n) dargestellt. Aufjeden Fall haben wir eine Berechnungsverfahren fur p, welches inPolynomzeit ausfuhrbar ist.

Der Grad eines Polynoms (in ausmultiplizierter Form) ist diemaximale Summe der Exponenten in einem Summanden.Beispielsweise hat p(x1, x2) = 3x3

1x22 + x4

1 + 2x32 + x2

1x2 den Grad 5.




Wir betrachten folgendes Problem:

NON-ZERO-POLY

Eingabe: ein Polynom p mit Grad kleiner gleich k

Ausgabe: ist p nicht identisch zu Null, d.h., gibt esa1, . . . , an ∈ Z, so dass p(a1, . . . , an) 6= 0 gilt?

Bemerkung: Sobald man NON-ZERO-POLY effizient losen kann,konnen auch zwei Polynome p, q effizient auf Ungleichheit getestetwerden. Dazu uberpruft man, ob (p − q) ∈ NON-ZERO-POLY.




Idee zur Berechnung von NON-ZERO-POLY: wahle beliebigeganze Zahlen a1, . . . , an ∈ Z und setze sie in p ein. Das Polynomwird akzeptiert, falls p(a1, . . . , an) 6= 0 gilt.

Dieser Test lauft sicherlich in Polynomzeit, aufgrund desgegebenen arithmetischen Ausdrucks bzw. polynomialenVerfahrens.

Das Verfahren akzeptiert niemals ein Polynom, das identischzu Null ist. D.h., die zweite Bedingung in der Definition vonRP ist auf jeden Fall erfullt.

Wir mussen uns nun noch uberlegen, ob auch die ersteBedingung erfullt ist.




Wahrscheinlichkeit fur Nullstellen (Schwartz-Zippel-Lemma)

Sei p ein ganzzahliges Polynom mit n Variablen und Grad kleinergleich k. Sei außerdem p nicht identisch zu Null. Wenn a1, . . . , anunabhangig und gleichverteilt aus 1, . . . ,N gewahlt werden, sogilt:

P(p(a1, . . . , an) = 0) ≤ k

N




Beweis: die Menge der Elementarereignisse ist Ω = 1, . . . ,Nn,wobei alle Elementarereignisse gleich wahrscheinlich sind. Wirfuhren eine Induktion uber n durch.

n = 1: in diesem Fall haben wir Polynom mit nur einer einzigenVariable x1. Ein solches Polynom kann hochstens k Nullstellenhaben und die Wahrscheinlichkeit, eine davon aus der Menge1, . . . ,N auszuwahlen ist kleiner gleich k

N .

n−1→ n: In diesem Fall lasst sich p schreiben als

p = p0 + p1 · xn + p2 · x2n + · · ·+ pt · x tn,

wobei die pi die Variable xn nicht enthalten. Außerdem ist pt nichtidentisch zum Nullpolynom und hat hochstens Grad k − t. Wirkonnen davon ausgehen, dass t > 0 ist, denn ansonsten hatte pnur Variablen aus x1, . . . , xn−1.




Wir definieren nun folgende Ereignisse:

PN = (a1, . . . , an) ∈ Ω | p(a1, . . . , an) = 0PTN = (a1, . . . , an) ∈ Ω | pt(a1, . . . , an−1) = 0

Es gilt:

P(PN) = P(PN | PTN) · P(PTN) + P(PN | PTN) · P(PTN)

≤ P(PTN) + P(PN | PTN)

Dabei ist PTN = Ω\PTN.Wir schatzen nun noch die beiden Wahrscheinlichkeiten in derSumme ab:

P(PTN) ≤ k−tN , denn pt ist ein Polynom vom Grad k − t mit

weniger Variablen, so dass die Induktionsvoraussetzungzutrifft.




P(PN | PTN) ≤ tN , denn es wird vorausgesetzt, dass

pt(a1, . . . , an−1) 6= 0 gilt. Dies ist der hochste Koeffizient desPolynoms q definiert durch:

q(xn) = p(a1, . . . , an−1, xn)

Dieses Polynom ist nicht identisch mit Null, da der hochsteKoeffizient ungleich 0 ist. Die Wahrscheinlichkeit, dass unterdieser Voraussetzung p(a1, . . . , an) = 0 gilt, ist dieWahrscheinlichkeit, dass wir eine Nullstelle von q wahlen. Unddiese Wahrscheinlichkeit ist kleiner gleich t

N , da q Grad t hat.

Insgesamt ergibt sich:

P(p(a1, . . . , an) = 0) ≤ k − t

N+

t

N=

k

N




NON-ZERO-POLY liegt in RP

NON-ZERO-POLY ∈ RP

Beweis: aufgrund der Voruberlegungen mussen wir uns nur nochuberlegen, dass man die Zahlen a1, . . . , an so wahlen kann, dassp(a1, . . . , an) = 0 mit Wahrscheinlichkeit kleiner 1

2 gilt, falls pnicht identisch Null ist. Nach dem vorherigen Satz konnen wira1, . . . , an zufallig aus der Menge 1, . . . , 2k wahlen.




Fur das Problem NON-ZERO-POLY gibt es noch keinenbekannten deterministischen Polynomzeitalgorithmus.

Falls das Polynom als arithmetischer Ausdruck gegeben ist, dannnutzt es auch nichts, den Ausdruck mit Hilfe desDistributivgesetzes auszumultiplizieren und das Polynom alsSumme von Termen der Form a · x i11 · · · · · x inn darzustellen. DieseDarstellung ist im Normalfall exponentiell großer als derursprungliche Ausdruck.




Es ist relativ leicht, P und RP miteinander zu vergleichen:

P vs. RP

Es gilt P ⊆ RP.

Begrundung: jede deterministische Turingmaschine kann auch alsprobabilistische Turingmaschine aufgefasst werden, die ihrenZufallsbit-Bandinhalt ignoriert.




Außerdem gilt folgende Beziehung zwischen RP und NP:

NP vs. RP

Es gilt RP ⊆ NP.

Beweis: falls L ∈ RP gilt, so gibt es eine probabilistischeTuringmaschine, die ein Wort w ∈ L mit Wahrscheinlichkeit großergleich 1

2 akzeptiert und ein Wort w 6∈ L nie akzeptiert.Dies kann durch eine nicht-deterministische Turingmaschinesimuliert werden, die ihre Zufallsbits selbst rat. Falls w ∈ L, so gibtes eine Folge von Zufallsbits, die zur Akzeptanz von w fuhrt. Fallsw 6∈ L, so gibt es eine solche Folge nicht.




Wir betrachten noch weitere Komplexitatsklassen:

Komplexitatsklasse BPP (bounded-error probabilistic polynomialtime)

Eine Sprache L ⊆ Σ∗ gehort zu der Klasse BPP genau dann, wennes eine probabilistische Turingmaschine M mit polynomialerLaufzeit gibt, so dass fur jede Eingabe x ∈ Σ∗ gilt:

1 falls x ∈ L, dann gilt P(M akzeptiert x) = P(aM(x) = 1) ≥ 34 .

2 falls x 6∈ L, dann gilt P(M akzeptiert x) = P(aM(x) = 1) ≤ 14 .




Bemerkungen:

Es macht wenig Sinn in obiger DefinitionP(M akzeptiert x) ≥ 1

2 und P(M akzeptiert x) ≤ 12 zu

fordern. Dann wurde ein einfacher Munzwurf, bei dem mitWahrscheinlichkeit 1

2 akzeptiert oder nicht akzeptiert wird,den Anforderungen an die Turingmaschine genugen.

Wie bei RP kann die Wahrscheinlichkeit fur eine falscheAntwort vermindert werden, indem man die Maschinemehrfach laufen lasst.

Jedes andere Paar von Zahlen p, q ∈ [0, 1] mit 1 > p > 12 und

0 < q < 12 kann statt 3

4 und 14 verwendet werden.

( Ubungsaufgabe)




Uber das Verhaltnis von RP und BPP weiß man folgendes, wasdaraus folgt, dass man die Akzeptanzwahrscheinlichkeit einerRP-Turingmaschine beliebig erhohen kann.

RP vs. BPP

Es gilt RP ⊆ BPP.

Es ist unbekannt wie sich NP und BPP zueinander verhalten.Bisher ist weder NP ⊆ BPP noch BPP ⊆ NP bekannt.




Zuletzt betrachten wir noch folgende Komplexitatsklasse:

Komplexitatsklasse ZPP (zero-error probabilistic polynomial time)

Eine Sprache L ⊆ Σ∗ gehort zu der Klasse ZPP genau dann, wennes eine probabilistische Turingmaschine M gibt, so dass derErwartungswert der Laufzeit polynomial beschrankt ist und fur jedeEingabe x ∈ Σ∗ gilt:

1 falls x ∈ L, dann gilt P(M akzeptiert x) = P(aM(x) = 1) = 1.

2 falls x 6∈ L, dann gilt P(M akzeptiert x) = P(aM(x) = 1) = 0.




Was bedeutet “der Erwartungswert der Laufzeit ist polynomialbeschrankt”?

Erwartungswert

Fur eine Zufallsvariable X : Ω→ R ist der Erwartungswert

E [X ] =∑ω∈Ω

P(ω) · X (ω) =∑y∈Y

P(X = y) · y ,

wobei Y = X (ω) | ω ∈ Ω ⊆ R die Werte sind, die X annehmenkann.

Fur die Turingmaschinen in der Definition von ZPP heißt das, dassfur jedes Wort x gelten muss: die Zufallsvariable tM(x), die dieLaufzeit von M in Abhangigkeits der Zufallsbits beschreibt, erfulltE [tM(x)] ≤ p(|x |), wobei p ein Polynom ist.




Fur Probleme in ZPP gilt also:

Es gibt Algorithmen fur diese Probleme, die immer die richtigeAntwort geben.

Aber: es ist unklar, ob diese Algorithmen immer polynomialeLaufzeit haben. Im Mittel, wenn man den Erwartungswertbetrachtet, ist die Laufzeit aber polynomial. Intuitiv bedeutetdas, dass die Algorithmen nur sehr selten lange Laufzeitenhaben.




Bemerkungen:

Algorithmen, die arbeiten wie die Turingmaschinen, dieZPP-Probleme entscheiden, nennt manLas-Vegas-Algorithmen: die Laufzeit, aber nicht die Ausgabedes Algorithmus ist randomisiert. Insbesondere ist derErwartungswert der Laufzeit polynomial beschrankt, dieAusgabe ist unabhangig von den Zufallsbits.

Verfahren, bei denen auch die Ausgabe randomisiert ist, nenntman Monte-Carlo-Verfahren. Sie entsprechen denTuringmaschinen fur RP- und BPP-Probleme. Hier ist dieLaufzeit immer polynomial beschrankt, die Ausgabe ist aberabhangig von den Zufallsbits.




ZPP und RP

Ein Problem L liegt in ZPP genau dann, wenn L und seinKomplement in RP liegen.

Zum Beweis dieser Aussage benotigen wir dieMarkow-Ungleichung:

Markow-Ungleichung

Fur eine Zufallsvariable X : Ω→ R+0 und t ∈ R mit t > 0 gilt:

P(X ≥ t) ≤ E [X ]

t




Beweis:

Zunachst beobachten wir, dass ZPP unter Komplementabgeschlossen ist (einfach Ja- und Nein-Ausgange derTuringmaschine vertauschen).

Das bedeutet, dass aus L ∈ ZPP auch L ∈ ZPP folgt. Es reichtdaher fur die Beweisrichtung von links nach rechts aus zu zeigen,dass ZPP ⊆ RP gilt. Die Aussage fur die Komplementproblemefolgt dann sofort.




“⇒”: Wir zeigen nun, dass ZPP ⊆ RP gilt.

Sei L ∈ ZPP und sei M eine probabilistische Turingmaschine, die Lakzeptiert. Der Erwartungswert der Laufzeit von M ist durch dasPolynom p beschrankt.Wir konstruieren eine neue Turingmaschine M ′, die bei Eingabevon x mit n = |x | folgendes macht: sie simuliert M 2p(n) Schrittelang und akzeptiert nur dann, wenn M bis dahin akzeptiert hat.




Es ist klar, dass P(M ′ akzeptiert x) = 0 gilt, falls x 6∈ L.

Außerdem gilt, falls x ∈ L: P(M ′ akzeptiert x) =P(M akzeptiert x in hochstens 2p(n) Schritten) ≥ 1

2 . Dennnach der Markow-Ungleichung uberschreitet eineZufallsvariable das Doppelte ihres Erwartungswertes nur mitWahrscheinlichkeit kleiner gleich 1

2 .

Genauer: P(M ′ akzeptiert x) = 1− P(M ′ akzeptiert x nicht)= 1− P(tM′(x) ≥ 2p(n)) ≤ 1− P(tM′(x) ≥ 2E [tM′(x)])≤ 1− 1

2 = 12 .




“⇐”: Sei nun L eine Sprache die in RP liegt und derenKomplement auch in RP liegt.

D.h., wir haben zwei Turingmaschinen M1, M2, so dass M1 Worterimmer korrekt akzeptiert und M2 Worter immer korrektzuruckweist. Wir nehmen an, dass die Laufzeit beider Maschinendurch das Polynom p beschrankt ist.

Wir lassen M1 und M2 immmer wieder solange parallel laufen bisentweder M1 akzeptiert oder M2 das Wort zuruckweist.Bei einem Durchlauf ist die Wahrscheinlichkeit fur das Eintretendieses Ereignisses mindestens 1

2 . D.h., die erwartete Laufzeit istkleiner gleich:

∞∑i=0

(1

2

)i

2p(n) = 2p(n)∞∑i=0

1

2i= 2p(n)

1

1− 12

= 4p(n)

wobei n die Lange des betrachteten Wortes ist.Barbara Konig “Form. Asp. der Software-Sicherheit und Kryptographie” 163



Dabei ist p(n) die Anzahl der Schritte eines Durchlaufs einerTuringmaschine und 2p(n) die Zahl der Schritte fur beideMaschinen. Ein Durchlauf fur jede Maschine wird mindestensdurchgefuhrt.

Die Wahrscheinlichkeit dafur, dass der (i + 1)-te Durchlauf

benotigt wird, ist kleiner gleich(

12

)i(alle vorherigen Durchlaufe

brachten kein definitives Ergebnis).

Die Reihe konvergiert zu 2 und damit haben wir wiederumpolynomiale Laufzeit.




Analog zu co-NP kann man auch co-RP definieren:

Komplexitatsklasse co-RP (Definition)

Die Komplexitatsklasse co-RP enthalt genau die Sprachen, derenKomplement in RP liegt.

Damit kann man den obigen Satz auch folgendermaßen notieren:

ZPP = RP ∩ co-RP




Es gelten folgende Beziehungen zwischen probabilistischenKomplexitatsklassen:

P ⊆ ZPP = RP ∩ co-RP ⊆ RP ⊆ BPP

RP ⊆ NP

Es ist jedoch nichts uber das Verhaltnis zwischen BPP und NPbekannt.

Außerdem gibt es Vermutungen, dass P und ZPP gleich seinkonnten, aber auch das ist nicht bewiesen.



Primzahltests

Wir betrachten nun den Miller-Rabin-Primzahltest, einprobabilistisches Verfahren, das einer RP-Turingmaschineentspricht. Primzahltests sind wichtig, um furVerschlusselungsverfahren – wie beispielsweise RSA – großePrimzahlen zu finden.

Wenn die eingegebene Zahl eine Primzahl ist, dann gibt derAlgorithmus dies auch immer aus. Wenn die Zahlzusammengesetzt, d.h., keine Primzahl, ist, dann irrt er sich mitWahrscheinlichkeit kleiner gleich 1

2 .

Das bedeutet auch, dass man sich auf den Test verlassen kann,wenn er behauptet, dass eine Zahl zusammengesetzt ist.



Primzahltests

Wir zeigen also, dass folgendes Problem in RP liegt:

COMPOSITE

Eingabe: eine naturliche Zahl n > 1

Ausgabe: ist n zusammengesetzt, d.h., gibt es naturlicheZahlen k , ` > 1 mit n = k · `?

Das Komplement von COMPOSITE ist das Problem PRIMES, dasauch in RP (und wie COMPOSITE sogar in P) liegt. Allerdingswerden wir das hier nicht zeigen.

PRIMES

Eingabe: eine naturliche Zahl n > 1

Ausgabe: ist n eine Primzahl?



Primzahltests

Die erste Idee, die hinter dem Miller-Rabin-Primzahltest steckt, istdie folgende:

Fermat-Zeugen

Sei n > 1 eine naturliche Zahl und a ∈ 1, . . . , n − 1. Fallsan−1 mod n 6= 1 gilt, so ist n zusammengesetzt.

Man nennt a dann auch einen Fermat-Zeugen dafur, dass nzusammengesetzt ist.

Diese Behauptung folgt unmittelbar aus dem Satz vonEuler-Fermat (siehe weiter oben im Abschnitt uber RSA).



Primzahltests

Idee: Fur ein gegebenes n wahle ein zufalliges a ∈ 1, . . . , n − 1und teste, ob an−1 mod n 6= 1.

Falls ja, gebe “zusammengesetzt” zuruck, ansonsten “prim”.

Dieser extrem einfach Test funktioniert sogar beinahe. Er schlagtnur fur sogenannte Carmichael-Zahlen fehl, das sindzusammengesetzte Zahlen, die sehr wenige Fermat-Zeugen haben.



Primzahltests

Carmichael-Zahlen

Eine zusammengesetzte Zahl n heißt Carmichael-Zahl, falls alleFermat-Zeugen dieser Zahl nicht teilerfremd zu n sind. D.h., jedesa ∈ 1, . . . , n − 1 mit ggT (a, n) = 1 erfullt an−1 mod n = 1.

Bemerkung: Fur alle n gilt: ein Nicht-Fermat-Zeuge a fur n istimmer teilerfremd zu n.

Die kleinste solche Carmichael-Zahl ist 561 = 3 · 11 · 17.

Es ist außerdem bekannt, dass jede Carmichael-Zahl ungerade ist.



Primzahltests

Wenn eine Zahl keine der relative seltenen Carmichael-Zahlen ist,dann gibt es sogar sehr viele Fermat-Zeugen.

Anzahl der Fermat-Zeugen

Sei n eine zusammengesetzte Zahl, die keine Carmichael-Zahl ist.Dann ist die Anzahl der Fermat-Zeugen in 1, . . . , n − 1 großergleich n

2 .

Beweis:

Zur Erinnerung: die Elemente vonZ∗n = a ∈ 1, . . . , n − 1 | ggT (a, n) = 1 bilden eine Gruppebezuglich der Multiplikation.

Wir betrachten nun

B = a ∈ Z∗n | an−1 mod n = 1.



Primzahltests

Man kann leicht zeigen, dass B eine Untergruppe von Z∗n ist (1 ∈ Bund B ist abgeschlossen unter Multiplikation und Inversenbildung).

B ist eine Untergruppe von Z∗n ist aber nicht gleich Z∗n, denn da nkeine Carmichael-Zahl ist, enthalt Z∗n mindestens einenFermat-Zeugen. Nach dem Satz von Lagrange ist die Anzahl derElemente einer Untergruppe ein Teiler der Anzahl der Elemente dergesamten Gruppe. Daher gilt |B| ≤ |Z

∗n |

2 < n2 .

Außerdem sind alle Elemente von Zn\Z∗n Fermat-Zeugen. Daher istdie Zahl der Nicht-Fermat-Zeugen durch n

2 beschrankt.



Primzahltests

Fur Carmichael-Zahlen benotigen wir nun noch ein zusatzlichesKriterium.

Miller-Zeuge

Sei n > 1 und sei b ∈ 1, . . . , n − 1 mit

b 6= 1 b 6= n − 1 b2 mod n = 1

Dann ist n eine zusammengesetzte Zahl.

Die Zahl b heißt auch Miller-Zeuge fur n oder nicht-trivialeQuadratwurzel von 1.

Beweis: es gilt n | (b2 − 1) = (b − 1)(b + 1), jedoch n - b − 1 undn - b + 1. Damit kann n keine Primzahl sein, denn wenn einePrimzahl ein Produkt teilt, teilt sie auch einen der Faktoren.

Bemerkung: b mod n 6= n − 1 ist aquivalent zu b 6≡ −1 (mod n).



Primzahltests

Man kann nun folgendes zeigen:

Wahrscheinlichkeit fur einen Miller-Zeugen

Gegeben sei eine Carmichael-Zahl n, insbesondere ist damit nungerade. Sei außerdem n− 1 = 2k ·m mit m ungerade und k ≥ 1.

Fur ein zufallig gewahltes a ist die Wahrscheinlichkeit, dass sich inder Menge a2i ·m mod n | 0 ≤ i < k ein Miller-Zeuge fur nbefindet, großer gleich 1

2 .

Der Beweis ist recht technisch, ist jedoch ahnlich zu demNachweis, dass eine Zahl n, die keine Carmichael-Zahl ist, mehr alsn2 Fermat-Zeugen hat. Auch hier wird der Satz von Lagrangeverwendet.

Bei Zahlen, die keine Carmichael-Zahlen sind, ist dieWahrscheinlichkeit, einen Miller-Zeugen zu finden, viel geringer.



Primzahltests

Man sucht nun nicht zufallig nach solchen Miller-Zeugen, sondernnutzt folgende Tatsachen aus:

Angenommen, n ist ungerade und der Test fur denFermat-Zeugen schlagt fehl, d.h., an−1 mod n = 1.

Sei nun n − 1 = 2k ·m fur k ≥ 1 und m ungerade.

Falls am mod n = 1 gilt, dann geben wir auf und geben (evtl.zu Unrecht) aus, dass die Zahl eine Primzahl ist.

Ansonsten (am mod n 6= 1) quadrieren wir die Zahl am immer

wieder, bis a2k ·m erreicht ist. Da letztere Zahl kongruent 1modulo n ist, erreichen wir irgendwann den ersten Index i mita2i ·m mod n = 1 (und dies gilt auch fur Indizes großer als i).

Falls nun a2i−1·m mod n 6= n − 1 gilt, so haben wir einenMiller-Zeugen b = a2i−1·m gefunden ( Zahl istzusammengesetzt!). Ansonsten geben wir wieder auf undgeben “prim” aus.



Primzahltests

Bemerkung: in der Folgeam mod n, . . . , a2i ·m mod n, . . . , a2k ·m mod n = an−1 mod nkonnen nur folgende Muster auftauchen.

1, 1, . . . , 1 Primzahl?

?, . . . , ?, 1, . . . , 1 zusammengesetzte Zahl!

?, . . . , ?, n − 1, 1, . . . , 1 Primzahl?

?, . . . , ? bzw. ?, . . . , ?, n − 1 zusammengesetzte Zahl!(kann nur auftreten, falls an−1 mod n 6= 1 und damit a einFermat-Zeuge ist)

Dabei steht ? fur eine Zahl ungleich 1 und ungleich n − 1.



Primzahltests

Beispiel:

Sei n = 561.

Wir wahlen zufallig a = 5 und testen, ob a ein Fermat-Zeugefur n ist: 5560 mod 561 = 1. D.h., 5 ist kein Fermat-Zeuge.

Es gilt 560 = 24 · 35. Wir berechnen

535 mod 561 = 2352·35 mod 561 = 232 mod 561 = 529522·35 mod 561 = 5292 mod 561 = 463523·35 mod 561 = 4632 mod 561 = 67524·35 mod 561 = 672 mod 561 = 1(Das wurde vorher schon berechnet!)

Also ist b = 67 ein Miller-Zeuge und das Verfahren gibt aus,dass 561 zusammengesetzt ist.



Primzahltests

Das Verfahren kann effizient so implementiert werden, dasszunachst am mod n berechnet wird und dann sukzessive Quadrategenommen werden.

Miller-Rabin-Primzahltest

Eingabe: eine ungerade naturliche Zahl n ≥ 3

Wahle zufallig ein a ∈ 1, . . . , n − 1falls ggT (a, n) 6= 1, gebe “zusammengesetzt” aussei n − 1 = 2k ·m mit m ungeradefalls am mod n = 1, gebe “prim” ausfor i = 0 to k − 1 do

falls a2i ·m mod n = n − 1, dann gebe “prim” ausendgebe “zusammengesetzt” aus

Gerade naturliche Zahlen mussen separat getestet werden.Barbara Konig “Form. Asp. der Software-Sicherheit und Kryptographie” 179


Primzahltests

Zusammenfassung (Miller-Rabin-Primzahltest):

Es gibt ein Verfahren, das bei Eingabe einer naturlichen Zahln “prim” oder “zusammengesetzt” ausgibt, wobei

mit einer Wahrscheinlichkeit großer gleich 12

“zusammengesetzt” ausgegeben wird, wenn nzusammengesetzt ist.immer “prim” ausgegeben wird, wenn n eine Primzahl ist.

Das Verfahren hat außerdem polynomiale Laufzeit.

Daher folgt COMPOSITE ∈ RP.

Man kann auch PRIMES ∈ RP nachweisen, daher giltCOMPOSITE ∈ RP ∩ co-RP = ZPP und auchPRIMES ∈ ZPP.

Inzwischen wurde sogar gezeigt, dass PRIMES ∈ P gilt(Agrawal, Kayal, Saxena). Dennoch wird der probabilistischeTest noch bevorzugt, da er wesentlich effizienter ist.



Primzahltests


Ein wichtiges Konzept in der Komplexitatstheorie sind sogenannteZeugen oder Zertifikate, die garantieren, dass ein Wort x in einerSprache L liegt. Fur probabilistische Komplexitatsklassen ist dieSituation wie folgt:

Gibt es fur jedes Wort x ausreichend viele Zeugen fur x ∈ Lund x 6∈ L, so liegt L in ZPP.

Gibt es fur jedes Wort x ausreichend viele Zeugen fur x ∈ L,so liegt L in RP.

Gibt es keine Zeugen, aber erhalt hat man trotzdemausreichend hohe Wahrscheinlichkeiten dafur, dass x ∈ L bzw.x 6∈ L gilt, so liegt L in BPP.



Einwegfunktionen

Wir betrachten nun sogenannte Einwegfunktionen, das sind intuitivFunktionen, die

leicht zu berechnen sind – sie liegen in FP – und

deren Umkehrung fast immer schwer zu berechnen ist(sogenannte preimage resistance)

Zusatzlich fordert man im Allgemeinen auch noch, dass dieUmkehrung sogar dann schwer zu berechnen ist, wenn man einprobabilistisches Verfahren verwendet.



Einwegfunktionen

Wir betrachten im Folgenden nur ehrliche Funktionen. Das sindFunktionen, die ihre Eingabe nicht zu stark verkurzen. Denn wenndie Große des Urbildes nicht polynomial in der Große des Bildes ist,dann kann das Urbild sowieso nicht in polynomialer Zeit gefundenwerden. Damit gabe es triviale Einwegfunktionen, an denen wiraber nicht interessiert sind.

Ehrliche Funktionen

Eine Funktion f : Σ∗ → Γ∗ heißt ehrlich, falls es ein Polynom qgibt, so dass fur alle x ∈ Σ∗ gilt:

|x | ≤ q(|f (x)|)



Einwegfunktionen

Außerdem benotigen wir – um ausdrucken zu konnen, dass dieWahrscheinlichkeit ein Kryptosystem zu entschlusselnvernachlassigbar gering ist – den Begriff einer vernachlassigbarenFunktion.

Vernachlassigbare Funktion

Eine Funktion r : N0 → R+0 heißt vernachlassigbar, wenn es fur

jedes Polynom p (mit p : N0 → N0) eine Zahl C ∈ N0 gibt mit

r(n) <1

p(n)

fur n > C .

Anschaulich: wenn der Funktionswert n groß genug ist, dann fallt rschneller als der Kehrwert jedes Polynoms.



Einwegfunktionen

Einwegfunktion

Eine Funktion f : 0, 1∗ → 0, 1∗ heißt Einwegfunktion, falls

f liegt in FP,

f ist ehrlich und

fur jede probabilistische polynomzeitbeschrankteTuringmaschine M ist die Wahrscheinlichkeit vernachlassigbar,dass M ein korrektes Urbild fur f (x) berechnet, falls x zufalligaus der Menge 0, 1n gewahlt wird.



Einwegfunktionen

Wir betrachten den dritten Punkt der Definition noch etwasgenauer:

Notation:

M(y) sei eine Zufallsvariable, die die Ausgabe derprobabilistischen Turingmaschine M bei Terminierung angibt,wenn die Turingmaschine mit Eingabe y gestartet wurde.

f (M(f (x))) = f (x) bedeutet, dass die Turingmaschine Mkorrekt ein Urbild von f (x) berechnet hat. Da f nicht injektivsein muss, konnen wir nicht erwarten, dass dieses Urbild auchgleich x sein muss.



Einwegfunktionen

Welche Wahrscheinlichkeit genau ist vernachlassigbar?

Elementarereignisse: die Elementarereignisse stammen aus derMenge Ω = 0, 1n × 0, 1q(q′(n)), wobei q das Polynom ist,das die Laufzeit von M beschrankt und q′ das Polynom ist,das die Laufzeit der Maschine beschrankt, die f berechnet.D.h., ein Elementarereignis ist ein Paar bestehend aus einemWort x ∈ 0, 1n und einem Zufallsbit-String b. AlleElementarereignisse sind gleich wahrscheinlich.

Wir betrachten nun folgende Zufallsvariable X nM :

X nM(x , b) =

1 falls M bei Eingabe f (x) und mit Zufallsbits bein Urbild von f (x) bestimmt

0 sonst

Beschrankt wird also die Wahrscheinlichkeit r(n) = P(X nM = 1) =

P(f (M(f (x))) = f (x)), wobei n die Lange von x ist.Barbara Konig “Form. Asp. der Software-Sicherheit und Kryptographie” 187


Einwegfunktionen

Warum fordert man nicht sogar, dass P(f (M(f (x))) = f (x)) furjedes x ∈ 0, 1n vernachlassigbar ist? Die Elementarereignissewurden in diesem Fall nur aus den Zufallsbit-Strings bestehen.

Solche Einwegfunktionen kann es gar nicht geben! Man kann nieverhindern, dass der Entschlusselungsalgorithmus auf bestimmtenverschlusselten Nachrichten korrekt funktioniert. Beispielsweisekonnte die Turingmaschine immer eine feste Nachricht ausgeben.



Faktorisierung

Wir betrachten nun einige mogliche Kandidaten furEinwegfunktionen, zunachst die Funktion pmult:

Primzahlmultiplikation pmult

pmult(p, q) = p · q,

wobei p, q beide k-Bit Primzahlen sind.

Die Funktion pmult liegt in FP. Die Umkehrfunktion musste dieFaktorisierung eines Produkts von Primzahlen bestimmen.



Faktorisierung

Als Entscheidungsproblem kann man das Faktorisierungsproblemfolgendermaßen darstellen:

Faktorisierung

Eingabe: Zwei Zahlen n, r ∈ N0, wobei n das Produkt vonzwei k-Bit Primzahlen ist.

Ausgabe: Besitzt n einen Faktor p 6= 1, der kleiner als r ist?

Eine andere Variante des Entscheidungsproblems fragt, ob das i-teBit des kleineren Faktors gleich 1 ist.

Beide Probleme liegen in NP, es ist jedoch nicht bekannt, ob sieNP-vollstandig sind. Auch aus dem Beweis der NP-Vollstandigkeitund aus P 6= NP kann man nicht notwendigerweise schließen, dasspmult eine Einwegfunktion ist.



Faktorisierung

Auch wenn nicht klar ist, ob pmult wirklich eine Einwegfunktionist, so ist dies durch den RSA Factoring Challenge zumindest“empirisch” uberpruft worden:

http://en.wikipedia.org/wiki/RSA Factoring Challenge

Es gibt darin immer noch zahlreiche Produkte von Primzahlen, diebisher noch nicht faktorisiert wurden.




Um den diskreten Logarithmus definieren zu konnen, benotigen wirzunachst einige Begriffe:

Primitivwurzel modulo m

Eine Zahl g ∈ 0, . . . ,m − 1 heißt Primitivwurzel modulo m, fallsg ein Generator der multiplikativen Gruppe

Z∗m = a ∈ 1, . . . ,m − 1 | ggT (a,m) = 1

ist. D.h., es muss gelten:

gk mod m | k ∈ N0 = Z∗m

Bemerkung: Es gilt |Z∗m| = ϕ(m).




Bemerkungen:

Nicht fur alle m ∈ N0 gibt es Primitivwurzeln. Es gibt jedochauf jeden Fall Primitivwurzeln, falls m eine Primzahl ist.

Nicht jedes Element von Z∗p ungleich 1 ist eine Primitivwurzel,auch wenn p eine Primzahl ist. Beispielsweise gilt fur p = 7:

20 mod 7 = 1, 21 mod 7 = 2, 22 mod 7 = 4,23 mod 7 = 1 2 ist keine Primitivwurzel modulo 730 mod 7 = 1, 31 mod 7 = 3, 32 mod 7 = 2,33 mod 7 = 6, 34 mod 7 = 4, 35 mod 7 = 5,36 mod 7 = 1 3 ist eine Primitivwurzel modulo 7




Wir betrachten die Funktion dexp:

Diskrete Exponentialfunktion

Gegeben seien eine Primzahl p, eine Primitivwurzel g modulo pund x ∈ Z∗p = 1, . . . , p − 1. Wir definieren

dexp(p, g , x) = (p, g , g x mod p)

Die Funktion dexp liegt in FP.

Die Umkehrfunktion, die aus g x mod p (und p und g) deneindeutig bestimmten Exponenten x berechnet, heißt diskreterLogarithmus und gilt als schwer zu berechnen.

Auch fur den diskreten Logarithmus existiert ebenfalls eindazugehoriges Entscheidungsproblem.



Einwegfunktionen

Mit Hilfe von Einwegfunktionen konnte man symmetrischeVerschlusselung realisieren. Dazu mussten Einwegfunktionenjedoch existieren.

Existieren Einwegfunktionen?

das weiß man nicht genau. Man weiß nur, dass folgendes ausder Existenz von Einwegfunktionen folgen wurde:

P 6= NP und NP 6⊆ BPP

es gibt (sichere) symmetrische Verschlusselungsverfahren, diemit kurzen Schlusseln arbeiten (anders als der One-Time-Pad)



Einwegfunktionen

Falls Einwegfunktionen existieren, dann gilt P 6= NP. Außerdemgilt dann NP 6⊆ BPP, d.h., es gibt eine Sprache in NP\BPP.

Beweis: sei f : 0, 1∗ → 0, 1∗ eine Einwegfunktion und sei

Lf = (x , y) | ∃u ∈ 0, 1∗ : f (xu) = y.

Lf liegt in NP, denn u kann geraten und in Polynomzeit uberpruftwerden. Falls P = NP gilt, so ware Lf in Polynomzeit entscheidbar,und man kann Lf dazu benutzen, um in Polynomzeit ein Urbild fureinen gegebenen Funktionswert f (x) zu bestimmen. (SieheArgumentation fur die sehr ahnliche Sprache LE weiter oben.) Dasist ein Widerspruch dazu, dass f eine Einwegfunktion ist.

Außerdem kann Lf nicht in BPP liegen, denn dann gabe es eineprobabilistische Turingmaschine, die mit ausreichend hoherWahrscheinlichkeit Urbilder finden wurde.



Einwegfunktionen

Bemerkung:

Es ist nicht bekannt, ob die umgekehrten Folgerungen gelten: d.h.,man weiß nicht, ob aus P 6= NP oder NP 6⊆ BPP die Existenz einerEinwegfunktion folgt. (Das liegt daran, dass eine Einwegfunktionnicht nur im worst-case schwer zu invertieren sein sollte.)



Einwegfunktionen

In der Praxis werden – neben der Primzahlmultiplikation und derdiskreten Exponentialfunktion – vor allem kryptographischeHashfunktionen (wie MD5, SHA1 oder SHA2) eingesetzt.

Diese arbeiten unter anderem mit bitweiser Rotation undxor-Operationen. (Wir sehen uns spater noch die sogenannteMerkle-Damgard-Konstruktion an, auf der solche kryptographischeHashfunktionen beruhen.)

Wichtig ist fur solche Hashfunktionen auch die Kollisionsresistenz:es sollte sehr schwierig sein, zwei verschiedene Eingabewerte zufinden, die denselben Funktionswert ergeben. (Eine probabilistischepolynomzeitbeschrankte Turingmaschine sollte ein solches Paar vonWerten nur mit vernachlassigbarer Wahrscheinlichkeit findenkonnen.)



Einwegfunktionen

Eine beliebige Einwegfunktion – wenn sie existieren sollte – kannman nicht direkt fur symmetrische Verschlusselung verwenden. DerGrund dafur ist, dass es auch eine dazugehorigeEntschlusselungsfunktion geben muss, die leicht zu berechnen ist.

Aber: die Existenz von Einwegfunktionen garantiert die Existenzvon Pseudo-Zufallsgeneratoren.

Pseudo-Zufallsgenerator (informell)

Ein Pseudo-Zufallsgenerator ist ein deterministisches Verfahren,das aus einem gegebenem Startwert eine Sequenz von Bits erzeugt,die von einer probabilistischen polynomzeit-beschranktenTuringmaschine nicht von einer zufallig erzeugten Bit-Sequenzunterschieden werden kann.



Einwegfunktionen

Anwendungen fur Pseudo-Zufallsgeneratoren:

Nach Austausch eines symmetrischen Schlussels kann dieserals Startwert fur einen Pseudo-Zufallsgenerator verwendetwerden. Damit kann der One-Time-Pad simuliert werden undsichere symmetrische Verschlusselung erreicht werden.

Generierung von Nonces.

Generierung von Zufallszahlen fur randomisierte Verfahren,Derandomisierung von randomisierten Verfahren.



Fallturfunktionen

Fur asymmetrische Verschlusselung mussen wir noch mehr fordern:spezielle Einwegfunktionen, sogenannte Fallturfunktionen.

Fallturfunktion (informell)

Die Verschlusselungsfunktion E eines asymmetrischenKryptosystems heißt Fallturfunktion, wenn

E in Polynomzeit berechenbar ist, wenn der offentlicheSchlussel bekannt ist,

die Entschlusselungsfunktion D in Polynomzeit berechenbarist, wenn der private Schlussel bekannt ist und

die Wahrscheinlichkeit (fur eine probabilistischepolynomzeitbeschrankte Turingmaschine), fur zufalliggewahlte Nachrichten und Schlussel, E nur unter Kenntnis desoffentlichen Schlussels zu invertieren, vernachlassigbar ist.



Fallturfunktionen

Das heißt, es gibt eine “geheime Falltur” (den privaten Schlussel),mit Hilfe derer die Verschlusselungsfunktion doch einfach zuinvertieren ist.

Man vermutet, dass das RSA-Kryptosystem eine Fallturfunktiondarstellt. Dies ist jedoch nicht bewiesen, denn die Existenz einerFallturfunktion wurde auch die Existenz von Einwegfunktionengarantieren.

Außerdem ist unklar, ob daraus, dass die Primzahlmultiplikationeine Einwegfunktion ist, folgt, dass die RSA-Funktion eineFallturfunktion ist.



Fallturfunktionen

Immerhin weiß man aber folgendes uber die Sicherheit von RSA:

Faktorisierungsalgorithmus durch Kenntnis der RSA-Schlussel

Falls die RSA-Schlussel (e, n) und (d , n) bekannt sind, gibt eseinen probabilistischen Polynomzeit-Algorithmus, der n in dieFaktoren p, q aufspaltet.

D.h., man kann zeigen, dass das Finden des privaten Schlusselsgleichbedeutend mit der Faktorisierung von n ist. Das bedeutetnicht, dass das Brechen des Kryptosystems gleichbedeutend mitder Faktorisierung ist.



Fallturfunktionen

Beweis (Skizze): wir betrachten n, e, d , wobei n = p · q dasProdukt zweier Primzahlen ist. Außerdem sind e, d moduloϕ(n) = (p − 1) · (q − 1) zueinander invers.

Das Produkt e · d ist ungerade, denn es gilt e · d ≡ 1 (mod ϕ(n))und ϕ(n) ist eine gerade Zahl. Sei nun e · d − 1 = 2k ·m mit mungerade.

Man wahlt zufallig ein a ∈ 1, . . . , n − 1. Falls ggT (a, n) 6= 1,dann haben wir mit ggT (a, n) einen Teiler von n gefunden.



Fallturfunktionen

Falls ggT (a, n) = 1, dann gilt aed−1 ≡ az·ϕ(n) ≡ 1 (mod n).Das Verfahren zur Faktorisierung von n beruht nun auf derTatsache, dass fur ein zufallig gewahltes solches a dieWahrscheinlichkeit, in der Menge

a2i ·m | 0 ≤ i < k

einen Miller-Zeugen fur n zu finden, großer gleich 12 ist (ohne

Beweis).Angenommen, b ware ein solcher Miller-Zeuge, d.h., n | (b2 − 1),aber n - (b − 1) und n - (b + 1). D.h., es gilt p | (b − 1) undq | (b + 1) (oder umgekehrt).Man bestimmt nun p = ggT (b − 1, n) und q = n

p .



Die funf Welten von Impagliazzo

Es ist unbekannt, ob Einweg- und Fallturfunktionen existieren.Diese Frage hangt mit der Frage nach P 6= NP zusammen, ist abernicht gleichbedeutend.

In seinem Artikel “A Personal View of Average-Case Complexity”hat Russell Impagliazzo die moglichen Antworten auf diese Fragenzusammengestellt und funf daraus resultierende mogliche Weltenbeschrieben.

Er geht dabei davon aus, dass – wenn ein Problem in P liegt – derdazugehorige Polynomzeitalgorithmus bekannt und praktikabel ist.




Algorithmica

In Algorithmica gilt P = NP (oder zumindest NP ⊆ BPP, was imwesentlichen dieselben Auswirkungen hat).

Fast alle Optimierungsprobleme waren einfach.

Programme mussten nur noch die Eigenschaften der Ausgabebeschreiben, das Berechnungsverfahren kann automatischgeneriert werden.

Es gibt keine Einweg- oder Fallturfunktionen.

Alle Kryptosysteme, die mit beschrankten Schlussellangenarbeiten, sind einfach zu brechen.

Es gibt keine Authentifizierungsverfahren.




Heuristica

Heuristica ist die Welt, in der NP-Probleme im worst-caseschwierig zu losen sind, aber fast alle zufallig gewahlten Instanzeneinfach sind. Insbesondere konnen schwere Instanzen nur mitgroßem Aufwand gefunden werden.

Da schwere Probleme sehr selten sind, konnen in der Praxisfast alle Aufgabenstellungen (aus NP) effizient gelost werden.

Auch in Heuristica ist Kryptographie im wesentlichen nichtmoglich, da schwere Instanzen – d.h., schwer zuentschlusselnde Nachrichten – nicht verlaßlich produziertwerden konnen.




Pessiland

Pessiland ist – nach Impagliazzo – die schlimmste aller Welten. Esist einfach, schwere Instanzen von NP-Problemen zu finden, aberes ist nicht moglich, verlaßlich schwere und geloste Instanzen zuerzeugen.

Es gibt wenige Vorteile fur das Losen von Problemen.

Es gibt keine Einwegfunktionen, denn Einwegfunktionen sindgerade ein Verfahren, um effizient schwere und gelosteInstanzen (das Bild der zu versendenden Nachricht unter derEinwegfunktion) zu generieren.

Ebensowenig ist Authentifizierung moglich.




Minicrypt

In Minicrypt kann man schwere und geloste Instanzen vonNP-Problemen generieren, d.h., es existieren Einwegfunktionen.Aber es gibt keine Fallturfunktionen.

Es gibt wenige positive algorithmische Aspekte. Man kannjedoch aus Einwegfunktionen Pseudo-Zufallsgeneratorenerzeugen und damit probabilistische Algorithmenderandomisieren.

Symmetrische Verschlusselung und Authentifizierung sindmoglich.

Asymmetrische Verschlusselungsverfahren sind nicht moglich.




Cryptomania

In Cryptomania existieren zusatzlich noch Fallturfunktionen.

Es gibt immer noch Einwegfunktionen,Pseudo-Zufallsgeneratoren, etc. und auch hier sindsymmetrische Verschlusselung und Authentifizierung moglich.

Zusatzlich sind auch asymmetrische Verschlusselung undzahlreiche andere kryptographische Protokolle (Austausch vongeheimen Schlusseln, digitale Signaturen, elektronischeWahlen, elektronische Bezahlverfahren, etc.) moglich.

Cryptomania entspricht von den praktischen Auswirkungen her amehesten unserer heutigen Welt. Es ist aber nicht klar, ob wirwirklich in Cryptomania leben!



Kryptographische Protokolle: Motivation

Falls wir in Cryptomania leben, gibt es Fallturfunktionen undasymmetrische Verschlusselung. Damit kann man zahlreicheinteressante kryptographische Protokolle gewinnen.


Authentifizierungs- und Identifizierungs-Protokolle

Zero-Knowledge-Protokolle

Munzwurf uber das Telefon

Secure Multi-Party Computations

Blockchain

Wir werden uns im Folgenden einige davon genauer ansehen.




Ein asymmetrisches Kryptosystem, das kommutativ ist, kann auchfur digitale Unterschriften verwendet werden.

Kommutatives, asymmetrisches Kryptosystem

Ein asymmetrisches Kryptosystem heißt kommutativ, fallsM = CM und folgende Bedingung fur die VerschlusselungsfunktionE : M × Ke → M und die EntschlusselungsfunktionD : M × Kd → M gilt:

D(E (m, e), d) = E (D(m, d), e)

fur jedes m ∈ M und jedes Schlusselpaar (e, d) ∈ K .

Beispiel: RSA ist kommutativ, denn es gilt:

D(E (m, (e, n)), (d , n)) = D(me mod n, (d , n)) = (me)d mod n

= (md)e mod n = E (md mod n, (e, n)) = E (D(m, (d , n)), (e, n))




Digitale Unterschrift

Alice, die eine Nachricht m an Bob schicken will,“entschlusselt” diese mit ihrem privaten Schlussel dA, erhalts = D(m, dA) und schickt (m, s) an Bob.

Bob “verschlusselt” s mit Hilfe von Alice’ offentlichemSchlussel eA und uberpruft, ob E (s, eA) = m. Falls ja, soakzeptiert er die Unterschrift.

Aufgrund der Kommutativitat des Kryptosystems ergibt sichaus einer korrekten Signatur wieder die ursprunglicheNachricht.

Nur Alice kennt dA und sie hat durch die Erzeugung von snachgewiesen, dass sie dA besitzt. Denn ohne Kenntnis vondA ist die Entschlusselung zu aufwandig (unter der Annahme,dass E eine Fallturfunktion ist).





Wenn ein Kryptosystem auch zum Signieren verwendet wird,so ist relativ leicht, einen Chosen-Ciphertext-Angriff auf dasKryptosystem durchfuhrbar: man bringt den Teilnehmer dazu,den gewahlten Ciphertext zu signieren.

In der Praxis wird nicht die gesamte Nachricht, sondern einHashwert, der aus der Nachricht gebildet wird, “entschlusselt”und als Signatur mitgeschickt.

Allerdings muss dann eine Hashfunktion gewahlt werden, sodass es schwierig ist, zwei Nachrichten mit demselbenHashwert zu finden (Kollisionsresistenz). Ansonsten konnteder Angreifer Alice eine Nachricht unterschreiben lassen, aberdie andere mit dieser Signatur verschicken.



Identifizierung und Authentifizierung

Identifizierungs- und Authentifizierungsverfahren dienen dazu, dassTeilnehmer in einem Netzwerk gegenuber anderen eindeutig ihreIdentitat nachweisen konnen.

Dies geschieht zumeist dadurch, dass sie nachweisen, einGeheimnis zu kennen, das nur diesem bestimmten Teilnehmerbekannt sein sollte.




Ein typisches Identifizierungsverfahren ist das folgende: dabeikommunizieren Victor (“Verifier”) und Peggy (“Prover”). Peggymochte sich gegenuber Victor identifizieren.

Challenge-Response-Schema mit offentlichem Schlussel

Victor wahlt eine Zufallszahl (einen Nonce) r und berechnetden dazugehorigen Hashwert x = h(r). Er verwendet denoffentlichen Schlussel eP von Peggy, berechnet den Challengec = E (r , eP) und schickt c , x an Peggy (gemeinsam mit seinerIdentitat).

Peggy beschließt, sich Victor gegenuber zu identifizieren. Sieberechnet r = D(c , dP) und uberpruft, ob x = h(r). Dannschickt sie r an Victor.

Victor akzeptiert den Beweis von Peggys Identitat, falls sieden korrekten Wert r zuruckliefert.




Bemerkungen:

Durch die Entschlusselung signiert Peggy den Challenge c . Sieweist dadurch – wie bei einer Signatur – nach, dass sie ihrenprivaten Schlussel kennt.Eine Zufallszahl r (statt einer festen Zahl) wird verwendet,damit kein Replay-Angriff von Dritten durchgefuhrt werdenkann.Durch den Hashwert x weiß Peggy, dass Victor den Wert rbereits kennt. Sie gibt ihm damit keine zusatzlichenInformationen und liefert ihm dadurch keine bisherunbekannte Signatur.Dieses Schema hat Vorteile gegenuber einerPasswort-basierten Identifizierung. Es muss kein Passwortausgetauscht werden und auch wenn ein Angreifer dieKommunikation abhort, kann er sich anschließend nicht alsPeggy ausgeben.




Wir wollen garantieren, dass Peggy außer ihrer Identitat Victorgegenuber keine weiteren Informationen verrat (beispielsweise ihrenoffentlichen Schlussel).

Insbesondere sind wir an Protokollen interessiert, bei denen PeggyVictor davon uberzeugen kann, ein Geheimnis zu kennen, ohnedieses Geheimnis selbst zu verraten. Solche Protokolle sind unterdem Namen Zero-Knowledge-Protokolle bekannt.



Interaktive Beweissysteme

Wir beschreiben zunachst interaktive Beweissysteme, bei denennoch nicht unbedingt verlangt wird, dass keine Informationenpreisgegeben werden.Es gibt eine Eingabe x ∈ Σ∗, die beide Partner kennen. Victor undPeggy senden sich wechselseitig Nachrichten und stellen Anfragen.Victor entscheidet zuletzt, ob x akzeptiert wird.Man macht dabei folgende Beschrankungen:

Victor ist eine polynomzeitbeschrankte probabilistischeTuringmaschine.

Peggy hat unbeschrankte Resourcen, insbesondere darf sienicht-deterministisch arbeiten, beliebig viel Zeit verbrauchenund Zufallsbits verwenden.

Es werden nur polynomial viele Nachrichten ausgetauscht, dieauch nur polynomiale Lange haben.




Wir betrachten ein interaktives Beweissystem furNicht-Graphisomorphie, ein Problem, von dem nicht bekannt ist,ob es in NP oder in BPP liegt.

NON-GRAPHISO

Eingabe: ein Paar (G1,G2), bestehend aus zwei ungerichtetenGraphen G1 = (V1,E1), G2 = (V2,E2). Dabei giltV1 = V2 = 1, . . . , n und eine Kante e ∈ Ei ist einezweielementige Knotenmenge.

Ausgabe: Sind die Graphen G1, G2 nicht isomorph? Das heißt,es gibt keine Permutation π : V1 → V2, so dass v1, v2 ∈ E1

genau dann, wenn π(v1), π(v2) ∈ E2.




Beispiel: wir betrachten folgende zwei Graphen G1,G2

1

3 4

2

1 2

3 4

G1 und G2 sind isomorph, d.h., (G1,G2) 6∈ NON-GRAPHISO.

Eine Permutation, die die Isomorphie nachweist istπ : 1, 2, 3, 4 → 1, 2, 3, 4 mit π(1) = 2, π(2) = 1, π(3) = 4,π(4) = 3.




Das interaktive Beweissystem fur NON-GRAPHISO funktioniertwie folgt: seien G1,G2 zwei Graphen, beide mit Knotenmenge1, . . . , n.

1 Victor wahlt eine Zufallszahl i ∈ 1, 2 und eine zufalligePermutation π : 1, . . . , n → 1, . . . , n.

2 Victor benennt die Knoten von Gi mit Hilfe von π um underhalt dadurch H = π(Gi ). Er schickt H an Peggy und fragtnach einem Index i , so dass Gi und H isomorph sind.

3 Peggy antwortet mit einem Index j .

4 Victor akzeptiert, falls i = j .




Falls G1 und G2 nicht isomorph sind, so kann Peggy – mit ihrenunbeschrankten Resourcen – immer herausfinden, ob H isomorphzu G1 oder zu G2 ist und eine korrekte Antwort schicken.

Falls die Graphen isomorph sind, so kann Peggy nur raten und kanndaher nur in der Halfte der Falle eine korrekte Antwort schicken.




Interaktives Beweissystem fur eine Sprache

Eine Sprache L hat ein polynomiales interaktives Beweissystem,wenn es ein – wie oben beschriebenes – interaktives Beweissystemgibt, das folgende Bedingung erfullt: es gibt einen Verifier V undeinen Prover P, wobei folgendes gilt.

falls x ∈ L liegt, dann ist die Wahrscheinlichkeit, dass V ,Pgemeinsam das Wort x akzeptieren, großer gleich 3

4 .

falls x 6∈ L liegt, dann ist fur jeden (potentiell bosartigen)Prover P ′ die Wahrscheinlichkeit, dass V ,P ′ gemeinsam dasWort x akzeptieren, kleiner gleich 1

4 .

IP ist die Menge aller Sprachen, die ein polynomiales interaktivesBeweissystem haben.




Bemerkungen:

Intuitiv ist P der gutartige Prover, der in der Lage sein muss,den Verifier V mit hoher Wahrscheinlichkeit zu uberzeugen.

Ein bosartiger Prover P ′ – der V evtl. tauschen will – hat nureine niedrige Wahrscheinlichkeit, mit der er V uberzeugenkann (falls das Wort nicht in der Sprache liegt).

Wie bei den probabilistischen Komplexitatsklassen kann mandie Wahrscheinlichkeit fur Akzeptanz bzw. fehlerhafteAkzeptanz durch mehrfache Ausfuhrung des Protokollserhohen bzw. vermindern.




NON-GRAPHISO hat ein polynomiales interaktives Beweissystem,d.h., NON-GRAPHISO ∈ IP:

Falls (G1,G2) ∈ NON-GRAPHISO, d.h., G1, G2 sind nichtisomorph, so antwortet Peggy immer richtig und Victorakzeptiert mit Wahrscheinlichkeit 1.

Falls (G1,G2) 6∈ NON-GRAPHISO, d.h., G1, G2 sindisomorph, so hat Peggy nur eine Wahrscheinlichkeit von 1

2Victor zu Akzeptanz zu bewegen.

Um die Akzeptanzwahrscheinlichkeit im Fehlerfall auf kleiner gleich14 zu drucken, ist es erforderlich, das Beweissystem zweimalauszufuhren und auf Nicht-Isomorphie zu entscheiden, wenn Peggybeide Male den korrekten Index schickt.




Analogie: Biertester

Im Finkenkrug gibt es zwei Sorten von Bier: Alt und Kolsch. Peggybehauptet, mit verbundenen Augen zwischen beiden unterscheidenzu konnen.

Ihr werden die Augen verbunden und sie erhalt in einer Testreihe inzufalliger Reihenfolge mit Alt und Kolsch gefullte Glaser. Der Testgilt als bestanden, wenn Peggy alle Glaser korrekt erkennt.




Man weiß folgendes uber die Beziehung zwischen NP und IP:

NP ⊆ IP

Die Komplexitatsklasse NP ist eine Teilmenge von IP.

Beweis: jedes Wort einer NP-Sprache besitzt ein Zertifikatpolynomieller Lange, das in Polynomzeit verifiziert werden kann.(Ein Zertifikat, das immer funktioniert, ist die Angabe einesakzeptierenden Berechnungspfades in einer gegebenennicht-deterministischen Turingmaschine.)

Peggy kann dieses Zertifikat berechnen und an Victor schicken,wobei Victor das Zertifikat uberpruft. Die Wahrscheinlichkeiten furkorrekte Akzeptanz und fehlerhafte Akzeptanz sind sogar gleich 1bzw. 0.




BPP ⊆ IP

Die Komplexitatsklasse BPP ist eine Teilmenge von IP.

Beweis: Fur ein Problem in BPP kann der Verifier selbst – ohnejede Interaktion mit dem Prover – die Antwort mit der gefordertenWahrscheinlichkeit berechnen.




Von Adi Shamir stammt folgendes wichtige Resultat zu IP:

IP = PSPACE

Die Sprachen, die ein polynomiales interaktives Beweissystemhaben, sind genau die Sprachen, die von (deterministischen)Turingmaschinen mit polynomialer Platzbeschrankung akzeptiertwerden.

Es existieren Sprachen in IP, von denen nicht bekannt ist, ob sie inNP liegen (beispielsweise NON-GRAPHISO, von der nur bekanntist, dass sie in co-NP liegt).




Wir wollen nun prazisieren, was es bedeutet, dass durch eininteraktives Beweissystem kein Wissen preisgegeben wird.

Perfekter Zero-Knowledge-Beweis

Ein Ablauf eines interaktiven Beweissystems P,V auf einerEingabe x erzeugt eine Folge von Nachrichten.Ein solches interaktives Beweissystem ist ein perfektesZero-Knowledge-Beweissystem fur L, wenn es fur jeden –moglicherweise bosartigen – Verifier V ′ eine probabilistischepolynomzeitbeschrankte Turingmaschine M gibt, die bei einerEingabe x ∈ L

dieselbe Menge von Protokollablaufen wie V ′,P erzeugt,

wobei die Protokollablaufe jeweils mit derselbenWahrscheinlichkeit wie in einem echten Beweis von V ′,Pvorkommen.




Bemerkungen:

Die Turingmaschine M wird auch als Falscher (engl. forger)bezeichnet.

Ein Beobachter kann die Menge von Ablaufen von V ′,P nichtvon den von M erzeugten Ablaufen unterscheiden.

Es muss fur jeden Verifier V ′ gefordert werden, dass dieProtokollablaufe von V ′,P simuliert werden konnen, denn esmuss sichergestellt werden, dass nicht nur der gutartigeVerifier V , der sich an das Protokoll halt, sondern auch einbosartiger Verifier nicht in den Besitz von zusatzlichemWissen kommen kann.

Eine andere Definition (Computational Zero-Knowledge)fordert nur, dass die Wahrscheinlichkeitsverteilungen fur dieechten und gefalschten Protokollablaufe nicht inprobabilistischer Polynomzeit unterschieden werden konnen.




Zero-Knowledge-Beweissystem fur NON-GRAPHISO:

Das vorgestellte interaktive Beweissystem fur NON-GRAPHISO istZero-Knowledge, denn eine polynomzeitbeschrankteTuringmaschine M kann bei Eingabe von nicht-isomorphenGraphen G1,G2 die Interaktion dadurch simulieren, dass sie Gi

geeignet permutiert und anschließend selbst die Antwort i schickt.




Analogie: Biertester

Wenn Victor, der die Biersorten auswahlt, und Peggy miteinanderkooperieren, dann konnen sie eine Testreihe durchfuhren, bei derPeggy die Biersorten immer richtig benennt, auch wenn sie sieeigentlich nicht unterscheiden kann.

Dazu muss vorab die Reihenfolge vereinbart werden oder Victorund Peggy einigen sich auf ein geheimes Zeichen.

Ein Beobachter kann aus einem Ablauf kein zusatzliches Wissengewinnen, denn der Ablauf konnte auch “simuliert” sein.Insbesondere weiß er nichts uber die echten Fahigkeiten von Peggy.




Wir betrachten nun einen weiteren Zero-Knowledge-Beweis furGRAPHISO, das Komplement von NON-GRAPHISO. VonGRAPHISO ist bekannt, dass es in NP liegt, aber nicht, ob esNP-vollstandig ist.

1 Peggy wahlt eine zufallige Permutationπ : 1, . . . , n → 1, . . . , n. Sie wendet π auf G1 an underhalt H = π(G1). Dann schickt sie H an Victor.

2 Victor wahlt eine Zufallszahl i ∈ 1, 2 und schickt diese anPeggy.

3 Peggy bestimmt eine weitere Permutation σ – fur die, wennmoglich, H = σ(Gi ) gilt – und schickt σ an Victor.

4 Victor akzeptiert, falls σ(Gi ) = H.




Aus ahnlichen Grunden wie zuvor ist dieses Protokoll eininteraktives Beweisprotokoll. Falls die Graphen G1,G2 isomorphsind, so akzeptieren Victor und Peggy gemeinsam mitWahrscheinlichkeit 1, denn Peggy findet immer eine entsprechendePermutation σ.

Falls die Graphen nicht isomorph sind, dann muss Peggy in derHalfte der Falle mit einer falschen Permutation σ antworten.




Das Protokoll erfullt außerdem die Zero-Knowledge-Bedingungen,denn ein Ablauf kann folgendermaßen von M simuliert werden:gegeben seien zwei isomorphe Graphen G1,G2, M kennt jedochnicht den dazugehorigen Isomorphismus.

M wahlt eine zufallige Permutation σ und einen Index i . Dannbestimmt sie H = σ(Gi ).

Die simulierten Nachrichten sind – der Reihe nach – H, i , σ.

Ein Beobachter kann nicht feststellen, dass H nicht unbedingtdurch Permutation von G1 gewonnen wurde.




Auch im Falle eines bosartigen Verifiers kann jeder Ablauf durcheine probabilistische Turingmaschine M simuliert werden.

Insbesondere folgt aus der Tatsache, dass es sich um einZero-Knowledge-Protokoll handelt, dass der Verifier nicht in denBesitz von Informationen kommen kann, die er nicht selbst inprobabilistischer Polynomzeit berechnen konnte.

Beispielsweise, falls GRAPHISO nicht in BPP liegt (was nichtbekannt ist), dann gewinnt der Verifier aufgrund desBeweissystems keine Informationen uber den Isomorphismuszwischen zwei gegebenen Graphen G1,G2.




Analogie: Verschlossene Tur

In einem Gebaude mit dem folgenden Grundriss gibt es eineverschlossene Tur. Peggy behauptet, dass sie weiß, wie diese Turgeoffnet werden kann. Sie will nachweisen, dass sie die Tur offnenkann, will aber niemanden zeigen, wie das funktioniert.

Tur

XlinkerKorridor Korridor

rechter




Der Test funktioniert folgendermaßen: sie betritt das Gebaude undgeht – ohne dass jemand dies beobachten kann – entweder in denlinken oder rechten Korridor. Anschließend stellt sich Victor – mitetwaigen Zeugen – auf den Punkt X. Er ruft anschließend entweder“links” oder “rechts” und Peggy muss auf diesem Korridor dasGebaude wieder verlassen. Dazu muss sie unter Umstanden dieTure durchqueren.

Wieder konnen Peggy und Victor gemeinsam einen korrektenProtokollablauf simulieren, indem sie sich vorher uber die Folgevon Links-/Rechts-Kommandos verstandigen. Dieser Ablauf kannvon einem Beobachter nicht von einem korrekt ablaufenden Testunterschieden werden.

Außerdem kann auch ein bosartiger Victor kein zusatzliches Wissenuber den Schließmechanismus der Tur erlangen.




Jede Sprache L ∈ BPP hat trivialerweise einZero-Knowledge-Beweissystem. Eine solche Sprache benotigtkeinen “allmachtigen” Prover, sondern der Verifier kann alleBerechnungen selbst ausfuhren.

Damit werden keine Nachrichten ausgetauscht und dasInteraktionsverhalten kann trivialerweise von einer weiterenMaschine M simuliert werden.




Falls Einwegfunktionen existieren, so kann man zeigen, dass jedeSprache in NP (und sogar jede Sprache in IP!) einZero-Knowledge-Beweissystem hat (im Sinne von ComputationalZero-Knowledge).

Wir werden uns dieses Resultat fur NP genauer ansehen (unter derstarkeren Voraussetzung, dass bijektive Einwegfunktionenexistieren). Dafur benotigt man jedoch zunachst Hilfsprotokolle . . .



Bit Commitment

Bit Commitment (Problemstellung)

Bob will, dass Alice sich auf den Wert eines Bits b ∈ 0, 1festlegt.

Alice konnte jetzt ein Bit wahlen und an Bob schicken. Siewill aber, dass Bob erst spater von ihrer Wahl erfahrt.

Wie kann Bob erreichen, dass sich Alice jetzt auf ein Bitfestlegt und spater – wenn sie zusatzliche Informationenbesitzt – nicht bezuglich ihrer Festlegung lugen kann?



Bit Commitment

Anwendung:

Alice und Bob wollen ein Zahlenratespiel spielen:

Alice soll eine Zahl n ∈ 1, . . . , 100 wahlen.

Bob nennt eine Zahl m und Alice sagt, ob m < n, m = n oderm > n gilt.

Bob rat so lange, bis er die korrekte Zahl gefunden hat. Er sollmoglichst wenige Schritte brauchen.

Alice hatte einen Vorteil, wenn sie ihre Zahl wahrend des Spielsandern kann. Von daher ware es gut, wenn sie sich zu Beginn aufeine Zahl festlegen konnte, ohne dass Bob diese Zahl kennt.



Bit Commitment

Voraussetzungen:

Eine bijektive Einwegfunktion f (eine sogenannteEinweg-Permutation).

Ein Hardcore-Pradikat B ∈ FP zu f , so dass B(x) ∈ 0, 1nur mit einer Wahrscheinlichkeit p ≤ 1

2 + ε (wobei εvernachlassigbar ist) in Polynomzeit vorhergesagt werdenkann, wenn f (x) bekannt ist.

Sowohl f als auch B konnen in Polynomzeit berechnet werden.D.h., insbesondere kann B(x) einfach berechnet werden, wenn dasWort x bekannt ist.



Bit Commitment

Kandidaten fur Hardcore-Pradikate:

Bei der diskreten Exponentialfunktion: hochstwertiges Bit

Bei der RSA-Fallturfunktion: niedrigstwertiges Bit

Eine Funktion mit Hardcore-Pradikat ist zwangslaufig eineEinwegfunktion. Außerdem existieren Hardcore-Pradikate, fallsEinwegfunktionen existieren.



Bit Commitment

Bit Commitment (Protokoll)

Ein Einwegfunktion f und ein dazugehoriges Hardcore-Pradikat Bwerden zu Beginn des Protokolls festgelegt.

Alice wahlt ihr Bit b ∈ 0, 1. Sie sucht ein x ∈ Σ∗ mitB(x) = b und schickt C = f (x) (die Festlegung, engl.commitment) an Bob.

Bob empfangt C , kann aus C allerdings keine Informationenuber b erlangen.

Spater kann Alice Bob gegenuber nachweisen, dass sie sichauf b festgelegt hat, indem sie x an Bob schickt.

Bob uberpruft dann, ob C = f (x) gilt und berechnet B(x).



Bit Commitment

Bemerkungen:

Es ist wichtig, dass f eine Einweg-Permutation ist. Ansonstenhat f (x) evtl. mehrere Urbilder, von denen sich Alice spatereines aussuchen kann.

Die Festlegung C werden wir in Zukunft auch mit C (b)bezeichnet.

Wie lang soll x gewahlt werden? Eigentlich sollte die Sicherheit eines Protokolls in derLange der Eingabe gemessen werden. Hier ist die Eingabe (einBit!) jedoch sehr kurz. Von daher nimmt man als Ersatz einenSicherheitsparameter als zusatzliche Eingabe. Dieser isteinfach eine Zeichenkette 1k und in Bezug auf k muss dieErfolgswahrscheinlichkeit fur den Angreifer vernachlassigbarsein.



Bit Commitment

Ein klassische “Anwendung” fur Bit Commitment ist die folgende:

Munzwurf uber das Telefon

Alice und Bob kommunizieren uber das Telefon (bzw. Internet)und wollen gemeinsam eine Zufallszahl bestimmen. Sie vertraueneinander nicht und die Aufgabe soll daher nicht einer der beidenParteien uberlassen werden.

Die grundlegende Idee ist, dass beide ein Bit wahlen und dasZufallsbit durch xor-Verknupfung dieser Bits entsteht. Durch BitCommitment wird verhindert, dass einer der beiden Partner seingewahltes Bit im Nachhinein andert.



Bit Commitment

Bemerkung:

Gleichzeitiges Ubertragen der Bits ist in diesem Berechnungsmodellnicht moglich.

Auf der Idee der gleichzeitigen Ubertragung beruht beispielsweisedas Spiel “Stein, Schere, Papier”, bei dem beide Teilnehmer mehroder weniger gleichzeitig ihre Wahl treffen.



Bit Commitment

Munzwurf uber das Telefon (Protokoll)

Alice wahlt ein Bit a ∈ 0, 1 und schickt eine FestlegungC (a) an Bob.

Bob kennt a nicht und wahlt sein Bit b ∈ 0, 1, welches eran Alice schickt.

Alice weist die Wahl von a nach und gibt das Ergebnis a⊕ bbekannt.



Bit Commitment

Beispiel: wir betrachten als Einwegfunktion die diskreteExponentialfunktion und wahlen die Primzahl p = 19 und denGenerator g = 3.

In diesem Fall verwenden wir folgendes Hardcore-Pradikat

most(x) =

0 falls x ≤ p−1

21 sonst



Bit Commitment

Beispielablauf Munzwurf:

Alice wahlt zufallig das Bit a = 1 und wahlt als x = 14 alsZeugen. Sie schickt f (x) = g x mod p = 314 mod 19 = 4 anBob.

Bob empfangt f (x) = 4 kann daraus jedoch keine Schlusseziehen. Er wahlt zufallig das Bit b = 0 und schickt es an Alice.

Alice ermittelt a⊕ b = 1 und gibt das Ergebnis derMunzwurfes bekannt. Außerdem schickt sie x = 14 an Bob,damit dieser ihre Festlegung nachprufen kann.

Bemerkung: fur reale Anwendungen ist p = 19 naturlich viel zuklein gewahlt!



Zero-Knowledge-Protokolle fur NP-vollstandige Probleme

Wir betrachten nun ein Zero-Knowledge-Protokoll fur ein alsNP-vollstandig bekanntes Problem: Farbbarkeit von Graphen

k-Farbbarkeit von Graphen (k-COL)

Dabei ist k ∈ N0 eine naturliche Zahl.

Eingabe: Ein ungerichteter Graph G = (V ,E ).

Ausgabe: Gibt es eine Zuordnung von k verschiedenen Farbenzu Knoten in V , so dass keine zwei benachbarten Knoten v1,v2 dieselbe Farbe haben?

Fur k ≥ 3 ist k-COL NP-vollstandig.




Beispiele:

Graph ist 3-farbbar, aber nicht2-farbbar

Graph ist 4-farbbar, aber nicht3-farbbar




Computational Zero-Knowledge-Beweissystem fur 3-COL

Wir nehmen an, dass V = v1, . . . , vn.Peggy berechnet eine beliebige 3-Farbung c : V → 1, 2, 3fur G . (Insbesondere gilt c(v1) 6= c(v2), falls v1, v2 ∈ E .)

Peggy schickt Festlegungen C (c(v1)), . . . ,C (c(vn)) an Victor.

Victor wahlt eine zufallige Kante u,w ∈ E und schickt siean Peggy.

Peggy weist gegenuber Victor nach, dass sie die Farben c(u),c(w) gewahlt hat und dass c(u) 6= c(w).

Anmerkungen: fur einen Knoten v ∈ V muss c(v) durch zwei Bitscodiert werden. C (c(vi )) besteht daher eigentlich aus zweiCommitments, ein fur jedes der beiden Bits.




Dieses Beweissystem hat folgende Eigenschaften:

Falls der Graph 3-farbbar ist, dann kann Peggy immer einekorrekte 3-Farbung wahlen und Victor akzeptiert mitWahrscheinlichkeit 1.

Falls der Graph nicht 3-farbbar ist, dann gibt es mindestenseine Kante u, v ∈ E , die “falsch” gefarbt ist, d.h.,c(u) = c(v). Victor hat also eine Wahrscheinlichkeit kleinergleich 1− 1

|E | , eine korrekt gefarbte Kante zu wahlen.

Um eine Wahrscheinlichkeit kleiner gleich 14 zu erhalten, muss

das Protokoll entsprechend oft iteriert werden. Dabei istwichtig, dass Peggy jedes Mal eine neue Farbung wahlt(beispielsweise durch Permutation einer fruheren Farbung),ansonsten erhalt Victor Wissen uber die Farbungsfunktion.




Es handelt sich um einen Zero-Knowledge-Beweis (im Sinne vonComputational Zero-Knowledge). Der Falscher kann das Protokollnicht exakt imitieren, wenn er keine 3-Farbung kennt. Er kannjedoch in einem Durchlauf:

Eine beliebige Kante u,w wahlen und dieser zwei zufalliggewahlte Farben zuordnen. Alle anderen Knoten werdenzufallig gefarbt (was mit großer Wahrscheinlichkeit eineungultige Farbung ergibt).

Er kann nun die entsprechenden Festlegungen fur die Farbenschicken, dann Victor u,w “wahlen” lassen und dieentsprechende Wahl nachweisen.

Ein Beobachter kann dieses Verhalten in Polynomzeit nicht voneinem echten Protokollablauf unterscheiden.




Da 3-COL NP-vollstandig ist, kann man mit Hilfe von Reduktionennun Zero-Knowledge-Beweise fur jedes NP-Problem A konstruieren.

Sei also A in Polynomzeit auf 3-COL reduzierbar (A ≤p 3-COL).Die dazugehorige Reduktionsfunktion bezeichnen wir mit g .

Computational Zero-Knowledge-Beweissystem fur A

Peggy und Victor bestimmen bei einer Eingabe x beide denGraphen G = g(x).

Anschließend wird der Zero-Knowledge-Beweis fur die3-Farbbarkeit von G durchgefuhrt.

Die Antwort von Victor ist dann auch die Antwort auf dieFragen “x ∈ A?”.




Die Standardreduktionsfolge eines NP-Problems A nach 3-COL ist:

Direkte Reduktion auf SAT (Umwandlung dernicht-deterministischen Turingmaschine fur A in eineaussagenlogische Formel)

SAT ≤p 3KNF-SAT

3KNF-SAT ≤p 3-COL

Man kann zeigen, dass alle diese Reduktionen auch diedazugehorigen Zertifikate ineinander umwandeln. Die Zertifikatesind jeweils:

Fur A: erfolgreicher Berechnungspfad der Turingmaschine

Fur SAT und 3KNF-SAT: Modelle der Formeln

Fur 3-COL: Farbungsfunktion des Graphen




Reduktionen die Zertifikate in Zertifikate uberfuhren, nennt manauch Levin-Reduktionen.

Die Existenz von Levin-Reduktionen heißt insbesondere, dass mandurch Reduktionen Zero-Knowledge-Beweise erhalt, bei denenPeggy nicht nur nachweist, dass x ∈ A gilt, sondern auch zeigt,dass sie das dazugehorige Zertifikat kennt. Denn sie weist ja dieKenntnis des Zertifikats fur 3-COL (die Farbungsfunktion) nach.

Es gibt jedoch auch direktere Zero-Knowledge-Beweise furNP-Probleme, die fur praktische Anwendungen vermutlich bessergeeignet sind.




Wir beschaftigen uns jetzt mit Secure Multi-Party Computations:

Alice und Bob berechnen gemeinsam eine zweistellige Funktion

f : I1 × I2 → O1 × O2,

zu der jeder genau einen Parameter kennt, ohne die Parameterselbst bekanntzugeben. Jeder erhalt dabei einen privatenAusgabewert.




Anwendungen:

Elektronische Wahlen: die einzelnen Teilnehmer wollen ihreStimme nicht offentlich bekanntgeben. Es muss jedochtrotzdem das Ergebnis der Wahl bestimmt werden.

Auktionen ohne vertrauenswurdigen Auktionator: kein Bietersoll erfahren, wie die Gebote der anderen Bieter lauten. Nurder Gewinner erfahrt, dass er gewonnen hat und welchen Preiser zahlen muss.




Carolin findet auf dem Speicher ein Bild.




Carolin findet auf dem Speicher ein Bild.Sie will es an Alice oder Bob verkaufen.

Alice: “Ich will das Bild haben.”

Bob: “Ich will das Bild haben.”

Alice: “Lass uns doch eine Auktion durchfuhren. Jeder von unsnennt ein Gebot. Derjenige von uns mit dem hoheren Gebotbekommt das Bild und muss das Geld an Carolin zahlen.”

Bob: “Wenn ich verliere, dann will ich aber nicht, dassirgendjemand mein Gebot erfahrt. Das soll geheim bleiben.”

Alice: “Kein Problem: Dann berechnen wir gemeinsam dasMaximum unserer Gebote, ohne die Gebote bekanntzugeben.”




Alice, Bob und Carolin beschließen, dass das Bild hochstens 3€wert sein kann, die moglichen Gebote sollten also in der Menge0€, 1€, 2€, 3€ liegen.

Falls die Gebote binar codiert sind (a1a0 fur Alice, b1b0 fur Bob),so berechnet sich das Maximum m1m0 durch folgendeaussagenlogische Formel:

m1 = a1 ∨ b1

m0 = (a1 ∧ a0) ∨ (b1 ∧ b0) ∨ (¬a1 ∧ b0) ∨ (a0 ∧ ¬b1)

Alice und Bob konstruieren einen Schaltkreis und werten ihngemeinsam aus.




Hilfsprotokoll: Oblivious Transfer = Unbewusster Transfer

Oblivious Transfer

Gemeinsame Berechnung der Projektions-Funktion:

f : 0, 1k × 1, . . . , k → ∗ × 0, 1f ((c1, . . . , ck), i) = (∗, ci )

Alice und Bob wollen diese Projektion gemeinsam berechnen, sodass:

Alice kennt c1, . . . , ck und erfahrt keine weiterenInformationen.

Bob kennt zu Beginn des Protokolls i und am Ende nur iund ci .



Oblivious Transfer

Voraussetzungen:

Eine bijektive Fallturfunktion (trapdoor permutation) t, derenInverses t−1 nur dann effizient in Polynomzeit berechnetwerden kann, wenn man den privaten Schlussel kennt. Derprivate Schlussel befindet sich im Besitz von Alice.

Ein Hardcore-Pradikat B zu t.



Oblivious Transfer

Protokoll: Oblivious Transfer

1 Alice bestimmt eine Fallturfunktion t mit Hardcore-PradikatB und schickt (t,B) an Bob.

2 Bob wahlt zufallig z1, . . . , zk und schickt(z1, . . . , t(zi ), . . . , zk).

3 Alice erhalt (y1, . . . , yk) und schickt(c1 ⊕ B(t−1(y1)), . . . , ck ⊕ B(t−1(yk))).

4 Bob empfangt (x1, . . . , xk) und bestimmt xi ⊕ B(zi ).



Oblivious Transfer

Korrektheit

Bob berechnet xi ⊕ B(zi ) = ci ⊕ B(t−1(yi ))⊕ B(zi ) =ci ⊕ B(t−1(t(zi )))⊕ B(zi ) = ci

Sicherheit

Alice kann zj und t(zj) nicht unterscheiden und erhalt dadurchkeine Informationen daruber, welches Bit Bob anfordert.

Bob kann aus cj ⊕ B(t−1(zj)) (fur j 6= i) nicht B(t−1(zj)) –und damit cj – bestimmen, da er nur t(t−1(zj)) = zj , nichtaber t−1(zj) kennt.



Oblivious Transfer

Bemerkung:

Das korrekte Verhalten von Bob muss aber erzwungen werden,ansonsten schickt er (t(z1), . . . , t(zi ), . . . , t(zk)) statt(z1, . . . , t(zi ), . . . , zk) und erhalt dadurch alle Bits c1, . . . , cn.

Dazu spater mehr . . .




Wir beschreiben nun die sichere Auswertung eines Schaltkreises,fur den die Teilnehmer jeweils eigene Eingabebits besitzen, die denanderen Teilnehmern unbekannt sind.

Diese Methode stammt von Yao und ist unter dem Namen garbledcircuit oder scrambled circuit bekannt.




Idee

Jede Verbindung zwischen Gattern wird verdopppelt.

Fur jede Belegung r einer Verbindung zwischen Gatternbekommen Alice und Bob Anteile a, b mit r = a⊕ b.

Ein Gatter mit k Eingangen und m Ausgangen wird durch ein“sicheres Gatter” mit 2k Eingangen und 2m Ausgangenersetzt.

r

r

∧

i1 i0

r




Idee




r = a ⊕ b

r = a ⊕ b

ba

r = ra ⊕ rb

S(∧)

i0 = a0 ⊕ b0i1 = a1 ⊕ b1

rbra

b0a1 b1 a0




Idee




ba

r = a ⊕ b

r = a ⊕ b

r = ra ⊕ rb

S(∧)

i0 = a0 ⊕ b0i1 = a1 ⊕ b1

ra rb

a1 b1 a0 b0




Verteilung der Eingabe-Bits

a0 b1a1 b0 Eingabebits

Schaltkreis

Alice Bob




Verteilung der Eingabe-Bits

a1 a0 b1 b0 Eingabebits

y0 x1a1⊕y1 y1 a0⊕y0 b0⊕x0x0b1⊕x1

S(Schaltkreis)

Alice erzeugt Zufallsbits x1, x0 und schickt sie an Bob. Bob erzeugtZufallsbits y1, y0 und schickt sie an Alice.




Auswertung eines not-Gatters:

Alice invertiert ihr Bit.

¬(a⊕ b) = ¬a⊕ ba

¬a b

b

S(¬)

Auswertung eines and-Gatters:

Alice wahlt ein zufalliges Bit z undberechnet rb,b′ = (a1 ⊕ b) ∧ (a0 ⊕ b′)fur alle b, b′ ∈ 0, 1.

Bob erhalt z ⊕ rb1,b0 durch ObliviousTransfer.

z ⊕ (z ⊕ rb1,b0) = (a1 ⊕ b1) ∧ (a0 ⊕ b0)

a0 b0b1a1

S(∧)

z z ⊕ rb1,b0



∧ ∧ ∧

∨

∨

∨

∧

¬¬

∨

m1 m0

1 0 0 1



S(∧) S(∧) S(∧)

S(∨)

S(∨)

S(∨)

S(∧)

S(¬)S(¬)

S(∨)

m1 m0

1 0 0 1

0 1 00 1 1 01



S(∧) S(∧) S(∧)

S(∨)

S(∨)

S(∨)

S(∧)

S(¬)S(¬)

m1 m0

1 0 0 1

0 1 00 1 1 01

1 0,1,0,0

S(∨)



S(∧) S(∧) S(∧)

S(∨)

S(∨)

S(∨)

S(∧)

S(¬)S(¬)

S(∨)

m1 m0

1 0 0 1

0 1 00 1 1 01

1 0,1,0,0



S(∧) S(∧) S(∧)

S(∨)

S(∨)

S(∨)

S(∧)

S(¬)S(¬)

S(∨)

m1 m0

1 0 0 1

0 1 00 1 1 01

1 0

1 1



S(∧) S(∧) S(∧)

S(∨)

S(∨)

S(∨)

S(∧)

S(¬)S(¬)

S(∨)

m1 m0

1 0 0 1

0 1 00 1 1 01

1 0

1 1

0 1,0,0,0



S(∧) S(∧) S(∧)

S(∨)

S(∨)

S(∨)

S(∧)

S(¬)S(¬)

S(∨)

m1 m0

1 0 0 1

0 1 00 1 1 01

1 0

1 1

0 1,0,0,0



S(∧) S(∧) S(∧)

S(∨)

S(∨)

S(∨)

S(∧)

S(¬)S(¬)

S(∨)

m1 m0

1 0 0 1

0 1 00 1 1 01

1 0

1 1

0 0

10

00 1 1 1 1

0 0 1 1

0 0



S(∧) S(∧) S(∧)

S(∨)

S(∨)

S(∨)

S(∧)

S(¬)S(¬)

S(∨)

1 0 0 1

0 1 00 1 1 01

1 0

1 1

0 0

10

00 1 1 1 1

0 0 1 1

1 00 0




Bemerkung:

Zuletzt werden die Ausgabewerte mit Hilfe von xor berechnet.

Wenn jeder Teilnehmer einen privaten Ausgabewert erhalten soll,dann muss noch Alice ihre entsprechende Bits an Bob schicken undumgekehrt.




Weder Alice noch Bob konnen in polynomieller Zeit Informationenuber die Eingabewerte des jeweils anderen bestimmen.(Abgesehen von den Informationen, die sie durch Kenntnis desberechneten Funktionswertes erhalten.)

Unter den Voraussetzungen, dass:

die (bei Oblivious Transfer) verwendeten Funktionentatsachlich Fallturfunktionen mit dazugehorigenHardcore-Pradikaten sind.

sich Alice und Bob korrekt bezuglich des Protokolls verhalten(semi-honest behaviour).




Die Forderung nach halb-ehrlichem Verhalten (semi-honestbehaviour) bedeutet, dass

Die Teilnehmer sich korrekt bezuglich des Protokolls verhalten,

aber alle erhaltenen Informationen mitprotokollieren konnenund aus diesen etwaige Schlusse ziehen.

In manchen Fallen mag die Annahme solches Verhaltensgerechtfertigt sein, beispielsweise wenn die Teilnehmer dazugezwungen werden konnen, mit bereitgestellter Software oderbereitgestellten Geraten zu arbeiten.

Im allgemeinen Fall sollte man jedoch mit bosartigem Verhalten(malicious behaviour) rechnen.




Es gibt die Moglichkeit, ein Protokoll, das korrekt fur halb-ehrlichesVerhalten ist, in ein Protokoll zu ubersetzen, das korrekt furbosartiges Verhalten ist (protocol compilation Goldreich).

Dabei werden als Hilfsprotokolle Bit Commitment undZero-Knowledge-Beweise eingesetzt.

Insbesondere muss jeder Teilnehmer gegenuber den anderenTeilnehmern nachweisen, dass:

die Eingabewerte zu Beginn festgelegt wurden und dass sichalle Berechnungen auf diese Eingabewerte beziehen,

die Zufallsbits tatsachlich zufallig sind und

die korrekte Art von Nachrichten geschickt wurden.

Das ist teilweise extrem aufwandig, da immer sichergestellt werdenmuss, dass der jeweils andere Teilnehmer keine zusatzlicheInformationen erhalt.




Was kann durch ein solches Protokoll nicht erzwungen werden?

Einer der Teilnehmer bricht das Protokoll ab.

Die Teilnehmer verwenden falsche Eingabewerte.

Der zweite Punkt ist bei vielen Anwendungen kein Problem, da dieTeilnehmer eine Motivation haben, den Eingabewert nicht zumanipulieren (z.B. Gebot bei Auktionen, Stimme bei Wahlen).

Im allgemeinen erlaubt man alles, was auch bei der Berechnung derFunktion durch einen vertrauenswurdigen Dritten (trusted thirdparty) passieren konnte.




Erweiterung:

Verwendung des vorgestellten Ansatzes fur beliebig vieleKommunikationspartner (two-party vs. multi-party).

Probleme: hohe Komplexitat durch Austausch vieler Nachrichtenund Erzwingung der semi-honest behaviour.

Es gibt viele Vorschlage von Protokollen fur bestimmteAnwendungen (Auktionen, Wahlen, etc.).



Blockchain

Motivation:

Ziel: Dezentrale Buchfuhrung in Peer-to-Peer-Systemen

Autorisierung von Transaktionen: durch Signaturen

Problem: Double-Spending (ein Betrag wird mehrfachuberwiesen, ein Objekt mehrfach ubertragen), nicht durchSignaturen zu losen

Im realen Leben losen zentrale Instanzen (Banken, Notare, etc.)das Double-Spending-Problem.

Bei einem Peer-to-Peer-Verfahren mussen sich alle Beteiligtendaruber einigen, was der aktuelle Zustand ist. Blockchains stellendafur Mechanismen bereit und implementieren nicht-umkehrbareTransaktionen.

Vorgeschlagen durch Satoshi Nakamoto (Pseudonym) im Jahr 2008



Blockchain

Idee: jedes Eigentum (Geld, Objekte) hat seine eigene Identitat.Bei einer Ubertragung von Eigentumer A zu einem anderenEigentumer zahlt nur die erste Transaktion.

Ein Timestamp Server fasst aufgelaufene Transaktionen in einemBlock zusammen und uberpruft deren Gultigkeit (Signaturenkorrekt, Eigentum wird korrekt ubertragen, kein Double-Spending,etc.). Aus dem Block wird ein Hashwert erzeugt. Als Referenz aufden vorherigen Block wird der Hashwert des vorherigen Blocks inden neuen Hashwert integriert.



Blockchain

Problem: bei der verteilten Implementierung eines solchenTimestamp Servers konnen baumartige Strukturen entstehen:

Verweis durch Hashwert

Verkauf von Objekt X an A

Verkauf von Objekt X an B

Block

Hier ist unklar, was der aktuelle Zustand wirklich ist. Insbesondere:Wem gehort Objekt X?

Losung: nur der langste Pfad – die langste Kette – ist gultig.



Blockchain

Problem: Ein Angreifer kann relativ einfach den fur ihn gunstigstenPfad verlangern und daraus die langste Kette machen.

Losung: es muss schwierig sein, einen Block hinzuzufugen

Proof of Work

Es wird gefordert, dass der erzeugte Hashwert bestimmteBedingungen erfullt (beispielsweise mit einer Folge von Nullenfestgelegter Lange beginnt).Dies kann erreicht werden, indem mit einem Nonce beliebige Bitshinzugefugt werden konnen.

Dadurch kann erreicht werden, dass es fur den Angreifer nichtmoglich oder zu teuer ist, die bisher langste Kette zu uberholen.



Blockchain

Aufbau eines Blocks:

Block

Prev Hash Nonce

...

Transaktionen

Next Hash

Der Nonce wird solange modifiziert, bis die Bedingungen an denHashwert (Next Hash) erfullt sind.



Blockchain

Problem: es gibt aufgrund des Aufwands keinen Anreiz, einenBlock zu erstellen.

Losung: die Erstellung eines Blocks fuhrt zu einer Belohnung.Diese Belohnung wird finanziert durch:

Erzeugung/Mining von Geld (z.B. Bitcoins, derzeit 12,5Bitcoins pro Block)

Erhebung von Transaktionsgebuhren

Anmerkungen:

Die Anzahl der erstellten Blocke ist in etwa proportional zurverfugbaren Rechenleistung (Ausgleich von Schwankungendurch Bildung von Mining Pools)

Das Netz ist schneller als der Einzelne, ein Angreifer kannalleine keine langste Kette erzeugen (wenn er weniger als 50%der Rechenleistung besitzt).



Blockchain

Problem Isolierung: es gibt immer noch einen moglichen Angriff,bei dem Teilnehmer vom Netz getrennt werden und der Angreiferihnen “seine” Version der Blockchain vermittelt.

Losung: die Transaktion wird erst nach einer gewissen Anzahl vonBlocken gultig (beispielsweise wird die gekaufte Ware erst dannubergeben). Je nach der festgelegten Anzahl der Blocke wird diessehr teuer fur den Angreifer, der in dieser Zeit auch nicht minenkann.



Blockchain

Vorteile von Blockchain

Dezentrale Buchfuhrung

Alternative Wahrungen (Bitcoin, etc.)

Neue Finanzierungsmethoden (Initial Coin Offerings)

Implementierung von Regeln/Vertragen (Smart Contracts),siehe Etherium

Nachteile von Blockchain

Probleme bei Verlust des privaten Schlussels

Fehlende Privatsphare

Hoher Stromverbrauch

Kriminelle Aktivitaten

Mining Pools & Kartellbildung



Blockchain


Geldbetrage haben ihre eigene Identitat, damit sienachverfolgt werden konnen: Mechanismen, um Betrageaufzusplitten und zusammenzufuhren (combining and splittingvalues) sind notwendig.

Großer Speicheraufwand fur die Blockchain: Merkle-Baumemit Hashing von Transaktionen

Statt dem rechenintensiven Proof of Work: Proof of Stake(Abstimmung der Stakeholder, Konsens-Algorithmus)

Blockchain kann als eine bestimmte Form von Multi-PartyComputation aufgefasst werden. Dabei ist auch dieKombination mit Zero-Knowledge-Protokollen (ZK-Snarks)interessant.



Blockchain

Literatur/Material:

Satoshi Nakamura: “Bitcoin: A Peer-to-Peer Electronic CashSystem”

Vitalik Buterin: “Ethereum White Paper: A Next GenerationSmart Contract & Dezentralized Application Platform”

CCC-Video zu Blockchains:media.ccc.de/v/33c3-7824-einfuhrung zu blockchains



Blockchain

Weitere Anmerkungen zu Bitcoin:

Einfuhrung im Jahr 2009.

Zur Zeit (Stand: Mai 2018) mehr als 200.000 Transaktionenpro Monat.

Etwa alle 10 Minuten wird ein Block erstellt.

Erstellung der Blocke kann unter blockchain.infobeobachtet werden.

Bitcoin verwendet SHA-256 als kryptographischeHashfunktion.

Die Mining Difficulty wird regelmaßig angepasst: der Hashwertmuss kleiner sein als ein vorgegebener Ziel-Wert.



Verifikation kryptographischer Protokolle

Wir wechseln nun die Sichtweise und beschaftigen uns mit derVerifikation kryptographischer Protokolle. Dabei gehen wir jetztvon folgenden Voraussetzungen aus:

Sowohl symmetrische als auch asymmetrische Verschlusselungist sicher und kann nicht gebrochen werden.

Wir wollen sicherstellen, dass der Angreifer keinerleiMoglichkeit hat, das Protokoll zu unterlaufen. (D.h., erkommt nicht in den Besitz von geheimen Informationen, kannsich nicht fur einen Dritten ausgeben, etc.) Dies soll durch(halb-)automatische Techniken verifiziert werden.

D.h., wir nehmen nicht mehr die komplexitatstheoretischeSichtweise ein, bei der der Angreifer eine polynomzeitbeschrankteprobabilistische Turingmaschine ist.




Die Protokolle, die wir im Folgenden verifizieren werden, sind voneher einfacher Art, dennoch gibt es typischerweise zahlreiche Fehlerin solchen Protokollen.

Mogliche Angriffe auf das Protokoll sind: Man-in-the-Middle,Replay, etc. Angriffe, die das Brechen der Verschlusselungbeinhalten, konnen jedoch nicht entdeckt werden.

Wir betrachten ein Angreifer-Modell (sogenanntesDolev-Yao-Modell), bei dem der Angreifer

beliebig Nachrichten abfangen und weiterverwenden kannkann,

jedoch nicht in der Lage ist, die Verschlusselung zu brechen.




Etwas genauer . . .

Eindringlingsmodell nach Dolev-Yao (I)

Der Angreifer kann

an beliebigen Protokollablaufen teilnehmen,

beliebig Nachrichten abfangen,

Nachrichten entschlusseln, falls er den entsprechendenSchlussel besitzt,

alte Nachrichten wieder einspielen und

aus bekannten Komponenten neue Nachrichten bauen und anbeliebige Kommunikationspartner verschicken.




Eindringlingsmodell nach Dolev-Yao (II)

Der Angreifer kann nicht:

Nachrichten entschlusseln, wenn er den entsprechendenSchlussel nicht besitzt

oder Nonces erraten, die er nicht abgefangen hat.

D.h., er hat nicht nur eine sehr kleine Wahrscheinlichkeit,Nachrichten zu entschlusseln, oder Nonces zu erraten, sondern garkeine Moglichkeit.




Eindringlingsmodell nach Dolev-Yao (III)

Wir nehmen ebenfalls an, dass ein Teilnehmer, der eineverschlusselte Nachricht empfangt,

herausfinden kann, ob diese Nachricht mit einem bekanntenSchlussel K verschlusselt ist.

Er erhalt dann entweder die entschlusselte Nachricht oder eineFehlermeldung.

Analog kann ein Teilnehmer Signaturen (erstellt mit einem privatenSchlussel) erkennen und verifizieren, wenn er den dazugehorigenoffentlichen Schlussel kennt.




Um das Protokoll verifizieren zu konnen, benotigen wir eine exakte,formale Beschreibung des Protokolls, die keine Mehrdeutigkeitenenthalt.

D.h., wir mussen mehr als bisher auf exakteProtokollbeschreibungen Wert legen.

Wir betrachten als Beschreibungsformalismus vor allem denangewandten π-Kalkul (es gibt jedoch auch andere geeigneteFormalismen).




Warum reichen bisherige Beschreibungsmechanismen nicht aus?

Eine Moglichkeit ist es, ein Protokoll als Folge ausgetauschterNachrichten zu modellieren:

Beispiele:

1 B → A: PB

2 A→ B: KSAPB

3 B → A: mK

Needham-Schroeder-Protokoll im Einfuhrungsteil Protokoll




Diese Notation ist noch zu unprazise. Insbesondere:

Sie sagt nichts daruber aus, was ein Teilnehmer berechnet,nachdem eine Nachricht empfangen wurde.

Wird uberpruft, ob alle Komponenten der Nachrichtkorrekt sind?Werden zuruckgeschickte Nonces mit fruher generiertenoder erhaltenen Nonces verglichen?Werden Zeitstempel uberpruft?Was macht der Teilnehmer, wenn die Nachricht nicht daskorrekte Format hat?

Es ist unklar, welche Moglichkeiten der Angreifer hat.

Konnen mehrere Protokollablaufe gleichzeitigdurchgefuhrt werden?Konnte ein (oder beide) Teilnehmer auch gleichzeitigeinen Protokollablauf mit dem Angreifer durchfuhren?




Bemerkung: das oben angegebene Protokoll der Form

1 B → A: PB

2 A→ B: KSAPB

3 B → A: mK

beschreibt folgendes Szenario:

Bob schickt an Alice seinen offentlichen Schlussel.

Alice schickt an Bob einen Sitzungsschlussel K , der von ihrsigniert ist und den sie mit Bob’s offentlichen Schlusselverschlusselt hat.

Bob verwendet den Sitzungsschlussel, um eine Nachricht anAlice zu verschlusseln.

Dieses Protokoll ist nicht korrekt: es gibt einen Angriff. Welchen?




Eve (E ) hat folgende Angriffsmoglichkeit(Man-in-the-Middle-Attack), falls Alice auch mit Evekommuniziert:

1 B → E : PB

2 E → A: PE

3 A→ E : KSAPE

4 E → B: KSAPB

5 B → A: mK

Die letzte Nachricht kann jedoch von Eve abgefangen undentschlusselt werden, denn Eve besitzt K .

Wir werden dieses Protokoll im Folgenden haufig als Beispieleinsetzen.




Verifikation kryptographischer Protokolle (Schema)

Modelliere das Protokoll im angewandten π-Kalkul. Damiterhalt man auch ein Angreifermodell und die Moglichkeit, dasmogliche Systemverhalten als Transitionssystem darzustellen.

Verwende dann eine der folgenden Analysetechniken:

Einschranken auf endlichen Zustandsraum undDurchsuchen des Zustandsraum ( Model-Checking)Horn-Formeln und ResolutionVerhaltensaquivalenzen




Dabei macht es einen Unterschied, welche Eigenschaft desProtokolls genau verifiziert werden soll. Wir werden hauptsachlichbetrachten:

Geheimhaltung: bestimmte Nachrichteninhalte bleibengegenuber dem Angreifer geheim.

(Beispielsweise verletzt das Beispielprotokoll weiter oben dieGeheimhaltung. Der Angreifer erfahrt m.)

Authentifizierung: der Angreifer ist nicht in der Lage, sich alsein anderer Teilnehmer auszugeben.



Angewandter π-Kalkul

Der angewandte π-Kalkul (applied π-calculus, von Abadi undFournet) ist ein sogenannter Prozesskalkul bzw. eineProzessalgebra.

Vorganger dieses Kalkuls sind CCS (Calculus of CommunicatingSystems) und der π-Kalkul, beide eingefuhrt von Robin Milner. Einanderer verwandter Kalkul ist der Spi-Kalkul (Spi calculus).

Prozesskalkule sind “Mini-Programmiersprachen”, in denenInteraktion von Prozessen sehr kompakt und auch sehr prazisebeschrieben werden kann.




Wir beginnen damit, die Syntax des angewandten π-Kalkulseinzufuhren:

Namen und Variable

Es gibt eine Menge von Namen, deren Elemente als Kanalnamen,Schlussel, Nonces, Nachrichteninhalte, etc. verwendet werden.

Außerdem gibt es eine Menge von Variablen.

Kanalnamen werden im Folgenden mit a, b, c, . . . bezeichnet,Schlussel mit K , Nonces mit n und Nachrichteninhalte mit m.Variablen werden im Allgemeinen mit x , y , z , x1, x2, . . . bezeichnet.




Funktionssymbole und Terme

Außerdem gibt es eine Menge von Funktionssymbolen. Aus denNamen, Variablen und Funktionssymbolen werden Terme gebildet.

Hinweis: dabei ist darauf zu achten, dass Funktionssymbole in derkorrekten Stelligkeit auf Elemente des korrekten Typs angewandtwerden. (Beispielsweise konnen bestimmte Funktionen nur aufNachrichten oder Schlussel angewandt werden.)

Beispiele fur Terme:

encrypt(m,K )

decrypt(encrypt(m, x), y)




Gleichungen

Gegeben ist eine Menge Σ von Gleichungen auf Termen(manchmal auch Theorie genannt), die das Verhalten derFunktionssymbole bzw. der dazugehorigen Funktionen beschreiben.

Fur zwei Terme M,N gilt Σ ` M = N (die Gleichheit M = N istaus den Gleichungen herleitbar), falls eine der folgendenBedingungen erfullt ist (jeweils fur geeignete Terme L,M ′,N ′):

M und N sind identisch (Reflexivitat),

die Gleichung M = N ist in Σ enthalten,

es gilt M = L[x/M ′], N = L[x/N ′] und Σ ` M ′ = N ′,

es gilt M = M ′[x/L], N = N ′[x/L] und Σ ` M ′ = N ′,

Σ ` N = M (Symmetrie) oder

Σ ` M = L und Σ ` L = N (Transitivitat).




Beispiele fur Terme und Gleichungen:

Symmetrische Verschlusselung

Funktionen sdecrypt und sencrypt, die als ersten Parametereine Nachricht und als zweiten Parameter einen Schlusselerhalten.

Definierende Gleichungen:

Σ = sdecrypt(sencrypt(x , y), y) = x

Es gilt daher beispielsweise:

Σ ` sdecrypt(sencrypt(m,K ),K ) = m

Σ 6` sdecrypt(sencrypt(m,K ),K ′) = m, falls K 6= K ′.

Σ ` sencrypt(sdecrypt(sencrypt(m,K ),K ),K ) =sencrypt(m,K )





Zusatzlich zu den Funktionen adecrypt und aencrypt gibt esnoch einstellige Funktionen sk, pk die aus einem Geheimniseinen privaten und offentlichen Schlussel ableiten.


Σ = adecrypt(aencrypt(x , pk(y)), sk(y)) = x




Signaturen

Zusatzlich zu den Funktionen pk, sk verwenden wir zweistelligeFunktionen sigcheck, sigget und sign und eine Konstante ok.


Σ = sigcheck(sign(x , sk(y)), pk(y)) = ok,

sigget(sign(x , sk(y)), pk(y)) = x




Logischer Operator xor

Wir verwenden eine zweistellige Funktion xor, definiert auf denWahrheitswerten 0, 1.


Σ = xor(x , y) = xor(y , x),

xor(xor(x , y), z) = xor(x , xor(y , z)),

xor(0, x) = x ,

xor(x , x) = 0




Paare

Wir benutzen eine zweistellige Funktion pair und einstelligeFunktionen fst, snd, die nur auf Paaren definiert sind.


Σ = fst(pair(x , y)) = x , snd(pair(x , y)) = y

Im Folgenden werden wir auch die Notation (x , y) statt pair(x , y)verwenden.




Syntax des angewandten π-Kalkuls

Ein Prozess ist entweder:

der inaktive Prozess 0,

eine parallele Komposition P | Q,

eine Replikation !P

eine Restriktion (νu)P,

eine Bedingung if M = N then P else Q,

ein Prozess mit Eingabe-Prafix c(x).P oder

ein Prozess mit Ausgabe-Prafix c〈M〉.P.

Dabei sind P,Q Prozesse, u ein Name, c ein Kanalname, M,NTerme und x eine Variable.




Bemerkungen:

Die syntaktischen Konstrukte sind eng verwandt mit denentsprechende Konstrukten in CCS. Insbesondere entspricht(νn)P dem Prozess P\n in CCS.

Der Name u ist in (νu)P gebunden. Damit erzeugt man neueSchlussel und Nonces, die der Umgebung nicht bekannt sindEbenso ist die Variable x in c(x).P gebunden. (DiesesKonstrukt ist als Restriktion oder auch Verschattungbekannt.) Gebundene Namen und Variablen konnen(gebunden) umbenannt werden.

Die Replikation !P steht fur beliebig viele Kopien von P, dieparallel ablaufen.

Ausgabe- bzw. Eingabe-Prafix beschreiben das Senden bzw.Empfangen einer Nachricht auf dem Kanal c , wobei sich derProzess anschließend wie P verhalt.




Evaluationskontext

Ein Evaluationskontext C [ ] ist ein spezieller Prozess, in dem derPlatzhalter , der fur einen Prozess steht, genau einmalvorkommen. Dieser Platzhalter darf nicht unter einer Replikation,unter einer Bedingung oder unter einem Prafix vorkommen.Mit C [P] bezeichnen wir den Prozess, der dadurch entsteht, dassder Platzhalter in C [ ] durch den Prozess P ersetzt wird.

Beispiele:

C [ ] = (νm)( | a(x).b〈m〉.0) ist ein Evaluationskontext.

! und a(x). sind keine gultigen Evaluationskontexte.




Semantik des angewandten π-Kalkuls (Strukturelle Kongruenz)

Strukturelle Kongruenz (≡) ist die kleinste Aquivalenzrelation aufProzessen, die mit Hilfe der folgenden Regeln hergeleitet werdenkann:

P ≡ P | 0 P | (Q | R) ≡ (P | Q) | R P | Q ≡ Q | P

!P ≡ P |!P (νu)0 ≡ 0 (νu)(νv)P ≡ (νv)(νu)P

P | (νu)Q ≡ (νu)(P | Q) falls u nicht frei in P vorkommt

P[x/M] ≡ P[x/N] falls Σ ` M = N

C [P] ≡ C [Q] falls P ≡ Q und C [ ] ein Evaluationskontext ist

Prozesse, die durch gebundene Umbenennung ineinander uberfuhrtwerden konnen, gelten ebenfalls als strukturell kongruent.




Bemerkungen zur strukturellen Kongruenz:

P[x/M] ist der Prozess P, in dem jedes freie Vorkommen derVariablen x durch den Term M ersetzt wurde. Dabei istfolgendes zu beachten: freie Namen oder Variablen, die in Mvorkommen, durfen durch diese Ersetzung nicht gebundenwerden. Falls dies passieren wurde, muss umbenannt werden.Beispiel: ((νn)a〈x〉.b〈n〉.0)[x/n] = (νn′)a〈n〉.b〈n′〉.0Die vorletzte Regel beschreibt, dass ein Term M durch einenanderen Term N ersetzt werden kann, falls die Gleichheit vonM und N unter Σ nachgewiesen werden kann.

Die letzte Regel garantiert die Abgeschlossenheit derstrukturellen Kongruenz unter Evaluationskontexten.




Semantik des angewandten π-Kalkuls (Reduktionsregeln)

Folgende Regeln beschreiben die Reduktionsrelation → aufProzessen:

c〈M〉.P | c(x).Q → P | Q[x/M]

if M = N then P else Q → P falls Σ ` M = N

if M = N then P else Q → Qfalls M,N variablenfreie Terme sind und Σ 6` M = N

C [P]→ C [Q] falls P → Q und C [ ] ein Evaluationskontext ist

P → Q falls P ′ → Q ′, P ≡ P ′ und Q ′ ≡ Q




Bemerkungen:

Die erste Regel beschreibt das Senden einer Nachricht M ubereinen Kanal c .

Falls die Gleichheit von M und N nachgewiesen werden kann,dann wird im Fall einer Bedingung der Then-Fall betreten.

Wenn die Gleicheit nicht nachgewiesen werden kann, danndarf der Else-Fall nur dann betreten werden, wenn die TermeM,N variablenfrei sind. D.h., es gibt keine Moglichkeit mehr,die Terme durch Substitutionen und Anwendungen derGleichungen in die gleiche Form zu bringen. Terme, die durchdie Theorie nicht unifiziert werden konnen, gelten alsverschieden.

Die letzten beiden Regeln beschreiben, dass dieReduktionsrelation unter Evaluationskontexten undstruktureller Kongruenz abgeschlossen ist.




Transitionssystem

Das Transitionssystem eines Prozesses P besteht aus:

Zustandsmenge: Aquivalenzklassen von Prozessen, die von Paus erreicht werden konnen. D.h., jede Aquivalenzklasse [Q]≡mit P →∗ Q ist ein Zustand. (Dabei ist ≡ die strukturelleKongruenz.)

Transitionen: Es gibt einen Ubergang von [Q1]≡ nach [Q2]≡genau dann, wenn Q1 → Q2.

Um die Anzahl der Zustande moglichst klein zu halte, sollte – wieoben beschrieben – die Menge der von P erreichbaren Prozessedurch die strukturelle Kongruenz faktorisiert werden.




Wir betrachten ein erstes kleines Beispielprotokoll(Nonce-Challenge):

1 A→ B: nK2 B → A: n − 1K

Dabei ist n ein Nonce und K ist ein Sitzungsschlussel von Bobbzw. Alice.

Um dieses Protokoll im angewandten π-Kalkul zu modellieren,verwenden wir die Theorie symmetrische Verschlusselungzusammen mit einer Dekrementierungsfunktion dec.




Die entsprechenden Prozesse sehen wie folgt aus:

Alice:

A = (νn)(c〈sencrypt(n,K )〉.c(x).

if sdecrypt(x ,K ) = dec(n)

then A′

else 0)

Bob:

B = c(y).

c〈sencrypt(dec(sdecrypt(y ,K )),K )〉.B ′




Bemerkungen:

Dabei ist n der zu verschickende Nonce, der zunachst in Agebunden ist und keinem anderen Teilnehmer bekannt ist.

Mit c bezeichnen wir den (offenen) Kanal, uber den derNachrichtenaustausch stattfindet.

A′ bzw. B ′ sind die Fortsetzungen von Alice und Bob.Dadurch wird das Verhalten der beiden Teilnehmer nachAustausch der beiden Nachrichten beschrieben. Wir nehmenan, dass x nicht frei in A′ und y nicht frei in B ′ vorkommt.

Das Verhalten von Alice und Bob zusammen wird durchS = (νK )(A | B) beschrieben. Durch die Restriktion kannman sicherstellen, dass das Geheimnis K nach außen hinverschattet ist.

Falls der Nonce nicht korrekt zuruckgeschickt wird, so brichtA das Protokoll ab und wird zum Null-Prozess.




Reduktionsfolge bei korrektem Verhalten (ohne Eindringling):

A | B ≡ (νn)(c〈sencrypt(n,K )〉.c(x).


then A′

else 0 | B)

Diese Aquivalenz gilt aufgrund der Regeln der strukturellenKongruenz, da n nicht frei in B vorkommt. (Falls dies der Fallware, so musste n zunachst umbenannt werden.) Diesen Effektbezeichnet man auch als Erweiterung des Bindungsbereichs (scopeextrusion).




Daher gilt:

A | B → (νn)(c(x).


then A′

else 0 |c〈sencrypt(dec(sdecrypt(sencrypt(n,K ),K )),K )〉.B ′)




Aufgrund der Gleichungen konnen wir folgenden Termvereinfachen:

Σ ` sencrypt(dec(sdecrypt(sencrypt(n,K ),K )),K )

= sencrypt(dec(n),K )




Daraus ergibt sich folgende Reduktion:

A | B →→ (νn)(if sdecrypt(sencrypt(dec(n),K ),K )

= dec(n)

then A′

else 0 | B ′)




Der so entstandene Prozess ist wegen

Σ ` sdecrypt(sencrypt(dec(n),K ),K ) = dec(n)

aquivalent zu

(νn)(if dec(n) = dec(n)

then A′

else 0 | B ′)

Und damit ergibt sich:

A | B →→→ (νn)(A′ | B ′)




Bemerkung:

Im angewandten π-Kalkul ist es auch moglich, einen vollkommenprivaten Kanal zu etablieren:

(νb)(b〈m〉.P | b(x).Q)

Aufgrund der Restriktion (νb) kann der Kanal b vom Angreifernicht abgehort werden, es sei denn, einer der beiden Teilnehmerverschickt b explizit uber einen anderen Kanal. Diese Mobilitat vonKanalnamen spielt im π-Kalkul eine große Rolle, ist fur uns hieraber nicht so wichtig.

Im Allgemeinen werden wir Kanalnamen nicht restringieren, da wirnicht annehmen konnen, dass es wirklich sichere Kanale gibt.



Modellierung des Angreifers

Mit Hilfe einer geeigneten Theorie kann man auchEinwegfunktionen modellieren: wir verwenden ein einstelligesFunktionssymbol f (ohne Gleichungen!). Da es keinFunktionssymbol fur die Umkehrfunktion gibt, kann auch niemandUrbilder ermitteln.

Beispielprozess:A = c〈f(g)〉.0

Dabei ist g ein “Geheimnis”.

Kein Angreifer, der f(g) als Nachricht empfangt, kann den Wert germitteln.

Hashfunktionen konnen ahnlich modelliert werden.




Wir betrachten nun das vorherige Beispielprotokoll:

1 B → A: PB

2 A→ B: KSAPB

3 B → A: mK

Um dieses Protokoll im angewandten π-Kalkul zu modellieren,verwenden wir die Theorien fur symmetrische und asymmetrischeVerschlusselung zusammen mit der Theorie fur Signaturen.




Die entsprechenden Prozesse sehen wie folgt aus:

Alice:

A = (νK )(νKA)(

c(p).

c〈aencrypt(sign(K , sk(KA)), p)〉.c(x).

A′[x ′/sdecrypt(x ,K )]

| !a〈pk(KA)〉.0)Dabei gibt Alice ihren offentlichen Schlussel pk(KA) uber denoffenen Kanal a bekannt, behalt aber sk(KA) als Geheimnis.




Bob:

B = (νm)(νKB)(

c〈pk(KB)〉.c(y).a(u).

(if sigcheck(y ′, u) = ok

then c〈sencrypt(m, sigget(y ′, u))〉.B ′

else 0)[y ′/adecrypt(y , sk(KB))]

| !b〈pk(KB)〉.0)Auch hier gibt Bob seinen offentlichen Schlussel bekannt.Außerdem empfangt er den offentlichen Schlussel von Alice, den erzum Uberprufen der Signatur benotigt.





A′ bzw. B ′ sind auch hier die Fortsetzungen von Alice undBob. A′ enthalt x ′ als freie Variable, wobei x ′ als Platzhalterfur die zu empfangene (entschlusselte) Nachricht m steht. B ′

enthalt analog y ′ als freie Variable.

Das Verhalten von Alice und Bob gemeinsam wird durchSys = A | B beschrieben.




Wie sehen Angreifer im Kalkul aus?

Ein Angreifer E (E steht fur Eve) kann ein beliebiger Prozess desKalkuls sein. Dieser wird mit dem eigentlichen System Sys (i.a.bestehend aus Alice und Bob) parallel komponiert: Sys | E .

Damit konnen wir nun auch beschreiben, was es bedeutet, dasseine Nachricht m geheimgehalten wird:

Geheimhaltung

Ein System Sys halt eine Nachricht m geheim, wenn es keinenAngreifer E gibt mit einer Reduktionsfolge Sys | E →∗ P, so dassin P m als (unverschlusselter) Nachrichteninhalt auf einemnicht-verschatteten Kanal verschickt wird.

Wenn der Angreifer in den Besitz von m kommt, so kann er dieseNachricht immer auf einem offenen Kanal verschicken.




Das letzte Beispielprotokoll halt die Nachricht m nicht geheim. Esgibt einen entsprechenden Angreifer:

E = (νKE )(c(pB).

c〈pk(KE )〉.c(z).(c〈aencrypt(v , pB)〉.c(u).a(pA).

s〈sdecrypt(u, sigget(v , pA))〉.0))[v/adecrypt(z , sk(KE ))])




Bemerkungen:

Die Schritte von Eve der Reihe nach:

1 E empfangt den offentlichen Schlussel von Bob.

2 E schickt ihren eigenen offentlichen Schlussel an Alice.

3 E empfangt den signierten und verschlusseltenSitzungsschlussel K von Alice.

4 E verschlusselt den signierten Sitzungsschlussel unter demoffentlichen Schlussel von Bob und schickt ihn an Bob.

5 E empfangt die mit dem Sitzungsschlussel verschlusselteNachricht m von Bob.

6 E entschlusselt diese Nachricht (denn sie kennt K !) und gibtdie Nachricht auf dem offenen Kanal s bekannt.




Es gibt einen Ablauf von Sys | E , bei dem zuletzt m auf demKanal s verschickt wird. D.h., die Geheimhaltung von m ist nichtgewahrleistet. Es gilt:

Sys | E →∗ (νm)(s〈m〉.0 | P)

fur einen geeigneten Prozess P.

Es gibt naturlich auch Ablaufe, bei denen das Geheimnis nichtpreisgegeben wird, aber mindestens ein Ablauf verletzt dieGeheimhaltung.




Wir modellieren nun das Needham-Schroeder-Protokoll (sieheEinfuhrungsteil Protokoll ).

Needham-Schroeder-Protokoll (fehlerhaft)

1 A→ S : A,B, nA2 S → A: nA,KAB , KAB ,AKBS

KAS

3 A→ B: KAB ,AKBS

4 B → A: nBKAB

5 A→ B: nB − 1KAB




Als Theorien verwenden wir die Theorie fur die symmetrischeVerschlusselung, sowie eine zweistellige Funktion check mit

check(sencrypt(x , y), y) = ok,

die feststellt, ob eine Nachricht, mit einem bestimmten Schlusselverschlusselt wurde. (Ansonsten kann Alice nicht uberprufen, obder Nonce nB mit dem korrekten Schlussel verschlusselt wurde.)

Außerdem verwenden wir die Dekrementierungsfunktion dec, dieTheorie fur Paare und – um dreistellige Tupel zu erhalten – einedreistellige Funktion triple (analog zu pair) mit den Projektionenfst, snd und thrd.




Alice:

A = (νnA)(

cS〈triple(A,B, nA)〉.cS(x).(

if first(u) = nA

then cAB〈thrd(u)〉.cAB(y).

if check(y , snd(u)) = ok

then cAB〈sencrypt(dec(sdecrypt(y , snd(u))),

snd(u))〉.0else 0

else 0)[u/sdecrypt(x ,KAS)]

)Barbara Konig “Form. Asp. der Software-Sicherheit und Kryptographie” 343



Bob:

B = (νnB)(

cAB(x).(cAB〈sencrypt(nB , fst(u))〉.cAB(y).

if sdecrypt(y , fst(u)) = dec(nB)

then 0

else fail〈〉.0)[u/sdecrypt(x ,KBS)])

Die Nachricht von Bob auf dem Kanal fail signalisiert, dass derProtokollablauf nicht erfolgreich war.




Server:

S = (νK )(

cS(x).

if fst(x) = A

then if snd(x) = B

then cS〈sencrypt(triple(thrd(x),K , sencrypt(pair(K ,A),

KBS)),KAS)〉.0else . . .)




Es gibt noch weitere Fallunterscheidungen, wobei alle Paare vonmoglichen Teilnehmern (einschließlich Eve) abgefragt werdenmussen.

Diese Fallunterscheidungen konnte man dadurch vermeiden, indemman eine einstellige Funktion key einfuhrt, die zu dem Bezeichnereines Teilnehmers den Schlussel zuruckgibt, den dieser Teilnehmermit dem Server teilt. Diese Funktion darf jedoch dem Angreifernicht zuganglich sein!




Das gesamte System besteht aus der parallelen Komposition vonA, B und S , zusammen mit der Restriktion der entsprechendenSchlussel:

Sys = (νKAS)(νKBS)(A | B | S)

Statt S kann auch !S verwendet werden, dann wird der Serverrepliziert und steht immer wieder fur Anfragen zur Verfugung.




Authentifizierung wird typischerweise folgendermaßen definiert:

Authentifizierung

Wenn Alice der Meinung ist, dass sie einen Protokollablauf mitBob durchfuhrt, dann hat Bob zuvor beschlossen, dass er einenProtokollablauf mit Alice durchfuhrt. (Oder umgekehrt.)

Um diese Eigenschaft formulieren zu konnen, fugen wirentsprechende Nachrichten ein, die Alice bzw. Bob an ihre Umweltschicken, um ihre Uberzeugungen bekanntzugeben. Wirmodifizieren also die Prozess-Beschreibungen leicht.




Alice (modifiziert):

A = (νnA)(

cS〈triple(A,B, nA)〉.cS(x).(

if first(u) = nA

then cAB〈thrd(u)〉.cAB(y).

cAB〈sencrypt(dec(sdecrypt(x , snd(u))), snd(u))〉.a〈(A,B)〉.0

else 0)[u/sdecrypt(x ,KAS))])




Bob (modifiziert):

B = (νnB)(

cAB(x).(b〈(B, snd(u))〉〉.0 |cAB〈sencrypt(nB , fst(u))〉.cAB(y).

if sdecrypt(y , fst(u)) = dec(nA)

then 0

else fail .0)[u/sdecrypt(x ,KBS)]

)Bemerkung: Um weitere Reduktionen nicht zu blockieren, sendetBob asynchron auf dem Kanal b, d.h., die Nachricht wird parallelzum weiteren Ablauf verschickt.




In diesem Fall mussen wir fur die Authentifizierung fordern:

Fur jeden Angreifer E gilt: in jedem Ablauf von Sys | E , in demAlice bekanntgibt, dass sie mit Bob spricht, d.h., es wird eineNachricht a〈(A,B)〉 geschickt, erzeugt Bob zuvor eine Nachrichtb〈(B,A)〉. D.h., er bezeugt, einen Protokollablauf mit Alicebegonnen zu haben.

Ahnlich musste man beschreiben, dass Alice sich gegenuber Bobkorrekt authentifiziert hat.




Hier gibt es einen Angreifer ( Angriff ) E , der das Protokollunterlaufen kann:

Angreifer Eve:

E = cS(x).

cS〈triple(A,E , thrd(x))〉.cAB(y).(cAB〈sencrypt(nB , fst(u))〉.cAB(z).0))

[u/sdecrypt(y ,KES)]

Bemerkung: Eve halt nB nicht geheim.




Es gibt Ablaufe von Sys | E , in denen Alice die Nachricht a〈(A,B)〉schickt, ohne dass Bob zuvor seine Nachricht geschickt hat.

In diesen Ablaufen ist Bob uberhaupt nicht beteiligt, eskommunizieren nur Alice, der Server und Eve.




Wir haben nun eine Methode gesehen, mit der man Angriffe aufein Protokoll beschreiben kann: man spezifiziert den Angreifer Eals Prozess.

Aber wie kann man zeigen, dass es keinen solchen Angreifer gibt?Man musste ja unendlich viele Angreifer ausprobieren!

Wir betrachten nun einen universalen Angreifer, der alleNachrichten abfangen kann, daraus weitere Nachrichten gewinnenkann, die er nicht-deterministisch abschickt.

Es gibt einen herkommlichen Angreifer, genau dann, wenn deruniversale Angreifer eine Angriffsmoglichkeit findet.




Wir fuhren nun einen neue Art von Prozess ein, indem wir dieSyntax des Kalkuls erweitern:

Angreifer

Sei nun auch E (M), wobei M eine Menge von Termen ist, einProzess.

Dabei ist M das Wissen, das der Angreifer hat, d.h., dieKanalnamen, Nonces und Schlussel, die er zu Beginn besitzt,zusammen mit den weiteren Nachrichten, die er empfangen hat.

Ein variablenfreier Term M ist aus M herleitbar (in ZeichenM ` M), wenn

es gibt Terme Mi ∈M, i ∈ 1, . . . , n,es gibt einen Term N, der keine Namen und die freienVariablen x1, . . . , xn enthalt, undΣ ` M = N[x1/M1, . . . , xn/Mn]




Strukturelle Kongruenz und Reduktionsregeln fur den Angreifer

(νn)P | E (M) ≡ (νn)(P | E (M))falls n in keinem der Terme von M vorkommt

c〈M〉.P | E (M)→ P | E (M∪ M) falls M ` c

E (M) | c(x).Q → E (M) | Q[x/M]falls M ` c und M ` M

Der Angreifer muss den entsprechenden Kanal c kennen, um aufihm Nachrichten empfangen oder versenden zu konnen.

D.h. im letzten Fall durfen nur diejenigen Nachrichten verschicktwerden, die aus dem bisherigen Wissen des Angreifers abgeleitetwerden konnen.




Der Angreifer wird mit einem bestimmten Vorwissen ausgestattet.D.h., er kennt zu Beginn des Protokollablaufs bestimmte Kanale,Schlussel, Nonces, die Elemente der Menge M sind.

Durch die Bindungsbereiche ist aber auf jeden Fall garantiert, dassder Angreifer keine “geheimen” Namen kennt, die anderswoverschattet sind.

Beispiel: in dem System ((νu)P) | E (u) ist der Name u, den derAngreifer kennt, nicht identisch mit dem Namen, der in Pgebunden ist.




Beispiel: im Fall des Needham-Schroeder-Protokolls gibt es einenAblauf von

Sys | E (cS , cAB ,A,E , nB ,KES),

in dem Alice eine Nachricht auf Kanal a erzeugt, ohne dass Bobzuvor seine Nachricht auf Kanal b erzeugt hat.



Durchsuchen des Zustandsraums – Model-Checking

Idee:

Beschreibe das gegebene Protokoll mit Hilfe des ProzessesSys.

Lege das Vorwissen M der Angreifers fest.

Uberprufe durch Durchsuchen des Zustandsraums, dassSys | E (M) nicht in einen Zustand kommen kann oder einenAblauf erzeugen kann, in dem die Geheimhaltungs- oderAuthentifizierungseigenschaften verletzt sind.

Problem:

Es ist nicht klar, dass der Zustandsraum des Transitionssystemsvon Sys | E (M) endlich ist. Um dies zu erreichen, muss manbestimmte Einschrankungen machen.




Einschrankungen:

Die Protokollbeschreibung Sys erlaubt nur endliches Verhalten(nicht beliebig viele parallele Sitzungen, keine Replikation).

Es gibt entweder nur endlich viele Aquivalenzklassen vonTermen oder die Große der vom Angreifer verschickten Termewird beschrankt.

Die Theorie muss entscheidbar sein, d.h., fur zwei gegebeneTerme M,N muss entschieden werden konnen ob Σ ` M = Ngilt oder nicht gilt.




Bemerkungen:

Es ist moglich, das Wissen des Angreifers on-the-fly zugenerieren. D.h., immer wenn ein Angreifer einen frischenNonce oder Schlussel braucht, so kann er diesen raten.

Bei Authentifizierung ist es oft wunschenswert, nicht nur zuuberprufen, dass ein bestimmtes Ereignis vor einem anderenEreignis stattgefunden hat, sondern dass – falls es mehrereProtokollablaufe gibt – die entsprechendenAuthentifizierungsereignisse in Eins-zu-Eins-Beziehung stehen.



Horn-Formeln und Resolution

Wir betrachten nun einen weiteren Ansatz (entwickelt von BrunoBlanchet), der

auch fur unendliche Zustandsraume und beliebig viele paralleleSitzungen funktioniert (Replikation ist erlaubt!).

uberapproximiert: es gibt moglicherweise korrekte Protokolle,die nicht als solche erkannt werden.

Dazu werden die Moglichkeiten des Angreifers und derProtokollablauf in Pradikatenlogik formalisiert (genauer: inHorn-Klauseln) und es wird versucht, mit Hilfe von Resolution zuzeigen, ob der Angreifer sein Ziel erreichen kann.

Dieser Ansatz ist in dem Tool ProVerif (proverif.inria.fr)implementiert.




Das Problem zu entscheiden, ob es auf ein gegebenes Protokolleinen Angriff gibt ist unentscheidbar (so wie die meistenVerifikationsprobbleme). Deshalb wird die Menge der erreichbarenSystemzustande uberapproximiert.

Erreichbare Zustande

Uberapproximation dererreichbaren Zustande

Menge aller Zustande

Menge derFehlerzustande




Falls der Schnitt der Uberapproximation der erreichbarenZustande mit der Menge der Fehlerzustande leer ist, ist dasSystem korrekt.

Wenn der Schnitt nicht-leer ist, dann kann allerdings keineAussage getroffen werden. In diesem Fall kann mannormalerweise nicht zeigen, dass in dem Schnitt keinerreichbarer Zustand liegt.



Wiederholung: Pradikatenlogik und Resolution

Wir wiederholen zunachst Pradikatenlogik und Resolution.

Gegeben seien Mengen von Variablen, Funktionssymbolen undPradikatsymbolen. Terme werden – wie im angewandten π-Kalkul– aus Variablen und Funktionssymbolen gebildet.




Syntax der Pradikatenlogik

1 Falls P ein Pradikatsymbol der Stelligkeit k ist, und fallst1, . . . , tk Terme sind, dann ist P(t1, . . . , tk) eine Formel.

2 Fur jede Formel F ist auch ¬F eine Formel.

3 Fur alle Formeln F und G sind auch (F ∧ G ) und (F ∨ G )Formeln.

4 Falls x eine Variable ist und F eine Formel, so sind auch ∃xFund ∀xF Formeln. Das Symbol ∃ wird Existenzquantor und ∀Allquantor genannt.

Eine Formel der Form P(t1, . . . , tk) oder ¬P(t1, . . . , tk) heißtLiteral.




Strukturen, Modelle

Gegeben sei eine Formel F . Eine zu F passende Struktur A bestehtauf einer Menge UA (dem Universum) und einer Interpretation, die

jeder in F vorkommenden freien Variable x ein Element xA

des Universums zuordnet.

jedem in F vorkommenden k-stelligen Funktionssymbol f eineFunktion f A : Uk

A → UA zuordnet.

jedem in F vorkommenden k-stelligen Pradikatsymbol P eineRelation PA ⊆ Uk

A zuordnet.

Man kann F unter A (auf offensichtliche Weise) auswerten underhalt einen Wahrheitswert A(F ) ∈ 0, 1. Falls A(F ) = 1, dannheißt A Modell von F .




Beispiel:

F = ∀x∃yP(x , f (y))

A mit UA = N0, PA = (m, n) | m < n und

f A(n) =

n − 1 falls n > 00 sonst

ist ein Modell fur F .

B mit UB = N0, PB = (m, n) | m > n und f B(n) = n istkein Modell fur F .




Erfullbarkeit, Unerfullbarkeit

Eine Formel F ist erfullbar, wenn sie ein Modell hat, ansonsten istsie unerfullbar.

Beispiele:

Die Formel F = ∀x∃yP(x , f (y)) ist erfullbar.

Die Formel G = ∀xP(x) ∧ ∃y¬P(y) ist unerfullbar.




Klauselform, Hornformel

Eine Formel F ist in Klauselform, wenn sie folgende Form hat:

F = ∀x1 . . . ∀xnF ∗,

wobei F ∗ keine Quantoren enthalt und sich in konjunktiverNormalform befindet.Sie ist eine Hornformel, wenn sich zusatzlich in jeder Klauselhochstens ein positives Literal befindet.

Beispiele:

F = ∀x∀y((¬P(x) ∨ Q(x , y) ∨ R(x)) ∧ (¬P(y) ∨ R(f (y)))

)ist in Klauselform, ist aber keine Hornformel.

F = ∀x∀y((¬P(x) ∨ Q(x , y) ∨ ¬R(x)) ∧ (¬P(y) ∨ R(f (y)))

)ist eine Hornformel.




Bemerkungen:

Zu jeder pradikatenlogischen Formel F kann man einfach eineerfullbarkeitsaquivalente Formel F ′ in Klauselformkonstruieren. (Die Umwandlung in eineerfullbarkeitsaquivalente Hornformel ist nicht so einfachmoglich.)

Es gibt drei verschiedene Typen von Hornklauseln:

Ein positives Pradikat: P0 ≡ 1→ P0 (Tatsachenklausel)Nur negative Pradikate:¬P1 ∨ · · · ∨ ¬Pn ≡ P1 ∧ · · · ∧ Pn → 0 (Zielklausel)Negative und ein positives Pradikat:¬P1 ∨ · · · ∨ ¬Pn ∨ P0 ≡ P1 ∧ · · · ∧ Pn → P0

(Prozedurklauseln)

wobei jedes Pi von der Form P(t1, . . . , tn) ist.




Substitution, Unifikation

Sei sub = [x1/t1, . . . , xn/tn] eine Substitution und seien P1, . . . ,Pn

Pradikate der Form P(t ′1, . . . , t′n). Die Substitution sub heißt

Unifikator der Pradikate, falls

P1sub = P2sub = · · · = Pnsub.

Sie heißt allgemeinster Unifikator, wenn es fur jede anderenUnifikator sub′ eine Substitution s gibt mit sub s = sub′.




Bemerkungen:

Substitutionen werden – anders als andere Funktionen – hinterihr Argument geschrieben.

Daher wird die Verknupfung von Substitutionenfolgendermaßen notiert: fur zwei Substitutionen s1, s2 ist s1s2

die Substitution, bei der zuerst s1 und dann s2 ausgefuhrtwird.




Resolvent

Gegeben seien zwei Klauseln K1 und K2. Wir nehmen an, dass eskeine Variable gibt, die in beiden Klauseln vorkommt. (Ansonstenkann man vorher umbenennen.)Seien P1, . . . ,Pn Pradikate aus K1 und ¬P ′1, . . . ,¬P ′m negiertePradikate aus K2, so dass P1, . . . ,Pn,P

′1, . . . ,P

′m unifizierbar ist.

Sei sub der allgemeinste Unifikator.Wir erhalten K ′1 und K ′2, indem wir die oben angegebenenPradikate aus K1 und K2 entfernen. Dann ist

R = (K ′1 ∨ K ′2)sub

ein Resolvent der Klauseln K1, K2.




Beispiel: zu resolvierende Literale sind unterstrichen.

P(x) ∨ P(f (y)) ∨ Q(x , y)

sub = [x/f (g(z)), y/g(z)]))

¬P(f (g(z)))

ww

Q(f (g(z)), g(z))

Oft benutzt man auch die Mengenschreibweise:

P(x),P(f (y)),Q(x , y)

sub = [x/f (g(z)), y/g(z)]

¬P(f (g(z)))

Q(f (g(z)), g(z))




Resolution

Fur eine Menge M von Klauseln bezeichnen wir mit Res(M) dieMenge aller Resolventen, die man aus den Klauseln von Mgewinnen kann, vereinigt mit M. Durch iterierteResolventenbildung erhalt man:

Res0(M) = M

Resn+1(M) = Res(Resn(M)) fur n ≥ 0

Res∗(M) =⋃n≥0

Resn(M).

Sei F = ∀x1 . . . ∀xnF ∗ eine Formel in Klauselform. Wir schreibenRes∗(F ∗) fur Res∗(K | K ist Klausel von F ∗).

Res∗(F ∗) kann moglicherweise eine unendliche Menge sein.




Resolutionssatz

Gegeben sei eine Formel F = ∀x1 . . . ∀xnF ∗ in Klauselform. DieFormel F ist unerfullbar, genau dann, wenn die leere Klausel(dargestellt durch ) in Res∗(F ∗) enthalten ist.

Beispiel: aus

∀x∀y(

(P(f (x)) ∨ Q(x)) ∧ ¬P(f (g(y))) ∧ ¬Q(g(a))

)kann man durch Resolution die leere Klausel herleiten.




Folgende Form der Resolution funktioniert speziell furHornklauseln:

Definition (SLD-Resolution)

Eine SLD-Resolutionsherleitungder leeren Klausel hat die rechtsabgebildete Form, wobei G eineZielklausel ist, G1,G2, . . . nur ausnegativen Literalen bestehen undK1, . . . ,Kn Tatsachen- oderProzedurklauseln sind.

G K1

G1 K2

G2

... Kn

Die Abkurzung SLD steht fur “linear resolution with selectionfunction for definite clauses”




Satz (Vollstandigkeit der SLD-Resolution)

Sei M eine unerfullbare Klauselmenge, bestehend ausHornklauseln, mit nur einer Zielklausel G . Dann gibt es fur F eineSLD-Resolutionsherleitung der leeren Klausel, die mit G beginnt.




Wir betrachten noch eine andere Form der Resolution, dievollstandig fur Horn-Klauseln ist:

Unare Resolution

Eine Menge M von Hornklauseln mit einer Zielklausel G . DieMenge M ist unerfullbar, genau dann, wenn es eineResolutionsableitung der leeren Klausel gibt, die folgendeBedingungen erfullt:

Bis auf die letzten Resolutionsschritte wird immer eineTatsachenklausel mit einer Prozedurklausel unifiziert. Dadurchentsteht entweder eine Tatsachen- oder eine Prozedurklausel.

In den letzten Schritten werden dann Tatsachenklauseln mitder Zielklausel G resolviert, um zu erhalten.

Weil eine der beiden Klauseln immer nur ein Element enthalt, wirddiese Resolution als unare Resolution oder unit resolutionbezeichnet.




Jetzt wieder zuruck zur Verifikation von kryptographischenProtokollen . . .

Idee: modelliere das Protokoll durch eine Menge von Hornklauselnund zeige, dass ein Resolutionsbeweis mit einer gegebenenZielklausel – die beispielsweise ausdruckt, dass der Angreifer in denBesitz des Geheimnisses kommen kann – nicht moglich ist.

Um ausreichende Effizienz zu erreichen, betrachten wir eineEinschrankung des angewandten π-Kalkuls: insbesondere werdenFunktionssymbole nach Konstruktoren und Destruktorenunterschieden.




Konstruktoren und Destruktoren

Wir unterteilen die Menge der Funktionssymbole in Konstruktorenund Destruktoren.Außerdem wird das Format der Gleichungen in Σ folgendermaßeneingeschrankt: alle Gleichungen sind von der Form

g(M1, . . . ,Mn) = M,

wobei M1, . . . ,Mn,M nur aus Variablen, Namen undKonstruktoren aufgebaut sind (wir bezeichnen solche Terme alsKonstruktorterme) und g ein Destruktor ist.




Die meisten der von uns betrachteten Theorien erlauben dieseKlassifizierung.

Beispiel:

Symmetrische Verschlusselung

Funktionen sdecrypt und sencrypt

Gleichungen:

Σ = sdecrypt(sencrypt(x , y), y) = x

Hier ist sdecrpyt ein Destruktor und sencrypt ein Konstruktor.




Außerdem wird die Semantik des Kalkuls modifiziert, insbesonderedie Reduktionsregel fur das Versenden von Nachrichten und dieReduktionsregeln fur If-Then-Else:

c〈M〉.P | c(x).Q → P | Q[x/M]

if M = N then P else Q → P falls Σ ` M = N

if M = N then P else Q → Qfalls M,N variablenfreie Terme sind und Σ 6` M = N

wobei M und N in allen Fallen Konstruktorterme sind




Bemerkungen: durch diese Modifikation entsteht ein Kalkul mitanderem Reduktionsverhalten. Insbesondere kann Senden undIf-Then-Else blockierend sein.

Beispiele:

Der Prozess P = c〈sdecrypt(m,K )〉.0 verschickt seineNachricht nie, da es sich bei sdecrypt(m) nicht um einenKonstruktorterm handelt.

Der Prozess Q = c(x).c〈sdecrypt(x ,K )〉.0 verschickt seineNachricht dann, wenn er auf c zuvor eine Nachricht empfangtund fur x einsetzt, die dazu fuhrt, dass sdecrypt(x ,K ) zueinem Konstruktorterm vereinfacht werden kann. Dies istbeispielsweise bei einer Nachricht der Form sencrypt(m,K )der Fall.




Bemerkungen:

Dieses blockierende Verhalten kann auch fur die Modellierung Sinnmachen.

Insbesondere kann damit ausgedruckt werden, dass ein Prozessnicht weiterarbeitet, wenn er eine empfangene Nachricht nichtentschlusseln kann.




Wir betrachten das kleine Beispielprotokoll in vereinfachter Form.(Wir lassen das Signieren des Sitzungsschlussels K weg.)

1 B → A: PB

2 A→ B: KPB

3 B → A: mK




Im angewandten π-Kalkul:

Alice: A = (νK )(c(p).

c〈aencrypt(K , p)〉.c(x).0

)Bob: B = (νm)(νKB)

(c〈pk(KB)〉.c(y).

c〈sencrypt(m, adecrypt(y , sk(KB)))〉.0)

Alle fur den Angriff nicht notwendigen Teile der Prozesse(Bekanntgabe der offentlichen Schlussel, Fortsetzungen, etc.)wurden weggelassen.




Alle moglichen Protokollablaufe dieses Protokolls – in Anwesenheiteines Angreifers – werden nun mit Hilfe von Hornklauselnmodelliert.

Als Theorien benotigen wir symmetrische und asymmetrischeVerschlusselung.




Wir verwenden Formeln, bestehend aus:

Funktionssymbolen, die den Konstruktoren aus der Theorieentsprechen.

Konstantensymbolen, die den im Protokoll vorkommendenNamen entsprechen oder das Vorwissen des Angreifersreprasentieren.

Pradikatsymbolen:

Att (einstellig)Intuition: Falls Att(M) fur einen Konstruktorterm M gilt,so bedeutet dies, dass der Angreifer M kennt.Msg (zweistellig)Intuition: Falls Msg(c ,M) fur einen Kanal c und einenKonstruktorterm M gilt, so bedeutet dies, dass der Termauf dem Kanal verschickt wird.




Hornklauseln fur die Konstruktoren

Att(x1) ∧ · · · ∧ Att(xn)→ Att(f (x1, . . . , xn))

fur jeden n-stelligen Konstruktor f in der Theorie.

Im betrachteten Beispiel:

Att(x) ∧ Att(y)→ Att(sencrypt(x , y)) (K1)

Att(x) ∧ Att(y)→ Att(aencrypt(x , y)) (K2)

Att(x)→ Att(pk(x)) (K3)

Att(x)→ Att(sk(x)) (K4)




Hornklauseln fur die Destruktoren

Att(M1) ∧ · · · ∧ Att(Mn)→ Att(M)

fur jede Gleichung der Form g(M1, . . . ,Mn) = M.


Att(sencrypt(x , y)) ∧ Att(y)→ Att(x) (D1)

Att(aencrypt(x , pk(y))) ∧ Att(sk(y))→ Att(x) (D2)




Hornklauseln fur das Verhalten des Angreifers

Msg(x , y) ∧ Att(x)→ Att(y) (E1)

(Angreifer kann Nachrichten von Kanalen, die er kennt, abfangen.)

Att(x) ∧ Att(y)→ Msg(x , y) (E2)

(Angreifer kann Nachrichten, die er kennt, auf Kanalenverschicken, die er kennt.)




Modellierung des Protokolls (Teil 1)

Fur einen Teilnehmer des Protokolls werden folgende Hornformelnerzeugt: falls der Teilnehmer nach dem Empfang der Nachrichtenx1, . . . , xn (jeweils auf den Kanalen c1, . . . , cn) denKonstruktorterm M als Nachricht auf dem Kanal c verschickt, soerzeugen wir folgende Klausel:

Msg(c1, x1) ∧ · · · ∧Msg(cn, xn)→ Msg(c ,M)

Es muss jede der vorher empfangenen Nachrichten berucksichtigtwerden, denn M konnte die entsprechenden Variablen enthalten.

Im betrachteten Beispiel: Verhalten von Alice

Msg(c , p)→ Msg(c , aencrypt(K , p)) (A1)

Dabei sind c ,K Konstanten und p eine Variable.Barbara Konig “Form. Asp. der Software-Sicherheit und Kryptographie” 394



Modellierung des Protokolls (Teil 2)

Falls der Term M, der verschickt wird, kein Konstruktorterm ist, sowird folgendermaßen verfahren:

Wir betrachten alle minimalen Substitutionen sub, so dassΣ ` Msub = M ′, wobei M ′ ein Konstruktorterm ist.(“Minimal” bedeutet, dass so wenig wie moglich ersetzt wird,analog zum allgemeinsten Unifikator.)

Fur jede solche Substitution sub wird folgende Klausel erzeugt:

Msg(c1, x1sub) ∧ · · · ∧Msg(cn, xnsub)→ Msg(c ,M ′)




Im betrachteten Beispiel: Verhalten von Bob

Msg(c , pk(KB)) (B1)

Msg(c , aencrypt(z , pk(KB)))→ Msg(c , sencrypt(m, z))(B2)

Dabei sind c ,KB ,m Konstanten und z eine Variable.

Die fur den zweiten Fall eingesetzte Substitution istsub = [y/aencrypt(z , pk(KB))], die dazu fuhrt, dassΣ ` Msub = sencrypt(m, z), furM = sencrypt(m, adecrypt(y , sk(KB))).




Vorwissen des Angreifers

Der Angreifer erhalt Wissen uber alle freie Kanale, außerdem erhalter Konstanten, die er als Nonces bzw. Schlussel einsetzen kann.


Att(c) (V1)

Att(KE ) (V2)




Zielklausel

Wir betrachten zunachst den Fall der Geheimhaltung einerNachricht m. Dann ist die Zielklausel

Att(m)

Dabei wird die Zielklausel negiert zur Klauselmenge hinzugefugt:¬Att(m) (Z)




Mit Hilfe der obigen Hornklauseln, kann man die leere Klauselableiten, wir benutzen dazu unare Resolution.

Att(c)(V1) ¬Att(x),¬Att(y),Msg(x , y)(E2)

¬Att(y),Msg(c , y)(R1)

Att(c)(V1) ¬Msg(x , y),¬Att(x),Att(y)(E1)

¬Msg(c , y),Att(y)(R2)




¬Msg(c , y),Att(y)(R2) Msg(c, pk(KB))(B1)

Att(pk(KB))(R3)




Att(KE )(V2) ¬Att(x),Att(pk(x))(K1)

¬Att(y),Msg(c, y)(R1) Att(pk(KE))(R4)

¬Msg(c, p),Msg(c, aencrypt(K , p))(A1) Msg(c, pk(KE ))

Msg(c, aencrypt(K , pk(KE )))(R5)




Msg(c, aencrypt(K , pk(KE )))(R5) ¬Msg(c, y),Att(y)(R2)

Att(aencrypt(K , pk(KE )))(R6)




Att(KE )(V2) ¬Att(x),Att(sk(x))(K2)

¬Att(aencrypt(x , pk(y))),¬Att(sk(y)),Att(x)(D1) Att(sk(KE))

Att(aencrypt(K , pk(KE )))(R6) ¬Att(aencrypt(x , pk(KE ))),Att(x)

Att(K)(R7)




Att(pk(KB))(R3) ¬Att(x),¬Att(y),Att(aencrypt(x , y))(K3)

Att(K)(R7) ¬Att(x),Att(aencrypt(x , pk(KB))))

¬Att(y),Msg(c, y)(R1) Att(aencrypt(K , pk(KB))))

Msg(c, aencrypt(K , pk(KB)))(R8)




Msg(c, aencrypt(K , pk(KB)))(R8) ¬Msg(c, aencrypt(z , pk(KB))),Msg(c, sencrypt(m, z))(B2)

¬Msg(c, y),Att(y)(R2) Msg(c, sencrypt(m,K))

¬Att(sencrypt(x , y)),¬Att(y),Att(x)(D2) Att(sencrypt(m,K))

Att(K)(R7) ¬Att(K),Att(m)

¬Att(m)(Z) Att(m)




D.h., da es einen Angriff auf dieses Protokoll gibt, ist die leereKlausel ist ableitbar.

Der dazugehorige Angriff laßt sich auch aus dem Resolutionsbeweisherleiten.

Es ist jedoch noch nicht klar, wie man im Fall eines korrektenProtokolls beweisen soll, dass die leere Klausel nicht herleitbar ist.




Achtung:

Der obige Resolutionsbeweis entspricht einem Angriff, derauch in dem Fall funktionieren wurde, wenn derSitzungsschlussel von Alice signiert wird. (Eve “denkt” sicheinen offentlichen Schlussel fur Bob aus und schickt diesen anAlice.)

In dem vereinfachten Protokoll gibt es noch einen direkterenAngriff fur Eve: sie erzeugt einfach selbst denSitzungsschlussel, verschlusselt diesen mit dem offentlichenSchlussel von Bob und schickt diese Nachricht an Bob.




Zunachst betrachten wir aber, wie weitere syntaktische Konstruktedes π-Kalkuls in Hornklauseln ubersetzt werden. Bisher hatten wirnur sequentielle Abfolgen von Prafixen betrachtet.

Parallele Komposition

Ein Prozess P | Q wird dadurch ubersetzt, dass sowohl dieKlauseln von P als auch die Klauseln von Q erzeugt werden.

Replikation

In einem Prozess der Form !P wird die Replikation zunachstignoriert. Das ist korrekt, da logische Formeln nicht “verbraucht”werden, sondern immer fur Schlussfolgerungen zur Verfugungstehen.Die Tatsache, dass unter einer Replikation aber immer wieder neueNamen erzeugt werden konnen, wird im nachsten Fall behandelt.




Verschattung

In einem Prozess der Form (νu)P wird fur jede Folge vonNachrichten, die zuvor empfangen wurden, ein neuer Name uerzeugt. Das ist insbesondere dann wichtig, wenn sich der Prozessunter einer Replikation befindet. Dabei wird u ersetzt durchu(x1, . . . , xn), wobei die Variablen aus den vorher vorkommendenEingabe-Prafixen entnommen werden.

Beispiel: !c(x).(νn)(d〈n〉.P) ergibt unter anderem die Hornklausel

Msg(c , x)→ Msg(d , n(x))

Das ist ahnlich zu der sogenannten Skolemisierung, bei derExistenzquantoren in pradikatenlogischen Formeln eliminiertwerden.




If-Then-Else

In einem Prozess der Form if M = N then P else Q bestimmtman die minimalen Substitutionen sub, so dass Σ ` Msub = Nsubund Msub ein Konstruktorterm ist. Auf die Klauseln, die aus Pentstehen, werden dann diese Substitutionen angewandt, um dieeigentlichen Hornklauseln zu erhalten. Die Klauseln, die aus Qentstehen, bleiben unverandert.

Beispiel: c(x).(if n = sdecrypt(x ,K ) then d〈x〉.0 else 0)

sub = [x/sencrypt(n,K )] ist die einzige minimale Substitution, diezur Gleichheit von n und sdecrypt(x ,K ) fuhrt.

Aus dem Then-Fall entsteht damit die KlauselMsg(c , sencrypt(n,K ))→ Msg(d , sencrypt(n,K )).




Das Verifikationsverfahren arbeitet zwar mit Uberapproximation,ist aber in folgendem Sinne korrekt:

Korrektheit des Verifikationsverfahrens

Wenn es einen Angriff auf das Protokoll gibt, dann ist die erzeugteKlauselmenge unerfullbar, d.h., die leere Klausel ist ableitbar.

bzw.

Wenn die leere Klausel nicht ableitbar ist, dann gibt es keinenAngriff auf das Protokoll. D.h., das Protokoll ist korrekt.




Literaturhinweise zur Verifikation von kryptographischenProtokollen mit Hornklauseln:

Bruno Blanchet: Using Horn Clauses for Analyzing SecurityProtocols. Formal Models and Techniques for AnalyzingSecurity Protocols. IOS Press, 2010.(Uberblick und Beschreibung der verwendetenResolutionstechniken)

Martın Abadi and Bruno Blanchet: Analyzing SecurityProtocols with Secrecy Types and Logic Programs. Journal ofthe ACM, 52(1):102-146, 2005.(Enthalt unter anderem das Verfahren zur Ubersetzung vonProzessen in Horn-Klauseln)




Bruno Blanchet: Automatic Verification of Correspondencesfor Security Protocols. Journal of Computer Security,17(4):363-434, 2009.(Beschreibt die Verifikation von Authentifizierung)

Artikel sind erhaltlich unterprosecco.gforge.inria.fr/personal/bblanche/index-eng.html




Wir betrachten nun die Funktionsweise von ProVerif:

ProVerif hat zwei verschiedene Eingabeformate: Hornklauselnund Prozesse des angewandten π-Kalkuls. Wir verwenden nurdas zweite Eingabeformat.

ProVerif liefert eine der folgenden drei Ausgaben:

Die zu verifizierende Eigenschaft ist erfullt. (Zielklauselist durch Resolution nicht herleitbar.)Es gibt einen Angriff (mit Ausgabe des Angriffs).Die Eigenschaft kann nicht verifiziert werden. (Zielklauselist durch Resolution herleitbar, es kann jedoch keinAngriff gefunden werden.)




Wir betrachten nun das obige Beispielprotokoll Protokoll undmodellieren es in ProVerif:

param traceDisplay = long.

(* Kleines Beispiel-Protokoll - vereinfacht *)

free c.

(* Asymmetric Encryption *)

fun aencrypt/2.

fun pk/1.

fun sk/1.

reduc adecrypt(aencrypt(m,pk(k)),sk(k)) = m.

(* Symmetric Encryption *)

fun sencrypt/2.

reduc sdecrypt(sencrypt(m,k),k) = m.




query attacker:secretM[].

let processA =

new K;

in(c, p);

out(c, aencrypt(K,p));

in(c, x).

let processB =

new secretM;

new Kb;

out(c,pk(Kb));

in(c,y);

out(c,sencrypt(secretM,adecrypt(y,sk(Kb)))).

process

(processA | processB)




Aufruf von ProVerif:

> proverif -in pi beispiel-prot-simple

[...]

A trace has been found.

RESULT not attacker:secretM_8[] is false.

Es wird auch der Angriff explizit ausgegeben.




Wir betrachten nun die Modellierung des fehlerhaftenNeedham-Schroeder-Protokolls in ProVerif.


(* Needham-Schroeder - fehlerhaft *)

free cs.

free cab.

free fail.


fun sencrypt/2.

fun ok/0.


reduc check(sencrypt(m,k),k) = ok().

(* Dekrementierung *)

fun dec/1.




query ev:a(x,y) ==> ev:b(y,x).

let processA =

new Na;

out(cs, (A,B,Na));

in(cs, x);

let (N,Kab,M) = sdecrypt(x,Kas) in

if N=Na

then out(cab,M);

in(cab,y);

if check(y,Kab)=ok()

then out(cab,sencrypt(dec(sdecrypt(y,Kab)),Kab));

event a (A,B).




let processB =

new Nb;

in(cab,x);

let (Kab,a) = sdecrypt(x,Kbs) in

event b (B,a);

out(cab,sencrypt(Nb,Kab));

in(cab,y);

if sdecrypt(y,Kab) = dec(Nb)

then 0

else out(fail,()).




let processS =

in(cs,(t1,t2,N));

new K;

if t1=A then (if t2=B then

out(cs,sencrypt((N,K,sencrypt((K,A),Kbs)),Kas))

else if t2=E then

out(cs,sencrypt((N,K,sencrypt((K,A),Kes)),Kas)))

else if t1=B then (if t2=A then

out(cs,sencrypt((N,K,sencrypt((K,B),Kas)),Kbs))

else if t2=E then

out(cs,sencrypt((N,K,sencrypt((K,B),Kes)),Kbs)))

else if t1=E then (if t2=A then

out(cs,sencrypt((N,K,sencrypt((K,E),Kas)),Kes))

else if t2=B then

out(cs,sencrypt((N,K,sencrypt((K,E),Kbs)),Kes))).




process

new Kas;

new Kbs;

(processA | processB | processS)




Bei Aufruf von ProVerif wird wieder ausgegeben, dass dieEigenschaft nicht erfullt ist:

> proverif -in pi my-needham-schroeder

[...]

The event a(A,B) is executed.

A trace has been found.

RESULT ev:a(x_25,y_26) ==> ev:b(y_26,x_25) is false.




Hier wird korrekte Authentifizierung durch Korrespondenz vonEreignissen uberpruft:

Wenn Ereignis (event) a(x,y) eintritt, dann muss zuvorEreignis b(y,x) eingetreten sein.

Dazu reichert man die Syntax und Semantik des π-Kalkuls umEreignisse an.

Die Verifikation funktioniert in etwa folgendermaßen: es wirduberpruft, dass in jedem Resolutionsbeweis, der eineTatsachenklausel mit dem Ereigniss a(x,y) ableitet, b(y,x)als Hypothese verwendet wird.




Das Needham-Schroeder-Protokoll kann korrigiert werden, so dassdie Verifikation erfolgreich ist. Insbesondere muss dazu der Serverden Namen des Kommunikationspartners mit in die Nachrichtaufnehmen und Alice muss dies uberprufen.

Wir andern das Protokoll (insbesondere die Prozesse, die Alice undden Server beschreiben) entsprechend ab . . .




let processA =

new Na;

out(cs, (A,B,Na));

in(cs, x);

let (N,b,Kab,M) = sdecrypt(x,Kas) in

if N=Na

then if b=B

then out(cab,M);

in(cab,y);

if check(y,Kab)=ok()

then out(cab,sencrypt(dec(sdecrypt(y,Kab)),Kab));

event a (A,B).




let processS =

in(cs,(t1,t2,N));

new K;

if t1=A then (if t2=B then

out(cs,sencrypt((N,B,K,sencrypt((K,A),Kbs)),Kas))

else if t2=E then

out(cs,sencrypt((N,E,K,sencrypt((K,A),Kes)),Kas)))

else if t1=B then (if t2=A then

out(cs,sencrypt((N,A,K,sencrypt((K,B),Kas)),Kbs))

else if t2=E then

out(cs,sencrypt((N,E,K,sencrypt((K,B),Kes)),Kbs)))

else if t1=E then (if t2=A then

out(cs,sencrypt((N,A,K,sencrypt((K,E),Kas)),Kes))

else if t2=B then

out(cs,sencrypt((N,B,K,sencrypt((K,E),Kbs)),Kes))).




Bei Aufruf von ProVerif wird ausgegeben, dass die Eigenschaft zuverifizierende Eigenschaft (Authentifizierung) erfullt ist:

> proverif -in pi my-needham-schroeder-correct

[...]

Starting query ev:a(x_26,y_27) ==> ev:b(y_27,x_26)

goal reachable: begin:b(B[],A[]) -> end:a(A[],B[])

RESULT ev:a(x_26,y_27) ==> ev:b(y_27,x_26) is true.




Dieses Verifikationsverfahren ist eine Approximationstechnik.Uber-Approximation entsteht insbesondere durch folgende Effekte:

Die Kodierung ignoriert wie oft eine Aktion ausgefuhrt wird.Auch wenn eine Nachricht nur einmal empfangen werdenkann, kann die dazugehorige Hornklausel beliebig oftverwendet werden. Das bedeutet im Wesentlichen, dass jederProzess als replizierter Prozess betrachtet wird.

Außerdem entsteht Uberapproximation durch die Behandlungvon If-Then-Else-Anweisungen. (Vor allem durch fehlendeEinschrankungen fur den Else-Fall.)

Des weiteren konnen verschattete Namen, die eigentlichverschieden sind, durch die Approximation als gleichangesehen werden.

Dies fuhrt jedoch nur zu zusatzlichem Verhalten, tatsachlicheSystemablaufe werden nie unterschlagen.




In folgendem Beispiel kann Prozess processB nur einen Nonceentschlusseln und zuruckschicken, processA schickt daher niemalsdas Geheimnis. Das kann durch die Uberapproximation jedochnicht erkannt werden.


(* Beispiel fuer Ueberapproximation *)

free c.


fun sencrypt/2.


query attacker:secretM[].




let processA =

new N1;

new N2;

out(c,sencrypt(N1,K));

out(c,sencrypt(N2,K));

in(c,x1);

in(c,x2);

if x1=N1

then if x2=N2 then out(c,secretM)

else 0 else 0.

let processB =

in(c,x);

out(c,sdecrypt(x,K)).

process

new K;

new secretM;

(processA | processB)




ProVerif erzeugt folgende Ausgabe:

> proverif -in pi approx

[...]

Could not find a trace corresponding to this derivation.

RESULT not attacker:secretM_7[] cannot be proved.

Ein echter Angriff wird jedoch gefunden, wenn processB repliziertwird. Denn dann kann er beliebig viele Nonces entschlusseln.




Ein Hauptproblem beim Einsatz von Resolution in ProVerif ist dieTerminierung. Fur eine gegebene Menge M von Klauseln ist esnormalerweise nicht klar, dass Res∗(M) endlich ist und derResolutionsprozess damit terminiert.

Man kann jedoch in vielen Fallen Terminierung erreichen, indemman SLD-Resolution und unare Resolution geeignet miteinanderkombiniert.



Verhaltensaquivalenzen

Wir betrachten nun (ganz kurz) eine dritte Technik zur Verifikationvon kryptographischen Protokollen: Verhaltensaquivalenzen. Dazunehmen wir an, dass ein externer Beobachter mit dem Systeminteragiert. Man mochte feststellen, ob der Beobachter das SystemSys von einem anderen System Sys ′ unterscheiden kann odernicht. (Ahnlich zu Zero-Knowledge.)

Wir schreiben P ≈ Q, wenn sich P,Q aus der Sicht des externenBeobachters gleich verhalten (Beobachtungskongruenz).



Verhaltensaquivalenzen

Geheimhaltung mit Verhaltensaquivalenzen

Sei P ein Prozess mit einer freien Variablen x , die fur eineNachricht steht. Ein Prozess P gewahrleistet die Geheimhaltungder entsprechenden Nachricht, wenn

P[x/m] ≈ P[x/n]

fur zwei beliebige Namen m, n gilt.



Weitere Verifikationstechniken

BAN-Logik (Burrows-Abadi-Needham-Logik): Logik, in derman Schlusse uber kryptographische Protokolle ziehen kannund Aussagen folgender Form machen kann: “Teilnehmer Aglaubt X”, “Teilnehmer B sagt Y ”, “Nonce N ist frisch”

AVISPA: Automated Validation of Internet Security Protocolsand Applications (EU-finanziertes Projekt)

CASPA: Causality-based Abstraction for Security ProtocolAnalysis (M. Maffei, Universitat des Saarlandes)

Scyther: A Tool for the Automatic Verification of SecurityProtocols (C. Cremers, ETH Zurich)

und viele weitere Methoden und Werkzeuge . . .



Schlussbemerkungen

Verifikatikonstechniken sollten helfen, Protokolle besser zuverstehen und robustere Protokolle zu entwerfen (auch indemman typische Fehler aufdeckt).

Siehe auch Abadi’s Design Principles in Security Protocols:Principles and Calculi – Tutorial Notes. Dort werden typischeFehler besprochen und erklart, wie man sie vermeiden kann.



Schlussbemerkungen

Kann man aus der Korrektheit eines Protokolls nach demDolev-Yao-Eindringlingsmodell auch etwas uber dieAngriffsmoglichkeiten von polynomzeitbeschranktenprobabilistischen Angreifern sagen?

dazu gibt es inzwischen ebenfalls Arbeiten (beispielsweise:Abadi, Rogaway: Reconciling two views of cryptography (Thecomputational soundness of formal encryption). Journal ofCryptology, 15(2):103–127, 2005.

Dieser Bereich ist weiterhin ein interessantesForschungsthema.



Schlussbemerkungen

Es gibt auch Verfahren, die Protokolle, in denenVerschlusselungsverfahren (RSA, etc.) explizit Teil desProtokolls sind, direkt verifizieren. (Korrektheit bezuglicheines polynomzeitbeschrankten probabilistischen Angreifers.)

Einsatz von Theorembeweisern (beispielsweise: GillesBarthe, Benjamin Gregoire, Sylvain Heraud, Santiago ZanellaBeguelin: Computer-Aided Security Proofs for the WorkingCryptographer. CRYPTO 2011: 71-90)


Documents

Formale Aspekte der Software-Sicherheit und Kryptographie ... · Gibt es eine andere Methode, den Text zu entschl usseln? Barbara K onig \Form. Asp. der Software-Sicherheit und Kryptographie"