passlib: long passwords trigger long checks

[Kurt Seifried]

Grant Murphy originally reported:

* Denial of Service

  The passlib restriction of 4096 for maximum password length is
  potentially too generous for production environments. On my local machine
  the sha512_crypt algorithm with input of 4096 and 40000
  rounds will potentially introduce a DOS problem:
       feasible length(128) password encrypt: 0.0707409381866 seconds
       feasible length(128) password verify: 0.140727996826 seconds
       excessive length(4096) password encrypt: 1.33277702332 seconds
       excessive length(4096) password verify: 2.66491699219 seconds

  I would consider tweaking these values (length or rounds) to reduce
  the computational overhead here or you're probably going to have a bad time.

If this is exploitable it will need a CVE, if not we should still harden it so it can't be monkeyed with in the future.

[Thierry Carrez (ttx)]

This one is slightly more borderline, although I'm not convinced you could drive a DoS from it -- some valid keystone actions already take more than 2 seconds and hit I/O harder than this... so your stack has to survive those kind of requests anyway.

Adding the keystone core team so that we get their opinion on this.

(it's also a painful fix, because you don't want to break hypothetical long passwords on upgrades)

[Dolph Mathews (dolph)]

I'd suggest making this public security, and simply making the value configurable going forward with the existing value as a default.

[Thierry Carrez (ttx)]

Adding Rob Clark from OSSG for input.

Thinking about it, this is non-authenticated load drive, which can definitely facilitate a DoS, so if we find a good fix for this, I'd rather issue an OSSA about it. How about in the security fix we truncate the password to the first 128/256 characters before feeding it to passlib ? Would that be a good trade-off ?

Alternatively, we can consider this a strengthening issue rather than a vulnerability, and have a configurable value we would truncate to... but that would only be for havana.

[Robert Clark (robert-clark)]

Thanks TTX.

My initial feeling is that truncating input is not the way to go. Indeed I seem to remember Microsoft getting lambasted for this many years ago (although the trucation was somewhat more extreme). My objection is on the basis that a client who believes they have a certain amount of complexity in their password should have confidence that this complexity is maintained in Keystone.

Making this option configurable and providing appropriate guidance seems prudent. Is there scope for throttling authentication attempts from tenants as an additional compensating control against this potential DoS ?

[Kurt Seifried (kseifried)]

Perhaps an acceptable maximum password length can be agreed upon. I think 4096 a bit long, surely 256 should suffice for any passphrase? That would be longer than this bug reply.

[Robert Clark (robert-clark)]

If we go down that road I'd rather see this made configurable with a sensible default selected. I believe some had concerns that this would break existing deployments though.

[Thierry Carrez (ttx)]

I see two ways out of this:

1/ Consider this a vulnerability and adopt the truncating approach (benefit is that you don't break anyone on upgrade, drawback is that you're potentially lowering expected complexity, as Rob points out. With 256 characters this may be a non-issue though).

2/ Consider this a performance issue and make password length configurable in future versions, but default to 4096 so that nobody is broken on upgrade.

I'm fine with either solution... I just don't see other solutions that let us solve this without breaking people on upgrade.

Thoughts ? Preferences ?

[Brant Knudson (blk-u)]

I prefer truncating. As long as it's not truncating to some really short value (I'd draw the line at 30 characters). After reading a discussion on stackforge it seems like the correct approach to me.

In order to exploit it, wouldn't you have to create users with long passwords, or allow some miscreant to set their password to a long value? At least you'd know who it is.

[Robert Clark (robert-clark)]

Would it be possible to present option 1 as option 2. That is to say, create a maximum password length setting that in reality truncates password input. This would perhaps satisfy the 'dont break stuff' requirement (you could truncate to 256 by default) while also allowing deployers to decide what cpu/complexity tradeoff they'd be happy to accept?

[Thierry Carrez (ttx)]

@Brant: my understanding is that you'd just have to try to log in with a very long password, that would trigger the verify delay.

[Grant Murphy (gmurphy)]

As you can currently configure the number of rounds I think it makes sense to be able to configure the maximum password length rather than using a hard coded value. This will give the administrator better control over their environment.

TBH I don't like the truncating approach. To me it seems like you are trying to 'fix' invalid input and continue like nothing has happened. IMO Any password that exceed the maximum password length should be rejected as invalid input (as really that is what it is).

[Dolph Mathews (dolph)]

Suddenly truncating long passwords to some arbitrary length shorter than 4096 will result in 401's for users with existing long passwords.

[Dolph Mathews (dolph)]

Also, we are currently truncating passwords to 4096 rather than raising 400 Bad Request:

  https://github.com/openstack/keystone/blob/master/keystone/common/utils.py#L103

[Robert Clark (robert-clark)]

In principle I'd rather have something configurable. The only way to not break existing deployments that I can see is to make this configurable, default it to 4096 and issue guidance on reducing this with accompanying text on how this will break users with passwords longer than the new default.

[Thierry Carrez (ttx)]

Hmm, I'm leaning towards what Rob proposed in comment 9: considering this a performance issue and making the password significant length (truncation) configurable in Havana, defaulting to 256. That sounds like a good trade-off between upgradeability and configurable security.

[Jeremy Stanley (fungi)]

