6
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Tangentially related, if you are allowed to modify the domain parameters (e.g. the base point of the curve that was used to sign) then it is actually quite easy to efficiently create a valid public key for arbitrary ECDSA signatures. $\endgroup$ – puzzlepalace Feb 5 at 19:25
  • $\begingroup$ @puzzlepalace That would be interesting reading, could you provide some reference? $\endgroup$ – catpnosis Feb 5 at 21:15
  • 1
    $\begingroup$ LetsEncrypt had a post for this attack on RSA signatures. My only reference for the ECDSA case is (the unreleased) set 8 of cryptopals, where problem 61 is basically this attack on both ECDSA and RSA. $\endgroup$ – puzzlepalace Feb 5 at 22:41
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Claiming that using ECDSA signatures is "not sane" seems a bit exaggerated. $\endgroup$ – Ruggero Feb 21 at 10:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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