David Ross -- PGP -- Digital Signatures

The recent enactment of a federal law on digital signatures in electronic communications and commerce purposely omitted any specification of the technology to be used. While I believe that most initial uses of digital signatures will involve certificate authorities and the digital certificates that they issue for a fee, eventually PGP signatures (possibly when verified through a digital certificate) may also become prominent. California's law on digital signatures used by local government when filing legal documents with the state describes PGP without actually naming it.

A Case History

Early in 1998, I was an official proponent of the proposed reorganization of a Usenet newsgroup. The discussion of this proposal (via newsgroup messages) was more than vigorous or even heated. At times, it was nasty and vitriolic.

During that discussion, messages began to appear in which I indicated a change of mind. According to these messages, I now opposed the proposal. These messages were, of course, fakes with forged headers that used my E-mail address. I quickly halted this fraud. I sent a message to the newsgroup to alert the participants that fake messages were appearing under my name. This message, however, was signed with my PGP key. The text warned others that any message without my signature was a fake; it also described how to obtain my PGP key. The warning informed the other participants that, not only should they look for the signature, but they should also verify it to ensure that no one else had altered the message and that no one attempted to submit a forged message after copying my signature from another, authentic message that I had signed.

This situation illustrates the use of digital signatures to verify both the authenticity and integrity of a message.

Generating and Verifying a Signature

Take a large file of many bytes. Subdivide the file into smaller pieces, each the same size. The last piece is padded with additional bytes to make it the same length as the other pieces. Then, treating the pieces as if they were large numbers (see the Single-Key Encryption discussion under my Key Encryption), add the pieces together. This is a very simple form of hashing. The result is a hashed digest.

PGP uses a much more elegant method of hashing to produce a digest. The digest is then encrypted with the user's private key, which is also the signature key. (Actually, this is true only for an RSA key. For a DSS/DH key, the smaller DSS part is the signature key; the larger DH part is the encryption key. The DSS and DH parts combine to make the private key.) Note that this is the reverse of encrypting a file, where the recipient's public key is used. Additional data are appended, including the date and time and the key ID. The result is a digital signature. While this description is in terms of a complete file, a portion of a file can be hashed for the signature. For example, when a user ID in a public key is signed, only that portion of the key is hashed.

Someone else can then verify a signature against its file. In this case, PGP again hashes the file but without encrypting the digest. Instead, PGP decrypts the digest in the signature using the public key corresponding to the private signature key. Finally, PGP compares the newly generated digest against the decrypted digest. If they are the same, the verification is successful. Otherwise, either the file was altered, the signature was altered, or the wrong signature key was identified.

Because the slightest alteration of the original file after it was signed will result in a changed digest when PGP attempts to verify a signature, that alteration will cause the verification to fail. Thus, a digital signature can be used to verify the integrity of a file — verify that no one altered the file after it was signed. In this case, a digital signature is actually better than a handwritten signature on a document.

Signing Messages and Files

In addition to verifying integrity, a digital signature also supports verification of authenticity. That is, someone who receives a signed message or a file and detached signature can verify that it indeed came from me. This requires, however, not merely my public key for checking the signature. It also requires that the recipient knows that I indeed own the key. This is part of the Web of Trust.

Some will add a third characteristic to integrity and authenticity: non-repudiation. This means that someone who signs a message or file cannot later deny it. I am not so sure about this. After all, it is too easy to claim that someone else obtained a copy of both my private key and passphrase. I have a responsibility to revoke my key as soon as I discover it was compromised, but I can do that merely to repudiate my signature even if no compromise actually occurred. On the other hand, I might still be accountable for the use of my digital signature since I would be expected to take reasonable care to prevent compromising my private key and passphrase. From a legal standpoint, the issue of repudiating a digital signature is too new to make any conclusions; there have been few (if any) court decisions. See Simone van der Hof's Digital Signature Law Survey, which discusses statutes regarding the legality of digital signatures.

