Opened 11 years ago

Closed 11 years ago

Last modified 9 years ago

#20760 closed Bug (fixed)

Account enumeration through timing attack in password verification in django.contrib.auth

Reported by: jpaglier@… Owned by: Aymeric Augustin
Component: contrib.auth Version: 1.5
Severity: Normal Keywords: security authentication timing enumeration
Cc: jpaglier@…, eromijn@… Triage Stage: Ready for checkin
Has patch: yes Needs documentation: no
Needs tests: no Patch needs improvement: no
Easy pickings: no UI/UX: no

Description

This bug is an example of http://cwe.mitre.org/data/definitions/208.html and very similar to https://cve.mitre.org/cgi-bin/cvename.cgi?name=CVE-2004-1602 .

Description


When attempting to authenticate using django.contrib.auth, if a user does not exist the authenticate() function returns None nearly instantaneously, while when a user exists it takes much longer as the attempted password gets hashed and compared with the stored password. This allows for an attacker to infer whether or not a given account exists based upon the response time of an authentication attempt.

This can be seen much more clearly when the number of rounds on the password hasher is set to something high like 100000.

Mitigation


In authenticate(), create a dummy user and set its password. If no user is returned from the database query, check a password which is guaranteed not to match against the dummy.

Note


This mitigation strategy does not entirely mitigate a timing attack of this fashion. It does, however, greatly increase the amount of work required to gain usable information from it. For example, with a smaller variation between the two cases (user exists, user does not exist), the differences in lengths of time become much harder to distinguish from network transit times.

Attachments (3)

20760_fix.diff (861 bytes ) - added by jpaglier@… 11 years ago.
patch to fix timing attack
20760_fix_w_delay.diff (1.2 KB ) - added by Justin Paglierani 11 years ago.
Patch with delay to further hide how long the check was taking
20760_fix_hash_once.diff (3.1 KB ) - added by Justin Paglierani 11 years ago.
set_password() solution and test

Download all attachments as: .zip

Change History (31)

by jpaglier@…, 11 years ago

Attachment: 20760_fix.diff added

patch to fix timing attack

comment:1 by Justin Paglierani, 11 years ago

Has patch: set
Owner: changed from nobody to anonymous
Status: newassigned

Patch submitted

comment:2 by Justin Paglierani <jpaglier@…>, 11 years ago

Cc: jpaglier@… added

Add myself to cc list and hopefully fix anonymous assignment, sorry about the excessive changes.

comment:3 by Justin Paglierani, 11 years ago

Thinking about this more we could probably make the previous patch stronger by adding a random delay to the beginning or end of the function, making timing even less predictable. I'll write another version of the patch tonight which includes that.

Also, this probably belongs in master rather than just 1.5, but that can be decided once there's been discussion.

by Justin Paglierani, 11 years ago

Attachment: 20760_fix_w_delay.diff added

Patch with delay to further hide how long the check was taking

comment:4 by Justin Paglierani, 11 years ago

Patch with delay added.

Delay was set between 1/4 and 1/2 second because it felt right and didn't add too much delay with either low or high numbers of hashing rounds on PBKDF2.

comment:5 by Sasha Romijn, 11 years ago

Cc: eromijn@… added
Needs tests: set
Triage Stage: UnreviewedAccepted

I agree with the problem and the patch. The timing difference is probably large enough that this could actually be exploited as well.

However, I'm not sure whether the random delay is a good addition. With your first patch, I already no longer see an opportunity for a timing attack. Slowing down logins more seems a unnecessary service degradation. I would also like to have a test for this, but I'm not sure hoe we could test this effectively and reliably. Perhaps it can't be done.

Note that until recently, the password reset would also reveal whether not an account exists, in a much more obvious way, but that was fixed in trunk a few weeks ago.

comment:6 by Justin Paglierani, 11 years ago

I actually agree with you about the random delay - I only added the alternate patch because I once had a colleague who insisted it's harder to use statistics to mitigate the randomness of scheduling and network transit if you add some more randomness to it. After that, the extra jump from the try block failing could be picked up on and you're back in business.

Sounds fallacious to me - randomness makes it harder to remove randomness? He did have a stronger math background than me though... Eh anyway, the initial patch is likely good enough - it will certainly change the attack from a simple task into one that requires a fair amount of time and effort before it can be useful.

As for tests, we could probably run authentication against both an existing user and a nonexistent user a large number of times and do some basic math to see if the two average computation times are reasonably close to each other. I'll see what I can do over the next few days.

comment:7 by Sasha Romijn, 11 years ago

Well, his point is somewhat valid. But, the time difference from a try/catch is incredibly small. And networks introduce quite a degree of randomness too, which I expect to be dramatically bigger than the try/catch. Password hashing, on the other hand, is something which is intentionally quite slow, which means it might still be visible through network jitter.

comment:8 by Aymeric Augustin, 11 years ago

Easy pickings: unset
Patch needs improvement: set

