Strengthening Security with PAKE Protocol

You know that guy who does a lot of work but just doesn’t get the attention he deserves? The PAKE Protocol is that guy.

PAKE – One of the most efficient cryptographic protocols ever drafted yet rarely gets used.

NOTE : Throughout this article, there might be words you have never heard of. I have tried explaining most of them in braces[] and in italics.

PAKE stands for Password Authenticated Key Exchange.

Let us consider a simple problem where there is a server which stores user passwords. The traditional way to do this is to hash [A cryptographic hash function is a hash function which takes an input and returns a fixed-size alphanumeric string] each user password and store the result in a database. But there exists a drawback : When the user comes back to log into the website, they will still need to send over their (cleartext) password, since this is required in order for the server to do the check.

The fact that the cleartext password has to reach the server poses a major threat if the server is compromised. Hence, there is a need to introduce a new method to ensure that the cleartext password doesn’t reach the server.

PAKE as the name suggests is a key exchange mechanism. Key exchange protocols are designed to help two parties (say a client and server) agree on a shared key, using public-key cryptography. Some key exchange protocols — like the Diffie-Hellman were unauthenticated, which made them vulnerable to man-in-the-middle attacks [Attacks where the attacker secretly relays and possibly alters the communication between two parties who believe they are directly communicating with each other]. The distinguishing feature of PAKE protocols is the client will authenticate herself to the server using a password.

PAKE provides protection for the client’s password. After a login attempt (valid, or invalid) both the client and server should learn only whether the client’s password matched the server’s expected value, and no additional information.

Ideal representation of the PAKE protocol

Why isn’t PAKE being adopted?

With the exception of SRP(explained below), which is a varied version of the PAKE protocol, there seems to be no sight of the PAKE anywhere else.

Possible reasons :

1. There’s a lack of good PAKE implementations in useful languages, which makes it a hassle to use.
2. Patents hinder its implementation.
3. PAKE is not officially a certified protocol and many people aren’t aware of it.

OPAQUE

There is a certain protocol called the SRP [Secure Remote Password] protocol, which is a varied version of the PAKE protocol. It is one of the widely used protocols right now. SRP has been declared as an industry standard, and is actually implemented in libraries like OpenSSL.

But SRP has its drawbacks. SRP is vulnerable to pre-computation attacks, because it hands over the user’s “salt” [In cryptography, a salt is random data that is used as an additional input to a one-way function that “hashes” data. A new salt is randomly generated for each password] to an attacker who can start an SRP session. This means the attacker can ask a server for your salt, and build a dictionary of potential password hashes even before the server is compromised (hence the term, pre-computation).

OPAQUE solves this scenario. The protocol might be too complex to explain in a single article. But its features and functionality advantages can be easily studied.

OPAQUE does not reveal the salt to the attacker. It solves this problem by using an efficient oblivious PRF [A Pseudo Random Function is a function that is indistinguishable from a function selected at random from the set of all functions with the same domain and value set.] to combine the salt with the password, in a way that ensures the client does not learn the salt and the server does not learn the password. OPAQUE works with any password hashing function. Since all the hashing work is done on the client, OPAQUE can actually take load off the server.

How OPAQUE works

Keeps the salt a secret

The salt, along with the password is fed into a hash function. If the server is the one that computes this function, then the server has to see the password and the purpose is destroyed. Meanwhile, if it’s the client, the client needs the salt, which again defeats the purpose.

To solve this, OPAQUE does the following. The protocol leaves the password has on the client’s side, but doesn’t provide the salt to the hash. Instead, a special two-party protocol called an oblivious PRF (mentioned earlier) is employed to calculate a second salt so that the client can use this new salt in the hash function, but does not know the original salt.

Proving that the client got the right key K

The client has derived a key K, but the server doesn’t know what it is or whether it’s the right key.

When the user registers on the server for the first time, she generates a strong public and private key for a secure agreement protocol, and encrypts the resulting private key under K, along with the public key of the server into a ciphertext. Let’s call this ciphertext C.

The server sends the stored ciphertext C to the client. If the client entered the right password into the first phase, she can derive K, and now decrypt this ciphertext. The server verifies the clients’ inputs against its copy of the client’s public key, and the client does similarly.

Whew, that was a lot of information to handle. But the point is the PAKE protocol is a perfectly secure protocol being overlooked for not-so-valid reasons.

– Nishanth Subramanian