[messaging] Introduction secrets and "unlinkable rendezvous" protocols

[Sven Moritz Hallberg]

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