NIP 04 - block cipher mode, padding, shared secret

[AdamISZ]

AES-CBC is kind of old tech and frowned upon nowadays, but I totally get that it fits pre existing software and libraries (if you care, you can read about a typical objection to using it, and my counterpoints, in the comment thread to the SNICKER gist).

However I feel like you should at least specify the padding scheme used, because implementations need to do it, and what's much much worse: I saw, a few years ago when I was paying attention to such things, at least 2 libraries that implemented PKCS7 wrong. The implications of that will just depend (it usually won't matter, except if two different libraries are using different algos and encrypt/decrypt just fails, but then you can easily figure that out).

Technically PKCS7 is not the only padding algo possible here, but it is by far the most used in that context I think.

A separate question is why you don't hash the pubkey? I'd have to double check whether the reason that's done is largely academic (namely: you don't have pure uniform randomness over the 32 bit range in the key, but in secp it's close enough that it doesn't matter, unless I missed something), but I'm curious if you had an actual reason to choose not to do it, as afaik standards for DH/ECDH always do that(? maybe?).

[ghost]

Another thing i'd like to throw in here is the fact that the raw generated shared secret is used as encryption key for AES. Why not derive a more-random key from it using HKDF (or something alike)? This makes sure there is no more structure in the secret

[ghost]

and yeah, why not AES-AEX or maybe even ChaCha20Poly1305 (XChaCha if you'd like to go even further)

[AdamISZ]

Another thing i'd like to throw in here is the fact that the raw generated shared secret is used as encryption key for AES.

That was my last paragraph, but you were a lot more explicit, which is always good :)

[AdamISZ]

And the more I think about not using a KDF, the more dangerous it feels (thinking about the fact that you're exposing the underlying homomorphism, or to put it less pretentiously, what happens if you are for some reason using related keys, in multiple sessions. I don't know but it's concerning.)

[fiatjaf]

AES-CBC is kind of old tech and frowned upon nowadays

I didn't know. My brief research before writing the spec showed that it was ok and didn't have any vulnerabilities, and it seemed simple enough. But I didn't care very much because I thought NIP-06 would be just a prototype and that someone would come up with a better idea later. I am not convinced Nostr should even have direct messages yet, to be honest, I think it would work better as a way for people to discover each other's better DM methods using other protocols.

A separate question is why you don't hash the pubkey?

I didn't look at any standards when writing it, I just did what felt ok (because, again, it was supposed to be just a prototype and because Ben Arc wanted it so badly). Then later when I learned it was common to hash the point I asked Stepan Snigiriev (I mean I just casually asked, please don't hold him accountable for this) if he saw something wrong with not hashing it, I believe he said it was ok, so I didn't worry anymore.

[AdamISZ]

Right, this all makes sense. (Btw did you mean NIP 6 or NIP 4 there?).

Has anyone implemented it yet? At this point I'm just curious, don't feel the need to give detailed accounting of what has or will happen here :) I ask because if not, why not just change it to a SHA2 hash of the point? It is after all much cheaper than the preceding EC mult operation.

A quick search throws up something much more sophisticated, but along the lines of my "mulling about related keys" above:

https://crypto.stackexchange.com/a/67609/14985

This kinda makes sense, if an adversary can use you as an "oracle", by pinging tons of keys at you to do ECDH with, then over time they can learn about your key, because you're doing algebraic operations and seeing the output. (see the description of "Cheon's attack" above). Hashing destroys that algebraic relationship.

[fiatjaf]

Oh, it has been implemented many times in many clients, perhaps 10.

I don't want to be the guy pushing everybody to change, I don't know if it makes sense to change, it is probably better to write a new standard completely different and then people can slowly switch while supporting both.

But I was thinking of actually making a different protocol just for private encrypted messages that lived outside Nostr. Something that used the same Nostr principles of having somewhat dumb servers relaying stuff over WebSockets in an open and interoperable way -- but also such that metadata couldn't be leaked and there was forward-secrecy, good practices etc.

