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

[jrzx]

> On 5/10/2021 12:23 AM, jrzx wrote:
> > > 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."

On Monday, May 10, 2021 1:08 PM, Christian Huitema <huitema at huitema.net> wrote:
> Suppose that there are a large number of parties trying
> to discover each other.

It can scale a mighty long way.  These are one ninety six byte messages, and my phone burns a gigabyte a day just
sitting around unused.

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

If someone steals my phone, and it is unlocked, they can
impersonate me just fine already.

If your device controls a great deal of money, you deploy two
factor authentication.

So Bob receives a message from Ann that she is now at IP
so and so.  That is single factor authentication.  "Ann" now
tells him to transfer a bag full of money.  That is
another protocol, which is out of scope for this protocol,
and in that second protocol, he will probably demand
a second factor of authentication.

For *finding* one's counterparty, single factor
authentication is more than enough.

> > 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
> > bX = xB, because both are equal to bxG.
> > 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.

Alice could simply sign the encrypted message with her public key.

But this wastes 32 bytes, and gives Bob the ability to prove that
Alice was at network address so and so to third parties, which we
probably do not want since neither Alice nor Bob want their
network addresses widely known.

Thirty two bytes might well matter if one receives ten million
such messages a day.

So:

Alice's public key, A=a*G
Bob's public key B=b*G
Alice's single use key X=x*G
lower case letters are scalars,
upper case letters are elliptic points.

Alice encrypts the message "From this network Address" with
the shared secret (x+a)*B
Then she prefixes that encrypted message with A, and encrypts
the concatenation with x*B
Then she prefixes that doubly encrypted message with X, and
sends it to Bob.

Bob decrypts with b*X, sees the public key A, and the
encrypted network address, decrypts the network address
with b*(A+X)

Now Bob knows that only Ann could have sent the message, and Ann
knows that only Bob could read it - but Bob cannot prove to
anyone else that it could only have come from Ann.

When Bob replies to Ann, he will use another single use key Y=y*G,
and will then have perfect forward secrecy, full authentication,
and prevention of replay attacks with the shared symmetric key:
(b+y)*(A+X) = (a+x)*(B+Y)
Since all of these messages are forever indecipherable once
x and y are discarded.