4
$\begingroup$

Is it possible for a client to send a blinded password to a server, so that the server does key derivation+stretching on that blinded value, but the key can then be unblinded by the client?

Clarifications

I'm using "blinded" the way it is used in an "oblivious pseudorandom function" (OPRF) like Ristretto255.

Usually I see Argon2id called a key derivation function, but in some contexts there is another key derivation function in play, and Argon2id is referred to as a key stretching function. I'm happy to learn the formal precise differences between "derivation" and "stretching", but what I care about making oblivious to the secret is the parts of Argon2id with deliberately large costs (or anything with comparable security), regardless of what we call that.

Motivation

So we already have "oblivious salting" by using an oblivious pseudorandom function (OPRF). This is used in asymmetric password authentication schemes (where the client never shares the password with the server), to allow the server to provide a salt without giving it freely to any attacker who "asks" by starting an attempted login. See for example the OPAQUE protocol.

But one downside of something like OPAQUE versus traditional password logins, is that since key stretching runs on the client instead of the server, parameters for the KDF/KSF have to be weak enough that the weakest client can still provide acceptably fast user experience when logging in.

For example, Argon2id with one lane, 16 MiB of memory, and three iterations, in the browser, takes ~250ms on a Pixel 5, but ~1400ms on a Samsung Galaxy 5s.

From a security perspective, I'd love to throw even larger parameters into Argon2id, even though OWASP recommendations considers my parameters above the acceptably safe minimum when I last checked.

But from a user experience perspective, I would hate to have a user login from slower hardware or a resource-constrained multitasking system and have to sit there for many seconds during login while their device struggles through a high cost Argon2id execution.

(And the same user might log in from devices with large capability disparities - one user might have a high-end gaming desktop but not want anything above a cheap low-end smartphone - if they're logging into the same website or app from both, then doing key stretching on the client means you still only get the security of the weakest key stretching parameters that give an acceptable performance and security balance.)

So! If we could do an oblivious KDF/KSF, then we can still have users benefit from a server with expensive hardware investment which can run the KDF/KSF with much larger costs than would be reasonably fast on typical clients.

$\endgroup$
2
  • $\begingroup$ IMHO, shifting the burden calculation is a good attack vector for DDOS. $\endgroup$
    – tur11ng
    Jun 6, 2022 at 22:24
  • $\begingroup$ @JAAAY of course, but not shifting the burden is a good vector for management lowering security for user credentials once they realize your users are deciding to use another website because yours takes too long to log in. So you're right but it's a trade-off. That (D)DoS protection isn't free - it costs either worse user experience or worse security for user credentials or needing higher specs for the hardware your users use. $\endgroup$
    – mtraceur
    Oct 19, 2022 at 19:18

1 Answer 1

6
$\begingroup$

For a scenario such as PAKE with a low-powered client and a high-powered server, Makwa offers a delegation feature, where the server performs the stretching part of the calculation. The server does not learn anything about the password. The amount of work on the client is less than an RSA signature and does not depend on the stretching factor.

Makwa is the only finalist of the Password Hashing Competition (which Argon2 won) that supports delegation.

Note that delegation is designed for password verification. It shifts the burden of the calculation on the verifier without letting the verifier know anything about the password other than whether it is correct, which it would need to know anyway (that's the whole point of authentication). Delegation can also be used for key stretching, in a scenario where a low-powered system has some data encrypted with a password-derived key using Makwa, and the user enters the password. The low-powered system can delegate the bulk of the Makwa calculation to a high-powered third party without risking the confidentiality of the password. However, as far as I know, it does need to trust the third party to perform the calculation correctly: I don't think it's possible to distinguish between a wrong password and a lying third party.

$\endgroup$
4
  • $\begingroup$ Thanks! That's really cool and I think I remember reading about that a couple years ago, but Makwa doesn't have the same resistance as Argon2 to various tradeoffs, like TMTO attacks, right? Is there a known scheme for achieving the same protections in combination with delegation? (Btw I already +1'ed right after you posted, but I'm giving it a couple days before accepting an answer.) $\endgroup$
    – mtraceur
    Jun 6, 2022 at 6:27
  • $\begingroup$ @mtraceur Makwa isn't memory-hard. So it may be possible to design specialized circuits that are cheaper at cracking it than a typical verifier — ideally, for a PBKDF, you'd want the typical verifier to be the optimal hardware design for computing it. The designer of Makwa contends that this is not a major problem. Especially since delegation allows it to be offloaded to optimal hardware even if you're a legitimate verifier. Makwa was the only PHC finalist with delegation, so there aren't any alternatives with the same level of vetting. $\endgroup$ Jun 6, 2022 at 10:15
  • $\begingroup$ That's a great point about offloading allowing for always using optimal hardware, in principle. In practice if I am trying to implement some app or website, how do I know as a simple developer if/when I need to order custom hardware which implements Makwa optimally? In other words, how do we know how much more optimal specialized hardware would be (and therefore how much cost savings an attacker could get by investing in optimal hardware (and therefore if it's even practical to build a server using Makwa on off-the-shelf general-purpose hardware))? $\endgroup$
    – mtraceur
    Jun 6, 2022 at 18:44
  • 1
    $\begingroup$ @mtraceur According to the Makwa specification § 5.6, the PC architecture is the cheapest platform to break Makwa unless an optimized platform becomes mass-produced: FPGA (or perhaps a dedicated ASIC?) can have better performance but they would have a huge upfront cost. The analysis is close to a decade old and may no longer be true today, but I doubt it's changed fundamentally. You only gain a performance advantage by delegating from typical server hardware if it's widespread enough so that the delegate runs on off-the-shelf hardware. $\endgroup$ Jun 6, 2022 at 20:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.