ENTER TEASER

The first rule of PAKE is: nobody ever wants to talk about PAKE. The second rule of PAKE is that this is a shame, because PAKE — which stands for Password Authenticated Key Exchange — is actually one of the most useful technologies that (almost) never gets used. It should be deployed everywhere, and yet it isn’t.

To understand why this is such a damn shame, let’s start by describing a very real problem.

Imagine I’m operating a server that has to store user passwords. The traditional way to do this is to hash each user password and store the result in a password database. There are many schools of thought on how to handle the hashing process; the most common recommendation these days is to use a memory-hard password hashing function like scrypt or argon2 (with a unique per-password salt), and then store only the hashed result. There are various arguments about which hash function to use, and whether it could help to also use some secret value (called “pepper“), but we’ll ignore these for the moment.

Regardless of the approach you take, all of these solutions have a single achilles heel:

When the user comes back to log into your website, they will still need to send over their (cleartext) password, since this is required in order for the server to do the check. 

This requirement can lead to disaster if your server is ever persistently compromised, or if your developers make a simple mistake. For example, earlier this year Twitter asked all of its (330 million!) users to change their passwords — because it turned out that company had been logging cleartext (unhashed) passwords.

Now, the login problem doesn’t negate the advantage of password hashing in any way. But it does demand a better solution: one where the user’s password never has to go to the server in cleartext. The cryptographic tool that can give this to us is PAKE, and in particular a new protocol called OPAQUE, which I’ll get to at the end of this post.

What’s a PAKE?

A PAKE protocol, first introduced by Bellovin and Merritt, is a special form of cryptographic key exchange protocol. Key exchange (or “key agreement”) protocols are designed to help two parties (call them a client and server) agree on a shared key, using public-key cryptography. The earliest key exchange protocols — like classical Diffie-Hellman — were unauthenticated, which made them vulnerable to man-in-the-middle attacks. The distinguishing feature of PAKE protocols is the client will authenticate herself to the server using a password. For obvious reasons, the password, or a hash of it, is assumed to be already known to the server, which is what allows for checking.

If this was all we required, PAKE protocols would be easy to build. What makes a PAKE truly useful is that it should also provide protection for the client’s password. A stronger version of this guarantee can be stated as follows: 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. This is a powerful guarantee. In fact, it’s not dissimilar to what we ask for from a zero knowledge proof.

Of course, the obvious problem with PAKE is that many people don’t want to run a “key exchange” protocol in the first place! They just want to verify that a user knows a password.

The great thing about PAKE is that the simpler “login only” use-case is easy to achieve. If I have a standard PAKE protocol that allows a client and server to agree on a shared key K if (and only if) the client knows the right password, then all we need add is a simple check that both parties have arrived at the same key. (This can be done, for example, by having the parties compute some cryptographic function with it and check the results.) So PAKE is useful even if all you’ve got in mind is password checking.

SRP: The PAKE that Time Forgot

The PAKE concept seems like it provides an obvious security benefit when compared to the naive approach we use to log into servers today. And the techniques are old, in the sense that PAKEs have been known since way back in 1992! Despite this, they’ve seen from almost no adoption. What’s going on?

There are a few obvious reasons for this. The most obvious has to do with the limitations of the web: it’s much easier to put a password form onto a web page than it is to do fancy crypto in the browser. But this explanation isn’t sufficient. Even native applications rarely implement PAKE for their logins. Another potential explanation has to do with patents, though most of these are expired now. To me there are two likely reasons for the ongoing absence of PAKE: (1) there’s a lack of good PAKE implementations in useful languages, which makes it a hassle to use, and (2) cryptographers are bad at communicating the value of their work, so most people don’t know PAKE is even an option.

Even though I said PAKE isn’t deployed, there are some exceptions to the rule.

One of the remarkable ones is a 1998 protocol designed by Tim Wu and called “SRP”. Short for “Secure Remote Password“, this is a simple three-round PAKE with a few elegant features that were not found in the earliest works. Moreover, SRP has the distinction of being (as far as I know) the most widely-deployed PAKE protocol in the world. I cite two pieces of evidence for this claim:

1. SRP has been standardized as a TLS ciphersuite, and is actually implemented in libraries like OpenSSL, even though nobody seems to use it much.
2. Apple uses SRP extensively in their iCloud Key Vault.

