Secure group key agreement [Elektronische Ressource] / von Michael Steiner
218 Pages
English

Secure group key agreement [Elektronische Ressource] / von Michael Steiner

-

Downloading requires you to have access to the YouScribe library
Learn all about the services we offer

Description

SSAATRIASVRSecure Group Key AgreementDissertation zur Erlangung des GradesDoktor der Ingenieurwissenschaften (Dr. Ing.)der Naturwissenschaftlich-Technischen Fakult¨at Ider Universita¨t des SaarlandesvonMichael SteinerGutachter:Prof. Dr. Birgit PfitzmannProf. Dr. Gene TsudikDekan:Prof. Dr. Rainer Schulze-Pillot-ZiemenEinreichung:20 Dezember, 2001Promotions-Kolloquium:15. Marz, 2002¨Saarbrucken, 2002¨IEEVNISNIUSiiAbstractAs a result of the increased popularity of group-oriented applications andprotocols, group communication occurs in many different settings: fromnetwork multicasting to application layer tele- and video-conferencing. Re-gardless of the application environment, security services are necessary toprovide communication privacy and integrity.This thesis considers the problem of key management in a special classof groups, namely, dynamic peer groups. Key management, especially ina group setting, is the corner stone for all other security services. Dy-namic peer groups require not only initial key agreement but also auxiliarykey agreement operations such as member addition, member exclusion andgroup fusion. We discuss all group key agreement operations and present aconcrete protocol suite, CLIQUES, which offers all of these operations.

Subjects

Informations

Published by
Published 01 January 2004
Reads 10
Language English
Document size 1 MB

