Hash functions with or without secret key

Question

The classical definition of hash functions (found in books) are OK, but when studying a little more there is a lot of notions that seem ambiguous (contradictory) to me :

• Sometimes we have hash functions that need a secret key $k$

• Certain papers that design hash functions speak about a family of hash functions, meaning I think, that there is a parameter $k$ that we choose at random to select a function among this family. We could think that this parameter is a secret key, or not, that is not clear for me...

• Sometimes we have hash functions that doesn't need a secret key. Besides, if we consider a hash function like SHA-2, we don't need any secret key to use it, nor we need to select such $k$ at random and I know that for any implementation SHA-2 gives the same result for the same input (this function is deterministic...)

• I've read that a hash function that need a secret key is in fact a MAC. However, some papers that speak about a hash function needing a key doesn't say that this is in fact a MAC.

So, I have several questions:

• When we want to use a particular collision-resistant hash function (in order to use it for a signature), from a specification of a hash function family, how I have to choose the parameter $k$ ?

• Is a hash function that need a secret key necessarily a MAC ?

• If not, is this kind of hash function usable like any other collision-free hash function ? For using it in a signature (for example) ?

Thank you.

Answer 1

The parameter $k$ appeared in the definitions of hash functions, since many properties are difficult to formulate for a single concrete hash function. For instance, what would it mean that SHA-256 is collision resistant? Clearly, there are values that collide, and there exists a very short algorithm that outputs a collision in a small constant time. To meaningfully define collision resistance, theoreticians started talking about infinite families of hash functions $$ H = \{H_k\,|\,k\in \mathbb{N}\}, $$ so that the family $H$ is collision resistant if an adversary needs to spend asymptotically $O(2^{n/2})$ time to find collisions for $n$-bit hash function from the family. Though the definition becomes sound, it does not help in practice since it is hard to expand the single SHA-256 to an infinite family of functions.

This parameter $k$, introduced solely to simplify the theory of hash functions, is often confused with a secret key. A hash function might take a key $K$ as an input, usually to form a message authentication code (MAC). A MAC should be difficult to forge, i.e. it is hard to find $M$ and tag $T$ such that $$ H(K,M) = T $$ without knowing $K$ (but knowing tags for other messages).

To answer your questions now

1. Whenever you need a collision-resistant hash function you choose a concrete function according to your security requirements and environment restrictions. You do not bother about families, they are for theoreticians.

2. It is usually MAC, but can also be a key derivation function. Usually MACs are not called hash functions (with key). When we talk about hash functions with key, it is quite often a usual hash function with part of its input made secret.