<div dir="ltr">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.<div><div><br></div><div>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):<div><br></div><div>   <a href="https://eprint.iacr.org/2014/429" target="_blank">https://eprint.iacr.org/2014/429</a><br></div><div><br></div><div>is therefore very interesting and relevant to this list.</div><div><br></div><div>It has the following features:</div><div><ul><li>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.</li><li>Password servers can/should apply online brute forcing protections. </li><li>Even if the user is somehow tricked into trying to authenticate with a set of fully malicious servers, the secret is still safe.</li><li>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.<br></li><li>Practical and should have usable performance even on mobile. Does not require any unusually intensive calculations.</li></ul></div></div><div>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.</div><div><br></div><div>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.</div></div><div><br></div><div>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).</div></div>