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

[Natanael]

Den mån 10 maj 2021 22:31Christian Huitema <huitema at huitema.net> skrev:

>
> 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
>

Local radio communications and networked communications have properties
which differ a fair bit in relevant ways. Discussing both below in separate
sections. Also, will take a stab at the forward secrecy issue.

For something like Bluetooth where you're expected to be in physical range
to communicate (inherently limiting the signal/noise ratio and thus
reducing risk of message flooding by malicious parties), an effective
approach may be similar to what's been previously discussed where you just
attempt to decrypt all headers (may work well for something like a laptop).
Messages addressed to you would successfully decrypt.

However, this is going to be energy inefficient for low power devices.
Addressing
to an arbitrary public key without mutual setup and without revealing to
others who you are addressing inherently (I assume) require that the
recipient performs operations involving the private key for each incoming
message, which impose limits on efficiency. Enabling batch processing of
broadcast tags might be a viable optimization? If a low power device can
collect many broadcast tags and perform a sublinear number of private key
operations then this may be sufficient?

Another possibility is to establish pairwise TOTP-like seeds and temporary
tags for messages, using only symmetric crypto and simple comparators for
much more efficient filtering. However, the volume of tags scales linearly
with the number of entities which you are signaling intent to communicate
with, and requires communication in advance for setup.

Broadcasting a Bloom filter over your set of such tags may also work as a
bandwidth optimization, where the sender computes the current set of tags
for entities they want to connect to and test it against observed broadcast
filters from nearby potential recipients.

Note: forward secrecy may be implemented via a hash ratchet for the seed in
the TOTP-like tag scheme, but this doesn't address key compromise recovery.
Recovery would either require communication between the users to rekey, or
a scheme like FSPKE (forward secure public key encryption) which is capable
of 1-RTT key exchange and where the client devices at any point in time
holds only delegated time limited private sub-keys, not the root key
(recovering on epoch rollover). For examples of the latter, see
libforwardsec (does encryption) and KeyForge (does signatures).

For online networks, there has recently popped up some seemingly viable
options to achieve this (rendezvous with a known party without disclosing
your identity to external observers).

Both these two rely on filtering of messages, which can be delegated to a
party which do not hold the decryption key (thus can't read contents) and
which you could connect to anonymously;

Fuzzy tags, designed to efficiently filter which messages are intended for
a given recipient;
https://git.openprivacy.ca/openprivacy/niwl

Vetted encryption, designed to allow the recipient to control who can send
messages to them via a filter, specifically the OVE or AVE variant;
https://eprint.iacr.org/2020/1348

In both cases the node operating the filter is meant to not be able to
learn much more than some traffic patterns.

Niwl is intended to be suitable in fully distributed networks. Connect to
some node anonymously, ask them to filter messages they see for a while and
to send what matches your way.

Vetted encryption might not be as efficient in a broadcast network when the
volume of messages to filter is large, but it works similarly. OVE type
vetted encryption may be more suitable to an email or IM style model where
you tell the sender where to send messages, but you're still not tied to a
specific server here either as your public key is the identity.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://www.metzdowd.com/pipermail/cryptography/attachments/20210519/60d8ab3d/attachment.htm>