Open Bug 1320222 Opened 8 years ago Updated 6 months ago

Review FxA client-side key stretching parameters

Categories

(Cloud Services :: Server: Firefox Accounts, defect)

Product:
Cloud Services
Component:
Server: Firefox Accounts
Type:
defect
Priority:
Not set
Severity:
normal

Tracking

(Not tracked)

People

(Reporter: rfkelly, Unassigned)

References

Details

(Keywords: sec-want) 

From https://github.com/mozilla/fxa-cure53/issues/14

----

On the client-side PBKDF2 with 1000 iterations is used for key stretching. This is done to add a work factor to attempts at brute-forcing the password and to obfuscate the password as it is sent to the server. The password can’t be sent in clear text to the server, since the password is used both for authentication, authPW, and as a base for unwrapping the kB encryption key, unwrapBKey. The cleartext password can directly be used to reveal the kB key, while knowing the obfuscated password, authPW, should not aid an attacker without having to perform a brute-force attack.

However, 1000 iterations of PBKDF2 is not enough to add a significant work factor. PBKDF2 is easily parallelized and a single modern computer can compute millions of PBKDF2 passwords per second and billions of passwords in a day. Also, given that the salt is well known, an attacker can pre-compute a sizable rainbow table before hand, it would not be hard for an attacker to find the password given either authPW or wrap(kB).

This issue is the result of a tradeoff between security and efficiency. The current recommendation for stored PBKDF2 passwords is estimated at 256000 iterations, which may not be feasible on a client with limited resources. Further this attack assumes a very strong attacker capable of bypassing TLS, as is discussed in the security analysis. Finding a sweet spot in this tradeoff is dependent on the efficiency (or perceived inefficiency) of the weakest of the expected clients, therefore an exact recommendation on the number of iterations is not given.
The first step here needs to be to review the current situation, then we can decide on where to go from here.  Let's:

* Gather metrics on the performance of our current key-stretching params in practice.
* Revisit the calculations that :warner did in [1] and see how much the landscape has changed.

With that data in hand, we can either:

* Decide that things are OK as they are, and WONTFIX this bug.
* Decide on updated parameters, define a plan for migrating to them, and close this bug in favour of an implementation bug for said plan.

[1] https://wiki.mozilla.org/Identity/CryptoIdeas/01-PBKDF-scrypt#PBKDF_User.2FAttacker_Costs
Summary: [cure53] FXA-01-014 Weak client-side key stretching → Review client-side key stretching paramaters
Summary: Review client-side key stretching paramaters → Review FxA client-side key stretching paramaters
Chris, can you recommend someone internally who we could loop in for a second opinion on our current key-stretching setup?  I recall you pointing me in the direction of skilled crypto folks in the past.
Flags: needinfo?(ckarlof)
If you need some crypto expertise, I'd start with Richard Barnes. 

It's worth revisiting the security goals for the client side stretching. It's been a while since I debated this with Warner, but I feel that the main purpose of that initial stretching was to not completely hose people who went through the trouble of generating a random or otherwise pretty good password. E.g., if you use a 128 bit password, even a single round is probably enough to resist a TLS-compromising eavesdropper, but zero rounds would simply disclose it.

I don't feel there was a ever any notion that 1000 rounds would do anything for people who use weak passwords against TLS-level attackers.

Regardless, I feel it's worthwhile to re-review design choices periodically, so it would probably be a good idea to get a crypto re-review from Barnes or one of his delegates in the first half of 2017.
Flags: needinfo?(ckarlof)
> It's been a while since I debated this with Warner, but I feel that the main purpose of that 
> initial stretching was to not completely hose people who went through the trouble of generating
> a random or otherwise pretty good password.

Yeah, this matches my recollection as well, see e.g. this thread:

  https://github.com/mozilla/fxa-auth-server/issues/344#issuecomment-29043199
I can probably speak to this somewhat, if :ulfr and/or :rbarnes are okay with it?
Well I'd be happy to hear anyway :-)

It also occurred to me that I should put this link here for easy reference:

  https://github.com/mozilla/fxa-auth-server/wiki/onepw-protocol

It includes a diagram of the way we use both PBKDF2 and scrypt when manipulating and storing the password.
NIST recommends 10k rounds, but I personally think that this is a bit low.  Both 1Password (HMAC-SHA512) and LastPass use 100k (HMAC-SHA256) iterations, which I find to be a pretty good tradeoff between security and performance.  On my iPhone SE, my 1Password vault takes about .5-1s to unlock, which I think is reasonable considering it would be slower on a less modern phone.

