Protecting Passwords from Eavesdroppers
This articles gets into technical security discussion of a new key-exchange protocol called OPAQUE.
You have seen One Time passwords, these are short digits-only codes you get as SMS in order to log into websites. Such one time passwords (OTPs) would protect you from a thief who stole your main password. Without knowing the OTP, which only you have received, the thief can’t login on your behalf. But, can’t he steal your OTP as well?
There are two ways how a thief can steal your OTP. He can observe it as you are typing it, or he can observe it as it’s transmitted to the website’s server afterwards. The former method is called Fishing (a.k.a “Phishing”), the latter method is called Man-in-the-Middle (MITM).
In the Fishing attack, the thief gets you to type your OTP on a rogue web page that looks like an authentic one. The Javascript on the page can see everything that you type, even if you don’t press any kind of “Submit” button. Therefore, he can collect the OTP that you have typed and use it to login into the authentic website by himself.
Alternatively, in the MITM attack, the thief intercepts and relays the complete data communication — which includes the OTP — in transit to an authentic destination. The presence of the MITM is invisible. For instance, if the user was logging into his Web mail (e.g. Gmail), he would still be able to see and read all his emails. The catch is that the MITM would also see them and could read them.
How can an attacker position himself in the middle of a transmission? Fifty years ago, one only had to tap into a phone line coming out of a building, to listen to all conversations flowing through. In the days of the Internet this can be accomplished through manipulating Domain Name System (DNS).
When you type a domain name such as “gmail.com” in you web browser, you browser must ask the DNS for an IP address. If the system has been compromised, then the browser will get an IP address to a rogue server. The browser will connect to that rogue server, and that server will relay the data to the authentic server, in a MITM operation.
The DNS can be compromised through a DNS cache poisoning attack. Alternatively, a virus can alter a special file (the “hosts” file) on your computer, and set a specific IP address for a particular domain. Here’s an example of the kind of impersonation this could accomplish:
The web browser has a way to defend against such impersonations, when you add the “https://” prefix in URLs. It relies on a central authority called PKI to verify that it is communicating directly with Facebook’s servers. The loaded facebook page must display a certificate which the browsers would verify against its own database. Because new websites are created all the time, not all of the possible certificates are in browser’s database. The browser would verify an unknown certificate with a central authority (CA).
In order to relieve pressure from the CA being bombarded by billons verification requests for websites, the CA federates the job to subsidiaries. The authenticity of the subsidiaries, as well as all the certificates, is validated through Public Key Infrastructure (PKI) cryptography. The whole infrastructure is organized according to a trust hierarchy.
The following analogy with a military Chain of Command will make it clear how PKI works. A soldier receives a command from his military commander to fire a rocket. Why should he obey? He should obey, because he trusts that his commander received that command from someone higher up. The commander, in turn received the command from his general. The commander obeys the general, because he trusts that the general received that command from the President himself. In summary, there’s a chain of trust between the soldier and the President, and the soldier knows that the command is legitimate despite the fact that the soldier get it from the President directly.
Getting back to web browsers and servers, the PKI system is based on certificates, each verifying another certificate. The web browser ships with a “President” certificate, the CA certificate. A website presents a certificate to the web browser, as well as a chain of certificates that in the end rely on the knowledge of the real CA certificate. The web browser then verifies that the presented certificate can be chained back to the root CA certificate.
Because the browser was shipped with the root CA certificate, and because the user trusts that the browser has no security vulnerabilities, he consequently trusts that the CA certificate is legitimate, and that the whole verification process is correct.
However, the chain of command in the military breaks if one of the generals or the commanders simply made up that a rocket has to be fired, having never received that command from the higher-ups. All it takes is one bad link in the chain.
Similarly, the PKI system breaks if one of the certificates in the chain is rogue. In 2009, a team of researches was able to produce such a rogue certificate. It accomplished it by getting a rogue piece of data to have the same checksum (MD5) as a legitimate piece of data. This was enough, because the PKI system is based on checksums of data, rather than the whole data inside the certificate. Because the checksums matched, a rogue certificate was indistinguishable to the PKI verification process from the authentic certificate. The rogue certificate allowed a MITM to present a web page with “https://facebook.com” URL that would not trigger any warnings in the web browser.
Furthermore, if the rogue web page shows a page that looks like the real Facebook, then this web page is doing a Fishing attack too. It can inspect everything that you do and steal your main password and OTP, all because you are interacting with the Javascript code running in that web page.
Not all Fishing attacks require a MITM attack, however. Someone can register a misspelling of a domain, hoping that the users land there by mistake. Or, he can send an email with a link leading to a page that looks like an authentic Google login. Although the domain name is different, the user may not notice because he is focused on the content on the web page, not on the URL bar above it.
In my previous article “Website Switcheroo” I have described another Fishing attack. These attacks are technically less sophisticated than MITM and DNS cache poisoning, but they are effective.
On the other hand, not all MITM attacks need to generate a Fishing page. You may be browsing a legitimate page that makes an API web request to a 3rd party service, such as Facebook comments embedded on a web page. The MITM may be able to intercept such requests, in which case the you have no URL bar to look at. (The URL is inside the Iframe HTML element, which you can see only if you use an HTML inspector.)
Last but not least, a tool called “sslstrip” developed by Moxie Marlinspike can be used to convert “https://” requests to “http://” requests, thereby bypassing the PKI infrastructure entirely. This tool can be deployed in various scenarios. For example, it can be deployed on a local LAN and can target any user as a MITM. This scenario is described in this article by Aditya Anand, in which he shows how to steal Facebook credentials.
In summary, a user may not automatically trust that he is interacting with an authentic web page. If the web page is not authentic, then it has Javascript that is not authentic. This Javascript will see everything that the user types, including his password, and can send this data anywhere, to be used maliciously.
So if the danger is inside the Javascript, is it possible to do a “login” without interacting with the Javascript on a web page? Yes, it is called HTTP Basic Authentication (BasicAuth) and it is supported by all web browsers.
The browser pops up a modal window and asks you for a username and password. Then, the browser sends the data to the server.
Note that the data can still be intercepted by a MITM, despite the fact that the Javascript could not catch it. Moreover, a rogue web page would not ask you for the password using this method, because it can’t eavesdrop on it that way. It will instead ask you for the password by presenting a form in the body of the page.
With this introduction, let’s formulate the problem as “How can a user authenticate to the server, and the server can authenticate to the user?”
At present, the user uses a password to authenticate to the server and the server uses a PKI certificate to authenticate to the user. Yet, we have seen that both of these methods in the face of MITM and Fishing attacks.
A solution is on the horizon, and it is called the OPAQUE protocol. The user sends an “opaque” password to the server, and the server replies to it with an “opaque” salt. Them being opaque, means that a MITM can not see inside the transmitted packages. Despite that, the user is able to manipulate all the data to form a cipher key.
The cipher key that the user forms can unlock data that was previously stored on the server by the user. Inside this data is the identifying certificate of the server which the user can verify against the purported identity of the displayed webpage. The user can use this certificate to create a secure channel with the server which a MITM would not be able to eavesdrop.
Also, the data that the user retrieves from the server contains identifying information about the user in the form of user’s private identity key. This key can be used to prove to the server the purported identity of the user.
All in all, the OPAQUE protocol accomplishes a secure channel to the server without any reliance on the PKI infrastructure. But unlike PKI authentication, it does require a user to know a password. Since most web sites require a user to login anyway, expecting a user to know a password is not a problem. Moreover, the password can be as short as a 4 digits OTP, just like with bank ATMs.
If I got the reader excited, let’s see how the mathematics of the OPAQUE scheme works. First, imagine a scenario in which a user has a strong password such as “d3E9fqHCjL%UeGM”. Such a long and cryptic password is one of 70¹⁵ or 2⁹⁰ possibilities, and can be used to generate a cipher key. He could request from the server previously stored encrypted data package. He could then decrypt that package, and obtain more data about his own identity and the server’s, as I have described above.
In reality, however, we can not expect a user to always have a strong password, which means that he can’t form a cipher key from it. If he did, a MITM would be able to generate all possible cipher keys that would derive from short passwords, and try them all to decrypt data in transit.
The OPAQUE protocol has a solution using a sub-protocol called DH-OPRF. This subprotocol is at the heart of the scheme: it allows to extend a short password to a longer password. It arranges for the server to send to the user a previously stored salt. Conventionally, a salt is a long password-looking string, which is only known to the server. But a transmission, a MITM would be able to see this salt too, thereby making it useless for our purposes. Yet, the DH-OPRF protocol is an ingenious solution to transmit the salt without the MITM being able to observe it.
The “DH” in the name DH-OPRF stands for Diffie-Hellman exchange. In the DH exchange similarly “opaque” values are transmitted. Particularly, instead of transmitting a value “x”, the value “2^x (mod p)” is transmitted, where “p” is a large prime number greater than 10⁶⁰⁰.
The “mod p” expression means that all multiples of a prime number “p” are removed from the computed value, in order to make the result smaller than “p”. This is not only done to make the number fit in a reasonably small space. Notice that it is hard to determine afterwards exactly how many multiples were removed. This difficulty is the reason why a MITM is not able to determine the exponent “x” from the eavesdropped value of “2^x (mod p).” It would be easy for small “x”, but hard for values greater than 10⁶⁰⁰.
You may wonder: if it is hard for the MITM to extract x from 2^x (mod p), then how can a legitimate user can do it? The user receiving 2^x (mod p) can form the expression 2^{xy} (mod p), without ever extracting the exponent. He does so using a basic principle of mathematical exponents: (a^x)^y = a^(xy). Here “y” is a number only known to the receiving party, which never enters transit through the MITM. In the end, the expression 2^(xy) forms the basis to derive a cipher key. (The other user receives 2^y and forms 2^y^x.)
The DH-OPRF does something similar, but uses another mathematical formula. In 17th century, the mathematician Fermat observed that multiplying a number “a” by itself and removing multiples of p from the intermediate results, would result in a repeating sequence: a, aa, aaa, …,1, a, aa, aaa, …, 1, a, aa, …. The number 1 occurs at position (p-1), which causes the sequence to repeat. In other words, a^(p-1) = 1 (mod p). The only requirement for this to work, is for “a” and “p” to have no common divisors. Because, usually p is taken to be a prime number, no number has common divisors with it.
Notice that in the list a, aa, aaa, …, 1, a, aa, … what follows number 1 is another “a”. This principle can be adapted to converting “a^x” back to “a”. This is how it works. Given a^x, we can find a matching “y” so that the product “xy” is greater than a multiple of (p-1) by exactly 1. Then, the sequence a, aa, …, a^(xy) will end exactly on “a”.
It is not difficult to compute such value “y”. This can be done by the Extended Euclidian algorithm, which is computationally quick because it only uses subtractions. The associated equation would be xy + n(p-1) = 1, and the solution would exist provided that “x” and “(p-1)” have no common divisors.
We now have enough background to understand the way the salt is sent in the DH-OPRF protocol. Let’s suppose that the salt known to the server is called “k”, and that the user’s password is the number “h”. The computation is ((h^x)^k)^y (mod p), with each exponentiation happening in a different communication leg of the protocol. Note that by regrouping exponents, this value can be rewritten as (h^k)^(xy).
If “x” and “y” were chosen so as to satisfy the equation a^(xy) = a (mod p) for any base value “a”, then the equation is also true when the base value is “h^k”. Thus, the overall result computed through DH-OPRF exchange simplifies from (h^k)^(xy) to the simple (h^k).
What have we accomplished? We still don’t know what is the isolated salt “k”. Turns out that this is not necessary, because value h^k is the mix that we wanted in the end. It combines a weak password “h”, with a long salt value k that the server supplied. This value can be used as a cipher key, as we have discussed.
I have omitted a few details about DH-OPRF protocol to make the explanations simpler. First, the user’s password is converted to the number “h” by the application of a Hash function. Such a function would take any string and convert it to a number. However, it is not a regular hash function which must only satisfy that it doesn’t “collide” two different strings by mapping them to the same numeric value. This function must also be a Pseudo-Random Function (PRF) that generates numbers that look “random”. Such a function is similar to the concept of Pseudo-Random Number Generator (PRNG), but instead of merely generating a list of random looking numbers, it maps strings to random looking numbers. This means that observing any number of such output values, will not allow to predict additional output values with any improved confidence. The function is called “pseudo”, because a function that gives truly random looking outputs would not be possible to implement in practice (it would require too much computation and storage).
The second detail about DH-OPRF I have omitted is that it is specified in a context of a general mathematical Group, instead of merely modular arithmetic. With modular arithmetic the values exchanged would have to be as large as 512 bytes long, which may not be ideal for some setups. Alternatively, Elliptic Curve Groups can be used, that would need only 32-bytes per exchanged value.
To summarize, the DH-OPRF protocol is an exercise in cryptographic wrapping and unwrapping. At the end of it, the user has a strong password, composed of his weak password and the salt.
An interesting feature of the protocol is that the server does not need to know either password of the user, or its hash code. In contrast, in conventional Log-In handling, the server stores the hash code of user’s password in order to verify the password that it receives. It is better to store hash codes of passwords instead of actual passwords. If the password database is stolen from the server, then the thief would still not know the actual passwords.
However, even if only hash codes are stored on the server, the thief can successfully determine a weak password by trying many possibilities and comparing hash codes. This is true also if the passwords were hashed with different salts per user account, because the thief would also have stolen those salts.
Let’s contrast this with the OPAQUE protocol handling. Here, the server stores encrypted blobs and user salts instead of hash codes of passwords. The thief can try generating many cipher keys per salt, and then try to decrypt such a blob. Because the blob contains structured data which must match other data in the server, the thief will be able to determine that decryption was successful. This in turn would tell him that he guessed correctly the user’s password.
Therefore, at first glance it does not seem that OPAQUE offers any advantages over conventional systems in cases of database compromise . However, this protocol is slightly better in this regard because it allows the keys to be generated with a strong Key Derivation Function (KDF) such as Scrypt.
Normally, servers use the Bcrypt hash function to create hash codes for the passwords, because the alternative Scrypt takes too much computational resources. Using Scrypt on the server would overload a busy server. But in the OPAQUE protocol, the the cipher key is generated on the client’s side, by the user’s personal computer. His computer has available CPU and Memory to run the stronger Scrypt algorithm.
Still, a theft of server database is grave in OPAQUE’s case. By merely holding the stolen salt, the encrypted blob, and any other metadata for the user, an attacker can setup a MITM server that would appear legitimate to the user, according to the OPAQUE protocol. This MITM would not need to relay the data to the real server, to simulate a full working session, but can merely present a Fishing page. After asking the user to authenticate, the MITM can ask the user to retype the password again, under some pretence. Having obtained the password, the MITM can connect to the authentic server and simulate a full session.
In summary, the OPAQUE protocol doesn’t make the server any less secure with respect to user’s passwords than conventional schemes. It offers an extra benefit that so long as the server itself is not compromised, then the user is safe from MITM and Fishing. And that is still the case if the user is using a weak password like a 4-digit PIN.
Bank’s ATMs are confident that they can maintain own integrity, and allow users to login with a PIN. Unfortunately, we have seen that many server’s databases get stolen all the time. Given such a threat risk, the OPAQUE protocol can still be used with weak passwords, as long as these are Second Factor Authentication (2FA) codes. Working together with the conventional DNS and PKI website authentication, the OPAQUE authentication will make it even harder to impersonate websites.
In summary, the OPAQUE protocol can’t be the single solution to authentication, but must work with other protocols, making the lives of eavesdroppers much harder. What other uses for the OPAQUE protocol you can think of?
