Algorithmen für Peer-to-Peer-Netzwerke Sommersemester 2004 09.07.2004 12. Vorlesung

1

HEINZ NIXDORF INSTITUTUniversität Paderborn

Algorithmen und Komplexität

Algorithmen für Peer-to-Peer-Netzwerke

Sommersemester 200409.07.2004

12. Vorlesung

Christian Schindelhauer

Algorithmen für Peer-to-Peer-Netzwerke 2


Algorithmen und KomplexitätChristian Schindelhauer

ORGANISATIONNächste Vorlesung:

Kommenden Montag 9 Uhr12.07.2004, 9-11 Uhr F0.530

Weitere interessante Veranstaltungen– Informationsveranstaltung: Umstellung DPO 4 nach

Bachelor/Master-StudiumDonnerstag, 15.07.2004, 15:00 Uhr im Audimax

– Projektgruppenvorstellung für Wintersemester 2004/05Montag, 19.07.2004, 16 Uhr in Raum F0.530




ORGANISATIONAbschlussveranstaltung: Termin: Dienstag 03.08. ab 20 UhrVeranstaltungsform: Grillen

Getränke werden gestellt, Essen muss selbst organisiert werden

Ort: 1. Freizeitparadies Lippe-See2. Schloß- und Auenpark Paderborn3. Bad Lippspringe: Hindahls Kreuz4. Nähe Campus: Grillplatz am Querweg (hinter B64)5. Hinter dem HNI-Gebäude6. ...




ORGANISATIONMündliche Prüfung: Termine: 13.-17.09.2004 (10-17 Uhr)

04.-08.10.2004 (10-17 Uhr)

Gastdozent:

Prof. Dr. Christian Scheideler(Johns Hopkins University)

30.07.2004, 9-10 Uhr, F0.530

Öffentliche mündliche Prüfung: 30.07.2004, 10 Uhr, F0.530

(in der letzten Vorlesung)




Kapitel IV

Algorithmen für Peer-to-Peer-Algorithmen für Peer-to-Peer-NetzwerkeNetzwerke

Sicherheit in

Peer-to-Peer-Netzwerken




Verschlüsselungsmethoden

Symmetrische Verschlüsselungsverfahren

– z.B. Cäsars Code, DES, AES– Es gibt Funktion f,g, so dass

• f(schlüssel,text) = code• g(schlüssel,code) = text

– Der Schlüssel • muss geheim bleiben• dem Sender und

Empfänger zur Verfügung stehen

Asymmetrische Verschlüsselungsverfahren–z.B. RSA, Ronald Rivest, Adi Shamir, Lenard Adleman, 1977

• Diffie-Hellman, PGP–Geheimer Schlüssel privat

• kennt nur der Empfänger der Nachricht–Öffentlichen Schlüssel offen

• Ist allen Teilnehmern bekannt• Wird erzeugt durch Funktion

keygen(privat) = offen–Verschlüsselungsfunktion f und Entschlüsselungsfunktion g

• sind auch allen bekannt–Verschlüsselung

• f(offen,text) = code• kann jeder berechnen

–Entschlüsselung• g(privat,code) = code• nur vom Empfänger




Digitale Unterschriften (Signaturen)

Beruhen auf asymmetrischen Verschlüsselungsverfahren, z.B. RSA

– Der Unterzeichner erzeugt geheimen Schlüssel (privat)

– und öffentlichen Schlüssel (offen)

– Komprimat des Texts, z.B. durch kryptographsiche Hash-Funktion h• txt = h(text)

– Unterzeichner berechnet g(privat,h(text)) = signature– Empfänger kennen

• offen, text und signature• verifizieren f(offen,h(text)) = signature

Problem:

– Veröffentlichte Berechnung mittels geheimen Schlüssel kann die Sicherheit des Schemas gefährden (chosen-message-attack)

Lösung:

– Nachweisbar sicheres Signaturschem von Shafi Goldwasser, Silvio Micali, und Ronald Rivest, 1988




Sicherheit in Peer-to-Peer-Netzwerken

P2P-Netzwerke sind offen und autonom

– Scheinbarer Widerspruch zu Sicherheit?P2P-Netzwerk arbeiten in feindlicher Umgebung

– InternetAnforderungen

– Verfügbarkeit

– Dokumentauthentifikation

– Anonymität

– ZugangskontrolleMaßnahmen gegen Attacken

– Verhinderung

– Entdeckung

– Handhabung

– Systemwiederherstellung nach einer Attacke




