Is it important to defend against key substitution attack in ECDSA?

Question

When planning a file signature scheme (basically, just to sign all files content). Is it obligatory to defend against ECDSA key substitution attack? ISO/IEC 14888-3:2018 NOTE 5 states:

The mechanisms of EC-DSA, EC-GDSA. EC-RDSA and EC-FSDSA may be vulnerable to a key substitution attack[10]. The attack is realized if an adversary can find two distinct public keys and one signature such that the signature is valid for both public keys. There are several approaches of avoiding this attack and its possible impact on the security of a cryptographic system. For example, the public key corresponding to the private signing key can be added into the message to be signed.

---

[10] Bohli J.M., Rohrich S., Steinwandt R. Key substitution attacks revisited: taking into account malicious signers. Int. J. Inf. Secur. 2006, 5 pp. 30–36

"May be vulnerable" may be read as "may be not vulnerable". I also heard opinions such that practically that attack is not applicable. For example, when the key source is a trusted CA or it's in HSM device. Also, common tools (like openssl) generate raw ECDSA signatures without protection against such attacks.

So the question may be rephrased to—is it still sane to use raw ECDSA signature in 2019? And not to use some schemes like CAdES.

Answer 1

So the question may be rephrased to—is it still sane to use raw ECDSA signature in 2019?

It's not insane, but you should use Ed25519 in any new applications: it is faster, simpler, and more confidence-inspiring.

However, the standard notion of security of a public-key signature scheme—EUF-CMA, or existential unforgeability under chosen-message attack—says nothing about whether a signature that is valid under one public key may also be valid under another public key. Let's call this property public key uniqueness.

Some exotic applications may rely on public key uniqueness, e.g. the Let's Encrypt name ownership verification protocol Acme was accidentally designed to rely on it at first[1], but most signature schemes do not provide this additional property, because most applications don't need it: you don't bother verifying a message with a public key unless you know the public key is good to begin with.

Neither ECDSA, nor RSASSA-PKCSv1_5, nor RSASSA-PSS provides public key uniqueness out of the box. There are many additional security properties that exotic applications might want: key anonymity, public key uniqueness, signature uniqueness (which Monero accidentally relied on[2] in their exotic application), verifiably unique pseudorandomness (a.k.a. VRF), etc. But most applications don't need them.

Rather than worry about exotic properties that an application once made the mistake of assuming, you should focus on what your application actually does need, by writing down what resources you rely on, what resources the adversary can control that you take action on, etc.

As it happens, Ed25519 does provide public key uniqueness, because the public key is hashed together with the message as part of making a signature. This is a generic structure that probably works to turn any EUF-CMA signature scheme without public key uniqueness into one with it, as the note you quoted suggests, although it has the consequence that it essentially rules out another exotic property, message recovery[3].