NIP-24: Private Messages

[jeffthibault]

Replaces #52

Formatted: https://github.com/jeffthibault/nips/blob/private-messages-v2/24.md

POC python code: https://github.com/jeffthibault/nostr-nip24-poc

[jeffthibault]

@jb55 @Cameri I created a new PR. The NIP now contains a way to obfuscate the sender and receiver's pubkey. POC python code also added.

[monlovesmango]

I do think the new kind 12 will be necessary to orchestrate this extra private DM so good to see that.

I had a couple questions:

• how is R[d-] defined? in order for receiver to send back DMs from the R[d+] pubkey they will need to know the R[d-]
• how will senders track all the RDIH events sent out?

@Cameri I think this scheme could easily be extensible for Randy's suggestion https://github.com/nostr-protocol/nips/pull/52#issuecomment-1278449938

[jeffthibault]

• how is R[d-] defined? in order for receiver to send back DMs from the R[d+] pubkey they will need to know the R[d-]

It's the same as Step 1 in the Sending section. When the receiver is responding, they are now the sender.

• how will senders track all the RDIH events sent out?

Not sure if I totally understand the question but the sender just needs to subscribe to all kind 4 events they have sent and will have all the RDIHs they have sent messages to. All RDIHs are deterministically derived from the sender's private key and the receiver's real public key.

[monlovesmango]

ok I think I understand now, thank you. I like that you can't even tell that these decoy keys are talking to each other (right?). nice proposal!

[jeffthibault]

Yeah, an outside observer will have no clue what people are talking to each other.

However, if two people are messaging via a malicious relay, such as one that logs IP addresses, then that could potentially be a problem. But that can be mitigated by connecting to relays with a VPN/Tor or running your own relay.

[cameri]

@jeffthibault any chance we could see a working implementation of this NIP?

[jeffthibault]

@jeffthibault any chance we could see a working implementation of this NIP?

There is a link to the POC implementation code that I wrote at the top of this PR. Is that good enough? I am not currently working on a client that I can implement this in.

[phyro]

First, I'd like to say that I'm not familiar with the query ability of the relays. My understanding is this NIP creates a new pubkey for each chat conversation which is only known to the party you're communicating with. Could an attacker query the following data:

1. all decoy proof events
2. query when new chatting keys appeared i.e. created_at=after_decoy_proof && kind=4 && pubkey=not_seen_before (I'm aware that not_seen_before doesn't exist, but you could find all events for a key and see when the first one was signed)

If it's possible to get this information, an attacker might be able to correlate the decoy proof event with a new key and thus probabilistically leak the receiver pubkey (potentially with a high probability if new conversations events come in rarely). Then you might still be able to do a half unblinded recipient version of https://twitter.com/wiz/status/1605493271903342592 where we could learn the receiver X is chatting with someone and when.

[fiatjaf]

In other words, a lot of bloat and complication for nothing?

Can we please do not merge this for now? People are free to implement and try, but I don't think it will work long term, aside from the problems @phyro has identified above.

If I'm wrong and it is an amazing idea then we merge.

[phyro]

Oh, I'm not suggesting the attack can be done, I'm trying to understand things and am asking if it can be and whether this affects the state of the NIP. Even if it can be done, it's still an improvement over NIP-04 as it blinds at least one party (judging from a quick skim). There are more questions that come to mind related to private DMing though i.e. should DMs even be recognized events through their own kind or should they just be some encrypted content with a decoy kind event while the real kind is hidden in the encrypted content (less public labeling of encrypted data ~= greater privacy). This would affect the relay querying though.

[jeffthibault]

It seems like this kind of timing analysis is possible but as you mention, it is only probabilistic, not conclusive. You correctly mention that the probability of discovering the recipient's public key becomes higher if new conversations happen rarely but my thought is that more new conversations will happen as more people use nostr. In which case, the probability of doing this kind of analysis successfully will diminish.

Thanks for the feedback, I will think about it some more.

[ghost]

