Publick Keys revocation

[paulobmarcos]

At the time of this issue, the DID spec mentions that:

If a public key does not exist in the DID Document, it MUST be assumed the key has been revoked or is invalid. The DID Document MAY contain revoked keys. A DID Document that contains a revoked key MUST also contain or refer to the revocation information for the key (e.g., a revocation list). Each DID Method specification is expected to detail how revocation is performed and tracked.

A discussion on how we can further develop the IPID specification to establish how the revocation is performed and tracked would be worthwhile.

[jonnycrunch]

Cool, let's chat.

[aschmahmann]

Some thoughts on this (derived largely from https://github.com/ipfs-shipyard/pm-idm/issues/2#issuecomment-451032749).

There are two types of functions that we tend to worry about here:

1. Revocation: How do I know that the keys that I'm using are out of date?
2. Rotation: What is the new key and how do I know it actually belongs to the correct party?

We also need to take into account the threat model and timing around revocation/rotation. For example:

1. Did we revoke our key long before the compromise occurred? (e.g. RSA-1024 no longer deemed secure)
2. Did we revoke the key after the compromise occurred? (e.g. laptop is stolen)

Below are some thoughts on how to solve this using a blockchain/global consensus system (which while not in the IPID spirit, is what most of the DID space is using) and an IPNS/eventual consistency system. I will use as a short-hand blockchain = global consensus system and IPNS = eventual consistency system.

Blockchain

Before Key Compromise

• Revocation: Advertise a message to the world saying "This key is compromised"
• Rotation: Advertise a message to the world saying "The new key is K"

After Key Compromise

• Revocation: If the system allows for key rotation then we're generally sad 😢 because the adversary rotated your key before you had a chance to revoke and now there's no way to signal the revocation.
  • However, if there's no key rotation scheme then just advertise the same "this key is compromised" message as above.
• Rotation: Generally no, because the key may have already been rotated by the adversary.
  • However, any non-consensus solution could potentially work in a consensus environment since consensus systems can theoretically have a superset of the functionality of non-consensus systems (e.g. by not choosing not to care about the consensus).

IPNS

Eventually consistent systems' lack of total global order makes using the breakdown of "before" vs "after" generally difficult, since depending on the state of the network "after" can always look like "before".

Revocation

• Change IPNS validation to reason about revocation
  • Implicit Revoke: Ensure that two logically simultaneous writes result in an error (since IPNS currently assumes only one writer is active)
  • E.G. There is an update key U that users can publish the next version of the DID to IPNS[U] = DID'. If there exists a record IPNS[U] then the current record is out of date. If there is exactly one update published then the update can be used, however if there is more than one update then flag that the key has been compromised => revocation.
  • Having a multi-writer IPNS would allow the application layer to worry about the implicit revoke instead of the IPNS layer
  • Explicit Revoke: An IPNS-record type with a flag that says "Revoke me", just as in the blockchain case
  • Would also need validation to assert that no updates can happen after a revocation and that for logically simultaneous updates revoke always wins

The security tradeoff here with a blockchain is related to availability, if an attacker can eclipse or distort a users' view of IPNS to see only one update instead of two then they are successful. Given that this is a forking attack some of the standard solutions to mitigate forking attacks can be employed (e.g. Keybase uses user tracking of keys, but any sort of embedding DIDs into other data to increase the amount of the network that needs to be forked is useful)

Rotation

As with blockchains this is very difficult to figure out after the key has been compromised. Additionally, since before and after are harder to tell apart here, we have difficulty even before the key has been compromised.

However, there are some options for key rotation that are viable and exist outside the IPNS/blockchain system.

1. Rediscover the key. IPNS keys are long strings of characters that are difficult to remember, the user probably found them somehow. Maybe it was via a distributed social network, maybe a blog post, a centralized lookup service, utilizing search + verifiable credentials, or any other mechanism. Redo whatever you needed to do the first time.
2. A single trusted authority. Maybe the it's the government, maybe it's my super secret key that I promise won't get compromised (I've seen this one proposed in various systems)
3. Some social based identifier recovery. Like the single trusted authority a user pre-designates a group of trustees that are the only ones who can do key rotation and then the user asks them to do the rotation. This could be via some group signature or Shamir secret sharing scheme to allow m of n users/organizations that can collectively work to restore the user's identity

Rotation => Revocation, but that's not the whole story

It is worth noting that if we wanted to, we could use our solution to rotation to help with revocation. For example, if users were willing to use a single trusted authority for key rotation it could also be used for discovering/dealing with revocation. However, these schemes are generally not as easy to work with (or secure) as the revocation schemes so separating revocation from rotation is likely a good way to go.