Let’s Talk about PAKE (2018)
blog.cryptographyengineering.com
blog.cryptographyengineering.com
Moreover, though, users run so much shit in their browsers. More than half of the logged errors on my site are from user scripts and browser extension content scripts doing lord knows what. They can all just slurp the value out of the DOM, no questions asked. Never mind my CSP, HTTPS, and all of the effort I go to making my server environment secure and safe. The weakest link is not the password getting sent to my servers (over HTTPS), it's the utter free-for-all happening on the page in the first place.
It's a problem with PAKEs that they're kind of neat to think about and play with, so people look for things to stick them onto. They're usually not the answer, which is why you don't see them used all that often, and why they're used almost exclusively in custom protocol settings.
(It doesn't help PAKE adoption that most custom protocols are better served by standard authenticated key exchanges based on real cryptographic secrets, rather than passphrases).
1) Factory paired devices
2) Pairing via ephemeral key pairs with out-of-band verification of a low entropy hash/fingerprint to prevent active MITM.
3) Straight up TOFU (trust on first use) pairing (and just praying MITM doesn't happen on first use).
The only case comes to mind is one where one device, although still physically trusted, has no persistent memory at all (and so can't store any keys).
The major reason HTTP Auth failed, despite the primitive crypto, is the bad client side UX.
I would argue the reason http auth failed is that there is no means of logging out, part of that is ui, part of that is protocol.
The server has a password derivative stored. An SRP verifier for instance is computed from the password hash, so if the server is compromised the hacker can immediate impersonate the server or the password can be brute-forced offline.
I believe OPAQUE is the same, just with stronger (slower) password hash functions in the mix.
Also, as it is you can brute force hashes offline as well. Yes, the original specification has become weak over time, but so have 3des and md5. SRP never was heavily used and as such new versions arent common; it's not inherently a problem with the concept of password-based mutual authentication.
Look at all the places in a standard authentication flow where the plaintext password is exposed:
- Any TLS-stripping middleboxes on the client's network. (My personal security nightmare is that someone finds a vulnerability in one of those, and hacks them to scrape anything that looks like a password.) BTW, remember when Kazakhstan did this to their entire country?
- Any TLS-terminating load balancer/front-end-server/etc at the server side of the network.
- Potentially between the front-end server and a backend that does the actual authentication, depending on how traffic is passed there.
- Finally, the server that's doing the authentication -- the password will at the very least be exposed in memory there, so anyone who can read its memory (or modify the server code to leak the passwords) can collect passwords in plaintext.
I'm less concerned about corporate level MITM since in those scenarios the MITM already owns the clients. Regardless of protocol, it's a lost cause there.
In Matrix E2EE chat, every user winds up with a ton of different E2EE sessions and thus a ton of different keys that they need to store. (This part of the protocol is unnecessarily complicated IMO, but it's too late to change it now.)
The key to making multi-device support work in practice has been to store an encrypted archive of all the keys for all your sessions, in encrypted form on the server. Where do you get the key for this encryption? It seems the only workable option is to derive it from a passphrase, since the user might choose to log in from a new device (or a new browser) at any moment. So the secret has to live only in the user's head.
But now each user has to remember two passwords: (1) their login password and (2) their encrypted key backup password. Do we really believe that they will pick two totally different, independent passwords??? And if they don't, then in what way are the E2EE keys protected from the server?
So it would be great if we could prevent the server ever learning the login password. For that reason, a few of us random volunteers have been looking at adding SRP or SCRAM or something to Matrix.
It sounds like what you want is a password-based KDF, to derive keys clientside for the encrypted bundle.
(SRP is pretty much dead now, for what it's worth).
> It sounds like what you want is a password-based KDF, to derive keys clientside for the encrypted bundle.
The encrypted blob containing E2EE keys is encrypted with a symmetric key that's derived from PBKDF2 on a passphrase.
The problem is that standard password-based authentication exposes the login password to the server every time the user logs in.
So if the user is lazy and uses the same password for both purposes, then the server could very easily derive the key and decrypt the blob that contains all of the E2EE keys.
Even if the user picks slightly different passwords, e.g. "password1" vs "password2", the server has a huge advantage over your standard brute force attacker.
> (SRP is pretty much dead now, for what it's worth).
:shrug: Was it ever really alive?
Like the "proper" answer is rethink your protocol, have 1 password and make everything not suck.
Minimum (and achievable) job? Client side hash.
Yes it's sh%tty JS crypto in the web case but you have legacy reasons you don't want plaintext even over SSL and you're not going to promise "military grade crypto" to anyone. It's explicable. You can use existing decently reviewed JS libs at least. Any kind of PAKE was gonna be weird JS libraries for web folks anyway.
Yes you're exposed to all the CDNs your UIs use but you were exposed to them anyway.
OK yes tptacek JS crypto is bad and the browser is the worst runtime ever but it's still orders of magnitude less code than needed to make a functional web ui for a chat client, it's pretty bounded, testable and the worst case screwup is not much different than sending your password to the server in plaintext. Which is current state.
The server can store a sha256 of the PBKDF2 output of your client hashing process or whatevs? It's likely to be harder to crack than the key blob you stored on servers already. From a data at rest and in flight standpoint this is at least the same security you get from a PAKE but way easier for everyone to understand. It's one-round, no one needs to think, on server side you can still politely upgrade with zero user interaction. Clients don't have to use fringe crypto supported by one person on github. (Good luck finding a cocoa pod for any kind of PAKE).
It will get weird sending salts to clients if you care about username enumeration, feels like the only way for that not to be stateful in a bad way on your servers is if you derive it from email or login id or something (aka don't actually need to store or send). Not sure how you would resolve that if your UX needs to support multiple login identifiers. That would be hard because you have secret but pre-auth information (relationship between names), and it would require its own sort of thinking.
I have zero knowledge of matrix and so this will probably go down as an embarassing comment. The things I don't know here outweigh the things I do, so this is probably bad advice.
I do want to say, sometimes you just have to go low tech and the dumb thing is the best answer. Sometimes you have to endure raised eyebrows and not doing the sexy thing for community and engineering reasons.
Props for shipping and maintaining a thing that people use and care about. That is hard. Everyone got raised eyebrows but no one got MRs.
Before we started working on the PAKE thing, I actually kludged together something similar in my own client:
I think you need to start by very clearly defining the security model you are trying to design, and then start talking about constructions to throw at it.
I don't know what the shrug means, but you shouldn't use SRP in a 2021 design.
> you shouldn’t use SRP in a 2021 design
Ok I guess I’ll take your word for it. Which PAKE should we use instead? This is the perfect time to change our plans, since we haven’t really built anything yet.
So the main thing is that apparently using a PAKE is not sufficient by itself. Not revealing the password at login time only solves part of the problem.
The second requirement is that the PAKE’s “password related string” that it learns and stores must be something that does not reveal (significant information about) the password itself.
I had assumed that that was a baseline “table stakes” kind of requirement for an authentication protocol in the 2020’s, but apparently that’s not part of the definition here(?)
As to your comment about using the same password to create the verifier and the encryption key, I agree it’s not ideal. But in the real world, what practical alternative do we have?
We have password hashing functions that are pretty good at making password cracking impractical. We should use them and trust them to do their job.
As long as the verifier comes from a hash that makes finding preimages prohibitively expensive (ie, a PHF), then it seems like there’s room to work here.
Or if you have better ideas, I would love to hear them. (Not being snarky here - it would actually be good to get input from someone who works on this stuff.)
Maybe I'm unclear about the application here! But what I'm reading is a proposal in which the deployment of a PAKE could make the system drastically less secure on the whole.
What gives? Are we just using different defaults or clients or something?
AFAIK, there are two ways to validate a new device in Matrix.
It sounds like you're describing the interactive device validation procedure. After that, your two devices trust each other, and the old device can "cross sign" the public key of your new device, so others can trust it too.
Personally for me, even with cross-signing, I was still getting a significant number of messages that failed to decrypt. Usually I think the problem was that one of my devices wasn't around to receive the original version of some key. And for whatever reason, even with cross-signing, it wasn't getting the keys from my other devices. For example, maybe my other devices were offline at the time.
The fix for me was to go the passphrase route. Now, regardless of what device I'm on, the passphrase gets me access to all of my secrets via the encrypted blob on the server.
Consider the Twitter issue mentioned in the article. Logging inputs is a very common thing and is often important for security auditing later. But if you add it, you need to make sure you're censoring passwords. If you do that wrong, or something around it later changes, you're leaking plaintext passwords to your logs.
And that's just one angle. There's also db compromise. DB snapshot/backup compromise. There's a dozen more dangerous attack surfaces we haven't even thought of yet.
PAKE means that no matter what you do, you can't leak a plaintext password because you don't know it. That's why it's powerful.
Those are tradeoffs, and the purism of never handling red data doesn't necessarily offset its costs. Especially in a small organization. If you're going to spend N hours on security, what's going to give you the biggest bang for your buck? PAKE would hardly crack my top 20, honestly. Are you confident your deps are updated quickly after CVEs are published? Is your server's kernel up to date? Are you sure your security group configuration is correct right now? Do you have lint rules to protect against XSS issues? PAKE makes a really bad issue slightly less bad, but there's thousands of things that you could be doing that meaningfully prevent issues in the first place.
If 0.5% of your users get a JavaScript exception from the PAKE library, are you confident that you can fix it? What's the cost of those users not being able to log in (and/or churning)?
When it comes to low hanging fruit at most small businesses, handling of plaintext passwords delivered over a secure connection is small potatoes compared to the myriad of other serious security challenges you're likely facing.
- SRP: https://www.cryptologie.net/article/503/user-authentication-...
- SPAKE2: https://www.cryptologie.net/article/490/whats-a-symmetric-pa...
- OPAQUE: https://livebook.manning.com/book/real-world-cryptography/ch...
- CPACE: https://livebook.manning.com/book/real-world-cryptography/ch...
https://news.ycombinator.com/item?id=18260407
Thanks.
1. It exposes the salt and verifier to the adversary, enabling a brute-force search for the password
2. It relies on the discrete log problem, and is thus vulnerable to quantum computers
In practice, I don't buy the argument that either one of these is a deal breaker, as long as you do SRP in a "modern" way, ie you're not tied verbatim to some 1997 version of the spec.
For #1, if you hash the password with a decent password hashing function (bcrypt/scrypt/argon2) with a reasonable work factor, then only the dumbest/worst passwords are at risk of being cracked in any reasonable amount of time. Notice that the password hashing happens entirely on the client, so you can crank that work factor up pretty high.
For #2, if somebody builds a huge quantum computer big enough to take on these problems, then we are so freaking screwed in so many other ways. SRP logins will be the least of our concerns.
Not to take away from EKE and its derivatives in any way. I've been a huge fan of the original Bellovin & Merritt construction since I first read about it 20 years ago.
You're certainly not correct that the article is saying SRP is flawed because it "relies on the discrete log problem", as ECDLP-based PAKEs are also vulnerable to QC.
No, that is not what I'm saying. The SRP paper says "Use a hash function to hash the password". When SRP was new, that might plausibly have been MD5, and if not, then probably something else like SHA-1 that is now unsafe. I'm saying, in 2021 use a hash function that doesn't suck for hashing passwords, like bcrypt or argon.
> You're certainly not correct that the article is saying SRP is flawed because it "relies on the discrete log problem", as ECDLP-based PAKEs are also vulnerable to QC.
Hmm good point. I must have interpreted the whole "Quantum annoyance" thing too strongly then.
Further, there's simply no reason to use it; there are better, equivalently simple protocols available. Even if you wanted to use simple multiplicative group DH math, the article points out, you could just instantiate BS-SPEKE on it; it even provides the formulae.
Nobody has "broken" SRP6a, just like nobody has really "broken" DES-EDE, or HMAC-MD5. But you clearly shouldn't be using any of them.
I guess standards for publication have, uh, evolved a bit over the past 20 years.
Thanks for the explanation, this was helpful.
I felt this way when I first read about RSA and public key encryption, and Shamir's secret sharing algorithm
This article gave me the same feeling with regards to OPAQUE.
I don't know that I will ever personally implement the algorithm, but just knowing about it is gives me a certain nerdy pleasure.
Thanks for the great writeup.
Some PAKEs have the interesting property that passwords are never sent to servers.
Which is definitely a good thing. Insider threats and excessive logging are real threats, and passwords can be leaked before being hashed.
However, these PAKEs still don't prevent brute force attacks. Sure, every attempt requires an interactive protocol. But if you are operating the server, or have a copy of the database (including keys for salt-hiding PAKEs), that can be done locally, and the PAKE doesn't provide any value.
What I would love to see is a standard scheme that requires at least a third party. A multi-party computation, relying on servers operated by different entities, that don't know about each other's secrets, and can be semi-honest. So, if any of these parties gets compromised (even internally), this doesn't reveal anything about passwords or the data held by the other party.
All the pieces to build this exist, but an actual protocol doesn't.
But this article will be useful; I have something unreleased that does password authentication by dumping the salt to the user, just out of ease of implementation. I'll probably take another look at it.
Super-duper fun fact: Before Blizzard moved to SRP, they fubared SHA1 by shifting 1 by a variable vs shifting a variable by 1. This meant that after the shift it was one of 32 values. Which let's one crack or collide the "XSHA1" hash in seconds. I was going to say just google "XSHA1" and you'll get my website with attack code but I think Google de-listed it... maybe I should link to Github vs a zip with code and a .exe... or make my site mobile friendly (for better ranking).
P.S. I thought Blizzard used SRP6a... although I'm not familiar with every SRP version. I looked at the early versions of SRP (I think I got to v3) and they were obviously broken (from the understanding of what a PAKE threat model should be).
Re: Green's question on why it is not more widely deployed, I assume it is since TLS already is common and PAKE would be an additional layer of encryption on this? Or is his proposal use PAKE for auth then discard keys, use TLS normally?
PAKEs are a fairly specialist protocol. If you don't need to use human memorable passwords then you should not do so. There are cases where you can't bootstrap some other means but you do have, or can agree, a human memorable password and PAKEs are a good choice then.
So there are lots of problems where a PAKE would be better than what you have today, but what you have today is rubbish and it makes more sense to do the Right Thing™ instead.
I don't want Hacker News to authenticate me with a PAKE instead of crummy password-in-a-form technology, the right thing is WebAuthn.
Even for one of the places a PAKE is commonly used today WiFi (WPA3) this is true. The PAKE is used to make the crummy WiFi shared password scheme less broken, and it's an improvement over prior approaches. But just not doing PSKs at all is better. An EduROAM participant from say, CalTech using WiFi on a trip to Rome isn't relying on a PAKE, they are doing full user authentication proxied to CalTech to authorise access to the Roman WiFi.
> the right thing is WebAuthn.
True, but if a good PAKE is added to TLS (it won't) then your logged-in sessions are protected by needing to solve a DLP for every password guess (ie "quantum annoyance", a property of a good PAKE). This does assume quantum computers become a thing.
> WiFi (WPA3)
They used the worst PAKE available. They even used the wrong class of PAKEs (balanced vs unbalanced (or augmented "aPAKE")).
> and it's an improvement over prior approaches.
No, it was broken but maybe it's fixed? The original version is basically "WEP 2.0" and they likely have backwards compatibility because "oops, we published a spec with a known to be broken PAKE... but it was an IEEE PAKE, don't blame us".
P.S. SPAKE2 is a balanced PAKE vs augmented PAKE (or unbalanced PAKE) like OPAQUE and SPAKE2+ (and SPAKE2+EE).
Naming things is hard for most people. Where some people are imaginative enough to name their stream cipher ChaCha20, the best you can expect from many engineers is something like PADMÉ (a padding scheme).
It is an "aPAKE" which stands for "augmented PAKE". An aPAKE is client-server vs peer-to-peer. The original PAKE was peer-to-peer then augmented to be client-server. A peer-to-peer PAKE is called PAKE or balanced PAKE, but "PAKE" could be use generally to mean client-server and/or peer-to-peer PAKE. aPAKEs are sometimes called unbalanced PAKEs.
I've heard people say asymmetric PAKE and symmetric PAKE (for client-server and peer-to-peer), but this causes confusion with asymmetric and symmetric cryptography. Thus should not be used. And was likely from a misunderstanding around what "a" meant in "aPAKE".
Oh there is a "double augmented PAKE" which I recently figured out a use case for that, WiFi. Also technically OPAQUE is a "double augmented PAKE", but only defined as an augmented PAKE.
(Sorry for the history lesson)
Let’s talk about PAKE - https://news.ycombinator.com/item?id=18259393 - Oct 2018 (98 comments)