I am not qualified to invent this protocol, but I think a "nostr-like" model could be successful here -- and then it could integrate seamlessly in existing Nostr clients, using the same base keypairs and so on. What do you think? Can this be done?

[ghost]

A new protocol over Nostr (or a protocol like Nostr) just for encryption seems like a nice idea, then we aren't bound by NIPs either. But i do wonder how that's going to be implemented

[johnalanwoods]

AES in CBC is vulnerable to ciphertext malleability ofc, and even when one tacks on a MAC it still has problems.

Suggest a move to AES in GCM, or ChaCha20-Poly1305.

One could also consider that for a project that is focused on censorship resistance hiding the curve points during ECDH could be extremely valuable. Techniques like Elligation exist, though on Weierstrass curves (given the nod to Bitcoin) there are options too.

Finally appreciate this is a protocol specification and not an implementation, but with cryptography mistakes will be made unless explicit guidance is provided (such as using a HKDF on the x coordinate after ECDH).

In their current form encrypted DM's aren't strong enough.

[fiatjaf]

@iloveyumyumshrimpnoodles @johnalanwoods do you think it is possible to design a protocol that allows users to store data (private messages) in servers without the servers actually knowing, but these servers can still identify these users somehow and can still serve the correct data (private messages) to the target user when that target users asks?

It's important for the servers to know that some specific user is using them and not others so they can charge money or restrict access as desired -- but it's not desirable that the servers learn a lot of metadata about the messages being sent and received.

How would you do this?

[ghost]

It shouldn't be too hard i'd imagine. Here's an example of how i'd do it:

• Alice has keypair KP1, which consist of PUBKEY1 and PRIVKEY1
• Bob has keypair KP2, which consts of PUBKEY2 and PRIVKEY1
• Alice sends Bob PUBKEY1, and Bob sends Alice PUBKEY2
• They exchange secrets (using Elliptic Curve cryptography), and then use a key derivation such as HKDF (the python cryptography module has an easy to use function for that)
• Now, they have a secret key which is used to encrypt the message, which only Alice and Bob can read

For the symmetric encryption algorithms, here's what i'd pick:

• Chacha20Poly1305 (or XChaCha)
• AES-GCM

Another thing we should look in is deniable encryption, perfect forward secrecy and metadata.
As the Ex-NSA chief Michael Hayden said: they kill people based on metadata.
If the ciphertext's encryption cant be broken, the metadata is still useful.
For example; currently the encrypted dm's still leak data about who sent the dm and who received it.
This is enough to kill a person like Edwards Snowden (say, he gets a message from a whisteblower with a known public key, they will know he got a message from that public key).

Sorry if my rants don't make much sense, i just woke up :3

[ghost]

i don't think Nostr (in a publish-retrieve) sense would work well with this, so we should build a new protocol over websockets aswell.

[ghost]

ANOTHER thing i'd like to throw in here is the fact that Nostr (or atleast the python library, haven't checked others) uses a single keypair for both signing and key exchanges which is a bad practice

[johnalanwoods]

@fiatjaf - definitely possible, solution would depend on the detailed requirements, but something akin to Onion routing would work.

[ghost]

@fiatjaf - definitely possible, solution would depend on the detailed requirements, but something akin to Onion routing would work.

Onion routing seems interesting, but how would we implement this so it can be used with Nostr?

[fiatjaf]

Hm, so what about people use different keys for each message, but they use some form of zero-knowledge proof to prove they are allowed to use that relay?

Or maybe they can get some blind tokens from the relay -- either by buying or by any other process -- and then use those tokens every time they want to publish something?

[shafemtol]

Or maybe they can get some blind tokens from the relay -- either by buying or by any other process -- and then use those tokens every time they want to publish something?

Some sort of chaumian ecash token system would be great. In the simplest form all tokens have a single denomination. One could for example charge one token for every k bytes of storage, plus one token for every n current subscribers that an event would reach. Deleting an event could result in the tokens spent on storage being refunded.

