On an exam I recently took, one of the questions was:
Consider the following signature scheme. The public key is $(p,g,g^x)$, where $p$ is a large prime number. $g$ is a generator of $\mathbb Z^*_p$, and $x$ is a random number in $\mathbb Z_{p-1}$. The secret key is $x$. The scheme also uses a public hash $H(M)$ that maps arbitrary messages to $\mathbb Z_{p-1}$. The signature algorithm signs message $M$ as $\mathsf{sig}=\left(g^ {H(M)}\right)^x\bmod p$. To verify a signature $\mathsf{sig}$ for message $M$, the verifier checks if $\mathsf{sig}=\left(g^x\right)^{H(M)}\bmod p$.
Show that this signature scheme isn’t UF-CMA.
I'm still thinking about this question. My answer was that an attacker would be able to compute the private key by using $\log_g(g^x)$ to find $x$. From here, an attacker can determine $H(M)$ from any signature assuming $\left(g^ {H(M)}\right)^x<p$. The attacker can compute $\left(g^x\right)^i\bmod p$ in range $(0,p-2)$ until they find a match.
I know my answer isn't correct. But I don't think I understand what is being asked of us. Supposedly the scheme uses a public hash function, so we shouldn't need to solve for $H(M)$ if we can put any message into it.
Are we supposed to solve for $M$ given a signature...? If so, should we take $\mathsf{sig}=\left(g^{H(M)}\right)^x\bmod p$ and rewrite the signature equation as $\left(g^{H(M)}\times g^x\right)\bmod p=1$ and solve for the modular inverse to get $g^{H(M)}$?
In short, I don't think I understand what the question is asking for, could someone explain it to me?