Considered Harmful
Cryptography schemes involve layers of cryptographic patterns in order to provide a valuable tool to end users. The lower level patterns, such as hashing or signatures, generally have a straight forward interface and super strong guarantees backed by the maths. It is tempting to take a few of these patterns, describe a protocol involving them, and think to yourself “Dang, I just made a super secure X!”. Whatever X may be, it is built on these battle tested cryptography patterns, so it just inherits the properties! This is a trap though, leading to the often typed advice “Do not roll your own crypto.” While the patterns do in fact have these guarantees (maths), it is all to easy to describe a protocol which completely undermines them on accident. A scheme which does this is “considered harmful” since users will shoot themselves in the foot trying to use it.
I think nostr’s NIP-04 is an interesting example. If I was to hack out an encrypted chat protocol over nostr, I think it would look something like NIP-04! Which is not the greatest sign for NIP-04. But the nostr context is a complicated one and does a good job exposing why these schemes are difficult to create, so let’s start there. The goal of nostr is censorship-resistance. In the simplest nostr use case, users post signed messages (events) to any number of un-trusted (!) relay servers. Any user can read these messages and verify the signature attributing the message to the author. For a user to be censored, an adversary would need to stamp out all relays hosting the user’s messages. One can view all the nostr relay’s as a public, censorship-resistant file system. And when you make it sound like that, you can start to imagine all sorts of use cases to build on top of this shared file system. So what about sending a message to just one person instead of the default public broadcast? A private message of sorts.
Nostr already has public/private key cryptography built-in, that is how any message is signed by its author. If we know a user’s public key on nostr, can we just encrypt a message with that, so only the user could decrypt it with their private key? Sure could, a quick pit stop on why that is not the most efficient scheme though.
Hybrid Cryptography
Asymmetric cryptography (public key cryptography) is almost never used to encrypt a message directly. It is far less efficient to encrypt and decrypt data than symmetric cryptography schemes. However, it is much easier to establish a symmetric key over an open channel using asymmetric cryptography. So higher level protocols generally use a bit of asymmetric to get things started and then symmetric after that, in other words, hybrid cryptography.
NIP-04
Ok, so we won’t encrypt the whole private message with the receiver’s public key. Instead, the sender generates a random symmetric key, encrypts the message with that, and then encrypt the symmetric key with the receiver’s public key. The sender can then post the nostr event to the “public file system” by just concatenating those two ciphertexts, delimited by some symbol. How would a receiver know the message is for them though? Maybe the sender just tacks on the receiver’s public key in plaintext, so the receiver can easily scan for their messages.
This is pretty close to NIP-04. There are some in-the-math-weeds things I am glossing over. However, the only major difference is the symmetric key is generated with a Diffie-Hellman exchange (instead of the transport pattern), but the same goal is accomplished. So what are some weaknesses of this scheme? Going back to the “nostr relays are a public file system” analogy, these encrypted messages are going to be sitting around forever for anyone to read. If someone is able to at any point steal a receiver’s private key, they can decrypt all the NIP-04 messages to the receiver. There is no forward secrecy (a.k.a. backtracking resistance). This is a downside to performing the key exchange over the public channel.
More weaknesses become apparent when we poke some holes in the “public file system” analogy. The analogy covers up the issue that not all relays are trustworthy. If all we care about is getting a message out to the world, this isn’t a big deal since we just need one relay to work. But does that still apply to the private message use case? When the sender posts their private message to the receiver on relay X, the sender is revealing all sorts of metadata to the relay. Since nostr is based on WebSockets (an extension of HTTP) the sender’s IP address, and any other network-level metadata, is revealed to the relay. The relay now knows that the owner of this IP is communicating with the owner of the receiver’s public key. It is similar to a side-channel attack, the cryptography scheme isn’t being attack directly, but data is leaking due to the underlying infrastructure the scheme is running on. The relay can’t decrypt the ciphertext, but the metadata can still be used to triangulate users. For example, a relay might also have information on when an IP address is communicating with a bitcoin node and could start to deduce the subject of the ciphertext.
So NIP-04 leaves a bit to be desired from a privacy perspective. Are there possible improvements?
NIP-17
NIP-17 is the followup to NIP-04. It composes two other NIPs, NIP-44 and NIP-59 which are kinda like cryptographic building blocks for nostr protocols.
NIP-44 defines a hardened encryption scheme. A user wants to send an encrypted payload to another user, which there are many ways to accomplish. How do they agree on things like key exchange and ciphers? The NIP defines a message format which includes a version field which sets the protocol. Version 2 uses a lot of the same cryptography as bitcoin’s BIP-324 which is great to keep dependencies to a minimum. And this is nice, and totally necessary, but doesn’t address the network privacy issues of NIP-04.
NIP-59 is where things get a little weird trying to plug some of the metadata leaks. The technique used is called a gift wrap. The gift wrapping makes it much more difficult for users to analyze the publicly stored messages. It accomplishes this with two wrappers of encryption.
+-------------------+
| Gift Wrap |
| +---------------+ |
| | Seal | |
| | +-----------+ | |
| | | Rumor | | |
| | +-----------+ | |
| +---------------+ |
+-------------------+
A gift wrap’d message.
At the kernel is the rumor which is the message, but it does not include a signature. The signature is generally a requirement for any nostr event to be accepted by a relay. In this case, the rumor is a payload to another event and the metadata is being broken up. Now if the rumor leaks somehow there is plausible deniability where it came from.
The seal (kind 13) contains the encrypted rumor as content and is signed with the signer’s pubkey. There is no other metadata on the seal event beyond the sender. If it leaks, that is the only information available since the contents is encrypted.
Finally, the gift wrap contains the encrypted seal and is tagged with the receiver’s pubkey so they know the event is for them. The gift wrap is signed with a random pubkey so only the receiver’s key is revealed. The receiver has to decrypt the seal to find out who the message is from. From the public’s perspective, it is now very hard to connect all these layers.
Again, all very cool. But again, the wrapping does not address the network-level leaks that relays see when the events are posted.
NIP-17 ties 44 and 59 together further defining which keys are used where and what not. NIP-17 does mention using private relays to increase privacy. One could try and only post private messages to trusted private relays. So to fully mitigate network metadata leak attacks the channel needs to be trusted and that is not super satisfying.
NIP-104
NIP-104 is another proposal for private messages based on Signal’s Double Ratchet scheme. It is pretty complicated, but one of the main takeaways is better forward secrecy at the expense of not being able to read message on different clients (which is kinda weird in nostr-land where that is a common feature). However, the scheme still does not address the network metadata leaks when a sender first posts to a relay.
Store and Forward
So initially, nostr’s “forever public file system” seems like a great medium for any sort of store-and-forward communication (maybe better described with a slight variation, “store and pull”). It allows clients to be dead-simple since they don’t have to be online to communicate with peers and the storage protocol is set and ready to go. As we see with NIP-04, NIP-17, and NIP-104, layering in privacy at this point is easier said than done. Are we able to accomplish extreme privacy for the use cases which require it?
The main leak which none of the current proposals address is the side-channel-esque network metadata relays receive when a client posts an event. It is very difficult to hide “this IP is talking to this public key owner” while still making it possible for the public key owner to know someone is trying to reach them! One popular suggestion for users is to use a private relay which they trust. At that point, maybe there is other tech better suited for the use case?
Oblivious HTTP
Oblivious HTTP (OHTTP) is a very simple protocol to separate the client metadata from a request. A nostr relay gets the client metadata and any part of the event that is in plaintext. An OHTTP relay only gets the client metadata, the entire request is encrypted. The tradeoff is that the client is trusting the OHTTP relay to forward along the request to its destination. And obviously not collude with the destination by sharing the client metadata associated with the request. There is a layer of overhead here since both the client and the destination need to understand the OHTTP protocol, but similar to nostr, it is simple.
The economics of running OHTTP relays may be better in certain scenarios than private and/or public nostr relays. It is an apples to oranges comparison, but maybe there is an incentive for nostr relay runners to integrate with an OHTTP layer?
This work is marked with
CC0 1.0
