There seems to be a distinct lack of implementations of RSA signatures using OAEP to pad the digest. Other than the old, funky, padding schemes, it's PSS all the way.

PSS seems to have the whiff of patents about it. OAEP, on the other hand, is accompanied by long diversions about its theoretical safety presented as claim and counterclaim.

Is it, in principle, very wrong to use OAEP with RSA for signatures? How wrong? As bad as those first generation padding schemes? Has the stench of patents lifted from PSS? If there's one thing more confusing than the underlying maths, it's the organisation of crypto standards: is this combination actually rather common, detailed well in a PKCS or RFC, and I've just missed it?

  • 3
    $\begingroup$ This thread may be of interest to you. $\endgroup$ – puzzlepalace Sep 23 '15 at 23:31
  • 1
    $\begingroup$ Our very own Thomas Pornin gives the best response in this thread. Basically (paraphrasing) there is no real reason to suspect using OAEP instead would instantly make your signature scheme insecure, but you no longer have the benefit of a provably-secure signature scheme because there is no proof of security for RSA signatures with OAEP. $\endgroup$ – pg1989 Sep 24 '15 at 1:14
  • $\begingroup$ Very wrong. There's no reason to do it, since you have provably secure schemes that are just as efficient. $\endgroup$ – Yehuda Lindell Sep 24 '15 at 12:46
  • $\begingroup$ @YehudaLindell The reason to look into it would be in considering it as an option in trying to find what is currently believed to be the most secure unencumbered signature protocol. The answers suggest that PSS and PKCS1-1.5 padding would be placed well above it, but you try to find some kind of clear survey on this subject on the internet -- I know I did! $\endgroup$ – Dan Sheppard Sep 24 '15 at 21:45
  • $\begingroup$ I've a reason to want to do it: that TPMs come with decrypt-only EK certs, but I want to build a simple server enrollment protocol and not have to worry about replay protection. In a comment to another answer to this question I explain why TPM EKcerts are decrypt-only. None of that means it's safe to use OEAP for signing. But recall that only PSS is provably secure, yet it's mostly not used, while the RSA digital signature algorithm that is most used is not provably secure. Still, no need to add new uses of not-provably secure algorithms. $\endgroup$ – user2259432 Jan 31 at 3:05

One good reason not to use RSAES-OAEP for signature is because as it stands, it can't do signature! RSAES-OAEP performs encryption of a message (of limited length) with optional label into a cryptogram, and decryption thereof. There is no way to turn some RSAES-OAEP black box into a signing machine.

OK, we could define an RSA signature scheme with a signature procedure that

  • hashes the message $M$ to be signed into $H$
  • applies OAEP padding on $H$ rather than $M$, with lHash (the hash of) some fixed constant, perhaps the 01 changed to some other non-zero byte, and as usual seed randomness as wide as the hash, and PS just enough zeroes to fill-in OAEP
  • applies the RSA private key function $x\to x^d\bmod N$

and the signature verification procedure matching that. I do not know that this was studied, or that we have a security reduction proving that if this signature scheme can be broken, then we can can break one of its components. I won't hazard into trying to guess in what framework such reduction could be made, and how quantitative it could be.

And why bother? The above signature scheme has no clear advantage over RSASSA-PSS, which has security reductions[*], is accepted by security authorities, and widely used. In particular, there is no grounds for fear about patents when using PSS signature, and there seldom was any (in my non-lawyer opinion and from the relative comfort of Europe on the legal uncertainty standpoint); quoting PKCS#1 v2.2 appendix D on intellectual property considerations:

The PSS signature scheme is described in U.S. Patent 6,266,771, which expired on July 24, 2009, and U.S. Patent 7,036,014, which expired on April 25, 2010, and was held by the University of California. The PSS signature scheme is specified in IEEE P1363a-2004. Prior to the finalization of this standard, the University of California provided a letter to the IEEE P1363 working group stating that if the PSS signature scheme is included in an IEEE standard, “the University of California will, when that standard is adopted, FREELY license any conforming implementation of PSS as a technique for achieving a digital signature with appendix”.

[*] I vaguely recall debate about if PSS security reductions are quantitatively satisfactory for practically used modulus size and other parameters, but fail to locate a source.

  • $\begingroup$ Thanks for you answer, which i'll accept in a bit if nothing marvelously wonderful comes along. A number of people have asked "why bother"? The answer is in my question patents. You have reassured me on this. But the original problem comes from a discussion about file formats. If there's one thing that can sink a file format and cause a whole load of pain it's patents. It's probably better, for the case in question, that the signatures be forgeable or not included at all in the scheme than some patent troll pop up in a couple of dozen years and do a gif/mp3 to it. $\endgroup$ – Dan Sheppard Sep 24 '15 at 21:39
  • 1
    $\begingroup$ [I'm not daft enough to be rolling my own signature protocols, :-) . It seemed conceivable to me, until the answers here, given the extreme disorder of crypto standards, that in some backwater standard there was a perfectly respectable but mysteriously neglected OAEP-based scheme]. $\endgroup$ – Dan Sheppard Sep 24 '15 at 21:42
  • $\begingroup$ One reason to use OAEP for signature generation is to provide signatures giving message recovery using a padding scheme that is present in most libraries. That said, most cryptographic libraries won't work if you use OAEP with a private key (and usually there is good reason for that, since private key operations require different implementation / security than encryption with a public key). So in that sense it is still pretty useless. PSS with message recovery (PSS-R) has been defined by Bellare and Rogaway, but I've never seen it used in practice. $\endgroup$ – Maarten Bodewes Aug 20 '18 at 16:06
  • $\begingroup$ Here's why bother: because sometimes you're stuck with a decrypt-only certificate. When? Well, TPM EK certificates are decrypt-only as a privacy protection measure for DRM use-cases of TPMs, which is nice and all... But if you're building a server enrollment function in an enterprise, you don't care about privacy, and it's much easier to build a protocol using signatures (TLS w/ client certs!) than to build one using encryption to the EKcert. You can think this is a lame reason, and... it is. But building a multi-rt protocol w/ replay protection is not trivial either. $\endgroup$ – user2259432 Jan 31 at 3:01

The accepted answer is correct, but it's useful to understand why. RSA digital signatures use the same mathematical operation to sign as RSA encryption uses to decrypt, fine, but when signing the message is used as a ciphertext whose "plaintext" is the signature, but OEAP's entire point is to make it so that random ciphertexts don't produce plaintext that passes a cryptographic sanity check! So if you attempt to "sign" a message be applying RSA-OEAP decryption to it, the RSA-OEAP decryption operation is exceedingly likely to fail. Therefore you can't make a digital signature scheme out of RSA-OEAP.

  • $\begingroup$ You mean we can't we get the plain-text back if we encrypt with OAEP. $\endgroup$ – kelalaka Feb 6 at 7: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.