Empirical analysis of Public Key Infrastructures and investigation of improvements
Ralph-Günther Holz · mediaTUM – the media and publications repository of the Technical University Munich (Technical University Munich) · 2014
Public Key Infrastructures (PKIs) were developed to address the key distribution problem of asymmetric cryptography.Certificates bind an identity to a public key and are signed by a trustworthy entity, called the issuer.Although seemingly a simple concept, the setup of a PKI is not an easy task at all.Trustworthy issuers need to be guaranteed, and certificates must be issued conforming to certain standards.A correct deployment is needed to ensure the PKI is usable for the parties that rely on it.Some PKIs, like the important X.509 PKI for TLS, were criticised from early on for being poor examples with respect to these aspects.The objective of this thesis is to provide a sound analysis of important PKIs and to analyse proposals for improvements for one of them, X.509.The contributions of this thesis are threefold.In the first part of this thesis, we carry out an analysis of known criticisms of the X.509 PKI and show that they were never addressed well.The approach here is both documental as well as empirical.Furthermore, we provide a survey of incidents in the X.509 PKI, some of which brought it close to failure, and identify their root causes.This analysis allows us to formulate requirements that improvements for the X.509 PKI have to meet.The methodology here is historical-documental.In the second part of the thesis, we apply empirical methods to analyse the status quo for three representative and important PKIs that address different use cases: X.509, the OpenPGP Web of Trust, and the simple key distribution mechanism of SSH.We measure their respective strengths and weaknesses, in particular with respect to deployment, and draw conclusions about the level of security that each PKI achieves in practical use.For X.509, we carried out HTTPS scans of a large number of servers over a period of 1.5 years, including scans from globally distributed vantage points.We also monitored live TLS traffic on a high-speed link of a large network.Our analyses of the thus obtained certification data reveals that the quality of certification lacks in stringency to a degree that is truly worrisome.For OpenPGP, we conducted a graph analysis of the Web of Trust, with a focus on properties such as usefulness and robustness of certification chains.We also analysed the community structure of the Web of Trust and mapped it to social relationships.This allows us to determine for which users, and on which scale, the Web of Trust is particularly useful.For SSH, we carried out several scans over the entire IPv4 address space and collected statistics on host-keys and ciphers used.A number of keys were found to be duplicates, but not due to cryptographic weaknesses.For these, we determined in which network setups they occurred and identified both secure as well as very insecure patterns of use.In the third part of this thesis, we study five representative schemes to improve the security of X.509.In order to describe each scheme succinctly, we first develop a unified notation to capture the essential protocol flows and properties of each scheme.We then analyse its security properties with particular regard to three threat models that we defined for this purpose.A further particular focus is on the deployment properties of a scheme, i.e., which entities need to make changes to implement it.Based on our findings, we identify the two most promising candidates to reinforce X.509.However, all schemes fall short in one respect, namely automatic incident reporting and localisation of the position of an attacker.We thus developed and deployed our own solution, Crossbear, to close this gap.Crossbear allows to detect an ongoing man-in-the-middle attack and initiates a distributed but centrally coordinated hunting process to determine the location of the attacker in the network with a fair degree of confidence.III Zusammenfassung Public Key Infrastructures (PKIs) wurden als Antwort auf das Problem der sicheren Schlüsselverteilung in der symmetrischen Kryptographie eingeführt.Zertifikate von vertrauenswürdigen Ausstellern binden einen öffentlichen Schlüssel an die Identität eines Teilnehmers.Der Aufbau einer PKI ist jedoch kein leichtes Unterfangen.Zum einen muss die Vertrauenswürdigkeit der Aussteller garantiert und Zertifikate müssen nach anerkannten Standards ausgestellt werden.Zum anderen müssen die Zertifikate auf korrekte Weise zum Einsatz kommen, um sicherzustellen, dass alle Teilnehmer sie auch nutzen können.PKIs wie X.509 wurden schon früh dafür kritisiert, dass sie in den genannten Bereichen Schwächen aufweisen.Das Ziel dieser Arbeit ist eine umfassende Analyse wichtiger PKIs und eine Analyse von Verbesserungen für eine davon, X.509.Im ersten Teil der Arbeit werden frühere, bekannte Kritikpunkte an X.509 daraufhin untersucht, ob seit ihrer Veröffentlichung Verbesserungen erreicht wurden.Es wird gezeigt, dass das nicht der Fall ist.Der Ansatz enthält sowohl dokumentarische als auch empirische Elemente.Weiterhin wird eine Ursachenanalyse für eine Reihe von kritischen Vorfällen in der X.509 PKI durchgeführt, von denen einige die Sicherheit der PKI beinahe außer Kraft gesetzt hätten.Daraus werden Anforderungen abgeleitet, die Erweiterungen von X.509 erfüllen müssen, um Verbesserungen bewirken zu können.Der Ansatz hier ist vor allem dokumentarisch.Im zweiten Teil kommen empirische Methoden zum Einsatz, um den Status Quo für drei repräsentative und wichtige PKIs zu ermitteln.Diese PKIs decken jeweils unterschiedliche Anwendungsfälle ab.Es handelt sich um X.509, das Open PGP Web of Trust, und die Schlüsselverteilung in SSH.Für jede PKI werden Methoden entwickelt, mit denen die besonderen Stärken und Schwächen der jeweiligen PKI ermittelt werden können.Das erlaubt Rückschlüsse auf die Sicherheit, die die jeweilige PKI bietet.Für X.509 wurde eine große Zahl an Servern über einen Zeitraum von 1,5 Jahren gescannt, zum Teil auch von Beobachtungspunkten rund um den Globus.Zusätzlich wurden Monitoringdaten genutzt.Die Analyse zeigt eine besorgniserregende Qualität der Zertifikate und ihres Einsatzes.Für OpenPGP wird eine Graphanalyse des Web of Trust durchgeführt.Der Fokus liegt auf der Nützlichkeit dieser PKI und ihrer Robustheit gegen ungewollte Änderungen.Zusätzlich wird untersucht, inwiefern sich die Teilnehmer des Web of Trust sogenannten Communities, die sozialen Verbindungen entsprechen, zuordnen lassen.Dies erlaubt es, Rückschlüsse zu ziehen, für welche Teilnehmer das Web of Trust einen besonders hohen Nutzen aufweist.Die Arbeiten zu SSH umfassen Scans, die internetweit durchgeführt wurden.Es werden zum einen Statistiken zu Chiffren und den Schlüsseln erhoben, mit denen sich Hosts in SSH authentisieren.Zum anderen wird eine Analyse von Schlüsseln durchgeführt, die keine kryptographischen Schwächen haben, aber häufig auftreten.Dies passiert vor allem in bestimmten Netzwerkkonfigurationen, von denen einige sehr unsicher sind.Im dritten Teil werden Systeme zur Verbesserung von X.509 untersucht.Dazu wird eine Notation entwickelt, die es erlaubt, die wesentlichen Protokollflüsse und Design-Elemente eines Systems in einheitlicher Weise zu beschreiben.Darauf baut eine Analyse der Sicherheitseigenschaften des Systems auf.Weiterhin wird eine Betrachtung durchgeführt, welche Schwierigkeiten sich bei der Einführung des Systems ergeben können.Mit Hilfe dieser Betrachtungen werden die zwei aussichtsreichsten Kandidaten zur Verbesserung von X.509 identifiziert.Alle betrachteten Systeme haben jedoch einen Nachteil: Sie erlauben keine automatisierte Meldung von Angriffen oder gar eine Lokalisierung des Angreifers.Daher wurde im Rahmen der Arbeit Crossbear entwickelt: Crossbear erlaubt, Man-in-the-middle-Angriffe auf TLS zu erkennen.Als Reaktion koordiniert Crossbear einen verteilten Prozess, der es ermöglicht, die Position des Angreifers mit hinreichender Genauigkeit zu ermitteln. VThis work would not have been possible without the invaluable help and steady support of a number of people.I would like to take the opportunity to express my gratitude.My first thanks go to my advisor Dr. Georg Carle, of course, for making it possible for me to carry out my