Alteration of Message Blocks

Note that, when creating an attached signature, the related message block is first "standardized" by wrapping the lines not to exceed a user-set length, breaking them at "white space" (e.g., blank (hex 20), tab (hex 09)) . This length should be less than the wrapping length of the user's E-mail or newsreader applications so that those applications do not subsequently rewrap the lines. (One of the most frequent causes of invalid signatures is the later alteration to the message block caused when it is rewrapped after the complete signed block has been created. This alteration violates integrity.)

If the message signature is added before or during composition, digitally signing the message with PGP changes the dash-dash-space line to dash-space-dash-dash (per the first two bullets above). This prevents subsequent automatic detection of the message signature for removal during a reply. The modifications described here are in accord with a standard (RFC 2440: OpenPGP Message Format) and thus have precedence over the convention. Note that a digitally signed message is generally altered when quoted in a reply, invalidating the digital signature.

Signing Web Pages

This can be problematical because the transfer of an ASCII file to a Web host and the later downloading of that file to a Web browser can each alter the file, especially if the original platform where the file was generated differs from the platform where it is browsed (e.g.: Mac to PC, PC to UNIX). Using a Web browser to download a Web page can also cause various alterations. Having experimented with Netscape, Internet Explorer, and Mozilla browsers, I must conclude that there is no one acceptable method to sign a Web page or its contents if that page is accessed from a Web server via a browser.

The only assured method of providing a verifiable signature for a Web page is to sign a copy of the HTML file and then send that copy and the detached signature file via E-mail.

The California Regulation

California's Government Code §16.5 provides for digital signatures on documents, forms, and reports filed by local governments with state agencies. The requirements of this section are indeed met by PGP. I quote part of the section below, with my comments in square brackets and with bold added for emphasis.

16.5. (a) In any written communication with a public entity, as defined in Section 811.2, in which a signature is required or used, any party to the communication may affix a signature by use of a digital signature that complies with the requirements of this section. The use of a digital signature shall have the same force and effect as the use of a manual signature if and only if it embodies all of the following attributes:

It is unique to the person using it.
[It is highly unlikely — probabilistically impossible — for two separately generated private keys to be the same. That is, private keys are indeed unique.]
It is capable of verification.
[This is the issue of authenticity. After proving that the asserted owner of a PGP key is indeed who he says, he then provides the fingerprint, key type, and key size. Those items are sufficient to prove that he does indeed own the key because two different keys cannot have all three items the same.]
It is under the sole control of the person using it.
[This is one of the best arguments against key escrow, under which a government agency or third party is given a copy of both the private key and passphrase of a PGP user. By surrendering control of these, the PGP user fails to meet this requirement for an authentic digital signature.]
It is linked to data in such a manner that if the data are changed, the digital signature is invalidated.
[This is the issue of integrity, discussed above.]
It conforms to regulations adopted by the Secretary of State.

Time Stamping

Since one of the items embedded in a digital signature is the date and time the signature was generated, some might think a signature could be used to prove when a file or message was generated. Wrong! It is too easy to adjust the clock on a computer to give a fraudulent date and time.

However, there are time-stamping services that will sign files and messages and return the resulting signatures. While these too could contrive incorrect dates and times, their operations are very easily tested — without them even being aware that a test is being made. They also retain and publish extensive logs of the signatures they generate.

I used Matthew Richardson's PGP Digital Timestamping Service (also known as Stamper) to obtain a provable time stamp for a Word file in which I describe a potential new line of business for my employer. Since this line of business would be completely different from any project on which I have ever worked, I did not know the person to whom I submitted the proposal. Rather than send the lengthy Word file to Stamper, I digitally signed it and then sent my signature to Stamper. Stamper's signature establishes the truth of the date and time within my own signature. In this manner, I can prove priority if anyone else claims to have created my proposal. (To protect my claim of priority, I held the Word file for about two weeks after I received the time stamp before sending it to the "new business" organization within my company.)

