[messaging] Passphrase-based key mobility (was: Peerio)

Natanael natanael.l at gmail.com
Sun Mar 1 12:18:19 PST 2015

Den 1 mar 2015 17:51 skrev "Trevor Perrin" <trevp at trevp.net>:
> On Sat, Feb 28, 2015 at 11:24 PM, Michael Hamburg <mike at shiftleft.org>
> > Perhaps you should use oblivious function evaluation with a
> > secret at the server.  So for example, server has a per-user secret key
> > and user has a (salted, scrypted) password p.  Let h = hash(p) on some
> > curve.
> >
> > client chooses a uniformly random scalar r.
> > client -> server: Q = h^r
> > server -> client: P = Q^e = h^er
> > client computers P^1/r = h^e, and uses the hash of that point as part
of the
> > secret key derivation.
> The server can still attempt offline cracking of the user's password
> though.  So I don't think this is better than just storing a
> passphrase-encrypted private key on the user's server, and delivering
> that to the user once they log in with the passphrase (using PAKE or
> some challenge-response protocol).
> So my claims are:
>  a) If you want passphrase-based mobility between devices, in a
> protocol where the user has a home server, just storing the
> passphrase-encrypted private key on the home server is the best
> approach.
>  b) It's unclear in what use cases this is a good idea - I think
> multidevice or new device cases are better handled by device pairing
> (e.g. short-auth strings between two devices).  Maybe passphrase-based
> mobility is desirable for users who roam between Internet cafes
> without a flash drive, or for backup purposes, but at best this seems
> like an optional, opt-in feature for unusual users, not something that
> should be a default for a widely-used system.
> Trevor

First I'd like to note that my preference is a small physical token, like a
Yubikey NEO with U2F, Bitcoin Trezor, USB Armory, or similar. This would be
used with a set of passwords, with different difficulty based on what it is
to be used for. PIN for the simple stuff, long password for the sensitive

However, for this particular software only scheme - couldn't you easily
make it a threshold scheme with multiple servers?

(Similar things have been discussed on the Tahoe-LAFS mailing list
regarding requiring multiple servers collaborating a while ago, FYI, there
might be relevant ideas in their archive.)

Require for example 2 of 3 to be online and respond, so at least two
servers of your three chosen ones needs to collude (or otherwise be
accessible by the same entity) in order to be able to bruteforce your seed
/ private key. The user could choose his set of servers and his threshold,
and with an n-of-m scheme you're protected as long as less than n have been
compromised by the same attacker.

There would still be some risk of bruteforce if a malicious server
precomputes possible derived keys with likely passwords (dictionary attack)
and then attempts to attack other servers to regenerate the other derived
keys, so that it can generate enough shares for the threshold key. Full
bruteforce is only practical for the attacker if he can extract the server
side user key databases from enough servers and run all the key derivations
simultaneously. Otherwise rate limiting by honest servers would add
effective protection for the user.

Is there any good and efficient method that even (practically, with
reasonable computational limits) blocks precomputation by malicious servers
outright, requiring simultaneous access to the server's key derivation
databases? Maybe group key derivation would work? If so, you could set it
up such that you would block precomputation when the attacker is attempting
to run a dictionary attack against the honest servers. For example, hashing
committed nonces from all the servers and using that as part of the group
key derivation means the attack must be almost 100% online if the attacker
has <n servers compromised.

A partial protection mechanism might be to not let the server know which
private keys on each server which he attacks belongs to the same person, so
even if he gets n-of-m he needs to know your configuration or face a really
really difficult combinatorial problem. With 100k users on each server he's
got 100k ^ 3 combinations to try in order to target all of the subset of
users that use 3-of-m with those servers. But how do you do this? Unique
usernames per server?

How would you guys design this algorithm to ensure the attacker can't
easily distinguish and identify user data across servers? Having plaintext
usernames in the database would reveal which is which if the same username
is used everywhere. Can't just do KDF either for a user identifier based on
the password and server public keys, as that allows direct bruteforce
without involving the servers and undoes the whole benefit of the scheme.
Assume the real user connects via Tor or I2P or similar for network
anonymity (attacker logging who's connecting from the same place fails).

By the way, if you want user account data stored on the server then keep
this disconnected from the multiparty key derivation, let the user log in
to the service with challenge-response using the derived key.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://moderncrypto.org/mail-archive/messaging/attachments/20150301/77a515ff/attachment.html>

More information about the Messaging mailing list