256k rounds might be okay if you can ensure that every machine using FxA is an i5 or better from the last half decade, but it's going to be annoyingly slow otherwise.  LastPass (IIRC, I don't personally use it) allows *up* to 256k rounds but I don't believe it is their default.

After a certain point you kind of reach diminishing returns and you'd probably be better off detecting weak passwords and suggesting users use something more complicated (along with, obviously, not sharing passwords between FxA and other things).

My personal recommendation is 100k rounds of PBKDF2 using HMAC-SHA512, and from here out we track what the 1Password folks are doing over time.  But feel free to test on supported low-end Android phones and see if that's acceptable for whatever hard time requirements that FxA has set.
> After a certain point you kind of reach diminishing returns and you'd probably be better off detecting weak passwords and suggesting users use something more complicated (along with, obviously, not sharing passwords between FxA and other things).

To further elucidate on this, adding a single extra randomly chosen lower+uppercase alphanumerical character (keyspace=62) on the end of a given password is the equivalent of going from 10k iterations to 620k iterations.
I don't have any special expertise here.  I'm basically OK with anything NIST is OK, but I can get on board with being a little more conservative.  Doing 100k like LastPass / 1Password seems like a fine idea.  I don't think there's any appreciable difference between SHA-256 and SHA-512 in this case.

On the other hand, if we've got this patient on the operating table, why aren't we moving to something more modern like scrypt or Argon2?
> On the other hand, if we've got this patient on the operating table,
> why aren't we moving to something more modern like scrypt or Argon2?

Mostly because trying to do those in web content on a mobile device sounds pretty scary :-)
(In reply to Ryan Kelly [:rfkelly] from comment #10)
> Mostly because trying to do those in web content on a mobile device sounds
> pretty scary :-)

Rather than relying on scariness, perhaps we could do some experimentation?  Those algorithms have parameters that can be tuned, and mobile devices are not what they used to be.
I'm fine with scrypt/bcrypt/Argon2, but I had assumed that there would be significantly more complexity involved switching to them over changing a parameter in an existing codebase. They also have considerably weaker support, such as via WebCryptoAPI.

AFAIK there is nothing known to be wrong with PBKDF2 other than the tendency for people not to keep up with an appropriate number of iterations as time goes on.

> I don't think there's any appreciable difference between SHA-256 and SHA-512 in this case.

I believe that HMAC-SHA512 is slightly more problematic to compute on GPUs, but that may have changed over the years.  Looking at hashcat benchmarks, it appears to be almost 65% slower than HMAC-SHA256 on GPUs:

https://gist.github.com/epixoip/a83d38f412b4737e99bbef804a270c40

Whereas, at least on my personal laptop's CPU, HMAC-SHA512 is only 29% slower.

> Mostly because trying to do those in web content on a mobile device sounds pretty scary :-)

Oh, this is done in JavaScript?  It might be a good deal slower than native C or Java code for calculation.  Definitely make sure to benchmark before jumping in.  :)
Thanks for your input here April and Richard, it's always good to take a fresh look at these things.

> perhaps we could do some experimentation?

Yep, I think getting some concrete metrics will be our next step here.

> Oh, this is done in JavaScript? 

So just to ensure we're all on the same page, I should back up and say a few more words about how we do password-stretching etc, and to add context to Chris's Comment 3 about the security goals of this stretching.

There's an excruciating amount of detail in this doc:

  https://github.com/mozilla/fxa-auth-server/wiki/onepw-protocol

But the short version is that we have two layers of hashing involved with the FxA password:

1) The user enters their password into web content [1] on the client, which does a small amount of PBKDF2 and submits the result to the server.
2) The server does scrypt on that value and stores the result in its database.

So at rest, the passwords are stored as scrypt(PBKDF2(password)).  The PBKDF2 part is there to guard against any attackers that might otherwise steal the password while it's in transit, such as:

* Mozilla, or someone who can coerce Mozilla to act on their behalf
* Someone who can MITM the TLS connection to the server
* Someone who can compromise the running server and view its memory

I don't believe there's a way to get a cheap verifier for PBKDF2(password) from any data at rest in the system.

It sounds like lastpass use a broadly similar scheme [2] except they use PBKDF on both client and server.  It's a little different to 1password [3] which AFAICT doesn't have a server-side component.  But in any case I quite like:

> from here out we track what the 1Password folks are doing over time

As a general strategy going forward.


