Mark Haas & Associates

The Next Step in RSA Digital Signatures
By Burt Kaliski, Chief Scientist, RSA Laboratories (ghost written by Mark Haas)

Digital signatures today are gaining in importance as nations around the globe pass legislation giving them equal legal standing with traditional handwritten signatures. By doing so, governments are paving the way for purely electronic transactions of all kinds, significantly reducing the need for paper documentation, while providing the opportunity for tremendous efficiency and productivity gains. As a result, digital signatures are poised to enter the mainstream as the primary vehicle for establishing trust for a wide variety of electronic transactions.
Most secure web transactions today are already based on digital signatures, which are included as part of the digital certificate a server presents to a client to identify itself. The digital certificate binds a public key with an identity, and enables a receiver to verify the sender's digital signature, or, as is the case when setting up a secure connection with a web server, enables only the identified server to decrypt the information being sent to it. The digital certificate caries the digital signature of the issuer of the certificate to enable the receiver to verify its legitimacy.
The RSA public-key cryptosystem and digital signature scheme are the most widely deployed today, and have become essential building blocks for creating the emerging public-key infrastructure (PKI). Electronic commerce has embraced this technology as a way to associate documents, transactions and so forth with their true originator, and to ensure their integrity.
Many standards for Internet and mobile e-commerce reference the RSA algorithm, often from the PKCS #1 v1.5 format developed in 1991. More recent proposals also use the RSA algorithm, including one developed by the U.S. banking industry, ANSI X9.31, and another that is being considered for new standards, called the Probabilistic Signature Scheme (PSS).
Considering all of the above, software developers may well be asking which standard for RSA digital signatures to follow as they develop new PKI applications. All employ the same underlying RSA algorithm, but they are incompatible with each other, and offer varying degrees of security.
This article will attempt to provide guidance to the community of programmers using RSA providing a discussion of the three most popular signature schemes today, illustrating how they are different, what the tradeoffs are and where and how RSA Laboratories thinks the industry should go over the next several years regarding these three approaches.

