Authentifizierungsmethoden in mobilen Ad-hoc-Netzen

Seminar: Datenkommunikation und Verteilte Systeme Wintersemester 2002-2003

Alexander Zimmermann Matrikelnummer: 217802

Betreuung: Ralf Wienzek Lehrstuhl für Informatik IV, RWTH Aachen

Rheinisch-Westfälische Technische Hochschule Aachen Lehrstuhl für Informatik IV

Prof. Dr. rer. nat. Otto Spaniol

1

Inhaltsverzeichnis 1. Einleitung ............................................................................................................................. 2 2. Konventionelle Authentifizierungsmethoden ........................................................................ 3 3. Grundlagen der Kryptographie............................................................................................ 4

3.1. Symmetrische Verschlüsselung...................................................................................... 4 3.2. Asymmetrische Verschlüsselung ................................................................................... 5

3.2.1. RSA Kryptographieverfahren ............................................................................... 5 3.3. Digitale Unterschriften ................................................................................................... 6 3.4. Secret-Sharing ................................................................................................................ 6

4. Modellierung ........................................................................................................................ 9 4.1. Das Netzwerkmodell ...................................................................................................... 9 4.2. Das Angreifermodell .................................................................................................... 10 4.3. Das lokale Vertrauensmodell ....................................................................................... 10

5. Der lokale Zertifizierungsdienst......................................................................................... 10 5.1. Verwendete Konzepte beim Zertifizierungsdienst ....................................................... 11 5.2. Der Ablauf des Zertifizierungsdiensts.......................................................................... 11 5.3. Die Parameter des Zertifizierungsdienst ...................................................................... 13 5.4. Das Zertifizierungsprotokoll ........................................................................................ 14

6. Parallel-Share-Update ....................................................................................................... 16 7. Implementierung und Leistungsbewertung ........................................................................ 17

7.1. Bewertung des Berechnungsaufwands......................................................................... 17 7.2. Bewertung der Kommunikationsprotokolle ................................................................. 18

7.2.1. Zertifizierungsdienst............................................................................................ 19 7.2.2. Parallel-Share-Update ......................................................................................... 20

8. Zusammenfassung .............................................................................................................. 21

2

1. Einleitung Seit ihren technologischen Anfängen in den frühen siebziger Jahren werden mobile Netzwerke immer populärer. Dies trifft insbesondere auf die letzten zehn Jahre zu, in denen die Netzfunktionen erweitert wurden, um Teilnehmermobilität zu ermöglichen [1]. Damals wurde die Entwicklung vor allem von US-Regierungsinstitutionen gefördert. Heutzutage wird zwischen zwei Typen von Wireless Networks unterschieden (Abbildung 1):

Infrastructured Network Ad Hoc Network

Base Station

Mobile Node

Wired Link

Wireless Link Abbildung 1: Mobile Netzwerke

Der erste Typ ist als Infrastructured Network bekannt, das heißt das Netzwerk besitzt sowohl Kabelstrecken (Wired Links) als auch Funkstrecken (Wireless Links). Typischerweise verbindet sich ein mobiler Knoten mit der nächsten Basisstation in seinem Funkbereich. Wenn sich nun ein mobiler Knoten außerhalb des Empfangsbereichs der bisherigen und in den Empfangsbereich einer anderen Basisstation bewegt, wird er mittels eines so genannten Handovers von der alten an die neue Basisstation übergeben und ist auf diese Weise fähig, ohne Unterbrechung im gesamten Netz zu kommunizieren. Eine typische Anwendung für diese Netzart ist zum Beispiel ein Wireless LAN in einem größeren Büro. Der zweite Typ von Wireless Networks ist das infrastrukturlose, mobile Netz, allgemein als Ad-hoc-Netzwerk bekannt [1]. Mobile Ad-hoc-Netzwerke haben unter anderem folgende wichtige Eigenschaften [2]:

o Dynamische Topologien: Die Knoten können sich frei bewegen, so dass sich die Netztopologie jederzeit beliebig und schnell ändern und aus bidirektionalen und unidirektionalen Links (typischerweise Funkverbindungen) bestehen kann.

o Links mit begrenzter Bandbreite und variabler Kapazität: Funkverbindungen werden

auf absehbare Zeit hin wesentlich geringere Kapazitäten als Kabelverbindungen aufweisen. Außerdem ist der tatsächliche Durchsatz einer Funkverbindung, abhängig von den Umgebungsbedingungen wie Interferenzen durch andere Sender, Reflexionen, etc., meist geringer als der theoretisch maximal mögliche. Ein Effekt der relativ geringen Linkkapazitäten ist, dass im Gegensatz zu Kabelverbindungen eine Vollauslastung der Links eher die Regel als die Ausnahme ist.

o Betriebsenergie ist nur begrenzt verfügbar: Einige oder alle Knoten in einem mobilen

Ad-hoc-Netzwerk beziehen ihre Betriebsenergie aus Batterien, Akkus oder ähnlichen Energiequellen. Für diese Knoten kann ein wichtiges Designkriterium sein, Energie zu sparen.

3

o Begrenzte physikalische Sicherheit: Da das Übertragungsmedium eines mobilen Ad-hoc-Netzes ein drahtloser Kanal ist, ist es anfälliger für bestimmte Angriffe als sein fest verdrahtetes Gegenstück. Die drei größten Probleme bei der Funkübertragung sind:

1. Eavesdropping, also Abhörangriffe auf den im Moment meist

unverschlüsselten Funkverkehr.

2. Spoofing, also Angriffe, bei denen sich ein Knoten als einer ausgibt, der er gar nicht ist.

3. Denial-of-Service-Angriffe (DoS), deren Ziel eine Einschränkung der

Verfügbarkeit darstellt. Im Folgenden wird das Thema die Authentifizierung bei mobilen Ad-hoc-Netzen sein. Unter Authentifizierung wird der Identitätsnachweis verstanden, den ein Benutzer gegenüber einem System oder einem Kommunikationspartner erbringen muss. Nachdem die Charakteristik der mobilen Ad-hoc-Netzwerke vorgestellt worden ist, wird der nächste Abschnitt zeigen, dass die in Praxis und Literatur bekannten zentralisierten und verteilten Authentifizierungsmethoden sich nicht für mobile Ad-hoc-Netzwerke eignen. Infolgedessen wird eine neue skalierbare, verteilte Authentifizierungsmethode vorgestellt. Abschließend wird im letzten Abschnitt eine auf Simulationsergebnisse basierende Bewertung vorgenommen. Sie zeigt, dass der hier vorgestellte Ansatz den hohen Ansprüchen eines mobilen Ad-hoc-Netzwerkes entspricht.

2. Konventionelle Authentifizierungsmethoden Eine in der Literatur und Praxis populäre Authentifizierungsmethode ist der zentralisierte Ansatz. Beim zentralisierten Ansatz stellt eine einzige Zertifizierungsautorität (CA) den Zertifizierungsdienst für das ganze Netzwerk zur Verfügung. Während sich dieses Modell für fest verdrahtete Netze in den meisten Fällen gut eignet, ist es aus folgenden Gründen für mobile Ad-hoc-Netzwerke ungeeignet:

o Zentralisierte Ansätze skalieren im Allgemeinen nicht.

o Die Verfügbarkeit der Server kann nicht sichergestellt werden. Zum einen stellen CA-Server einen Single-Point-of-Failure dar. Dadurch werden sie zum Hauptangriffspunkt für mögliche DoS-Angriffe. Zum anderen kann es vorkommen, dass durch eine ungünstige Änderung der Netzwerktopologie, die CA-Server physikalisch gar nicht erreichbar sind.

o Durch die Kommunikation über einen fehleranfälligen drahtlosen Kanal erfolgt die

Datenübertragungen mit einer höheren Verlustrate und einer höheren durchschnittlichen Latenz. Häufige, durch die Knotenmobilität induzierte Routenänderungen machen die Lokalisierung und Kontaktierung des CA-Servers in adäquater Zeit zu einem nichttrivialen Problem [5]. Variationen des obigen Modells, wie zum Beispiel hierarchische CA-Server können die Situation etwas verbessern, jedoch bleiben die Verfügbarkeit sowie die Robustheit des Systems weiterhin inakzeptabel.

4

