As an outsider to the local-first ecosystem, working with Ink & Switch on BeeKEM made me realize that I held many implicit assumptions about cryptographic protocols which are not general. In this piece, I will discuss end-to-end encryption (E2EE) in the local-first setting and highlight how its security properties, threat model, and goals differ from the centralized setting implicit to most E2EE cloud applications.
First, I will define the notion of causal ordering, which has been referenced in prior posts but may be unfamiliar to readers from a more cryptography-oriented background (like me). I will then describe a type of attack which can be performed only in the decentralized CGKA setting and define a corresponding security property, which has no analogue in typical models of centralized CGKA. I will conclude by discussing a tension between forward secrecy and “tolerance to concurrency” in the decentralized setting and discussing areas of future work.
Hopefully this piece will serve to foreground the relevance of the assumed communication model in cryptographic protocols and increase academic interest in E2EE in settings beyond central-server applications.
To recap, BeeKEM is a Continuous Group Key Agreement (CGKA) protocol for the decentralized setting, where there is no central server as party to the protocol. Most CGKA protocols require a central server—and this assumption is typically unremarkable, as most downstream E2EE applications also require a central server anyway. However, because BeeKEM was developed to support Keyhive and other local-first applications, this assumption is untenable for the setting, and the protocol must be able to operate over a variety of communication architectures, such as peer-to-peer.
Coming into the project, it was initially unclear to me what special challenge is presented by developing a CGKA protocol for the decentralized setting. After all, isn’t the point of E2EE that the central server’s participation in the protocol is minimal? What actually hinges upon the existence of a central server?
It turns out that a lot actually depends upon the central server: the central server acts as a go-between for group members, and building without it has significant consequences for protocol design.
One of the primary functions of a central server is that it serializes the operations performed by group members, meaning that it imposes a canonical ordering of events. It is important for group members to agree upon the ordering of operations because the order typically affects behavior. For example, if Alice adds Carol to the group while Bob simultaneously removes Alice from the group, the order in which the central server processes these messages affects the outcome: namely, whether Alice’s addition happens first (and Carol is added) or whether Bob’s removal happens first, nullifying Alice’s addition (and Carol is not added).
There is not necessarily an underlying objective truth as to which operation occurs “first”: it might be that Alice presses the button on her phone ten milliseconds before Bob does, but Bob’s network connection to the server has lower latency, and so the central server receives his message first; or maybe Bob’s message arrives first but the server processes Alice’s request first anyway, etc. The important thing is that the centralized setting empowers the central server to declare a total ordering over operations (serialization) and broadcast messages to users accordingly. But in the decentralized setting, where there is no central server, there is no authority to create this ordering.
Many decentralized applications instead relax the protocol design to only assume a certain partial order over messages, called the causal order. I present a formal definition of the causal order then explicate its properties.
Definition [Causal Order] The causal order over events, denoted ≼, is the least partial order satisfying the following properties:
- If a user first performs event x, then performs event y, then x ≼ y.
- If a user receives a message informing them about event x before performing event y, then x ≼ y.
- The causal order is transitive (x ≼ y and y ≼ z ⇒ x ≼ z).
- The causal order is irreflexive, i.e. we do not have x ≼ x for any x.
The causal order captures an intuitive notion of (potential) causal dependencies between events: if a user is “aware of” a set of events X at the time that they perform y, then y is causally dependent upon every event in X, and therefore comes after those events in the causal ordering.
Some of the important properties of the causal order include:
- The causal order respects users’ “subjective” views of the ordering of events, i.e. that if a user sees an operation x before themselves performing an operation y, then x is before y in the causal order.
- “Simultaneous” operations can indeed manifest as such. If we have neither x ≼ y nor y ≼ x, we say that x and y are concurrent, denoted x ~ y.
- The causal order reduces to a serial ordering of messages when there are no concurrent operations. Concurrency can result in the group state diverging.
- Assuming only a network where broadcasted messages are eventually delivered (but no guarantees on ordering), it is possible for users to record the causal order over operations in an efficient and locally-computable way, only using a collision-resistant hash function.
This last property goes hand-in-hand with how BeeKEM is compatible with many possible network topologies and implementations—anything which supports eventual delivery of messages. If convenient, BeeKEM can make use of sync servers, which ferry messages between users—approaching the connectivity of a centralized protocol without any of the protocol-level duties ascribed to the central server. At the extreme end, BeeKEM could even be operated over the sneakernet, where the only communication between users happens through flash drives literally carried on foot between devices.
Viewed as a DAG over messages, the causal order also corresponds to how group state branches and diverges due to concurrency. Extended periods of concurrency, e.g. due to network partitions splitting the group, result in the creation of forks in the graph. The network healing, in turn, closes these forks.
For a familiar example of the causal order, the commit graph of a git repo can be viewed as implementing a causal order over commits. The changes to a repo which a given commit represents causally depend upon those commits which created that repo; likewise, any further commits which build upon a commit causally depend upon that commit in turn. (The analogy is not perfect: it is possible to e.g. checkout a particular commit and create a new commit that is a descendant only of that commit even if the repo has already recorded other later commits.)
As mentioned in a prior post, the classic CGKA security properties of Forward Secrecy and Post-Compromise Security have natural analogues in the decentralized setting. Rather than “before” and “after” being determined based on a linear ordering of epochs, instead we reference the causal ordering.
This raises an immediate question by omission: what guarantees should be offered with respect to update secrets which are from operations concurrent to the most recent update of the compromised user? Put differently, are there schemes in which an adversary can compromise a user on one branch and use that user’s state to attack a group secret on a different branch?
This type of “cross-fork attack” is actually possible upon prior decentralized CGKA schemes, such as Causal TreeKEM and the scheme proposed by Weidner et al. For BeeKEM, we have formalized security against cross-fork attacks as a security property given the creative name “cross-fork security,” which I will omit a formal definition of. Informally, cross-fork security states that compromising a user does not allow an adversary to obtain group secrets defined by Update operations concurrent to the compromised user’s most recent processed Update.
There is a sense in which the weakness of decentralized protocols to cross-fork attacks seems inherent: if Alice is compromised and Bob performs an Update, the resulting group secret must necessarily be available to Alice for correctness. Being more precise about the exact possible security guarantees requires introducing the notion of a security parameter.
BeeKEM is parameterized by a natural number, the “security parameter” (denoted kappa κ), which can be thought of as controlling a tradeoff between security and robustness to concurrency.1 Specifically, the security parameter is the number of individual secrets which a user retains at all times. So for example, with κ = 3, the user retains their current individual secret, as well as their previous and second-previous individual secrets.
To explain the significance of the security parameter, it is worth spelling out a mental model of how Updates work in a DCGKA scheme. Consider the following mental model: whenever a user A performs an Update, the resulting group secret is (necessarily, for correctness) accessible to the individual secrets of all current group members, under A’s current view. A’s view is subjective; it is specific to their current state of both group membership and the group members’ associated secrets.
Intuitively, any κ > 1 immediately eliminates forward secrecy, as a user losing their local state entails the loss of older versions of their individual secrets, and thus potentially some number of older group secrets.2
However, κ > 1 is also necessary to handle the possibility of group partitions and concurrency, which is important for local-first software. Suppose that Alice and Bob are separated into different fragments of a network partition and Alice Updates; her fragment of the network uses the new group secret she defined to encrypt data. The network later heals, and it is discovered that Bob performed a concurrent Update under partition. Unless he has retained the individual secret he possessed prior to partition, the group secret (and data encrypted under that secret) will be inaccessible to Bob. Thus users must retain some number of old individual group secrets in order to access group secrets defined under concurrency.3
As is suggested from the motivating example, the formal definition of cross-fork security depends upon κ: higher values of κ cause fewer concurrent group secrets to be protected, as that user has retained state which was used in relatively more group secrets.4 The above figure illustrates the three security properties targeted by BeeKEM with κ=2: nodes denote updates, with the nodes labeled “id” denoting a user of interest. The user “id” is compromised at the point denoted by the X. Nodes with the solid blue background are protected under Forward Secrecy; nodes with the red horizontal stripe background are protected under Post-Compromise Security; and nodes with the yellow vertical stripe background are protected under Cross-Fork Security (all with κ=2). Nodes with no background are given no security guarantees.
We stress that κ > 1 still leads to a meaningful definition of cross-fork security (and of forward secrecy, which is also affected by κ). Even if there are stronger security definitions, security is not the only consideration for a protocol: there are contexts where it is not important to access group secrets defined under concurrency, or at least that it is not relatively as important as forward secrecy. (There may be contexts, for example, where re-encrypting all data encrypted under concurrent group secrets is not prohibitively expensive.) But BeeKEM was developed for a context where i) it is important that users can access these ciphertexts without reencryption and ii) forward secrecy is not considered very important.
I had not yet encountered a context where engineering concerns dominate security concerns; indeed, as a cryptographer I naturally think more about security considerations.
Conclusion
Cryptographers are broadly aware of the ways in which implementations of cryptographic schemes introduce a lot of complications in practice—side channel attacks, subtle bugs, etc. But there are other kinds of “engineering”-type considerations which are critical to the design of cryptographic protocols. Working on formalizing the security of BeeKEM helped illustrate some of these considerations to me, such as the significance of having a serialization of operations in multi-party protocols for both protocol design and security.
I hope that this post will help cast light on the challenges of decentralization for cryptographic protocols5 and, beyond that, encourage cryptographers to remain attentive to the engineering considerations that shape cryptographic protocols in practice.
The actual implementation of BeeKEM uses a security parameter set to infinity, but other values are conceivable and help illustrate what is underpinning the design of the protocol. ↩︎
Actually, if we want to be very exact, BeeKEM (like TreeKEM) does not have standard forward secrecy even when κ = 1 because the same individual secret can access multiple group secrets. ↩︎
There are some optimizations that can be performed by using tests for member activity or the presence of partitions. For example, one could dynamically increase κ when members do not reply to pings. BeeKEM does not implement such things for simplicity. ↩︎
We lack a formal impossibility result; it seems inherent, but this is something I will be thinking about a little more. ↩︎
Local-first design also has security benefits, such as reducing dependence upon a single company—see this Ink & Switch essay on the local-first ecosystem for a more detailed discussion. ↩︎
This is the last entry for now, but you can go back to read the lab notebook from the beginning.
The Ink & Switch Dispatch
Keep up-to-date with the lab's latest findings, appearances, and happenings by subscribing to our newsletter. For a sneak peek, browse the archive.
Instagram Engineering
Shopify Engineering