However, I don't think one can assume that relays cannot identify most users by other means, such as by their IP address, IP TTL, TLS library, HTTP headers and client behavior. My impression is that current clients will happily connect to any relay they come across and proceed to reveal the user's pubkey. So any secure messaging system will have to be designed with this in mind.

[ghost]

WabiSabi is a ecash system with anonymous amounts, increasing the anonset to all users, the user can hold his entire balance in a single token without privacy downsides.

https://github.com/zkSNACKs/wabisabi
https://github.com/zkSNACKs/nwabisabi

[paulmillr]

Thoughts on using proof of work to combat spam?

[ghost]

I think it's a good idea, but then there's more questions:

• What algorithm will be used?
  • simple hashing algorithms can be abused by ASIC's (like SHA, biggest example)
  • too heavy means poor cross platform compatibility (phone vs high-end desktop seems a bit unfair)
  • too slow means users will be demotivated to post, because it takes too long
  • what about regular bots that post messages? they'll need to perform heavy work for simple posts (like a twitter mirror)
• Should the expected "nonce" be something that's hardcoded, or should it change with the scale of the network?
  and probably some more i can't think of from the top of my head

This issue goes more in-depth on this topic

[fiatjaf]

@shafemtol I am not talking about Nostr or current clients, but about a separate hypothetical system that is similar to Nostr but optimized for encrypted direct communication.

@paulmillr in a system like that the relays could sell trade proof-of-work for these tokens.

Some sort of chaumian ecash token system would be great.

I am not talking about "money" tokens, just usage tokens. I don't think you should call these ecash tokens. It's just a way to control access to the relay resources without requiring users to identify themselves explicitly.

[paulmillr]

@fiatjaf no tokens, no trust towards relays. Just publicly observable proof of work. Like bitcoin block sha256 hash with some amount of zeros.

[fiatjaf]

I don't understand how can you build such a system without some level of trust in relays, and why having tokens is bad. Also how can have publicly observable proof-of-work if we want to hide all the metadata?

Maybe if you explain better how the general system would look like in your mind. Are you talking about pure Nostr or a new, better, hypothetical system?

I believe proof-of-work in general does not work because there is no difficulty adjustment outside Bitcoin, so the proof-of-work may become meaningless as soon as one user has exponentially more hashing power than the other.

[fiatjaf]

