1
$\begingroup$

Suppose there are two collision-resistant hash functions $h_1$ and $h_2$ with output sizes of $n_1$ and $n_2$ respectively.

Is $H'(x) = h_1(h_2(x))$ collision resistant for the different relationships between $n_1$ and $n_2$?


This has been boggling me and my colleagues for the past few days since two different approaches contradict each other:

1st approach:

Based on the definition of collision resistance $H'$ has an output of $n_1$ length and so if we can find an attack with less complexity than $\mathcal O(2^{n_1/2})$ it is not collision-resistant.

We want $$\mathcal O(2^{n_2/2}) < \mathcal O(2^{n_1/2}) \implies \ldots \implies n_2 < n_1$$

So if $n_2 < n_1, H'$ is not collision resistant and in other cases it is


2nd approach:

Let's suppose $H'$ is not collision resistant.

Then there exist different $x_1$ and $x_2$ so that $H'(x_1) = H'(x_2)$ i.e. $h_1(h_2(x_1)) = h_1(h_2(x_2))$

That can happen if $h_2(x_1) = h_2(x_2)$, but $h_2$ is collision resistant

It can also happen if $h_1(A) = h_1(B)$ where $A = h_2(x_1)$ and $B = h_2(x_2)$ but $h_1$ is collision resistant.

We have proved that $H'$ is collision-resistant and the relationship of $n_1$ and $n_2$ doesn't matter.

$\endgroup$
4
  • $\begingroup$ Welcome to Cryptography. Is this a homework question? (We have dupes for this) $\endgroup$
    – kelalaka
    Feb 21, 2022 at 18:20
  • $\begingroup$ A hint: if $n_1 = n_2$ then the 1st approach is the same as 2nd. When they differ the $n_2 < n_1$ makes problem... $\endgroup$
    – kelalaka
    Feb 21, 2022 at 18:28
  • $\begingroup$ It is preparation for my master's applied cryptography exam, I've seen the dupes but I have not found the first approach anywhere. $\endgroup$
    – John St
    Feb 21, 2022 at 18:32
  • $\begingroup$ Based on your comment I realise the latter solutions assumes $n_1=n_2$ ? Although, how can I understand it does and is therefore not applicable to this problem? $\endgroup$
    – John St
    Feb 21, 2022 at 18:33

2 Answers 2

4
$\begingroup$

This has been boggling me and my colleagues for the past few days since two different approaches contradict each other

The reason is that these two approaches assume differing definitions of 'collision-resistant'; these two definitions are not equivalent; that is, we can find functions that meet one definition and not the other.

The first attempt uses the definition 'there is no collision finding attach that takes less that $\mathcal{O}(2^{n/2})$ operations; because $n$ is fixed, we use this as shorthand for 'an attack takes $c2^{n/2}$ operations, for some $c$ not drastically far from 1, and some reasonable definition of operation (in this case, hash function evaluation).

The problem with this definition is that it leads to some absurd conclusions, for example, SHA-256 truncated to 8 bits is 'collision resistant' by this definition. In the other direction, 1kbyte output from SHAKE-256 is not 'collision resistant', because you can find collisions with far fewer than $2^{8192/2}$ hash evaluations.

In contrast, approach 2 uses the definition 'a hash function is collision resistant if we cannot find a collision'. Expressing this formally is a bit tricky (because, as long as the input is allowed to be longer than the output, there must be collisions, we just don't know what they are), and also because this is relative to the computational resources we have (right now, SHA-256 truncated to 200 bits is collision resistant; it might not be 20 years from now as we gain more computational power); on the other hand, it is closer to the intuitive notion of 'collision resistant' that we have.

With this definition, approach 2 could be reworded as 'if we assume $H'$ is not collision resistant, then we know $x \ne y$ with $H'(x) = H'(y)$. Then either $h_2(x) = h_2(y)$ (and hence $h_2$ is not collision resistant, as we know a collision), or $h_2(x) \ne h_2(y)$, in which case we have $h_1(u) = h_1(v)$ for $u = h_2(x), v = h_2(y), u \ne v$ (and hence $h_1$ is not collision resistant, as we know a collision).

$\endgroup$
3
  • $\begingroup$ Does this mean both approaches are valid but involve different collision resistance definitions? $\endgroup$
    – John St
    Feb 21, 2022 at 19:25
  • $\begingroup$ @JohnSt: actually, I thought I made it clear that I didn't think the definition in approach 1 was really that valid; however as long as you understand the issues, you can make up your own mind $\endgroup$
    – poncho
    Feb 21, 2022 at 19:29
  • $\begingroup$ I see, thank you for your explanation, I was on board on the approach 2 ship from the start so I will use that in case this shows up in the exam, also stating which definition of collision resistance I will be using $\endgroup$
    – John St
    Feb 21, 2022 at 19:31
0
$\begingroup$

I got the chance to ask my professor and he expected the first solution, as the second assumes $ n_1 = n_2 $ (i still don't know why or where it does that).

He also explained that:

  • a $n_2$ of 1000 bits that then converts to a $n_1$ of 2 bits is considered collision resistant since you utilize the full security the 2 bits provide i.e. you get all the value that 2 bits that you "paid" for.
  • On the contrary a $n_2$ of 500 bits that then converts to a $n_1$ of 1000 bits is not considered collision resistant since you "pay" for 1000 bits of security and only use 500.

This really helped me understand the concept in an intuitive and logical way.

$\endgroup$
5
  • 1
    $\begingroup$ So, he is claiming that a hash function with a 2 bit output can be "collision resistant"? I'm sorry, but that seriously conflicts with my understanding of what "collision resistance" means... $\endgroup$
    – poncho
    Mar 2, 2022 at 22:45
  • $\begingroup$ The more I think about this, the less the professor's definition makes sense. We define terms, not because we like making up definitions, but because those definitions are useful. My definition of collision resistant (we don't know of a collision, and don't know of a practical way of finding one) lends itself as a security assumption to various security proofs of things involving hash functions. In contrast, I can't think of a single use for "for this 2-bit hash function, we can't find a collision without performing $\sqrt{2^2}$ hash evaluations" $\endgroup$
    – poncho
    Mar 3, 2022 at 19:45
  • $\begingroup$ The way I get it is thst the collision resistance definition is more of an implementation criteria. For example the 2 bit function is implemented in a way to offer the maximum resistance possible for its output length. Whether or not the final product suffices and has enough resistance to collisions (based on needs not the definition) is a different matter. $\endgroup$
    – John St
    Mar 5, 2022 at 11:45
  • $\begingroup$ That said, I agree the definition is a bit peculiar and misleading. $\endgroup$
    – John St
    Mar 5, 2022 at 11:46
  • $\begingroup$ A usage example for this definition is whether any function $H'$ composed of multiple functions is implemented to use the respective functions security to the fullest. (i.e. You can't break it easier by braking an inner function that is part of it) $\endgroup$
    – John St
    Mar 5, 2022 at 11:47

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.