Robust and private computations of mobile agent alliances [Elektronische Ressource] / von Regine Endsuleit

Sujets

• Informatik

Informations

• Publié par: karlsruher_institut_fur_technologie
• Publié le: 01 janvier 2007
• Nombre de lectures: 25
• Langue: Deutsch
• Poids de l'ouvrage: 1 Mo

Extrait

Robust and Private Computations
of
Mobile Agent Alliances
Zur Erlangung des akademischen Grades eines
Doktors der Naturwissenschaften
von der Fakult¨at fu¨r Informatik der Universit¨at Fridericiana
zu Karlsruhe (TH)
genehmigte
Dissertation
von
Regine Endsuleit
aus Freiburg i.Br.
Tag der mu¨ndlichen Pru¨fung: 11. Mai 2007
Erster Gutachter: Prof. Dr. Jacques Calmet
Zweiter Gutachter: Prof. Dr. Andrea OmiciniFu¨r meinen Mann Ralf und die
su¨ßen Ma¨use Marc und EmilyDeutsche Zusammenfassung
DasParadigmadermobilenSoftware-Agentenhatsichnachwievorinderprak-
tischen Anwendung nicht in aller Konsequenzdurchgesetzt. Dies liegt vor allem
an der Schwierigkeit, einzelne autonome Agenten vor bo¨swilligen Gastrechn-
ern zu schu¨tzen. Man muß sich nicht nur mit einer m¨oglichen Korruption von
Code und Daten des Agenten befassen, sondern auch damit, daß er nicht kor-
rekt ausgefu¨hrt, fehlgeleitet, ausspioniert oder gar gelo¨scht wird. Diese Arbeit
pr¨asentiert ein Sicherheitsmodell basierend auf Agentenallianzen, welche eine
robuste und geheime Funktionsauswertung in einer nicht vertrauenswu¨rdigen
Umgebung wie dem Internet erm¨oglichen.
Der Schutz von mobilen Agenten ist ein sehr reges und anspruchsvolles For-
schungsgebiet. Die meisten Publikationen bieten kryptographische Methoden
an, mit denen gezielte Angriffe verhindert bzw. massiv erschwert werden (bei-
spielsweise durch Verschlu¨ssellung von Code und Daten). Wegen der Vielf¨altig-
keit der Gefahren hat dies zum einen zur Folge, daß die meisten Ansa¨tze sich
lediglich mit einem Angriffstyp befassen k¨onnen; zum anderen ist ein starker
kryptographischer Schutz in der Regel mit einer zu hohen Komplexita¨t verbun-
den. Auch gibt es bisher kein praktisch einsetzbares Sicherheitsmodell, welches
ohneVerwendungeinervertrauenswu¨rdigenInstanzbeweisbareSicherheitgegen
die Gesamtheit der genannten Bedrohungen liefert.
Die vorliegende Arbeit verfolgt einen v¨ollig anderen Ansatz. Inspiriert durch
kryptographischeProtokollefu¨r sichere Mehrparteienberechnungen,werden Al-
lianzen von Agenten erzeugt, die verteilte und fehltertolerante Berechnungen
durchfu¨hren. Die Korrektheit dieser Berechnungen ist garantiert, solange ein
aktiver Angreifer nicht mehr als t Agenten gleichzeitig korrumpiert. Der Wert
t ist protokollabha¨ngig und liegt fu¨r Allianzen, die aus n Agenten bestehen,
1 1zwischen ⌈ n⌉− 1 und ⌈ n⌉− 1. Die Eingaben der einzelnen Agenten fu¨r2 3
die gemeinsam zu berechnende Funktion werden mittels eines (t,n)-Verifiable
Secret-Sharing Schemas in Form sogenannter t-Shares auf alle Agenten verteilt.
Dies impliziert zum einen, daß nur bei Kooperation von mehr als t Agenten
Information u¨ber die verteilten Daten bekannt wird, und zum anderen, daß die
Integrit¨atderSharesgepru¨ftwerdenkann.DieeigentlicheFunktionsberechnung
entsprichtderAuswertungeinesarithmetischenSchaltkreises,wobeiAdditionen
von jedem Agenten lokal und ohne Kommunikation berechnet werden k¨onnen.
Fu¨r jedes Multiplikationsgatter hingegen muß die Allianz kommunizieren. Dies
bildet den beschr¨ankenden Faktor des vorgestellten Modells fu¨r den Einsatz in
realen Netzwerken.
Da Protokollefu¨r sichere Mehrparteienberechnungenn feste Parteien vorsehen,
muß fu¨r mobile Agenten das Problem der Migration gehandhabt werden. Bere-
its in einem statischen Szenario ist es unabdingbar, daß alle Mitglieder einerAllianz auf unterschiedlichen Hosts ausgefu¨hrt werden. Andernfalls k¨onnte eine
Allianzkompromittiertwerden,obwohlwenigeralstServermalizio¨ssind.Dieses
Sicherheitsproblem verscha¨rft sich in einem dynamischen Szenario, in welchem
dieAgentenvonHostzuHostmigrierenk¨onnenunddabeiihrenBerechnungszu-
stand mitfu¨hren. Ein Angreifer k¨onnte durch Ausfu¨hrung mehrerer Agenten
zu unterschiedlichen Zeitpunkten ausreichend viel Information erlangen, um
den Berechnungszustand aus den gesammelten t-Shares zu rekonsturieren. Fol-
glichistesnotwendig,außerhalbderanwendungsspezifischenBerechnungen(der
Auswertung des Schaltkreises) weitere verteilte Protokolle zur Verfu¨gung zu
stellen, welcheeine sichereMigrationerlauben. Inder vorliegendenDissertation
wird eine Lo¨sung aufgezeigt, die auf Resharing-Protokollen, Zertifikaten und
Mehrheitsentscheiden beruht.
Ein randomisierte Resharing erlaubt zum Zeitpunkt der Migration eine Neu-
verteilungdes BerechnungszustandeseinerAllianz,indemmithilfederaktuellen
t-Shares neue t-Shares fu¨r die neuen Hosts erzeugt werden. Das Verfahren stellt
sicher, daß die alten Shares schließlich nutzlos werden. Mit dieser Technik kann
also der Berechnungszustand sicher von einer Menge von Hosts auf eine andere
u¨bertragen werden.
Fu¨r statische Daten, wie beispielsweise den Schaltkreis, reicht eine digitale Sig-
natur des Allianzenerzeugers aus, um Hosts von der Integrit¨at der Daten u¨ber-
zeugen zu k¨onnen. Problematischer ist dynamisches Wissen, wie zum Beispiel
eine Liste der aktuellen Hosts der Allianz, welches nicht verteilt aufbewahrt
wird, aber auch nicht signiert werden kann. Das Modell fu¨r sichere Multiagen-
tenberechnungen sieht aus Effizienzgru¨nden fu¨r diese Art von Daten Mehrheit-
sentscheidevor.SowohlHostsalsauchdieAllianzenbedienensichdiesesMittels.
Neben dem theoretischen Rahmenwerk fu¨r Allianzen schl¨agt die Dissertation
eine konkrete Implementierung vor, welche eine quadratische Kommunikation-
skomplit¨aterreicht.DiesesErgebnisistoptimalfu¨rdenFall,daßkeinBroadcast-
Kanal zur Verfu¨gung steht. Dies ist in realen Netzen, wie dem Internet, meist
derFall.DerEinsatzeinerBroadcast-Simulationistdeswegennotwendig,welche
die Ursache fu¨r die quadratische Komplexita¨t des Gesamtprotokolls ist.
Fu¨r den Implementierungsvorschlag werden verschiedene Anwendungen vorge-
stellt, deren Komplexita¨t analysiert wird. So zeigt sich, daß das Modell zwar
derzeit fu¨r beliebige Anwendungen zu aufwendig, aber fu¨r eine sichere Imple-
mentierungverschiedenerkryptographischerPrimitivedurchauspraktikabelist.
SozumBeispielfu¨reineverteilte,fehlertoleranteSignatur.MitsteigenderBand-
breite wird sich die Praktikabilit¨at des Modells in Zukunft erho¨hen.
Dank der Natur der verteilten Berechnungen in dem vorgestellten Modell, k¨on-
nen korrumpierte Agenten entdeckt, eliminiert und ersetzt werden, ohne daß
Kommunikation mit einer vertrauenswu¨rdigenInstanz notwendig wird. Werden
zukeinemZeitpunktmehralstAgentengleichzeitigkorrumpiert,sobeeinflussen
sa¨mtliche der eingangs genannten Angriffe die Korrektheit und Geheimhaltung
der Berechnungen nicht. Somit liegt nun endlich ein theoretisches Rahmenwerk
vor, welches den Einsatz von mobilen Agenten fu¨r sensitive Anwendungen in
offenen und nicht vertrauenswu¨rdigen Netzen gestattet.Contents
Acknowledgement 1
Introduction 3
Mobile Agents – A Question of Trust . . . . . . . . . . . . . . . . . . . 3
Host and Agent Security . . . . . . . . . . . . . . . . . . . . . . . . . . 5
Secure Multi-Agent Computations . . . . . . . . . . . . . . . . . . . . 6
A Word on Concurrency . . . . . . . . . . . . . . . . . . . . . . . . . . 7
Structure of this Thesis . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1 The Mobile Agent Paradigm 11
1.1 What are Agents? . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.2 Agent Mobility . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.3 Mobile Agent vs. Client/Server Paradigm . . . . . . . . . . . . . 13
1.4 Where do we Need Mobile Agents? . . . . . . . . . . . . . . . . . 15
1.5 The Notion of Trust . . . . . . . . . . . . . . . . . . . . . . . . . 16
2 Security Issues and Related Work 19
2.1 Host Security . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.1.1 Threats . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.1.2 Security Measures . . . . . . . . . . . . . . . . . . . . . . 22
2.2 Agent Security . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.2.1 Threats . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
2.2.2 Approaches against Single Attacks . . . . . . . . . . . . . 26
2.2.3 Advanced Approaches . . . . . . . . . . . . . . . . . . . . 32
2.2.4 Security through Co-Operation . . . . . . . . . . . . . . . 38
3 SMAC in a Nutshell 41
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
3.1.1 Alliance Generation . . . . . . . . . . . . . . . . . . . . . 42
3.2 Lifetime of an Alliance . . . . . . . . . . . . . . . . . . . . . . . . 45
3.3 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
4 Secure Multi-Party Computation 49
4.1 How to Define a Security Model . . . . . . . . . . . . . . . . . . . 50
4.1.1 Protocol Properties. . . . . . . . . . . . . . . . . . . . . . 51
4.1.2 Attacker Models . . . . . . . . . . . . . . . . . . . . . . . 51
4.1.3 Error Behaviour . . . . . . . . . . . . . . . . . . . . . . . 53
4.1.4 Network Type . . . . . . . . . . . . . . . . . . . . . . . . 53
i4.1.5 The Notion of Security . . . . . . . . . . . . . . . . . . . . 55