[messaging] Introduction secrets and "unlinkable rendezvous" protocols

[Trevor Perrin]

Hi Sven,

There's some requirements here you missed:

 * Alice and Bob need to exchange a few hundred bytes of information
(some secret) before they can use regular Pond / Petmail
communications.  Verifying each other's public-key fingerprints is not
sufficient.  If it was, the parties would simply do *that* during
their physical meeting, and wouldn't need the rendezvous protocol.

 * The rendezvous protocol needs to be "unlinkable", i.e. it should
not reveal to a network observer that Alice and Bob are communicating.
 Thus, any attempt to use a PAKE or Socialist Millionaire-type
protocol is complicated by the fact that the parties must secretly
"rendezvous" at an address to speak to each other.  If that rendezvous
address is a function of the secret, then offline and online guessing
attacks against the rendezvous address could be used to recover the
secret, undermining the value of PAKE or SMP.


Trevor


On Tue, Feb 11, 2014 at 6:29 PM, Sven Moritz Hallberg <sm at khjk.org> wrote:
> On Tue, 11 Feb 2014 12:05:09 -0800, Trevor Perrin <trevp at trevp.net> wrote:
>> So now the bootstrapping problem has been reduced to exchanging an
>> "introduction secret".
>>
>> How much entropy does the introduction secret need? [...]
>>
>> It would be great if we could make low-entropy passwords work here,
>> but it's not obvious that this can be safely done.
>
> I've entertained the idea of combining SMP with the diceware word list
> (7776 words, ~12.9 bits).
>
> Assume Alice and Bob have exchanged keys through an insecure channel and
> need to verify their fingerprints.
>
> Alice picks two random words from the list and writes them on the back
> of a business card. She hands the card to Bob at their next meeting.
>
> Many such cards can be prepared in advance; Alice remembers the list of
> word pairs where the first word serves as an index (must be unique).
>
> When Bob gets to his computer, he initiates SMP fingerprint verification
> with Alice as in OTR, using the first word as the "question" and the
> second as the secret. He doesn't need to know the details of this; his
> client can simply present an interface to enter the two magic words from
> Alice.
>
> Alice in turn doesn't need to remember whom she gave which card to, her
> client can look up the right secret in the table.
>
> Only one party needs to bring their card to the meeting.
>
> Since SMP is zero-knowledge, an attacker must perform an online attack
> and can only derive from each try whether his guess was correct or not.
>
> Brute force attacks (apart from being easy to detect) should be avoided
> by restricting the number and frequency of SMP attempts. (Also, don't
> reject SMP attempts on unused indices, just let the protocol fail at the
> end, i.e. don't leak which indices are valid.)
>
> The above assumes Alice and Bob being online at the same time. However,
> the protocol could be run via an intermediary if Alice trusts the
> third party to fairly handle brute force / denial of service situations.
>
>
> Cheers,
> SMH
> _______________________________________________
> Messaging mailing list
> Messaging at moderncrypto.org
> https://moderncrypto.org/mailman/listinfo/messaging