Given a message and signature, find a public key that makes the signature valid (ECDSA)

Question

This question is a variant on Given a message and signature, find a public key that makes the signature valid, which discusses the analogous question for RSA. It was suggested to me by this post over on Bitcoin.SE.

Suppose we are given an ECDSA signature $S$, a message $M_1$, and a public key $P_1$, such that $S$ is a valid signature of $M_1$ with $P_1$. Let $M_2$ be another message. Is it known whether we can feasibly find another public key $P_2$ such that the same $S$ is also a valid signature of $M_2$ with $P_2$?

Is there a general name for this kind of an attack (on a general signature algorithm)?

What would be the practical implications of such an attack? I can't think of any obvious way to use it to cause mischief, but I may just not be creative enough.

(Apologies if this is well-known or if my terminology or notation is bad. I am a mathematician but not a cryptographer.)

Edit: Thanks to Ricky Demer for the link to the paper by Pornin and Stern (see comment below). In their terminology, if I have it right, this attack is called a second key construction, and a vulnerable signature algorithm is said to lack destructive exclusive ownership. They also describe a way that an attacker could use this to produce a fake revocation of a victim's X.509 certificate.

Answer 1

Yes. We can easily generate the malicious public key as in DSS case. The following attack was proposed in Section 4.5 of Blake-Wilson and Menezes: Unknown Key-Share Attacks on the Station-to-Station (STS) Protocol (PKC 1999).

Let $(G,q,n,P)$ be the ECDSA parameters, where $n$ is the order of the group $G$ over the elliptic curve and $P$ is a generator of $G$.

Let $P_1 = d_1 P$ be the public key, let $M_1$ be the message, and let $S_1 = (s_1, r_1)$ be the signature as you noted.

Since $S_1$ is a valid signature under the public key $P_1$, it satisfies the following equaitons. $$ s_1 k_1 \equiv e_1 + d_1 r_1 \pmod{n},$$ where $e_1$ is a digest of the message $M_1$, and $r_1 \in \mathbb{Z}_n$ is a $x$-coordinate of $k_1 P$ modulo $n$.

How to construct a malicious public key

Let $M_2$ be the target message. We now virtually compute a malicious secret key $d_2$ as $$ d_2 = r_1^{-1} (s_1 k_1 - e_2) \bmod{n}, $$ where $e_2$ is a digest of the message $M_2$. We then compute a malicious public key $P_2 = d_2 P$, which is $$ r_1^{-1} (s_1 k_1 - e_2) P = r_1^{-1} (e_1 + d_1 r_1 - e_2) P = r_1^{-1}(e_1 - e_2)P + P_1$$.

Validity of the public key $P_2$.

The public key $P_2$ makes the message $M_2$ and the signature $S_1 = (s_1, r_1)$ valid. Let us verify the validity of them.

1. $r_1$ and $s_1$ is in the range $[1,n-1]$, because the signature $S_1$ is valid.
2. Let $X = u_1 P + u_2 P_2$, where $u_1 = e_2 s_1^{-1} \bmod{n}$ and $u_2 = r_1 s_1^{-1} \bmod{n}$. By the construction of $P_2$, we have $X = (u_1 + u_2 d_2) P = s_1^{-1} (e_2 + r_1 d_2) P = s_1^{-1} (s_1 k_1) P = k_1 P$. Therefore, $r_1$ is the $x$-coordinate of $X$.

How to prevent this attack

It is easy to prevent this attack. We just use a digest $e' = \mathrm{Hash}(pk,M)$ instead of $e = \mathrm{Hash}(M)$.

Answer 2

An attack is described in Section 4.1.6 of the SEC1 document.

Regarding xagawa's answer:

1. The attack you describe is different from that described in Section 4.5 of the Blake-Wilson--Menezes paper. Specifically, their attack: (a) does not require knowledge of the secret ephemeral key $k$, and (b) changes the reference point $P$, which is not allowed in some instantiations of ECDSA.

2. Your attack requires knowledge of the secret ephemeral key $k$, which is equivalent to knowing the private key $d$.

These comments on xagawa's answer should be in a separate comment on that answer but I don't have enough reputation so instead I included them here.