16.1 Digital Signatures Explained

Digital signatures are a different application of the asymmetric algorithms that we discussed in Chapter 15. You use an asymmetric key pair to create a "signature" for a message by adding a signature function to the asymmetric algorithm. The recipient can verify the signature using a verification function. Asymmetric algorithms that support signature and verification functions are digital signature algorithms. Each digital signature is specific to an individual message or document, and if Alice signs a message, Bob can be confident that Eve has not sent him a forgery.

Figure 16-1 provides an overview of using digital signatures, which work as follows:

1. Alice selects an asymmetric signature algorithm and follows the key generation protocol to create a new pair of keys. She keeps her private key secret and sends the public key to Bob.

2. Alice composes a message and creates a signature using her private key.

3. Alice sends the message and the signature to Bob.

4. Bob uses Alice's public key to verify the signature. If the signature is valid, Bob can be confident that:

   1. Alice is truly the author of the message.

   2. Eve has not altered the message contents.

Figure 16-1. Using asymmetric signature algorithms to provide message authentication

Notice that Alice, the sender of the message, creates the key pair and retains the private key; this is different from asymmetric encryption, where the recipient (Bob) is responsible for key creation. Digitally signing a message creates a separate piece of data, which Alice sends to Bob along with the message.

The relatively slow performance of asymmetric algorithms means that Alice does not sign the entire message she wants to send; instead, she creates a cryptographic hash code for the message and signs this instead. Subject to the limitations of hash code security (discussed in Chapter 13), signing hash code for a message is equivalent to signing the message itself, but is much faster, because the hash code is less data to process with the asymmetric algorithm. Figure 16-2 illustrates the way that Alice creates the signature by using her private key, the data hash code, and the asymmetric signature function.

Figure 16-2. Using a hash code as the basis for creating a digital signature

Bob verifies the signature by creating his own hash code and using the asymmetric signature verification and Alice's public key. Bob cannot verify the signature if the message is altered in any way, meaning that Eve cannot secretly tamper with the contents and Bob cannot alter a message and later claim that Alice had signed the altered version. Alice and Bob must use the same hash code algorithm; otherwise, Bob will not be able to verify valid signatures. Figure 16-3 illustrates how Bob verifies a signature.

Figure 16-3. Using a hash code as the basis for verifying a digital signature

Digital signatures allow more than one person to sign a message or document, such as a contract. Each person signs the message using the basic protocol we described, and sends their signature to all of the other signatories. If Alice and Bob wish to sign a digital contract, the basic protocol that they use is as follows:

1. Alice and Bob agree on the contents of the contract they will sign.

2. Alice creates a hash code for the contract and signs it with her private key.

3. Bob creates a hash code for the contract and signs it with his private key.

4. Alice and Bob exchange digital signatures and public keys.

5. Alice checks that Bob has used the correct hash code (and therefore has signed the expected version of the contract) and verifies the signature using his public key.

6. Bob checks that Alice has used the correct hash code and verifies the signature using her public key.

Should there be any dispute, a third party (perhaps a judge or other arbitrator) can use Alice and Bob's pubic keys to verify that both Alice and Bob have signed the same contract. Neither party can alter the contract (because then the hash code would not match) nor deny that they signed the contract (because the third party can verify each separate signature).

16.1.1 Digital Signature Security

Digital signatures have two objectives: they must be cryptographically secure and they must provide equivalent security features to an ink signature on a printed document. We summarize the security features of digital signatures as follows:

• Eve should not be able to forge Alice's digital signature. Eve cannot create a fake signature unless she knows Alice's private key; as in almost all aspects of cryptography, digital signatures rely on the careful protection and management of keys. If Eve could forge Alice's signature, Eve could make it appear that Alice has signed any document.

• Eve should not be able to reuse one of Alice's digital signatures. Eve can only take Alice's signature from one document and associate it with another if both documents produce the same data hash code. See Chapter 13 for details of why this is not a simple thing to achieve.

• Eve should not be able to alter a signed document. If Eve alters the content of a document, then Alice's signature will no longer be valid, because the altered document will produce a different data hash code to the one that Alice signed. Eve could alter a document successfully if it resulted in the same data hash code as the original (which is, in effect, the same as reusing Alice's signature).

• Alice should not be able to deny that she has signed a document. Alice cannot sign a document and then later claim that she did not, because we assume that she is the only person who knows her secret key. If she suspects that her key has been compromised, then she must create a new key pair.

From these features, you can see that digital signatures provide a reasonable analogue to a physical signature. You can also see that the entire security of digital signatures is dependent on the following assumptions:

• Eve is unable to guess or otherwise obtain Alice's secret key.

• Eve is unable to find a document that results in a specific data hash value.

We know that these assumptions are optimistic. Eve can find Alice's secret key by testing every possible value and find a document that results in a specific hash code if she creates and tests enough variations. In Chapter 13 and Chapter 14, we found that Eve can do these things, but that they can take her a very long time to accomplish. The security of digital signatures, like every other aspect of cryptography, is based on probabilities and effective key management. When using digital signatures, you should be aware that they are susceptible to the same attacks as data hash codes and asymmetric keys.

The final point raises a very serious issue. Alice should not be able to sign a document and then later claim that she did not. Relying on digital signatures means making another assumption: Alice is responsible for all signatures created with her private key, even if Eve is able to guess the secret value.

The problem that this presents is that Eve may be able to guess Alice's private key by brute force without Alice being aware that her private key is compromised. Eve could then sign documents using Alice's signature, but Alice would not find out that this was happening until it was too late. For example, if Eve signs a digital money order to herself, Alice will not know that money is missing from her account until she receives her next bank statement.

