May 24, 2019 at 14:48Talk about PAKE
- Transfer
Now let's talk about information security. This publication is dedicated to the launch of the course “Cryptographic Information Security” , which will start on May 30. Go.
First rule of PAKE: never talk about PAKE. The second rule of PAKE states that the first rule is nonsense, since PAKE or Password Authenticated Key Exchange (rus. Key exchange with password authentication) is one of the most useful technologies that is practically never used anywhere. It should be implemented wherever possible, but not so simple.
To understand why we are talking about nonsense, let's look at a real problem.
Suppose I work with a server that stores user passwords. There is a traditional way of storing - hashing each user password and storing the result in a password database. There are many ideas on how to handle the hash process. The most common recommendation today is to use a memory-hard password hashing function (such as scrypt or argon2 (with a unique salt ) for each password), and then store the hashed result. There are different opinions about which hash function to use and whether it can use some secret value (called “pepper” ), but for now we will not talk about it.
Regardless of the approach you choose, all these solutions have one Achilles heel:
When the user returns to enter the site, he will still need to send his (open) password to the server so that he can verify it .
This need can lead to unpleasant consequences if your server is ever compromised or if your developers make some stupid mistake. For example, at the beginning of last year, Twitter asked all its users (and this 330 million!) To change passwords - because it turned out that the company stored textual (non-hashed) passwords.
At the moment, the problem of logging in does not in any way contradict the benefits of password hashing. However, you need to find a better solution: one in which the password would never be sent to the server in clear text. The cryptographic tool that will help us achieve this is PAKE, and in particular, a new protocol called OPAQUE, which we will cover at the end of this article.
The PAKE protocol, first proposed by Bellovin and Merritt , is a specific kind of key exchange protocol . Key exchange protocols (or “key agreements”) are designed to help the two parties (let's call them client and server) agree on a shared key using public-key cryptography. The earliest key exchange protocols (for example, the classic Diffie-Hellman ) were unauthorized, which made them vulnerable to attacks such as man-in-the-middle . A distinctive feature of the PAKE protocols is that the client authenticates to the server with a password. For obvious reasons, it is assumed that the password or its hash is already known to the server, which allows verification.
If that were all it needed, PAKE protocols would be easy to build. But what makes PAKE really useful is that it also provides client password protection. A more serious guarantee can be formulated as follows: after an attempt to enter the system (successful or unsuccessful), the client and server should only know if the client password matches the value expected by the server, and no more additional information. This is a pretty good defense. In fact, this is no different from what we require from a zero-disclosure proof .
Of course, the obvious problem with PAKE is that many developers do not want to run the “key exchange” protocol in the first place! They just want to make sure the user knows the password.
The great thing about PAKE is that the “login only” use case is pretty easy to execute. Suppose I have a standard PAKE protocol that allows the client and server to agree on a common key K. If he knows the correct password (and only in this case), then all we need to implement is a simple check that both parties received the same key. (This can be done, for example, if the parties calculate with it some cryptographic function and verify the results.) Thus, PAKE can be useful even if you just want to verify the password.
The PAKE concept seems to provide an obvious security advantage over the naive approach we use today to enter the server. And the methods themselves are old, in the sense that PAKE has been known since 1992! Despite this, the light never saw him. Why it happens?
There are several obvious reasons. The most obvious is related to the limitations of the Internet: it is much easier to put a password form on a web page than to implement fancy cryptography in a browser. However, this explanation is not enough. Even native applications rarely implement PAKE for login operations. Another possible explanation is related to patents , although most of them have already expired. For me, there are two likely reasons for not having PAKE:
Despite the fact that I said that PAKE is not used now, there are still exceptions to the rules.
There is one great protocol developed in 1998 by Tom Wu (not to be confused with Tim Wu), which is called “SRP” (short for “Secure Remote Password“). In fact, it’s just a three-stage PAKE with some additional functions that were not implemented in the very first works. As far as I know, SRP differs in that it is the most common PAKE protocol in the world. I will give two proofs of this statement:
The second fact in itself could make SRP one of the most widely used cryptographic protocols in the world, the number of devices that Apple stamps is so great. And there is nothing funny.
The fact that the industry has accepted the SRP is certainly good, but on the other hand, and not very. Mostly because even though any PAKE endorsement is cool, SRP alone is not the best PAKE implementation. I thought to go into the jungle of discussions about SRP, but this speech was already dragging on, and I digress from the story about a really good protocol, which we will talk about below. If you are still interested in the discussion about SRP, I brought it here .
Instead of these unnecessary details, let me write a short summary of my thoughts on SRP:
Of all these points, the latter is almost certainly responsible for the (relatively) high degree of commercial success that SRP achieved over other PAKE protocols. He is not perfect, but real. This is what I wanted to convey to cryptographic security experts.
When I started thinking about PAKE a few months ago, I couldn't help but note that most of the existing implementations performed rather poorly. They either had problems, such as those in SRP, either required the user to store the password (or effective password) on the server, or the “salt” was shown to the attacker, making it possible to carry out the attack before calculating.
Then, at the beginning of last year, Jarecki, Kravczyk and Xu revealed to the world a new protocol called OPAQUE . It has a number of significant advantages:
There is even an Internet Draft proposal for OPAQUE, which you can read here. Unfortunately, at the moment I do not know anything about the quality of the code implementation, except that there are already several potential implementations. I hope this issue clears up soon.
The full-fledged OPAQUE protocol is listed below. In the remainder of this section, I'm going to talk about how it works.
Problem 1: Keeping salt a secret. As I mentioned above, the main problem with earlier versions of PAKE is the need to transfer salt from the server to the client (still not authenticated). This allows an attacker to carry out attacks before computing where he can generate a dictionary based on the data received.
The problem here is that salt is usually passed to a hash function (e.g. scrypt) along with the password. Intuitively, someone needs to compute this function. If it is a server, then the server should see a password, which kills any meaning. If this is a client, then he needs salt.
Theoretically, you can work around this problem by computing the password hashing function using the secure two-party computation protocol (2PC) . In practice, such solutions will almost certainly be ineffective, primarily because password hashing functions are complex and time-consuming. This will incredibly increase the complexity of any 2PC system.
OPAQUE goes around this as follows. It leaves a password hash on the client side, but does not show it salt. Instead, it uses a special two-way protocol called forgetful PRF to compute another salt (let's call it salt2) so that the client can use salt2 in the hash function but cannot access the original salt.
It works something like this:
The actual implementation of forgetful PRF can be done using several group elements and exponents. Even better, if the client enters the wrong password, then the protocol receives a dummy value “salt2”, which does not say anything about the real value of salt.
Problem 2: Proof that the client received the correct key K. Of course, at the moment the client has received the key K, but the server has no idea what it is. The server also does not know if this is the correct key.
OPAQUE's solution is based on the old idea of Gentry, Mackenzie and Ramzan. When a user first logs on to the server, the server generates a reliable public and private key for the secure agreement protocol (for example, HMQV) and encrypts the received private key under K along with the server’s public key. The resulting authenticated cipher (and public key) is stored in the password database.
C = Encrypt (K, client secret key | server's public key)
Full version of the OPAQUE protocol, excerpt from the article .
When the client wants to authenticate using the OPAQUE protocol, the server sends it the stored C code . If the client has entered the correct password in the first phase, he can get K, and decrypt this cipher. Otherwise, it is useless. Using a wired secret key, he can now run a standard agreement protocol with an authenticated key to complete the handshake. (The server checks the input of the clients, checking them against its copy of the client’s public key, and the client does the same.)
Now we will put everything together. All these steps can be combined into one protocol, which has the same number of steps as SRP. If you do not pay attention to the verification steps, it will look like the protocol above. In principle, the idea is only in two messages: one from the client, and the second is sent back to the server.
The last aspect of OPAQUE's work is that it has good security evidence that tells us that the resulting protocol can be considered secure if we take one or more discrete logarithms in a random oracle model, which is a standard assumption, which apparently , takes place in the settings with which we work.
So, in short, we have a reliable technology that can make the process of using passwords much easier, and can also allow us to deal with them more efficiently - with a lot of hashing parameters and more workload on the client side. Why is this not used everywhere? Maybe in the next few years everything will change. Time will tell.
According to the established tradition, we are waiting for your comments and invite you to visit the open door day , which will be held on May 27 by our teacher, cryptanalyst Elena Kirshanova .
First rule of PAKE: never talk about PAKE. The second rule of PAKE states that the first rule is nonsense, since PAKE or Password Authenticated Key Exchange (rus. Key exchange with password authentication) is one of the most useful technologies that is practically never used anywhere. It should be implemented wherever possible, but not so simple.
To understand why we are talking about nonsense, let's look at a real problem.
Suppose I work with a server that stores user passwords. There is a traditional way of storing - hashing each user password and storing the result in a password database. There are many ideas on how to handle the hash process. The most common recommendation today is to use a memory-hard password hashing function (such as scrypt or argon2 (with a unique salt ) for each password), and then store the hashed result. There are different opinions about which hash function to use and whether it can use some secret value (called “pepper” ), but for now we will not talk about it.
Regardless of the approach you choose, all these solutions have one Achilles heel:
When the user returns to enter the site, he will still need to send his (open) password to the server so that he can verify it .
This need can lead to unpleasant consequences if your server is ever compromised or if your developers make some stupid mistake. For example, at the beginning of last year, Twitter asked all its users (and this 330 million!) To change passwords - because it turned out that the company stored textual (non-hashed) passwords.
At the moment, the problem of logging in does not in any way contradict the benefits of password hashing. However, you need to find a better solution: one in which the password would never be sent to the server in clear text. The cryptographic tool that will help us achieve this is PAKE, and in particular, a new protocol called OPAQUE, which we will cover at the end of this article.
What is PAKE?
The PAKE protocol, first proposed by Bellovin and Merritt , is a specific kind of key exchange protocol . Key exchange protocols (or “key agreements”) are designed to help the two parties (let's call them client and server) agree on a shared key using public-key cryptography. The earliest key exchange protocols (for example, the classic Diffie-Hellman ) were unauthorized, which made them vulnerable to attacks such as man-in-the-middle . A distinctive feature of the PAKE protocols is that the client authenticates to the server with a password. For obvious reasons, it is assumed that the password or its hash is already known to the server, which allows verification.
If that were all it needed, PAKE protocols would be easy to build. But what makes PAKE really useful is that it also provides client password protection. A more serious guarantee can be formulated as follows: after an attempt to enter the system (successful or unsuccessful), the client and server should only know if the client password matches the value expected by the server, and no more additional information. This is a pretty good defense. In fact, this is no different from what we require from a zero-disclosure proof .
An idealized representation of the PAKE protocol. Input from both sides includes some randomness, which is not shown here. The eavesdropper does not need to find out the shared secret key K, which is itself random and is not a function of the password.
Of course, the obvious problem with PAKE is that many developers do not want to run the “key exchange” protocol in the first place! They just want to make sure the user knows the password.
The great thing about PAKE is that the “login only” use case is pretty easy to execute. Suppose I have a standard PAKE protocol that allows the client and server to agree on a common key K. If he knows the correct password (and only in this case), then all we need to implement is a simple check that both parties received the same key. (This can be done, for example, if the parties calculate with it some cryptographic function and verify the results.) Thus, PAKE can be useful even if you just want to verify the password.
SRP: PAKE, about which time itself has forgotten
The PAKE concept seems to provide an obvious security advantage over the naive approach we use today to enter the server. And the methods themselves are old, in the sense that PAKE has been known since 1992! Despite this, the light never saw him. Why it happens?
There are several obvious reasons. The most obvious is related to the limitations of the Internet: it is much easier to put a password form on a web page than to implement fancy cryptography in a browser. However, this explanation is not enough. Even native applications rarely implement PAKE for login operations. Another possible explanation is related to patents , although most of them have already expired. For me, there are two likely reasons for not having PAKE:
- Lack of high-quality PAKE implementations in popular languages, which makes it troublesome to use;
- Cryptography specialists do not convey the essence and value of their work poorly, so most people do not even know that PAKE exists at all.
Despite the fact that I said that PAKE is not used now, there are still exceptions to the rules.
There is one great protocol developed in 1998 by Tom Wu (not to be confused with Tim Wu), which is called “SRP” (short for “Secure Remote Password“). In fact, it’s just a three-stage PAKE with some additional functions that were not implemented in the very first works. As far as I know, SRP differs in that it is the most common PAKE protocol in the world. I will give two proofs of this statement:
- SRP was standardized as TLS ciphersuite and implemented in libraries such as, for example, OpenSSL , although no one seems to use it especially.
- Apple makes extensive use of SRP in its iCloud Key Vault
The second fact in itself could make SRP one of the most widely used cryptographic protocols in the world, the number of devices that Apple stamps is so great. And there is nothing funny.
The fact that the industry has accepted the SRP is certainly good, but on the other hand, and not very. Mostly because even though any PAKE endorsement is cool, SRP alone is not the best PAKE implementation. I thought to go into the jungle of discussions about SRP, but this speech was already dragging on, and I digress from the story about a really good protocol, which we will talk about below. If you are still interested in the discussion about SRP, I brought it here .
Instead of these unnecessary details, let me write a short summary of my thoughts on SRP:
- SRP does some things right. First, unlike earlier versions of PAKE, you do not need to store the raw password on the server (or, equivalently, a hash that could be used by an attacker instead of a password). Instead, the server stores a “verifier,” which is a one-way function of the password hash. This means that a password database leak does not allow an attacker to immediately replace a user only if he does not carry out further costly dictionary attacks. (The technical name for this is “asymmetric” PAKE.)
- There is better news, the current version of SRP (v4 v6a) has not yet been hacked!
- However (don't be offended by the developers) the architecture of the SRP protocol is completely crazy, and its earlier versions were hacked several times - which is why we now have version 6a. Plus, the "proof of safety" in the original research article does not actually prove anything .
- SRP is currently based on integer (final) arithmetic, and for various reasons (see clause 3 above) its architecture clearly cannot be transferred to an elliptic curve . This requires more bandwidth and computation, so SRP cannot take advantage of the many performance improvements that we have developed in add-ons like Curve25519 .
- SRP is vulnerable to pre-computing attacks because it passes the user's salt to any attacker who can initiate an SRP session. This means that I can ask the server for your salt and build a dictionary of potential password hashes before the server is compromised.
- Despite all these shortcomings, SRP is extremely simple, and also comes with working code. In addition, OpenSSL has working code that even integrates with TLS, which makes it relatively easy to implement.
Of all these points, the latter is almost certainly responsible for the (relatively) high degree of commercial success that SRP achieved over other PAKE protocols. He is not perfect, but real. This is what I wanted to convey to cryptographic security experts.
OPAQUE: PAKE new generation
When I started thinking about PAKE a few months ago, I couldn't help but note that most of the existing implementations performed rather poorly. They either had problems, such as those in SRP, either required the user to store the password (or effective password) on the server, or the “salt” was shown to the attacker, making it possible to carry out the attack before calculating.
Then, at the beginning of last year, Jarecki, Kravczyk and Xu revealed to the world a new protocol called OPAQUE . It has a number of significant advantages:
- It can be implemented even if there are problems of Diffie-Hellman and discrete logarithms. This means that, unlike SRP, it can be easily instantiated using effective elliptic curves.
- Even better: OPAQUE does not reveal salt to an attacker. He solves this problem by using “forgetful PRF” to combine the salt with the password so that the client does not receive the salt and the server does not receive the password.
- OPAQUE works with any password hashing function. Since all hashing work is performed on the client, OPAQUE can actually take the load off the server, freeing the online service, for example, to use extremely voluminous security settings, for example, configure it
scryptwith a lot of RAM . - In terms of message count and exponent, OPAQUE is not much different from SRP. But since it can be implemented with more efficient parameters, it is likely to work much more efficiently.
- Unlike SRP, OPAQUE has reasonable safety evidence (in a very strong model).
There is even an Internet Draft proposal for OPAQUE, which you can read here. Unfortunately, at the moment I do not know anything about the quality of the code implementation, except that there are already several potential implementations. I hope this issue clears up soon.
The full-fledged OPAQUE protocol is listed below. In the remainder of this section, I'm going to talk about how it works.
Problem 1: Keeping salt a secret. As I mentioned above, the main problem with earlier versions of PAKE is the need to transfer salt from the server to the client (still not authenticated). This allows an attacker to carry out attacks before computing where he can generate a dictionary based on the data received.
The problem here is that salt is usually passed to a hash function (e.g. scrypt) along with the password. Intuitively, someone needs to compute this function. If it is a server, then the server should see a password, which kills any meaning. If this is a client, then he needs salt.
Theoretically, you can work around this problem by computing the password hashing function using the secure two-party computation protocol (2PC) . In practice, such solutions will almost certainly be ineffective, primarily because password hashing functions are complex and time-consuming. This will incredibly increase the complexity of any 2PC system.
OPAQUE goes around this as follows. It leaves a password hash on the client side, but does not show it salt. Instead, it uses a special two-way protocol called forgetful PRF to compute another salt (let's call it salt2) so that the client can use salt2 in the hash function but cannot access the original salt.
It works something like this:
The server stores “salt”, and the client has password.salt2 = PRF (salt, password), this is calculated between the client and server using a protocol in which the client will never recognize the salt and the server will know the password. The client receives salt2K = PasswordHash (salt2, password) - and all this is considered on the client.
The actual implementation of forgetful PRF can be done using several group elements and exponents. Even better, if the client enters the wrong password, then the protocol receives a dummy value “salt2”, which does not say anything about the real value of salt.
Problem 2: Proof that the client received the correct key K. Of course, at the moment the client has received the key K, but the server has no idea what it is. The server also does not know if this is the correct key.
OPAQUE's solution is based on the old idea of Gentry, Mackenzie and Ramzan. When a user first logs on to the server, the server generates a reliable public and private key for the secure agreement protocol (for example, HMQV) and encrypts the received private key under K along with the server’s public key. The resulting authenticated cipher (and public key) is stored in the password database.
C = Encrypt (K, client secret key | server's public key)
Full version of the OPAQUE protocol, excerpt from the article .
When the client wants to authenticate using the OPAQUE protocol, the server sends it the stored C code . If the client has entered the correct password in the first phase, he can get K, and decrypt this cipher. Otherwise, it is useless. Using a wired secret key, he can now run a standard agreement protocol with an authenticated key to complete the handshake. (The server checks the input of the clients, checking them against its copy of the client’s public key, and the client does the same.)
Now we will put everything together. All these steps can be combined into one protocol, which has the same number of steps as SRP. If you do not pay attention to the verification steps, it will look like the protocol above. In principle, the idea is only in two messages: one from the client, and the second is sent back to the server.
The last aspect of OPAQUE's work is that it has good security evidence that tells us that the resulting protocol can be considered secure if we take one or more discrete logarithms in a random oracle model, which is a standard assumption, which apparently , takes place in the settings with which we work.
Conclusion
So, in short, we have a reliable technology that can make the process of using passwords much easier, and can also allow us to deal with them more efficiently - with a lot of hashing parameters and more workload on the client side. Why is this not used everywhere? Maybe in the next few years everything will change. Time will tell.
According to the established tradition, we are waiting for your comments and invite you to visit the open door day , which will be held on May 27 by our teacher, cryptanalyst Elena Kirshanova .