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

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. 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?

• The verification algorithm checks if the signature (which should only be computable using the secret key) equals something efficiently computable using only the public key and the message. Do you see the problem? May 2 at 6:51
• The question is problematic as the scheme can be shown to be UF-KOA insecure i.e. chosen/known messages are not required to produce forgeries. You should be able to produce a valid signature $\mathsf{sig}$ for any message $M$ without knowledge of $x$. May 2 at 7:31

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.

True, but

• it's near impossible that $$\left(g^{H(M)}\right)^x 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).

• I just want to verify what you said, I believe I understand: Given a signature for a message x, we want to find an identical signature for unknown message y. Would we be able to find this using random self-reducability? Or am I on the wrong track? May 3 at 1:32
• @smitc29: no, that's not the goal, or the mean. The assigned goal is stated in the answer. And it is met if given the public key, and an arbitrary message $M$, we can obtain a signature that is accepted as valid for message $M$. That is easy if we look at the condition, stated in the question, that the verifier checks.
– fgrieu
May 3 at 8:41
• (This does not really change anything about the answer.) It appears that you're interpreting UF-CMA to mean "universal unforgeability under chosen message attack". It is not clear to me that this is what is meant. May 3 at 10:25
• @Maeher: Right. I was assuming the lack of E (for Existential) means Universal forgery, when the U is likely for Unforgeability and we don't know (or need to know) if Existential or Universal is meant. I have expanded the answer.
– fgrieu
May 3 at 15:51