Neben den zentralisierten Ansätzen existieren auch verteilte Authentifizierungsmethoden. Ein in der Praxis weit verbreiteter Ansatz ist PGP [6, 7], welches auf dem Web-of-Trust Authentifizierungsmodell basiert. Dieser Ansatz skaliert jedoch relativ schlecht mit der Netzwerkgröße. Es wäre schon in einem kleinen Netzwerk für jeden Knoten zu aufwendig, eine Liste seiner vertrauenswürdigen Partner zu verwalten. Hinzu kommt, dass die Meinungen der Mitglieder eines Netzwerks über die Vertrauenswürdigkeit eines bestimmten Knotens nicht notwendigerweise übereinstimmen müssen. Es besteht das Problem, wem vertraut werden kann und wem nicht. Nach den obigen Überlegungen ist ersichtlich geworden, dass die existierenden zentralisierten und verteilten Authentifizierungsmethoden nicht für ein mobiles Ad-hoc-Netzwerk geeignet sind. In dieser Arbeit wird ein neuer, zweckentsprechender verteilter Ansatz vorgestellt. Die Idee dieses Ansatzes ist, dass alle bzw. eine Mindestanzahl an Knoten des Netzwerks gemeinsam die Rolle der Zertifizierungsautorität übernehmen. Die Autorität und Funktionalität der CA wird also auf eine Menge von Knoten verteilt. Die Grundlage der verteilten Authentifizierungsmethode ist das Secret-Sharing-Protokoll nach Shamir [8], das im folgenden Abschnitt neben der symmetrischen und asymmetrischen Verschlüsselung vorgestellt wird.

3. Grundlagen der Kryptographie Dieser Abschnitt stellt die grundlegenden kryptographischen Konzepte vor. Es wird im Einzelnen auf symmetrische und asymmetrische Verschlüsselung, digitale Unterschriften und das Secret-Sharing-Protokoll von Shamir eingegangen.

3.1. Symmetrische Verschlüsselung Ein symmetrisches Verschlüsselungsverfahren benutzt zum Ver- und Entschlüsseln denselben Schlüssel. Zwei Kommunikationspartner, die eine symmetrische Verschlüsselung benutzen, müssen sich vorher über den Schlüssel einigen. Mit diesem Schlüssel verschlüsselt der Absender die Nachricht und schickt sie an den Empfänger, der sie unter Benutzung desselben Schlüssels wiederherstellt. Nach diesem Prinzip funktionierte beispielsweise die deutsche Enigma. Modernere Beispiele für symmetrische Verschlüsselungen sind Blowfish oder IDEA [9]. Ein gutes Verschlüsselungsverfahren legt den Schwerpunkt der Sicherheit auf die Geheimhaltung des Schlüssels und nicht auf die Geheimhaltung des verwendeten Algorithmus. Daher ist es keine Hilfe für einen Angreifer, wenn das Verschlüsselungs-verfahren bekannt ist, solange er nicht im Besitz des Schlüssels ist. Da die gesamte Sicherheit auf dem Schlüssel beruht, ist es wichtig, dass der Schlüssel mit verfügbaren Mitteln nicht zu erraten ist. Daraus folgt, dass der Vorrat an möglichen Schlüsseln, der so genannte Key-Space, möglichst groß sein muss. Eines der grundlegenden Probleme bei symmetrischen Verschlüsselungen ist nicht die Sicherheit der eingesetzten Verfahren, sondern der Austausch der Schlüssel. Wenn zwei Kommunikationspartner einmal die Schlüssel ausgetauscht haben, kann der betreffende Schlüssel für einen sicheren Datenaustausch benutzt werden. Die Frage ist nur, auf welchem sicheren Wege der Schlüsselaustausch stattfindet. In vielen Fällen wäre es für einen Angreifer leichter, den Schlüssel abzufangen, als alle möglichen Schlüssel im Key-Space auszuprobieren. Ein weiteres Problem ist die Anzahl der insgesamt benutzten Schlüssel. Wenn die Zahl der Leute, die miteinander kommunizieren wollen, n beträgt, so werden insgesamt n(n-1)/2 Schlüssel benötigt. Dies mag für eine geringe Personenzahl noch akzeptabel sein, lässt sich aber bei großen Personengruppen nicht mehr handhaben.

5

3.2. Asymmetrische Verschlüsselung Der Sinn der Public-Key-Verschlüsselung besteht darin, dass das Sicherheitsrisiko beim gegenseitigen Schlüsselaustausch gänzlich vermieden wird. Jeder Kommunikationspartner besitzt ein Schlüsselpaar bestehend aus einem öffentlichen Schlüssel PK, sowie einem geheimen Schlüssel SK, mit der Eigenschaft SK(PK(w)) = w für eine beliebige Nachricht w. Zum Verschlüsseln einer Nachricht wird der öffentlichen Schlüssel des Empfängers verwendet. Nur der Empfänger ist dann in der Lage, die Nachricht mit seinem geheimen Schlüssel wieder zu entschlüsseln. Ein weiterer Vorteil der asymmetrischen Verschlüsslung ist, dass nur n Schlüsselpaare notwendig, wenn n Leute vertraulich miteinander kommunizieren wollen. Public-Key-Verschlüsselungsverfahren basieren auf so genannten Einwegfunktionen. Dies sind Funktionen, die auf mathematisch schweren Problemen basieren, jedoch bei der Kenntnis gewisser Informationen trivial zu berechnen sind. So ist es zum Beispiel leicht, zwei Primzahlen miteinander zu multiplizieren, um eine Nichtprimzahl zu erhalten. Mathematisch gesehen ist es jedoch schwer, eine Nichtprimzahl in ihre Primfaktoren zu zerlegen. Wie bei guten symmetrischen Verschlüsselungsverfahren beruht die Sicherheit auch bei Public-Key-Verfahren hauptsächlich auf der Schwierigkeit, den geheimen Schlüssel zu ermitteln. Aus diesem Grund kann die Schlüsselgröße als ein Maß für die Sicherheit des Systems angesehen werden. Allerdings kann die Größe eines symmetrischen Schlüssels nicht mit der von Public-Key-Verfahren verglichen werden, um Rückschlüsse auf deren relative Sicherheit ziehen zu können. Bei einem Brute-Force-Angriff auf eine symmetrische Verschlüsselung mit einer Schlüsselgröße von 80 Bit muss der Angreifer bis zu 280-1 Schlüssel ausprobieren, um den richtigen Schlüssel zu finden. Bei einem Brute-Force-Angriff auf eine Public-Key-Verschlüsselung muss der Angreifer bei einer Schlüsselgröße von 512 Bit eine in 512 Bit kodierte Nichtprimzahl in ihre Primfaktoren zerlegen. Der Rechenaufwand für einen Angriff weist je nach Verschlüsselungsverfahren große Unterschiede auf. An dieser Stelle soll exemplarisch für die Public-Key-Verschlüsselung das Kryptographieverfahren RSA vorgestellt werden, welches einfach zu verstehen ist und heutzutage in der Praxis häufig eingesetzt wird.

3.2.1. RSA Kryptographieverfahren Der RSA-Algorithmus wurde nach ihren Entwicklern Rivest, Shamir und Adleman benannt und ist eines der bekanntesten Public-Key-Verschlüsselungsverfahren. RSA hat sich mittlerweile bewährt und ist eins der am besten untersuchten asymmetrischen Verfahren. Aufbau von RSA Zuerst muss ein öffentlicher und ein privater Schlüssel generiert werden:

o Wähle zwei große Primzahlen p und q.

