Safely discovering which workspaces you have in common with another peer (without disclosing the others)

[cinnamon-bun]

What's the problem you want solved?

Workspace addresses are supposed to be kept secret.

How can peers discover which workspaces they both have (so they can sync them), without disclosing the workspaces they don't have in common?

Example:
Peer1 has W1, W2
Peer2 has W2, W3.

They should discover they both have W2. Peer1 should not learn about W3. Peer2 should not learn about W1.

Is there a solution you'd like to recommend?

Share the hashes of the workspace addresses?

• Peer1 and Peer2 each generate a random nonce.
• Each peer hashes their workspaces with the nonces and shares them with each other: sha256(workspaceAddress + nonce1 + nonce2)

The hashes they have in common correspond to the workspaces they both have.

The hashes that are unique to one peer will reveal no information to the other peer.

A MitM won't learn the workspace addresses even if they know both of the nonces.

HTTP example

Alice: hey, here's a nonce, give me your workspace hashes.
--> GET /workspaceHashes?nonceA=foo

                Bob: ok, I made my own nonce too, here's the result
                <-- {
                  nonceA: "foo", nonceB: "bar",
                  workspaceHashes: [
                    // sha(workspace + nonceA + nonceB)
                    "bq49f8jq0o4f9jqf",
                    "b098ja0jhahahfa3",
                  ]
                }

Alice: now I can compute the same hashes from
my own workspace list, and now I know which
workspaces we have in common.

Security thoughts

The peers will learn the number of workspaces they each have. 🤷 They could add random fake entries to the list, but you could still collect a statistical sample and infer the real number.

The nonce prevents a replay attack by making the hashes specific to one particular sync session.

[cinnamon-bun]

Problem

The above protocol is safe against MitM, but once both peers know which workspaces they have in common they will start syncing them in plaintext with each other. At that point a MitM will observe the actual workspace address (and actual data).

An example attack is: "Hey everyone, use my cool pub https://totally-safe-pub.com. It definitely is not just a proxy that forwards your requests to an actual pub in order to learn the names of your workspaces!! Look it's https, very safe"

Solution

Right now when our peers talk, in general, they don't authenticate or know the identity of each other.

I think we need to do a secure key exchange like secret-handshake which identifies the peers to each other.

This means each peer needs to have a keypair.

For regular peers: I think it's ok for secret-handshake to re-use the same author keypair across multiple devices?

For pubs: we'll have to generate keypairs for them, and... trust on first use, or add them into the pub URL?

BTW, I don't want to start treating pubs as part of the human social graph like SSB does. Earthstar doesn't even have a social graph actually!

[cinnamon-bun]

Other solutions

Once we have these two...

• Access-controlled workspaces (invite-only) #7 Invite Only Workspaces (limited people can write to a workspace)
• Figure out: fully wrapped encrypted documents #11 or Add simple helper functions for encrypting & decrypting content #49 Encrypted Documents (limited people can decrypt/read)

...it won't matter as much if random people learn your workspace address.

In the long run that's probably a better and safer approach -- encrypt the actual data instead of just encrypting the transport using secret-handshake.

Also, to clarify: in the proposed algorithm, a MitM can only learn of the workspaces the two peers have in common, not the ones that are unique to one side.