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!