Why isn't the provided scheme UF-CMA secure?

Question

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?

Answer 1

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:

1. 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$.
2. 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.
3. 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).