Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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.

share|improve this question
1  
related $\;$ –  Ricky Demer Apr 12 at 4:16
1  
Check out 4.1.6 Public Key Recovery Operation in Certicom - SEC 1: Elliptic Curve Cryptography –  CodesInChaos Apr 12 at 12:50
    
    
@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 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 at 15:54

1 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, k_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 \equiv k_1^{-1} (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 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$.

Validity of the public key $P_2$.

The public key $P_2$ makes the message $M_2$ and the signature $S_1 = (s_1, k_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)$.

share|improve this answer
    
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. $\;$ –  Ricky Demer Apr 13 at 5:49

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.