LetsEncrypt was vulnerable to this exact attack - it let people issue valid TLS certificates for domains they didn't control:

https://www.agwa.name/blog/post/duplicate_signature_key_sele...

We discuss this exact attack (and blog post) in Section 5.1 of the paper :).

IIRC: it was missed by both an academic analysis of LE and a 3rd party audit of their crypto design. Thankfully Andrew spotted it a few weeks before they went live in major browsers!

In particular, see also this 2005 paper by Thomas Pornin: http://www.bolet.org/~pornin/2005-acns-pornin+stern.pdf

EDIT: Looks like this paper is also already included in the list of citations for the 2019 paper :)

This is also a Cryptopals exercise in Set 8:

https://toadstyle.org/cryptopals/61.txt

The first time I heard of this bug was through the Another Look series where it was called DSKS.

> In the process, we find new attacks on DRKey and SOAP's WS-Security, both protocols which were previously proven secure in traditional symbolic models.

Does that mean the previous proofs were wrong? or that they proved a narrower version of "secure" that didn't include those particular attacks?

The latter. The tools in question (Tamarin and ProVerif) use a model of signatures that goes back to 2000/2001 which is around when these key substitution properties were discovered. Consequently, they were missed from the models and because the properties themselves aren't that well known, it took a while before it was noticed.

Btw you don’t mention repudiation in there, but would you say it makes sense to say that most signature scheme actually don’t provide non-repudiation?

It depends what you consider to be non-repudiation!

With key substitution, you have a signature that can verify under multiple public keys. However, each key was either honestly generated and used to sign the message, or was maliciously generated and intended to appear to have signed the message.

In this sense, the party associated with each public is indisputably associated with the corresponding signature.

However, this gets a bit more confusing with message key substitution (two public keys, two messages, one signature) or colliding signature (one public key, any number of messages, one signature). For example, a malicious party might produce a signature which is valid for any message. Does the fact that they've "signed everything" mean they can repudiate having signed anything? (The connection between intent to sign and the signature has arguably been lost).

We do discuss these other properties in the paper, but we don't really delve into non-repudiation in the informal sense.

It’s also worth pointing out that non-repudiation requires stronger properties than cryptography alone can guarantee. If I surreptitiously leak my private key onto the internet I can later plausible deny that I signed messages. (The Signal protocol deliberately leaks old MAC keys for this reason).

If you really want non-repudiation then you have to have hardware, legal, and procedural controls in place.