Measuring unlinkability for privacy enhancing technologies [Elektronische Ressource] / vorgelegt von Lars Fischer

Lars Fischer

Sujets

• Informatik
• Mathematics

Informations

• Publié par: technischen_universitat_darmstadt
• Publié le: 01 janvier 2010
• Nombre de lectures: 18
• Langue: English
• Poids de l'ouvrage: 4 Mo

Extrait

Measuring Unlinkability for
Privacy Enhancing Technologies
Vom Fachbereich Informatik der Technischen Universit at Darmstadt
zur Erlangung eines Doktors der Naturwissenschaften (Dr. rer. nat.)
genehmigte Dissertation
vorgelegt von Dipl. Inf. Lars Fischer,
aus Marburg an der Lahn
Gutachter: Prof. Dr. Claudia Eckert
Prof. Dr. Stefan Katzenbeisser
Prof. Dr. Dogan Kesdogan
Tag der Einreichung: 21.09.2010
Tag der Prufung: 29.11.2010
Darmstadt 2010
D 17Abstract
This work contributes to the eld of unlinkability. Unlinkability describes a
situation where attackers are unable to correctly cluster items of interest. The
focus of this work is on modelling and measuring unlinkability. Additionally a
protocol for provision of unlinkable certi cates, tailored to the requirements
of vehicular communication is introduced. The vehicular scenario is used
throughout this work as a motivating example.
In this work, a linkability graph is developed and used to illustrate the
tight relation between unlinkability and anonymity in certi cation schemes.
The main distinction between anonymity and unlinkability problems is cap-
tured by the notion of inner structure, which is developed in this work.
Inner structure describes the inherent di erence between hypotheses of un-
linkability problems. This di erence is expressed by metrics that re ect the
attackers’ objectives and world-view. Inner structure motivates consistency
of an attacker’s world-view as criterion for assessment of attacker quality.
Previous entropy-based global unlinkability measures do not re ect the
consistency of attacker probability mass assignments. In this work, these
shortcomings are analysed, and criteria for unlinkability measures are de-
veloped. These criteria are then discussed for a new unlinkability measure
introduced herein. This expected distance unlinkability measure is de ned
using the inner structure of a space of hypotheses. It thus re ects the con-
sistency of an attacker’s assignment and not only the attacker’s certainty as
done by entropy-based measures.
This work also contributes a certi cation protocol that provides revocable-
anonymous protocols that are not linkable to each other or the authenticated
requester by the issuing certi cation authority or others. Revocation of an-
onymity is possible only by a quorum of independent revocation authorities.
The objective is to reduce the trust that has to be put into single authorities
to reduce the risk of misuse. The protocol is based on a previously known
cut-and-choose blind signature protocol, but made more exible to suit ve-
hicular communication scenarios. An extensive security analysis of newly
introduced protocol-parameters is provided.
Concluding, this work provides a contribution to the ongoing discussion
on unlinkability, unlinkability measures and analysis. It draws motivation
from a communication scenario that is intensively researched at the moment
and contributes to the protocol development there.
iiZusammenfassung
1In dieser Arbeit wird die quantitative Analyse von Unverkettbarkeit be-
handelt. Unter Unverkettbarkeit versteht man die Unm oglichkeit, dass ein
Angreifer den Zusammenhang zwischen Datenobjekten heraus nden kann.
Das bedeutet insbesondere, dass kein Angreifer in der Lage ist anonyme
Nachrichten miteinander zu verketten.
Wir konkretisieren zun achst die Unterscheidung zwischen Anonymit at
und Unverkettbarkeit indem wir formal Anonymit ats- und Verkettbarkeit-
sprobleme de nieren. Der Zusammenhang zwischen beiden Problemklassen,
insbesondere, dass Anonymit atsprobleme spezielle Verkettbarkeitsprobleme
darstellen wird im Anschluss gezeigt. Der Zusammenhang wird dann in
einem Analysemodell weiter konkretisiert und auf ein konkretes Szenario, die
Zerti katsstruktur in Fahrzeugkommunikation, angewendet. Das in dieser
Arbeit verwendete Beispiel der Fahrzeugkommunikation ist besonders geeignet
weil dabei zum einen hohe Anforderungen an die Privatheit gestellt wer-
den, andererseits aber sehr genaue und umfangreiche Positionsdaten ver-
wendet werden und zus atzlich besondere Dringlichkeit der Informationszu-
verl assigkeit besteht.
In unserer und anderen Arbeiten zu Unverkettbarkeitsma en wird an-
genommen, dass der Angreifer eine Wahrscheinlichkeitsverteilung ub er den
gesamten Hypothesenraum eines Verkettbarkeitsproblems liefert. Der Hy-
pothesenraum umfasst dabei alle Partitionierungen der Menge der betra-
chteten Objekte (Items of Interest (IOI)). In dieser Arbeit entwickeln wir die
Unterscheidung zwischen dieser outer structure und der inner structure des
Hypothesenraums. Die au ere Struktur beschreibt die durch den Angreifer
induzierte Bewertung des Hypothesenraums. Die innere Struktur wird durch
2De nition einer Metrik der ahnlic hkeit von Hypothesen aufgebaut.
Bisher bekannte Verkettbarkeits-Ma e verwenden ausschlie lich die au ere
Struktur und ignorieren die innere Struktur des Hypothesenraums. Als Re-
sultat werden unterschiedlich gute Angreifer von bisherigen Ma en gleich
bewertet. Wir entwickeln den Begri der Konsistenz eines Angreifers ( con-
sistency) aus dieser Kritik heraus, welcher sich auf die innere Struktur stutzt.
In dieser Arbeit werden Kriterien fur Verkettbarkeitsma e entwickelt und
diskutiert und ein neues Ma ( Expected Distance Unlinkability Measure)
vorgestellt, welches den zu erwartenden Fehler des Angreifers zur Bewertung
verwendet. Der erwartete Fehler ist die, durch die Angreifer-bestimmten
Wahrscheinlichkeiten (externe Struktur) gewichtete, Summe der Distanzen
(innere Struktur) aller Hypothesen von einer gegebenen Referenzhypothese.
1 Ubers. Unlinkability
2oder Quasi-Metrik
iiiWir unterscheiden die zwei Analysearten Black Box und White Box. In der
Black Box Analyse ist die korrekte Hypothese, welche mit der Realit at korre-
liert, unbekannt, weshalb sinnvollerweise die vom Angreifer h ochstbewertete
Hypothese als Referenz genommen. In der White Box Analyse wird die kor-
rekte Hypothese als Referenz verwendet. In beiden F allen korreliert der da-
rauf berechnete erwartete Fehler des Angreifers mit dem von uns eingefuhrten
Konsistenzbegri .
Die Verwendung von Verkettbarkeitsma en an realen Beispielen ist im
Allgemeinen schwierig aufgrund der Kardinalit at des Hypothesenraums und
der Summe die ub er diesem Raum gebildet werden mu . Wir stellen in dieser
Arbeit erste Ans atze vor mit der die Komplexit at der Berechnung fur ein-
fache Angreifer deutlich reduziert werden kann. Diese soweit zu entwickeln,
da Verkettbarkeitsma e in realistischen Szenarien mit beliebigen Angreifern
durchgefuhrt werden k onnen ist Teil zukunftiger Forschung.
Unverkettbarkeit setzt Anonymit at voraus. In fruhere n Arbeiten haben
wir Protokolle entwickelt die kontrolliert widerrufbar-anonyme Zerti zierung
3unter der besonderen Pr amisse der Trennung von Zerti zierungs- und Wider-
4rufsstelle vorgestellt. Eine Zerti zierungsstelle hat die Aufgabe die Au-
thentizit at und Authorisierung eines Antragsstellers zu prufen und ist au-
thorisiert anonyme Zerti kate auszustellen ohne diese allerdings spater dem
Antragssteller zuordnen zu k onnen. Die Widerrufsstelle ist authorisiert diese
Verbindung herzustellen und damit die Anonymit at des Antragsstellers auf-
zuheben. Das Ziel ist unverkettbare Kommunikation auch gegenub er der
Zerti zierungsstelle.
In dieser Arbeit erweitern wir ein bestehende Protokoll Zerti zierungs-
Protokoll. In einer vollst andigen Analyse wird anschlie end gezeigt wie die
Sicherheit der Revozierung gegen Berechnungsaufwand in Verschiedenen Pro-
tokollabschnitten abgewogen werden kann. Am Beispiel der Fahrzeugkom-
munikation wird aufgezeigt, dass dadurch eine ausreichend kurze Veri ka-
tionszeit w ahrend des Kommunikationsvorgangs bei ausreichender Sicherheit
erreicht werden kann.
Erst durch Protokolle wie das hier vorgestellte ist es m oglich Unver-
kettbarkeit zu implementieren, die starke Anonymit at und h au ge Zerti-
katswechsel voraussetzt. Nicht nur im behandelten Szenario ist eine Vielzahl
von auswertbaren Informationen enthalten die letztendlich Objekte verket-
tbar machen.
Protokollentwickler ben otigen pr azise Ma e zur Entwicklung von pri-
vatheitserhaltenden Systemen. Der hier verfolgte Ansatz, ein Ma anhand
von festen Kriterien zu entwickeln tr agt dem Rechnung. Die aufgezeigten
3Certi cation Authority
4Revocation A
ivProbleme bestehender Ma e werden diskutiert und durch die Entdeckung
der inneren Struktur des Hypothesenraums erkl art. Die von uns vorgestellte
Expected Distance Unlinkability Measure vermeidet die Probleme bestehen-
der Ma e. Zudem liefert unser Ansatz die erste Diskussion der Umsetzbarkeit
der bisherigen Ma e, die in Zukunft weiter gefuhrt werden muss um quanti-
tative Absch atzungen von Verkettbarkeit realistisch zu implementieren.
vviContents
1 Introduction 1
2 Fundamental De nitions and Models 5
2.1 Privacy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.2 Items of Interest and Identi cation Anchors . . . . . . . . . . 6
2.3 Anonymity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.3.1 Perfect/Conditional Anonymity . . . . . . . . . . . . . 8
2.3.2 Local/Dispersed Anonymity . . . . . . . . . . . . . . . 9
2.3.3 Individual/Global Anonymity . . . . . . . . . . . . . . 9
2.4 Pseudony