Create a CR hash function where truncating one bit leads to collisions

Question

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!

Answer 1

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.