Verifying cryptographically signed files when the key has been revoked

Question

This is mostly a question out of idle curiousity. If I use my private key to sign a file today, forming a signature, and distribute that signature with the document to someone they can then use my public key (which they've obtained out-of-band in a secure manner) and the signature and verify the document remains unaltered. So far so good.

But if the verification step only happens some time later, and in the mean time I revoke my key, how should this be handled?

On the one hand, the file was signed in good faith at a particular time and if the file is somehow timestamped and the timestamp is before the date of revocation and the revocation is not because of a compromised key, then the revocation shouldn't automatically mean distrust of the signature.

On the other hand, assuming the key was revoked because it was compromised, someone else could have used my compromised private key to sign a file with a false timestamp within the placing in within the active period of the key.

As far as I understand, the longer a key stays 'active' the less secure it gets, because the more time there has been to brute force it and the more it has signed/encrypted, the more information is available to use in various attacks. Now I understand that theoretically brute forcing a key should take longer than it will take for the universe to suffer heat death, but it's always possible that short cuts may be found in the future. So I imagine one would want to revoke keys regularly.

Is there a way to tell the difference between the two situations described above?

Is there way to tell the differences between a revocation because of cycling and a revocation because of compromise?

It seems (from this question) that regular key revocation is not longer best practice, but I'm not 100% sure I'm reading that right. Instead Trust-on-first-use and "pinning" are used in practice today. Also the answers and comments in said question make it clear that there's no mechanism to expire a key. Having done some brief reading on TOFU and pinning though, and it doesn't seem to influence my question.

To prevent this being closed with an "XY" complaint, let me be more explicit. In the situation of a compromised key mentioned above, I can't think of of a way to reliably verify the document even though it was signed by an at-the-time uncompromised key. This could very easily be a gap in my knowledge, and I want to know if there are techniques to still do this reliably?

Answer 1

Is there way to tell the differences between a revocation because of cycling and a revocation because of compromise?

Certificates.
Certificates usually include validility times, during which the associated public key is valid for use. Most certificates are issued for 1 up to 3 years and afterwards you need to cycle the certificate (and also maybe the associated key). With most better TOFU and pinning schemes you will still see and check the certificate and not solely trust on the pinned key, to ensure that the key is actually still valid and not expired nor revoked (which is handled via OCSP and CRLs).

But if the verification step only happens some time later, and in the mean time I revoke my key, how should this be handled?

This is actually a tricky problem, that requires some (2) changes to the way documents and data is signed and verified.

First, we need to change the OCSP responders. Right now, you usually only get "good", "unknown", "revoked" or "suspended" from the CA as an answer. This is clearly not enough, as you need to know when the certificate was revoked or suspended. Given this information you can actually check if the signature was issued before the key was compromised. Of course this still leaves the issue that anybody could just use a pre-revokation date for signing data.

To fix this issue, you need some more reliable way of time-stamping data than by letting the time stamp be created by the signer. You need to outsoure the timestamp, by either letting a trusted service sign a combination of the hash and the current time, by cleverly chaining the hashes like is done with Certificate Transparency or by insert an entry into the block chain.

As soon as you have a (valid-looking) signature with a trusted time stamp before the revokation date, you can rest assured that the signature is valid, but note that your signature should be included by the hash sent to the time stamping service to ensure nobody ripped it off and replaced it.

The alternative possible solution is to get rid off this whole revokation system and just (exclusively) use short-lived certificates where you can be sure that if it was revoked, that all the data in this short time frame could have been signed maliciously.

Answer 2

Assuming that there is no time delay between compromising the private key and revoking the public key and that there is a way to reliably find out when the key has been revoked, this could work if you time-stamp the signature, not the file. This way, it can be shown that the signature was made before you lost your private key.

However, typical key revocation protocols do not cater for this application. The revocation database would need a time stamp for the receipt of your revocation and it would have to sign a declaration from you that states up to what time signatures can be trusted, e.g. the earliest time your system may have been intruded.