S
S
A
A
T
R
I
A
S
V
R
Secure Group Key Agreement
Dissertation zur Erlangung des Grades
Doktor der Ingenieurwissenschaften (Dr. Ing.)
der Naturwissenschaftlich-Technischen Fakult¨at I
der Universita¨t des Saarlandes
von
Michael Steiner
Gutachter:
Prof. Dr. Birgit Pfitzmann
Prof. Dr. Gene Tsudik
Dekan:
Prof. Dr. Rainer Schulze-Pillot-Ziemen
Einreichung:
20 Dezember, 2001
Promotions-Kolloquium:
15. Marz, 2002¨
Saarbrucken, 2002¨
I
E
E
V
N
I
S
N
I
U
SiiAbstract
As a result of the increased popularity of group-oriented applications and
protocols, group communication occurs in many different settings: from
network multicasting to application layer tele- and video-conferencing. Re-
gardless of the application environment, security services are necessary to
provide communication privacy and integrity.
This thesis considers the problem of key management in a special class
of groups, namely, dynamic peer groups. Key management, especially in
a group setting, is the corner stone for all other security services. Dy-
namic peer groups require not only initial key agreement but also auxiliary
key agreement operations such as member addition, member exclusion and
group fusion. We discuss all group key agreement operations and present a
concrete protocol suite, CLIQUES, which offers all of these operations. By
providing the first formal model for group key establishment and investi-
gating carefully the underlying cryptographic assumptions as well as their
relations, we formally prove the security of a subset of the protocols based
on the security of the Decisional Diffie-Hellman assumption; achieving as a
side-effect the first provably secure group key agreement protocol.ivKurzzusammenfassung
Mit der Verbreitung offener Netze, insbesondere des Internets, fand auch
die Gruppenkommunikation eine rasante Verbreitung. Eine Vielzahl heuti-
ger Protokolle sind gruppen-orientiert: angefangen bei Multicast-Diensten
in der Netzwerkschicht bis hin zu Videokonferenzsystemen auf der Anwen-
dungsschicht. Alle diese Dienste haben Sicherheitsanforderungen wie Ver-
traulichkeit und Integritat zu erfullen, die den Einsatz kryptographischer¨ ¨
Techniken und die Verfu¨gbarkeit gemeinsamer kryptographischen Schlu¨ssel
oft unumganglich machen.¨
In der folgenden Doktorarbeit betrachte ich dieses grundlegendste Pro-
blem der Gruppenkommunikation, n¨amlich das Schlu¨sselmanagement, fu¨r
dynamische Gruppen, die sogenannten “Dynamic Peer-Groups”. Die Dy-
namik dieser Gruppen erfordert nicht nur initialen Schlu¨sselaustausch in-
nerhalb einer Gruppe sondern auch sichere und effiziente Verfahren fur die¨
AufnahmeneuerunddenAusschlußalter Gruppenmitglieder.Ichdiskutiere
alle dafur notwendigen Dienste und prasentiere CLIQUES, eine Familie von¨ ¨
Protokollen, die diese Dienste implementiert. Ich gebe erstmalig eine for-
male Definition fur sicheres Gruppen-Schlusselmanagement und beweise die¨ ¨
Sicherheit der genannten Protokolle basierend auf einer kryptographischen
Standardannahme,der “Decisional Diffie-Hellman” Annahme.Diese Sicher-
heitsbetrachtung wirddurch eine detaillierte Untersuchung dieser Annahme
und ihrer Relation zu verwandten Annahmen abgeschlossen.viZusammenfassung
Der zunehmende Bedarf an gruppenorientierten Anwendungen und Proto-
kollen hat in den letzten Jahren zu einer enormen Verbreitung der Grup-
penkommunikation in verschiedensten Bereichen gefuhrt: angefangen bei¨
Multicast-Diensten in der Netzwerkschicht bis hin zu Videokonferenzsyste-
men auf der Anwendungsschicht. Die Gewahrleistung von Sicherheitsgaran-¨
tien wie Vertraulichkeit, Authentizitat und Integritat sind dabei wichtige¨ ¨
Eigenschaften von Gruppenkommunikation, vor allem um die notwendige
Akzeptanz auf der Anwenderseite zu erreichen.
W¨ahrend Peer-to-Peer Sicherheit ein relativ erwachsenes und gut er-
forschtes Gebiet ist, stellt die sichere Gruppenkommunikation noch im-
mer eine ziemlich unerforschte Landschaft dar. Entgegen einer weit ver-
breiteten Fehleinschatzung, ist sichere Gruppenkommunikation keine trivia-¨
le Erweiterung sicherer Zwei-Parteien-Kommunikation. Es gibt eine Viel-
zahl gravierender Unterschiede und sichere Gruppenkommunikation stellt
noch immer zahlreiche Herausforderungen an die Forschungsgemeinde (vgl.
Smith and Weingarten (1997) und Canetti et al. (1999)).
An dieser Stelle seien nur einige Unterschiede und Probleme erwahnt:¨
Aufgrund ihrer zahlreichen und sehr unterschiedlichen Einsatzgebiete ist es
sehr schwer eine allgemeingultige und konsistente Definition fur Gruppen-¨ ¨
Kommunikation zu finden. So haben beispielsweise Gruppen, die fu¨r ei-
ne Video-on-Demand Anwendung gebildet wurden, grundlegend andere Si-
cherheitsanforderungen als dynamische, spontan gebildete Peer-Gruppen in
drahtlosenad-hocNetzwerken. Folglich werdenTaxonomien undKlassifizie-
rungskriterienbeno¨tigt,umProblemklassenundihreSicherheitsanforderun-
1gen zu identifizieren und zu definieren. Noch wichtiger ist es die Sicherheit
grundlegender Dienste, wie beispielsweise Authentifikation, formal zu defi-
nieren, daohnefundierteundformale Sicherheitsdefinitionen, die Sicherheit
der zugrundeliegenden Protokolle nicht rigoros bewiesen werden kann.
EinzweiterUnterschiedliegtindergro¨ßerenBedeutungderRechen-und
Kommunikationskomplexitat der Protokolle, da diese in direkter Abhangig-¨ ¨
keit zur Anzahl der Teilnehmer steht. Desweiteren sind Topologie und Cha-
1Erste Schritte zur Charakterisierung sicherer Gruppenkommunikation wurden bereits
in Hutchinson (1995) und Canetti et al. (1999) diskutiert, jedoch nur als sehr abstrakte
und informelle Taxonomien.
viiviii
rakteristikdesNetzwerkes bedeutendeFaktorenfurdasDesignunddieAus-¨
wahl geeigneter Protokolle.
Ein weiterer Unterschied liegt in der Dynamik der Gruppen: Zwei-
Parteien-Kommunikation kann als ein diskretes Ph¨anomen betrachtet wer-
den: es beginnt, hat eine bestimmte Dauer und endet wieder. Gruppenkom-
munikation ist komplexer: die Gruppe wird gebildet, kann sich durch Ein-
oder Austritt von Teilnehmern a¨ndern und es gibt nicht notwendigerweise
ein fest definiertes Ende. Diese Dynamik macht die Garantie von Sicher-
heitseigenschaften wesentlich aufwendiger und erschwert insbesondere auch
das Schlusselmanagement.¨
Die Lo¨sung all dieser Fragen wu¨rde den Rahmen einer Doktorarbeit bei
weitem sprengen. Daher betrachte ich in dieser Arbeit das grundlegendste
Problem auf dem alle weiteren Sicherheitsmechanismen der Gruppenkom-
munikation aufbauen, namlich das Schlusselmanagement. Desweiteren be-¨ ¨
schra¨nke ich mich auf eine spezielle Klasse von Gruppen, die Dynamischen
Peer-Gruppen (DPG). DPGs sind Gruppen deren Mitglieder in symmetri-
schen Relationen zueinander stehen und daher als ¨aquivalent bzw. gleich-
wertig behandelt werden. Insbesondere sind spezielle Rollen wie Gruppen-
Koordinator nicht von vornherein fixiert, d.h. es gibt keine zentrale Instanz,
die mehr M¨oglichkeiten als andere Gruppenmitglieder hat. Eine Zuweisung
dieser speziellen Rollen sollte nurvon der(moglicherweise variablen) Sicher-¨
heitsstrategie abha¨ngenundunabha¨ngigvondemSchlu¨sselmanagementpro-
tokoll sein. Die Gruppenzugehorigkeit ist dynamisch, d.h. jeder Teilnehmer,¨
insbesondere auch der aktuelle Gruppen-Koordinator, sollte sich prinzipi-
ell einer Gruppe anschließen, oder diese auch verlassen konnen. Diese an-¨
spruchsvollen Eigenschaften heben DPGs von der zur Verteilung digitaler
Multimediainhalte ublichen Multicast-Gruppen ab und machen sie zu ei-¨
nem interessanten Studienobjekt. DPGs sind in vielen Netzwerkschichten
und Anwendungsgebieten u¨blich. Beispiele umfassen replizierte Server aller
Bereiche (wie Datenbank-, Web- oder Zeitserver), Audio- und Videokonfe-
renzsysteme,Battlefield-Netze oderkooperationsunterstu¨tzendeAnwendun-
genallerArt.ImGegensatzzugroßenMulticast-GruppensindDPGsrelativ
klein. Gr¨oßere Gruppen auf Peer-Basis sind sehr schwierig zu kontrollieren
und werden daher meist hierarchisch organisiert. DPGs besitzen im allge-
meinen auch ein many-to-many Kommunikationsmuster statt der u¨blichen
one-to-many Kommunikation in großen hierarchischen Gruppen.
¨Uberblick
Die Doktorarbeit ist wie folgt aufgebaut:
In den Kapiteln 1 und 2 gebe ich eine Einfu¨hrungin die Thematik und
analysiere notwendige Anforderungen an die Schlusselverwaltung, um die¨
Dynamik von DPGs zu unterstu¨tzen.
Die Basis fur eine rigorose Sicherheitsanalyse lege ich in Kapitel 3, in¨ix
dem ich die notwendigen fundamentalen mathematischen Aspekte untersu-
che. Dabei betrachte ich insbesondere kryptographische Annahmen, die auf
diskretenLogarithmen aufbauen,klassifiziere sieunddiskutierewichtige Ei-
genschaften und Parameter, deren Vera¨nderung unterschiedliche Varianten
dieser Annahmen implizieren. Zusatzlich beweise ich mehrere Relationen¨
zwischen unterschiedlichen Annahmen, welche sich in sp¨ateren Sicherheits-
beweisen fu¨r die Protokolle zum Gruppen-Schlu¨sselaustausch als hilfreich
¨erweisen werden. Insbesondere wird die Aquivalenz des Decisional Genera-
lized Diffie-Hellman Problems und des Decisional Diffie-Hellman Problems
konstruktiv bewiesen, indem eine effiziente Reduktion zwischen beiden Pro-
blemen in einer Vielzahl von Annahmenformulierungen angegeben wird.
Desweiteren zeige ich, wie Bit-Strings aus Diffie-Hellman Schlusseln erzeugt¨
werden ko¨nnen, so daß diese Strings ununterscheidbar von gleichverteilten
Strings sind.
Kapitel 4 zeigt CLIQUES, eine vollst¨andige Familie von Protokollen zur
Schlusselverwaltung in Netzen mit authentischen Verbindungen. Diese um-¨
faßt Protokolle zum initialen Schlu¨sselaustausch, zur Schlu¨sselerneuerung
¨und zur Anderung von Gruppenzugeh¨origkeiten. Das Kapitel schließt mit
einer Untersuchung der Eigenschaften und Effizienz dieser Protokolle sowie
einigen Argumenten zum Beweis ihrer Sicherheit.
DieseSicherheitsargumenteentsprechenvomFormalitatsgradherdenSi-¨
cherheitsbeweisen existierender Gruppen-Schlu¨sselaustausch Protokolle. In
Kapitel5geheichweit uberdiesesbisherublicheMaßanFormalitat hinaus.¨ ¨ ¨
Dazu definiere ich zuna¨chst ein formales Modell fu¨r Gruppen-Schlu¨sselaus-
tausch Protokolle und zeige einen detailierten und rigorosen Sicherheitsbe-
weis eines der CLIQUES Protokolle zum initialen Schlu¨sselaustausch. Ins-
besondere zeige ich, daß das Protokoll sogar gegen adaptive Angreifer unter
der Decisional Diffie-Hellman Annahme sicher ist, wenn das Protokoll um
eine Besta¨tigungsnachricht erweitert wird.
Die Arbeit schließt in Kapitel 6 mit einer Zusammenfassung der vorge-
stellten Ergebnisse und einem Ausblick auf offene Probleme und mo¨gliche
weitere Forschungsrichtungen.
Ergebnisse
Die Hauptresultate dieser Arbeit konnen wie folgt zusammengefaßt werden:¨
1. Die erste detaillierte Klassifizierung kryptographischer Annahmen ba-
sierend auf diskreten Logarithmen wird vorgestellt. Diese Klassifizie-
rung erlaubt eine prazise und dennoch allgemeine Darstellung dieser¨
Annahmen und liefert neuartige Einsichten in die Zusammenh¨ange
zwischen diesen Annahmen. So wurden ausgehend von dieser Klas-
sifizierung u¨berraschende Ergebnisse hinsichtlich der Separierbarkeit
von Annahmen in Abhangigkeit des zugrundeliegenden Wahrschein-¨
lichkeitsraumes erzielt (Sadeghi and Steiner 2001).x
2. Ein neues Problem, das Decisional Generalized Diffie-Hellman Pro-
blem, wird eingefu¨hrt und konstruktiv als ¨aquivalent zum Decisional
Diffie-Hellman Problem bewiesen, wobei der Beweis auch die konkrete
Sicherheit, d.h., die genauen Reduktionskosten liefert. Das Problem
bzw. die zugehorige Annahme ist nicht nur im Kontext von Diffie-¨
Hellman-basierten Gruppen-Schlu¨sselaustausch Protokollen nu¨tzlich,
sondern dient auch als Basis fu¨r die erste effiziente Konstruktion einer
beweisbar sicheren Pseudo-Zufallfunktion (Naor and Reingold 1997).
3. CLIQUES, eine Familie flexibler Schlu¨sselmanagementprotokolle fu¨r
dynamische Peer-Gruppen, wird eingefuhrt. Sie sind die ersten kol-¨
2lusionstoleranten Protokolle, die keinen festen Gruppen-Koordinator
voraussetzen. Die Protokolle sind optimal oder zumindest nahezu op-
timal bezu¨glich verschiedenster Leistungsmerkmale.
4. DieersteformaleDefinitionvonsicheremGruppen-Schlusselaustausch¨
wird pr¨asentiert. Ausgehend von dieser Definition wird die Sicherheit
zweier effizienter Gruppen-Schlusselaustausch Protokolle auf Netz-¨
werken mit authentischen Verbindungen bewiesen. Dadurch wird ei-
ne wichtige Lu¨cke in der Sicherheitsanalyse von Protokollen zum
Gruppen-Schlu¨sselmanagement geschlossen und das Vertrauen in der-
artige Protokolle entsprechend erho¨ht. Ein weiterer Vorteil dieser De-
finition ist, daß sie die sichere modulare Kombination mit anderen
Protokollen ermo¨glicht. Als Spezialfall liefert sie gleichzeitig auch die
erste Definition fureinsicheres, modularkombinierbares Schlusselaus-¨ ¨
tausch Protokoll fu¨r den Zwei-Parteien-Fall.
Alle oben genannten Ergebnisse wurden bereits in
Vorversionen vero¨ffentlicht. Die erste Publikation ist
Steiner, Tsudik, and Waidner (1996), welche die Grundlage fur die¨
Protokollfamilie CLIQUES legte, das Decisional Generalized Diffie-Hellman
¨Problemeinfuhrtesowieeinenersten, nicht-konstruktiven Aquivalenzbeweis¨
zwischen dem Generalized Diffie-Hellman Problem und dem Decisional
Diffie-Hellman Problem enthielt. Die dynamischen Aspekte von Gruppen-
SchlusselaustauschwurdeninSteiner, Tsudik, and Waidner (1998)beleuch-¨
tet. Diese Publikation fu¨hrte auch die ersten Gruppen-Schlu¨sselaustausch-
Protokolle ein, die kollusionstolerant sind und dynamische Gruppen-
Koordinatore erlauben. Diese Papiere wurden zu einer erweiterten
Journalversion (Steiner, Tsudik, and Waidner 2000) kombiniert. Die Un-
tersuchung und Klassifizierung der kryptographischen Annahmen, wie in
Kapitel 3 gezeigt, basiert auf Sadeghi and Steiner (2001, 2002). Das formale
Modell von Group-Key-Agreement und die zugeh¨origen Beweise wurden in
Pfitzmann, Steiner, and Waidner (2002) vero¨ffentlicht.
2Kollusionen sind Koalitionen von unehrlichen Teilnehmern.