Address private set intersection exploit

[sgwilym]

What's the problem you want solved?

When two peer sync, they send each other a DISCLOSE message:

/** An event for disclosing which shares a Peer has without actually revealing them. Another peer can use the salt to hash their own shares' addresses and see if they match. */
export type SyncerDiscloseEvent = {
  kind: "DISCLOSE";
  syncerId: string;
  salt: string;
  shares: string[];
  formats: string[];
  canRespond: boolean;
};

While this does not reveal the share addresses, it seems like there's a way for a malicious peer to trick a peer into thinking they both have the same shares: simply mirroring the honest peer's disclose message back at them.

The honest peer would then assume the other peer has all the same shares in common, and would proceed to send sync messages potentially containing share addresses to the malicious peer.

This problem domain is called private set intersection.

Is there a solution you'd like to recommend?

• ~We could make it so that if a peer receives a DISCLOSE message with the same salt as it sent itself, it'd be enough reason to suspect funny business and disconnect.~
  • But a malicious peer could simply harvest some hashes + salts from failed attempts, and then send them back on subsequent sync attempts, getting around the check and tricking the honest peer into sending sync messages.
• ~Peers could start sync by sending each other the salt they have to use when hashing their shares. Then the probability of the other peer having a hash using that specific salt is very low.~
  • The malicious peer could wait for the other side's salt, and just send it back.
• We could use public key encryption. Alice and Bob send each other public keys (generated just for this sync session) for encrypting with. Alice and Bob generate a salt, encrypt that salt with the other's public key, and send it to each other. Each side expects the other to send a list of their shares hashed with the salt they provided.

[sgwilym]

Additionally, we should probably not have share addresses in sync messages. Rather we should refer to the shares by the salted hash that was sent at the beginning of sync. But that is a breaking change.

[AljoschaMeyer]

The canonic solution for rather small sets is Huberman, Bernardo A., Matt Franklin, and Tad Hogg. "Enhancing privacy and trust in electronic communities." Proceedings of the 1st ACM conference on Electronic commerce. 1999.; for a very succinct summary see here, for a more accessible summary see here. Before using or implementing, ask someone who actually knows their crypto, i.e., not me.

For a fairly recent and accessible, high-level introduction to private set intersection, see this presentation.