This second fact by itself could make SRP one of the most widely used cryptographic protocols in the world, so vast is the number of devices that Apple ships. So this is nothing to sneer at.

Industry adoption of SRP is nice, but also kind of a bummer: mainly because while any PAKE adoption is cool, SRP itself isn’t the best PAKE we can deploy. I was planning to go into the weeds about why I feel so strongly about SRP, but it got longwinded and it distracted from the really nice protocol I actually want to talk about further below. If you’re still interested, I moved the discussion onto this page.

In lieu of those details, let me give a quick and dirty TL;DR on SRP:

1. SRP does some stuff “right”. For one thing, unlike early PAKEs it does not require you to store a raw password on the server (or, equivalently, a hash that could be used by a malicious client in place of the password). Instead, the server stores a “verifier” which is a one-way function of the password hash. This means a leak of the password database does not (immediately) allow the attacker to impersonate the user — unless they conduct further expensive dictionary attacks. (The technical name for this is “asymmetric” PAKE.)
2. Even better, the current version of SRP (v4 v6a) isn’t obviously broken!
3. However (and with no offense to the designers) the SRP protocol design is completely bonkers, and earlier versions have been broken several times — which is why we’re now at revision 6a. Plus the “security proof” in the original research paper doesn’t really prove anything meaningful.
4. SRP currently relies on integer (finite field) arithmetic, and for various reasons (see point 3 above) the construction is not obviously transferable to the elliptic curve setting. This requires more bandwidth and computation, and thus SRP can’t take advantage of the many efficiency improvements we’ve developed in settings like Curve25519.
5. SRP is vulnerable to pre-computation attacks, due to the fact that it hands over the user’s “salt” to any attacker who can start an SRP session. This means I can ask a server for your salt, and build a dictionary of potential password hashes even before the server is compromised.
6. Despite all these drawbacks, SRP is simple — and actually ships with working code. Plus there’s working code in OpenSSL that even integrates with TLS, which makes it relatively easy to adopt.

Out of all these points, the final one is almost certainly responsible for the (relatively) high degree of commercial success that SRP has seen when compared to other PAKE protocols. It’s not ideal, but it’s real. This is something for cryptographers to keep in mind.

OPAQUE: The PAKE of a new generation

When I started thinking about PAKEs a few months ago, I couldn’t help but notice that most of the existing work was kind of crummy. It either had weird problems like SRP, or it required the user to store the password (or an effective password) on the server, or it revealed the salt to an attacker — allowing pre-computation attacks.

Then earlier this year, Jarecki, Krawczyk and Xu proposed a new protocol called OPAQUE. Opaque has a number of extremely nice advantages:

1. It can be implemented in any setting where Diffie-Hellman and discrete log (type) problems are hard. This means that, unlike SRP, it can be easily instantiated using efficient elliptic curves.
2. Even better: OPAQUE does not reveal the salt to the attacker. It solves this problem by using an efficient “oblivious PRF” 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.
3. OPAQUE works with any password hashing function. Even better, since all the hashing work is done on the client, OPAQUE can actually take load off the server, freeing an online service up to use much strong security settings — for example, configuring scrypt with large RAM parameters.
4. In terms of number of messages and exponentiations, OPAQUE is not much different from SRP. But since it can be implemented in more efficient settings, it’s likely to be a lot more efficient.
5. Unlike SRP, OPAQUE has a reasonable security proof (in a very strong model).

There’s even an Internet Draft proposal for OPAQUE, which you can read here. Unfortunately, at this point I’m not aware of any production quality implementations of the code (if you know of one, please link to it in the comments and I’ll update). (Update: There are several potential implementations listed in the comments — I haven’t looked closely enough to endorse any, but this is great!) But that should soon change.

The full OPAQUE protocol is given a little bit further below. In the rest of this section I’m going to go into the weeds on how OPAQUE works.

Problem 1: Keeping the salt secret. As I mentioned above, the main problem with earlier PAKEs is the need to transmit the salt from a server to a (so far unauthenticated) client. This enables an attacker to run pre-computation attacks, where they can build an offline dictionary based on this salt.

The challenge here is that the salt is typically fed into a hash function (like scrypt) along with the password. Intuitively someone has to compute that function. If it’s the server, then the server needs to see the password — which defeats the whole purpose. If it’s the client, then the client needs the salt.

