Die Snowden-Enthüllungen aus dem Jahr 2013 gaben Aufschluss über das Ausmaß staatlich durchgeführter Massenüberwachungsprogramme, die Menschen auf der ganzen Welt ausspionieren, ihre Privatsphäre verletzen und ihre Cyber-Sicherheit gefährden. Das vermutlich teuerste dieser Programme, das Entschlüsselungsprogramm Bullrun der NSA, zielt darauf ab, Kryptosysteme zu brechen und sogar zu sabotieren. Allein im Jahr 2013 kostete Bullrun 254,9 Millionen Dollar. Kryptosysteme sind anfällig für Sabotage in ihren mathematischen Spezifikationen, der Standardisierung ihrer Parameter und ihrer Implementierungen. Es war eine bittere Überraschung zu realisieren, dass die Fähigkeiten von Angreifern, die in klassischen kryptographischen Modellen betrachtet werden, oft nicht annähernd an das herankommen, was für einen Big Brother, d.h. einen Angreifer auf Staatsebene, machbar ist. Eine gründliche Untersuchung der kryptographischen Sabotage und die Entwicklung resistenter Kryptosysteme sind deshalb von größter Notwendigkeit. Dadurch, dass der von uns berücksichtigte Angreifer äußerst mächtig ist, erfordern Lösungen in solchen Szenarien nicht nur eine Anpassung der bestehenden Ansätze aus diversen Bereichen der Kryptographie und anderen eng verwandten Disziplinen an neue Szenarien, sondern manchmal auch völlig neue Design- und Beweistechniken. Daher setzt sich diese Dissertation als Ziel, neue Erkenntnisse und Techniken zum kryptographischen Werkzeugkasten beizutragen, damit man solche Angriffe besser bekämpfen kann. Wir befassen uns insbesondere mit der Deaktivierung von Hintertüren im mathematischen Design kryptographischer Primitiven sowie der Wiederherstellung der Sicherheit in ihren unterwanderten Implementierungen.

Der erste Teil dieser Dissertation beschäftigt sich mit dem Vernichten von Hintertüren in Hashfunktionen, die eine der grundlegendsten und vielseitigsten Primitiven in der Kryptographie sind. Wir formulieren und untersuchen Hashfunktionen mit eingebetteten Hintertüren, wobei ein Big Brother eine Hashfunktion entwirft, die zwar vernünftige Funktionalität und Sicherheitseigenschaften vorzeigt, aber mit einer geheimen Hintertür gebrochen werden kann. Wir beginnen mit der Modellierung von Hashfunktionen mit Hintertüren im Standardmodell (d.h. ein Modell ohne idealisierte Primitiven), wobei die Hintertür ein mit der Hashfunktion entworfener Schlüssel ist. Wir zeigen die Realisierbarkeit effizienter Hashfunktionen mit fester Eingabelänge und eingebetteten Hintertüren und wie das Iterieren dieser Funktionen durch die Merkle-Damgard- oder die Sponge-Kontruktionen zu Hashfunktionen mit beliebiger Eingabelänge und Hintertüren führt, bei denen wesentliche Sicherheitsgarantien versagen. Auf der positiven Seite zeigen wir, dass die schwache Pseudozufälligkeitseigenschaft der Hashfunktionen, die einen geheimen Schlüssel verwenden, in der Tat robust gegen Hintertüren ist. Dieses Resultat erlaubt es uns, eine hintertürresistente iterative Pseudozufallsfunktion zu bauen, genauer gesagt eine Variante von HMAC. Wir zeigen auch, wie die Schlüsselableitungsfunktion, HKDF, mit geringem Aufwand gegen Hintertüren immunisiert werden kann. Leider deuten unsere Resultate auch darauf hin, dass das Immunisieren einer Hashfunktion, ohne sich dabei auf einen geheimen Schlüssel zu verlassen, vermutlich schwierig ist. Diese Beobachtung motivierte später unsere Idee zum Kombinieren von unabhängigen Hashfunktionen als eine Strategie für die Konstruktion sicherer und hintertürresistenter Hashfunktionen.

Wir führen anschließend ein Modell ein, das wir Backdoored-Random-Oracle (BRO) nennen, auf Deutsch Zufallsorakel mit Hintertür, wobei ein Big Brother eine zufällige Hashfunktion, d.h. ein Zufallsorakel, auswählt, aber dennoch beliebige Funktionen seiner Tabelle mit Hilfe eines Hintertürorakels sehen kann. Dieses Modell erfasst zusätzlich zu den gewöhnlichen Angriffen wie Kollisionsfindung oder Invertieren auch jegliche denkbare Schwäche, die eine Hashfunktion haben kann. Ausgestattet mit einem solchen Hintertürorakel sind Angreifer daher so mächtig, dass keine auf einem einzelnen BRO mit allmächtigem Hintertürorakel basierende Sicherheit erreichbar ist. Wir zeigen jedoch, dass bestimmte Sicherheitseigenschaften wie One-Way-Sicherheit, Pseudozufälligkeit und Kollisionsresistenz gerettet werden können, wenn zwei unabhängige BROs zur Verfügung stehen. Dies gilt, auch bei uneingeschränktem und adaptivem Zugriff auf beide Hintertürorakel. Zu diesem Zweck berücksichtigen wir drei weitverbreitete Kombinierer: Konkatenation, Kaskade und XOR. Im Mittelpunkt unserer Resultate stehen neue Reduktionen von kryptographischen Sicherheitszielen auf die Kommunikationskomplexitäten verschiedener Zweiparteienaufgaben. Dabei etablieren wir auch eine neue Unterschranke für die Kommunikationskomplexität von Schnittmengenberechnung für kryptographisch relevante Bereiche von Parametern und Verteilungen, wobei das Problem der Mengendisjunktheit einfach sein kann.

