2

Given an RSA signature as produced by

openssl dgst -sha256 -sign rsapriv.pem -out afile.sig afile

and without access to the private key used for that, one can¹ come up with a fully functional RSA public/private key pair such that signature afile.sig verifies against that new public key and any desired file.

This does not break the basic security promise of signature, which is that given a public key, it's impossible to come up with a signature and a file that matches the public key, unless the holder of the matching private key is involved and is willing that.

Nevertheless, that could enable signature misappropriation attacks with some level of social engineering.

Say afile.sig and afile are hosted on a trusted website, in order to authenticate afile. Malory makes a key pair matching afile.sig and afile, perhaps gets it certified, then has something to pass as evidence for affiliation with afile or/and the trusted website, on the tune of: "the website entrusts me for matters related to afile, since it host my signature for that. Yes I made that signature, check it yourself against my certificate!".

In a variant, afile is on a website under control of Malory, who makes whatever bfile, then a key pair matching afile.sig and bfile, and tries to pass bfile as the real thing since it checks against a (rightly) trusted signature.

Which deployed signature formats are resistant (or not) to such signature misappropriation?


Mildly formal definition: a signature scheme is misappropriation resistant if, given one of its public key Pub, message M, and legitimately computed signature S (thus passing verification), it is computationally infeasible to exhibit a public key Pub' and a message M' such that

  1. Pub', M', S pass signature verification.
  2. When later given a random message M", the attacker exhibits with sizable probability S" such that Pub', M", S" pass signature verification.

Exhibiting Pub' and M'=M (resp. M'≠M) would be misappropriation without (resp. with) alteration (of the message). Pub'≠Pub is implied by condition 2 and the usual security property of a signature scheme. We define weakly misappropriation resistant by replacing 2 with Pub'≠Pub.


If the public key, or a second premimage resistant hash thereof, is part of the signature, or is hashed with the signed data (as in EdDSA), then the scheme is misappropriation-resistant.

In OpenPGP, it seems the signature embeds the key id, which is the low-order 64 bits of the hash of the oublic key. We'd need to generate 264 suitable public keys and hash them to carry the attack. That's not unimaginable, but a lot of work.

And then there are all the other formats that I do not even know about.


¹ That's a matter of seconds for standard modulus size. The resulting key is fully PKCS#1 conforming, and can even be made secure. Disclosing details on how would risk to ruin an ongoing CTF asking for similar math, but trust me, it works.

1

Mildly formal definition: a signature scheme is misappropriation resistant if...

The properties you describe as signature misappropriation have acquired a few different names in the academic literature:

  • Conservative Exclusive Ownership is name of what you describe as misappropriation resistance without message alteration. Schemes lacking this property are said to be vulnerable to key substitution attacks or duplicate signature key selection attacks.
  • Destructive Exclusive Ownership is name of what you describe as misappropriation resistance with message alteration. Schemes lacking this property are said to be vulnerable to message key substitution attacks.
  • Weak Variants are also defined where the attacker does not know the correct private key as in your weak notion.

We wrote a paper which contains formal definitions of these properties and their consequences: See sections 3.1.1 and 3.1.2 of Seems Legit: Automated Analysis of Subtle Attacks on Protocols that Use Signatures. It has a discussion of their history and references to the papers which first described these properties.

If the public key, or a second premimage resistant hash thereof, is part of the signature, or [...], then the scheme is misappropriation-resistant.

This seems intuitively true and the very first paper to discover this kind of attack made the same observation. However, this isn't true in general as the attacker can use the message alteration property so that the included public key is changed to be the theirs. However, you are correct that EdDSA's specific design does prevent this.

Which deployed signature formats are resistant (or not) to such signature misappropriation?

Vulnerable to "strong signature misappropriation" (lacking CEO/DEO):

  • RSA with PKCSv1.5
  • RSA with PSS
  • DSA
  • ECDSA with the elliptic curve parameters treated as part of the public key.

Vulnerable to "weak signature misappropriation" (lacking wCEO/wDEO):

  • ECDSA with fixed elliptic curve parameters

Source: Seems Legit Paper, Table 1.

| improve this answer | |
  • Thanks for the reference and established vocabulary. I don't get your refutation of "If the public key, or a second preimage resistant hash thereof, is part of the signature, [...], then the scheme is misappropriation-resistant.". I'm meaning the (hash of the) public key is a segment of the signature, and I imply (should have written it) that this segment is compared to the (hash of the) public key by the signature verification (as OpenPGP does, albeit with a hash/keyid of only 64-bit). I conclude that the public key can't be changed to pass my 1, then that passing 2 breaks UF-CMA. – fgrieu May 6 at 20:39
  • 1
    Ah, I understood your sentence to mean including the public key with the signature payload to be signed ("hashed with the signed data"). I think you are definitely correct as long it is a bitwise equality check. Using it in the group structure in EdDSA probably needs careful analysis to provably avoid this kind of property. – Dennis Jackson May 7 at 23:57

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.