In theory one could get around this problem by computing the password hashing function using secure two-party computation (2PC). In practice, solutions like this are almost certainly not going to be efficient — most notably because password hashing functions are designed to be complex and time consuming, which will basically explode the complexity of any 2PC system.

OPAQUE gets around this with the following clever trick. They leave the password hash on the client’s side, but they don’t feed it the stored salt. Instead, they use a special two-party protocol called an oblivious PRF to calculate a second salt (call it salt2) so that the client can use salt2 in the hash function — but does not learn the original salt.

It works like this:

The server stores "salt", and the client has the password.

salt2 = PRF(salt, password) // This is calculated between the 
                            // client and server, using an oblivious
                            // protocol where the client never learns
                            // salt, and the server never learns
                            // the password. The client obtains salt2

K      = PasswordHash(salt2, password) // This is done on the client

The actual implementation of the oblivious PRF can be done using a couple of group elements and exponentiations. Even better, if the client enters the wrong password into that protocol, she obtains a completely bogus “salt2” value that reveals nothing about the real salt value.

Problem 2: Proving that the client got the right key K. Of course, at this point, the client has derived a key K, but the server has no idea what it is. Nor does the server know whether it’s the right key.

The solution OPAQUE uses based an old idea due to Gentry, Mackenzie and Ramzan. When the user first registers with the server, she generates a strong public and private key for a secure agreement protocol (like HMQV), and encrypts the resulting private key under K, along with the server’s public key. The resulting authenticated ciphertext (and the public key) is stored in the password database.

C = Encrypt(K, client secret key | server’s public key)

When the client wishes to authenticate using the OPAQUE protocol, the server sends it the stored ciphertext C. If the client entered the right password into the first phase, she can derive K, and now decrypt this ciphertext. Otherwise it’s useless. Using the embedded secret key, she can now run a standard authenticated key agreement protocol to complete the handshake. (The server verifies the clients’ inputs against its copy of the client’s public key, and the client does similarly.)

Putting it all together. All of these different steps can be merged together into a single protocol that has the same number of rounds as SRP. Leaving aside the key verification steps, it looks like the protocol above. Basically, just two messages: one from the client and one returned to the server.

The final aspect of the OPAQUE work is that it includes a strong security proof that shows the resulting protocol can be proven secure under the 1-more discrete logarithm assumption in the random oracle model, which is a (well, relatively) standard assumption that appears to hold in the settings we work with.

In conclusion

So in summary, we have this neat technology that could make the process of using passwords much easier, and could allow us to do it in a much more efficient way — with larger hashing parameters, and more work done by the client? Why isn’t this everywhere?

Maybe in the next few years it will be.

 

 

 

 

Enlarge / One of the hacked websites, wifelovers.com, as it appeared on October 12. (credit: Internet Archive)

A recent hack of eight poorly secured adult websites has exposed megabytes of personal data that could be damaging to the people who shared pictures and other highly intimate information on the online message boards. Included in the leaked file are (1) IP addresses that connected to the sites, (2) user passwords protected by a four-decade-old cryptographic scheme, (3) names, and (4) 1.2 million unique email addresses, although it’s not clear how many of the addresses legitimately belonged to actual users.

Robert Angelini, the owner of wifelovers.com and the seven other breached sites, told Ars on Saturday morning that, in the 21 years they operated, fewer than 107,000 people posted to them. He said he didn’t know how or why the almost 98-megabyte file contained more than 12 times that many email addresses, and he hasn’t had time to examine a copy of the database that he received on Friday night.

Still, three days after receiving notification of the hack, Angelini finally confirmed the breach and took down the sites on early Saturday morning. A notice on the just-shuttered sites warns users to change passwords on other sites, especially if they match the passwords used on the hacked sites.

“We will not being going back online unless this gets fixed, even if it means we close the doors forever,” Angelini wrote in an email. It “doesn't matter if we are talking about 29,312 passwords, 77,000 passwords, or 1.2 million or the actual number, which is probably in between. And as you can see, we are starting to encourage our users to change all the passwords everywhere.”

Besides wifelovers.com, the other affected sites are: asiansex4u.com, bbwsex4u.com, indiansex4u.com, nudeafrica.com, nudelatins.com, nudemen.com, and wifeposter.com. The sites offer a variety of pictures that members say show their spouses. It's not clear that all of the affected spouses gave their consent to have their intimate images made available online.