This issue has security ramifications; it would have been more appropriate to report it privately to security@…. In fact, it was independently discovered and reported to the core team a few weeks ago.

Erik points out that until Django 1.5, the default password reset view leaks the same information. However, this is still a new vulnerability for websites that didn't use that view.

Anyway, the horse has left the barn, so let's just continue the discussion here.


To summarize the private discussion of the core team:

  • While it's possible to reduce the gap between the two cases (username exists / no such username), the code paths are too different to eliminate timing attacks entirely. For instance the ORM goes through completely different code paths when it finds a matching user or raises User.DoesNotExist. And I'm not even talking of custom authentication backends.
  • As a consequence, some core devs expressed concern at the idea of adding complexity without actually solving the issue.
  • Some even argued that a timing attack is a disproportionately involved way of determining whether a username exists or not (a fairly harmless information) and that we should acknowledge this issue but not fix it.
  • We had an inconclusive debate about the usefulness of an additional random delay.

I'd like to submit the following design decision to other core devs and the community:

  • since Django now ships with strong hashers by default, the login view spends most of its time hashing the password;
  • there's some value in running the hasher regardless of whether the user exists or not, in order to make a timing attack (at least) non-trivial;
  • random delays, rate limiting, and other defensive measures are better left to third-party addons.

It seems to me that the patch runs the hasher twice in the case of a non-existing user: once to set a password, once to verify another password. So it doesn't fix the issue.

Regarding tests, I veto timing tests; since Django's test suite isn't always run in a controlled and isolated environnement, such tests always fail randomly. I recommend writing a custom hasher or mocking the hasher to ensure it runs exactly once.

comment:9 by Justin Paglierani, 11 years ago

The hasher is run twice in all cases. The flow of execution is:

  1. Set dummy password
  2. ORM lookup
  3. check password (real if succesfful, dummy if User.DoesNotExist)

If you want to safely run check_password() only once you're going to need some kind of default value to compare against. I strongly dislike that approach because someone is most certainly going to use it in weird ways, which (depending on implementation) could definitely have security implications of its own.

comment:10 by Aymeric Augustin, 11 years ago

Oh, I see.

I'd like to avoid the penalty of running the hasher twice when the username exists, because it adds up to a few hundred milliseconds to the response time of the login view.

comment:11 by Justin Paglierani, 11 years ago

Then you could decouple password verification from the User object returned from the ORM, but that point you're either breaking backward compatibility (anything relying on User.check_password needs refactoring) or destandardizing how you go about checking passwords (if you leave check_password in User, but create another means of checking).

comment:12 by Sasha Romijn, 11 years ago

To fix the penalty introduced by the current patch, there might be two other options:

  • We could only set a password for the dummy user in case no user was found. So, if we do find a user, we run check_password() against it, if we don't, we run set_password() against the dummy user. There might still be a tiny time difference between the two functions, but as Aymeric already mentioned, we have a minor time difference in the ORM in any case, which is not as much of a concern.
  • In case the user does not exist, we could test against a random user and always return False. If there are no users in the database, we'd have to return False. In that case, it's still visible through timing when there were no users, but I see much less risk, if any at all, in an attack that reveals whether or not you have any users in your database without revealing any information about them.

Regarding the argument made in comment:8, about the difference in effectiveness of a timing attack with and without this fix, I've built a small test setup. I built a fresh project with the new project template, using Django trunk, and created one user named abbaf. I set up the login view with a simple template. For simplicity, I removed the CSRF protection. I then used requests to measure the time of the POST request for all 5-char usernames possible with the characters abcdef, all with the same invalid password.

Even when only running 5 queries per possible username, the result is immediately obvious: the correct username is 2-10 times as slow as an incorrect username. I tested this on localhost, but such a massive difference should be easy to detect through any modern network with even the most basic script. After applying the (non-ideal) initial patch, the correct username doesn't even come out as fastest anymore.

Conclusion: whereas the password hashing is so incredibly slow that the difference is trivial to measure, the other timing variations, like the ORM code path, are smaller than normal response time jitter in my test. That's not to say a timing attack becomes impossible when we remove the password hashing time difference, because my test has limitations, but there is definitely significant value in fixing just the hashing timing and not the rest, like ORM code paths.

comment:13 by Aymeric Augustin, 11 years ago

Thank you Erik for setting up this experiment. It validates the path we're following.

The two options you suggest are those I had in mind. I prefer the first one because it will require fewer changes: one line to create a user and set his password to something random, a comment above to explain why we're doing this, and a test.

comment:15 by Justin Paglierani, 11 years ago

Patch written using the set_password() solution, including a test. This solution will still have a timing difference due to the lack of a hash comparison in the case of a failed lookup, on top of those that have already been decided to have been acceptable. Test definitely needs a set of fresh eyes to check it over, it's late enough that I probably made a mistake.

Erik, if you have time could you check out what the difference looks like with this new one?

by Justin Paglierani, 11 years ago

Attachment: 20760_fix_hash_once.diff added

set_password() solution and test

