Written for veilid_core version 0.5.7

This post presents DHTKEM-DH: a Distributed Hash Table Key Encapsulation Mechanism using Diffie-Hellman, a system which implements secure secret sharing and group membership using the Veilid Distributed Hash Table (or DHT). Note that the system described here is not completely implemented and this post is primarily to serve as point of discussion for subsequent iterations on the idea. In particular, I do not recommend you use this design as written for anything, particularly the incomplete proof-of-concept implementation linked at the end. Again, this post is motivated primarily by a desire to document my thinking somewhere other than offline journals and to serve as a point of discussion for future iterations - for which there is a teaser at the end of this post.

Motivations & Threat Model

Cryptographically defining group membership is frequently useful for decentralized applications, especially those in which members of a group may not be online at the same time and between whom secure out-of-band coordination may be difficult.

Distribution is the perennial challenge with simply sharing a group key: out-of-band key distribution (i.e. telling your friend the password on the phone) frequently leaves much to be desired in terms of security, and sharing device-to-device via some interactive mechanism requires both the joiner and the inviter to be online at the same time. It would be nice if no private information had to be shared out of band, and did not require any particular members to be online simultaneously to agree on group membership.

To define our threat model more precisely: Privacy from casual surveillance by third-party actors with access to IP flows is the priority; resistance to attack by insiders or highly motivated targeted attacks is worthy of consideration but as a secondary concern. DHTKEM-DH is motivated a desire for a more decentralized, distributed world: devices should talk to each other directly, servers be used judiciously rather than treated as a baseline assumption, and data remain on its owner's devices.

Background

It is assumed that the reader is familiar with public-key cryptography and Diffie-Hellman key exchange.

The Veilid DHT is, to summarize extremely briefly for those unfamiliar, a key-value store kept on the Veilid network. The table is keyed by a hash of two things: A public key and a schema. The "schema" in this case is not a schema like a database schema; for the purposes of this post I will grievously oversimplify it as "the number of values in the record". If we fix that number, the Veilid DHT is effectively keyed by public key. In order to publish new values, those values must be signed with that public key's partner private key. Each record's values are limited to 1MB total maximum, among other limitations. For the rest of this post, a "record" will refer to a DHT record, a set of values associated with a keypair.

A DHT record remains available via the Veilid network while devices participating in the record have it open, and may be cached for a while beyond that. This has consequences for users of DHTKEM-DH, which will be described in the next section.

DHTKEM-DH Design & Properties

DHTKEM is concerned with trusted group membership and sharing information (such as encryption keys) within that group. A "group" is represented by a DHT record, with its data composed of references to "left" and "right" branches to other "group" records, and its own secret key encrypted for the owners of the left and right keys, using the shared secret resulting from the Diffie-Hellman key exchange of left and right. This forms a binary tree of records, where leaf nodes represent individual devices. Not every leaf node needs to have a DHT record associated with it; a public key may be present in the tree only as a child.

This may be slightly confusing. If so, I highly recommend pausing to go read Ink & Switch's description of BeeKEM, then coming back to finish. Seriously, it's very good at explaining the binary-tree-Diffie-Hellman thing, even though I apply the idea differently here. It's got pictures.

A group record is composed of:

• A header, containing the public key of the record
• A left child public key
• A right child public key
• A payload of bytes encrypted with left and right's Diffie-Hellman shared secret

A decrypted payload contains the record's ownership key (i.e. the private key corresponding to the public key in the header), and a list of symmetric keys (intended as a log of rotated keys). Data can be encrypted for other group members by using one of the symmetric keys stored in the payload. The group's public key may be included with data encrypted for the group. The maximum length of the list is dependent on the cryptosystem chosen and is left as an exercise to the reader.

New members may be added to the group by ensuring a public key owned by the new user appears in the tree. This may be done by creating a new individual node and converting the previous individual node into a group node, or by altering the child of a node to "insert" a new record midway into the tree. This can be used to maintain logical "subgroups", depending on where in the hierarchy new members are added.

In order to validate if a given public key is a member of a group, a validator must walk the tree starting from the root of the group until it either finds that public key or exhausts the tree. Group membership can only be determined by starting at the "root" group and walking the tree; since child nodes contain no information about "parent" nodes, nodes may be part of multiple group trees, there is no way to determine which groups a given public key is part of without inspecting the group trees in question.

The membership tree may be cached for offline use at the cost of possibly being out of date with membership additions or removals. The process of walking the tree may be slow, depending on the speed of the DHT and state of the participating devices, and walking the tree for a group in advance and keeping up to date using Veilid's DHT record watching mechanism is recommended for devices that are not resource-constrained. In addition, this will ensure the entire tree remains available via the DHT for other group members.

Since DHT records may "age out" and become unavailable on the network unless kept open or rehydrated, it is possible for portions of the tree to "age out" of the network, resulting in failures to traverse the tree. To prevent this, member systems which are able to should hold the records for the entire membership tree for known groups, and all nodes should minimally be able to rehydrate the records in the tree between their leaf and the root of the tree in order to guarantee that new or long-offline members can successfully traverse the tree to the root.

Member removal proves a bit trickier than member addition: once someone is a member of a group, they know the private key of the root group (and the groups in the tree between their node and the root). The keypair of the group cannot be changed, as it determines the DHT record's address, and so a new root group must be created with modified entries. Portions of the tree between the root and the subgroup containing the member to be removed must be replaced. Since members "higher" in the hierarchy cannot "look down" into child records to retrieve private key material, this may involve creating new subgroups out of whole-cloth. In this case, the member performing the group replacement ought to indicate this by placing itself in the new hierarchy.

To be honest, member removal with this scheme just sucks. It was part of the way through figuring out member removal that I decided that the limitations inherent in this scheme make it more trouble than it's worth to finish the implementation of this design, and to focus on a second iteration, using some of the same ideas with with slightly different primitives.

Implementation & Future Work

I've published a very rough proof-of-concept implementation demonstrating the core idea. Most notably missing is any implementation of removal, even as a stub. While figuring out how it would need to work, I was also considering how this design to could be adapted to use RFC 9180-compliant Hybrid Public Key Encryption (HPKE) primitives, and came to believe that a fundamental shift in the nature of the scheme is required. That new design based on HPKE primitives, however, will enable both more useful properties in the final scheme and also drastically reduce the number of DHT fetches required - look out for a draft design of DHTKEM-HPKE in this space in the coming months.

Inspirations & Comparisons

I will again tip my hat to BeeKEM as the primary inspiration for this work, though by necessity the application of the ideas differs: BeeKEM makes a similar application of the cryptographic properties of the Diffie-Hellman binary tree, but uses its own synchronization mechanism for sharing that tree between member systems. Effort is also dedicated to conflict resolution in BeeKEM, whereas DHTKEM-DH can largely rely on the Veilid DHT to solve both.

DHTKEM-DH's approach to member removal is more or less the same as well, in terms of "blanking" the tree between the member to be removed and the root. However, that becomes significantly more painful since the keys in question are used to address the DHT records holding the tree data, so changing the keys necessarily changes the address! It sure would be nice if we could figure out how to separate out some of these keys so granting group membership doesn't necessarily grant write access to the root record (perhaps something that can be resolved in a future iteration!).

The idea of the binary tree of Diffie-Hellman pairs, however, was used in RFC9420's "Ratchet Trees" as part of Messaging Layer Security (MLS) Protocol before it appeared in BeeKEM, in yet another context which uses a different coordination mechanism, in this case a central server which holds the tree.