Home
As secure messaging/email applications become more wide-spread, users still face the difficulties of key management. Even if existing secure messaging applications have built-in key management, these often still do not have a way for users to ensure that the keys for their friends/contacts remain consistent over time and across users. We have developed CONIKS to address this issue. CONIKS is a key management service for end-user public keys that integrates into existing secure messaging systems. It requires centralized identity providers to maintain consistent bindings of names to keys in directories containing all bindings registered under their individual namespaces/domains. Because these key directories are cryptographically verifiable, identity providers do not need to be trusted, which allows clients to verify the consistency of bindings in-band. This means that users do not have to worry about verifying keys out-of-band, or managing keys altogether.
How do clients check the consistency of bindings?
In a strawman design, each client could periodically download the entire key directory and check that each individual bindings is included in the provider's directory and has not changed unexpectedly since the last check. Then to check that each client is seeing a consistent view of the provider's directory, each client exchanges and compares its version of the key directory with every other client. This way, all clients can be sure that all bindings in the provider's key directory are consistent over time and across different "locations". But this is very wasteful in terms of storage and bandwidth.
Our design for CONIKS focuses on making consistency checks more efficient. First, we divide time into epochs. This allows providers to create snapshots of their entire key directory at regular time intervals. Thus, clients no longer have to check all individual bindings in a directory. Second, providers also distribute their snapshots to other providers in order to build a verifiable history of their directory. Third, the snapshots providers generate are digitally signed so they cannot later deny having created them.
We achieve these properties by requiring each provider to maintain all of the bindings it manages in a tamper-evident data structure called a binary Merkle prefix tree.
Merkle trees give us the nice property that the root node represents the state of the entire structure because each node in the tree contains the hash of its two subtrees below it. From this, we get the property that any change in one of the leaf nodes containing a key binding results in a change in the value of the root hash. So when identity providers create the snapshots of their directory, all they do is generate the root of their directory tree and digitally sign it for non-repudiation.
A Merkle prefix tree additionally imposes an ordering on the contents of the tree as each branch represents the next bit in the binary representation of a leaf node's lookup index. In particular, the left subtree of a node contains the all indices whose next bit is 0, and the right subtree contains all indices whose next bit is 1. At this point, it is only important to know that providers in CONIKS have a way of converting odrinary usernames into these lookup indices such that each name is assigned a unique index. For more details, please read our technical paper.
How do clients check that key bindings are consistent using this data structure?
First, since clients check the consistency using only snapshots of the key directory, they need a way to know that a binding they want to retrieve for communication is in fact in a given version of the directory, i.e., it is consistent with the snapshot for a given epoch. Thus, whenever a client looks up a binding, the provider sends a proof of inclusion that clients can verify. This proof of inclusion consists of an authentication path, which is a pruned Merkle tree that only contains the nodes along the path from the requested binding to the root. To verify the authentication path, the client recomputes the hash of each node along the path starting at the leaf node, and propagates the recomputed hash all the way up to the root. then, the client need only compare that the recomputed root is consistent with the directory snapshot for the same epoch.
Second, as providers generate and distribute a new directory snapshot at the beginning of every epoch to build a verifiable history of their directory, clients and providers need to ensure that every new snapshot is a proper extension of the snapshot history they have observed so far from some provider. To enable this check, providers include a hash of the previous epoch's tree root in the current snapshot, along with the current and previous epoch times. This creates a linear hash chain of snapshots, which enforces the property that if the provider ever equivocates, i.e. forks the chain in order to present diverging views of its history to different clients/providers, the malicious provider must maintain these forked hash chains for the rest of time, or otherwise risk detection when clients observe/are presented a snapshot belonging to a different branch of the hash chain.
CONIKS provides four main protocols for checking the consistency of bindings.
- Registration: register new name-to-key bindings, or update existing bindings with new keys.
- Key Lookup: verify that the requested binding is consistent with the key directory snapshot in a given epoch.
- Monitoring: check validity, i.e. the key in a requested binding has not been replaced with a spurious key.
- Auditing: check for non-equivocation, i.e. clients and providers see consistent directory snapshot histories.
For more technical details, please refer to our technical paper.