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?
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– Maarten Bodewes ♦2024-01-03 21:43:39 +00:00Commented Jan 3, 2024 at 21:43
Add a comment |
1 Answer
$\begingroup$ $\endgroup$
6 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.
- 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– Wouter2024-01-03 14:38:00 +00:00Commented Jan 3, 2024 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$2024-01-03 14:52:43 +00:00Commented Jan 3, 2024 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– Wouter2024-01-03 18:23:45 +00:00Commented Jan 3, 2024 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$2024-01-03 18:33:11 +00:00Commented Jan 3, 2024 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$2024-01-04 14:39:59 +00:00Commented Jan 4, 2024 at 14:39