[messaging] Memento, decentralised password-to-key method with brute forcing controls

[Natanael]

Den 17 okt 2014 15:32 skrev "Mike Hearn" <mike at plan99.net>:
>
> Online anti brute forcing systems are crucial to making passwords work
well enough for mass usability. I worked on the Google anti brute forcing
system and appreciate how important it was for keeping users secure.
Additionally, anti brute forcing is naturally extended to heuristic
anti-hacking techniques. I think e2e crypto has to ultimately present the
familiar username/password paradigm to users to achieve acceptance. But
intuitively it seems that this can't be done in an end to end secure way.
>
> The recent paper "Memento: How to Reconstruct your Secrets from a Single
Password in a Hostile Environment" by IBM Research (Camenisch,
Lehmann, Lysyanskaya and Neven):
>
>    https://eprint.iacr.org/2014/429
>
> is therefore very interesting and relevant to this list.
>
> It has the following features:
> Can be used to store cryptographic secrets "in the cloud" (across an
n-of-m threshold of dedicated password servers) such that some of the
servers can be malicious or compromised, yet the system remains secure.
> Password servers can/should apply online brute forcing protections.
> Even if the user is somehow tricked into trying to authenticate with a
set of fully malicious servers, the secret is still safe.
> All the user needs to remember for this protocol to work is the username
and password, and at least one of the servers in the group. This
requirement is easy and fulfilled by all users who have email addresses.
> Practical and should have usable performance even on mobile. Does not
require any unusually intensive calculations.
> The core idea is to use a form of thresholded homomorphic ElGamal, in
which the core secret (i.e. private key for decrypting messages or cloud
documents) is split into shares and distributed amongst a group of password
servers. These are not Shamir secret shares, rather they are ciphertext
shares. The protocol is such that the servers can check if the password is
correct without knowing what the password is, and without obtaining
anything useful in an offline brute force attack (specifically they learn
if the real password divided by the attempted password = 1 i.e. they are
the same). If the password is correct they release their share, along with
the ciphertext of the core secret, and the user can then combine the shares
to decrypt the secret.
>
> Memento is quite complicated and I do not understand the underlying maths
well enough to give you a better summary. In particular to make it secure
in the fully malicious setting and not just honest-but-curious involves
zero knowledge proofs and other things. There is no implementation.
>
> We can imagine a practical implementation involving professionally run
password servers that exist in a variety of jurisdictions, making it hard
for a rogue government to successfully bypass the online anti brute forcing
and make offline brute forcing possible (short of a hack that affects every
node).

My instant idea to implement something resembling this (in user experience,
and partly in security model) is with Tahoe-LAFS (storage nodes never knows
anything but ciphertext, has deduplication as part of the system), with
either a standard password store or the GPG based variant Pass here:
http://www.passwordstore.org/ (stores each password in individual encrypted
files and may fit this model better)

One note: Tahoe-LAFS doesn't force a requirement of access to at least n of
m storage nodes. This might be considered a requirement to reliably enforce
rate limiting? I think you can control which storage nodes hold what,
however, so the client software could implement a threshold encryption
scheme resembling what momento uses. Maybe Tahoe-LAFS can implement that
natively in the future?

Then you can add the authentication scheme you mentioned from the paper in
order to be able get access to the storage nodes, allowing you to connect
your Tahoe-LAFS gateway to them and access and decrypt the passwords. Then
you get rate limiting too.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://moderncrypto.org/mail-archive/messaging/attachments/20141017/d67b67ed/attachment.html>