I liked the tokens idea (even though I don't know if it makes sense), but they do not fix querying. There must be a way for the message sender to communicate to the receiver how to fetch the next messages from him.

Maybe whenever a message is sent it contains some random id, which the receiver can use to query the next messages.

Then, when creating the next messages the sender attaches that id somehow.

[metacatdud]

I was thinking about the same thing. If you strip all the metadata how will the relay know where to send the message?

One (dumb) idea can be to broadcast and all receivers can attemp to decode it but this obviosly will create massive traffic, so... no.

Another one worth trying/discussing is to use two set of keys one for the machine and one for the user. The message is send to the machine and machine key is used (for now) for routing purpose only, but if the correct receiver is using that machine only they can read the message.

As far as I understand we are trying to avoid p2p for obvious reasons of complexity and stability. So why not emulate that through relays with keys?

To put this into alice bob stanza.l:

1. Bob has a key pair
2. Alice has a key pair
3. Alice gives a public key to one of her computers to Bob, or many for that matter, they can also be public machines.
4. Bob sends a DM to machine's pub key
5. If Alice is in session on that machine can use the agreed upon ways to read the message, if not than it can be decieded later, store on that machine until Alice arrives? Machine query the relay for new message everytime a session starts?

What do I mean by machine pub key?
I mean a wrapper session of sorts that will open a communication channel with the relay.

Think iris or snort for example: instead of login you create a session (key pair). Then you communicate me that pubkey. I already have your personal pubkey for creating the cypher beforehand. I will write to you using that key, but I will send the message to the session key.

The machine/session key can still be used to validate signatures, integrity etc...

[metacatdud]

Than we can find a way to move the message from one machine to another.

1. Either I send you to a list of machines
2. The receiver re-encrypt the message and using same principle as above is syncing with other machines

[fyookball]

@metacatdud it's possible to grind a nonce and use that as a searchable prefix hiding in an anonymity set. This is an idea from reusable payment addresses. It's a trade off between privacy and scalability because you'll have to download more messages, but not all of them.

[ghost]

One (dumb) idea can be to broadcast and all receivers can attemp to decode it but this obviosly will create massive traffic, so... no.

BitMessage does this, it broadcasts encrypted messages over a p2p network and then only the actual receiver can decrypt the message.

This is not a bandwith friendly option, as for every message we'd have to send it to every peer imaginable and they would have to try and decrypt that message (also uses unnecessary processing power)

[metacatdud]

That's why I acknowledge it and discarded in the same phrase 😁
Broadcasting in whatever form can be pretty expensive.

[fiatjaf]

(I know I should probably understand more about current DM systems that do these things before I try come up with better ways, but I don't know when I'll be able to do that, so I'm throwing ideas here hoping that you cryptography experts will use some of them to design a good system.)

[mikedilger]

This topic has also been discussed twice before, although not as deeply as this thread. Thought I'd link the prior discussions:
#72
#107

[johnalanwoods]

You can do searches on ciphertext using homomorphic crypto systems like Paillier.

[paulmillr]

@shafemtol for separate messaging private key, we could make it deterministic: kdf(nostr-main-private-key, counter) could be used, the counter could be incremented whenener key rotation is necessary.

[shafemtol]

That would break forward secrecy. Compromise of the main private key would result in compromise of all (initial) messages.

[paulmillr]

Not necessarily. Initial messages for rotated keys could incorporate ephemeral secret in existing conversations.

[paulmillr]

Hey repo owners, could you convert this issue to "Discussion"? That would look better and could be more efficient. Maybe with title "Replacing NIP04 with better messaging system" or something.

[shafemtol]

I have written down my ideas on anonymous delivery here: Anonymous Delivery of Secret Events

In summary:

• I agree that, while as anonymous as one can get it, "send to all" does not scale well.
• The alternative I propose is rendezvous beacons:
  • These are very small events (only 4 to 16 bytes content) with some proof of work.
  • Each recipient publicly chooses to receive either all rendezvous beacons or a subset (1/16 proposed).
  • From the rendezvous beacon, recipient derives a secret rendezvous point which locates the actual message.
  • Users who have interacted publicly might set up implicit rendezvous points between them, no beacon needed. E.g., if your inbox is only open to those you follow, you won't need to subscribe to rendezvous beacons.
• To address sender (and maybe recipient) anonymity towards relays, I propose anonymous messengers:
  • Separate from the secret messaging standard, users/clients can choose to use them or not.
  • Built upon an ephemeral variant of rendezvous beacons and secret events.
  • Messengers listen to relays for secret (onion-encrypted) messages.
  • Messages to messengers contain within them an event and a destination relay.
  • Senders are anonymous to messengers and to the destination relay. First relay might identify sender, but cannot identify the message.

[shafemtol]

I've started a draft for the format of secret events: #306

This is meant to be used as the carrier for any kind of secret messaging as well as private storage in general (could be useful for storing certain state for the messaging protocol).

[fyookball]

reposting this comment I left on #107 for visibility:

I put together a quick POC based on the suggestions to use HKDF and aes-256-gcm.
https://github.com/Electron-Cash/Nostron/blob/nip04research/nip04research/EncryptedMessaging.py

Disclaimer: I'm not a cryptographer.

[paulmillr]

I have opened pull request for (allegedly) NIP-44 Encrypted Direct Message (Versioned): #574

It uses versioning, XChaCha20 and hashed shared secret. Algorithm choice rationale is described in the pull request. New Versioning feature explicitly requires non-compatible versions to throw user-visible errors.

Please take a look at it! Any comments are welcome.