On the Security of Hash Function Combiners

Lehmann, Anja (2010)
On the Security of Hash Function Combiners.
Technische Universität Darmstadt
Dissertation, Erstveröffentlichung

URL / URN: urn:nbn:de:tuda-tuprints-20949

Kurzbeschreibung (Abstract)

A hash function is an algorithm that compresses messages of arbitrary length into short digests of fixed length. If the function additionally satisfies certain security properties, it becomes a powerful tool in the design of cryptographic protocols. The most important property is collision-resistance, which requires that it should be hard to find two distinct messages that evaluate to the same hash value. When a hash function deploys secret keys, it can also be used as a pseudorandom function or message authentication code. However, recent attacks on collision-resistant hash functions caused a decrease of confidence that today’s candidates really have this property and have raised the question how to devise constructions that are more tolerant to cryptanalytic results. Hence, approaches like robust combiners which “merge” several candidate functions into a single failure-tolerant one, are of great interest and have triggered a series of research. In general, a hash combiner takes two hash functions H0,H1 and combines them in such a way that the resulting function remains secure as long as at least one of the underlying candidates H0 or H1 is secure. For example, the classical combiner for collision-resistance simply concatenates the outputs of both hash functions Comb(M) = H0(M)||H1(M) in order to ensure collision-resistance as long as either of H0,H1 obeys the property. However, this classical approach is complemented by two negative results: On the one hand, the combiner requires twice the output length of an ordinary hash function and this was even shown to be optimal for collision-resistance. On the other hand, the security of the combiner does not increase with the enlarged output length, i.e., the combiner is not significantly stronger than the sum of its components. In this thesis we address the question if there are security-amplifying combiners where the combined hash function provides a higher security level than the building blocks, thus going beyond the additive limit. We show that one can indeed have such combiners and propose a solution that is essentially as efficient as the concatenated combiner. Another issue is that, so far, hash function combiners only aim at preserving a single property such as collision-resistance or pseudorandomness. However, when hash functions are used in protocols like TLS to secure http and email communication, they are often required to provide several properties simultaneously. We therefore introduce the notion of robust multi-property combiners and clarify some aspects on different definitions for such combiners. We also propose constructions that are multi-property robust in the strongest sense and provably preserve important properties such as (target) collision-resistance, one-wayness, pseudorandomness, message authentication, and indifferentiability from a random oracle. Finally, we analyze the (ad-hoc) hash combiners that are deployed in the TLS and SSL protocols. Nowadays, both protocols are ubiquitous as they provide secure communication for a variety of applications in untrusted environments. Therein, hash function combiners are deployed to derive shared secret keys and to authenticate the final step in the key-agreement phase. As those established secret parameters are subsequently used to protect the communication, their security is of crucial importance. We therefore formally fortify the security guarantees of the TLS/SSL combiner constructions and provide the sufficient requirements on the underlying hash functions that make those combiners suitable for their respective purposes.

Typ des Eintrags:

Dissertation

Erschienen:

2010

Autor(en):

Lehmann, Anja

Art des Eintrags:

Erstveröffentlichung

Titel:

On the Security of Hash Function Combiners

Sprache:

Englisch

Referenten:

Fischlin, Dr. Marc ; Dodis, Prof. Dr. Yevgeniy

Publikationsjahr:

23 März 2010

Ort:

Darmstadt

Verlag:

Technische Universität

Datum der mündlichen Prüfung:

19 März 2010

URL / URN:

urn:nbn:de:tuda-tuprints-20949

Kurzbeschreibung (Abstract):

Alternatives oder übersetztes Abstract:

Alternatives Abstract

Sprache

