Q:

Why is $h(H, m) = E(m, H) \oplus m$ insecure?

I am taking a cryptography class on Coursera. I learned that the compression function $h(H, m) = E_m(H) \oplus m$ is insecure (even though other variants like Davies­-Meyer or Miyaguchi-Preneel are secure).  Why is this compression function insecure?   What is the attack?
(See also Why are the Davies-Meyer and Miyaguchi-Preneel constructions secure? for a related question.)

A:

Well, the problem with $h(H,m) = E_m(H) \oplus m$ is that it makes the preimage attack easier than we'd expect; with a 128 bit hash, we'd hope that it'd take around $2^{128}$ attempts to find a preimage; with this compression function, we can find a preimage with only around $2^{64}$ effort.
This happens because this compression function is reversible; with a fixed m and a target value J, as one can efficiently find the H with $h(H,m)=J$, namely, $H = D_m(J \oplus m)$ (where $D_m$ is the decryption operation using $m$ as a key).
Here is how we use this property to find a message that hashes to $J$:

We select $2^{64}$ distinct initial blocks $m_1, m_2, ..., m_{2^{64}}$, and compute the $2^{64}$ values $h(H_0, m_i)$, where $H_0$ is the fixed IV of this hash function
We select $2^{64}$ distinct final blocks $n_1, n_2, ..., n_{2^{64}}$ and compute the $2^{64}$ values $h^{-1}(J, n_i)$, where $h^{-1}$ is the compression function run backwards.

Search the two lists for a common value; assuming a 128 bit hash, a collision is likely.  If we find a pair with $h(H_0, m_i) = h^{-1}(J, n_j)$, when we have found a message $m_i || n_j$ which hashes to $J$.

