Premeditated substitution of ECDSA-signed message by the signer

Question

If I understand correctly section 4.2 in Jacques Stern, David Pointcheval, John Malone-Lee, and Nigel P. Smart's Flaws in Applying Proof Methodologies to Signature Schemes, in proceedings of Crypto 2002, they describe an attack that allows premeditated substitution of ECDSA-signed message by the signer.

Per their notation, one can

1. Freely decide any two messages m1, m2 ; say large files.
2. Craft (using the article's method) an apparently normal ECDSA public-private key pair (y,x) and signature (r,s) such that both m1 and m2 verify against (y,x) and (r,s) !
3. Distribute the public key y or obtain a certificate for it, in the usual way (including signing the Certificate Signing Request with the private key x as necessary).
4. Optionally, use the private key x normally to sign various messages, with the signatures verifying normally.
5. Put message m1 online and send to a verifier it's signature (r,s), invitation to check it, and indication that m1 will stay online.
6. Later (after the logs on the server have shown m1 was read once by the verifier), change m1 to m2 and from then on stand firm on the position m2 what was there in the first place.

Is there something I miss? A documented case where what the paper describes has lead to disaster or dispute? A common mitigation?

I have not found a way to confound the perpetrator from m2, (r,s), y, or even with x on top of that. Surest mitigation seems to be keeping a copy of m1, which could give some degree of confidence to a third party expert that the signer was malicious. But that's impractical for large messages, and might not be an option for legal reasons. Keeping the hash h1 of m1 is feasible for the verifier, but I don't see that's enough to convince a third party.

Is there a well-known name for the security property an ideal signature scheme (and AFAIK EdDSA) has w.r.t. such attack, but ECDSA fails to have here?

Answer 1

Is there something I miss? A documented case where what the paper describes has lead to disaster or dispute? A common mitigation?

There are certainly some attacks which have used very similar properties:

• A draft Let's Encrypt certificate issuance protocol
• The Station to Station Key Exchange
• WS-Security Mutual Authentication Profile
• Secure Scuttlebutt's Handshake

In all of these circumstances, the designers implicitly assumed a signature could only be verified against one particular message and as Stern and colleagues show, this isn't necessarily true. We did a review of these properties, explain the above attacks and found some new ones in Seems Legit, published at ACM CCS 2019. We also tried to exhaustively reference the earlier works which used different terminologies which may be helpful.

Is there a well-known name for the security property an ideal signature scheme (and AFAIK EdDSA) has w.r.t. such attack, but ECDSA fails to have here?

Whilst EdDSA does indeed resist this particular attack, it is vulnerable to a related one where an adversary can pick a small subgroup element as their public key and then produce a signature which will verify for any message. It turns out whether or not this attack works actually comes down to the EdDSA implementation, with LibSodium (provably) resisting it but most implementations vulnerable to it.

We looked at this in The Provable Security of Ed25519:Theory and Practice (S&P 2021), where we dubbed it "Message Bound Signatures" (Definition 12). A very closely related notion is that of Strong Universal Exclusive Ownership and Malicious Strong Universal Exclusive Ownership. We define security games for all three notions and show under what requirements Ed25519 has these properties.

Henry de Valence did a survey of Ed25519 implementations to see how they handle different signature inputs and produced a fantastic visualisation. Recently, Cremers, Düzlü, Fiedler, Fischlin and Janson have looked at these properties in the context of NISTs post-quantum signature schemes and are advocating for changes to prevent these attacks.

References:

Jackson, D., Cremers, C., Cohn-Gordon, K., & Sasse, R. (2019, November). Seems legit: Automated analysis of subtle attacks on protocols that use signatures. In Proceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security (pp. 2165-2180).

Brendel J, Cremers C, Jackson D, Zhao M. The provable security of ed25519: theory and practice. In Proceedings of the 42nd IEEE Symposium on Security and Privacy (S&P'21). IEEE Press.

Cremers, C., Düzlü, S., Fiedler, R., Fischlin, M., & Janson, C. (2021). BUFFing signature schemes beyond unforgeability and the case of post-quantum signatures. In Proceedings of the 42nd IEEE Symposium on Security and Privacy (S&P'21). IEEE Press.

It’s 255:19AM. Do you know what your validation criteria are? Henry de Valence https://hdevalence.ca/blog/2020-10-04-its-25519am

Answer 2

The point of the cited paper is that security analysis of a signature algorithm must look beyond the signature algorithm itself. Here, the authors demonstrate that collusion between key generation and signature algorithms can affect the security analysis wrt non-repudiation properties.

But this does not mean that ECDSA is insecure in practice.

For example, the authors mention that as soon as m2 is published, anyone can reconstruct the private key using h1 and h2 (hashes and message contents are equivalent in this context). The signer cannot sneakily substitute m2. This will leak the key, and it will be clear that the key was crafted maliciously. The threat here is that we can't know whether a key is malicious or not until m2 is disclosed.

It is also necessary that the messages be known before the key is generated. This becomes difficult in real-world scenarios when a certificate was obtained long before the messages are signed. It becomes outright impossible in an interactive protocol where the public key is shared in advance, and the message must include an arbitrary value chosen by the recipient.