TU Darmstadt / ULB / TUprints

Cryptographic Primitives that Resist Backdooring and Subversion

Mazaheri, Sogol (2020):
Cryptographic Primitives that Resist Backdooring and Subversion. (Publisher's Version)
Darmstadt, Technische Universität,
DOI: 10.25534/tuprints-00014550,
[Ph.D. Thesis]

Available under CC-BY-NC-ND 4.0 International - Creative Commons, Attribution Non-commerical, No-derivatives.

Download (1MB) | Preview
Item Type: Ph.D. Thesis
Status: Publisher's Version
Title: Cryptographic Primitives that Resist Backdooring and Subversion
Language: English

The Snowden revelations of 2013 have shed some light on the extent of state-performed mass surveillance programs that target people all over the world, violate their privacy, and endanger their cyber security. The presumably most expensive of these surveillance programs is the NSA's decryption program, Bullrun, which aims at breaking and sabotaging cryptosystems. This program cost $254.9 million in 2013 alone. Cryptosystems are vulnerable to sabotage in their mathematical specifications, standardization of their parameters, and their implementations. It has been a bitter surprise to realize that the capabilities of adversaries that have been classically considered in cryptographic models often do not even come close to what is attainable for big brother (i.e., state-level) adversaries. Therefore, it is of utmost necessity to rigorously study cryptographic sabotage and to develop resilient cryptosystems. Considering that the anticipated adversary is an extremely powerful one, finding solutions against sabotage requires not only tailoring the existing approaches from various areas in cryptography and other closely related disciplines to new scenarios but at times also entirely new design and proof techniques. As such, this thesis aims at adding new knowledge and techniques to the cryptographic toolbox to help better combat such attacks. In particular, we tackle the problem of disabling backdoors embedded in the mathematical design of cryptographic primitives as well as re-establishing security in their subverted implementations.

The first part of this thesis is concerned with defeating backdoors in hash functions, which are one of the most fundamental and versatile primitives in cryptography. We formulate and study backdoored hash functions, whereby a big brother designs a hash function that despite displaying reasonable functionality and security properties, can be broken using a secret backdoor. We start by modeling backdoored hash functions in the standard model (i.e., a model without idealized primitives), where the backdoor is a key co-designed with the hash function. We then show the feasibility of efficient backdoored hash functions for fixed-length inputs and how iterating such functions in the Merkle-Damgard or the sponge constructions leads to backdoored hash functions for inputs of arbitrary length, where crucial security guarantees break down. On the positive side, we give evidence that the weak pseudorandomness property of hash functions, which rely on a secret key, is in fact robust against backdooring. This result allows us to build a backdoor-resilient iterative pseudorandom function, more precisely, a variant of HMAC. Furthermore, we show how the key derivation function HKDF can be immunized against backdoors at little cost. Unfortunately our findings also suggest that immunizing a hash function against backdoors, without relying on a secret key, is presumably hard. This observation later motivated our study of combining independent hash functions as a possible strategy in building secure backdoor-resilient hash functions.

We then introduce a model which we call the backdoored random-oracle (BRO) model, whereby a big brother picks a random oracle, i.e., a random function, but he can also obtain arbitrary information about the random oracle using a backdoor oracle. This model captures not only weaknesses that lead to collision-finding and inversion attacks but also any conceivable weakness that can exist in a hash function. Therefore, adversaries equipped with such a backdoor oracle are powerful to the extent that no security can be achieved based on a single arbitrarily backdoored random oracle. However, when two independent BROs are available, we show that certain security properties, such as one-wayness, pseudorandomness, and collision resistance can be re-established. This is true even when we allow unrestricted and adaptive access to both backdoor oracles. To this end we consider three common combiners: concatenation, cascade, and xor. At the core of our results lie new reductions from cryptographic security goals to the communication complexities of several two-party tasks. Along the way we establish a communication complexity lower bound for set-intersection for cryptographically relevant ranges of parameters and distributions and where deciding set-disjointness can be easy.

We further study the technique of combining independent BROs in order to construct a hash function from two or more BROs in a way that it can be used in many cryptographic applications that rely on a backdoor-free random oracle. The property that practically allows a hash function construction to replace a random oracle is referred to as indifferentiability and was introduced by Maurer, Renner, and Holenstein (TCC 2004). Achieving full indifferentiability in our model seems very challenging at the moment. We however make progress in this direction by showing that the xor combiner goes well beyond security against preprocessing attacks and offers indifferentiability as long as the number of the adversary's query switches between the backdoor oracles remains logarithmic in the input size of the underlying BROs. We also show that an extractor-based combiner of three BROs can provide indifferentiability even against adversaries that make a linear number of switches. To prove these results we build on and refine a recent technique by Göös, Lovett, Meka, Watson, and Zuckerman (STOC 2015) for decomposing high-entropy distributions into convex combinations of distributions on bit strings that are fixed on some points and highly unpredictable on others. Furthermore, a natural restriction of our definition of indifferentiability in the BRO model gives rise to a notion of indifferentiability with auxiliary input, for which we give two positive feasibility results.

The second part of this thesis aims at providing security in face of malicious implementations. We put forward the notion of self-guarding cryptographic primitives as a countermeasure to a subclass of so-called algorithm substitution attacks (ASAs). These attacks are formalized by Bellare, Paterson, and Rogaway (CRYPTO 2014) as attacks, where a big brother secretly substitutes the genuine implementation of a cryptosystem with a malicious one in order to undermine users' security. The authors also show that randomized symmetric encryption schemes are vulnerable to devastating ASAs that practically allow a big brother to steal secret keys, while to users the input-output behavior of the encryption algorithm remains undetectable from that of a genuine implementation. Detecting ASAs, even if theoretically possible, is unfortunately not an easy task. Our self-guarding primitives, however, do not rely on detection and can still prevent undesirable leakage by subverted algorithms, usually for a bounded time, if one has the guarantee that the system has been working properly during an initial phase. This secure initial phase is justified for instance, before a malicious software update is performed or before a malicious internal state is reached. We present constructions of basic self-guarding primitives for symmetric and asymmetric encryption and for signatures. We also argue that the model captures attacks with malicious hardware tokens and show how to self-guard a key exchange protocol that is based on a physical uncloneable function (PUF).

Alternative Abstract:
Alternative AbstractLanguage
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.German
Place of Publication: Darmstadt
Collation: xix, 189 Seiten
Classification DDC: 000 Allgemeines, Informatik, Informationswissenschaft > 004 Informatik
Divisions: 20 Department of Computer Science > Cryptography and Complexity Theory
Profile Areas > Cybersecurity (CYSEC)
Date Deposited: 10 Dec 2020 13:53
Last Modified: 11 Dec 2020 09:02
DOI: 10.25534/tuprints-00014550
URN: urn:nbn:de:tuda-tuprints-145508
Referees: Fischlin, Prof. Dr. Marc and Rogaway, Prof. Dr. Phillip
Refereed: 24 August 2020
URI: https://tuprints.ulb.tu-darmstadt.de/id/eprint/14550
Actions (login required)
View Item View Item