Author:

Abstract:

Cryptographic hash functions form the basis of the security of today's digital environment, and find applications in numerous cryptographic systems such as tamper detection, key derivation functions, and digital signatures. Ideally, hash functions behave like a random oracle, a function that returns random outputs for each new input, but in practice such a construction does not exist. Usually, a hash function is designed to give strong confidence that it is indeed secure, and it is presumed secure until it is broken. In 2004-2005, cryptanalytic breakthroughs have raised doubts about the security of many widely employed hash functions, such as MD5 and SHA-1. As a response, in 2007 the US National Institute for Standards and Technology (NIST) announced a call for the design of a new SHA-3 hashing algorithm.This dissertation deals with the fundamental security properties of hash functions. It is divided into two parts.In the first part of the dissertation, we analyze existing hash functions and introduce design methodologies. We particularly search for the limits within the provable security framework, by considering minimalist designs with maximal security. Firstly, we look at double block length 3n-to-2n-bit compression functions based on block ciphers with an n-bit message and key space. We consider the MDC-4 hash function, and improve its collision and preimage security bounds. Next, we present a family of designs that make three cipher calls and achieve optimal collision security and very good preimage security. Furthermore, we consider the possibility of compression functions based on permutations, and provide a full security classification of all 2n-to-n-bit compression functions solely built of XOR operators and three permutations.As a final contribution of this part, we propose the family of parazoa functions as a generalization of the sponge hash function design, and prove that parazoa functions are indifferentiable from a random oracle. The sponge is a popular hash function design and many derivatives, called sponge-like functions, appeared in literature. However, these sponge-like functions do not automatically enjoy the same security guarantees as the original sponge. Our generalized parazoa family applies to a wide class of sponge-like functions, and the indifferentiability proof for parazoa naturally carries over.In the second part of the dissertation, we consider NIST's SHA-3 hash function competition from a provable security point of view. We provide a detailed survey of the five SHA-3 finalists, in which we analyze and compare their security guarantees. We consider collision, preimage, and second preimage resistance and indifferentiability of all finalists, and solve open problems where needed.