comment:16 by Paul McMillan, 11 years ago

To address some things mentioned earlier:

Adding a random delay to the return is absolutely not an acceptable solution, for both the reason that it introduces unnecessary latency, and the fact that it does not, in fact, solve the problem in any meaningful fashion. An attacker can always take more samples.

If you actually want to test for a timing difference, you'll want to retain all of the processing times for both samples and use the Kolmogorov-Smirnov test to figure out if they're different. You can't use Student's t-test because the samples are not normally distributed. There's more information on this in my presentation from Djangocon 2011.

The latest patch and test look reasonable to me.

comment:17 by Aymeric Augustin, 11 years ago

Needs tests: unset
Owner: changed from anonymous to Aymeric Augustin
Patch needs improvement: unset
Triage Stage: AcceptedReady for checkin

Thank you Paul for the review.

I'm going to wait a few days in case Erik has the time to re-run his benchmark against the latest patch, and then push it (after a little bit of reformatting).

comment:18 by Sasha Romijn, 11 years ago

I've re-run my benchmark, and the patch looks good. With 30 tries per username, and otherwise the same parameters as the last test, the correct username is somewhere near the middle of the timing range. In any case, the result gives no hint to the correct username.

I should stress that this is not a foolproof benchmark: it will catch the very obvious differences, like whether or not a slow hash function is being run, but the fact that this benchmark can't find the correct username, does not mean it can not be done at all. However, we can be sure now that we at least make this attack much harder, and that the ORM timing difference is incredibly tiny compared to the hash timing difference.

comment:19 by Aymeric Augustin, 11 years ago

Yes, I understand the limitations of your benchmark. I just wanted to make sure we weren't missing something obvious and that the patch really improves the situation wrt. timing attacks, since the test doesn't say much about that. Thank you!

comment:20 by Aymeric Augustin <aymeric.augustin@…>, 11 years ago

Resolution: fixed
Status: assignedclosed

In 5dbca13f3baa2e1bafd77e84a80ad6d8a074712e:

Fixed #20760 -- Reduced timing variation in ModelBackend.

Thanks jpaglier and erikr.

comment:21 by Aymeric Augustin <aymeric.augustin@…>, 11 years ago

In 4525eab0779a2946063288224dcebb61ba382976:

[1.6.x] Fixed #20760 -- Reduced timing variation in ModelBackend.

Thanks jpaglier and erikr.

Backport of 5dbca13f3baa2e1bafd77e84a80ad6d8a074712e from master.

comment:22 by anonymous, 11 years ago

Hi

CVE requested on oss-security list at http://www.openwall.com/lists/oss-security/2013/07/22/4 and following.

comment:23 by Aymeric Augustin, 11 years ago

I assume that you're trying to help but you're failing very hard.

As explained above, we chose not to treat this report like a security issue, because:

  • The consequences are rather harmless;
  • There are much easier and well known ways to achieve the same result in all currently released versions of Django and it hasn't been considered a problem until very recently — Django 1.6 will be the first version where the login failure message doesn't leak the existence of usernames;
  • It has been reported in public, and at that point there's no good solution anyway.

We're grown ups and we ask for CVE privately when we fix security issues through the appropriate process (which is rather complicated and isn't public). If you have concerns about the security of Django, please email security@… and talk to us instead of forcing our hand by requesting a CVE in public.

comment:24 by Sasha Romijn, 11 years ago

Not negating any of your other points, Aymeric, but are you sure that the login error message leaks existence of usernames prior to 1.6? Just tested this on a 1.5 setup, although in Dutch, and the error message asks for a correct username and password, not revealing which one was wrong. Also, I can't imagine I would not have spotted this before.

I do know that prior to 1.6, we leaked username existence through the password reset form, which would either say that an email has been sent, or that no match was found. This was fixed a few weeks ago, if I remember correctly.

comment:25 by Aymeric Augustin, 11 years ago

My fault -- I was referring to the password reset form, not the login form. Sorry for the confusion.

comment:26 by Aymeric Augustin <aymeric.augustin@…>, 11 years ago

In 5b47a9c5a0dcb513dc5ff68b617b3aa374c90f3b:

Fixed a test that could fail depending on PASSWORD_HASHERS.

Thanks Claude. Refs #20760.

comment:27 by Aymeric Augustin <aymeric.augustin@…>, 11 years ago

In 88e4a3a3d932997aabebba772217f954df2fd65b:

[1.6.x] Fixed a test that could fail depending on PASSWORD_HASHERS.

Thanks Claude. Refs #20760.

Backport of 5b47a9c5a0dcb513dc5ff68b617b3aa374c90f3b from master.

comment:28 by jedie, 9 years ago

Maybe someone interests: I made a test app to generate a matplotlib PDF file.

Results looks like this:

https://raw.githubusercontent.com/jedie/django-timingattack-test/master/results_default_hasher.jpg

Source code:

https://github.com/jedie/django-timingattack-test/

Note: See TracTickets for help on using tickets.
Back to Top