Whatever the number of real accounts exposed, this latest hack harkens back to the 2015 breach of the Ashley Madison dating service for cheaters. That earlier breach made public the intimate details of 36 million account holders. Within weeks, affected users were receiving emails from unknown people threatening to notify spouses of the irinfidelities unless the users paid hefty ransoms. Reports of at least two member suicides soon surfaced.

In many respects, the most recent breach is more limited than the hack of Ashley Madison. Whereas the 100GB of data exposed by the Ashley Madison hack included users’ street addresses, partial payment-card numbers, phone numbers, and records of almost 10 million transactions, the newer hack doesn’t involve any of those details. And even if all 1.2 million unique email addresses turn out to belong to real users, that’s still considerably fewer than the 36 million dumped by Ashley Madison.

“Devastating for people”

Still, a quick examination of the exposed database demonstrated to me the potential damage it could inflict. Users who posted to the site were allowed to publicly link their accounts to one email address while associating a different, private email address to their accounts. A Web search of some of these private email addresses quickly returned accounts on Instagram, Amazon, and other big sites that gave the users’ first and last names, geographic location, and information about hobbies, family members, and other personal details. The name one user gave wasn’t his real name, but it did match usernames he used publicly on a half-dozen other sites.

“This incident is a huge privacy violation, and it could be devastating for people like this guy if he’s outed (or, I assume, if his wife founds out),” Troy Hunt, operator of the Have I Been Pwned breach-disclosure service, told Ars.

Ars worked with Hunt to confirm the breach and track down and notify the owner of the sites so he could take them down. Normally, Have I Been Pwned makes exposed email addresses available through a publicly available search engine. As was the case with the Ashley Madison disclosure, affected email addresses will be kept private. People who want to know if their address was exposed will first have to register with Have I Been Pwned and prove they have control of the email account they’re inquiring about.

Remember Descrypt?

Also concerning is the exposed password data, which is protected by a hashing algorithm so weak and obsolete that it took password cracking expert Jens Steube just seven minutes to recognize the hashing scheme and decipher a given hash.

13 chars base64 usually descrypt (-m 1500 in hashcat)

VTB3d1ZQYv.7o:ecotone

— hashcat (@hashcat) October 18, 2018

Known as Descrypt, the hash function was created in 1979 and is based on the old Data Encryption Standard. Descrypt provided improvements designed at the time to make hashes less susceptible to cracking. For instance, it added cryptographic salt to prevent identical plaintext inputs from having the same hash. It also subjected plaintext inputs to multiple iterations to increase the time and computation required to crack the outputted hashes. But by 2018 standards, Descrypt is woefully inadequate. It provides just 12 bits of salt, uses only the first eight characters of a chosen password, and suffers other more-nuanced limitations.

“The algorithm is quite literally ancient by modern standards, designed 40 years ago, and fully deprecated 20 years ago,” Jeremi M. Gosney, a password security expert and CEO of password-cracking firm Terahash, told Ars. “It is salted, but the salt space is very small, so there will be thousands of hashes that share the same salt, which means you’re not getting the full benefit from salting.”

By limiting passwords to just eight characters, Descrypt makes it nearly impossible to use strong passwords. And while the 25 iterations requires about 26 more time to crack than a password protected by the MD5 algorithm, the use of GPU-based hardware makes it easy and fast to recover the underlying plaintext, Gosney said. Manuals, such as this one, make clear Descrypt should no longer be used.

The exposed hashes threaten users who may have used the same passwords to protect other accounts. As mentioned earlier, people who had accounts on any of the eight hacked websites should examine the passwords they’re using on other sites to make sure they’re not exposed. Have I Been Pwned plans to disclose the breach soon. People who want to know if their personal information was leaked should register with the breach-notification service now and check back over the next day or so.

Legal liability

The hack underscores the risks and potential legal liability that comes from allowing personal data to accumulate over decades without regularly updating the software used to secure it. Angelini, the owner of the hacked sites, said in an email that, over the past two years, he has been involved in a dispute with a family member.

“She is pretty computer savvy, and last year I required a restraining order against her,” he wrote. “I wonder if this was the same person” who hacked the sites, he adds. Angelini, meanwhile, held out the sites as little more than hobbyist projects.

“First, we are a very small company; we do not have a lot of money,” he wrote. “Last year, we made $22,000. I am telling you this so you know we are not in this to make a ton of money. The message board has been operating for 20 years; we try hard to operate in a legal and safe environment. At this moment, I am overwhelmed that this happened. Thank you.”

