Recovering Public Key from ECDSA signature- why is it required at all?

Question

I am looking at SEC 1: Elliptic Curve Cryptography

4.1.6 Public Key Recovery Operation

Given an ECDSA signature $(r, s)$ and EC domain parameters, it is generally possible to determine the public key $Q$, at least to within a small number of choices.

I am unable to figure out why recovering Public Key from the Signature is a useful option at all?

The Document says

This is also useful in bandwidth constrained environments, when transmission of public keys cannot be afforded

But the whole idea of signatures is that the verifier needs to already need to know the public key - else the whole verification becomes meaningless.

Let us say Alice signs a message & sends the message & the signature to Bob. Now Bob knows her Public Key & he can check if the message has indeed been signed by someone who has the private key corresponding to the public key he knows for sure is Alice's Public Key.

Let's say Mallory intercepts Alice's message & signature. He changes the message & signs it with his own private key. Now Bob gets the tampered message & the signature. Bob doesn't have Alice's Public Key - so Bob recovers what he thinks is Alice's Public key from the signature - then verifies if the message is signed by who ever has the Private Key corresponding to that public key. Now the Public Key Bob recovers is actually Mallory's & not Alice's. So Bob will never know that the message has been tampered. So what is the point of the signature?

Answer 1

I'm not actually convinced that this is actually useful to save bandwidth in constrained environments. Sometimes, in specifications, sentences like “it is useful in this scenario” get written in even though the scenario is hypothetical.

However, I am familiar with environments where a system will verify a signature, yet does not store the key. There are secure environments that do not have any rewritable persistent storage, but have some ROM code (identical on all devices of the same model) plus a very small amount of one-time writable memory (a typical amount would be a little over 256 bits). During manufacturing, the vendor burns a hash of its root CA public key (and also a secret key that never escapes the secure environment). To make the secure environment do something, you send it code and data signed by a key that comes with a certificate chain from the vendor's CA. The device checks that the hash of the public key at the root of the chain corresponds with the reference hash in its one-time writable memory. On the devices that I'm familiar with, the amount of data that you'd need to upload is large enough that saving the transmission of the public key would be negligible and not worth the extra complexity.

I would imagine that recovering the public key from a signature is more useful in environments that manipulate a large amount of data because they store a large number of signatures. Blockchains come to mind. But that's not a domain that I'm very familiar with.

In any case, it is of course useful to know that it's possible to recover the public key, because it means that ECDSA signatures offer no privacy.

Answer 2

But the whole idea of signatures is that the verifier needs to already need to know the public key - else the whole verification becomes meaningless.

That's not true. Somewhere in the verification process it is required that the public key is trusted. This is why leaf (and parent CA certificates) are - for example - included in higher level signature schemes such as CMS (aka PKCS#7). As long as a trust path can be established to a trust anchor then the signature can be verified to have come from a specific entity that controls the private key.

This is assuming that the other information in the certificate is also valid and that the certificate is used for the correct purpose; I'll leave the finer details of PKI out of the answer if you don't mind.

Let us say Alice signs a message & sends the message & the signature to Bob. Now Bob knows her Public Key & he can check if the message has indeed been signed by someone who has the private key corresponding to the public key he knows for sure is Alice's Public Key.

Yes, that's correct.

Let's say Mallory intercepts Alice's message & signature. He changes the message & signs it with his own private key. Now Bob gets the tampered message & the signature. Bob doesn't have Alice's Public Key - so Bob recovers what he thinks is Alice's Public key from the signature - then verifies if the message is signed by who ever has the Private Key corresponding to that public key. Now the Public Key Bob recovers is actually Mallory's & not Alice's. So Bob will never know that the message has been tampered. So what is the point of the signature?

Same as it always was, but without a pre-distributed key. In the example above it is assumed that Mallory cannot obtain a valid certificate, so any public key / certificate containing (or implying a specific public key) cannot be produced by Mallory.

This was just an example using PKI, schemes may and willuse other methods to establish trust. In this case the various crypto-coin standards are probably more on topic.