We need Alice to be responsible for signatures created with her key; otherwise, digital signatures would be worthless, and Alice could simply deny signing documents that are not in her favor. On the other hand, because it is possible to guess the value of Alice's key, we run the risk of holding her responsible for signatures that she really did not create. There is currently no solution to this problem, which is a fundamental barrier to the adoption of digital signatures.

16.1.2 The .NET Framework Digital Signature Algorithms

The .NET Framework includes two asymmetric algorithms that support digital signatures, one is the RSA algorithm that we discussed in Chapter 15; this algorithm defines functions for both data encryption and digital signatures.

The second algorithm is the Digital Signature Algorithm (DSA), published as a U.S. FIPS in May 1994. DSA supports digital signatures but not data encryption. Initially created to provide a standard algorithm for digital signatures for federal projects, DSA has gained support in commercial projects gradually but still lags behind RSA in terms of adoption.

The creators of DSA based their design, in part, on the ElGamal algorithm that we introduced in Chapter 15. In Section 16.4 of this chapter, we add support for signatures and signature formatting to our ElGamal implementation.

All asymmetric algorithms include a key generation protocol, similar to the ones that we discussed in Chapter 15. If an algorithm supports both encryption and digital signatures, then the same keys can be used by the encryption, decryption, signature, and verification functions; following the key generation protocol results in keys that can be used for all asymmetric cryptographic tasks.

16.1.3 Creating Digital Signatures

The hash code created from the document to be signed is usually formatted before being processed by the algorithm's signature function; this ensures that the specified key pair pads the hash code to the maximum size that can be signed. See Chapter 15 for more information about how to determine the length of a key and how the length affects the amount of data that algorithm functions can process. The act of formatting a hash code before it is signed also protects the digital signature from certain types of cryptographic attack.

The most commonly used signature-formatting protocol is PKCS #1, which we summarize as follows:

1. Create H, the cryptographic hash code for the document. SHA-1 and MD5 are the most commonly used hashing algorithms; see Chapter 13 for details of these hashing algorithms and the .NET Framework support for them.

2. Concatenate the hashing algorithm ID and the hexadecimal representation of the hash code together to form the DigestInfo value. Each hashing algorithm has a unique identifier. Table 16-1 lists the hexadecimal IDs for each of the algorithms that the .NET Framework supports.

3. Create an array of padding bytes, PS; the value of each byte is 255. The number of bytes to create depends on the length of the key and the length of DigestInfo. The number of bytes is , where the lengths DigestInfo and the key are expressed in bytes. The length of PS will be at least 8 bytes.

4. Combine the following to form the formatted data:

   1. One byte with a value of 0

   2. One byte with a value of 1

   3. The padding string PS

   4. DigestInfo, represented as bytes

The acronym PKCS stands for Public Key Cryptography Standard, which is a series of documents published by RSA Security, whose founders developed the RSA Algorithm. The PKCS #1 formatting for digital signatures is not the same as the PKCS #1 padding that we described in Chapter 15.

Each PKCS standard addresses a specific aspect of asymmetric cryptography, and PKCS #1 describes how to use the RSA algorithm for encryption and digital signatures. The PKCS #1 data padding and signature formatting techniques we describe are both contained in the PKCS #1 document.

Table 16-1. Hexadecimal IDs for hashing algorithms

Algorithm	Hexadecimal ID
MD5	30 20 30 0c 06 08 2a 86 48 86 f7 0d 02 05 05 00 04 10
SHA-1	30 21 30 09 06 05 2b 0e 03 02 1a 05 00 04 14
SHA-256	30 31 30 0d 06 09 60 86 48 01 65 03 04 02 01 05 00 04 20
SHA-384	30 41 30 0d 06 09 60 86 48 01 65 03 04 02 02 05 00 04 30
SHA-512	30 51 30 0d 06 09 60 86 48 01 65 03 04 02 03 05 00 04 40

Once you have created the formatted data, sign it using the signature function. In this section, we continue our illustrations using the RSA protocol. The RSA signature function is shown below, where s is the signature value and m is the formatted data to sign:

s = m^dmodn

The values d and n are parameters of the RSA key; see the previous chapter for details about RSA key pairs and how to create them. The RSA key length required to create a digital signature depends on the size of the hash code that the selected hashing algorithm produces. For example, MD5 produces a 128-bit hash code, and with the 18 bytes of the algorithm ID and the 11 bytes of data that PKCS #1 formatting adds as a minimum, you need a key that is able to process 360-bits of data. Therefore, the smallest key length that you can use to sign a PKCS #1-formatted MD5 hash code is 368 bits.

We won't walk through the computation required to create a digital signature because the numeric values that make up a 368-bit key are simply too large to print on a page; see Chapter 15 for an example of using the RSA functions with small key lengths.

To verify a signature, take the document you have received and create a PKCS #1-formatted hash code, following the protocol we described previously. Use the RSA verification function, shown below, where m² is the verification result, s is the digital signature, and e and n are the RSA public key parameters:

m₂ = s^emodn

When you verify the signature, the value of m² should be the PKCS #1-formatted hash code that you created from the document you received with the signature. If someone has tampered with the document in transit, the value of the hash code that you created will be different then the output of the verification function, and you should reject the signature.

Notice that the RSA signature and verification functions are the same as the encryption and decryption functions that we described in Chapter 15; the signature and decryption functions are identical, as are the verification and encryption functions. This relationship does not apply to all asymmetric algorithms, and we describe a very different approach when we extend our ElGamal implementation in the Section 16.4.

The DSA algorithm specification requires that PKCS #1 formatting is always used, and all hash codes are generated using the SHA-1 hashing algorithm. The SHA-1 algorithm ID is still included as part of the PKCS #1 formatting.