On the Security of Hash Function Combiners

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