Oddbean

3/n Keychat's initial encrypted group chat implementation, known as "pairwise group," will be rebranded as "small group" in the forthcoming version. In this setup, when a group member sends a message within the small group, they are effectively sending a separate one-on-one message to each other member, creating a group chat through multiple individual chats. Thus, this model nearly completely retains the security features of one-on-one chats, fulfilling the five previously mentioned requirements. However, it supports only a limited number of participants and operates on an expensive "one stamp per message" basis. https://image.nostr.build/c898221292eaa597b992d5fe9acd94a4f1f4fb3ac52935f2eac184e237f89f2f.jpg

4/n Keychat's second implementation of encrypted group chat is termed "shared key group," which will be discontinued in the next release. Within a shared key group, a single encryption key is shared among all participants. Members encrypt their messages using this common key before sending, and others decrypt using the same key upon reception. This setup fails to meet the third and fourth requirements previously outlined. If a member who has compromised the group's confidentiality needs to be removed, fundamentally, a new group must be created. The group administrator must individually communicate the new shared key to each member of the new group, denoted as N, the number of participants. This illustrates a significant drawback of the shared key group: the inefficiency in dynamically updating its members. Visualizing the five types of end-to-end encrypted group chats as a spectrum, the pairwise group occupies the most secure position, while the shared key group is positioned at the least secure end. Initially, Keychat tested both extremes of this spectrum before proceeding to explore the intermediate options. https://image.nostr.build/70994a1f9e8ba57bafd0a295f47be278df72be85382f0fc629d34080767dc293.jpg

5/n The "sender key group" is the protocol currently employed by the Signal app. Previously, Signal utilized the "pairwise group" model. We argue that Signal should have retained the pairwise group alongside introducing the sender key group, offering users a choice between the two. In a sender key group, new members communicate their initial encryption key, k0, to the existing members. They use this key to encrypt their first message with k1 = kdf(k0), with subsequent messages encrypted using a succession of keys derived from the previous one, k2 = kdf(k1), and so on, where kdf is a one-way key derivation function. Other members decrypt messages by sequentially deriving keys from k0. These encryption keys are deleted after use, ensuring forward secrecy (meeting requirement 3), but failing to ensure backward secrecy (failing requirement 4). Removing a member who has compromised the group's secrecy effectively requires forming a new group. This necessitates each remaining member conducting N*N one-on-one chats to share their new k0, where N is the total number of members in the new group. This is the primary challenge of the sender key group: inefficiently updating membership. Both the "upgraded sender key group" and the "MLS group" seek to address this by enabling efficient membership updates. Achieving efficient updates of k0 would fulfill requirement 4, providing backward secrecy. Keychat bypassed the sender key group in favor of developing the upgraded sender key group model.

6/n Keychat is on the verge of launching an updated model known as the upgraded sender key group, expected to be released this week and will be termed "medium group" in the new version. Unlike the sender key group, where each member communicates their initial key, k0, to all other members, the upgraded sender key group has members sharing a common group key, k, akin to the mechanism used in the shared key group. Each member derives their personal k0 using a Diffie-Hellman calculation with their ID and the shared group key. They then encrypt their first message with k1 = kdf(k0), and subsequent messages with sequentially derived keys, like k2 = kdf(k1). Other members decrypt incoming messages by sequentially deriving keys from the sender's k0. After use, these encryption keys are discarded. Thus, the upgraded sender key group maintains forward secrecy, meeting the third requirement, but does not offer backward secrecy, failing to meet the fourth requirement. Efficiently updating the group key, k, would enable the group to meet the fourth requirement concerning backward secrecy. If a member who has disclosed confidential chat information needs to be removed, a new group formation is necessary. The group admin must then individually share the new encryption key, k, with each member, where N represents the number of members. This upgraded approach reduces the need for member updates from N*N individual chats in the sender key group to just N chats in the upgraded sender key group, significantly enhancing efficiency and maintaining forward secrecy. Alternatively, this model could be described as an upgraded shared key group because, compared to the original shared key group, it offers forward secrecy and simplifies member updates to only N individual chats. Yet, the requirement for N individual chats to update members remains a significant challenge for larger groups.

7/n The MLS (Messaging Layer Security) group's central feature is its efficiency in updating both group members and the shared root key, reducing the number of necessary communications from N individual chats down to log2(N). Consider the MLS group as an evolution of the upgraded sender key group, with a similar mechanism for deriving encryption keys from a root key at the top of a hierarchy. Imagine a scenario where a group member, A, believes their key has been compromised and needs an update. This would trigger an update of the root key. But the challenge is how A informs the rest of the group about this change. In an upgraded sender key group, A would have to individually communicate with every other member, resulting in N-1 private messages. The MLS group, however, is structured around a key tree. The leaves of this tree represent the group members—A through H—with the root key at the very top. A distinctive feature of this structure is that each child node has access to its parent node’s private key. For instance, A can update E, F, G, and H by sending a single message encrypted with the public key of node 1. Since these members are the children of node 1 and possess its private key, they can decrypt the message. Similarly, A can inform C and D by encrypting a message with the public key of node 2, to which they, being children of node 2, have the private key and can thus decrypt. A directly communicates the update to B with one personal message. In total, A needs to send log2(8) = 3 messages to update the entire group. If the group size were as large as 1024 members, A would only need to send log2(1024) = 10 messages. This efficient mechanism of updating members and the root key grants the MLS group the backward secrecy feature, an enhancement over capabilities found in the upgraded sender key group. We are studying the MLS protocol and will implement the MLS group feature in Keychat later. https://image.nostr.build/da70b8c9dea1a8954e6bca4e9d8f60b74df87555e1944810e73c61c620b28494.jpg