Names and games for security properties preventing substitution of signed message by the signer

Question

Some signature schemes, notably ECDSA, unwillingly allow users to prepare their public/private key pair as a function of two arbitrary messages of their choice, and compute a signature that checks for both messages¹. In the case of ECDSA, the public/private key pair is fully functional, and can sign normally, including for making a certificate signing request for it's public key. Convincing a third party of the intend of foul play is hard, and requires both messages. I ask about concrete security consequences there.

Some others signature schemes, notably any $3k$-bit short Schnorr signature scheme² (not EdDSA which is $4k$-bit), have an even more worrying security vulnerability. At any time after normal generation of a key pair, a holder of the private key can prepare two messages with distinct and arbitrary chosen content except for a small section, and their common signature, by a collision search attack on the hash only, with expected cost a mere $\Theta(2^{k/2})$ hashes. The attack can be repeated, and be undistinguishable by a third party from a successful pre-image attack of the hash without the private key, of expected cost $\Theta(2^k)$ hashes.

Broadly, these attacks could be named substitution of signed message by the signer, with the first kind premeditated. Sub-classification makes sense (like if perpetrating the attack reveals the private key; it does in the first attack, not in the second).

What are standard names for the security properties preventing such attacks? Are there standard security experiments for these security properties?

Note: I also asked how IT practice deals with the issue there on security-SE, so please don't answer here on that aspect. I admit there is overlap for the naming part.

---

¹ See 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.

² Claus Peter Schnorr, Efficient Identification and Signatures for Smart Cards, in proceedings of Crypto 1989 then Journal of Cryptology, 1991.

Answer 1

I found part of the answer in Dennis Jackson, Cas Cremers, Katriel Cohn-Gordon and Ralf Sasse: Seems Legit: Automated Analysis of Subtle Attacks on Protocols that Use Signatures, in Cryptology ePrint Archive, Report 2019/779, originally in proceedings of ACM CCS 2019.

Their term for the attack against the signature scheme is Colliding Signatures, rather than Duplicate Signatures in the original paper in footnote 1 of the question.

They name the desirable property ECDSA lacks Non-Colliding Signatures. Sec1v2 dismiss that's a worrying repudiation risk, as follows:

The malicious signer may try to repudiate the signature on one of the messages. An argument for repudiation entailing that some third party caused the duplicate signature to occur seems to presuppose the existence of genuine forgery attack. Because such attacks are unknown, the balance of the probabilities falls to malice by the signer, since the signer has access to the private key and therefore much greater ability to generate signatures. Over and above these general concerns, this duplicate signature attack has the added deficit that it exposes the signer’s private key. Because the private key is determined by the signature and the two messages signed, the probability that the signer had generated the private key in an honest manner is negligible, and one can deduce almost certainly that the private key was deliberately generated in order to launch this attack. To repudiate the signatures, a signer would therefore have to assert that some third party generated the signer’s private key, which contradicts the usual assertion that signers must make for non-repudiation: namely, that the signer has generated the private key and not revealed it to anybody else.

I get the argument, but "better safe than sorry" comes to mind. As a practitioner, I wish ECDSA had forced the $Y$ coordinate to be even, which would have prevented this and made the scheme SEUF-CMA in one move. In the same vein, I wish EdDSA had rejected the few low-order public keys from the onset.

The formalization as security experiment goes: on input $1^n$, adversaries try to output $(\mathrm{pk},m,m',\sigma)$ with the correct $n$ conveyed in $\mathrm{pk}\,$, $m\ne m'\,$, $\mathsf{Vrfy}(\mathrm{pk},m,\sigma)=1\,$, and $\mathsf{Vrfy}(\mathrm{pk},m',\sigma)=1$.

---

But the question also asks about a more worrying attack on the Schnorr short signature, which differs because the public/private keys is not maliciously generated, and several message pairs can be generated.

For this one, I have not found a reference (I won't mark the answer as accepted for this reason). I tentatively name the attack Non-Premeditated Colliding Signatures. I hesitate for the security property.

The formalization as security experiment can go: on input $(\mathrm{pk},\mathrm{sk})$ output by $\mathsf{Gen}$, adversaries try to output $(m,m',\sigma)$ with $m\ne m'\,$, $\mathsf{Vrfy}(\mathrm{pk},m,\sigma)=1\,$, and $\mathsf{Vrfy}(\mathrm{pk},m',\sigma)=1$. A small variant would additionally give as input a copy of $\mathsf{Gen}$'s random tape/generator.