Wir untersuchen die Technik der Kombination unabhängiger BROs weiter, um eine Hashfunktion aus zwei oder mehr BROs zu bilden, so dass diese Konstruktion in vielen kryptographischen Anwendungen verwendet werden kann, die auf ein hintertürfreies Zufallsorakel setzen. Die Eigenschaft, die es einer Hashfunktionskonstruktion praktisch erlaubt, ein Zufallsorakel zu ersetzen wird als Undifferenzierbarkeit bezeichnet und wurde von Maurer, Renner und Holenstein (TCC 2004) eingeführt. Das Erreichen vollständiger Undifferenzierbarkeit in unserem Modell scheint im Moment sehr herausfordernd zu sein. Wir machen jedoch Fortschritte in dieser Richtung, indem wir zeigen, dass der XOR-Kombinierer weit über die Sicherheit gegen Vorverarbeitungsangriffe hinausgeht und Undifferenzierbarkeit bietet, solange die Anzahl der Abfragewechsel des Angreifers zwischen den Hintertürorakeln logarithmisch in der Eingabelänge der einzelnen BROs bleibt. Wir zeigen auch, dass ein auf einem Zufallsextrahierer basierender Kombinierer für drei BROs kann Undifferenzierbarkeit sogar gegen Angreifer mit einer linearen Anzahl von Abfragewechsel anbieten. Um diese Behauptungen zu beweisen, verwenden und verfeinern eine neue Technik von Göös, Lovett, Meka, Watson und Zuckerman (STOC 2015) für die Zerlegung von Verteilungen mit hoher Entropie in konvexe Kombinationen von Verteilungen über Bitstrings, die in einigen Punkten fixiert und in den restlichen Punkten sehr unvorhersehbar sind. Eine natürliche Einschränkung unserer Definition von Undifferenzierbarkeit im BRO-Modell führt außerdem zu einer Definition von Undifferenzierbarkeit mit Hilfseingabe, für die wir zwei positive Machbarkeitsergebnisse liefern.

Der zweite Teil dieser Dissertation befasst sich damit, Sicherheit in der Gegenwart von unterwanderten Implementierungen zu bieten. Wir stellen die Idee des Selfguarding der kryptographischen Primitiven als eine Gegenmaßnahme zu einer Unterklasse sogenannter Algorithm-Substitution-Attacks (ASAs), auf Deutsch Algorithmensubstitutionsangriffe, vor. Solche Angriffe werden von Bellare, Paterson und Rogaway (CRYPTO 2014) als Angriffe formalisiert, bei denen ein Big Brother heimlich die sichere Implementierung eines Kryptosystems durch ein Bösartiges ersetzt, um die Sicherheit der Nutzer zu unterminieren. Die Authoren zeigen darüber hinaus, dass randomisierte symmetrische Verschlüsselungsverfahren anfällig für solch verheerende ASAs sind, die es einem Big Brother praktisch ermöglichen, geheime Schlüssel zu extrahieren. Dabei bleibt das Ein-Ausgabeverhalten des Verschlüsselungsalgorithmus ununterscheidbar von dem einer aufrichtigen und sicheren Implementierung. Die Erkennung von ASAs, auch wenn theoretisch möglich, ist leider keine leichte Aufgabe. Unsere Selfguarding-Primitiven sind nicht auf Erkennbarkeit angewiesen und können trotzdem unerwünschte Informationsleck durch unterwanderte Algorithmen unterbinden, meist für eine begrenzte Zeit, wenn man die Garantie hat, dass das System während einer Anfangsphase richtig funktioniert hat. Diese sichere Anfangsphase ist beispielsweise gerechtfertigt, bevor eine böswillige Software-Update durchgeführt wird oder ein bösartiger interner Zustand erreicht wird. Wir präsentieren Konstruktionen für symmetrische und asymmetrische Verschlüsselung und für digitale Signaturen. Wir argumentieren auch, dass das Modell Angriffe mit bösartigen Hardware-Tokens erfasst und zeigen, wie ein Schlüsselaustauschprotokoll, das auf einer Physical-Unclonable-Function (PUF) basiert, Selfguarding werden kann.