Why not use OAEP for signatures?

Question

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?

Answer 1

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
• 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.}

Answer 2

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.