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

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.

• related $\;$ – user991 Apr 12 '14 at 4:16
• Check out 4.1.6 Public Key Recovery Operation in Certicom - SEC 1: Elliptic Curve Cryptography – CodesInChaos Apr 12 '14 at 12:50
• – CodesInChaos Apr 12 '14 at 13:01
• @CodesInChaos yes, but this will allow to recover the public key corresponding to the signing key used for producing the signature at hand. Nate asks for $P_2\neq P_1$. – DrLecter Apr 12 '14 at 15:47
• @RickyDemer: Thanks very much. That paper seems to give a very good overview, and I've noted it in my question. – Nate Eldredge Apr 12 '14 at 15:54

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)$.

• Usefully, the change you describe would also stop a hash collision from immediately yielding $\hspace{.9 in}$ a way to violate unforgeability for every public key. $\;$ – user991 Apr 13 '14 at 5:49
• The signature $S_1 = (s_1,k_1)$ is not a signature. The signature should be $S_1 = (r_1,s_1)$ as the knowledge of $k_1$ leads to the private key $d_1$. The attacker has no knowledge of $k_1$ and can't perform this attack. See the answer by @ggutoski which provides more details. – Ruggero Apr 17 '15 at 8:10
• Thank you for pointing out my mistake. Well, I correct the form of the signature. But, please notice that the attack I described does not require knowledge of $k_1$. – xagawa Apr 17 '15 at 23:18

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

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