RSA Digital Signatures

The RSA public-key cryptosystem and digital signature scheme are 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 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.

In this article, I'll examine three RSA-based signature schemes, illustrating how they are different, what the tradeoffs are, and where and how 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 their landmark paper "New Directions for Cryptography" (IEEE Transactions on Information Theory, 1976), Whitfield Diffie and Martin Hellman introduced the idea that someone could form a digital signature using public-key cryptography that 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 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 (see "Elliptic Curves and Cryptography," by Aleksandar Jurisic and Alfred J. Menezes, DDJ, April 1997) have also been embodied in several standards, but neither has yet been as widely adopted in practice as RSA.

The RSA digital signature scheme applies the sender's private key to a message to generate a signature; see 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; with typical parameters, the chance is roughly 1 in 2160 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.

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 to do it in a way such that two conditions are satisfied:

• It is difficult to find a message with a specific hash value.
• 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," with a length that is the same as the length of the RSA key being employed. This is done by applying a padding format to the resulting hash value or embedding 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 in Example 1(a), where n equals the RSA modulus, d equals the private exponent, m equals the message representative, and s equals 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 that 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 in Example 1(b).

All that remains is to verify that the integer m', the recovered message representative, is a correct embedding of the new hash value through the verify process, where H'=hash (M) and M equals 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 that 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 embed 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 a target 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. You 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 a cryptographer's 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. Proper use of the primitive — proper embedding of the hash value — ensures that the mathematical properties can be used to an 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. Although it is not yet possible to prove that the RSA primitive itself is secure — that, as for most other cryptographic primitives, rests on a well trusted assumption — it is possible to prove that a signature is as secure (within some factor) as the RSA primitive. 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, is the most widely used signature scheme today, and does not 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 determine whether 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 well remain 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 to be insufficient. More importantly, there is no way to determine this today.

With methods for breaking security 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, if necessary, is sure to be reminiscent on a smaller scale of the work necessary to avoid the Y2K problem. As if presenting an omen of this potential problem, another class of RSA signature schemes thought to have been secure since the early 1990s — not any of those being discussed here — was 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 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. The new hash functions, SHA-256, SHA-384, and SHA-512, which the U.S. government recently announced, are more suitable for certain applications. But changing hash functions does not require architectural changes, just supporting a new function 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 should not 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 in 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 m₁, m₂, and m₃, such that m₁=m₂*m₃ mod n. If someone could do so, then it might be possible to 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 and is widely deployed, though no formal proof of the scheme's security is known. 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), is available at 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; see 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 1 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 online from ANSI at http://www .ansi.org/.

Bellare-Rogaway PSS

Addressing the concern that many RSA-based signature schemes 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 primitive. As a result, assuming only that the RSA primitive 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 easier to forge than breaking the RSA primitive because no formal proof is known for those schemes.)

Figure 5 gives the specification for the padding format for PSS from draft D7 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, although not necessarily plausible, 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 concatenating a hash value with fixed padding, the padding format generates a random mask from the hash value and XORs it with the fixed padding. As further protection, PSS includes a random salt value that 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 (for example, the first string of 00 bytes is the length of the recoverable part, which is 0 here).

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 is available at http://grouper.ieee.org/groups/ 1363, while the latest draft of PKCS #1 v2.1 is available from the PKCS web page just noted.

Recommendation for Future Direction

The incompatibility of the PKCS #1 v1.5 and ANSI X9.31 signature schemes limits interoperability. Some steps have already been taken to address this concern. For instance, the National Institute of Standards and Testing (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 it has stronger security assurances. Although no weaknesses have 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. Already, extensive work has been 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.

You need to keep in mind that in spite of the 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 infrastructure by providing provable security with minimal disruption to the current architecture.

DDJ