Signature verifying against multiple certified public keys? I'm wondering if and how the current public key certificate infrastructure is guarded against the following scenario:


Honest Alice obtains Eve's public key certificate Certe, made by honest CA Carol; checks it the usual way; and assumes she knows Eve's public kev Pube.
Alice generates a message M mentioning obligation by Eve, sends it towards Eve, and receives apparently from Eve a signature S; Alice verifies that M, S, and Pube match.
Later, Eve denies having approved M or produced S; suggests that S must be by Frida; and as argument asserts that S also checks against Frida's certified public key.
Alice obtain Frida's public key certificate Certf, made by honest CA Carl; checks it the usual way; and assumes she knows Frida's public key Pubf.
Alice verifies that indeed M, S, and Pubf match!
Pube and Pubf are different, and Alice finds them unremarkable, as well as Certe and Certf; these carry a certification date earlier than the generation of M by Alice; there was no certificate revocation.
Alice obtains other (M, S) pairs attributed to Eve and Frida; they verify against only one of Pube or Pubf, as intended.




Unless I err, that scenario could happen with 2048-bit RSA, usual e=F4=65537, and RSASSA-PSS as signature, assuming Eve and Frida are crooks operating as follows:


Eve and Frida jointly choose two distinct small close primes, say re=101 and rf=103; and jointly generate their respective RSA modulus Ne and Nf with Ne=re⋅p⋅q, Nf=rf⋅p⋅q, 22047&lt;Ne&lt;Nf&lt;22048, p and q large random primes with gcd(p-1,65537)=1=gcd(q-1,65537).
Eve computes her private exponent de=e-1 mod LCM(re-1,p-1,q-1) matching her public key Pube=(Ne,e) with e=65537. Frida does similarly for df matching her public key Pubf=(Nf,e).
Eve and Frida obtain their certificate the normal way; the only caveat is that they avoid CAs that check for small factors in public modulus.
When Eve generates a signature using RSASSA-PSS, she proceeds normally, except that she additionally checks the signature against Pubf: about one signature among rf pass this test! Eve iterates signing until finding a signature for M matching her intention to later attribute the signature to Frida, or not. Frida does similarly.


Update: I asked again there, where questions about policies belong.
From a cryptography perspective, this works as advertised; Eve and Frita can generate signature keys where a nontrivial fraction of signatures for one key will validate with the other.

That said:


It is trivial to detect this, if anyone looks.  If we suspect that Eve and Frita are colluding (which we may, if someone demonstrates a signature that validates with both public keys), then a simple computation of $\text{gcd}( N_e, N_f )$ will reveal it.  Alternatively, if someone just checks either $N_e$ or $N_f$ for small factors, that'd show that something nonkosher is going on.  While I don't believe most CA's routinely check the public keys submitted to them for small factors, there might be some that do (and it certainly would not be expensive, compared to the other operations CA's must do).
It's not clear if this is actually an attack; $S$ is a valid signature for $M$ under $Pub_e$, and Eve cannot argue that it's not.  Eve's argument of 'maybe Frita did it' doesn't address the question of 'how did Frita forge a signature of Eve's key'.
Also, as for your question of 'maybe real signatures embed a public key identifier', no, they do not.