Let's talk about PAKE
Now let's talk about information security. This publication is timed to the launch of the course "Cryptographic Information Protection" , which starts as early as May 30. Go.
The first rule of PAKE: never talk about PAKE. The second rule, PAKE, states that the first rule is nonsense, since PAKE or the Password Authenticated Key Exchange (Rus. Key exchange with password authentication) is one of the most useful technologies that is almost never used. It should be implemented wherever possible, but not so simple.
')
To understand why we are talking about nonsense, let's look at the real problem.
Suppose I work with a server that stores user passwords. There is a traditional way of storage - to hash each user password and store the result in the password database. There are many ideas on how to handle the hashing process. The most common recommendation today is to use the hash function of a hard memory password (memory-hard password hashing function, such as scrypt or argon2 (with unique salt ) for each password), and then store the already hashed result. There are different opinions about which hash function to use and whether it will be able to use some secret value (called “pepper” ), but for now we will not talk about it.
Regardless of the approach you take, 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 .
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 of its users (and this 330 million!) To change passwords - because it turned out that the company stored text (not hashed) passwords.
At the moment, the login problem in no way contradicts 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 the new protocol called OPAQUE, which we will look at at the end of this article.
The PAKE protocol, first proposed by Bellovin and Merritt , is a specific type of key exchange protocol . Key exchange protocols (or “key agreements”) are designed to help two parties (let's call them client and server) agree on a common key using public key cryptography. The earliest key exchange protocols (for example, classic Diffie-Hellman were unauthorized, which made them vulnerable to man-in-the-middle attacks . A distinctive feature of PAKE protocols is that the client is authenticated to the server with a password. For obvious reasons that the password or its hash is already known to the server, which allows for verification.
If this were all that was needed, PAKE protocols would be easy to build. What makes PAKE really useful is that it also protects the client password. A more serious guarantee can be formulated as follows: after an attempt to enter the system (successful or unsuccessful), the client and the server need only know if the client's password matches the value expected by the server, and no further information. This is a pretty good defense. In fact, this is no different from what we require from the proof with zero disclosure .
Of course, the obvious problem with PAKE is that many developers don’t want to launch 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 fairly easy to execute. Suppose I have a standard protocol, PAKE, which allows the client and server to agree on the common key K. If he knows the correct password (and only in this case), then all we need to do is simply check that both parties received same key. (This can be done, for example, if the parties calculate some cryptographic function with it and compare the results.) Thus, PAKE can be useful even if you just want to check the password.
The concept of PAKE seems to provide an obvious security advantage over the naive approach that we use today to log on to 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 due 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 a login operation. Another possible explanation is related to patents , although most of them have already expired. For me, there are two possible reasons for the absence of PAKE:
Despite the fact that I said that PAKE is not used now, there are still exceptions to the rules.
There is one remarkable protocol developed in 1998 by Tom Woo (not to be confused with Tim Wu), which is called “SRP” (short for “Secure Remote Password”). In fact, this is just a three-stage PAKE with some additional features that were not implemented in the very first works. As far as I know, SRP is different 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, so many devices that Apple is stamping. And there is nothing funny.
The fact that the industry took the SRP is certainly good, but on the other hand, and not very. Basically, because, at least, any PAKE approval is cool, but SRP alone is not the best implementation of PAKE. I thought to go into the wilds of reasoning about the SRP, but this speech was already prolonged, and I digress from the story of a really good protocol, which we will discuss below. If you are still interested in the SRP discussion, I brought it here .
Instead of these unnecessary details, let me write a summary of my thoughts on the subject of SRP:
Of all these points, the latter is almost certainly responsible for the (relatively) high degree of commercial success that the SRP has achieved compared to 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 could not help but note that most of the existing implementations are pretty badly executed. They either had problems, the same as in SRP, or it was required that the user stored the password (or effective password) on the server, or the “salt” was shown to the attacker, giving the opportunity to make an attack before the calculation.
Then, at the beginning of last year, Yaretski, Kravchik and Xu revealed to the world a new protocol called OPAQUE . It has a number of significant advantages:
There is even an Internet Draft offer for OPAQUE, which you can read here. Unfortunately, at the moment I do not know anything about the quality of the implementation of the code, except that there are already several potential implementations. I hope this issue will clear up soon.
The full OPAQUE protocol is a little lower. In the rest 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 perform attacks before computing where he can generate a dictionary based on the data received.
The problem here is that the salt is usually passed to the hash function (for example, scrypt) along with the password. It is intuitively clear that someone has to calculate this function. If this is a server, then the server should see the password, which kills all sense. If this is a client, then he needs salt.
Theoretically, this problem can be circumvented 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 the password hashing functions are complex and time consuming. This will incredibly increase the complexity of any 2PC system.
OPAQUE bypasses this as follows. He leaves the password hash on the client, but does not show him the salt. Instead, it uses a special two-way protocol called the forgetful PRF to compute another salt (let's call it salt2) so that the client can use salt2 in the hash function, but did not get access to the original salt.
It works like this:
The actual implementation of the forgetful PRF can be accomplished using several group and exponent elements. Even better, if the client enters the wrong password, then the protocol gets the dummy value “salt2”, which says nothing about the real meaning of the salt.
Problem 2: Proof that the client received the correct K key. Of course, at the moment the client received the K key, but the server has no idea what it is. The server also does not know if this key is correct.
At the core of the OPAQUE solution is the old idea of Gentry, Mackenzie and Ramzan . When a user first registers with the server, the server generates a secure public and private key for the secure agreement protocol (for example, HMQV) and encrypts the received private key under K along with the public key of the server. The received 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 a client wants to authenticate using the OPAQUE protocol, the server sends it a stored C code. If the client entered the correct password in the first phase, he can get K , and decrypt this cipher. Otherwise it is useless. Using a private key, it can now run a standard protocol agreement with an authenticated key to complete the handshake. (The server validates the client's input data, verifying it with its copy of the client's public key, and the client does the same.)
Now let's put it all together. All these steps can be combined into one protocol that 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 final aspect of OPAQUE’s work is that it has good security evidence, which tells us that the resulting protocol can be considered safe if we take one or more discrete logarithms in a random oracle model, which is a standard assumption that , 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 also can allow us to handle them more efficiently - with a lot of hashing parameters and a greater load on the client side. Why is it not used everywhere? Maybe in the next few years things will change. Time will tell.
According to the established tradition, we are waiting for your comments and invite you to visit the open door , which our teacher, cryptanalyst Elena Kirshanova , will hold on May 27.
The first rule of PAKE: never talk about PAKE. The second rule, PAKE, states that the first rule is nonsense, since PAKE or the Password Authenticated Key Exchange (Rus. Key exchange with password authentication) is one of the most useful technologies that is almost never used. It should be implemented wherever possible, but not so simple.
')
To understand why we are talking about nonsense, let's look at the real problem.
Suppose I work with a server that stores user passwords. There is a traditional way of storage - to hash each user password and store the result in the password database. There are many ideas on how to handle the hashing process. The most common recommendation today is to use the hash function of a hard memory password (memory-hard password hashing function, such as scrypt or argon2 (with unique salt ) for each password), and then store the already hashed result. There are different opinions about which hash function to use and whether it will be able to use some secret value (called “pepper” ), but for now we will not talk about it.
Regardless of the approach you take, 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 .
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 of its users (and this 330 million!) To change passwords - because it turned out that the company stored text (not hashed) passwords.
At the moment, the login problem in no way contradicts 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 the new protocol called OPAQUE, which we will look at at the end of this article.
What is PAKE?
The PAKE protocol, first proposed by Bellovin and Merritt , is a specific type of key exchange protocol . Key exchange protocols (or “key agreements”) are designed to help two parties (let's call them client and server) agree on a common key using public key cryptography. The earliest key exchange protocols (for example, classic Diffie-Hellman were unauthorized, which made them vulnerable to man-in-the-middle attacks . A distinctive feature of PAKE protocols is that the client is authenticated to the server with a password. For obvious reasons that the password or its hash is already known to the server, which allows for verification.
If this were all that was needed, PAKE protocols would be easy to build. What makes PAKE really useful is that it also protects the client password. A more serious guarantee can be formulated as follows: after an attempt to enter the system (successful or unsuccessful), the client and the server need only know if the client's password matches the value expected by the server, and no further information. This is a pretty good defense. In fact, this is no different from what we require from the proof with zero disclosure .
Idealized representation of the PAKE protocol. Input data from both sides include some randomness, which is not shown here. The eavesdropper does not need to know the shared secret key K, which is itself random and not a function of the password.
Of course, the obvious problem with PAKE is that many developers don’t want to launch 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 fairly easy to execute. Suppose I have a standard protocol, PAKE, which allows the client and server to agree on the common key K. If he knows the correct password (and only in this case), then all we need to do is simply check that both parties received same key. (This can be done, for example, if the parties calculate some cryptographic function with it and compare the results.) Thus, PAKE can be useful even if you just want to check the password.
SRP: PAKE, which time itself has forgotten
The concept of PAKE seems to provide an obvious security advantage over the naive approach that we use today to log on to 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 due 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 a login operation. Another possible explanation is related to patents , although most of them have already expired. For me, there are two possible reasons for the absence of PAKE:
- The lack of high-quality implementations of PAKE in popular languages, which makes it troublesome to use;
- Cryptographic specialists do not convey the essence and value of their work, 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 remarkable protocol developed in 1998 by Tom Woo (not to be confused with Tim Wu), which is called “SRP” (short for “Secure Remote Password”). In fact, this is just a three-stage PAKE with some additional features that were not implemented in the very first works. As far as I know, SRP is different in that it is the most common PAKE protocol in the world. I will give two proofs of this statement:
- SRP was standardized as a TLS ciphersuite and implemented in libraries such as, for example, OpenSSL , although no one seems to use it much.
- 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, so many devices that Apple is stamping. And there is nothing funny.
The fact that the industry took the SRP is certainly good, but on the other hand, and not very. Basically, because, at least, any PAKE approval is cool, but SRP alone is not the best implementation of PAKE. I thought to go into the wilds of reasoning about the SRP, but this speech was already prolonged, and I digress from the story of a really good protocol, which we will discuss below. If you are still interested in the SRP discussion, I brought it here .
Instead of these unnecessary details, let me write a summary of my thoughts on the subject of 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 can 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 prevents an attacker from immediately replacing a user only if he does not conduct further costly dictionary attacks. (The technical name for this is "asymmetrical" PAKE.)
- There is better news, the current version of SRP (v4 v6a) has not yet been cracked!
- However (mind you, developers do not take offense) the architecture of the SRP protocol is completely crazy, and its earlier versions were hacked several times - that is why we now have version 6a. Plus the “proof of security” in the original research article does not really prove anything .
- SRP is currently based on integer (finite) 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 efficiency improvements that we have developed in add-ons such as Curve25519 .
- An SRP is vulnerable to pre-compute 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 even before the server is compromised.
- Despite all these shortcomings, SRP is extremely simple, and also comes with a 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 the SRP has achieved compared to 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 could not help but note that most of the existing implementations are pretty badly executed. They either had problems, the same as in SRP, or it was required that the user stored the password (or effective password) on the server, or the “salt” was shown to the attacker, giving the opportunity to make an attack before the calculation.
Then, at the beginning of last year, Yaretski, Kravchik and Xu revealed to the world a new protocol called OPAQUE . It has a number of significant advantages:
- It can even be implemented if there are Diffie-Hellman and discrete logarithm problems. This means that, unlike SRP, it can be instantiated easily with efficient elliptic curves.
- Better yet: OPAQUE does not reveal salt to the 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 the password.
- OPAQUE works with any password hashing function. Since all the hashing work is performed on the client, OPAQUE can actually take the load off the server, freeing the online service, say, to use extremely large security settings, for example, configure
scryptwith a lot of RAM . - In terms of the number of messages and exponents, OPAQUE is not much different from SRP. But since it can be implemented with more efficient parameters, it will probably work much more efficiently.
- Unlike SRP, OPAQUE has reasonable security proof (in a very strong model).
There is even an Internet Draft offer for OPAQUE, which you can read here. Unfortunately, at the moment I do not know anything about the quality of the implementation of the code, except that there are already several potential implementations. I hope this issue will clear up soon.
The full OPAQUE protocol is a little lower. In the rest 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 perform attacks before computing where he can generate a dictionary based on the data received.
The problem here is that the salt is usually passed to the hash function (for example, scrypt) along with the password. It is intuitively clear that someone has to calculate this function. If this is a server, then the server should see the password, which kills all sense. If this is a client, then he needs salt.
Theoretically, this problem can be circumvented 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 the password hashing functions are complex and time consuming. This will incredibly increase the complexity of any 2PC system.
OPAQUE bypasses this as follows. He leaves the password hash on the client, but does not show him the salt. Instead, it uses a special two-way protocol called the forgetful PRF to compute another salt (let's call it salt2) so that the client can use salt2 in the hash function, but did not get access to the original salt.
It works like this:
The server stores “salt” (salt), and the client has password.salt2 = PRF (salt, password), this is calculated between the client and the server using a protocol in which the client never learns the salt, and the server the password. The client receives salt2K = PasswordHash (salt2, password) - and all this is considered on the client.
The actual implementation of the forgetful PRF can be accomplished using several group and exponent elements. Even better, if the client enters the wrong password, then the protocol gets the dummy value “salt2”, which says nothing about the real meaning of the salt.
Problem 2: Proof that the client received the correct K key. Of course, at the moment the client received the K key, but the server has no idea what it is. The server also does not know if this key is correct.
At the core of the OPAQUE solution is the old idea of Gentry, Mackenzie and Ramzan . When a user first registers with the server, the server generates a secure public and private key for the secure agreement protocol (for example, HMQV) and encrypts the received private key under K along with the public key of the server. The received 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 a client wants to authenticate using the OPAQUE protocol, the server sends it a stored C code. If the client entered the correct password in the first phase, he can get K , and decrypt this cipher. Otherwise it is useless. Using a private key, it can now run a standard protocol agreement with an authenticated key to complete the handshake. (The server validates the client's input data, verifying it with its copy of the client's public key, and the client does the same.)
Now let's put it all together. All these steps can be combined into one protocol that 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 final aspect of OPAQUE’s work is that it has good security evidence, which tells us that the resulting protocol can be considered safe if we take one or more discrete logarithms in a random oracle model, which is a standard assumption that , 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 also can allow us to handle them more efficiently - with a lot of hashing parameters and a greater load on the client side. Why is it not used everywhere? Maybe in the next few years things will change. Time will tell.
According to the established tradition, we are waiting for your comments and invite you to visit the open door , which our teacher, cryptanalyst Elena Kirshanova , will hold on May 27.
Source: https://habr.com/ru/post/453334/
All Articles