Why do we need to hash both the message and the $h$ value in ElGamal signature? The professor left us a question on ElGamal signatures:


  Given the hash function $H$ and message $M$, choose a random $r$ and compute $h=g^r$ and $H(M||h)$. Show that, if $H(M)$ is used instead of $H(M||h)$, the signature can be existentially forged.


I am struggling with the problem, and I think that maybe we can get one known message signed twice with different $(M, c_1, h_1)$ and $(M, c_2, h_2)$, and then use that to sign some other messages $M'$, but I have no idea how to proceed. Can anyone give me some hints?
It's not a complete answer because an adversary needs control on the random choice of a signing algorithm.


First let me define ElGamal signature to not get lost in notation.
$x \in N$ is the secret key.
$p$ is a prime, it defines $Z_p^*$.
$g$ is a generator of $Z_p^*$.
$y=g^x$ and the public key is $(p, g, g^x)$.
Then $k$ is picked at random from $0&lt;k&lt;p-1$,
$r = g^k \bmod p$, $s = (H(m) - xr)k^{-1} \bmod (p-1)$ and the signature is 
$(r,s)$.
Suppose we know two signatures of the message $m$ for different $k$-s:
$\sigma_1 = (g^{k_1} \bmod p, (H(m) - xr)k_1^{-1} \bmod (p-1)) = (r_1, s_1)$ and 
$\sigma_2 = (g^{k_2} \bmod p, (H(m) - xr)k_2^{-1} \bmod (p-1)) = (r_2, s_2)$.


Let $\sigma_3=(r_1r_2 \bmod p, s_1 + s_2 \bmod (p-1))$.


Verification of $\sigma_3$ leads us to an equation $(k_1+k_2)(k_1^{-1}+k_2^{-1})\equiv 1 \bmod (p-1)$. If an attacker can choose $k_1, k_2$, then he can probably find proper $p$ and $k_1, k_2$. Otherwise - still a problem.