If hierarchical derivation of keys from a seed phrase is possible for nostr, we could have something like silent payment but instead of payment it will be silent messages.

So every nostr user can share a code which creates a new public key for everyone trying to DM. All DMs sent to different keys can be read using one account with a single seed phrase.

https://gist.github.com/RubenSomsen/c43b79517e7cb701ebf77eec6dbb46b8

[phyro]

@1440000bytes If I'm not mistaken, this would require a lot of scanning of all the DM messages. Months ago I was playing around with the idea how to improve DMs where I was trying to make the keys only be used once. Here's a TLDR: There's only 1 DM event type chat-dm. The start is similar to this NIP, you compute shared secret with an ephemeral key you created and communicate the ephemeral pubkey to the counterparty. Then the parties derive new keys based on the counter keeping track of historical messages. This comes with downsides i.e. it doesn't work well cross device because you need to keep up with the counter (you'd need to publish an event that describes the counter state or smth). You could do a similar thing without a counter and just keep communicating the "next" pubkey to the counterparty. Many variants are possible. What I documented has too much complexity imo, so please don't think of it as a proposal. Perhaps the most practical would be to communicate the next pubkey every X messages or minutes. I hope someone comes up with a scheme that achieves the following properties:

1. Minimizes the number of "kind" objects needed - preferably 0 so that we can decoy kind attribute
2. Use ephemeral keys (per message) or switch them up very frequently

This would provide a good "information" privacy, leaving only the relays being able to gather data of who's communicating with whom - I believe they can derive this by observing the websocket requests. I guess first step is blinding the event data itself and then we can try to tackle blinding the relays as well i.e. through dandelion-like event routing or similar.

[bernii]

@phyro I'm not sure I fully get the concern mentioned here: https://github.com/nostr-protocol/nips/pull/56#issuecomment-1361247687

The only thing that is being leaked is the fact that the recipient probably started a private conversation (second part of the handshake could happen subsequently to further obfuscate the parties).

To obfuscate the recipient at the expense of the processing power, the decoy events could have no target recipient specified but only the actual recipient would be able to decrypt the message directed at him. This means the clients would have to spend some time processing garbage but that might be okay as chat-start events might be fairly rare.

[phyro]

@bernii I'll try to break it down into steps. Let's say Alice wants to start a conversation with Bob.

1. Alice creates a throw-away key T and derives her key A' for conversation with Bob
2. Alice creates a decoy-key-proof event E1 whose content holds A', but is encrypted for B such that only Bob can read it
3. Alice publishes E1
4. Bob reads the event and derives his B' key for messaging Alice
5. Bob now publishes "hello world" event E2 through NIP-04 with the sender being B' for A'

What you can do now is the following. I can find decoy-key-proof event E1 and check its created_at field which is 12:05pm.

Note now that E2 is the first event where B' or A' appear. I can now query for NIP-04 DM events that happened after 12:05pm whose keys appeared for the first time and find E2, E3 and E4 which appeared on the same day. The sender of one of these three is likely Bob's key B'. Now we assume it's one of these three, but we don't know which one. We can play probabilities or do further analysis. Let's say we query all known relay servers to check which ones contain events from Bob - that is events with Bob's actual pubkey B which we saw in the decoy-key-proof event E1. This is the set of relay servers Bob is using. If E3 landed in one of these, but E2 and E4 did not, E3.sender is likely B'. It's entirely possible I may have made a mistake, please let me know if you find any and I will gladly correct them.

[bernii]

Thanks for laying it out!

I think you do have a good point under the condition that the actual pubkey B is publicly visible in the decoy-key-proof event E1.

As I mentioned above - this could be a good middleground of reasonable privacy vs efficiency - but an alternative could be sending decoy-key-proof Events without recipient. This way client implementations interested in footprint-less communication handshake would just spend some compute power to see if published decoy-key-proof events can be decrypted by them (meaning that a given user was actually the recipient). A little tradeoff - privacy for some additional wasted compute power 😄

[khimaros]

perhaps worth looking at how secure scuttlebutt solved this problem: https://ssbc.github.io/docs/ssb/end-to-end-encryption.html -- there are some performance trade-offs because everyone must try to decrypt every private message even if it is not destined for them, but they found that in practice it was an acceptable cost.

[jeffthibault]

@phyro Thanks for clearly breaking it down. The analysis is both logical and valid. With that being said, it does rely on the heuristic that B' will first appear on the same day as E1, which is a fair assumption but not guaranteed. Point being that Bob has plausible deniability. Also, do you agree with the premise that the probability of this analysis being successful goes down as more people start conversations?

Also, there is an Authentication NIP in the works that would prevent anyone from querying for other users' DMs. So if two people use this messaging scheme on relays that require authentication, they should have some pretty good privacy (as long as they use a VPN/Tor).

I am by no means an expert on this stuff. There is probably a better way to do private comms but I think this is at least better than NIP-04.

[phyro]

@bernii yes, if you blind B you resolve this, but this requires you to query all decoy-key-proof events and scan through them. I guess the tradeoff here is more bandwidth and more computation for blinding of B. I'm not familiar enough with the system to tell if this is good and scales in the long run.

@jeffthibault I agree with your points. It becomes increasingly unlikely if there are many such events around - unless Bob replies really fast (i.e. gets an event right away and starts chatting) or uses a very rarely used relay server in which case the relay set intersection analysis becomes effective. This definitely has higher privacy than NIP-04, especially when coupled with other NIPs you mentioned.

[jeffthibault]

A thought I had to reduce the bloat that @fiatjaf mentioned is to make the decoy key proof event ephemeral. The clients do not need them after initial contact so the relays don't need to store them. Will update the NIP if others think this makes sense.

[cameri]

A thought I had to reduce the bloat that @fiatjaf mentioned is to make the decoy key proof event ephemeral. The clients do not need them after initial contact so the relays don't need to store them. Will update the NIP if others think this makes sense.

If both clients are not connected at the same time the ephemeral event will be missed. Something to be aware of.

[jeffthibault]

If both clients are not connected at the same time the ephemeral event will be missed. Something to be aware of.

Right...

Okay, will leave it as is for now. Thanks

[ghost]

Nothing is "sufficient" for privacy. It's a goal to work towards, but it is so multi-faceted that no single piece of technology can "solve" privacy.

https://www.reddit.com/r/Bitcoin/comments/e65vdf/could_bitcoins_privacy_benefit_from_litecoins_eb/f9oxfyk

[ursuscamp]

I think this is great. One thing I sort of found confusing was that the DKP's content is supposed to be encrypted, but it kept calling it "unencrypted content". Is that because "unencrypted content" is terminology from other specifications, or am I missing something?

[jeffthibault]

@ursuscamp I understand your confusion. The content of the DKP is encrypted. In the spec, I am just trying to show what the content looks like in plaintext because it is a specific format.

[dyng]

• how is R[d-] defined? in order for receiver to send back DMs from the R[d+] pubkey they will need to know the R[d-]

It's the same as Step 1 in the Sending section. When the receiver is responding, they are now the sender.

• how will senders track all the RDIH events sent out?

Not sure if I totally understand the question but the sender just needs to subscribe to all kind 4 events they have sent and will have all the RDIHs they have sent messages to. All RDIHs are deterministically derived from the sender's private key and the receiver's real public key.

I'm not sure if I understand right. I have two questions.

1. If the receiver want to reply to sender, does he need to send Decoy Key Proof for R[d+] to S[+] (the same as sender did in Step 1)?
2. How RDIH is used for? What about receiver and sender just listen to S[d+] and R[d+] without RDIH (i.e. ["REQ", "dms-with-sender", {"kinds": [4], authors=[<S[d+]>, <R[d+]>]}]

[dyng]

I think another problem is when migrating my account. After export-import private key to a new client, I can't retrieve my decoy key unless I remember the recipient's pubkey, and therefore can't recover private messages.

[staab]

Closing in favor of #574 and #686