[messaging] Introduction secrets and "unlinkable rendezvous" protocols

[Robert Ransom]

On 2/18/14, Trevor Perrin <trevp at trevp.net> wrote:
> On Mon, Feb 17, 2014 at 11:56 PM, Brian Warner <warner at lothar.com> wrote:
>> On 2/15/14 4:50 PM, Trevor Perrin wrote:
>>
>>> During an offline meeting, users would exchange their long-term
>>> fingerprints. They would then enter the other party's fingerprint into
>>> their app, which would perform some pre-rendezvous steps:
>>>  - Retrieve the other party's introduction cert by querying one of the
>>>    mirrors.
>>
>> Would that require some sort of PIR protocol? Seems like the mirrors
>> could learn who's interested in whom at about the same time, and thus
>> deduce the connection.
>
> Hmm, good question.
>
> The directory would learn: "a Tor user is interested in Alice" and "a
> Tor user is interested in Bob".  These wouldn't be tightly correlated
> in time, as Alice and Bob might fire up their app at different times
> after the meeting.
>
> If the directory can also monitor users as they communicate with Tor
> entry nodes, it could attempt end-to-end timing correlation (But this
> is also true of a rendezvous server with meeting IDs, not just my
> proposal).
>
> Some possible defenses, not sure which are best:
>
> - Have all users occasionally send dummy lookups to the directory.

There is no such thing as ‘dummy traffic’.

>  - Eliminate the central directory and lookup a party's key at a
> directory of her choice.  So instead of just exchanging fingerprints,
> Alice and Bob exchange <fingerprint><@directory-name>, and choose
> directories who they trust not to do these things.

This reveals more information to an attacker passively observing the
directory server.

>  - Access the directory over a high-latency mix network, to break up
> the end-to-end timing correlation.

* Even a high-latency-variance anonymity system cannot guarantee that
there will be a large enough anonymity set to hide the Alice<->Bob
connection.

* If you believe that a low-latency anonymity system is adequate to
provide anonymity, then using a high-latency-variance anonymity system
is roughly equivalent to having the client wait for a random amount of
time, then send a message using a low-latency anonymity system.

* I don't trust users to not send low-latency messages, even if they
do use (a protocol equivalent to) a high-latency-variance anonymity
system.

PIR is a very good idea.


Robert Ransom