Skip to content

Instantly share code, notes, and snippets.

@staab
Last active April 27, 2024 05:04
Show Gist options
  • Save staab/f8284af12450dbbdcead6e0c3ed95e2c to your computer and use it in GitHub Desktop.
Save staab/f8284af12450dbbdcead6e0c3ed95e2c to your computer and use it in GitHub Desktop.
A survey of Nostr DM proposals

This is an attempt to take a step back and summarize all proposed approaches to private messages (DMs, group chats, and general-purpose nostr-within nostr, including for large groups of people) for the purpose of building a secure, feature-complete, interoperable solution.

This topic has come up repeatedly over nostr's history, and has entered the limelight again because of HRF's e2e encrypted group chats bounty. The hope here is to get everyone on the same page and hammer out one or more NIPs that can incorporate the best parts of all proposed solutions so we can finally get secure messaging on nostr.

Please comment with thoughts, criticisms, missing proposals/implmentations, and I will update the gist as we go along.

Proposals Reference

Problems with NIP 04

  • Metadata leakage
  • No future secrecy
  • No group chat support
  • No generic kind support
  • Poor cryptography primitives

Common Themes

  • General-purpose wrappers (59, 24b, nostr-protocol/nips#107 (comment))
  • Ephemeral keys (59, 24b, 107)
  • Key exchange (101, 76, 24a, 31)
  • BIP-32 key derivation (31, 76)
  • Entrust relays with the role of obscuring metadata using AUTH (29, 44)
  • Group chat implemented as multiple DMs (31, 112)
  • Group chat implemented using shared secrets (38, 112, 76)
  • Reliance on NIP 44 as a solid cryptographic base (59, 24b, 107)
  • Ability to REQ wrapped events with minimal metadata leakage as a tradeoff (59, b1)
  • Randomization of outer created_at field to obscure timing analysis (24b)
  • Multiple wrappers (onion routing) (103, 24b)
  • Using expiration with relay cooperation to facilitate better forward secrecy (112)
  • Incorporation of nsec bunker to implement key sharing with revocable and limited authorization (b1)
  • Making messages "leak-proof" (in the sense that even if the content is shared, the signature can't be) by stripping sig (24b)
  • Sending messages to multiple pubkeys to obscure true recipient (17)
  • Moderator/member lists (29, b1, 172)
  • Using zaps to bootstrap DMs (107)
  • DMS between users can take advantage of ECDH shared secrets that groups cannot, obscuring metadata and still allow subscriptions and plausible deniability. But it does not allow someone to send a DM to somebody they don't know. (107)

Implementations

Summary

The consensus at this point seems to be that:

  1. The encryption described by NIP-44 (not the entire NIP) is superior to NIP 04, and should be used going forward.
  2. Gift wrap is a useful general-purpose primitive for dissociating sender and receiver. Many proposals use this concept, even if they don't follow NIP 59 in particular.

NIPs 112 and 24b seem to adhere closest to the consensus above. NIP 112 has the advantage of including a scheme for key exchange and rotation, while 24b reduces the impact of key leakage on the entire group.

As for the others:

  • NIP 103 introduces unnecessary indirection which will impact deliverability by routing messages through other keys controlled by bots. Double-wrapping per NIP 24b solves this much more cleanly.
  • BIP-32 derivation (76, 31) introduces unnecessary complexity and doesn't solve forward secrecy.
  • Naive shared secrets (38, 112, 76) fail to provide forward secrecy, which is especially problematic for larger groups. If shared secrets are used, invalidation should be a part of the protocol as described in NIP 112.
  • 24a, 18, and others are very old proposals and offer only partial solutions.
  • 101 is only a partial solution. However, it offers a solid key exchange protocol which can be adapted to fit a more complete solution. Its key exchange schema could be improved further by moving away from long-lived aliases in favor of session keys by specifying recommended invalidation behavior (see NIP 112). This would provide a measure of forward secrecy. This key exchange protocol can also be adapted to negotiate shared keys for groups as well.
  • NIP 29's relay-centric approach seems to be relatively unpopular, and while relay selection can be a recommendation for improved privacy (as in several proposals), it's not sufficient on its own.
  • NIP 172 is not really related to the discussion, except for how it manages moderation, similar to 29 and b1. Moderation is a desired feature for many encrypted group chat use cases.

Outstanding issues

Forward secrecy

No solution proposed solves forward secrecy. In order for it to be solved, we have to have:

  • Key revocation. This means that long-lived keys with no invalidation/rotation scheme (whether shared or not) can't be used.
  • Ratchets. As long as session keys can be discovered by decrypting either one's own events or those received from another party, the chain of key rotation can be followed forward in time. Likewise, in some cases leakage of a session key might leak other session keys backwards in time.

Forward secrecy depends either on the destruction of information or on storing it out-of-band. Event expiration as proposed by 112 is a partial solution because it breaks the chain of key exchange, but can't stand up against hostile relays who refuse to cooperate. 24b's double-wrapping could get us closer to forward secrecy, if instead of sending a wrapper to oneself, the client only stored messages locally. This would break message sharing between client instances, but would make it so that a person's message history would only be recoverable if their correspondent's key was leaked (as opposed to their own). This limitation could be overcome by allowing users to transfer message history out of band (e.g. by animated qr code, export/import, or another event kind signed with an ephemeral key shared out of band).

Adding key exchange to 24b's double-wrapping approach could further limit the impact of a leaked key, if the attacker is unable to retrieve intermediate events.

Another improvement might be to exchange keys (or a shared nonce) out-of-protocol using a p2p encrypted channel, qr code, or other method. This way, session keys could not be discovered as a result of user private key leakage.

Of course, as @earonesty notes here, true deniability is probably out of scope for nostr, so we should probably just do the best with what we have.

More:

Scaling large groups

One important use case for encrypted groups is very large groups (1000+). In such a situation, shared secrets will almost certainly not stay private, and the space complexity of 24b's approach (sending every message to each member) is O(members * messages). In addition, group membership in 24b cannot be dynamic since the group is defined by its members.

By adding key exchange to 24b, large groups could be partitioned into n groups by sharing n keys among all members, and introduce key invalidation. This would change the space complexity of such a group to O(members/n * messages), which could be much more manageable.

Relay-based attacks

Metadata leakage is still possible since relays can correlate session keys with real keys via connection/ip.

Relays can also refuse to store encrypted messages. Adding POW to wrappers would at least prove the content has value to the sender, and might convince relay operators to store those messages. Special-purpose relays could opt to store only encrypted data and build a business model on charging for such higher-risk storage.

Decoupling components

I think the way froward involves identifying which layers this problem can be broken down into, and re-assembling them to support a given set of trade-offs which are still largely compatible with different implementations. Here's what I propose:

  • A new NIP (NIP A) should combine details related to cryptography from NIP-44, and the wrapping schema defined by NIP-59 and NIP-24b. Double-wrapped events should just be the standard for gift wrapping, since they provide much more flexibility and privacy than a bare 1059. This NIP should not include details about specific use cases (i.e. kind 44, what defines a "group", etc), but should mention that any kind can be wrapped to accomplish nostr-in-nostr.
  • A new NIP (NIP B) should be drafted to define a key exchange protocol similar to NIP 101. Invalidation/expiration/rotation should be included, and sharing keys betweeen two or more parties, should be differentiated from the large-group use case of sharing a few keys across a larger number of people (in this case, a group admin might be responsible for generating and rotating n private keys and sending them to group members. That way member clients would only have to know how to receive and use invitations).
  • A new NIP (NIP C) should be drafted describing how to use A and B together to implement DMs.
  • A new NIP (NIP D) should be drafted describing how to use A and B together to implement group chats (similar to 24b).
  • A new NIP (NIP E) should be drafted describing how to use A and B together to implement large groups (similar to 112).

This allows us to share a common set of building blocks across different encrypted use cases without tying them all together. Certain affordances (like adding k tags to wrappers) can be recommended or not by C/D/E based on use case, rather than in the core nips.

@earonesty
Copy link

earonesty commented Jul 31, 2023

it is a good summary of everything. personally I don't like the forward secrecy concept because you're implicitly trusting the relay to discard data no matter what. if the relay adheres to ephemeral protocol, it leads to a user experience where messages are dropped if you move between clients.

that being said it seems important to people so any proposal should probably have that optionality,

in addition DMS between users can take advantage of ECDH shared secrets that groups cannot. for example a shared secret can be used as a private key. I'm not sure if that's mentioned above but I do think that that solution is very different and it is the solution we currently use to obscure metadata between DMS and still allow subscription and plausible deniability. but it does not allow someone to send a DM to somebody they don't know. so we still have to use nip44 for those.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment