Key management draft

In Condensation, keys are managed through actor groups.

As opposed to systems like PGP, an entity (user, service, ...) owns a set of key pairs, and not just a single key pair. Each key pair constitues an actor, and actors belonging to the same entity form an actor group.

Within such a group, keys (actors) can be active, idle (obsolete), or revoked:

All active keys are equal – there is no master key or leader actor.

An entity manages its keys on its own (distributed), and does not rely on a key server or any other centralized key management infrastructure.

Key pairs are generated on the device on which they are used. Private keys are stored in a safe place on the device, and may be protected with a fingerprint or a PIN code. They never leave the device, and are not backed up.

Groups may evolve over time. To add a device to its actor group, an entity generates a new key pair on the new device, and adds it to the actor group. To remove a device, the entity marks the corresponding key as idle or revoked, and destroys it.

Every group member publishes the status of all keys on its public card. Two actors are in the same group if they both claim to be together. Every connected component of the resulting graph is an actor group:

Knowing any actor is enough to discover its group.

Key rotation and forward secrecy

All keys of an actor group are ephemeral. A device may rotate its key by generating a new key pair, and destroying the old one. The old key should then be marked idle:

Through regular key rotation, a certain degree of forward secrecy can be achieved. If a key is compromised,

• only messages sent to that key,
• and private data stored for that key

can be retrieved. However, since private data often changes slowly, key rotation primarily offers forward secrecy for messages.

Key rotation is optional. If used, all actors of a group should rotate their keys at roughly the same interval.

Key loss

If a private key inadvertently got destroyed (e.g. because the device got destroyed), the key can simply be marked idle. This is the same as removing an actor from a group.

Backup actor

If the last active key is lost or destroyed, the group becomes irrecoverable, and its private data may be lost.

To avoid that, a user may set up a backup actor. Such an actor is registered as an active member of the group, and therefore receives all data updates. It may run on a safe device in a safe place, and only wake up occasionally to merge data updates.

The backup actor may be operated by a trusted service company.

Losing track of an actor group

Actor groups need to be followed to keep track of changes. If an actor group is not followed for an extended amount of time, one may lose track of it.

To illustrate that, consider the following evolution of a group:

At time A, the group has 3 active accounts. Over the course of time, the group evolves: new actors are added, and old actors are marked idle. At time E some idle actors become so old that they are completely removed. Their public key and card are removed from the store. At time F, all actors active at A have vanished.

Somebody regularly following the group will first discover A, then B, and so on, until eventually discovering F.

However, somebody knowing the group at time A, and not following up would lose track of the group at time F.

To alleviate this, idle accounts are typically stored for several years. An idle account only needs a public box with an envelope, a public card, and a public key, all of which amounts to less than 20 KiB of (rarely accessed) storage space.

Key theft

Key theft entails several issues intrinsic to public-key encryption. To alleviate these problems

• the stolen key should immediately be revoked by all active group members,
• and messaging store(s) of the exposed actor should be erased, if possible.

The latter requires that the store is under control of the user.

Impersonation and data breach

An attacker in possession of an active private key is a valid member of the group, and can thus read and modify the group's private data, and send messages on behalf of the group.

Once the key is revoked, the attacker is left with the last version of the private data before key revokation. Although it can still modify this data locally, other group members won't merge these changes any more.

Key revokation thus reestablishes group integrity from the point of view of all remaining group members.

Revokation symmetry and group splitting

After revokation, an outside observer will see the group split into two, and may only guess which part belongs to the actual entity, and which part belongs to the attacker.

To illustrate this, consider a group of two actors, of which one (white) gets exposed. An outside observer will see one of the following:

• A: No key has been revoked yet.
• B: The entity revoked the stolen key.
• C: The attacker revoked the remaining key.
• D: Both revoked each other.

In cases B, C, and D, the group splits into two parts, but because of the symmetry, an outsider cannot know which of the two keys got exposed. The entity needs to be authenticated again.

Assuming that an attacker may steal multiple keys at the same time, the problem remains symmetric for larger groups.

Deleting the messaging account (on the store) of the stolen actor solves the problem. This, however, requires the user to have a separate access (with separate credentials) to the store, and is therefore external to key management.

Comparison with centralized key management

The group splitting problem is intrinsic to all key management schemes — whether central or distributed — and constitues a theoretical limit of key management.

What changes is the number of exposed entities per key theft:

An application may obviously use a central key server on top of actor groups.

Suicide

When anticipating a problem (e.g. after too many wrong PIN code attempts, through remote wipe), an actor may commit suicide by destroying its private key. This immediately renders access the data impossible.

To recover, the device joins the actor group with a new key pair.

Scalability

Actor groups usually consist of 2 to 10 active actors. Users rarely own more devices, which naturally limits the number of active actors.

Discovering a group requires downloading the public cards of active actors only, and therefore has no scalability issues. To thwart malicious users intentionally creating large groups, the discovery algorithm may limit the number of accepted active accounts (e.g. 32).

Over time, an actor group may however accumulate hundreds of idle accounts, especially if keys are rotated regularly. Idle accounts scale fairly well:

• An idle actor only needs a public box with about 20 KiB of storage (public key, public card, and envelope).
• Cards of idle actors are not downloaded during discovery, unless they are still believed to be active.

Revoked actors do not need any storage space at all.

There is some information about data loss on the security page, which should probably be merged here.