Hash Funktionen verarbeiten Eingaben beliebiger Länge und bilden diese auf Zeichenketten mit kurzer, fester Länge ab. Besitzen solche Funktionen zusätzlich bestimmte Sicherheitseigenschaften, sind sie ein wichtiger Bestandteil von zahlreichen kryptographischen Protokollen. Die wohl wichtigste Eigenschaft von Hash Funktionen ist Kollisionsresistenz. Diese verlangt, dass es schwierig ist, zwei verschiedene Nachrichten zu finden, die durch die Funktion auf den selben Hashwert abgebildet werden. Setzen Hash Funktionen zudem geheime Schlüssel ein, können sie auch als Pseudozufallsfunktionen oder Message Authentication Codes dienen. Erfolgreiche Angriffe gegen kollisionsresistente Hash Funktionen ließen allerdings die Frage aufkommen, wie solche Funktionen besser vor kryptanalytischen Resultaten geschützt werden können. Eine Möglichkeit stellen sogenannte Robust Combiner dar, die verschiedene Varianten eines kryptographischen Verfahrens kombinieren, um so die gewünschte Robustheit gegen neue Angriffe zu bieten. Im Allgemeinen besteht ein Hash Combiner aus zwei Hash Funktionen, die so zu einer Funktion zusammengesetzt werden, dass deren Sicherheit garantiert ist, solange mindestens eine der unterliegenden Funktionen sicher ist. Für die Eigenschaft der Kollisionsresistenz besteht der klassische Combiner aus dem einfachen Konkatenieren zweier Hashwerte Comb(M) = H0(M)||H1(M). Die so kombinierte Hash Funktion ist kollisionsresistent, solange mindestens eine der Funktionen H0,H1 diese Eigenschaft besitzt. Der klassische Combiner für Kollisionsresistenz hat allerdings auch Nachteile: Zum einen, erfordert er eine Ausgabe, die doppelt so lang ist wie die einer einzelnen Hash Funktion. Zum anderen steigt die Sicherheit nicht im gleichen Masse wie die Ausgabelänge, denn der Combiner ist im Wesentlichen nur so stark wie die Summe der Einzelsicherheiten. In dieser Arbeit betrachten wir daher die Frage, ob Combiner existieren, welche die Sicherheit beider unterliegenden Funktionen sogar verstärken können. Dabei stellen wir eine Konstruktion vor, die diese Eigenschaft erfüllt und dabei nahezu genauso effizient ist wie der klassische Ansatz. Weiterhin wurden Hash Combiner bisher nur so konzipiert, dass sie einzelne Eigenschaften, wie z.B. Kollisionsresistenz oder Pseudozufälligkeit, erhalten. Wenn Hash Funktionen allerdings in Protokollen wie TLS eingesetzt werden, müssen sie darin oft mehrere Eigenschaften gleichzeitig erfüllen. Aus diesem Grund führen wir den Begriff der Robust Multi-Property Combiner ein und diskutieren zunächst verschiedene Definitionsmöglichkeiten und deren Auswirkungen. Anschließend werden Konstruktionen für solche Combiner vorgestellt, die bis zu sechs wichtige Eigenschaften gleichzeitig absichern. Im letzten Teil der Arbeit untersuchen wir die Hash Combiner die in den TLS und SSL Protokollen eingesetzt werden. Beide Protokolle ermöglichen eine sichere Kommunikation in nicht-vertrauenswürdigen Umgebungen und sind daher in zahlreichen Anwendungen zu finden. Zur Erzeugung des notwendigen Schlüsselmaterials setzen sowohl TLS als auch SSL eigene Hash Combiner ein. Da die so ausgehandelten Schlüssel anschließend die Grundlage der abgesicherten Kommunikation bilden, ist deren Sicherheit von großer Bedeutung. Aus diesem Grund analysieren wir die vorgeschlagenen Combiner Konstruktionen und zeigen, unter welchen Annahmen die gewünschte Sicherheit erreicht werden kann.

Deutsch

Sachgruppe der Dewey Dezimalklassifikatin (DDC):

000 Allgemeines, Informatik, Informationswissenschaft > 004 Informatik

Fachbereich(e)/-gebiet(e):

20 Fachbereich Informatik

Hinterlegungsdatum:

25 Mär 2010 06:46

Letzte Änderung:

05 Mär 2013 09:33

PPN:

Referenten:

Fischlin, Dr. Marc ; Dodis, Prof. Dr. Yevgeniy