[1] There are of course additional threats around compromising this web content that handles the raw password, which are beyond the scope of this bug...
[2] https://helpdesk.lastpass.com/account-settings/general/password-iterations-pbkdf2/
[3] https://support.1password.com/opvault-design/#key-derivation
Thanks Ryan, that's a great summary. Some additional context is that the original design was made to also accommodate login from low end FxOS devices, which is no longer a goal. :) A v2 of this design could probably boost the number of rounds of pre-hashing done on the client, especially if we use WebCrypto.

Since FxA login needs be supported in pure Web content (e.g., from other browsers to your settings), we can't assume any non-standard access to native crypto.
Summary: Review FxA client-side key stretching paramaters → Review FxA client-side key stretching parameters
from mtg: we are looking into prioritizing this...
Group: cloud-services-security
(In reply to Richard Barnes [:rbarnes] from comment #11)
> Rather than relying on scariness, perhaps we could do some experimentation? 

As mentioned in bug 1444866, I actually did some experimentation for PfP: Pain-free Passwords. I ruled out Argon2 because 64 bit arithmetics cannot be implemented efficiently in JavaScript. scrypt on the other hand can be remarkably effective, StableLib (https://www.npmjs.com/package/@stablelib/scrypt / https://github.com/StableLib/stablelib/) performed best. scrypt(32 * 1024, 8, 1) requires around 100ms on a laptop and around 1s on low-end smartphones. That's about the same performance as PBKDF2-HMAC-SHA1(256 * 1024) (no big difference between WebCrypto and asmCrypto JS library here) but much harder to speed up. My entire decision process is documented under https://github.com/palant/pfp/issues/58.
This bug has got a bit of renewed attention after being linked from:

  https://palant.de/2018/03/13/can-chrome-sync-or-firefox-sync-be-trusted-with-sensitive-data

Which is a good reminder for me to sum up the current state of affairs, and say a bit about what engineering work would be involved in revising the key-stretching parameters here.

> Some additional context is that the original design was made to also accommodate login from low
> end FxOS devices, which is no longer a goal. A v2 of this design could probably boost the number
> of rounds of pre-hashing done on the client

I think there's broad agreement that we should (at minimum) try to increase the number of rounds of PBKDF2 here, in response to evolving device capabilities and product requirements.  Our protocol accepts the fact that privileged TLS-level attackers will get a cheaper brute-force attack against the password, but it seems worthwhile to try to keep "cheaper" meaning "as hard as reasonably possible within product constraints".

> I'm fine with scrypt/bcrypt/Argon2, but I had assumed that there would be significantly more
> complexity involved switching to them over changing a parameter in an existing codebase.

Due to the way the password is handled and the split between client and server responsibilities, even an apparently simple change like increasing the number of iterations will involve a non-trivial amount of work.  I took some time to write out a proposal for the mechanics of such a change here:

  https://github.com/mozilla/fxa-auth-server/issues/2344

Which should help us have discussions around the prioritizing such a change.
from mtg: might come back in Q4
As a small step forward here, I've deployed a dev box with the number of PBKDF2 rounds increase to 100k.  You can try it out here:

  https://keystretching.dev.lcip.org/

If you create an account or sign in, it should log a message to the console saying how long the key-stretching took.  On my desktop machine here it says "key-stretching took 719 milliseconds" which is eminently reasonable.

Let's try this out on a variety of different devices and see how to experience feels from an end-user perspective.
On my laptop it said 565 ms. This seems rather high, what is being used here? I tried WebCrypto and I get times below 200 ms (measured together with key import).
I think Ryan's point is that anything below the second (and maybe even a few seconds) is perfectly fine from a user experience perspective.
My point is: this might get too slow on mobile devices which are the ones you should worry about.
On my middle-of-the-road iOS device (an iPhone SE, equivalent to the computing power of an iPhone 6S), the keystretching took 967 milliseconds.
> This seems rather high, what is being used here?

It's probably using the implementation from SJCL even in cases where WebCrypto has a native PBKDF2 available; trying WebCrypto and falling back to SJCL would make sense here to improve user experience.

> I think Ryan's point is that anything below the second (and maybe even a few seconds) is perfectly fine from a user experience 

Alex and Shane, what's you take on a ballpark acceptable delay here?
Flags: needinfo?(stomlinson)
Flags: needinfo?(adavis)
Tried this with Firefox on Moto G4 Play, got 8098 ms.
I think the most important part is the user experience. Literal speed is only a factor IMO since we've learned from Photon that there are various ways to make things feel fast.

For example, if there is any noticeable user delay (1-5 seconds), we could display an animation that shows we're doing some cool "security/crypto stuff". This could both allow us to improve security but also reinforce how FxA and Sync treat security and data encryption.

Obviously, this would remain to be tested but from what I can tell here, the delays seem somewhat manageable.

I have an old Nexus on my desk at work. I'll try it out tomorrow. Since it's 5 years old (but was flagship then), it's a device I like to test things on.
Flags: needinfo?(adavis)
On a 2 year old Pixel 1 (3 year old design), 2400ms. 

I agree with Alex that up to about 5 seconds seems acceptable. How far back do we have to go before the average device crosses the 5 second threshold? As Wladimir points out, the average 5 year old device might take 8 seconds, but the average 3 year old device might only take 4.


I have ~ 4 year old Samsung Tab S2 at home, I'll try on that too.
Flags: needinfo?(stomlinson)
> It's probably using the implementation from SJCL even in cases where WebCrypto has a native PBKDF2 available

Hu, why do you even need to use SJCL? Actually, that should not be needed, i.e. only for legacy clients. The WebCrypto API is not that new and supported in Firefox everywhere, as far as I know, so can't you just get rid of SJCL altogether?
(In reply to rugk from comment #29)
> > It's probably using the implementation from SJCL even in cases where WebCrypto has a native PBKDF2 available
> 
> Hu, why do you even need to use SJCL? Actually, that should not be needed,
> i.e. only for legacy clients. The WebCrypto API is not that new and
> supported in Firefox everywhere, as far as I know, so can't you just get rid
> of SJCL altogether?

Once upon a time we had to support back to Gecko 18 for Firefox OS. FxA still officially
supports back to Firefox 29 [1]. Web Crypto is only available un-preffed from Firefox 34 [2].
Until we remove support for these old browsers (which is in the plans, though movement has
been glacial) [3], we have to use some library to provide PBKDF2 support.


[1] - https://mail.mozilla.org/pipermail/dev-fxacct/2017-September/002443.html
[2] - https://developer.mozilla.org/en-US/docs/Web/API/Web_Crypto_API
[3] - https://github.com/mozilla/fxa-content-server/issues/5651
Given that PBKDF2-HMAC-SHA256 is being used, it is only supported as of Firefox 47 (bug 1238277).
(In reply to Wladimir Palant from comment #31)
> Given that PBKDF2-HMAC-SHA256 is being used, it is only supported as of
> Firefox 47 (bug 1238277).

We use node-jose instead of sjcl for other portions of the code. node-jose
supports PBKDF2-HMAC-SHA256 [1] and delegates to WebCrypto in browsers with support.
Perhaps this is a good avenue to explore [2].

[1] - https://github.com/cisco/node-jose/blob/master/test/algorithms/pbes2-test.js#L35
[2] - https://github.com/mozilla/fxa-js-client/issues/286
(In reply to Shane Tomlinson [:stomlinson] from comment #28)

> I have ~ 4 year old Samsung Tab S2 at home, I'll try on that too.

On the Galaxy Tab S2, 4355ms.
I'll note that, on the topic of perceived performance, my mobile devices routinely take 5 to 10s to open URLs, even on fast wifi/4g networks. I don't _think_ an added delay on login will surprise a lot of mobile users, but verifying that with data would be nice.
> verifying that with data would be nice.

If we pick parameters that we think *should* work fine, I think it'll be fairly straightforward to run an A/B test that does a fake PBKDF2 of the desired iteration count, and measure how it affect login success rate in practice.
Has anybody considered using PAKE ? I think this article by Prof. Matthew Green makes a good case that PAKE should be considered best practice nowadays: https://blog.cryptographyengineering.com/2018/10/19/lets-talk-about-pake/.
> Has anybody considered using PAKE?

Thanks for the link.  This has been discussed (and in fact an earlier prototype of the login flow used SRP) but would be a much more significant change.
This is a very interesting problem and we targeted this problem in our research ("AuthStore: Password-based Authentication and Encrypted Data Storage in Untrusted Environments" https://arxiv.org/abs/1805.05033)

Ultimately, the KDF parameters needs to be adapted over time, e.g. the iteration count needs to be increased to mitigate faster CPUs... Furthermore, the KDF parameters should be configurable by the user. In our proposed solution we make this possible. To make this work we store the KDF parameters on the server. However, this leads to other problems, i.e. the server could perform a "parameter attack". Briefly: in a parameter attack the server sends back the weakest possible KDF parameters to the user in order to obtain an easier to brute force authentication token. To prevent this attack we use an adapted version of the provable secure EKE2 protocol. This protocol does not reveal any information about the entered password. For example, if you entered "123" (not your real password) in the password field the server is not able to find out that this is what you did. The server can only tell if the entered password is correct or not. This property prevents parameter attacks since the server does not learn anything about the weakened auth token. Please have a look at our paper for more details.

I implemented our solution as a browser extension (FejoaAuth: https://fejoa.org/fejoapage/auth.html). However, having something like FejoaAuth integrated into the browser would be much more convenient. Our approach can be used to securely authenticate at multiple services with the same password and the same password can even be reused for data encryption.

Please let me know if you have questions!
Keywords: sec-want

Hi,
Is that issue resolved ? I can read an update on Master password in Firefox or Thunderbird? Do not bother! that say weakness is resolved since Firefox 72 ?
Thanks.

(In reply to Cyrille from comment #40)

Is that issue resolved ? I can read an update on Master password in Firefox or Thunderbird? Do not bother! that say weakness is resolved since Firefox 72 ?

These are different issues. The article you link to is about the master password and local encryption. This issue is about Firefox Sync and encryption when data is being uploaded to the cloud. It’s referenced in another article I wrote: Can Chrome Sync or Firefox Sync be trusted with sensitive data?

With the recent security incidents at LastPass many users might (re-)evaluate whether their current password manager is safe enough. Seeing that this six-year-old (and this nine-year-old) issues are not resolved is not very confidence inspiring. As a step to gain (and keep) Firefox Sync users, it might be good to at least increase the number of client-side PBKDF2 rounds (and periodically adjust the number of rounds to reflect recommended practices).

This ticket was mentioned in an article that explains the same issue in LastPass and Vaultwarden and how in Sync the iterations are very low: https://palant.info/2023/01/23/bitwarden-design-flaw-server-side-iterations/

This has also been disclosed in the 2017 audit and determined that no changes would be made at that time, so to be consistent with that announcement it is probably best to just close this bug report.
https://blog.mozilla.org/security/2017/07/18/web-service-audits-firefox-accounts/

Unlike LastPass, the encryption key is secured behind further scrypt hashing server-side so the client-side hashing mentioned in the palant.info article is a bit misleading since that is not the last line of protection and was merely meant to avoid plain text passwords being exposed in a MITM attack. So to brute-force a compromised data file without any other information one would need to hash with 5000 iterations of PBKDF2 AND scrypt before checking the validity of the password.

The problematic scenario isn’t merely MITM (something that is probably rather unlikely) but also a compromise of the fxa-auth-server. If an attacker manages to control the server as opposed to merely accessing the data, they will be able to log the password hashes as they come in. At 1,000 PBKDF2 iterations, the cost of 2³² guesses is merely $0.06 (cost estimate by 1Password, my estimate based on cloud computing prices arrives at roughly twice the number). Guessing a password with 40 bits of entropy will cost $7.68 on average.

While it is hard to tell what the typical entropy of a password is, zxcvbn will give a score 4 out of 4 to a password with 33 bits of entropy. Add to this that the Firefox Accounts signup page doesn’t offer much help for choosing a strong password – “asdfyxcv” is considered a perfectly good password. Even if someone followed the advice (combine two words, change letters to numbers etc.), it’s hard to come up with a truly strong password this way.

FWIW I'd prefer us to have not only strong crypto, but also strong looking crypto. Most of the people in this thread have at least basic idea what PBKDF2 or 1000 iterations are. Overwhelming majority of the people on Earth do not have such knowledge. But they trust in whatever their friend said about in an article on Internet.

P.S. I love users, but I don't trust them to pick a strong password. Lets not count on that.

but also a compromise of the fxa-auth-server

If the server is compromised to that extent the hash can just be copied into a new API request, what good is it to guess the password?

I'd prefer us to have not only strong crypto, but also strong looking crypto.

I agree, it isn't a good look - Core53 ranked it "high" severity - and logically, if it was ever worth hashing then it should be worth updating the hashing iterations to keep up with the times, but it seems Mozilla decided that it wasn't anymore.
(probably because it would be non-trivial - the old hash is still required to decrypt so the old would still have to be sent until the client is somehow aware that it no longer has to - would probably require multiple new API endpoints so significant changes on both client and server-side - though still totally doable)
My point was just that there is no reason to keep this bug report open if it has already been decided it won't be fixed.

(In reply to colin from comment #49)

If the server is compromised to that extent the hash can just be copied into a new API request, what good is it to guess the password?

The password is still required to decrypt the data, even on a compromised server.

You need to log in before you can comment on or make changes to this bug.