Recently, I was asked to design a new authentication protocol for a web service. I know that I shouldn't do reinvent the wheel, so I immediatly proposed OAUTH. It turns out that it can't be used in this situation. Here are the constraints:
-calls to the webservice must be authenticated: I can keep the tokens and signature from OAUTH here. The problem is: how do I get that token?
-calls are made from devices or applications without access to a webbrowser (embedded devices, phones, etc.). The redirection dance of OAUTH is not acceptable here
-communications are done over an untrusted network, without SSL.
-I can't use application keys and secrets to encrypt and sign the authentication process: clients include open source software and smartphone applications. You can't hide a secret key in these.
-the protocol has to be simple to implement, on a lot of languages
-the server must not store the password in cleartext (I shouldn't have to precise this...), the client must not store the password
Summing it up: no preshared keys, no browser, no SSL, untrusted networks, no passwords stored, and an OAUTH-like environment once the client is authenticated (tokens, authorizations, revoking, etc)
Apparently, I should just give up. But I like to play, so I'll try!
First, I must say that I am not an expert in security nor cryptography. But I'm really enthusiastic about these subjects, and my day job is at a company providing strong authentication solutions (no, this protocol is not related to my day job). So, I know a bit about the subject, and I know that I should ask for reviews, hence this post.
Rough ideas
We need a safe communication over an untrusted network. TLS immediatly comes to mind, but the targeted applications might not have access to a TLS implementation. I'd like to use SRP, but I don't think I'm able to implement it correctly (and it has to be SIMPLE). Using Diffie-Hellman to establish a shared key is another idea, but it is not safe against MITM.
Here's my idea: we don't need to generate a shared secret, we already have it. It's the password!
But how can I use the password if the server doesn't store it in cleartext?
The trick: key derivation functions
Decveoplers are finally understanding that they should not use MD5 nor SHA1 to store their passwords, even with a salt, because computing power is so cheap these days that anyone could crack easily a lot of passwords.
It is now recommended to use other functrions tro store passwords. The key derivation functions are a class of functions that create a key from a password. Basically, they do it by interating a lot of times. That makes them very slow, which is an interesting property if you want to stpre passwords: it is too expensive to "crack" the password. PBKDF2, bcrypt and scrypt are well known key derivation functions. They're simple to use and available in a lot of languages.
With these functions, I can safely store the passwords, and generate a key shared with the client.
In short: if I store kdf(password, N) with N the number of iterations, I can send any M > N to the client and ask him to compute the key, without compromising what I store.
Designing the protocol
Now that we have a way to use a shared key, we can look at what will go over the wire to establish it. If I use directly kdf(pass, M), anybody getting access to the client storage will be able to obtain the key for any L > M. So, the key establishment has to use a nonce. That way, the client will only use the password once and forget it, and store the derivated key.
I would rather use a truly random key that has no relation with the password. It could be given to the client, encrypted with the derivated key. The derivated key could then be thrown away. But I still do not know if it is really necesary.
The server still needs to authenticate the client. The client will make a second call to the web service, signing it with HMAC and the key.
That's it! It is really simple, so if there are flaws I did not see, you will surely catch them.
TL; DR
The protocol is based on key derivation functions, like PBKDF or bcrypt.
- The server stores login and H = kdf(pass, N), with N integer
- The client wants to authenticate and makes a call to the server with the login as argument
- The server replies with M > N and i nonce
- The client calculates k1 = kdf(kdf(pass, M)+i, 1)
- The server calculates k2 = kdf(kdf(H, M-N)+i, 1)
- The client calls the server with args "user=login&sign=".HMAC("user=login", k2)
- If k1=k2. The signature matches and the client is authenticated.