o Setze qpm ⋅=: und )1)(1(:)( −−= qpmϕ .

o Wähle großes d > 1 mit 1))(,( =mdggT ϕ und bestimme e mit )( mod 1 mde ϕ≡⋅ .

o Der öffentliche Schlüssel ist >< me, und der private Schlüssel ist >< md , .

6

Verschlüsseln und Entschlüsseln mit RSA Um eine Nachricht w zu verschlüsseln, wird mit dem öffentlichen Schlüssel des Empfängers

>< me, die Berechnung mwc e mod = durchgeführt. Die verschlüsselte Nachricht kann nur noch der Besitzer des privaten Schlüssels >< md , , das heißt der Empfänger, durch Berechnen der Nachricht mcw d mod = lesen. Um RSA zu knacken, müsste ein unbefugter Dritter versuchen, den privaten Schlüssel d aus dem öffentlichen Schlüssel e zu berechnen oder )(mϕ zu bestimmen. Es lässt sich zeigen, dass beides mindestens so schwer ist, wie die Primfaktorzerlegung qpm ⋅=: zu berechnen. Es ist bisher noch kein Verfahren bekannt, das diese Berechnung in einem akzeptablen Zeitraum durchführt.

3.3. Digitale Unterschriften Public-Key-Verschlüsselungsverfahren können in der Regel auch zum Unterschreiben von Dokumenten benutzt werden. Hierzu muss jedoch neben SK(PK(w)) = w auch zusätzlich PK(SK(w)) = w gelten. Der Unterzeichner A verschlüsselt das Dokument w mit seinem privaten Schlüssel SKA, das heißt er berechnet u := SKA (w). Will nun der Empfänger B die Unterschrift prüfen, so benutzt er den öffentlichen Schlüssel PKA des Unterzeichners, entschlüsselt das Dokument und prüft, ob w = PKA (u) gilt. Ist dies der Fall, so kann B sicher sein, dass A das Dokument w unterschrieben hat, da nur A im Besitz des privaten Schlüssels SKA ist. Abbildung 2 zeigt den prinzipiellen Ablauf einer digitalen Unterschrift.

A : , , SK PK wA A B : PKA

w, uu SK (w):= A

Teste ob = ( )w PK uA

Abbildung 2: Eine einfache Digitale Unterschrift

Eine Möglichkeit, die Unterschrift zu fälschen, besteht darin, dass ein Angreifer C seinen öffentlichen Schlüssel PKc an B sendet und ihn überzeugt, dass dieser von A stammt. Gelingt es dem Angreifer, so kann er von nun an im Namen von A unterschreiben. Um dies zu verhindern, muss B sicherstellen, dass der öffentliche Schlüssel von A auch wirklich zu A gehört. Dies wird in der Regel durch Ausstellen von Zertifikaten erreicht, die eine Beziehung zwischen Identität und öffentlichen Schlüssel herstellen.

3.4. Secret-Sharing Aus Abbildung 2 ist ersichtlich, dass wenn ein Angreifer im Besitz des privaten Schlüssels von A kommt, er in der Lage ist, die digitale Unterschrift zu fälschen. Interessant wäre es, den privaten Schlüssel SKA von A auf mehrere Knoten aufzuteilen. Der Angreifer müsste in diesem Fall nicht einen, sondern mehrere Knoten kompromittieren, um in Besitz des Schlüssels zu kommen.

7

Genau diesen Ansatz verfolgt das Prinzip des Secret-Sharing, welches sich am einfachsten an einem Beispiel erklären lässt.

1. 11 Wissenschaftler arbeiten gemeinsam an einem geheimen Projekt. 2. Sie wollen ihre Arbeit so sichern, dass diese nur dann geöffnet werden kann, wenn 6

oder mehr Wissenschaftler anwesend sind. Welches ist die kleinste Anzahl von Schlüsseln, die jeder Wissenschaftler für die Sperren haben muss? Es ist leicht zu sehen, dass die minimale Lösung ( ) 46211

6 = Sperren und

( ) 252105 = Schlüssel pro Wissenschaftler braucht. Der naive Ansatz ist somit nicht

praktikabel, da die Zahl der Schlüssel und Sperren exponentiell steigt, wenn die Anzahl der Wissenschaftler linear zunimmt. Durch das Secret-Sharing wird nun versucht, das Problem zu lösen. Definition 1: Secret-Sharing Sei das Geheimnis ein beliebiger Datensatz S. Ohne Einschränkung der Allgemeinheit kann angenommen werden, dass S eine natürliche Zahl ist. Ein Algorithmus A, der S in n Teile S1,…,Sn zerlegt, so dass

1. die Kenntnis von mindestens k der Si eine Berechnung von S ermöglicht, und

2. die Kenntnis von bis zu k-1 der Si keine Information über S preisgibt, wird (n,k)-Secret-Sharing-Algorithmus genannt. In dieser Arbeit soll der Secret-Sharing-Algorithmus nach Shamir [8] vorgestellt werden. Er basiert auf einer einfachen Polynominterpolation. Algorithmus 1: Shamirs Secret-Sharing Sei NS ∈ das Geheimnis, n die Anzahl der Teilnehmer und k der Schwellwert. Sei weiter p eine Primzahl mit S,k < p.

o Aufbau des Systems 1. Wähle zufällig und gleichverteilt die k-1 Koeffizienten }1,...,0{ −=∈ pZa pi des

Polynoms 1110 ...)( −

−+++= kk xaxaaxf , wobei Sa =:0 durch das Geheimnis S

festgelegt ist. 2. Berechne für jeden Teilnehmer },...,1{ ni ∈ dessen Schlüssel pifS i mod)(:= . 3. Verteile an jeden Teilnehmer i seinen privaten Schlüssel Si.

o Rekonstruktion

Sobald sich k Teilnehmer zusammenfinden, um das Geheimnis zu rekonstruieren, können sie das Polynom f(x) durch Interpolation 1 in Zp wiederherstellen. Das Geheimnis ist dann durch S = f(0) gegeben.

1 Polynominterpolation: siehe Anhang

8

Lemma 1: Secret-Sharing Der obige Algorithmus ist ein (n,k)-Secret-Sharing-Algorithmus. Beweis:

1. Punkt 1 ist erfüllt, da sich eine eindeutige Polynominterpolation eines Polynoms vom Grad k-1 mit der Kenntnis von k Punkten in Zp effizient durchführen lässt.

2. Es wird angenommen, dass k-1 der n Teilgeheimnisse dem Angreifer bekannt sind.

Für jeden Wert pZS ∈' kann der Angreifer genau ein Polynom )(' xf vom Grad k-1

konstruieren, so dass ')0(' Sf = und iSif =)(' für die bekannten k-1 Teilgeheimnisse gilt. Nach Konstruktion sind diese p möglichen Polynome alle gleichwahrscheinlich und somit kann der Angreifer keine Informationen über das Geheimnis S erhalten. 9

Des Weiteren besitzt Shamirs (n,k)-Secret-Sharing-Algorithmus, im Vergleich zum naiven Ansatz, einige sehr nützliche Eigenschaften:

o Die Größe eines jeden Teilgeheimnisses Si ist nicht größer als die Größe des Originalgeheimnisses.

o Wenn k fest gewählt wird, können weitere Si dynamisch hinzugefügt oder auch

gelöscht werden.

o Es ist einfach, die Si neu zu bestimmen ohne das Geheimnis S selber zu ändern, indem ein neues Polynom f(x) mit gleichem a0 gewählt wird.

Beispiel 1: Shamirs Secret-Sharing Der Ablauf des Secret-Sharing-Algorithmus soll an einem Beispiel im Z11 vorgeführt werden. Das Geheimnis aus Z11 sei die Zahl S := 7, welches unter n := 4 Teilnehmern aufgeteilt wird, so dass jeweils k := 3 von ihnen S rekonstruieren können. Für den Schwellwert k = 3 wird ein Polynom zweiten Grades benötigt. Der Koeffizient a0 := S = 7 steht bereits fest. Zufällig werden die Koeffizienten a1:= 0 und a2 := 4 gewählt. Das erhaltene Polynom ist also: 247)( xxf += . Es ergeben sich für die vier Teilnehmer folgende Schlüssel:

Teilnehmer i Schlüssel Si = f(i) 1 0 2 1 3 10 4 5

9

Angenommen, die Teilnehmer v1, v2 und v4 wollen das Geheimnis entschlüsseln. Sie setzen sich zusammen und bestimmen durch die Lagrange-Polynominterpolation f(0) = S:

11 mod 74

)23(10)45(5

)2)(1(65)4)(1(9

)42)(41()2)(1(

5)24)(21()4)(1(

1)14)(12()4)(2(

0

)()(

2

22

11

3

1

3

,1

3

1

+≡

+−++−≡

−−⋅+−−≡

−−−−

+−−−−

+−−−−

≡

−

−≡

≡

−−

= ≠=

=

∑ ∏

∑

x

xxxx

xxxx

xxxxxx

xx

xxy

xLyxf

i ijjij

ji

i ii

4. Modellierung Bevor die Architektur und die Protokolle des Authentifizierungsdiensts beschrieben und bewertet werden können, ist es notwendig, dass das Netzwerkmodell, das Angreifermodell und das Vertrauensmodell formalisiert wird.

4.1. Das Netzwerkmodell Betrachtet wird ein dynamisches drahtloses Ad-hoc-Netzwerk mit n Netzwerkknoten. Die Anzahl der Netzwerkknoten ist dynamisch, da Knoten dem Netzwerk beitreten, es verlassen oder auch ausfallen können. Mobile Knoten kommunizieren miteinander über einen bandbreitenbeschränkten und fehleranfälligen drahtlosen Kanal. Folgende Annahmen werden gemacht:

o Jeder Knoten i besitzt eine global eindeutige ID vi mit 0≠iv .

o Eine One-hop-Kommunikation2 ist zuverlässiger als eine Multi-hop-Kommunikation bei einem fehleranfälligen, drahtlosen Kanal.

o Jeder Knoten besitzt mindestens k gültige One-hop-Nachbarschaftsknoten3.

o Die maximale Geschwindigkeit eines Knotens ist Smax.

o Jeder Knoten ist mit einem lokalen Intrusion-Detection-System4 ausgestattet.

2 Knoten kommunizieren direkt miteinander. 3 Wenn ein Knoten keine k Nachbarn finden kann, so muss er sich zu einem neuen Standort bewegen. 4 Eine Intrusion ist eine absichtliche Verletzung der Sicherheitsmaßnahmen eines Systems. Intrusion-Detection ist demnach der Versuch, diese Verletzung zu erkennen, sie entsprechend zu melden oder zu protokollieren und eventuell Gegenmaßnahmen einzuleiten.

10

4.2. Das Angreifermodell Das hier betrachtete Authentifizierungsmodell handhabt zwei verschiedene Angriffsarten: DoS-Angriffe, sowie Knotenpenetration. Die Architektur des Modells ist so gewählt, dass durch die Maximierung der Dienstverfügbarkeit versucht wird, die Wirkung eventueller DoS-Angriffe zu minimieren. Es wird angenommen, dass es einem Angreifer nicht möglich ist, das verwendete kryptographische Verfahren, das heißt RSA zu knacken. Jedoch ist der Angreifer in der Lage, Netzwerkknoten, bedingt durch ein unsicheres Betriebssystem, Softwarefehler, etc, zu kompromittieren. Sobald ein Netzwerkknoten von einem Angreifer kompromittiert worden ist, stehen dem Angreifer alle Daten, also insbesondere die privaten Schlüssel, des Knotens zur Verfügung. Einen Angreifer ist wie folgt charakterisiert:

Sei die Zeit in Intervalle der Länge T eingeteilt. In jedem Zeitintervall T kann der Angreifer höchstes k-1 Knoten gleichzeitig kompromittieren.

Obwohl es dem Angreifer also nicht möglich ist, k oder mehr Knoten gleichzeitig zu kompromittieren, kann er seine Ziele in jedem Zeitabschnitt neu definieren. Dadurch ist es möglich, dass jeder Knoten im Netzwerk während eines gewissen Zeitintervalls kompromittiert wird.

4.3. Das lokale Vertrauensmodell In dem hier vorgestellten lokalen Vertrauensmodell gilt ein Knoten als vertrauenswürdig, wenn eine Gruppe von k Knoten ihn für eine Zeitperiode Tcert für vertrauenswürdig hält. Diese k Knoten befinden sich typischerweise in der One-hop-Nachbarschaft des Knotens. Sobald ein Knoten von seiner lokalen Nachbarschaft als vertrauenswürdig angesehen wird, wird er auch global als vertrauenswürdig akzeptiert. Anderseits wird ein Knoten, der von seinen lokalen Nachbarn nicht mehr als vertrauenswürdig angesehen wird, im ganzen Netzwerk als unzuverlässig betrachtet. Die Parameter k und Tcert sind zwei fundamentale Parameter. Im Allgemeinen gibt es zwei Möglichkeiten, den Parameter k zu wählen. Die erste Möglichkeit ist, k als einen global festen Parameter anzusehen, der von jedem Knoten im System akzeptiert wird. In diesem Fall handelt es sich um eine systemweite „Vertrauensschwelle“. Die zweite Möglichkeit ist, k als einen lokal abhängigen Parameter zu sehen. Das in dieser Arbeit vorgestellte Authentifizierungsmodell wählt die erste Möglichkeit. k ist also ein netzwerkweit fester Parameter, der entsprechend der Netzdichte und der Anforderung an die Systemrobustheit gewählt werden kann (Abschnitt 5.3). Wenn ein Knoten keine k lokalen Nachbarschaftsknoten finden kann, so kann er seine Suche ausdehnen oder auf neue Knoten warten, um sie dann in seine Nachbarschaft einzubeziehen.

5. Der lokale Zertifizierungsdienst Dieser Abschnitt beschreibt die Architektur des lokalen Zertifizierungsdiensts für mobile Ad-hoc-Netzwerke. Im Folgenden werden die verwendeten Konzepte, der Ablauf des Authentifizierungsmodells und abschließend das Zertifizierungsprotokoll im Detail vorgestellt.

11

5.1. Verwendete Konzepte beim Zertifizierungsdienst RSA: Der hier vorgestellte Zertifizierungsdienst basiert auf RSA, welches gegenwärtig das geläufigste Public-Key-Kryptographieverfahren ist. Jeder Netzwerkknoten Knoten i besitzt eine von Null verschiedene ID vi, sowie ein persönliches RSA-Schlüsselpaar {ski, pki}, wobei ski der private und pki der öffentliche Schlüssel ist. Das persönliche RSA-Schlüsselpaar wird von vi zum verschlüsselten Nachrichtenaustausch, sowie zum Generieren von Signaturen verwendet. Polynomielles Secret-Sharing: Das RSA-Schlüsselpaar der CA wird als {SK, PK} angegeben, dabei ist SK der private und PK der öffentliche Systemschlüssel. SK wird benutzt, um die Zertifikate der Netzwerkknoten zu unterschreiben. Durch das von Shamir vorgestellte polynomielle Secret-Sharing wird der geheime Systemschlüssel SK unter allen n Netzwerkknoten entsprechend einem zufällig gewählten Polynom vom Grad k-1 aufgeteilt. Dadurch besitzt jeder Knoten vi einen Anteil

ivP des geteilten Geheimnisses. Eine Gruppe von k Knoten kann mit ihren k Koeffizienten SK durch Lagrange-Interpolation wiedergewinnen und somit zusammen die Rolle einer CA übernehmen. Zu beachten ist jedoch, dass SK keinem Knoten als Ganzes bekannt ist, noch von ihm rekonstruierbar ist. Jeder Knoten vi kennt nur seinen eigenen Anteil

ivP . Authentifizierung durch Zertifikate: Bei einer auf RSA basierenden Authentifizierung muss ein Knoten vi zum einen den Beweis erbringen, dass er im Besitz des geheimen Schlüssel ski ist und zum anderem muss er beweisen, das pki auch wirklich sein öffentlicher Schlüssel ist. Der Beweis, dass vi im Besitz des geheimen Schlüssel ski ist, kann durch ein Challenge-Response-Mechanismus realisiert werden. Der Beweis, dass pki der öffentliche Schlüssel von vi ist, wird durch ein unterschriebenes Zertifikat realisiert. Um seinen persönlichen Schlüssel zu zertifizieren, besitzt jeder Knoten vi also ein Zertifikat certi = < vi, pki, T >, das wie folgt zu interpretieren ist: „Es wird bescheinigt, dass der persönliche öffentliche Schlüssel von vi pki während des Zeitintervalls [T; T + Tcert] ist.“ Ein Zertifikat ist nur dann gültig, wenn es durch den geheimen Systemschlüssel SK unterschrieben ist: CERTi := (certi)SK. Der wohlbekannte öffentliche Systemschlüssel PK wird dazu benutzt, ein mit SK unterschriebenes Zertifikat zu überprüfen: certi = (CERTi)PK. Ein gültiges Zertifikat, stellt also sicher, das pki der öffentliche Schlüssel von vi ist.

5.2. Der Ablauf des Zertifizierungsdiensts Wie in einem auf Public-Key basierenden System, beinhaltet auch der hier vorgestellte Zertifizierungsdienst ein Erstellen, Erneuern und Entziehen von Zertifikaten. Das Erstellen von Zertifikaten: Jeder neue Knoten vi, der sich mit dem Netzwerk verbinden will, benötigt ein Anfangszertifikat, sowie seinen Anteil

ivP des geteilten Geheimnisses. Die Herausgabe des Anfangszertifikates ist ein wichtiger Sicherheitspunkt, denn sobald ein Knoten sein Anfangszertifikat erhält, besitzt er das Vertrauen des ganzen Netzwerks. Die Herausgabe des Anfangszertifikates und des Anteils des geteilten Geheimnisses kann auf zwei Arten realisiert werden. Die erste Möglichkeit ist, dass ein Knoten sein Anfangszertifikat von einer Offline-Autorität erhält, nachdem sie die Identität durch äußerliche Merkmale überprüft hat. Die zweite Möglichkeit ist, dass eine Gruppe von k Netzwerkknoten dazu benutzt wird, dem neuen Knoten ein Anfangszertifikat auszustellen. Der Einfachheit halber wird hier die erste Möglichkeit angenommen.

12

Das Entziehen von Zertifikaten: Jeder Netzwerkknoten vi besitzt zwei Mechanismen, mit deren Hilfe er mögliche Angreifer im Netz ausfindig machen kann. Der erste Mechanismus ist ein Intrusion-Detection-System. Mit Hilfe dieses Systems ist vi in der Lage, einen potentiellen Angreifer vj in seiner lokalen One-hop-Nachbarschaft zu lokalisieren. Der zweite Mechanismus ist die Certificate Revocation List (CRL), die im Folgenden näher erläutert wird. Jeder Eintrag in vi’s CRL besteht aus einer Knoten-ID vj und einer Liste von Netzwerkknoten, die den Knoten vj nicht mehr für vertrauenswürdig halten. Wenn diese so genannte Anklägerliste des Knotens vj mindestens einen und höchstens k-1 legitime Ankläger enthält, wird vj von vi als „verdächtig“ gekennzeichnet. Enthält die Anklägerliste mehr als k-1 Ankläger, so wird vj als ein Angreifer angesehen und als „überführt“ markiert. Der Parameter k ist also der Schwellwert, bei dem ein Knoten als überführt markiert wird. Durch die Wahl von k als Schwellwert wird sichergestellt, dass ein legitimer Knoten nicht von einem Angreifer überführt werden kann. Es existieren zwei Szenarien, bei denen ein Knoten als überführt gekennzeichnet wird. Zum einen, wenn vi durch Intrusion-Detection einen seiner Nachbarn als ein Angreifer bestimmt. In diesem Fall nimmt vi den Knoten in seine CRL auf und kennzeichnet ihn direkt als überführt. Anschließend propagiert vi eine unterschriebene Anklage gegen den Knoten. Zum anderen, wenn vi eine Anklage gegen einen Knoten empfängt. In diesem Fall überprüft vi, ob der Ankläger in seiner CRL als ein überführter Knoten gekennzeichnet ist. Ist dies der Fall, so wird die Anklage als ein böswilliger Akt angesehen und fallen gelassen. Anderenfalls aktualisiert vi seine CRL, indem er den Ankläger in die Anklägerliste des Knotens einfügt. Der angeklagte Knoten wird als überführt gekennzeichnet, wenn die Anzahl der Ankläger k erreicht. Ist ein Knoten als überführt gekennzeichnet worden, so löscht vi den Knoten aus allen Anklägerlisten. Andererseits wird ein überführter Knoten wieder als verdächtig gekennzeichnet, wenn die Anzahl der Ankläger wieder kleiner als k ist. Das Erneuern von Zertifikaten: Wie bereits erwähnt, besitzt jeder Netzwerkknoten ein mit SK unterschriebenes Zertifikat. Knoten ohne gültige Zertifikate werden als Angreifer betrachtet und von den Netzwerkressourcen wie Packet Forwarding und Routing ausgeschlossen. Wenn ein mobiler Knoten sich zu einem neuen Standort bewegt, findet ein Zertifikatsaustausch mit seinen Nachbarn statt. Da die Zertifikate mit einem Zeitstempel versehen sind, muss ein Knoten vor Ablauf seines bisherigen Zertifikates ein neues erhalten, um nicht vom Netzwerk getrennt zu werden. Ein Knoten vi beantragt den Zertifizierungsdienst, indem er eine Broadcast-Anfrage an seine One-hop-Nachbarschaft sendet (Abbildung 3).

Abbildung 3: Zertifizierungsanfrage

Beim Empfang der von vi initiierten Zertifizierungsanfrage überprüft ein Knoten vj seine Aufzeichnungen. Diese Aufzeichnungen bestehen einerseits aus den Intrusion-Detection-Daten und andererseits aus der CRL. Ist vi nicht in vj’s Aufzeichnungen vermerkt, so

13

betrachtet vj ihn als einen legitimen Knoten und sendet an vi ein Teil-Zertifikat jvCERT

zurück. Ist vi vermerkt, so verwirft vj die Anfrage. Durch Sammeln von k Teil-Zertifikaten kann vi sich ein neues vollständiges Zertifikat generieren, genau so als ob er es von einem CA-Server direkt erhalten hätte. Ein Angreifer, der von seinen Nachbarn entdeckt worden ist, ist nicht in der Lage sein Zertifikat zu erneuern. Er wird spätestens nach Ablauf seines gegenwärtigen Zertifikates vom Netzwerk getrennt. Im vorgestellten Zertifizierungsdienst steht ein gültiges Zertifikat für das Vertrauen von k Knoten. Einerseits wird einem Knoten mit gültigem Zertifikat global vertraut, andererseits wird einem Knoten ohne Zertifikat der Zugriff auf Netzwerkressourcen verweigert. Jeder Netzwerkknoten trägt zum allgemeinen Vertrauensmanagement bei, indem er seine Nachbarknoten überwacht und zertifiziert. Hierdurch wird das lokale Vertrauensmodell, wie es in Abschnitt 4.3. beschrieben wurde, realisiert. Angreifer werden, sobald sie entdeckt wurden, vom Netzwerk isoliert.

5.3. Die Parameter des Zertifizierungsdienst Übertragungsreichweite einer unterschriebenen Anklage: Wie im vorherigen Abschnitt erläutert, propagiert ein Knoten eine unterschriebene Anklage, sobald er durch Intrusion-Detection einen seiner Nachbarn als einen Angreifer identifiziert. Dabei ist die Reichweite der unterschriebenen Anklage ein wichtiger Parameter. Eine zu große Reichweite verursacht einen übermäßigen Kommunikations-Overhead, während es bei einer zu kleinen Reichweite nicht möglich ist, den Angreifer zu überführen. Die Reichweite der unterschriebenen Anklage sollte so groß sein, dass es dem Angreifer nicht möglich ist, das Gebiet, in dem er als überführt markiert worden ist, zu verlassen, bevor sein gegenwärtiges Zertifikat abläuft. In der Praxis wird die Reichweite durch das TTL-Feld 5 im IP-Header der Anklagedatenpakete eingestellt. Eine Möglichkeit den TTL-Wert zu wählen, basiert auf der Lebensdauer der Zertifikate Tcert, der drahtlosen Übertragungsreichweite D und der maximalen Knotengeschwindigkeit Smax. Um sicherzustellen, dass es einem Angreifer nicht möglich ist, das Gebiet, in dem er als überführt markiert worden ist, zu verlassen, bevor sein gegenwärtiges Zertifikat abläuft, sollte für den TTL-Wert folgendes gelten:

⋅

≥D

STTTL cert max2

Um die Komplexität der CRL zu reduzieren, kann ein Knoten eine Anklage nach Tcert aus seiner CRL entfernen. Möglich wird dies durch die Tatsache, dass das Zertifikat eines überführten Knoten nach Tcert abläuft und er somit vom Netzwerk getrennt wird. Parameter k und Tcert: Der wichtigste Parameter der Architektur ist k. Eine Implementierung des Zertifizierungsdienstes mit einem großem k kann zwar mächtigen Angreifern widerstehen, jedoch ist die Verfügbarkeit des Dienstes schlecht. Systeme mit einem kleinen k zeigen eine hohe Dienstverfügbarkeit, andererseits ist es für einen möglichen Angreifer leicht, sein gegenwärtiges Zertifikat zu erneuern. Im Allgemeinen charakterisiert der Parameter k den Kompromiss zwischen Dienstverfügbarkeit und Systemrobustheit. Durch den Parameter Tcert kann der Overhead zwischen dem Erneuern und dem Entziehen von Zertifikaten balancieren werden. Ein kleines Tcert verursacht nur einen geringen Overhead

5 TTL ist definiert als Time to live: Die maximale Anzahl Hops, die ein Datenpaket durchlaufen darf, bevor es verworfen wird.

14

beim Propagieren der Anklage, sowie beim Unterhalt der CRL. Jedoch ist der Overhead beim Erneuern der Zertifikate proportional größer. Folglich ist bei einem steigenden Tcert der Overhead fallend.

5.4. Das Zertifizierungsprotokoll Wie in Abschnitt 5.2. erläutert worden ist, muss ein Knoten vi sein Zertifikat periodisch erneuern, um nicht vom Netzwerk getrennt zu werden. Eine Möglichkeit wäre, dass eine Gruppe von k Nachbarknoten ihre Anteile

jvP an vi sendet. Anschließend wäre vi in der Lage,

SK durch Lagrange-Interpolation zu berechen und sein Zertifikat erneuern. Diese naive Lösung ist jedoch nicht praktikabel, da der Knoten vi nach dem Erneuern seines Zertifikates im Besitz des geheimen Schlüssels SK ist. Anstelle der Enthüllung des privaten Schlüssels der CA, wird ein besserer Sicherheitsmechanismus für den Zertifizierungsdienst gebraucht, der ohne Kenntnis von SK auskommt. Die hier verfolgte Strategie basiert auf Teil-Zertifikate. Ein Knoten vi beantragt den Zertifizierungsdienst, indem er eine Broadcast-Anfrage an seine One-hop-Nachbarschaft sendet. Ein benachbarter Knoten vj, der die Anfrage empfängt und beschließt, sie zu beantworten, sendet ein Teil-Zertifikat an vi zurück. Nach dem Erhalten von mindestens k solcher Teil-Zertifikate, kann der Knoten vi sich ein neues vollständiges Zertifikat generieren. Dieser Ansatz kommt ohne ein explizites SK aus. SK ist also von keinem Knoten als Ganzes rekonstruierbar. Diese Idee wird durch das im Folgenden beschriebene Protokoll realisiert: Während der Anfangsinitialisierung des Netzwerks generiert die Offline-Autorität das RSA-Schlüsselpaar { >=< mdSK , , >=< mePK , } der CA und wählt ein zufälliges Polynom

111 ...)( −

−+++= kk xaxadxf von Grad k-1 aus, so dass das geteilte Geheimnis df =)0( ist.

Anschließend erhält jeder Knoten vi seinen Anteil ( )mvfP ivimod)(= des geteilten

Geheimnisses, sowie sein Anfangszertifikat CERTi := (certi)SK. Ein Knoten führt nun das Zertifizierungsprotokoll aus, um sein Zertifikat zu erneuern. Algorithmus 2: Zertifizierungsprotokoll

1. Knoten vi generiert sich ein neues Zertifikat certi = < vi, pki, T > und schickt es an alle

Koten vj in seiner Nachbarschaft.

2. Ein Knoten vj, der die Zertifizierungsanfrage erhält und beschließt sie zu beantworten, berechnet ( ) mcertCERT jv

j

Pv mod= und sendet das Teil-Zertifikat

jvCERT an vi

zurück.

3. Nach Erhalten von mindestens k solcher Teil-Zertifikate, wählt vi k von ihnen aus. Ohne Einschränkung der Allgemeinheit seien diese },...,{

1 kvv CERTCERT . Anschließend konvertiert vi jedes ausgewählte Teil-Zertifikat:

( ) mCERTCERT jv

jj

lvv mod' )0(= , wobei ∏ ≠= −

=k

jrrjr

rv m

vvv

lj ,1

mod)0( die Lagrange-

Koeffizienten sind.

15

4. vi multipliziert alle Teilergebnisse zusammen: mCERTCERTk

r vi rmod''

1∏ == .

5. Schlussendlich benutzt Knoten vi folgenden Algorithmus, um aus CERTi´ sein neues

Zertifikat CERTi = (certi)SK zu erhalten.

Eingabe: CERTi´

Z := (certi)-m mod m; j := 0; Y := CERTi´; while j < k do Y := Y Z ⋅ mod n; j := j + 1; if (certi = Ye mod m) then break while; end if; end while;

Ausgabe: Y = CERTi Lemma 2: Der obige Algorithmus generiert für einen Knoten vi ein korrektes neues Zertifikat CERTi. Beweis: Die Korrektheit des Algorithmus lässt sich beweisen, indem die einzelnen Schritte zusammengefasst werden:

( )( )

( )

ktcertCERT

cert

olationnge-Interpnach Lagramcert

m cert

cert

CERT

CERTCERT

mtii

SKmti

mSKi

)(lPi

k

j

lPi

k

j

lv

k

j vi

k

j jvjv

jvjv

jv

j

j

<≤⋅=

=

=

∑≡

≡

≡

≡

⋅

+⋅

⋅

=

⋅

=

=

=

∏∏∏

0mit )(

)(

)( mod)(

mod

''

mod

0

1

)0(

1

)0(

1

1

CERTi´ und CERTi unterscheiden sich nur durch einen konstanten Faktor, der in Schritt 5 des Algorithmus eliminiert wird. 9 Beispiel 2: Zertifizierungsprotokoll Der Ablauf des Zertifizierungsprotokolls soll an einem Beispiel im verdeutlicht werden. Sei { >=< 55,23SK , >=< 55,7PK } das RSA-Schlüsselpaar der CA. Das Geheimnis ist also S := 23, welches unter n := 4 Teilnehmern aufteilt wird, so dass jeweils k := 3 von ihnen S rekonstruieren können. Für den Schwellwert k = 3 wird ein Polynom zweiten Grades benötigt. Der Koeffizient a0 := S = 23 steht bereits fest. Zufällig werden die Koeffizienten a1:= 2 und a2 := 4 gewählt. Das erhaltene Polynom ist also: 2324)( 2 ++= xxxf .

16

Es ergeben sich für die vier Teilnehmer folgende Anteile:

Teilnehmer vi Anteil ( )mvfP ivimod)(=

1 29 2 43 3 10 4 40

Angenommen, Teilnehmer v1 will sein Zertifikat cert1 := 17 erneuern lassen. Er sendet sein Zertifikat an v2, v3 und v4. Diese führen Schritt 2 des Protokolls aus: CERT2 := 1743 mod 55 = 18 CERT3 := 1710 mod 55 = 34 CERT4 := 1740 mod 55 = 1 Anschließend führt Teilnehmer v1 die Schritte 3 und 4 des Protokolls aus: Schritt 3: l2(0) := 12 12 −⋅ mod 55 = 6 l3(0) := 8 154 −⋅ mod 55 = 47 l4(0) := 6 12 −⋅ mod 55 = 3 CERT2’ := 186 mod 55 = 4 CERT3’ := 3447 mod 55 = 34 CERT4’ := 13 mod 55 = 1 Schritt 4: CERT1’ := 134 4 ⋅⋅ mod 55 = 26 Schlussendlich konvertiert v1 im Schritt 5 noch CERT1’ und erhält sein neues Zertifikat CERT1 = 18. Jeder Knoten vj kann nun mit Hilfe des öffentlichen Schlüssel PK der CA das Zertifikat von v1 überprüfen:

cert1 = (CERT1)PK = 187 mod 55 = 17

6. Parallel-Share-Update Der folgende Abschnitt beschreibt kurz die Idee des Parallel-Share-Update. Um das grundlegende Konzept besser verstehen zu können, soll an dieser Stelle noch einmal auf das Angreifermodell eingegangen werden. Wie in Abschnitt 4.2 bereits erläutert, ist es einem Angreifer nicht möglich, k oder mehr Knoten gleichzeitig zu kompromittieren. Jedoch wurde einem Angreifer erlaubt, seine Ziele in jedem Zeitabschnitt neu zu definieren. Zum Beispiel kann ein Angreifer in Zeitperiode t k-1 Netzwerkknoten kompromittieren und in der nächsten Zeitperiode t+1 wiederum k-1 Knoten. Nach zwei Zeitperioden wäre ein potentieller Angreifer also in der Lage, den geheimen Schlüssel SK der CA durch Lagrange-Interpolation zu berechen. Durch Parallel-Share-Updates soll genau dies verhindert werden. Die grundlegende Idee des Parallel-Share-Updates ist, dass die Anteile

ivP des geteilten Geheimnisses eines jeden Knoten vi im Netzwerk periodisch erneuert werden.

17

Allgemein lässt sich das Update-Verfahren in drei Phasen einteilen:

o Phase 1: Das verteilte Generieren eines Share-Update-Polynoms uf : Ein Knoten vi initiiert ein Update mit einer Wahrscheinlichkeit von n̂1 , wobei n̂ eine Schätzung der Anzahl der gesamten Netzwerkknoten ist. Dies stellt sicher, dass statistisch gesehen nur ein Knoten den Updateprozess initiiert. Sobald ein Knoten vi beschließt, ein Update durchzuführen, lokalisiert er eine Gruppe von k Nachbarknoten und generiert mit ihnen zusammen ein verschlüsseltes zufälliges Updatepolynom ( )

PKk

kuuu xaxaxf 11,1, ...)( −

−++= mit 0)0( =uf . Abschließend benutzen die k Knoten

ihre polynomiellen Anteile von SK, um das verschlüsselte uf zu unterschreiben. Durch diese Unterschrift wird ein Angreifer daran gehindert, eine Gruppe von k Knoten zu emulieren, um so ein Share-Update-Polynom zu fälschen.

o Phase 2: Das Propagieren des Updatepolynoms: Der Knoten vi propagiert das

verschlüsselte Updatepolynom ( )PKuf inklusive der Unterschrift im Netzwerk. Durch das Propagieren des Updatepolynoms kann sichergestellt werden, dass jeder Knoten im Netzwerk das Updatepolynom mindestens einmal empfängt.

o Phase 3: Das verteilte Auswerten des Share-Update-Polynoms uf : Nach Erhalt des

verschlüsselten Share-Update-Polynoms ( )PKuf kontaktiert jeder Knoten vi k seiner Nachbarn, um es gemeinsam zu entschlüsseln. Genau wie beim lokalen Zertifizierungsdienst schickt jeder Nachbarschaftsknoten sein Teil-Update an vi zurück. Dieser fügt nun k Teil-Updates zusammen, um uf wiederherzustellen. Abschließend kann nun vi seinen Anteil berechnen: )(:, iuvu vfP

i= .

Nach Abschluss der obigen drei Phasen kann jeder Netzwerkknoten vi seinen Anteil

ivP des geteilten Geheimnisses geeignet aktualisieren. Durch das hier vorgestellte Verfahren ist es einem Angreifer nicht mehr möglich, den geheimen Schlüssel SK der CA durch Lagrange-Interpolation zu berechen. Selbst dann nicht, wenn er in jedem Zeitabschnitt verschiedene Knoten kompromittiert. Durch Parallel-Share-Updates ist die Architektur des Zertifizierungsdienstes also robust gegen den in Abschnitt 4.2 definierten Angreifer. Detaillierte Algorithmen, Kommunikationsprotokolle und Beweise sind [11] und [12] zu finden.

7. Implementierung und Leistungsbewertung Die vorgestellte verteilte Authentifizierungsmethode ist unter Unix mit Hilfe des Netzwerksimulators NS-2 [13] bezüglich Berechnungsaufwand, Skalierbarkeit, Dienstverfügbarkeit, Mobilität und Übertragungsfehler untersucht worden. In den folgenden Abschnitten werden die Ergebnisse der Simulation vorgestellt.

7.1. Bewertung des Berechnungsaufwands In diesem Abschnitt sollen der Berechnungsaufwand der Kommunikationsprotokolle bewertet werden. Hierzu wird die Auswirkung der RSA-Schlüssellänge, sowie die Auswirkung des Parameters k auf die Rechenzeit der Kommunikationsprotokolle betrachtet.

18

Die Simulation wurde auf Rechnern mit drei unterschiedlichen SPECint_rate95 Werten durchgeführt: 10, 107 und 202 [14]. Dies entspricht der Leistung eines Pentium 75, Pentium II 300 und eines Pentium III 500. Die Messungen zeigen, dass die Performance stark von der Leistung des verwendeten Rechners abhängt. Zum Beispiel braucht ein Pentium 75 über 5 Sekunden länger für den Zertifizierungsdienst als ein Pentium III 500 bei einer Schlüssellänge von 1024 oder 1280 Bits und einer Gruppengröße von k ≤ 10. Die Auswirkung der RSA-Schlüssellänge: Abbildung 4 zeigt6, dass die standardmäßige RSA-Unterschrift fast 2,5-mal schneller ist, als die Partial Certificate Computation (PCC). Der Grund dafür ist, dass die standardmäßige RSA-Unterschrift eine Optimierungstechnik benutzt, die nicht ohne die Kenntnis der zwei Primfaktoren des RSA-Modulo anwendbar ist. In der gleichen Abbildung ist auch zu erkennen, dass ein kleiner persönlicher Schlüssel (z.B. 768 Bits) die Bearbeitungszeit auf 1,3 Sekunden reduzieren kann.

Abbildung 4: Die Auswirkung der RSA

Schlüssellänge auf den Zertifizierungsdienst Abbildung 5: Die Auswirkung des

Parameters k auf den Zertifizierungsdienst Die Auswirkung des Parameters k: Die Abbildung 5 zeigt, wie die Wahl von k die Bearbeitungszeit beeinflusst. Es ist ersichtlich, dass der Parameter k nur eine geringe Auswirkung auf die Bearbeitungszeit für den Zertifizierungsdienst hat. Dies folgt aus der Tatsache, dass die Multiplikation der k Teil-Zertifikate eine billige Rechenoperation ist.

7.2. Bewertung der Kommunikationsprotokolle In diesem Abschnitt sollen die Kommunikationsprotokolle in Bezug auf Skalierbarkeit, Dienstverfügbarkeit, Mobilität und Übertragungsfehler bewertet werden. Bevor jedoch auf die Simulationsergebnisse eingegangen wird, müssen einige Begriffe definiert werden:

o Success-Ratio misst das Verhältnis zwischen der Anzahl der erfolgreich ausgestellten und angefragten Zertifikate.

o Average-Delay misst die durchschnittliche Latenz eines Knoten bei der Beantwortung

einer Zertifizierungsanfrage.

o Overhead misst den Kommunikations-Overhead in Bytes. Es wurde ein Netzwerk variabler Größe (30 bis 100 Knoten) simuliert. Die Knoten-geschwindigkeit variiert zwischen 1 m/s und 20 m/s. Der Parameter k wird, wenn nicht anders

6 In den Diagrammen zeigt Speed den SPECint_rate95 Wert an. RSA steht für die standardmäßige RSA-Unterschrift. PCC steht für Partial Certificate Computation (Algorithmus 2: Schritt 2). Combine steht für die Schritte 3 bis 5 des Algorithmus 2.

19

angegeben, auf 5 gesetzt. Einzige Ausnahme bildet die Netzwerksimulation mit 30 Knoten, hier besitzt k den Wert 3.

7.2.1. Zertifizierungsdienst Skalierbarkeit und Mobilität: Die Skalierbarkeit des Zertifizierungsdienst lässt sich durch Variation der Netzgröße bewerten. Abbildung 6 zeigt die Success-Ratio des Zertifizierungsdienstes. Es ist ersichtlich, dass die Success-Ratio immer über 85% liegt und bei höherer Knotengeschwindigkeit (mehr als 1 m/s) sogar fast 100% beträgt. Beträgt die Knotenmobilität 1 m/s, so ist die Success-Ratio nur etwa 85%. Der Grund hierfür ist, dass ein Knoten bei niedriger Knotendichte und niedriger Knotengeschwindigkeit Schwierigkeiten hat, seine k Nachbarknoten für den Zertifizierungsdienst zu lokalisieren. Die Ergebnisse zeigen, dass die Knotenmobilität die Dienstverfügbarkeit verbessert.

Abbildung 6: Zertifizierungsdienst: Success-

Ratio in Abhängigkeit der Kontenanzahl Abbildung 7: Zertifizierungsdienst: Success-Ratio in Abhängigkeit von k

Parameter k: Abbildung 7 zeigt die Success-Ratio in Abhängigkeit von k. Es ist zu erkennen, dass die Success-Ratio unabhängig von der Größe der Gruppe ist und nahe zu 100% beträgt. Im Wesentlichen bedeutet dies, dass k erhöht werden kann und somit die Sicherheit des Netzwerks steigt, ohne dabei auf Effektivität zu verzichten. Kommunikations-Overhead: Abbildung 8 zeigt den Kommunikations-Overhead in KBytes in Bezug auf die Knotenanzahl im Netzwerk. Der Overhead wächst linear mit der Knotenanzahl, das heißt, dass der Overhead pro Knoten unverändert bleibt und somit mit der Netzgröße skaliert. Hinzu kommt, dass der Kommunikations-Overhead fast unabhängig in Bezug auf die Knotengeschwindigkeit ist.

Abbildung 8: Zertifizierungsdienst:

Overhead in Abhängigkeit der Kontenanzahl Abbildung 9: Zertifizierungsdienst: Success-Ratio

in Abhängigkeit der Kontenanzahl, Fehlerw’keit 10%

20

Übertragungsfehler: Die Auswirkung von Übertragungsfehlern auf die Protokolle wird in Abbildungen 9 und 10 dargestellt. Die Knotengeschwindigkeit beträgt 5 m/s, der Übertragungsfehler 10%. Im Folgenden wurde der hier vorgestellte verteilte Authentifizierungsdienst einem auf CA-Server basierten zentralisierten Ansatz gegenübergestellt. Die Abbildungen zeigen einerseits, dass der verteilte Authentifizierungsdienst robust gegenüber Übertragungsfehler ist und andererseits auch, dass der zentralisierte Ansatz eine deutlich schlechtere Performance hat.

Abbildung 10: Zertifizierungsdienst: Bearbeitungszeit in Abhängigkeit der Kontenanzahl, Fehlerw’keit 10%

Abbildung 11: Parallel-Share-Update: Bearbeitungszeit in Funktion der Kontenanzahl

7.2.2. Parallel-Share-Update Skalierbarkeit und Mobilität: Abbildung 11 zeigt die durchschnittliche Rechenzeit, die ein Knoten braucht, um seinen Anteil des Geheimnisses zu aktualisieren. Es ist ersichtlich, dass die Bearbeitungszeit beim Erhöhen der Knotenanzahl fast konstant bleibt und dass auch die Knotenbeweglichkeit nur eine geringe Auswirkung hat. Diese Resultate zeigen, dass das hier vorgestellte Authentifizierungsmodell skalierbar in Bezug auf die Netzwerkgröße ist. Die Abbildungen 12 bis 14 stellen Details des Parallel-Share-Update-Prozesses dar. Die Abbildungen stellen den Prozentsatz der Knoten, die ihr Update vollendet haben, in Abhängigkeit der Zeit dar. Sie zeigen die kumulative Verteilung des Updateprozesses. Es ist interessant zu beobachten, dass im größten Netzwerk der Updateprozess am schnellsten vollendet ist. Zum Beispiel in einem Netzwerk mit 60 Knoten und einer Knotengeschwindigkeit von 15 m/s vollenden 90% der Knoten ihr Update innerhalb von 550 Sekunden, während sie in einem Netzwerk mit 100 Knoten nur etwa 300 Sekunden brauchen. Die Abbildungen zeigen auch, dass wenn die Netzwerkgröße ansteigt, die Auswirkung der Knotengeschwindigkeit sinkt.

Abbildung 12: Kumulative Verteilung

des Updateprozess, 60 Knoten Abbildung 13: Kumulative Verteilung

des Updateprozess, 70 Knoten

21

Kommunikations-Overhead: Abbildung 15 zeigt den Kommunikations-Overhead in KBytes in Bezug auf die Knotenanzahl im Netzwerk. Einerseits ist zuerkennt, dass der Kommunikations-Overhead linear mit der Knotenanzahl ansteigt. Anderseits ist jedoch auch zuerkennt, dass bei hohen Knotengeschwindigkeiten (über 15 m/s) der Kommunikations-Overhead nicht mehr linear wächst, da nun mehrere Kommunikationsrunden nötig werden.

Abbildung 14: Kumulative Verteilung

des Updateprozess, 100 Knoten Abbildung 15: Parallel-Share-Update:

Overhead in Abhängigkeit der Kontenanzahl

8. Zusammenfassung Zum Abschluss sollen noch mal die wichtigsten Punkte des vorgestellten Zertifizierungsdienstes für mobile Ad-hoc-Netze zusammengefasst werden. Einleitend wurden die allgemeinen Eigenschaften eines mobilen Ad-hoc-Netzwerks vorgestellt. Daraufhin konnte gezeigt werden, dass die in Praxis und Literatur bekannten konventionellen zentralisierten und verteilten Authentifizierungsmethoden sich nicht für mobile Ad-hoc-Netzwerke eignen. Infolgedessen wurde eine neue skalierbare, verteilte Authentifizierungsmethode vorgestellt. Die grundlegende Idee war, den geheimen Systemschlüssel SK der CA mit Hilfe des polynomiellen Secret-Sharing unter allen n Netzwerkknoten aufzuteilen. Mit Hilfe dieses Schlüssels konnte sich ein Knoten sein RSA-Schlüsselpaar zertifizieren lassen. Weiterhin wurde das Parallel-Share-Update-Prinzip vor. Die Idee der Updates war, die Anteile des geteilten Geheimnisses eines jeden Knoten im Netzwerk periodisch zu erneuern. Durch die Parallel-Share-Updates war das Authentifizierungsmodell in der Lage mächtigeren Angreifern zu widerstehen. Abschließend wurde eine Leistungsbewertung der Kommunikationsprotokolle durchgeführt. Anhand der Simulation konnte gezeigt werden, dass das vorgestellte lokale Zertifizierungsmodell den hohen Ansprüchen eines mobilen Ad-hoc-Netzwerkes entspricht.

22

Anhang: Interpolation nach Lagrange Die Interpolationsmethode nach Lagrange hat hauptsächlich theoretische Bedeutung, in der Praxis wird meist das Verfahren nach Newton bevorzugt. Da aber in der Literatur im Zusammenhang mit der Secret-Sharing-Methode von Shamir auch meist die Interpolationsmethode nach Lagrange erwähnt wird, soll diese kurz beschrieben werden. Allgemein lässt sich das Problem der Polynominterpolation wie folgt formalisieren:

o Gegeben: n verschiedene Stützstellen (x0, y0), (x1, y1), …, (xn-1, yn-1).

o Gesucht: ein Polynom p(x) niedrigsten Grades mit der Eigenschaft p(xi) = yi, }1,...,0{ −∈∀ ni

Lagrange setzt das gesuchte Polynom p(x) folgendermaßen fest:

∑ ==+++=

n

i iinn xLyxLyxLyxLyxp01100 )()(...)()()(

mit denen wie folgt definierten Lagrangeschen Grundpolynomen:

∏≠=+−

+−

−−

=−−−−−

−−−−−=

n

kii ik

i

nkkkkkkk

nkkk xx

xxxxxxxxxxxx

xxxxxxxxxxxL

,01110

1110

))...()()...()(())...()()...()((

)(

Der Sinn dieser Festlegung wird durch folgende Überlegung offensichtlich: Der Zähler stellt ein Produkt aus den Faktoren (x-x0), (x-x1),..., (x-xn) mit Ausnahme des Faktors (x-xk) dar, im Nenner lauten die Faktoren (xk-x0), (xk-x1),..., (xk-xn) mit Ausnahme von (xk-xk). Dadurch nimmt Lk(x) an der Stelle xk den Wert 1 an und an allen anderen Stützstellen den Wert 0. Somit interpoliert das Polynom p(x) tatsächlich die Punkte P0, P1, …, Pn-1.

23

Literaturverzeichnis [1] E. M. Royer and C-K Toh, A Review of Current Routing Protocols for Ad-hoc-Mobile

Wireless Networks, IEEE Personal Communications, April 1999. [2] J. Macker and S. Corson, Mobile Ad-hoc-Networking: Routing protocol performance

issues and evaluation considerations, Internet RFC 2501, January 1999. [3] A. Aresenault and S. Turner, Internet X.509 public key infrastructure, draft-ietf-pkix-

roadmap-06.txt, 2000. [4] R. Perlman, An overview of PKI trust models, IEEE Network, p. 38-43, vol.13, (no.6)

Nov.-Dec. 1999. [5] D. B. Johnson and D. A. Maltz, Dynamic source routing in Ad-hoc-wireless networks,

Mobile Computing, vol 353, 1996. [6] A. Abdul-Rahman, The PGP trust model, EDI-Forum: the Journal of Electronic

Commerce, Apr. 1997. [7] S. Garfinkel, PGP: Pretty Good Privacy, O’Reilly & Associates Inc., USA, 1995. [8] A. Shamir, How to share a secret, Communications of ACM, 1979. [9] B. Schneier, Angewandte Kryptographie, Addison-Wesley, Mai 1996. [10] R.L. Rivest, A. Shamir, L.M. Adleman, A method for obtaining digital signatures and

Public-Key cryptosystems, Communications of the ACM, Vol. 21, 120-126, 1978. [11] A. Herzberg, S. Jarecki, H. Krawczyk, and M. Yung, Proactive secret sharing, Extended

abstract, 1995. [12] H. Luo and S. Lu, Ubiquitous and robust authentication services for ad hoc wireless

networks, UCLA Computer Science Technical Report 200030, Oct. 2000. [13] NS-2 (The Network Simulator), http://www.isi.edu/nsnam/ns/. [14] Standard Performance Evaluation Corporation, http://www.specbench.org.