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

[Jerry Leichter]

>> 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.
What matters is not that they *met* - in private or otherwise.  If they met but didn't exchange any non-public or at least non-replicable information (e.g., we assume no "Mission-Impossible" perfect masks, in which case Alice can recognize Bob by his face) then they are no better off after the meeting than before.  And there's also an subtle difference here:  The assurance that Alice is getting here is "I'm talking to the guy who at met last week who said his name was Bob and that he was the president of CryptoCorp" - but not "I'm talking to the president of CryptoCorp."

Look, we all know how this kind of thing works in practice; we've done it forever, without any cryptography.  The reason I bring this up is the long-standing false claim that public-key cryptography allows two parties who've never interacted previously to talk securely to each other, without any other parties being involved.  But it doesn't work like that - it *can't* work like that - in any meaningful sense.

Sure, you can use DH key agreement to set up a secure discussion ... but absent some additional mechanism, you can make no assertions about *who* you had that secure conversation with.  Full asymmetric cryptography, in and of itself, gives you no more than that.  The original claim was that I could shop in safety because I knew for sure that I was setting up a private connection to Macy's, having never before contacted them.  Except I can only make that assertion to the degree that (a) I trust CA who signed the key not to lie to me; and (b) I trust that the CA *has some additional data to prove to it that the public key it thinks belongs to Macy's does, indeed, belong to Macy's.  *Both* of these bits of trust have proven misplaced in the past, and certainly will be again in the future.

This is an induction.  Having *even once* been a position to exchange information privately with "the real Bob," directly or through third parties, Alice can use that information to communicate securely with that same Bob in the future.  n -> n+1.  But you also need the base case, that first secure connection - and *that* requires something different than the inductive step.

                                                        -- Jerry