Verfügbarkeit

Denial-of-Service Attack

– Dienstverweigerungsangriff, z.B.

– Viele Peers fragen ein Dokument nach

– Viele Peers bombardieren Knoten mit zentralen Aufgaben, z.b. Super-Nodes in Gnutella

Chosen-Victim Angriff in Gnutella (II)

– Ein bösartiger Peer lässt sich zum Super-Node erklären

– Dann erzeugt er eine Menge von Scheinanfragen für einen seiner PeersTypische Angriffe

– Ausnutzung von Protokoll-Schwächen

• kann nachgebessert werden

– Infiltration durch bösartigen Peers

• siehe byzantinische Generäle




Dokumentauthentifikation

Problemstellung:

– Welches Dokument ist authentisch?

– Welches ist gefälscht, nachgemacht oder verfälscht?Lösung:

– Digitale UnterschriftenDas Problem des Alters:

– Welches Dokument war zu erst da?

– Das Independent-Label oder der Markentitel

Wie kann man nachweisen, dass eine Datei älter ist als ein anders?

– C14-Methode, Vergilbung etc. funktioniert nicht

– Man kann mit herkömlichen Methoden höchstens nachweisen, dass ein Dokument jung ist (aber nicht, dass es alt ist)

• z.B. durch Referenz auf aktuelle nicht vorhersehbare Ereignisse (Europa-Meisterschaft)




Anonymität

Motivation

– nicht nur die Verhinderung des berechtigten Zugriffs staatlicher Verfolgungsbehörden gegen die unrechtliche Verletzung von Urheberschutzgesetzen

– Zensor und Verfolgung in DiktaturenGrade der Anonymität

– Autor

• Wer hat das erzeugt?

– Server

• Wo wird das gespeichert?

– Leser

• Wer hat sich das geholt?

– Dokument

• Welche Dokumente werden auf einen bestimmten Peer gespeichtert?Free Haven und Crowds

– bieten eine Palette verschiedener Grade der Anonymität




Zugangskontrolle

Motivation:

– Anwendung von Peer-to-Peer-Netzwerken in Unternehmen, Militär, etc. über das Internet

– Bezahl-Peer-to-Peer-Netzwerke

• siehe aktuelles NapsterLösung:

– Zentrale Authorisierung

– Virtual Money (ebenfalls zentral authentifiziert?)

Verteilte Lösungen hängen mit dem Problem der Identifizierung zusammen

– Kollision mit Anonymität

– Beispiel

• „Jeder darf sich eine Datei herunterladen“

• Wie erkennt man, dass er nicht schon dran war?




Die Sybil Attacke

Wer war Sybil?

– Flora Rheta Schreiber schrieb 1973 ein Buch „Sybil“

– Es handelte von einer Frau mit 16 separaten Persönlichkeiten:• Sybil: Aushilfslehrerin mit „Zeit-Aussetzern“• Peggy: 9 Jahre altes wütendes, verängstigtes Mädchen• Vicki: spricht fließend französisch, weiss alles• Vanessa: spielt Klavier und ist befreundet mit dem Nachbarn• Marsha: dunkle Persönlichkeit mit Selbstmordabsichten• ...

– Das Buch (und der darauf folgende Film 1976) geht auf einen tatsächlichen Fall zurück von

– Multipler Persönichkeitsstörung, mehrfacher SchizophrenieBis heute ist umstritten, in wie weit diese Krankheit bei Menschen wirklich

existiertBei Peer-to-Peer-Netzwerken ist eine absichtliche Persönlichkeitsstörung

ein probates Mittel um die Strukturen zu unterlaufen




Was kann eine Sybil-Attacke bewirken?

Ein Netzwerk kann dadurch den Zusammenhalt verlieren

– betrifft CAN, Chord, Viceroy, Pastry, Tapestry

– aber nicht Napster (nicht verteilt)

– nicht zwingend GnutellaMehrheitsabstimmungen über den Zustand des Netzwerks können gestört

werden

– Mehrheitsfrage: „Verhält sich ein Peer korrekt“

– Entscheidend für die Lösung des Problems der byzantinischen GeneräleAnfragen im Netzwerk

– können dadurch weitestgehend observiert werden

– können verlangsamt werden

– durch Zerstörung der NetzwerkstrukturDoS-Angriffe können gestartet werden

Sybil-Attacken greifen Peer-to-peer-Netzwerke wirkungsvoll an




Wie kann man Sybil-Attacken abwehren?

