Tuesday, February 7, 2012

On SRP - some implementation notes and a critical review

Some time ago, Dan Kaminsky mentioned the Secure Remote Password protocol (SRP) on Twitter. As I find certificates to be cumbersome, I'm always interested in solutions to setup trusted communications without them.

Update: this post has been updated based on suggestions by SRP designer, Tom Wu!

SRP is surprisingly unknown for what it offers, so I decided to do a writeup here to help spread the word on what SRP is and isn't, how to implement and what the caveats are.

SRP was designed by Tom Wu while he was at Stanford University. Details can be found from the page linked above, and the Wikipedia page is also informative.

This writeup assumes familiarity with hashes and Diffie-Hellman, but not a lot else.

What is the problem that SRP solves?

To do anything important on the public Internet, we need secure communication channels. Stricter definitions are available, but the core of this is that we have secrecy (other people on the Internet can't listen in) and that we know who we are talking to (other people can't impersonate the endpoint we think we are talking to).

Often we use SSL, in the form of https, to deliver both. The SSL protocol negotiates a session with privacy, and through the use of X509 certificates, makes sure that we are talking to someone with a certificate that matches who we think we are talking to (what this means in the year 2012 is anybody's guess, though).

In addition, once we have setup this secure channel, most of the time we will then log in to a remote system (think gmail, for example). We do so by providing a username and a password.

And here's the interesting thing. The server has provided proof of its identity to us in a way that doesn't allow us to subsequently impersonate that server. However, as users, we are then asked to give that same server our full username and password! If we share passwords, this mean the operator of the server can now try to log in elsewhere with our credentials.

Enter SRP.

Zero knowledge proof of identity with key establishment

SRP rolls up most of the things above. As a user, we can prove to the other side that we are who we say we are (or at least, that we know the password we enrolled earlier). We never have to send the remote our password, not even when we are enrolling. Simultaneously, we get proof that the other side is one that we enrolled with in the past. Finally, we also get a secure session key to encrypt our communications.

And all this without certificates!

Compare this to SSH, where we first setup a secure connection, and then send our full password over that same session. Or CRAM-MD5, which allows us to prove who we are without sending over our password, but which does demand that the server have a plaintext copy of our credentials.

All pretty impressive.

Practical details

With our username, the server stores a 'verifier' of our credentials, plus the salt used to generate this verifier. As is usual, we deal with hashes of the password, and not the password itself. The verifier however is even further away from the password, and consists of the result of a one-way cryptographic operation on the hash.

Password + Salt  -> Hash -> Verifier

We never need to tell the server our password if we don't want to, we can just send them a random salt and the verifier (which we can calculate) when we enroll. Quite often though, we'll provide the password just once, though, and have the server calculate the salt thence hash & verifier.

When we want to setup a secure authenticated session, we connect to the server and tell it our username. In return, it reminds us of the salt used in generating the hash.

The user now enters the password on his own computer, which subsequently calculates the hash based on the salt. This hash constitutes our secret key. The verifier stored on the other side performs the role of a public key.

Next, a modified Diffie-Hellman key exchange is performed, based on the public and private keys derived from our password. If the server verifier is indeed related to our client hash, both parties will end up with a shared secret which, once hashed, forms our session key.

A final message exchange based on the shared session key is then performed, and if the session key is in fact identical on client and server, this will prove that the verifier and user password match.

And we are logged in, and have an authenticated secure shared key!

Downsides

There are a few downsides to the above. For one, we have to send out our username in plaintext at the very beginning of the session. An eavesdropper can derive from this who we are claiming to be.

Secondly, while the server is 100% assured we know the password associated with the username, we are in turn not 100% sure if we are connected to the right server. We only know we are connected to someone who has access to our username and password (knowing only the verifier is not enough).

The last bit basically means that if someone knows our username and password, he'd be able to impersonate the server you connect to, and transparently send everything on. But then again, if he knows your username and password, he could just log in as well.

If an attacker only knows the verifier, he can wait for a user to connect, and pretend to be the intended server. However, the attacker can't setup a transparent connection to the authentic server, so you'd have an authenticated connection to a server that does not have the contents of the original server.

Patent situation

Update: this section has been updated after further research. The previously mentioned patent is predated by the publication of SRP by a wide margin, so it does not apply.
Various sources mention that there might be a patent issue with SRP, but there is nothing concrete to point to. There is a Stanford patent, but it has been licensed in such a way that it does not hinder SRP usage in any way. It might in fact protect it.

When the SRP RFC was initially written, two firms made IPR disclosures, but these have not been followed up on. When RFC 5054 was published, which also describes SRP, there were no further IPR disclosures.

SRP has by now seen quite some use, if there were any applicable patents out there that were still valid, we would probably have heard from them already. If anyone knows of specific patents that apply, please let me know. It would be good to put this to rest.

The balance

SRP is pretty cool, and delivers quite a lot of 'bang for the buck'. It is way better than many other solutions, which either require plaintext passwords on the server, or require us to hand over our password to the server every time we log in.

In particular, it appears SRP should have been used in WPA2 instead of what was used.

However, SRP falls short of having 'real' authentication. If an attacker knows the password, he can effectively pretend to be the remote server. And even though an attacker with the correct password was pretty powerful already, this is a downside.

The usecase for SRP is therefore for people who'd like to have better security than just passing around passwords, but don't want to go through the hassle of doing certificate administration.

Potential improvements

If we could keep the salt a secret, it could function as a poor man's authenticator. The server does not need to know the salt, as long as it has the verifier. The salt itself could then be used as the 'public' key of the remote.

Implementation notes

The best place to start reading is the SRP Design Page. There is a also  paper which describes the math, but not the practicalities. RFC 5054 meanwhile describes how to do SRP within SSL/TLS, and Tom Wu suggests using that if possible. If you do SRP outside of SSL/TLS, it appears wise to follow the practicalities in of SRP-TLS (mostly related to padding) anyhow, for interoperability's sake.

2 comments:

  1. A good article, but I must correct one piece of information. US patent 7076656 cannot cover SRP because it is dated eight years after SRP was invented. The correct patent number for SRP is 6539479 and has been made freely available worldwide by Stanford.

    ReplyDelete
    Replies
    1. Hi Tom,

      Had a question on how to use SRP libraries that you authored some time ago..

      Delete