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

[Christian Huitema]

On 5/10/2021 12:23 AM, jrzx wrote:
> On Saturday, May 8, 2021 6:43 PM, Christian Huitema
> <huitema at huitema.net> wrote:
>> The initial problem that I had in mind is probably better
>> called something like "discrete handshake". The typical
>> scenario involve parties that know each and have exchanged
>> credentials beforehand, like employees of the same company
>> or devices belonging to the same owner.
>>
>> The problem is to establish a network connection without
>> divulging their identities and presence to outside
>> observers. For example, in the two employees scenario, their
>> laptops discover each other by broadcasting messages over
>> WiFi or Bluetooth, but these messages do not reveal to
>> observers identifying information like static MAC
>> Addresses, IP addresses or public key values.
> Easy:  Ann broadcasts a message that only Bob can decrypt.
> Bob attempts to decrypt all incoming messages.  If he
> succeeds, then the message from Ann will say "Hi Bob, this
> is Ann, and my current network address is such and such."

Yes indeed. All the proposed solutions do something like that. But there 
are to problems: scaling, and robustness.

Scaling is obvious: Bob doesn't know if the message comes from Alice, or 
Carol, or any of Bob's friends, or someone else entirely. Suppose that 
there are a large number of parties trying to discover each other. The 
number of messages on the broadcast channel will increase with the 
number of parties attempting to discover each other, not to mention 
adversaries injecting noise in the process. And Bob will have to try 
decrypt all these messages. Without some careful design, Bob's phone 
might run out of battery.

Let's assume that the design prevents replay attacks and other such 
gross failures. The next worry is a variation of forward secrecy. If 
adversaries manage to break into Alice's phone, can they impersonate 
Alice? Can they discover Bob and all of Alice's other friends? For how 
long? How is the attack discovered or cured?


>
> Bob then narrowcasts an encrypted message to Ann
> "Hi, this is Bob, and my current network address is
> so and so."
>
> Assume Ann knows Bob's public key, and Bob knows Ann's
> public key, but their network addresses are likely to
> randomly change
>
> They want each other to know each other's network addresses,
> but do not want the whole wide world to know each other's
> network addresses.
>
> So Ann generates a random single use scalar r, and generates
> the corresponding elliptic point R=r*G
>
> Bob's public key is B=b*G, where only Bob knows b.
>
> So Ann broadcasts a message containing R in the clear,
> followed by encrypted data encrypted using the secret value
> r*B
>
> For every incoming message, Bob tries to decrypt the encrypted
> part using the value b*X, where X is the elliptic point at the
> start of the message.
>
>
> If the message is intended for him
> b*X = x*B, because both are equal to b*x*G.
>
> When Bob replies, he similarly constructs a message that only
> Ann can decrypt.

Yes of course. But at that point Bob does not know that the message 
comes from Alice. What if the message was sent by an adversary that 
somehow acquired a copy of Bob's public key? That adversary may not be 
able to decrypt Bob's response which is intended for Alice, but they can 
notice that Bob is sending a message, thus "discover Bob", and track his 
movements.

One way to protect against that is to include a signature that Bob can 
verify using Alice's public key. With that Bob can verify that the 
message comes from an authorized party, and can also silently discard 
the random messages from the adversaries. That means two public key 
operations per message. It increases scaling issues by a factor 2, but 
that's probably OK.

Basing the design on public keys is indeed more robust that trying to 
use shared secrets. But if the private keys of Alice leaks, the 
adversaries can impersonate Alice and actively track all of Alice's 
friends. More concerning, if the private key of Bob leaks, the 
adversaries can go back to their recording of the message on the 
broadcast channel and identify all past attempts to discover Bob. Which 
may be a serious forward secrecy issue.

-- Christian Huitema