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

[Mike Hearn]

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).
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://moderncrypto.org/mail-archive/messaging/attachments/20141017/4dc14f1e/attachment.html>