Update 04.08.2018: clarified behavior on timestamping certificate revocation

Hello again! Today I would like to discuss about digital signatures and signature usage questions.

A very short introduction to digital signatures

As you know the signature guarantees that the electronic document wasn't changed after signing process. This is a useful feature for sensitive data that may be changed during transfer over network. For example, Internet. There is one well-known attack named Man In The Middle (MITM). In MITM, malicious user intercepts document change some data and transfer to the original recipient. If the document is originally signed (by sender) the recipient will attempt to validate document signature and will see that the document was changed during data transmission. This would invalidate the document.

In real world digital signatures are used very often and use asymmetric encryption/decryption processes.

What is the asymmetric encryption? This encryption type is based on two cryptographic keys — public (this key is available to any user without restriction) and private or a secret (held by the key owner. No one except the owner should know this key) key. These keys are mathematically related so if something is encrypted by one (public or private) key then encrypted string can be decrypted by corresponding second key (private or public). These mathematically related keys usually referred to key pair. In other words, anything that is encrypted by a public key can be decrypted by corresponding private (or secret) key only and vice versa.

Simple digital signature

How the signing process work?

1. Sender produces a document and calculates a cryptgraphic hash over it by using one of the one-way hashing algorithm. Hash is something like a checksum and is unique for each document. When you change a document, the document hash is changed too. There are a lot of hashing algorithms like SHA1, SHA2 (family), MD5 and so on. By using these algorithms you can get a checksum, but cannot reconstruct the original document from this checksum (hash).
2. When the hash is calculated the sender encrypts it by using its own private key. Resulted encrypted string is the desired digital signature that is attached to a document.
3. When recipient receives signed document, they want to check whether the document was changed during file transfer or not. Recipient detaches signature from a document and takes signer public (which is publically available) key to decrypt encrypted string and extracts original document hash.
4. If both hashes match, the signature is valid and the document wasn't changed during transmit. Otherwise, the document was changed and we cannot trust it. So, reject the document.

As you see original hash is encrypted by user's private key. Encrypted string (or sequence) can be decrypted by user's public key. Since the public key may be available to any other user (and as the result can be decrypted by anyone) this encryption type don't guarantee data confidentiality, only integrity!

After that the recipient calculate a hash for a document by using the same hashing algorithm as was used during signing process. If the document is not changed both hashes (calculated by a recipient and extracted from the signature) MUST match and the document is considered as valid. If they don't match then the document was changed by unauthorized person and the document considered as untrusted.

This is what digital signatures does! And here is a simple signature structure:

Pretty simple (actually there is nothing complex).

Signature trust model

Windows introduces 4 digital signature trust levels:

1. Untrusted. The signature was created by an explicitly distrusted publisher. The signing certificate often are revoked when certificate holder loose his own signing private key or when it is stolen. In order to avoid lost certificate from usage (so no one will be able to use stolen certificate to impersonate legitimate user and create malicious signatures) the certificate MUST be revoked and/or placed to Untrusted Certificates container in Windows local certificate store.
2. Unknown publisher. The identity is not known and the signature is invalid. Because there is no verified signature, an identity cannot be determined. The signing certificate is not revoked or explicitly untrusted but is issued by untrusted Certification Authority (CA).
3. Known publisher. The identity is known and the signature is valid. A valid Authenticode signature provides an identity. The signing certificate is a valid certificate issued by trusted CA.
4. Trusted publisher. The signature is valid and was created by an explicitly trusted publisher. Signing certificates for this trust level must be issued by any trusted CA and the certificate must be placed in a Trusted Publishers local certificate store.

For what reason there are so many trust levels? Perhaps it should be simply Trusted/Untrusted? Yes, for certain scenarios this is enough, but not always. Applications use various trust levels depending on internal requirement. As there are many trusted CAs they issue a lot of signing certificates to various publishers. However it is common when we don't want to trust any document signed by these publishers. 4-level trust model allow us to trust only certain publishers and no more.

Signature lifecycle and timestamping

Suppose the following scenario. You have a signing certificate and you sign a lot of documents. Once, the certificate is expired, you receive a new one and continue document signing.

In normal case (like with SSL and other encryption certificates) once the certificate is expired, all signed data will be invalidated. You cannot connect to web server with expired SSL. However, you need to retain signatures valid even if the signing certificate is expired. One idea is to allow successful signing certificate (and signature) validation even after certificate expiration. However, this solution wouldn't be wise, because we would lost control over illegal certificate usage -- signing operations after signing certificate expiration. In addition, if signing key was compromised and it is confirmed that they was valid prior to specified date/time, we won't be able to tell whether the signature was generated prior or after compromise date.

To address this issue an additional service was introduced -- timestamping. According to wikipedia:

Trusted timestamping is the process of securely keeping track of the creation and modification time of a document. Security here means that no one – not even the owner of the document – should be able to change it once it has been recorded provided that the timestamper's integrity is never compromised.

Usually timestamping services are provided by a trusted 3rd party authorities. They have a special device that synchronizes current time with world time sources and have signing certificates for timestamp signing. Signer calculates document hash (usually during signing process) and sends it to a timestamp server. Server append current date and time to a received hash and sign resulting data with its own timestamping certificate. Resulting message is called a signed timestamp. After that server return timestamp back to signer and signer attaches the timestamp to a document signature.

And how the timestamp is attached to a signature:

