Ameliorating the effects of malware in a web of trust

Let's say it's the future, and everyone has at least one public key and is a full participant in a global web of trust. Wonderful, until EvilWorm9000 hijacks your mail client and starts spamming everyone within 4 degrees of separation. How does the ideal network respond? In this post I provide a possible approach (temporary key tainting), but the main goal here is to stimulate a conversation.

There are two types of attack here: Confused deputy, and leakage of private key. I'll address them separately.

Leakage of private key

This is the simpler case, so I'll address is first. If the malware sends your private key to Nigeria, you're hosed. Better distribute that revocation certificate pronto. You might not have noticed yet, or perhaps you are otherwise incapable of revoking that key, so there had better be a way for other people to initiate this process. Perhaps there is a mechanism in place by which you have sent your friends the revocation certificate in such a way that only a quorum of them can decrypt it to broadcast. If your friends acted fast enough, they could revoke the key on your behalf before too much damage was done.

But perhaps the key isn't stolen after all. It could be a matter of a...

Confused deputy

If the malware has, for instance, injected itself into your email client, then it does not have direct access to your private key but can nevertheless send email signed as you (and read mail encrypted to you.) The mail program is deputized to use your key on your behalf, so this is more or less an instance of the confused deputy problem. Under these circumstances, key revocation is overkill. (You'd need to abandon the old key even though it had not been compromised.) Maybe all you need is a way to temporarily prevent your key from being trusted.

I'm imagining a "tainting" system whereby (again) a quorum of friends would be entrusted the ability to issue a message marking your public key as possibly compromised. Anyone receiving this message would treat the key as revoked: No encrypting to the key, no trusting new signatures from it. Without further action, this taint would hold indefinitely. Once you'd cleaned up your system, you could ask your friends to sign an untainting message that repeals the original. Any signatures generated in the duration would still be regarded as untrusted, but new signatures would be handled normally.


I'll leave you with a few questions:

  • Is it important for there to be a way for the focal individual to untaint a key themselves in the case of shenanigans/rampant malware/social drama?
  • Should tainting be a global property or n-degrees local to the focal key?
  • If used, should tainting be an integral part of any web of trust mechanism, or is it meaningful to build it as an overlay? (I think the former, since the latter relies on bug-prone opt-in programming.)
  • Should a taint automatically become permanent if not repealed within some duration of time?

Responses: 7 so far

  1. _miw says:

    It is not to possible to allow the original key owner to 'untaint' a key, once marked as compromised or semi-compromised it can never be trusted to unrevoke itself. It would be trivial for an attacker to unrevoke a key if all one needed was the private component to reactivate it.

    In the event social drama was preventing legitimate activation of a semi-compromised key, the web of trust could be considered corrupt at the key owners node -- if there is sufficient distrust to prevent the reactivation of a key it makes no sense to reactivate that node.
    New key generating routines should be followed and web links reestablished. This is almost a self healing property of the wot.

    a crypto system should never 'activate' keys on time based triggers, activation should always require either manual one time triggers or human interaction. Leave semi-revoked until successive key is generated. On gen of new key perm mark the old one as compromised (perma).

  2. Tim McCormack says:

    Oh, I'm not suggesting that the focal keypair could be used to untaint itself -- the owner would have to convince their friends out-of-band to do the untainting, again as a quorum.

  3. _miw says:

    Isn't that the issue tho?

    When quorum cannot be reached due to social shenanigans (such friends refusing to sign the Unrevoke contract), and the standard semi-compromised key unrecoverable process cannot be followed?

    In an age of connectedness one, key redistribution isn't so difficult. Does the semi-compromised state offer any benefit over canceling and regenerating a new key?

  4. Tim McCormack says:

    My gut feeling is that there would be a lower standard of proof (and therefore less work involved) for convincing your friends to untaint a key vs. providing your new public key for signing.

    You also wouldn't have to change your key *everywhere*, you'd be able to authenticate with services again without reestablishing identity, etc.

  5. dittendatt says:

    One could also imagine an override key, not stored on the computer, with permission to untaint the lesser key.

  6. Tim McCormack says:

    Hunter Heinlen suggested an amelioration strategy of creating and signing an alternate personal key, then keeping it in cold storage until needed. When your first key is compromised, you'd at least have a second key that your friends trust.

  7. _miw says:

    I don't know if this actually solves the problem -- you create a redundant 'override' key, then have to ensure that its trusted by peers (so you would say, get it signed when you have your primary public key signed), then ensure that it is saved in such a way that it is offline and can be made online in the event of compromise. Sounds like a manual process that is unlikely to be followed by a majority of keyholders.

    Its turtles -- do you have a 3rd recovery key in the event that is compromised?
    How do you ensure that people don't get lazy and forget to move that key offline?
    In the event of machine compromise, which most likely is the cause of key compromise, chances are all online keys would be tainted.

    I think that generating a redundant override key is unnecessary and it moves the model away from a WoT.

    You need to harness the trust model that is implicit in the WoT, having infinite additional keys that allow their descendant keys to be revoked/activated adds overhead, that may not be followed realistically by the keyholders.

    I like the idea that some ratio of key peers (that have signed and trusted the key) have the ability to globally revoke/reactivate a peer key. This means that only a single key need be generated and signed at a time, with a mechanism for de/reactivation.