Signing PGP Keys

Actually, the title of this section is a misnomer. Keys as a whole are not signed. The user IDs within a key are signed. While most keys seem to have only one user ID, several keys on my public keyring have two or more IDs. This allows the owner to use the same key for multiple E-mail accounts.

Self-Signing

Self-signing occurs when the owner of a key uses his private key to sign his public key. Since PGP 5.0, each user ID is automatically self-signed as it is added to the key (including the first ID as the key is generated). However, PGP 2.6.x requires manual self-signing.

Self-signing a key establishes some authenticity for the key, at least for the user IDs. The user ID of the signature must match the user ID of the key. (Where there are multiple user IDs, the ID of the signature must match the primary ID of the key.) Also, the key ID of the signature matches the key ID of the key. This verifies that whoever placed a user ID on a public key also possesses the private key and passphrase. Of course, this does not verify that the owner of the key is really who she says she is. That is done by the signatures of others on the public key (below).

The importance of self-signing is detailed by Walter Soldierer in his Why should I sign my own public key?. The Key Validity Vulnerability illustrates a risk from having a key with a user ID that is not self-signed. As a rule, I never leave someone else's key on my public keyring with an unsigned user ID. With multiple user IDs, I delete any that is not self-signed; I delete the entire key if there is no self-signature at all.

Signing Someone Else's Key

Just as a sender's signature on an E-mail message allows the recipient to verify the integrity and authenticity of the message, non-owner signatures on a public key allows others to establish the validity and trust of the key.

For keys owned by businesses, a certificate authority (CA) is often used. Since established CAs are generally recognized as trusted, the signature of a CA on a key means the key is valid. However, a CA charges a fee for its signature; and the signature often has an expiration date beyond which the fee must be paid again for a new signature. Thus, individuals rarely use a CA. Instead, individual users of PGP sign each other's keys.

*** Begin Right Sidebar ***

Key Types and Signing

Although quite old, PGP 2.6 is still in common use for various reasons. That version of PGP, however, can generate and process only RSA v.3 keys. Newer versions of PGP can process both RSA v.3 and DH/DSS keys. The newest versions can also process RSA v.4 keys.

There is no problem if a DH/DSS key is signed by an RSA v.3 key. The versions of PGP that can process DH/DSS keys can easily handle keys with mixed signatures. There is also no problem if an RSA v.4 key is signed by a DH/DSS key. All versions of PGP that can process RSA v.4 keys can also process DH/DSS keys (and RSA v.3 keys, too), including keys with mixed signatures.

There is a problem, however, if an RSA v.3 key is signed by a DH/DSS or RSA v.4 key. The result can no longer be processed by PGP 2.6, which then treats the key as corrupted.

Do not sign an RSA v.3 key — also called an RSA legacy key — except with another RSA v.3 key.

*** End Right Sidebar ***

Two valid and trusted keys from others cause an unsigned key from still another person to be flagged as valid. This form of indirect validity is part of the Web of Trust. For details about the Web of Trust, see An Introduction to Cryptography.

The above example assumes that any key that I sign as valid is also trusted. With PGP 2.6.x, you mark someone else's key as both valid and trusted when you sign that key. Starting with PGP 5.0, a valid (signed) key is separately marked as untrusted, partially trusted, or trusted. The trust property applies only on your own keyring and does not appear in a key when you export it to someone else or to a key server. (As in PGP 2.6.x, an unsigned — not valid — key is always untrusted in all versions of PGP.)

While occasions arise where signatures are exchanged one at a time, this can be tedious and generally limits you to collecting signatures only from individuals you know. Instead, key signing parties are conducted. These are not really social events. Instead, these are brief meetings where a group of individuals — some of them strangers — collectively identify themselves and their keys.

PGP: Digital Signatures

Copyright © 1998-2001, 2003, 2005, 2022 by David E. Ross