Durch zentrale Authorisierung der teilnehmenden Peers

– Eine zentrale Instanz authentifiziert die Existenz eines Teilnehmers und die Gültigkeit seiner öffentlicher Schlüssel durch eine digitale Unterschrift

– Jeder Peer kann sich dadurch von der Existenz des Peers überzeugenProblem: Dezentrale Authorisierung

– Erlaubt man einem Peer auch nur eine kleine Menge von anderen Peers zu authorisieren, dann

– Authorisiert Peer 1 den Peer 2

– Peer 2 authorisiert Peer 3

– Peer 3 authorisiert Peer 4

– ...

– Damit steht einer Sybil-Attacke nichts mehr im Wege




Der Sybil-Abwehransatz John Douceur(Microsoft Research)

Annahmen:

– Peers sind einzelne Rechner, die einer Person unterstehen

– Einzelpersonen besitzen nicht unbeschränkte RechenresourcenAlle Teilnehmer des Peer-to-Peer-Netzwerks

– müssen ein bestimmtes mathematisches Problem (Challenge) lösen.

– Zum Beispiel müssen sie für verschiedene Werte y, das x finden mit h(x)=y,

• h ist eine kryptographisch sichere Hash-Funktion

• y= h(x) wurde von einem herausfordenden Peer (Challenger) gewählt

• Die Größe der Aufgabe kann durch die teilweise Bekanntgabe der Bits von x bestimmt werden

Innerhalb einer gewissen Zeit kann jeder virtuelle Peer nur eine bestimmte Anzahl von solchen „Challenges“ lösen

Vorteil:

– Liefert einen Ansatz mit Sybil-Attacken fertig zu werdenNachteile: ...




Der Sybil-Abwehransatz von John Douceur und seine Nachteile

Riesige Verschwendung von RechenresourcenDurch „Ein-Hacken“ in fremde Rechner stehen Angreifer durch enorme

Rechenkapazitäten zur Verfügung

Heterogenität des Netzwerks

– Studenten an Universitäten können über Pool-Recher große Rechenkapazitäten verfügen

– Staatliche Einrichtung verfügen über noch größere Resourcen (siehe Motivation)

– Wenig leistungsfähige Peers können durch den Challenge überfordert werden

• ältere PCs, Pocket-PCs, etc.

Der Challenge selbst ist ein institutionalisierte Form des Denial-of-Service-Attacks




Das Problem der byzantinischen Generäle

3 Armeen stehen bereit die gegnerische Burg zu besiegen

Diese sind getrennt und kommunizieren über Boten

Greift nur eine Armee an, so verliert diese.

Greifen zwei an, so gewinnen dieseGreift keine an, so wird die Burg

ausgehungertAber ein General ist übergelaufen

–man weiß nicht, wer...





Der übergelaufene General X versucht nun

–A zum Angriff zu überreden–B zum Abwarten

A übermittelt den Befehl an BB übermittelt den Befehl an A

–Widerspruch! Attacke

Abwarten

X

A

B





A übermittelt den Befehl an BB übermittelt den Befehl an A

–Widerspruch!Weder B noch A können X als

Betrüger überführen–da X A oder B als Überläufer darstellt A

ttacke

Abwarten

X

A

B

Atta

cke? A

bwarten?




Byzantinische Abstimmung

Theorem

Das Problem der drei byzantinischen Generäle kann nicht gelöst werden

Für vier Generäle ist das Problem lösbar:

1-General, 3 Offiziere-Problem

1. Betrachte einen (loyalen) General und 3 Offiziere.

2. Verbreite Information des loyalen Generals an alle

Überläufer

General A: Attacke A: Attacke

A: AttackeA: pfft!




Byzantinische Abstimmung




2. Verbreite Information des loyalen Generals an alle Offizieren

Algorithmus

1. General A sendet seinen Befehl an alle anderen (A bleibt bei seinem Befehl)

2. Jeder andere General sendet diesen erhaltenen Befehl an alle anderen

3. Jeder berechnet die Mehrheitsentscheidung aus den Befehlen von B, .., D

Überläufer

General A: Attacke

A: AttackeB: AttackeC: AttackeD: Attacke

A: AttackeB: AbwartenC: AttackeD: Attacke

pfft!

A

B

D

C




Byzantinische AbstimmungDer Überläufer als General A




2. Verbreite Information des loyalen Generals an alle Offizieren

Algorithmus

1. General A sendet seinen Befehl an alle anderen

