12 ms·
Let’s Talk about PAKE (2018)
- tptacek 5y agoRelatedly, a recent post on SRP (the most commonly used PAKE) and how it's worse in all cases than PAKEs derived from SPEKE: https://tobtu.com/blog/2021/10/srp-is-now-deprecated/ https://tobtu.com/blog/2021/10/srp-is-now-deprecated/
- ignoramous 5y agoCurious to know your thoughts on: "...what are [some] problems [tptacek has] with password-authenticated key exchange?" https://news.ycombinator.com/item?id=18260407 https://news.ycombinator.com/item?id=18260407 Thanks.
- cvwright 5y agoSo the two main problems with SRP, according to this post, are: 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.
- tptacek 5y agoI don't understand what you're trying to say here. It seems like you're saying that SRP is OK as long as you don't use SRP, but rather a modern PAKE, and then call it SRP. 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.
- cvwright 5y ago> It seems like you're saying that SRP is OK as long as you don't use SRP, but rather a modern PAKE, and then call it SRP. 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.
- tptacek 5y agoNo, that's not what the article is saying. It's saying that in addition to (1) being based on old multiplicative group cryptography, (2) lacking a security proof, and (3) not being built on a construction we already trust (Noise-KN) and instead its own weird protocol, it's also misuse-prone, because an easy state machine misstep that lots of people make gets you a server that allows offline password guesses. 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.
- cvwright 5y agoSRP never got a security proof?!? Wtf man? I guess standards for publication have, uh, evolved a bit over the past 20 years. Thanks for the explanation, this was helpful.
- georgelyon 5y agoThere's some dust on it, but I made a proof-of-concept OPAQUE implementation some years back (disclaimer: this was done for educational, not security, purposes). The README has some good discussion of the various components of OPAQUE, and I'd argue the code (mostly C) is quite readable. If folks are interested, I'd encourage them to take a look: https://github.com/GeorgeLyon/Opaque https://github.com/GeorgeLyon/Opaque.
- kodablah 5y agoA few years ago, I saw this article and wrote https://github.com/cretz/gopaque https://github.com/cretz/gopaque as a learning exercise (meaning I am no cryptographer, code has not been vetted, probably outdated, etc). See https://pkg.go.dev/github.com/cretz/gopaque/gopaque https://pkg.go.dev/github.com/cretz/gopaque/gopaque for docs on how it abstracts registration and authentication.
- mellosouls 5y ago(2018)
- ttyprintk 5y agoPrior commentary: https://news.ycombinator.com/item?id=18259393 https://news.ycombinator.com/item?id=18259393
- dang 5y agoThanks! Macroexpanded: Let’s talk about PAKE - https://news.ycombinator.com/item?id=18259393 https://news.ycombinator.com/item?id=18259393 - Oct 2018 (98 comments)
- dang 5y agoAdded. Thanks!
- collegeburner 5y agoWhy did he recommend OPAQUE over others like SPAKE2? 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?
- tialaramex 5y agoI don't know why OPAQUE was chosen in this 2018 article, but OPAQUE was eventually selected as CFRG's preferred asymmetric PAKE 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.
- sc00bz 5y agoOPAQUE was chosen because it was new and had the new "no precomputation" property. Which can be added to better PAKEs by adding an OPRF vs just sending the salt. OPRFs can be added without adding an extra trips to the protocol. > 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".
- RcouF1uZ4gsC 5y agoOne of the reasons I love reading about crypto algorithms is that there is a certain elegance and the pleasure of solving an intellectual puzzle when you read them. 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.
- bastawhiz 5y agoI probably would never try to implement this on my own website. My login pages don't use JS, so unless the browser did the work for me, it's complexity that I'm never going to understand running on the most crucial page on my site. 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.
- tptacek 5y agoIt's really hard to come up with a sane reason why you would ever implement a PAKE with a browser HTTPS application. Probably the best-known use of any PAKE is in Magic Wormhole, where the PAKE passphrase (auto-generated) is a fundamental part of the trust model, and the application itself never touches a browser. 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).
- nly 5y agoIndeed. It's hard to come up with use cases where a chosen, long-term low entropy secret is more suitable than alternatives like: 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).
- GoblinSlayer 5y agoA mentioned use case is twitter logging requests on server side.
- nly 5y agoFrank Denis has an elliptic curve PAKE built on top of libsodium called CPACE. The implementation is less than 150 lines of C https://github.com/jedisct1/cpace https://github.com/jedisct1/cpace
- makeworld 5y agoLibrary for PAKE (but not OPAQUE specifically) in Go: https://github.com/schollz/pake https://github.com/schollz/pake
- sc00bz 5y agoThis was recently broken then fixed. I heard about it because of that then looked at it and broke it again. I only checked one thing and it was wrong. I would not trust this. Also SPEKE based PAKEs are better.
- boardwaalk 5y agoFun fact: World of Warcraft used SRP4 for a long while (I'm not sure if it does anymore). That's a pretty big deployment. 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.
- sc00bz 5y agoSuper fun fact: Blizzard's (ie World of Warcraft's) safe prime was 256 bits which was known to be broken at the time, but no one really knew this until they got hacked and their database got leaked. 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).
- baby 5y agoshameless plug: I wrote some ELI5 explanations on some of these technologies: - SRP: https://www.cryptologie.net/article/503/user-authentication-with-passwords-whats-srp/ https://www.cryptologie.net/article/503/user-authentication-... - SPAKE2: https://www.cryptologie.net/article/490/whats-a-symmetric-password-authenticated-key-exchange-spake-and-how-does-spake2-work/ https://www.cryptologie.net/article/490/whats-a-symmetric-pa... - OPAQUE: https://livebook.manning.com/book/real-world-cryptography/chapter-11/61 https://livebook.manning.com/book/real-world-cryptography/ch... - CPACE: https://livebook.manning.com/book/real-world-cryptography/chapter-11/184 https://livebook.manning.com/book/real-world-cryptography/ch...
- sedatk 5y agoSo, OPAQUE stands for what? Or, do we not care anymore? :) Apparently, it's based on "aPAKE" which stands for "Asymmetric PAKE", but I guess OPAQUE is an acronym that sounds cool.
- tialaramex 5y agoOPAQUE was chosen because the name OPAKE already existed, and it's an Oblivious PAKE. So, it does not form an acronym.
- sedatk 5y agoIf it's not an acronym, why is it all caps?
- tialaramex 5y agoWell, if it was just named opaque that would be confusing because that's a word meaning the opposite of transparent. 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).
- sc00bz 5y ago> Apparently, it's based on "aPAKE" which stands for "Asymmetric PAKE" 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)
- gnachman 5y agoWhatsApp’s encrypted backups use OPAQUE. Source: https://scontent.whatsapp.net/v/t39.8562-34/241394876_546674233234181_8907137889500301879_n.pdf/WhatsApp_Security_Encrypted_Backups_Whitepaper.pdf?ccb=1-5&_nc_sid=2fbf2a&_nc_ohc=Lm8MOEVgHlkAX_raq6d&_nc_ht=scontent.whatsapp.net&oh=e8e39815f571a8fdf54600ed4726a13e&oe=6177B67C https://scontent.whatsapp.net/v/t39.8562-34/241394876_546674...
- bullen 5y agoWhat is the benefit of PAKE over this: https://datatracker.ietf.org/doc/html/rfc2289 https://datatracker.ietf.org/doc/html/rfc2289
- sc00bz 5y agoPAKEs are secure over insecure channels. Also I'm pretty sure for RFC2289 the server stores a password equivalent. If you neither care about creating an encrypted session nor being secure over an insecure channel, then you should use SCRAM. With SCRAM, the server stores a password hash equivalent. Meaning an attacker needs to crack the password before they can login as them.
- deleted 5y ago[deleted]
- jedisct1 5y agoBesides pairing devices, there isn't a lot of actual use cases for balanced PAKEs. 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.