RSA Digital Signatures
The notion of digital signatures goes back to the beginning of public-key cryptography. In 1976, Diffie and Hellman wrote in their landmark paper, New Directions for Cryptography (W. Diffie and M.E. Hellman. New Directions in Cryptography. IEEE Transactions on Information Theory, IT-22: 644-654, 1976) the idea that someone could form a digital signature using public-key cryptography which anyone else could verify but which no one else could generate.
While Diffie and Hellman provided a general model for digital signatures of any kind, the method developed by Rivest, Shamir and Adleman in 1977, known as RSA, has become the most proven and most popular, and has achieved the widest adoption by standards bodies and in practice. Two other methods, discrete logarithm cryptography (including the Digital Signature Algorithm and the Diffie-Hellman key agreement method) and elliptic curve cryptography, have also been embodied in several standards, but neither has yet been as widely adopted in practice as RSA.
[Figure 1]
The RSA digital signature scheme applies the sender's private key to a message to generate a signature, as depicted in Figure 1. The signature can then be verified by applying the corresponding public key to the message and the signature through the verification process, providing either a valid or invalid result. These two operations – sign and verify – comprise the RSA digital signature scheme.
Any signature generated by the first operation will always verify correctly with the second operation if the corresponding public key is used. If the signature was generated differently, or if the message was altered after being signed, then the chances of the second operation verifying correctly are extremely small – when using 1024-bit keys, for example, the chance is roughly 1 in 21024, or essentially zero. Although there are better ways to forge a signature than just guessing, the use of a sufficiently large key ensures security by making it computationally impractical to do so. For instance it has been estimated to take thousands or even millions of years to “break” a given 1024-bit key (find the private key, given the public key), depending on the amount of computing power applied.
[Figure 2]
Taking a closer look at the signature generation portion of the process in Figure 2, the first step in generating an RSA signature is applying a cryptographic hash function to the message. The hash function is specifically designed to reduce a message of any length to a short number, called the hash value (typically 160 bits long), and do it in a way such that two conditions are satisfied: 1) it is difficult to find a message given a specific hash value, and 2) it is difficult to find two messages with the same hash value (an easier problem to solve). While many hash functions are available, only a few are commonly used in practice.
Next, the hash value is converted into an integer, called the message representative, whose length is the same as the length of the RSA key being employed, by applying a padding format to the resulting hash value, or "encoding" the hash value, to produce the message representative. In addition to its length-matching function, the padding format also provides additional security, and is the primary differentiator among the various RSA signature schemes. The final step applies the RSA signature primitive to the message representative using the RSA private key to generate the signature.
In mathematical notation, the RSA signature primitive computes the equation
s = m^d mod n
where
n = the RSA modulus d = the private exponent m = the message representative, and s = the RSA digital signature.
The RSA private key is formed by the RSA modulus n and the private exponent d.
Signature verification likewise starts with the message, which is first reduced by the same hash function to produce a new hash value. The signature verification process then applies the RSA verification primitive to the signature using the public key, which consists of the RSA modulus n and the public exponent e, to recover the message representative m' by computing the equation
m' = s^e mod n.
All that remains is to verify that the integer m', the recovered message representative, is a correct encoding of the new hash value through the verify process:
Verify (H', m’)
where H’ = hash (M) M = the original message
The verify process varies depending on the method used to encode the hash function as a message representative. The RSA primitive has not changed over time, and is the core ingredient of the digital signature. Hash functions have been studied and developed independently of RSA signatures, and it is generally assumed they will vary over time from one signature scheme to another, but good hash functions are essentially interchangeable and don't impact the security of the digital signature.
The three main RSA signature schemes – PKCS #1, ANSI X9.31 and PSS – differ mainly in the padding format the signature generation operation employs to encode the hash value into a message representative, and in how the signature verification operation determines that the hash value and the message representative are consistent.
With so much riding on the veracity of digital signatures, understanding the strength of the security any digital signature scheme provides is crucial. To forge a signature, an attacker needs to figure out a way to compute the RSA signature primitive without knowing the private key. Stated differently, given the RSA public key and the recovered integer m', an attacker needs a way to invert the RSA verification primitive and generate the digital signature s.
The strength of the RSA primitive is expressed as its average behavior. One can say the RSA primitive is good, on average – it's hard to break the RSA primitive but may be easy in some special cases. Given any m', it's usually quite difficult to invert the RSA primitive to create the signature (or more generally, to find ways to manipulate existing signatures to create a new one). But as it turns out, this is easier to do for some m's than for others, and this depends on the padding format, the critical connection between the hash function and the RSA primitive. (As a simple exercise for the reader, it’s trivial to invert the primitive for m' = 0, 1 or n?1. Of course, the chance that m' happens to have one of these values is essentially zero.)
The padding format is crucial to cryptographers' ability to prove the strength of a signature scheme’s security. Over the years, people have discovered a number of ways to exploit the RSA primitive, taking the same mathematical properties that make it strong and using them to make it weak in some special cases. And so proper use of the primitive – proper encoding of the hash value – ensures the mathematical properties can be used to advantage and security is not compromised.
The state of the art has advanced to the point where it is now possible to mathematically prove the strength of the security achieved through using the RSA primitive. Until recently, cryptographers could only make educated guesses about this. But current signature schemes don't reflect this new knowledge, and still employ padding formats that don't allow this proof. PKCS #1, developed in 1991, the most widely used signature scheme today, doesn't offer such a proof. ANSI X9.31, developed later in the 1990s, though not widely implemented, also doesn't offer a proof.
A new signature scheme first proposed in 1996, Bellare-Rogaway PSS, is generally recognized to offer a very good way to achieve this proof, but it has not been considered in standards until recently. But this is understandable because it takes time to make the transition from research to standards, giving the standards communities time to review the methods and have confidence they are effective, and to determine whether or not there are any better approaches on the horizon. Today, several standards bodies are working on this new signature scheme, and developers should expect to see it specified in the near future.

Why Change?
The PKCS #1 digital signature scheme has proven to be quite reliable and secure, and over time it may turn out to be sufficient to meet users' needs. But on the other hand, because there is no way to scientifically prove the strength of its effectiveness, it might turn out not to be sufficient. More importantly, there is no way to determine this today.. With methods for breaking security are improving all the time, staying with the current scheme runs the risk of having to make expensive infrastructure changes later when PKI deployment is much more extensive and much more difficult to change, a change that is sure to be reminiscent of the work necessary to avoid the Y2K problem. As if presenting an omen of this potential problem, another class of RSA signature schemes – not any of the ones being discussed here –thought to have been secure since the early 1990s where found to be vulnerable in the summer of 1999 when methods were devised to break it.
The new technology offered by PSS provides a way to mathematically prove the strength of the security, as opposed to just guessing at it, and it comes at a time when it is still possible to plan a phased approach to its adoption that results in minimal disruption to the current infrastructure. PKI today is still in its infancy, and there are plenty of opportunities to piggy-back the transition to PSS with other changes that will be necessary as other standards evolve.
For example, new hash methods will need to be incorporated in current applications. A new hash function, SHA-2, which the U.S. government will make available later this year is more suitable for certain applications. But changing hash functions does not require architectural changes, just supporting a new functions at one place in the architecture. Similarly, PSS involves only upgrading the padding format. The change is localized, and no architectural changes are necessary. The same RSA algorithm is employed, meaning no new mathematical routines are needed, and the same RSA keys are used.
Which signature scheme to use shouldn't be a question of what's in standards or what's in practice today, but what will ensure the integrity of the infrastructure for the longest term.

PKCS #1 v1.5
The most common RSA-based signature scheme was developed in 1991 as part of RSA Laboratories' Public-Key Cryptography Standards (PKCS). In this scheme, described in the PKCS #1 v1.5 document, a simple padding format (embedding) is applied to the hash value to produce a message representative, as illustrated in Figure 3.
[Figure 3]
The format was designed with two main security goals in mind:

• It should be difficult to find message representatives that have some mathematical relationship: for instance to find message representatives m1, m2 and m3 such that m1 = m2 * m3 mod n. If someone could do so, then it might be possible for forge signatures because the corresponding signatures would have the same relationship, and a signature on a new message could be forged by combining the signatures on other messages. The padding format achieves this property in part by padding the hash value to the full length of the modulus n.
• The message representative should identify the hash function. This is important because in practice many different hash functions may be used, and it prevents an adversary from trying to forge a signature by causing the verifier to use a different hash function than the signer intended.

The PKCS #1 v1.5 signature scheme has held up to scrutiny over the past decade, though no formal proof of the scheme's security is known, and is widely deployed. Most digital certificates in the Secure Socket Layer (SSL) protocol, for instance, are signed with PKCS #1 v1.5. The signature scheme is cited in many other Internet-related standards as well.
The PKCS #1 v1.5 document (as well as the latest version, v2.0, which continues to support the v1.5 signature scheme), can be downloaded from RSA Laboratories' PKCS web page, http://www.rsalabs.com/pkcs/.

ANSI X9.31
Another RSA-based signature scheme, ANSI X9.31 was developed in the late 1990s by the ANSI X9F1 standards working group, which produces data security standards for the U.S. financial services industry. This scheme is described in the ANSI X9.31-1998 standard, "Digital Signatures Using Reversible Public Key Cryptography for the Financial Services Industry (rDSA)." Again, a simple padding format is applied to the hash value to produce a message representative, as illustrated in Figure 4.
[Figure 4]
The format was designed with the same security goals in mind as PKCS #1 v1.5. For compatibility with certain international standards, a different padding format than the one used in PKCS #1 v1.5 was chosen. Like PKCS #1 v1.5, no formal proof of the scheme's security is known.
ANSI X9.31 standardizes other aspects of RSA digital signatures such as key size (the minimum is 1024 bits), how keys are generated, and the underlying hash function (SHA-1 or another ANSI-approved hash function). The signature operation also has an additional "absolute value" step where the smaller of the values s and n ? s is selected, and this saves one bit in the size of the resulting signature. The verification operation "disambiguates" between the two possibilities by checking the rightmost byte of the recovered message representative.
The ANSI X9.31 signature scheme has not yet been widely deployed, but it does have significant support by standards bodies. For instance, FIPS 186-2, the digital signature standard for U.S. federal agencies, lists the ANSI X9.31 signature scheme as one of three options (the others are the Digital Signature Algorithm and the Elliptic Curve Digital Signature Algorithm specified in ANSI X9.62). IEEE Std 1363-2000, which specifies a large set of public-key techniques, and ISO/IEC 14888-3, an international digital signature standard, also include the ANSI X9.31 signature scheme.
The ANSI X9.31 standard can be purchased on-line from ANSI at http://www.ansi.org/

Bellare-Rogaway PSS
Addressing the concern that many RSA-based signature scheme had only "ad-hoc" or anecdotal assurances of security, University of California researchers Mihir Bellare and Phillip Rogaway in 1996 proposed a new RSA-based scheme that enables a formal proof of security.
This security of this method, called Probabilistic Signature Scheme (PSS) because of its use of randomization, can be closely related to the security of the RSA algorithm itself. Bellare and Rogaway showed that any general-purpose algorithm for forging PSS signatures could be used to break the underlying RSA algorithm. As a result, if the RSA algorithm is secure, PSS signatures will be hard to forge by any general-purpose algorithm. (In contrast, PKCS #1 v1.5 or ANSI X9.31 signatures might be easy to forge, even if the RSA algorithm is secure, because no formal proof is known for those schemes.)
[Figure 5]
Figure 5 gives the specification for the padding format for PSS from draft D5 of IEEE P1363a, a proposed amendment to IEEE Std 1363-2000. The padding format is an adaptation of Bellare and Rogaway's original format that fits the model of producing a message representative from a hash value, and addresses other implementation issues.
In the PKCS #1 and ANSI X9.31 schemes, most of the bytes of the message representative are fixed padding. An attacker who can invert the RSA function for message representatives having those bytes can forge a signature. It is possible that this is easier to do than inverting the RSA function on arbitrary values.
PSS overcomes this potential vulnerability by producing random-looking message representatives. Rather than concatentating a hash value with fixed padding, the padding format generates a "random" mask from the hash value and exclusive-ORs it with the fixed padding. As further protection, PSS includes a random “salt” value which makes it difficult for an attacker to determine in advance what the message representative will be for a given message. This protection, along with other features, helps in the proof of security for PSS.
A variant of PSS, called PSS-R (where the R stands for "message recovery"), conveys part of the message being signed within the signature itself, thereby reducing the overhead due to the signature. The padding format allows this variant as well, which is the reason for some of the peculiar features in Figure 5 (e.g., the first string of 00 bytes, which is the length of the recoverable part, and is empty).
Several standards are being drafted that include PSS or PSS-R. Among these are IEEE P1363a; a revision of ISO/IEC 9796-2, an international digital signature standard; and the upcoming PKCS #1 v2.1.
The latest draft of IEEE P1363a can be downloaded from http://grouper.ieee.org/groups/1363, while the latest draft of PKCS #1 v2.1 is available from the PKCS web page noted above.

Recommendation for Future Direction
The incompatibility of the PKCS #1 v1.5 and ANSI X9.31 signature schemes limits interoperability. To address this concern, it seems reasonable that both formats should be allowed in standards and supported in practice. Some steps have already been taken in this direction. For instance, NIST is allowing a "grace period" during the implementation of FIPS 186-2 whereby PKCS #1 v1.5 signatures will also be acceptable for federal agency use.
In the long term, the Bellare-Rogaway PSS signature scheme is preferable in standards and in practice because of its stronger security assurances. Although no weaknesses have yet been found in the PKCS #1 v1.5 or ANSI X9.31 signature schemes, no proof has been given that weaknesses do not exist. While there is no immediate need to change to PSS, a gradual upgrade process can begin which will yield the eventual benefits. The standards development efforts already underway are preparing the path for this upgrade. The primary area for interoperability is the padding format itself, but for full interoperability, additional aspects must be compatible as well, such as the choice of hash function and the range of key sizes supported. Other aspects can usually be left to the implementation, such as how key pairs are generated and how private keys are stored. These "assurance" issues are the ones where industry, banking and government standards often need to diverge; the padding format itself need not be a cause for incompatibility.

Conclusion
Developers today have the opportunity to make a planned, gradual migration to an RSA digital signature scheme offering several compelling benefits, most notably provable security, continued use of existing RSA keys and hardware accelerators and straightforward, localized software changes.
The time to act is now, and the industry is ready for this change. Extensive work has already done to make architectures algorithm independent, and implementing this improved digital signature scheme can build on that. Systems are constantly undergoing other upgrades and maintenance works as new hash functions, encryption algorithms (such as AES) and digital certificates (such as attribute certificates) are embraced. Over time, systems will need to be modified to accommodate these changes anyway. As systems are upgraded to support new kinds of information in their digital certificates, they can have their digital signature scheme upgraded as well.
And developers need to keep in mind that in spite of the fact there will need to be changes, these are only changes in how the hash value is processed, not in any of the underlying mathematics or the keys or anything else. Investments made to develop software or hardware support to implement the RSA functions are preserved.
RSA Laboratories believes adopting the Bellare-Rogaway PSS signature scheme is a prudent investment for protecting the future public-key infratstructure by providing provable security with minimal disruption to the current architecture.

# # #