3.5. Digital Signatures

Suppose that Alice sends a message to Bob. Digital signatures provide a way for Alice to certify that she is the sender of the message and that the message has not been altered after it was signed. As the name suggests, a digital signature is the digital equivalent of the traditional written signature.

This concept is similar to the notion of the message authentication code that we discussed in the previous section, but as we shall see, MACs are not appropriate for use in digital signature applications. The major problem is that MACs are symmetric algorithmsthey use the same key to verify the MAC as they do to generate the MAC.

It's easy to see why this is a problem: If Bob has Alice's signature key, he can forge messages from Alice. Furthermore, Bob can't demonstrate the genuineness of the message to third parties, because he can't prove that Alice, not he, signed the message. This last propertybeing able to prove to a third party that Alice signed the messageis called nonrepudiation and is an important concern because one use of digital signatures is for Alice to sign, say, a contract in digital form. There is also the problem of scaling that we discussed in connection with symmetric ciphers: The number of keys required grows quadratically with the number of parties wishing to send signed messages to each other.

These considerations suggest using one of our asymmetric algorithms to form a digital signature. Fortunately, this is easy to do, and we shall discuss two of the most-used methods: RSA and DSS.

RSA Digital Signatures

It's natural to use RSA as a way of signing messages. When using RSA to encrypt messages, Alice encrypts the message with Bob's public key and sends the message to Bob, who uses his private key to decrypt it. There is, however, nothing special about the role of the two keys; Alice could just as well encrypt the message with her private key. That would mean that anyone with Alice's public key could decrypt the message, so doing this serves no privacy function, but observe that anyone who does decrypt it with Alice's public key will know that the message is from Alice and that it hasn't been altered, because only Alice could have encrypted it. Alice has, in effect, signed the message. This method was suggested by Rivest, Shamir, and Adleman in their paper describing the RSA algorithm. In fact, that paper, [Rivest, Shamir, and Adleman 1978], was entitled A Method for Obtaining Digital Signatures and Public-Key Cryptosystems, suggesting that they viewed the ability to use the algorithm for digital signatures as important as its use for encryption. The paper discusses using RSA for digital signatures in detail.

Just as with encryption, it usually doesn't make sense to sign a message by encrypting the message itself. Rather, the normal procedure is to first take a digest of the message, using a cryptographic hash function, and then sign the digest by encrypting it with a private key. Just as with encrypting session keys, one must encode the signature in some way to avoid obvious weaknesses, such as small digests. PKCS #1 [RSA Laboratories 2002] specifies two such methods; [Ferguson and Schneier 2003] suggests another.

To avoid certain attacks, there are usually separate keys for encryption and signing. Typically, the same modulus (n = pq) is used, but a different e, and therefore d, is chosen for signing and encryption. This is, however, an implementation detail and doesn't affect the way we use and form digital signatures.

When Bob receives a message from Alice, he verifies the signature by decrypting the digest with Alice's public key, computing the hash of the message himself, and verifying that the two values are the same. Recall that given a message, m, it is very difficult to find another message m' such that they hash to the same value. For this reason, signing the hash of a message provides the necessary verifiability.

The Digital Signature Standard

On May 19, 1994, NIST published the Digital Signature Standard (DSS) as FIPS (Federal Information Processing Standards) 186. The standard was revised in 1998 (FIPS 186-1) and again in 2000 (FIPS 186-2). The latest version, [NIST 2001], contains an important change notice dated October 5, 2001.

DSS specifies an algorithm, the Digital Signature Algorithm (DSA), that is used to digitally sign messages. Although DSA is similar to ElGamal encryption, it is intended solely for signing digital documents.

However, [Schneier 1996] points out that one can, in fact, use it for encryption.

FIPS 186-2 also allows digital signature algorithms using RSA and elliptic curves, but the standard does not describe these algorithms. It merely includes them by reference to their specifications (ANSI X9.31 and X9.62).

To use DSA, we first pick

Next, we calculate g = h^(p-1)/q and y = g^x. The numbers p, q, and g are public and can be shared by a group of users. The public key is y, and the corresponding private key is x.

To sign a message m, we pick a random number k such that 1 < k < q, and calculate

r = (g^k mod p) mod q

s = (k^-1(S(m) + xr)) mod q

where k^-1 is the multiplicative inverse of k mod q, and S(m) is the SHA-1 hash of m. A new value of k is chosen for every signature. The digital signature of m is the two numbers r and s.

To verify the signature, we first check that 0 < r, s < q and reject the signature if not. Then we calculate

w = s^-1 mod q

u1 = (wS(m)) mod q

u2 = (rw) mod q

v = ((g^u1y^u2) mod p) mod q

We consider the signature verified if v = r. A proof that v = r for the same message m is in [NIST 2001].

MD5 and SHA-1 Security

One of the necessary properties of a cryptographic hash function is strong collision resistance. That is, given a hash function h, it is computationally infeasible to find messages m₁ and m₂ such that h(m₁) = h(m₂).

By the birthday paradox, computationally infeasible means that it takes O(2^½) operations to find a collision, where l is the length in bits of the hash function output. We often express this by saying that finding a hash collision by brute force takes 2^½ work. Thus, for example, the expected work to find a SHA-1 collision is 2⁸⁰.

At the CRYPTO 2004 conference in August 2004, a team of Chinese cryptographers led by Xiaoyun Wang announced that it had devised a method to generate collisions in MD5and other related hash functions but not SHA-1thus violating the strong collision resistance property. Wang's announcement did not include any details, but she and her colleagues did publish a short note [Wang, Feng, Lai, and Yu 2004] that showed colliding messages and stated that finding them took about an hour on an IBM P690 supercomputer. A later paper [Wang and Yu 2005] provided the details of the Wang team's method, which uses a form of differential cryptanalysis to find the collisions.

In early 2005, Vlastimil Klima discovered an independent method that was able to generate MD5 collisions on a 1.6 GHz laptop computer in about 8 hours [Klima 2005].

[Lenstra, Wang, and Wegner 2005] showed how to use Wang's method to produce a pair of X.509 certificates (Section 3.6) with the same MD5-based signature. The two certificates differ only in their public keys and thus don't constitute a usable exploit, but they do suggest that using MD5 as a signature method is no longer safe.

In February 2005, [Wang, Yin, and Yu 2005] announced an attack on SHA-1 that can find collisions with 2⁶⁹ work instead of the 2⁸⁰ work required for brute force. At the time of this writing, the details of the attack have not been published.

Although O(2⁶⁹) operations is still on the far side of practical, it is just barely so. Thus, even though the practical effects of the attack are limited, it does sound the death knell for SHA-1. We can expect that a combination of refinements in the attack and ever-expanding computing power will eventually force the abandonment of SHA-1. Indeed, NIST has already announced its intention to phase out SHA-1 in favor of stronger hash functions in the SHA family, such as SHA-256 and SHA-512, by 2010 (<http://csrc.nist.gov/hash_standards_comments.pdf>).

It is important to keep these results in perspective. They don't mean that digital signatures, secure email, and other applications of hash functions are suddenly unsafe. Indeed, some hash-based functions, such as HMAC, are not affected at all. Most important, we should be aware of what these attacks cannot do: they cannot find a preimage. That is, given a hash function, h, and a hash value, x, it is still computationally infeasible to find a message, m, such that h(x) = m.