If a private key is believed to be compromised, how can the owner indicate what new public key to trust?

Question

Abstractly I'm thinking of a situation where there's an authority that houses public keys for users. Say a user goes about using their private key to sign messages but one day finds that their private key has been compromised. Assuming the cause of the original compromise has been fixed (to prevent a second compromise), how can the user publicly indicate not only "Do not use my previous public key" but also "This is my new public key and it can be trusted"?

If the user wasn't compromised then they could publish a signed message saying "Use this new public key" but this is no longer possible because there's no confidence in who signed the message once it's compromised. An Eve could create a new public/private pair and try to coerce people that this new pair is to be trusted, just like the user is trying to do with their new key.

I imagine there could be some sort of Certificate Revocation List but for public keys that a user could add their public key to once they believe they've been compromised. How then could a user re-establish trust with a new key?

Answer 1

I think if you continue down this line of thinking you will end up inventing Certificate Authorities.

Yes, any key should be able to revoke itself (ie sign a message saying "Don't trust any future message from this key"). Whether this goes onto a revocation list or some other mechanism depends on how the system is designed.

As for telling the world which key to trust next, well in a web-of-trust system like PGP there's really no way to do that - your key is gone. You need to start over with collecting signatures on a new key. In a PKI system with a CA you can contact the people who issued your certificate, prove your identity (over the phone or in person or whatever your policy requires) and then get them to issue you a new certificate.

---

Off the top of my head I suppose you could always keep two keys -- the active one that you use and a backup, and have the current key sign a message saying "My backup key is XXXX". Given that your active key is compromised at some point in the future and you had a way to cryptographically prove that the cross-validation happened prior to the compromise (which also will require some foresight), then people could safely extend trust from the old key to the new key. ... I wonder if this is done is practice, I'm mostly an expert in Certificate Authorities where you can just get the CA to re-issue.

Answer 2

Good question! (For TLDR, skip to point #9 and the paragraph after that)

So the story goes like this:  

Alice decides to use key pairs, PRIV1 and PUB1, so that people know that her documents have not been tampered with...

1. Alice signs a document with her private key PRIV1.
2. Bob downloads her document, along with the public key (say, shared via email), PUB1.
3. Bob uses the public key to ensure that the document is valid.

 

Alice's private key is compromised...

4. Alice creates a new key pair, PRIV2 and PUB2, but forgets to share PUB2 with her users.
5. Bob downloads a second document from Alice's website.
6. Bob tries to use the old public key PUB1 to validate the file. It fails.
7. Bob emails Alice to let her know.
8. Alice decides to publish her new public key PUB2 on her website for all to see, so that she doesn't need to keep telling lic keyher users about her new public key.
9. Alice smartly decides to enable https on her website so that a hacker can't change the public key using a man-in-the-middle attack.

So, in the end, enabling https with a valid (i.e., not CRL'd) certificate enables a sure-fire way to ensure that Alice's published public key is correct at any given point in time.