Extending SRP's guarantees to validated registration

This post is about work done jointly with Michael Sanders and Jacob Hurwitz for 6.858 (One of MIT's Computer System's Security courses).

The Stanford Remote Password Protocol is a really amazing little piece of cryptography. Like almost every great crypto-system, it provides seemingly impossible guarantees. Namely, it allows a server to recognize a client without having any real usable information about them.

In most authentication systems, the server is at some point in time privy to sufficient information to impersonate the user: perhaps you send your password to Google, Microsoft, or Facebook, or perhaps you send a hash. Regardless, as some point in the process, the server sees enough information about your password to fake a login later. With SRP, this isn't the case. To quote the SRP website:

SRP is a secure password-based authentication and key-exchange protocol. It solves the problem of authenticating clients to servers securely, in cases where the user of the client software must memorize a small secret (like a password) and carries no other secret information, and where the server carries a verifier for each user, which allows it to authenticate the client but which, if compromised, would not allow the attacker to impersonate the client. In addition, SRP exchanges a cryptographically-strong secret as a byproduct of successful authentication, which enables the two parties to communicate securely.

 Still, there is a slight problem with SRP, if you're willing to crimp down your tinfoil hat a little.

As specified, SRP does not allow the server to check that a password is strong without violating it's own security principals. Sure, the server can push some javascript out to users to do the checking for them, but that has problems of its own:

1. A really malicious user might be able to bypass the checks by modifying the javascript.
2. A really paranoid / low-level user might disable javascript or insist on running their own code.
3. A really malicious / stupid server or other entity might take the opportunity to sneak some code into the password checking code that ruins guarantees by shipping code back serverside for checking.

It's also ambiguous what a "strong password" really is. In fact, many strong password requirements actually weaken the space of passwords users chose from, or at least doesn't really improve the situation. One way to specify the strength of a password by the Information-Theoretic Entropy of the process used to create it. This definition is nice in theory, and a good model of truly secure passwords: the best passwords are generated completely at random.

It's also super inconvenient to remember totally random passwords. I've actually got another post on exactly that coming up, so hang tight there and pretend that we actually do want totally random passwords.

The work myself and my group members did augmented SRP to handle ensuring that users pick totally random passwords without revealing those passwords in the process. The basic idea (exchanging DL commitments then revealing them to the user), is pretty simple, but it took us a little while to come up with and we couldn't find another instance of someone else doing the same thing in a practical manner. I'm perhaps unjustifiably proud of our work.

Our paper is hosted on the 6.858 website. It is also mirrored on github, where we keep our example code (full credit and awe to Jacob Hurwitz for putting together an excellent demo on a tight timetable).

That said, what we have done has its flaws. For one we introduce a partition attack into SRP, which we suggest resolving by rate limiting login attempts and increasing SRP's security parameter. We also require more client side computation than standard SRP, and that's computationally taxing enough that logins can take upwards of a second even largely ignoring network delays. Finally we have to introduce a few changes to SRP that make it harder to optimize on the server.

Without more auditing and investigation, I can't recommend our protocol for practical use, but I'd love to see it get some further analysis, because I think it presents a practical candidate solution to an interesting problem.