TU Darmstadt / ULB / TUprints

On the Foundations of Key Exchange

Brzuska, Christina (2013)
On the Foundations of Key Exchange.
Technische Universität
Ph.D. Thesis, Primary publication

[img]
Preview
Text
thesis-tuprint-2013.pdf
Copyright Information: CC BY-NC-ND 2.5 Generic - Creative Commons, Attribution, NonCommercial, NoDerivs .

Download (1MB) | Preview
Item Type: Ph.D. Thesis
Type of entry: Primary publication
Title: On the Foundations of Key Exchange
Language: English
Referees: Fischlin, Prof. Dr. Marc ; Warinschi, Prof. Dr. Bogdan
Date: 2013
Place of Publication: Darmstadt
Date of oral examination: 1 October 2012
Abstract:

Key exchange protocols allow two parties to agree on a shared secret over an untrusted channel. A huge number of scientific works on key exchange have been published since the discovery of the first key exchange protocol, designed in 1976 by Diffie and Hellman [DH76]. The most prominent of these works is the game-based security model by Bellare and Rogaway [BR93], published in 1993 and, today, known as the "golden standard" for the security of key exchange protocols.

The main purpose of key exchange protocols is to establish keys for a symmetric-key protocol such as a secure channel. Ideally, if both, the key exchange protocol and the channel protocol, are secure, then we would hope that they can be securely composed. While this is true for simulation-based security models [Can01, KT11, BPW03], game-based models usually lack composition theorems altogether. That is unfortunate, as they are often more suitable for real-life protocols such as TLS.

Our first two composition theorems address the composition of BR-secure key exchange protocols with arbitrary symmetric-key protocols. We formally establish that an additional condition is necessary, namely, the key exchange requires a public session matching algorithm.

Maybe surprisingly, many important key agreement protocols are not BR-secure due to the popular technique of explicit key confirmation. We devise a more flexible yet sufficiently strong model for this class of protocols and prove that it is closed under reductions. Overall, we devellop a tool for the modular analysis of real-life protocols and exemplify the use of our framwork on a profile of the TLS protocol.

As in the case of most practical cryptography, information-theoretic security for key exchange protocols is out of reach, i.e., impossible in a formal sense. Therefore, protocols such as TLS rely on computational assumptions, e.g., the Diffie-Hellmann assumption or the hardness of factoring numbers. As the security of protocols is tightly related to the underlying complexity assumptions, researchers have been striving for simpler and weaker assumptions. The holy grail in this area is to base key agreement, one-way functions or simply any type of cryptography on the mere assumptions that NP does not equal P [FF93, BT03, AGGM06]. While positive results in this area remain elusive, there has been some recent progress on negative results [HMX10, PTV11], showing that cryptographic primitives such as hash functions cannot be based on NP-hardness unless coAM is contained in NP. In this thesis, we provide two oracle results that show that, via relativizing techniques, these negative results do not carry over to key agreement and regular one-way functions. In particular, we give an oracle relative to which the intersection of NP and coNP is easy while infinitely many often secure key agreement exists; and we give an oracle relative to which languages in the intersection of AM and coAM is easy while regular function families exists that are infinitely many often one-way.

Alternative Abstract:
Alternative AbstractLanguage

Ein Schlüsselaustausch ermöglicht zwei Parteien, sich über einen unsicheren Kanal auf einen gemeinsamen, geheimen Schlüssel zu einigen. Diffie und Hellman [DH76] entwickelten 1976 das erste Schlüsselaustauschprotokoll und legten damit den Grundstein für ein fruchtbares Forschungsgebiet. Eine der wichtigsten Arbeiten auf diesem Gebiet ist das spielebasierte Sicherheitsmodell von Bellare und Rogaway [BR93] aus dem Jahre 1993, welches heutzutage als "goldener Standard" fur die Sicherheit von Schlüsselaustauschprotokollen gilt.

Ein Schlüsselaustausch wird gemeinsam mit einem anderen Protokoll ausgeführt, welches die abgeleiteten Schlüssel verwendet. Idealerweise hoffte man, daß ein BR-sicherer Schlüsselaustausch und ein sicheres Anwendungsprotokoll auch bei gemeinsamer Ausführung sicher bleiben. Diese Aussage ist für simulationsbasierte Sicherheitsmodelle bekannt [Can01, KT11, BPW03], für spielebasierte Modelle verfügen wir allerdings oft über kein einziges Kompositionstheorem. Das ist insofern ungünstig, als daß spielebasierte Modelle für praktische Protokolle wie TLS besser geeignet sind.

Unsere ersten zwei Kompositionstheoreme befassen sich mit der Komposition von BR-sicheren Protokollen mit Anwendungsprotokollen, die auf symmetrischen Schlüsseln basieren. Wir stellen dabei durch einen formalen Beweis fest, daß es notwendig ist, daß der Schlüsselaustausch einen Public Session Matching Algorithmus besitzt.

Überraschenderweise sind einige bedeutende Schlüsselaustauschverfahren nicht BR-sicher, da sie sogenannte Key Confirmation verwenden. Wir entwickeln daher ein zugleich flexibleres und starkes Modell für diese Klasse von Protokollen und zeigen, daß das Modell unter Reduktionen abgeschlossen ist. Insgesamt bieten unsere Kompositionsresultate eine Technik zur modularen Analyse praktischer Protokolle, was wir anhand einer abstrahierten Version von TLS aufzeigen.

Da praktische Kryptographie und Schlüsselaustausch insbesondere keine informationstheoretische Sicherheit bieten kann, basieren Protokolle wie TLS auf komplexitätstheoretischen Annahmen wie z.B. der Diffie-Hellman Annahme. Da die Sicherheit eines Protokolls auf dem Schwierigkeitsgrad des zugrundeliegenden Problems beruht, ist die Studie schwächerer, einfacher Annahmen eine wichtige Forschungsrichtung. Das größte offene Problem auf diesem Gebiet ist es, Schlüsselaustausch, One-Way-Funktionen oder andere Primitive darauf zu reduzieren, daß NP ungleich P ist [FF93, BT03, AGGM06]. Kürzlich konnten Unmöglichkeitsresultate zeigen, dass z.B. Primitive wie Hash-Funktionen nicht auf NP-schwierige Probleme reduziert werden können, sofern coAM nicht in NP liegt [HMX10, PTV11].

In dieser Arbeit zeigen wir mittels zweier Orakelseparierungen, dass es nicht möglich ist, die vorgenannten Unmöglichkeitsresultate mithilfe von relativierenden Reduktionen auf Schlüsselaustausch und reguläre One-Way-Funktionen zu übertragen. Relativ zu unserem ersten Orakel sind Sprachen in der Schnittmenge von NP und coNP einfach, während unendlich häufig sicherer Schlüsselaustausch existiert. Unser zweites Orakel erreicht, dass die Schnittmenge von AM und coAM in P enthalten ist, während zugleich eine Familie regulärer Funktionen unendlich oft one-way ist.

German
URN: urn:nbn:de:tuda-tuprints-34147
Classification DDC: 000 Generalities, computers, information > 004 Computer science
Divisions: 20 Department of Computer Science > Cryptography and Complexity Theory
Date Deposited: 13 Jun 2013 07:41
Last Modified: 09 Jul 2020 00:20
URI: https://tuprints.ulb.tu-darmstadt.de/id/eprint/3414
PPN: 322668743
Export:
Actions (login required)
View Item View Item