[Cryptography] Anonymous rendezvous (was Business opportunities in crypto)

[Christian Huitema]

On 4/15/2021 4:58 PM, Jerry Leichter wrote:
>>>>> Anonymous rendezvous is a vexing problem.
>>>> When you put it that way, it sounds pretty impossible.
>>> Sounds pretty much reducible to PSSK.
>> Excuse my ignorance, but can you spell out PSSK?
> I believe he was referring to Pre-Shared Secret Key, though we usually just use PSK.
You can indeed do private messages with PSK, but using Public keys is 
easier to manage. If the PSK is shared by a group, that's very fragile 
because anyone in the group can impersonate anyone else. Pair-wise PSK 
is more robust but then requires pair-wise settings.
>
>> Anonymous rendezvous is not entirely impossible. During the discussion 
in the DNSSD working group, we saw one plausible proposal. Assume that each of the parties has a public/private key pair, that authorized peers know the public key of the party with which they want to rendezvous, and that this public key is otherwise kept hidden from third parties. In short, 
the public key is treated as a shared secret between parties authorized to discover the owner of the key pair....
> Talking about the cryptography hides the fundamental underlying problem:  If Alice wants to establish a secure connection to Bob, she needs to know *something* about Bob that lets her identify him.  If "Bob" is just a 
three-character sequence to Alice and she knows absolutely nothing else about him, Mallory walking up to her and saying "Hi, I'm Bob" cannot, even 
in principle, be distinguished from one from Bob walking up to here and saying exactly the same thing.  And further, if everything that Alice knows about Bob is also known to Mallory, the same applies (and certainly if everything about Bob is public).
>
> Much of the discussion about asymmetric cryptography fails to consider this.  Sure, if Bob has a public key that Alice knows, she can send him a 
message only he an apply to.  But that just pushes the problem back a level:  How did Alice know that the public key corresponds to the "Bob" that 
she wishes to talk to, if she knows nothing at all about Bob to begin with?

In practice, many scenarios allow for an initial setup in a "private" 
environment. For example, one important scenario has coworkers traveling 
together and connecting their laptops to jointly work on a presentation 
while waiting for a plane -- they may have established credentials 
before moving to a public network. Another scenario has devices part of 
a "personal area network", e.g., your watch talking to your cell-phone. 
You don't want the devices to broadcast identifying data, but it is 
plausible to have them join the local network in your own home, before 
using them in a public area.

> At some point, Alice needs either to (a) have access to secret information shared only by her and Bob; or (b) trust some third party who already 
knows who the "right" Bob is and who can give her appropriate identifying 
information (Bob's known-correct public key; or a Kerberos-style secret that the third party hands to her and Bob).  And how did that third party get to know which the right "Bob" is?  We haven't actually solved the problem, just pushed it around.
The key is to push the problem in time, so credentials can be installed 
safely before moving to a public place. If that's not possible, the 
problem does indeed become much harder.
> There is a real-world alternative which actually ends up just reducing to this:  The classic spy trope in which a dollar bill is ripped in half, 
with a half going to each participant.  You can view this as like a Kerberos ticket (with the implicit assumption that a torn half of a dollar bill can't be accurately duplicated, which works for a physical object but for a set of bits which can always be duplicated you need secrecy); or by saying that Alice doesn't really know that she has a connection to "the right Bob"; what she can really say is that she has a connection to "the holder of the other half of of this dollar bill."  Binding that notion of identity to "Bob" requires another step - typically by the third party who gave the bills to them.

If Bob and Alice can receive halves of a dollar bill before hand, they 
might probably be able to receive some kind of keys...

-- Christian Huitema

>