|Title:||Key Reset Specification|
Style note: the author has chosen to use the singular 'they' throughout the document to refer to unspecified users and communications partners in examples. Efforts have been made to ensure the singular/plural context is clear.
p≡p is an an encryption product which automates as much of the key management and trust process as possible. As a result, one of its greatest challenges is that when there are key related issues - e.g. compromise, revocation, or simply needing to use a different default key for a partner - the software must be able to provide both internal and user access to the ability to change these default keys without actually exposing the concept of keys, which goes against p≡p's "Pretty Easy" principle, or the details of trust management.
This document describes the Key Reset protocol, which is implemented primarily in the engine and allows applications to provide simple high level functionality to users needing to perform some of the aforementioned functions while still ensuring that the appropriate low-level changes in keyrings and trust management are handled consistently, and that communication of these changes to active partners (where necessary) happens seamlessly, without explicit action on the part of the user. Additionally, the protocol provides important lower-level internal functionality to other internal protocols (e.g. KeySync).
The following are terms used in the document which may not be familiar to developers new to the system, and are defined upfront for easy reference.
For the individual p≡p user and corresponding address, their own default key is the key they use to sign messages to others, to decrypt messages from communications partners, and to encrypt messages to themselves.
Additionally, however, for every identity that this user communicates with, there is (where available) a default key belonging to the communications partner which is used to encrypt messages to that identity and to verify messages signed by that identity.
A user may have several identities, and each of those identities may have a distinct default key.
These defaults generally stay stable unless a key becomes invalid or unusable. However, there are times when a user or an internal protocol needs to reset these defaults and replace them with new ones. Additionally, when a user begins using a new default key, they may need to communicate this change of desired defaults to communications partners. Or an automated internal protocol may, for example, have a reason to invalidate one or more of a user's own keys.
Within the p≡p environment, there are several circumstances under which we might need to reset the default key that p≡p would ordinarily use as the default key either for the user themselves to sign messages and data, or for a communications partner in order to encrypt it. A user may need to revoke one or more of their own keys due to compromise or accidental creation of a new key. And internally, there are protocols, such as KeySync, which, as part of automated key management, may need to securely force removal and regeneration of default keys across devices.
And finally, p≡p allows users to assign trust (through the exchange of Trustwords) or mistrust to a key associated with an identity, and sometimes desires that these values are reset, either due to error or a change in their own perception of trust. A mechanism needs to be available to reset this information about keys as well.
The largest part of the problem comes in two parts:
Because we want to abstract the idea of keys away from the user, having them only focus on their contacts and the expression of trust with these contacts as applied to the sending and receipt of messages, p≡p must provide a way for apps to create this abstraction without needing to retain information about specific keys, especially since we want to avoid users interacting with the idea of keys at all costs.
Thus, we need a way for the engine to provide this functionality for both the reset of own keys belonging to an own identity as well as such a reset for partner keys belonging to a partner identity which does not require any information about keys from the application or external protocol layer, while still ensuring the the appropriate low-level (keyring and management database) actions can occur appropriately.
We also need to be able to ensure that partners a user who has reset their own key(s) contacts regularly can be notified and informed that they should use the new key (and stop using the old one) corresponding to the specific user address they have been communicating with without the need for the user to inform partners explicitly while still ensuring some verification that this information actually came from the user.
The Key Reset protocol aims to solve this problem of providing an abstraction to the adapter/application layer as well as providing both opportunistic and situation-based automated communication of changes to partners without compromising the trust system and minimising man-in-the-middle attacks. It does this by providing API functions which operate at both the user and identity levels for both own users and partners, using the engine to both map identity information to keys and to do all key manipulation and management database functions, as well as to automate the partner-notification process.
Implementation of this protocol impacts engine development, the adapter team (which must wrap the API functions for applications), and the application layer, where apps must decide where and how they call these functions and build the necessary user abstractions to execute the protocol (e.g. a "Reset User" button in the UI which contextually requests that keys are reset for the current user being displayed).
This document is intended for developers at these three levels.
Early implementations of p≡p lacked an easy means for high-level key revocation of own keys, for partners to stop using a key at the request of the user, and for notification of default key changes through revocation to communications partners. This made it very difficult to clear default key data when desired without forcing applications to keep track of default key information, and partners would continue encrypting messages to the older default key. There was no means for applications to simply tell the engine, "please reset all key data for this identity", or to automatically tell partners they were using a revoked key and to start using a new one.
Key reset provides this functionality, which can be used both by applications and by internal protocols to provide these functions under a variety of circumstances.
This section uses key use cases to create a list of requirements the key reset protocol must fulfill. This is central to designing a solution.
One preexisting requirement, however, that impacts all of the examples is this, and is driven by one of the principles of the system, which is that users should neither need to know or care about the concept of "keys":
A p≡p user decides, for any reason, that they want to replace their current default key for one of their identities[^1]. ([^1]: This is current generally not expressed at the application later for reasons to be explained in section TODO; however, it remains possible from the engine level) The key should not be used by communication partners in the future, and they want to ensure the old key is invalid for future use by communications partners or adversaries.
This creates the following additional requirements in addition to 1. above:
The protocol must provide a mechanism at the cryptographic engine level (i.e. within the keyring) for the revocation of the own default key associated with this identity.
The protocol must provide a mechanism for the generation of a new keypair corresponding to this identity and to assign this key as the identity default.
If the key being replaced was also the user default, the new key generated by 3) must replace the first key in the management database as the user default key.
Communications partners must be informed, at latest at the first reply to a message encrypted to the now-revoked key, of the revocation of the first key and its replacement with the second.
The notification in 5. requires communication of both the revocation in 2 via a revocation certificate (signed by the now-revoked key) and the public part of the new keypair.
The notification in 5. must, at the very least, contain some artifact that requires the private key of the now-revoked key to produce (e.g. a revocation certificate).
The notification in 5. must, at a minimum, be signed with the private key of the new keypair. 1
A p≡p user is forced to unlock and give up their phone at the border[^2]. ([^2]: The "device compromise" use case can happen in other ways, but we want to initially provide the simplest case, where the user recovers the same device after compromise. Dealing with device compromise from another device is handled later). They want to ensure that the keys on that phone are no longer valid for use in order to prevent unauthorised parties from decrypting their future communications or posing as an imposter, sending mails which can be falsely "verified" as them.
This creates the following requirements:
A p≡p user, Alice, has the public key of another p≡p user, Bob. Bob has done a key reset of his own key, but Alice is not among the people he has yet notified of this change. Because Alice does not know that Bob has a new key, the public key she uses to encrypt to him corresponds to a key he has already revoked and does not want others to use. While the initial encryption to Bob using this key cannot be stopped, as Alice is unaware of its invalidity, Bob needs to be certain that on the next round of communication originating from Alice, she uses the correct new key to encrypt to him, replacing the older key as its default in the corresponding Bob identity in her database.
That said, if Alice and Bob have exchanged Trustwords and Bob's old key was trusted (creating a "green" channel in the parlance of the applications), Bob's new key should not retain this trust; rather, Alice and Bob should have to exchange trustwords again to establish trust for this particular new key, while still maintaining other communications channel information, such as whether or not Bob is a p≡p user.
This creates the following additional requirements:
The p≡p communications partner must have the means to process and validate such a notification. This creates the following relevant requirements:
The protocol must provide the means for processing and validating notifications as specified in requirements 5 through 8. This requires 16-21:
The protocol must verify that the notification contains at least one artifact signed by the now-revoked previous key.
The protocol must process the revocation certificate of the sender, recording the revocation with the cryptographic engine and mistrusting the revoked key in the management database. This certificate fulfills the requirement in a. above.
The protocol must verify that this revoked key corresponds to the extant default key of the user.
The protocol must verify that the replacement key is attached to the message and corresponds to the key information given in the received key reset message
The protocol must set the received key as the default key for the communications partner
The protocol must ensure that any trusted status gained by the previous exchange of Trustwords with the sending partner is removed; trusted status can only be set with the new key upon a new exchange of Trustwords.
A p≡p user has a key set as default for a communications partner that this partner does not want used for communication for a particular address (and, thus, in p≡p terms, a particular identity). However, that partner is not using, and may not have access to, the key reset mechanism for that key. This could happen if the partner is an OpenPGP partner, if the partner only had their private key on one device which is now inaccessible to them, or if the partner does not intend to revoke that key, they simply do not want it used for the address associated with the identity in question.
p≡p needs to provide a mechanism for the user to manually indicate that this key should not be used as the default.
This creates the following requirement:
(Note that if there is a compromise indicated, the p≡p protocol itself provides the means for users to mistrust keys of their contacts, and that this is not an explicit part of manual key reset of partner keys.)
A p≡p user may have exchanged Trustwords with a partner and accidentally or intentionally confirmed them and want to rescind that decision. Alternately, a p≡p user may have mistrusted a partner key and want to rescind that decision.
These two possibilities imply the following requirements:
N.B. This example requires understanding of the KeySync protocol, which is out of scope for this document. Minimal key terms are defined in the glossary.
KeySync is a protocol which allows several of a user's different devices running p≡p to synchronise and use the same private keys for synchronised own identities. This group of devices is called a device group.
A user may decide to reset one or more keys associated with identities marked for synchronisation. The request for reset is done on a single device, but must be propagated to the other devices. Because this is an automated reset of own private keys initiated externally for the other devices, it has some additional special requirements for security reasons, in addition to requirements 9-12:
This specification is being written a posteriori; thus, there already exists an implementation which fulfills these requirements.
The Key Reset protocol provides a high-level API to the adapter/application level which allows the reset, according to the requirements above, of either all of a user's default keys in the database, or of the default key associated with a specific identity. These functions are opaque to the upper layers; any necessary communications will be dropped into the applications message queue directly by the protocol, and all underlying database manipulation, key generation, etc, is done in the engine without further interaction with the application.
The engine is responsible for evaluating the input identity or identities (if only a user is specified to the engine), determining whether it is an own identity or a partner identity, and processing the reset appropriately according to the requirements, including management database manipulation, default key setting, and, where appropriate, key revocation, key generation, and sending of any initial key reset notification messages.
It is also responsible for receiving and processing key reset messages both from partner identities and from own identities, and for interacting with them in accordance with the requirements above.
An additional component of the solution, though not strictly required (as seen above), is that we provide a mechanism for opportunistic notification of recently contacted partners (where "recently contacted" indicates contact originating from the user, not received communications) at the time an own key reset is made. This is not strictly necessary, as we will notify on the first receipt of a message encrypted with a revoked key, but it does speed up the process of appropriate key usage by frequent communications partners.
The applications, on the other hand, are responsible for giving the users an interface to these functions as required [^user_caveat]. ([^user_caveat]: At the moment, under some circumstances, applications are only required to provide users with the option to reset an entire user. This should be discussed in more detail in a later version of the document, as the author may have gotten this partially wrong.) How this works will depend on how much of the user/identity model is exposed in their interfaces and the context from which the reset is called.
FIXME: Ask Huss/Thomas/Andreas for more input here. I don't know what they do. - KB
For the most part, the solution is an interaction triggered by the application, through the adapter, and serviced by the engine. At the end of processing, the old default key should be reset according to the requirements, given the input identity or user. Applications will need to implement context-dependent mechanisms to allow users to call the API functions. And, as with KeySync, Key Reset, at the engine level, will interact with the application's/adapter's message queue for this session, if present, putting Key Reset notifications into the queue for certain kinds of calls (specifically, own resets of various kinds).
The applications, then, are responsible for processing the message queue and ensuring sending and receipt of messages, as is normal.
The engine must implement and deliver the following API:
key_reset_identity(p≡p_SESSION session, p≡p_identity* ident, const char* fpr)
This function resets the default management database status for the identity / keypair provided by removing the fingerprint
fpr as a default key for this identity, and removing
any trusted or mistrusted status from the trust database for this key and this identity's user.
If this corresponds to an own identity and a private key, it will also revoke the key,
generate a new one, and communicate the reset to recently contacted p≡p partners for this identity.
If the fingerprint
NULL, then whatever key is set as the default for this identity
is treated as above. Note that if the key reset by this function is the default for any other user
or identity, it will be removed as the default for that identity.
Currently, this also removes a partner key from the keyring, where applicable[^key_election].
([^key_election]: This will change with the integration of key election removal.)
key_reset_user(p≡p_SESSION session, const char* user_id, const char* fpr)
This function effectively applies
key_reset_identity() to a series of identities corresponding
to the user as indicated by
user_id, as follows:
fpris present, apply
key_reset_identity()for each of the partner's identities containing
fpras the default key.
key_reset_identity()on ALL of the partner's identities corresponding to their
NULL fpras above.
user_idindicates the own user, however,
fprmust not be
NULL. The appropriate function in that case is
fpris present, then the functionality is as with the communications partner case.
As above, reset keys are removed as defaults for all users and identities.
This function will revoke and mistrust all own keys, generate new keys for all own identities, and opportunistically communicate key reset information to people we have recently contacted. This is effectively
key_reset_identity() for every own identity and own default key.
Note that if any identities share one of these own default keys as a default, they will each have different
(separate) new default keys after completion.
This function is, on the surface, like
key_reset_all_own_keys(), only it is only applied to the default
keys for identities that are marked for synchronisation as part of a KeySync device group.
However, because of the fact that these are synchronised identities, this function has additional functionality. This function must create a special Key Reset message to be used internally in order to communicate to each grouped device the following information:
This whole message is encrypted to and, more importantly, signed by one of the device group's current valid keys at the time the reset function is called. This function must wait until it produces and signs this message before, on the caller device, performing the revocation functionality associated with Key Reset of own keys and replacing with the new defaults it generated and sent to the other devices in the key reset message.
The device on which this function is called is the sole device responsible for communicating any opportunistic key reset messages to partners as described in Requirements 123123-12312312.
Processing the results of
key_reset_user() from a communications partner
Practically speaking, from the receiver point of view, this will only involve individual messages from
For any given message, the recipient must verify that:
If all of these things are true, then the recipient will replace the new key as the default for this identity in their
database and mistrust the revoked key.
Note that if the reset key is not the default key for this identity, the database will not change, but the
revocation certificate will be imported as well as the new key. This means that if another identity contains
the to-be-replaced key as a default key, it will not be valid; however, it will not be removed as the default key
for that identity until the engine tries to use it, and it will not be replaced by the newly-sent key unless a
specific key reset message is received for that identity indicating it should do so.
This is perhaps the most security-critical part of the protocol from the user's perspective, as it is processed automatically, it changes the user's default private keys, and it revokes their extant private keys.
When receiving an own_grouped_keys reset message, the user must verify that the key used to sign the message
corresponds to the default own identity it was sent from, that the corresponding key is still valid, and that
it contains a private key. Note that because
key_reset_own_grouped_keys() does not send revocation certificates,
but rather references to these keys to devices in the device group indicating which keys to replace and revoke locally,
this key will still be valid if it is an actionable and correct own grouped key reset message.
Should this be the case, for every transmitted identity and replacement key pair, the recipient device will revoke the old key for that identity and replace it with the indicated new key (instead of generating a new key). Recipient devices do not send out key reset notifications to partners, as this was handled by the device that generated the reset message.
These new keys are then trusted as new keys and operation can continue as normal.
Implementation requires the following features, many of which were present before Key Reset was implemented:
social_graph table, binding partner identities with the addresses the user has contacted them from.
This is to avoid exposing own user aliases to the partner when sending key reset messages and ensures there is a
match between the address the reset is for and the identity the partner associates with the key to be reset
on the recipient end. Note that only identities the user as proactively contacted themselves are contained in this
table, an important note for 2).
Timestamps on identities indicating recent access or update. This is used to filter which partners to opportunistically contact. Note that only identities which the user has intentionally communicated with (rather than just receiving a message from) will be sent these opportunistic messages; this is to prevent spammers from receiving key reset messages.
Other tables and fields (e.g. ```main_key_fpr`` for identity default keys, etc) are already integral to the system and are used here, but their DDL semantics remain unaltered.
FIXME: This should probably, in fact, indicate these fields and tables, but it depends on how deep we intend the spec to go, and this is dragging on as an example.
In this section, we take the indicated use cases from the requirements section and show how the protocol operates.
Recall that the p≡p user, in this example, wants to replace one default key from one identity.
The application must provide a way for the user to select the identity (presumably by address)
they wish to reset. Since the application does not keep track of the default key for that address,
but does (either in the application or through the adapter) have a constant representation
of the own
user_id, it will call
key_reset_identity with the
the appropriate own identity, and a
The engine then:
This example featured a p≡p user which wanted to reset all of their own keys on their single, ungrouped device and wished to invalidate their keys for future use.
In this case, the application provides a mechanism for the user to simply reset all own keys.
This will call
key_reset_all_own_keys() with the current session as the argument.
The engine will then use its knowledge of its own
user_id to fetch all own identities, and then,
for each own identity, proceed as in step 2 of Example 1 above.
In this example, a p≡p user, Alice, only has an outdated key from her p≡p communications partner, Bob. Bob has revoked the key, but Alice is unaware of it, and so sends Bob a message encrypted to the key he has revoked.
Bob, who still has the revoked key in his keyring and can decrypt with it, decrypts and verifies
Alice's message as usual. However, in
decrypt_message(), the engine notes that Alice is
using one of Bob's revoked, mistrusted keys.
The engine looks up the revoked key in the database. If its replacement key is his current default, it creates a key reset message for alice containing the revocation certificate of the old key (this can be done by just sending the revoked key, which contains the revocation certificate), his new key along with the specified key reset information.
If, however, the engine notes that the key that replaced his revoked key is also revoked, it follows the chain of replacements until it finds the current valid default key and uses this in the key reset message.
Alice then receives Bob's message. On decrypting his message, the engine will import both the new key and the revocation certificate. On processing the key reset message, the engine will, if it notes that the old key is now revoked in her keyring and the message is signed by the new key, mistrust Bob's old default key and replace the default key for Bob's respective identity with the new key; however, no trust status will carry over to the new key.
If Alice wishes to trust Bob's new key, she will contact Bob on a side channel and exchange Trustwords for their combined public keys and set the trust for the new keypair if she can verify them.
There are two likely scenarios which generate this use case: Bob is an OpenPGP user with several keys, and Alice's p≡p installation has chosen to make the wrong one the default, or perhaps Bob is a p≡p user who has reinstalled his client several times without resetting keys, and thus has partners who have an unusable (for Bob) public key for him.
In either event, Bob contacts Alice and says, "Hey, I need you to stop using that public key" in the first case, or in the second, "Hey, I can't decrypt the mails you sent me."
In both cases, the application provides the means for Alice to either reset an identity
or reset the user (note that in engine parlance this is resetting the key of the identity
or user, but the application does not keep track of keys). Presuming the application allows
resets at the identity level of granularity (e.g. contact address rather than contact),
it will call
key_reset_identity() with Bob's identity and a
The engine will then see that this is a partner identity and remove the current default key as the default as well as resetting its trust status in the database. This will leave an empty default [^key_deletion]. ([^key_deletion]: IMPORTANT NOTE: In the current implementation, we remove Bob's reset key from the keyring entirely. This is to ensure that key election does not, next time Bob's identity is updated, simply reselect the reset key. See * for more details on this and this will change in the near future).
If, on the other hand, only the user (e.g. the user's keys) is available as a reset option
in the application UI, the application will call
key_reset_user with Bob's
NULL fpr. This will repeat the process above for individual identities for each
of Bob's known identities.
Bob should then mail Alice again. If he is mailing from a p≡p client, he will automatically attach his new key and it should be selected as the default on receipt (again, see *). If it was a full user reset, he will at some point need to mail from all impacted accounts in order to ensure Alice has keys for each. If Alice and Bob wish to trust these keys, they must exchange Trustwords (possibly again) for each impacted identity.
If Bob is mailing from an OpenPGP client, he should simply attach his key to a message and mail Alice at his earliest convenience.
Recall that this involves a user wanting to reset the trusted or mistrusted status of a communications partner identity.
The application must provide the means for the user to select an identity whose trust should
be reset. This functionality should call
key_reset_user() as in
example 4 and will take the same steps with the same remedy.
There are a couple of examples where this could happen - a grouped device is reset with
reset_all_own_keys(), and some of the identities corresponding to some keys are
marked for synchonisation, or as an internal function, a device leaves a device group
and the remaining member devices need to revoke old keys and set new ones.
####### Manual reset of grouped keys
In the first case,
reset_all_own_keys() separates out the identities which are
synchronised identities and which ones are non-synchronised identities. Non-synchronised identities
are subjected to the same treatment as examples 1/2. The remaining identities are
key_reset_own_grouped_keys(); through this function, the engine collects
all identities which are marked for synchronisation and proceeds as specified in
key_reset_own_grouped_keys() (from the initiating device) and
the processing description for key reset messages generated by
key_reset_own_grouped_keys() (for the recipient devices).
####### Leaving a device group
In the case where the user decides to take a device out of a device group, this part of the protocol becomes more complicated. We divide the actors, at first, into two groups: the leaver, and the remaining group.
When the leaving device calls
leave_device_group() within the KeySync protocol, two
sets of events are triggered, one set for the leaving device, and one for the remaining group.
The leaving device notifies the group it is leaving, unmarks all of its identities for
synchronisation, and then resets all of them locally via
key_reset_user() and proceeds as with Example 2.
The group, on the other hand, chooses a leader. This leader calls
and both the leader, as the initiating device, and the rest of the group, as recipient
devices, proceed as under manual reset of grouped keys above in this example.
See section security.
Suggested logging additions, at a minimum, would be the fingerprints of reset default keys and their replacements as well as the event that triggered their reset, or, alternately/additionally, reasons for failure.
Key Reset has been deployed for some time and involves heavy implementation in the engine as well as access at the application and UI level. This was achieved some time ago.
Should there be API changes or radical changes in behaviour, the engine team will file tickets with the appropriate stakeholders (adapter for API changes, adapter and applications for semantic and functionality changes).
Does P = NP?
This is because once revoked, we cannot sign with the old private key. ↩︎