an attacker would be able to compute the private key by using $\log_g(g^x)$ to find $x$.
No, because we are supposed to assume/understand that the public key really is $(p,g,g^x\bmod p)$, and that $p$ is such that the Discrete Logarithm Problem is hard. A meta reason is that if it was possible to compute the private key from the public key without even considering how the signature system works, that would a dumb question.
From here, an attacker can determine $H(M)$ from any signature assuming $\left(g^{H(M)}\right)^x<p$.
True, but
- it's near impossible that $\left(g^{H(M)}\right)^x<p$ with $x$ and $H(M)$ essentially random in $\mathbb Z_{p-1}$
- guessing $H(M)$ from the signature is not a goal of the attacker under UF-CMA.
What is being asked of us… Are we supposed to solve for $M$ given a signature?
No. We are asked to prove that the signature scheme is not UnForgeable under Chosen Message Attack. That is, we are asked an algorithm to produce (with non-negligible probability) a Forgery under Chosen Message Attack.
A "Forgery" is a message/signature pair $(M,\mathsf{sig})$ that passes the verifier check, but somewhat (see note) was not obtained legitimately/per the normal signature procedure (which involves the private key). The "Chosen Message Attack" part is to tell that our algorithm can ask for signature of message(s) that it chooses.
Recommendations:
Briefly explain that/why the signature system is sound, that is such that the verification procedure can be carried with the public key, message and signature, and succeeds if the signature was produced legitimately.
Give an algorithm to make a forgery for this signature scheme.
Hint: The algorithm will not need to ask for signature (the CMA thing). It just accepts the public key and a message $M$, and produces a valid signature $\mathsf{sig}$.
This attack can be generalized to any sound signature system such that the verification procedure reduces to comparing the signature to something computed from message and public key only.
Note: There are three degrees of attack. It's not clear (and it's not important) which of the first two the question is about:
- In an Universal forgery (breaking the UUF-CMA property), the message $M$ in the forgery $(M,\mathsf{sig})$ is an input of the algorithm, and the algorithm is prohibited from asking the signature of $M$.
- In an Existential forgery (breaking the EUF-CMA property), the algorithm does not win the experiment with a forgery $(M,\mathsf{sig})$ if it has submitted the message $M$ for signature.
- In a forgery breaking the Strong EUF-CMA property, the algorithm does not win the experiment with a forgery $(M,\mathsf{sig})$ if it has submitted the message $M$ for signature and obtained $\mathsf{sig}$ as signature.
An algorithm that succeeds in 1 (resp. 2) can easily be turned into one that succeeds in 2 (resp. 3).