2. Jeder andere General sendet diesen erhaltenen Befehl an alle anderen

3. Jeder berechnet die Mehrheitsentscheidung aus Befehl von B, .., D

Überläufer

A: AbwartenB: AbwartenC: AbwartenD: Attacke

A: AttackeB: AbwartenC: AbwartenD: Attacke

General A: pfft!

A: AbwartenB: AbwartenC: AbwartenD: Attacke

A

B C

D




Lösung des Byzantinischen Generäle-Problems

TheoremFalls m Generäle Überläufer sind, müssen mindestens 2m+1 Generäle ehrlich sein, damit das Problem der Byzantinischen Generäle lösbar ist.

Diese Schranke ist genau, wenn keine kryptographischen Annahmen gemacht werden

– D.h. wenn man genug Zeit hat jede Verschlüsselung zu brechen

TheoremSteht ein digitales Signaturschema zur Verfügung, dann kann eine beliebige Anzahl von falschen Generälen verkraftet werden

Lösung:Jeder General unterschreibt seinen BefehlIn jeder Runde gibt jeder General alle Befehle an alle anderen weiterJeder inkonsistenter Befehl oder jede falsche Weitergabe kann sofort aufgedeckt und bewiesen werdenSchweigt ein General, so kann das unter den ehrlichen Generälen festgestellt werden




Byzantinische Generäle und Peer-to-Peer-Netzwerke - Ein Resumee

Durch den Einsatz von digitalen Unterschriften reduziert sich das Problem auf den (bösartigen) Ausfall von Knoten in einem Netzwerk

– wenn die Nachbarn die Kommunikation rekonstruieren könnenProblem

– dafür werden O(n) Nachrichten pro Peer verwendet

In „Scalable Byzantine Agreement“ von Clifford Scott Lewis und Jared Saja, 2003

– wurde ein skalierbares Verfahren auch ohne Signatur vorgestellt

– verkraftet n/6 bösartige Generäle

– verwendet nur O(log n) Nachrichten pro Knoten im Erwartungswert

– und findet eine Übereinkunft mit hoher Wahrscheinlichkeit




Ein Zensor-Resistentes Peer-to-Peer-Netzwerk

Amos Fiat, Jared Saia, 2002

– „Censorship Resistant Peer-to-Peer Content Addressable Networks“Problemstellung

– Ein Angreifer schaltet 50% aller Peers durch einen Angriff aus

– Gibt es ein Netzwerk, dass solche Angriffe verkraftet?Annahme:

– Der Angreifer weiß nichts über die interne Netzwerk-Struktur

– Verwendet man eine zufällige Zuweisung von Aufgaben,

– fällt jeder Knoten mit W‘keit 1/2 aus




Das Netzwerk

Besteht aus einer Butterfly-Struktur mit Clustern der Größe c log n

Die Cluster sind bipartite Expander-Graphen

Definition Bipartiter Graph

–Ein bipartiter Graph besteht aus zwei disjunkten Knotenmengen A und B, so dass jede Kante einen Knoten aus A und B besitzt

Definition Expander-Graph

–Ein bipartiter Graph ist ein Expander-Graph,

–wenn für jede Teilmenge X von A, deren Größe A um höchstens einen (gewissen) konstanten erreicht,

–die Menge der Nachbarknoten in B um einen (gewissen) konstanten Mindestfaktor größer ist

A

B




Diskussion

Vorteile:

– Sehr effizientes, robustes, einfaches Verfahren

– Das Funktionsprinzip lässt sich auf alle bisher diskutierten Verfahren verallgemeinern

Problem:

– Starke Annahme:

• Der Angreifer weiß nichts/wenig über die interne Struktur

• Funktioniert damit bei Systemen mit ZugangskontrolleFalls der Angreifer die Struktur kennt:

– Dann kann er jedes System mit konstanten Grad mit einem Denial-of-Service-Angriff auf wenige Peers aushebeln

Siehe auch

– Baruch Awerbuch, Christian Scheideler

• Eingeladener Vortrag am letzten Vorlesungstag

29


Algorithmen und Komplexität

Vielen Dank

Ende der 12. VorlesungNächste Vorlesung: Mo. 12.07.2004 9-11 UhrNächste Übung: Mo. 12.07.2004 16 Uhr (C)

Fr. 16.07.2004 9-11 Uhr (A+B)

Documents

Algorithmen für Peer-to-Peer-Netzwerke Sommersemester 2004 09.07.2004 12. Vorlesung