3
$\begingroup$

My guess would be that families are more secure. In which way though?

I have seen claims that hash function families can be collision resistant while single hash functions can not be. Is this true? And if so, why?

$\endgroup$
1
  • 1
    $\begingroup$ For the novice reader: Beware that we also talk about e.g. the SHA-2 family of hashes sometimes. That's a set of related functions with different output sizes. In that case we're not talking directly about hash functions that are selected using a (key) parameter. $\endgroup$
    – Maarten Bodewes
    Jan 3 at 21:43

1 Answer 1

8
$\begingroup$

Actually, it's more about security proof techniques rather than the actual security.

When we talk about the security of a cipher (e.g. randomly keyed AES), we want to express it as "there's no fast program that can distinguish AES encryption from a random Oracle (that is, one that generates random ciphertexts in response to any query)".

If we take that as an assumption (and it certainly looks like a reasonable one), we can use that to prove the security of things that use that cipher. Hence, that is a useful paradigm.

However, when we look at a single hash function, well, there does exist a fast program that exhibits a collision - it just outputs two preimages that happen to collide.

Now, we don't know what that program is (because we don't happen to have two such preimages on hand) - but it still remains that the program exists.

To talk about hash functions in this paradigm, we talk about hash function families, which avoids this simple counterexample.

$\endgroup$
6
  • 1
    $\begingroup$ Lets take some more practical question. Say we want to find a collision for a single hash function, then the birthday attack gives us a somewhat efficient way to find this collision. Does this change when talking about hash families? Because when we are given a key K, then its just the same as finding a collision for a single hash function, right? $\endgroup$
    – Wouter
    Jan 3 at 14:38
  • 2
    $\begingroup$ @Wouter: well, if you take a single member of a hash function family (e.g. the one with publicly known key $K$), it is effectively a single hash function. $\endgroup$
    – poncho
    Jan 3 at 14:52
  • $\begingroup$ I think I see where I made my mistake. To break collision resistance, a polynomial time algorithm has to exist that outputs two values $x_1$ and $x_2$ such that $h(x_1)=h(x_2)$. I assumed that such algorithms start with 0 knowledge, such as the birthday attack. However, as I now understand it, we can define this algorithm as "output the two colliding values $x_1$ and $x_2$", which must exist due to the pigeonhole principle. For a keyed hash function this is not possible since for different keys the colliding values are not the same. Is this correct? $\endgroup$
    – Wouter
    Jan 3 at 18:23
  • 3
    $\begingroup$ @Wouter: yes, that is correct. One way to look at it: the $K$ variable is a way to exclude some information about the hash function (such as a preexisting collision), while continuing to include other information (such as the internal structure of the hash function, which the attacker is free to use) $\endgroup$
    – poncho
    Jan 3 at 18:33
  • 1
    $\begingroup$ @Wouter: we assume that the program is concise (that is, of reasonable size), and so it cannot contain entries for every possible key (and so the set of keys doesn't have to be infinite, just large) $\endgroup$
    – poncho
    Jan 4 at 14:39

Your Answer

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

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