Read Comments

President Nixon 45 years ago precipitated the departure of the attorney general, deputy attorney general and Watergate special prosecutor as the criminal investigation of his administration escalated.

(Image credit: Henry Burroughs/AP)

Halo of the Cat s Eye Not a Falcon 9 rocket launch after sunset, the Cat's Eye Nebula (NGC 6543) is one of the best known planetary nebulae in the sky. Its haunting symmetries are seen in the very central region of this composited picture, processed to reveal an enormous but extremely faint halo of gaseous material, over three light-years across. Made with data from ground- and space-based telescopes it shows the extended emission which surrounds the brighter, familiar planetary nebula. Planetary nebulae have long been appreciated as a final phase in the life of a sun-like star. But only more recently have some planetaries been found to have halos like this one, likely formed of material shrugged off during earlier active episodes in the star's evolution. While the planetary nebula phase is thought to last for around 10,000 years, astronomers estimate the outer filamentary portions of this halo to be 50,000 to 90,000 years old.

Enlarge / The Cambodian city of Angkor was once the largest in the world until vast swathes of the population decamped in the 15th century. Its famous temple, Angkor Wat (above), survived. (credit: Stefan Irvine/LightRocket/Getty Images)

The Cambodian city of Angkor was once the largest in the world... then the vast majority of its inhabitants suddenly decamped in the 15th century to a region near the modern city of Phnom Penh. Historians have put forth several theories about why this mass exodus occurred. A new paper in Science Advances argues that one major contributing factor was an overloaded water distribution system, exacerbated by extreme swings in the climate.

Angkor dates back to around 802 CE. Its vast network of canals, moats, embankments, and reservoirs developed over the next 600 years, helping distribute vital water resources for such uses as irrigation and to help control occasional flooding. By the end of the 11th century, the system bore all the features of a complex network, with thousands of interconnected individual components heavily dependent on each other.

Such a configuration, hovering at or near the so-called critical point, is ideal for the effective flow of resources, whether we're talking about water, electricity (power grids), traffic, the spread of disease, or information (the stock market and the Internet). The tradeoff is that it can become much more sensitive to even tiny perturbations—so much so that a small outage in one part of the network can trigger a sudden network-wide cascading failure.

That's what a team of researchers from the University of Sydney think happened to Angkor. Sure, the Siamese sacked the city in 1431 CE, but most historians believe that event alone would not have been sufficient to drive most of the population from the city. The area had also suffered decades-long drought around the same time, followed by a period of unusually intense summer monsoons. According to the scientists, these extreme climate shifts critically damaged the water distribution infrastructure.

"The water management infrastructure of Angkor had been developed over centuries, becoming very large, tightly interconnected, and dependent on older and aging components," says co-author Mikhail Prokopenko, director of the Complex Systems Research Group at the University of Sydney. "The change in the middle of the 14th century CE, from prolonged drought to particularly wet years, put too much stress on this complex network, making the water distribution unstable."

Using archaeological maps of the region's water distribution system as it existed in the middle of the 14th century, Prokopenko and his colleagues built a mathematical model based on erosion and sedimentation dynamics. Their goal was to identify the particular areas in the network that were most vulnerable to catastrophic failure.

Their model network had 1013 edges (including excavated canals, embankments, dikes, and so forth serving to control and direct the flow of water) and 617 nodes (canal confluences or bifurcations, reservoirs, temple moats), which represent points at which edges meet or terminate. They found that the damage was most severe upstream, in areas that served as primary hubs, akin to major airline hubs like Chicago's O'Hare Airport. If O'Hare shuts down for some reason, the delays will ripple through the entire network, because it is a central transfer point. This is likely what happened in Angkor with the extreme flooding during heavier than usual monsoon seasons, following on the heels of decades of drought.

There is a lesson here for our modern-day cities in the fate of Angkor. Our cities are larger, more complex—and our infrastructure is aging rapidly. This makes cities more vulnerable to the rippling effects brought on by climate change, most notably an increase in extreme weather events. "If we don't build resilience into our critical infrastructure, we may face severe and lasting disruptions to our civil systems, that can be intensified by external shocks and threaten our environment and economy," says Prokopenko.

DOI: Science Advances, 2018. 10.1126/sciadv.aau4029  (About DOIs).

Read Comments