0
$\begingroup$

Knowing that ECDSA signatures are non-deterministic (barring RFC 6979), is it possible to verify that two different, yet valid signatures of the same message came from the same private key?

To provide an example: let's say Bob receives a valid signature from Alice and subsequently stores Alice's public key. If Alice, after some time, sends a different (yet valid) signature of the same message made with the same private key, can Bob verify the signature using the stored public key and be certain that only Alice generated this new signature given the same private key was used to create it?

$\endgroup$
3
  • $\begingroup$ The whole point of a digital signature is that only the secret-key-holder can generate signatures that pass verification. So if you see 2 signatures of the same message that both pass verification under the same public key, then you can conclude that a secret-key-holder must have generated both. $\endgroup$
    – Mikero
    Commented Apr 21 at 23:40
  • $\begingroup$ Do you know either the common message, or the common public key (or neither). As Mikero pointed out, if you know both, it's easy to verify... $\endgroup$
    – poncho
    Commented Apr 22 at 2:02
  • $\begingroup$ This is what signature does. However, if somebody gets access to Alice’s private key physically or by her fault there is no meaning of signature scheme. $\endgroup$
    – madhurkant
    Commented Apr 22 at 4:52

2 Answers 2

1
$\begingroup$

is it possible to verify that two different, yet valid signatures of the same message came from the same private key?

There are three possibilities (depending on the verifier's knowledge); lets go through all three:

  • Suppose the verifier knows the common message, but not the private key; can he verify this.

Answer: yes (with an extremely tiny probability of getting a 'false hit'). There's a well known technique that, given an ECDSA signature and a message, generates a handful of public keys (exactly two if the curve has cofactor 1) that would have verified that message/signature pair. So, what the verifier would do is for each signature, generate the handful of public keys, and if they have a public key in common, say "yes" (and we also know the public key). Of course, it's possible (since each signature gives us several public keys) that both signatures would happen to give us the same wrong public key (that is, a 'false hit'), but the probability of that happening is tiny.

  • Suppose the verifier didn't know the common message, but did know the public key that both supposedly signed (and wants to verify if both signatures correspond to that public key).

In this case, also yes (with a similar probability of a 'false hit')

The ECDSA verification check can be written as:

$$hs^{-1}G + rs^{-1}P \in X(r)$$

where:

  • $r, s$ are parameters from the signature system
  • $h$ is the (possibly truncated) message hash
  • $P$ is the public key
  • $G$ is the elliptic curve generator
  • $X(r)$ is the set of elliptic curve points with $r$ as the x-coordinate

We can rewrite this to be:

$$hG \in sX(r) - rP$$

with the operation between values and sets being element wise, that is $s\{A, B\} - rP = \{sA - rP, sB - rP\}$

Now, if we have two signatures $(r_1, s_1), (r_2, s_2)$ which both satisfy the above relation with a known $P$ and common but unknown $h$, we can evaluate the above rhs, and see if they share an $hG$ in common; if they do, then we can be pretty sure (except for a 'false hit' analogous to the previous possibility) that the hypothesis is correct - both message were signed with the same private key.

It should be obvious that we're actually using the same trick as we did for the public key recovery with a known message; we're just recovering $hG$ rather than $P$...

  • Suppose the verifier didn't know either the message or the public key

Answer: it doesn't look possible; it would appear for any pair of signatures $(r_1, s_1), (r_2, s_2)$ there are a pair of common message hashes/public keys that would verify under both, and this would be true whether or not both signatures actually were generated with the same key.

On the other hand, when you ask:

can Bob verify the signature using the stored public key and be certain that only Alice generated this new signature

In two of the above scenarios, Bob can verify (with only a tiny probability of being wrong) that the same private key generated both signatures. However, it cannot verify that Alice was the holder of the private key that generated both; that is something beyond what a signature system can do.

$\endgroup$
1
$\begingroup$

If the same private key was used and produced different signatures, then any public key produced from that private key must verify each of those signatures. Even if public keys are not deterministic. Otherwise it’s not a public key for the private key.

If you can verify both signatures with the same public key, then it’s the same private key (up to a one in a gazillion chance). If you can verify one but not the other with some public key then the private keys must be different.

If you can verify both signatures with different public keys, then you need to enquire whether producing public from private keys is deterministic. If it is deterministic then your two different public keys come from different private keys. So a one in a gazillion chance that the signatures come from the same private key. If it is not deterministic then you don’t know. You might have received different signatures and different public keys because both are not deterministic.

If you can’t verify any signature, then I can’t see any way to find if they were created by the same private key. (Assuming that nondeterministic signatures are nondeterministic in order that no conclusions can be drawn and not because of stupid software, like signatures that are identical up to random padding, for example).

$\endgroup$
1
  • $\begingroup$ I believe this answer would be better if it didn't assume a generic signature system was used, but instead it was specifically ECDSA (which was mentioned in the question). For ECDSA, there are ways to detect whether the same public key was used for two signatures of the same known message, even if you didn't know what the public key was (and hence could not verify either signature). $\endgroup$
    – poncho
    Commented Apr 23 at 2:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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