As you see the timestamp is not a part of a signed document hash (though this is a part of digital signature) so you can update only timestamp. But if you re-sign the document the timestamp will be updated (or removed if during re-signing process you decided to not use timestamps). Since both encrypted hash and timestamp contain document hash it is not possible to detach the timestamp and attach it to a different document to falsify actual signing time.

Example scenarios

Next two sections (where each of them contains two subsections) will illustrate the signature validation outcome in different situations.

Example scenario - standard certificate lifecycle

Suppose the following scenario: you have a document signing certificate with validity: 1 Jan 2015 - 31 Dec 2015. The following two sections will illustrate what will happen with the signature at various time points. First section assumes that you made signatures without timestamping and second scenario assumes that you made timestamped signatures.

Standard certificate lifecycle - no timestamped signature

The rule here is pretty simple: signatures can be validated only in a signing certificate's validity period time frame. If you attempt to validate signature (non-tampered) in a time frame between 1 Jan 2015 and 31 Dec 2015, validation will succeed. Any validation attempts beyond certificate's vlidity will fail. This is because we do not have any information about when signatures were created.

The bad news here is that when you receive new signing certificate (as a replacement of expired one), you would have to re-sign all previously signed documents, because they are no longer valid.

Standard certificate lifecycle - timestamped signature

Validation rules here are a bit different. Since we have a trustworthy information about when the particular signature was created (this is achieved by including a signed timestamp in the signature) we can trust signatures created not only in a signing certificate's validity period time frame, but even after signing/timestamping certificate expiration. This is because we certainly know that the signature was made within signing certificate's validity period and nothing was changed.

As the result we can trust signatures if we perform signature validation even after signing certificate expiration. This scenario eliminates the requirement to re-sign all previously signed documents, because signing certificate is expired. Moreover, the signature will be trusted even if all certificates in both chains (signing certificate and timestamping certificate) are expired, including CA certificates. As long as both roots are explicitly trusted (are presented in the Trusted Root CAs container on the machine).

In short, we can trust timestamped signatures that were made with signing certificate's validity period and it doesn't matter when we perform this validation.

Note that we still can't trust signatures created at time frames outside of signing certificate's validity. The signature MUST be created within certificate's validity, otherwise, the signature is untrusted.

Example scenario - revocation

Here we extend previous example by adding an unfortunate case: the signing certificate was stolen/lost and eventually revoked.

You have a document signing certificate with validity: 1 Jan 2015 - 31 Dec 2015. The certificate (and its private key) was lost at 1st August, 2015. You took required actions to immediately revoke the certificate. The following two sections will illustrate what will happen with the signature at various time points. First section assumes that you made signatures without timestamping and second scenario assumes that you made timestamped signatures.

Revoked certificate scenario - no timestamped signature

The rule here is pretty simple. If you attempt to validate signature between 1 Jan 2015 (signing cert's start validity) and 1 Aug 2015 (when the certificate was revoked and placed in CRL) we will trust the signature. However, after 1st August the trust will be ended. Once we found signing certificate in CRL, we will invalidate *all* signatures made by revoked certificates.

This is because we don't have any information about when particular signature was created, as the result we invalidate all signatures. Even if they were made prior to certificate revocation. Remember, that timestamps weren't applied, so this information is not available to us. In order to restore the trust to previously signed documents -- we have to re-sign them with new signing certificate.

Revoked certificate scenario - timestamped signature

In general, if the signature is timestamped, we can trust it if the signature was made within signing certificate's validity period. However, our scenario has a condition: the certificate was revoked. Since revocation date is presented in CRL and signature creation time is presented in the timestamp, we can safely trust all signatures generated between signing cert's start validity (1 Jan 2015) and till revocation date (1 Aug 2015). We can't trust any signatures created after 1st August, because the control over the key is lost.

The unobvious point here is that we can successfully validate signature even after signing certificate expiration (and the cert is actively listed in the CRL), because we know that the signature was made in the period when the key was not compromised.

This leads us to another revocation management best practice:

Some certification authorities (CA) remove expired certificates from their certificate revocation lists (CRL). However, for better security you SHALL NOT remove expired code/document/email/whateverelse signing certificates from CRL until the CA is fully decommissioned. Otherwise, you open a breach in successful signature validation when the signing key was revoked.

Digital signature lifecycle table

This section provides a quick table that shows signature validation status under all above described conditions.

	Simple signature	Timestamped signature
Signing certificate (or certificate chain) is valid and not revoked
Signing certificate (or certificate chain)  is valid and is revoked before signing
Signing certificate (or certificate chain)  is valid and is revoked after signing
Signing certificate (or certificate chain)  is expired after signing
Timestamping certificate (or certificate chain) is revoked before signing	N/A
Timestamping certificate (or certificate chain) is revoked with Key Compromise reason	N/A
Timestamping certificate (or certificate chain) is revoked with any other reason after signing	N/A
Timestamping certificate (or certificate chain) is revoked with any other reason before signing	N/A
Timestamping certificate (or certificate chain) is expired after signing	N/A

as you see there is only one case when simple signature remains valid — while the certificate is time valid and is not revoked. In all other cases the signature will become invalid. But timestamped signature remains considered as a valid even if all certificates in the signing and timestamping chains are expired. Therefore you should timestamp your signatures each time you sign something as it is possible. Some time ago (when I wasn't educated in PKI) I asked a question — "for what purposes Windows is shipped with expired root certificates in the Trusted Root CAs container? They are expired and there are no reasons to trust them!". And the answer was pretty simple — for timestamped digital signature checking purposes. Therefore if you issue signing certificates by your internal CA — don't remove your root CA certificate after CA certificate renewal.