Score:1

Is the composition of collision resistant functions H' = h1(h2()) collision resistant?

id flag

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.

kelalaka avatar
in flag
Welcome to [cryptography.se]. Is this a homework question? (We have dupes for this)
kelalaka avatar
in flag
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...
John St avatar
id flag
It is preparation for my master's applied cryptography exam, I've seen the dupes but I have not found the first approach anywhere.
John St avatar
id flag
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?
Score:4
my flag

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).

John St avatar
id flag
Does this mean both approaches are valid but involve different collision resistance definitions?
poncho avatar
my flag
@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
John St avatar
id flag
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
Score:0
id flag

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.

poncho avatar
my flag
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...
poncho avatar
my flag
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"
John St avatar
id flag
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.
John St avatar
id flag
That said, I agree the definition is a bit peculiar and misleading.
John St avatar
id flag
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)
mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.