4
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ There are families of Universal Hash Functions, and selecting a member of such a family is a little like choosing a cipher key. See en.wikipedia.org/wiki/Universal_hashing (in which the term "key" refers to the input to the hash function, not to any property of the hash function or the family it belongs to). $\endgroup$ Feb 21, 2014 at 0:49

1 Answer 1

3
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ "Usually MACs are not called hash functions (with key)"; this is certainly true, because often a MAC is not a secure hash function against someone who knows the MAC key. Nothing in the definition of a MAC requires it to be, and a lot of real MACs in practice (e.g. CMAC) don't even have preimage resistance if you know the key. $\endgroup$
    – poncho
    Feb 15, 2014 at 20:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.