Is it possible to move the current hard-coded (4096) default into a maxlength field for each existing password? Then the configuration could set a desired global maxlength which would be applied per-entry on new accounts and lowered as necessary on password changes of existing accounts. This sort of "eventually consistent" transition would relieve administrators from forced password changes or invalidating existing hashes of their entire userbase (which is of course extremely disruptive to those users).

[Grant Murphy (gmurphy)]

Users with a password longer than the truncation limit are receiving absolutely no security benefit and are being misled about the security provided by the underlying system. So why do it?

The approach suggested in #9 will still mean that users with a password longer than the truncation limit will need to change their passwords. The computed password will no longer match the stored password as the input has been truncated. If this is the case why truncate the passwords at all? Why not enforce a configured password limit? Why not send a clear error code (400 Bad Request) rather than an ambiguous (401 Unauthorized)? This would be my ideal solution however I understand that this is probably not acceptable for reasons such as upgrade and backwards compatibility.

I agree with comment #14. As a compromise perhaps the way the limit is used could also be configurable e.g. truncate/enforce and accompanied with appropriate guidance.

[Thierry Carrez (ttx)]

OK... My proposal is to consider this a potential performance issue (rather than a vulnerability) and have the Keystone devs openly fix it in Havana, by implementing a password max length parameter.

Depending on the implementation, it could follow Jeremy's suggestion (comment 16, store maxlength per-password for eventually consistent transition), or a default of 4096 with documentation on how to reduce it. The first option is a bit convoluted, but the only way to mitigate the issue with new users without breaking old ones.

Does that work for everyone ?

[Jeremy Stanley (fungi)]

Just to clarify, my suggestion in #16 was based in part off similar non-breaking password transition recommendations Solar Designer made in the wake of the major signedness issue fixed in crypt_blowfish 1.1 ( http://www.openwall.com/lists/announce/2011/06/21/1 ) but was mainly brought up for the sake of completeness. I really have little context for whether such a transition plan would be of interest to havana adopters.

[Grant Murphy (gmurphy)]

Sounds reasonable to me. As long as introducing the per user maxlength doesn't introduce too many other headaches.
FWIW I would also suggest the move towards using passlibs CryptContext instead of embedding the algorithm etc in the code.

[Thierry Carrez (ttx)]

@keystone devs: does that sound reasonable ? Which implementation option would you like to pursue ?

[Dolph Mathews (dolph)]

I'd like to do the simpler solution immediately (make the maximum password length configurable), and simply log warnings when truncation is occurring. From there, we can implement the phased approach to shorter passwords and adopt CryptContext (which looks quite valuable in the long run).

[Dolph Mathews (dolph)]

Simple solution is attached. This seems like a logical first step towards storing maximum password lengths per-user as well.

[Thierry Carrez (ttx)]

OK, unless someone complains soon, I will make the bug public and handle this as a performance/hardening issue to be mitigated in havana.

[Dolph Mathews (dolph)]

@ttx: +1

[Robert Clark (robert-clark)]

@ttx: +1

[Thierry Carrez (ttx)]

Opening so that we can apply the strengthening in a public patch.

[OpenStack Infra (hudson-openstack)]

Fix proposed to branch: master
Review: https://review.openstack.org/29542

[Dhiru Kholia (dhiru)]

I am a bit late to the party but here are my suggestions,

1. Rate limiting should be implemented with a high priority. (e.g. Gmail shows a CAPTCHA if you keep entering wrong password).
    In KeyStone case, this rate limited should also be applied even if the authentication succeeds, for best results.

   I am not sure about the "layer" at which these rate limiting features should be implemented though.

2. "iterations" in the hashing algorithm can be reduced by a factor of 25 if the minimum password length is increased by 1.
    See http://blog.agilebits.com/2012/07/31/1password-is-ready-for-john-the-ripper/

3. Ideally, a configurable hashing algorithm (like Django's PBKDF2-HMAC-SHA256 or better) should be used which allows tweaking of the "iterations" parameter to attain the desired balance.

* I have written a DoS tool which is able to saturate a KeyStone server with almost zero bandwidth and CPU consumption.

[Dolph Mathews (dolph)]

Unassigning due to inactivity.

[Matthew Thode (prometheanfire)]

This seems like the same issue that django had (talked about here).

Just set a max password length, have it configurable :D

https://www.djangoproject.com/weblog/2013/sep/15/security/

[David Stanek (dstanek)]

Is there any reason this bug is marked as Triaged? I see that Dolph's patch was merged back in may and I'm wondering if there is more to do here.

[Lance Bragstad (lbragstad)]

Looks like Dolph's patch from comment #28 was resubmitted by Morgan Fainberg and was merged:

https://review.openstack.org/#/c/40929/1

The review wasn't posted to this bug report.

[Dolph Mathews (dolph)]

Fix merged in https://review.openstack.org/#/c/40929/

[Dolph Mathews (dolph)]

Looks like I failed to follow up on my patch (thanks Morgan!) and our friendly neighborhood bot didn't update the status here when the patch was restored & merged during havana-3.

[Matthew Thode (prometheanfire)]

backports? grizzly/folsom

[Thierry Carrez (ttx)]

This is adding a new config option, which makes it unsuitable for backport to a stable branch.