Raising the Standard for RSA Signatures: RSA-PSS
Burt Kaliski, RSA Laboratories
February 26, 2003
RSA-PSS is a new signature scheme that is based on the RSA cryptosystem and provides increased security assurance. It was added in version 2.1 of PKCS #1.
While the traditional and widely deployed PKCS #1 v1.5 signature scheme is still appropriate to use, RSA Laboratories encourages a gradual transition to RSA-PSS as new applications are developed.
The "PSS" refers to the original Probabilistic Signature Scheme by Mihir Bellare and Phillip Rogaway on which RSA-PSS is based. Bellare and Rogaway's work raised the bar in the research community for practical, secure signature schemes based on the RSA cryptosystem. RSA-PSS is the adaptation of their work to industry standards.
RSA-PSS has recently been added to RSA Security's RSA BSAFE Crypto-C and Crypto-J toolkits.
How RSA-PSS Works
RSA-PSS, like most digital signature schemes, follows the “hash-then-sign” paradigm. Let M be a message to be signed. A signature is computed on the message M in three steps:
1. Apply a one-way hash function to the message M to produce
a hash value mHash.
2. Transform the hash value mHash into an encoded message EM.
3. Apply a signature primitive to the encoded message EM using the private key to produce a signature S.
This can be expressed in equation form as
S = SigPrim (private key, Transform (Hash (M)))
Here, SigPrim denotes the signature primitive. With the RSA cryptosystem, this is the classic formula
S = EMdmod n
where (n, d) is the private key, and EM and S are considered as integers.
Assuming that the encoded message can be recovered from the signature, which is the case for the schemes described here, the signature is verified in three steps:
1. Apply a one-way hash function to the message to produce a hash value
2. Apply a verification primitive to the signature S to recover the encoded message EM.
3. Determine whether the encoded message EM is a valid transform of the hash value mHash. (If there is only one valid transform of each hash value, then one can just transform mHash again and compare to EM; but if more than one, further processing is needed.)
In the PKCS #1 v1.5 signature scheme, the Transform operation consists of fixed padding; the hash value is simply prepended with a header string of the form 00 01 ff ff … ff ff 00 (in hexadecimal) followed by a string that identifies the hash function. In RSA-PSS, the operation is much more “random.” Instead of fixed padding, the scheme generates a random “salt” value then applies a hash function and a mask generation function to the salt and the hash value to produce the encoded message. The transformation, illustrated in Figure 1, consists of the following steps:
1. Generate a random salt value salt.
2. Concatenate fixed padding, the hash value mHash, and salt to form a string M’.
3. Apply the hash function to the string M’ to compute a hash value H.
4. Concatenate fixed padding and the salt value to form a data block DB.
5. Apply the mask generation function to the string M’ to compute a mask value dbMask.
6. Exclusive-or the mask value dbMask with the data block DB to compute a string maskedDB.
7. Concatenate maskedDB, the hash value H, and fixed padding to compute the encoded message EM.
To determine whether an encoded message EM is a valid transformation of a given hash value mHash, one simply reverses steps 7 to 4 to recover the salt value and original hash value H, then repeats steps 2 and 3 to see if the hash value is correct.
Because of the hash function and the mask generation function, the encoded message EM is almost entirely “random” as there is no almost special structure that distinguishes it from a random string of the same length, assuming that the two functions are considered as “black boxes” (aka “random oracles”). The only non-random parts are the fixed padding bc at the end (introduced for compatibility with other standards efforts), and potentially a few leading 0 bits at the beginning (when EM is considered as an integer modulo n). In addition, the transformation is randomized because of the random salt value: there are many possible encoded messages and hence many possible signatures for a given message M. This helps with the security analysis as described next.
Figure 1: EMSA-PSS encoding operation. Verification operation follows reverse steps to recover salt, then forward steps to recompute and compare H. (Source: PKCS #1: RSA Cryptography Standard).
Advantages of RSA-PSS
The primary advantage of RSA-PSS over the traditional PKCS #1 v1.5 signature scheme is that modern methods of security analysis can relate its security directly to that of the RSA problem. While no attacks are known on the traditional scheme, and while solving the underlying RSA problem (e.g., factoring the modulus) is the best method known for forging a signature, the connection of PKCS #1 v1.5 signatures to the RSA problem has never been proved. RSA-PSS, in contrast, has such a proof if one models its hash functions as "random oracles" as is commonly done.
In recent years there has been a trend toward so-called "provably secure" cryptographic techniques that are more directly connected to underlying hard problems. If a signature scheme does not have a security proof, it is theoretically possible that signatures could be easy to forge, yet the underlying problem still be hard to solve. Ideally, one would like some assurance that the problems take about the same amount of time. Although the state of complexity theory does not let us prove that an underlying problem, e.g., RSA, is definitely hard to solve, we will still have the assurance that if the problem is indeed hard to solve, signatures are just as hard to forge.
RSA-PSS offers the long-term benefit of higher assurance by narrowing the gap between the widely held assumption that the RSA problem is hard to solve, and the claim that signatures are hard to forge. Indeed, RSA-PSS has one of the smallest such gaps among current "provably secure" techniques; in the usual parlance, the proof of security for RSA-PSS is very "tight." The randomization in the signature scheme plays an important role in achieving tightness and is one of the key contributions from Bellare and Rogaway’s PSS scheme.
Another advantage of RSA-PSS is that, due to the randomization, an attacker does not know in advance what the encoded message EM will be. This makes "fault analysis" attacks of the sort proposed by Bellcore a few years ago more difficult to mount (see the RSA Laboratories’ Bulletin No. 5).
The signature scheme has been recommended by the European NESSIE project, and has also received positive evaluations by from Japan's CRYPTREC project. RSA-PSS is also in the (nearly final) draft amendment IEEE P1363a. A companion scheme that also provides "message recovery" is included in the international standard ISO/IEC 9796-2:2002.
RSA Laboratories is encouraging a gradual transition to RSA-PSS as standards bodies upgrade to new techniques in other areas, such as SHA-256 and AES. As one example of the ongoing work, a profile for specifying RSA-PSS within IETF PKIX certificates has been published as an Internet-Draft. RSA Laboratories welcomes suggestions for other venues in which to promote the new scheme.
- Mihir Bellare and Phillip Rogaway. The exact security of digital
signatures: How to sign with RSA and Rabin. In U. Maurer, editor, Advances
in Cryptology - EUROCRYPT 96, volume 1070 of Lecture Notes in
Computer Science, Springer-Verlag, 1996, pages 399-416. Full version
available via http://www.cs.ucdavis.edu/~rogaway/.
- Jean-Sébastien Coron. Optimal security proofs for PSS and
other signature schemes. In L.R. Knudsen, editor, Advances in Cryptology
- EUROCRYPT 2002, vol. 2332 of Lecture Notes in Computer Science,
Springer, 2002, pages 272-287.
- Jakob Jonsson. Security proofs for the RSA-PSS signature scheme and
its variants. Presented at Second
NESSIE Workshop, September 12-13, 2001. Full version available as
IACR ePrint 2001/053, http://eprint.iacr.org/2001/053/.
- B.S. Kaliski Jr. RSA digital signatures. Dr. Dobb’s Journal,
May 2001. Available at http://www.ddj.com/articles/2001/0105/.
- NESSIE Security Report. Version 1.0, October 21, 2002. Available at https://www.cosic.esat.kuleuven.ac.be/nessie/deliverables/D20-v1.pdf.