5
$\begingroup$

I was reading Boneh and Shoups's A Graduate Course in Applied Cryptography, when I stumbled upon the following exercise (I have changed the array indices to start at 1 instead of 0):

8.1 (Truncating a CRHF is dangerous). Let $H$ be a collision resistant hash function defined over $(\mathcal M,\{0,1\}^n )$. Use $H$ to construct a hash function $H'$ over $(\mathcal M,\{0,1\}^n )$ that is also collision resistant, but if one truncates the output of $H'$ by one bit then $H'$ is no longer collision resistant. That is, $H'$ is collision resistant, but $H''(x) := H' (x)[1 \ldots n - 1]$ is not.

I've tried many different approaches, but I have not been able to come up with an $H'$ that satisfies both requirements, namely that (1) $H'$ is a CRHF over its full range, and (2) is insecure over its truncated range (by one bit).

Note that if $H'$ was instead defined over $(\mathcal M , \{0,1\}^{n+1})$, then solving the exercise would be easy. Simply define:

$$ H'(x) = H(x[1 \ldots m - 1]) || x[m] \tag 1 $$

It is easy to see that this $H'$ is a CRHF over its full range $\{0,1\}^{n+1}$ by a reduction to $H$, while insecure if we truncate its last bit.

However, if we try to adapt this idea to the range $\{0,1\}^n$, for example as follows

$$ H'(x) = H(x[1 \ldots m - 1])[1 \ldots n-1] || x[m] \tag 2, $$

then the reduction to $H$ doesn't work anymore. Specifically, suppose we found a collision $H'(x) = H'(y)$, where $x = \tilde x || b_x \neq y = \tilde y || b_y$. Since this is a collision for $H'$, we must have $b_x = b_y$, so $\tilde x \neq \tilde y$. But notice that $\tilde x$ and $\tilde y$ is not necessarily a collision for $H$. Rather, it is a near-collision in the first $n-1$ output bits, i.e., $H(\tilde x)[1 \ldots n -1] = H(\tilde y)[1 \ldots n -1]$. But that doesn't imply $H(\tilde x) = H(\tilde y)$.

Thus my question: how do you actually solve this exercise as stated?

Note that one could try other constructions similar to (2). For instance $H'(x) = H(\tilde x) \oplus b_x$, where we take the full output of $H$ on the substring $\tilde x$ and XOR the last bit of that hash with the last bit of $x$. But again, one can at most show that this leads to a near-collision for $H$, but not a full collision.

The only reference I could find in the literature regarding this problem, is the following statement from Boneh and Boyen:

Kelsey [13] observed that truncating a collision resistant hash function need not be collision resistant.

And Kelsey [13] is this (.mov video) 2005 Crypto Rump session presentation by Kelsey, using more or less the same slides as in this presentation: https://csrc.nist.gov/CSRC/media/Events/First-Cryptographic-Hash-Workshop/documents/Kelsey_Truncation.pdf. However, what he shows is that truncating can lead to problems if your hash has near-collisions. But he doesn't actually exhibit an explicit collision resistant hash function with near-collisions --- which is essentially what this exercise is asking us to provide!

$\endgroup$
1
  • $\begingroup$ How big is $\mathcal{M}$? Because an obvious answer is that if $\mathcal{M} = \{0,1\}^n$ then the identify function is CR but, of course, the truncated version is not. $\endgroup$
    – AntonioFa
    May 26, 2019 at 15:55

1 Answer 1

6
$\begingroup$

Assume there exists a collision-resistant $H$ from $\mathcal M$ to $\{0,1\}^n$; that $\mathcal M$ has at least two distinct elements $x_0$ and $x_1$, which we can exhibit (otherwise, any function from $\mathcal M$ to any set is collision-resistant); and $n>0$ (otherwise we can't define $H''$).

Proposition: there exists a collision-resistant function $H'$ from $\mathcal M$ to $\{0,1\}^n$ such that $H''$ from $\mathcal M$ to $\{0,1\}^{n-1}$ with $H''(x)\;=\;H'(x)[1\ldots n -1]$ is not collision-resistant.

Proof: Define function $G$ from $\mathcal M$ to $\{0,1\}^{n-1}$ by $G(x)\;=\;H(x)[1 \ldots n -1]$.

Define function $\hat H$ from $\mathcal M$ to $\{0,1\}^n$ by $\hat H(x)\;=\;\begin{cases} 1\|G(x_0)&\text{if }x=x_1\\ 0\|G(x)&\text{otherwise} \end{cases}$

If $G$ is not collision-resistant, define $H'=H$, from which it follows that $H''$ is $G$. Function $H'$ is collision-resistant, because it is $H$, which is collision-resistant; but $H''$ is not collision-resistant, since a colliding message pair for $G$ can be found, and is a colliding message pair for $H''$.

Otherwise (that is, if $G$ is collision-resistant), define $H'=\hat H$, from which it follows that $H''(x)\;=\;\begin{cases} G(x_0)&\text{if }x=x_1\\ G(x)&\text{otherwise} \end{cases}$. Function $H'$ is collision-resistant, because any colliding message pair for $H'$ would be one for $G$, which is collision-resistant; but $H''$ is not collision-resistant, because $(x_0,x_1)$ is a colliding message pair.

$\endgroup$
5
  • $\begingroup$ +1 I really like the cleverness of this answer! It is akin to the non-constructive proof that an irrational number raised to an irrational number can be rational. However, I was hoping there would be a constructive solution though. $\endgroup$
    – hakoja
    Mar 14, 2018 at 16:24
  • $\begingroup$ @hakoja: The issue is that it is asked $H'$ of $n$-bit and we start from something both $n$-bit (rather than $n-1$) and only collision-resistant (rather than secure in the ROM). Change any of these two, and we can remove the If $G$ is not collision-resistant branch of the argument. $\endgroup$
    – fgrieu-onstrike
    Mar 14, 2018 at 19:54
  • 1
    $\begingroup$ Don't we have to prove that the collision is not hard to find? Because I don't understand how a collision by itself should be proof of non collision-resistance of H''. $\endgroup$
    – Kranta
    May 25, 2019 at 15:53
  • $\begingroup$ Kranta, you need some minimum amount of reputation to comment. Please consider asking a question rather than commenting if something is unclear. $\endgroup$ May 25, 2019 at 18:00
  • $\begingroup$ @Kranta: somewhat I read your comment only now. I admit my answer is paradoxical, in that I don't tell how to determine if G is not collision-resistant. But I have no better answer. $\endgroup$
    – fgrieu-onstrike
    Apr 13, 2022 at 1:57

Your Answer

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

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