2
$\begingroup$

A function is $(\varepsilon, t)$-collision resistant if there is no boolean circuit (using "not", "and", "or") of size at most $t$ which outputs a collision with probability at least $\varepsilon$.

Let $h_0:\{0,1\}^{2m}\rightarrow\{0,1\}^m$ be a $(\varepsilon, t)$-collision resistant hash function and $i\in\mathbb{N}_{\geq 1}$.
Define a hash function $h_i: \{0,1\}^{2^{i+1}\cdot m}\rightarrow \{0,1\}^m$ recursively using $h_{i-1}$ in the following way:
Interpret the bit string $x\in \{0,1\}^{2^{i+1}\cdot m}$ as $x=x_1 x_2$, where both $x_1,x_2\in \{0,1\}^{2^i\cdot m}$.

Then the hash value $h_i(x)$ is defined as

$$h_i(x)=h_0(h_{i-1}(x_1)h_{i-1}(x_2)).$$

For which $(\varepsilon_i, t_i)$ is $h_i$ $(\varepsilon_i, t_i)$-collision resistant?
And can we successfully use the birthday attack on this hash function to find collisions?

Improve this question
$\endgroup$
2
  • $\begingroup$ Welcome to CS.StackExchange! FYI, you're more likely to get good answers to this kind of question on Cryptography.StackExchange. $\endgroup$ Commented Jan 17, 2013 at 22:39
  • $\begingroup$ By the way, Shu, may I ask: is this homework? (It looks like something that would be a good homework problem!) If it is homework, can you show us what you've tried so far, and where you've gotten stuck? $\endgroup$ Commented Jan 17, 2013 at 22:40

2 Answers 2

Reset to default
3
$\begingroup$

The birthday attack applies to any hash-function, regardless of its structure, and also to $h_i$.

For your first question, here is a possible hint. Note that

  • if we can find a collision in $h_i$ then we can find a collision in $h_0$ (by considering the top-most $h_0$, for instance).
  • if we can find a collision in $h_0$ then, we can find a collision for $h_i$ (by replacing one of the inner-most $h_0$ with it's collision).
Improve this answer
$\endgroup$
6
  • $\begingroup$ I don't really understand how I can use this hint for the $(\varepsilon, t)$-resistance proof. Could you elaborate on that? $\endgroup$ Commented Jan 13, 2013 at 20:08
  • $\begingroup$ if there is a $(\epsilon,t)$-circuit that finds collision for $h_0$, then by the second claim, the same(?) circuit finds a collision for $h_i$? $\endgroup$ Commented Jan 13, 2013 at 20:42
  • $\begingroup$ What do you mean by $(\varepsilon, t)$-circuit? Doesn't $(\varepsilon, t)$-collision resistant mean that there is NO circuit of the properties stated above? $\endgroup$ Commented Jan 13, 2013 at 20:57
  • 1
    $\begingroup$ yes, $(\epsilon,t)$-resistant means there is no such circuit. So if you know $h_0$ is $(\epsilon,t)$-resistant, and you know that a circuit for $h_i$ implies a circuit for $h_0$, you can infer that $h_i$ is also $(\epsilon,t)$-resistant (assuming it is exactly the same circuit, or otherwise, change $t$ accordingly). $\endgroup$ Commented Jan 13, 2013 at 21:40
  • $\begingroup$ And how do we know (concretely) for which $(\varepsilon, t)$ the function is collision resistant? $\endgroup$ Commented Jan 14, 2013 at 1:57
2
$\begingroup$

There's a problem with the formal details of your definition of collision-resistance: if we take it seriously, then no function (whose output is shorter than its input) can ever be collision-resistant.

By the pigeonhole property, it is guaranteed that there exists some pair of messages $x,x' \in \{0,1\}^{2m}$ such that $h_0(x)=h_0(x')$ but $x\ne x'$. Therefore, there exists some circuit $C$ that outputs a collision in $h_0$ (just take the circuit that has $x$ and $x'$ hardcoded in it and that outputs $x,x'$; it will do, and it is very small, with fewer than $t$ gates for any reasonable value of $t$). Consequently, no matter what function $h_0$ you pick, it won't be collision-resistant.

Similarly, no matter what function you pick, $h_i$ will never be collision-resistant.

Therefore, the question is framed poorly. I suspect you will want to go back to the drawing board and think more carefully about what exactly you want to know.

Improve this answer
$\endgroup$
1
  • $\begingroup$ D.W. that's a good point. I automatically assumed we are talking about a family of hashes $\{h_0\}$ and look for a single $C$ that works for all of them. A single hash function never makes sense, almost always people actually mean a sample out of a family. But this indeed should be clarified by the OP. $\endgroup$ Commented Jan 18, 2013 at 4:17

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.