Why does it take longer to reject an invalid password than to accept a valid one?


You may have noticed that it takes longer to reject an invalid password than to accept a valid one. There are a few reasons for this.

First of all, it simply takes longer to confirm that a password is invalid.

Your local computer retains a password cache. This password cache improves performance of local authentication operations, such as unlocking a workstation. If you unlock the workstation with the same password you used to log on, then the password is assumed to be good. This allows the workstation to unlock quickly. Without the password cache, unlocking the workstation would require going back to the domain controller to validate the password, which for slow network connections, can take a very long time. In fact, you might not have any network connection at all (an extreme case of slow), say because you've taken your laptop on the road and are not connected to the corporate network any more. In that case, without the password cache, it would be impossible for you to unlock your workstation at all!

Note that you can disable these password caches if they offend you.

The algorithm for testing if a password is valid goes like this:

  1. If password is in cache and matches: Return valid.
  2. Else contact domain controller for password validation.

If you pass a valid password, then the validation succeeds at step 1. Notice that step 1 can be performed entirely on the local machine. It doesn't need to contact any other computers to get an answer.

On the other hand, if you pass an invalid password, then we go on to step 2, which attempts to contact the domain controller to validate the password. Obviously you have to do this for passwords not in the cache, because you have no information about those passwords. But why do you also have to do this for passwords that are in the cache and don't match? Why don't you just say invalid without contacting the domain controller?

Because your cache itself may be invalid.

If the user recently changed the password on another machine, then the password in your machine's cache is not valid. If the user tries to use the new password, your computer's cache says, "Nope, that's not the right password." If you returned invalid immediately instead of contacting the domain controller, then users whose passwords have changed would not be able to use that password to access any computer which had cached the old password! They would have to sit around and wait for the old password to fall out of the cache, so that the computer would continue to step 2 and get the new password from the domain controller.

You can imagine the bizarro technical support calls that would have resulted. "Yes, I know you changed your password, but you have to keep using your old password until the system starts rejecting it, and then you switch to the new password. And the rejection time will vary from computer to computer, depending on how many other people use the computer also. Oh, and if you're the only person who uses the computer, then it will never accept your new password. But once you log onto the computer with the old password, you might need to give your new password when connecting from that machine to other machines, because those other machines might have received your new password."

Okay, so one reason why invalid passwords take longer to reject is that the computer has to try more things before finally deciding to reject it.

Another reason why invalid passwords take longer to reject is to reduce the effectiveness of dictionary attacks. If invalid passwords were rejected just as quickly as valid passwords were accepted, then a bad guy could just churn through a dictionary trying out invalid passwords at high speed. Adding a delay of a few seconds before rejecting invalid passwords introduces a minor inconvenience to users who mistyped their passwords, but makes a huge dent in stopping dictionary attacks. For example (and these numbers are completely made up), suppose you have a 75,000 word password dictionary, and passwords are accepted or rejected in 100ms. It would take a little over three hours to attempt every password in the dictionary. Introducing even a simple 5-second delay into the rejection of invalid passwords increases the time to perform a dictionary search to over four days.

The invalid password rejection time in some places can get quite high, especially if the delay escalates each time you get the password wrong. For example, after you type the third (fourth?) incorrect password to the Windows logon screen, it displays the incorrect password error for something like 30 seconds before letting you try again.

Comments (37)
  1. Joe says:

    But does this cache thing on the other hand mean, that one could logon on on a machine with an old password as long as it is in the cache? So if you are the only user on this particular machine it would be possible that you could use your old password for ages?

    [Check out those links. -Raymond]
  2. Leo Davidson says:

    My memory is fuzzy but I think the "the bizarro technical support calls" situation did used to happen with NT4 and the screen-lock password.

    If you changed your password but then didn’t log-out and back in, the screenlock continued to require your old password. (Or something like that. It may have only happened when changing it on another machine or via an API taht didn’t tell the GINA component.)

    Long fixed, but a pain (and a good way to instantly forget your new password) at the time.

    I’ve noticed that navigating to non-existent UNC shares also seems to take ages to return an error. If I mis-type a path I can wait a long time, while typing it properly returns it instantly. Not sure if that’s on purpose or if there’s a complex series of accidents, in the code and/or my LAN setup, conspiring to make it happen.

  3. Joe says:

    So if you’re not connected to the corporate network and the password cache is disabled it means you can’t unlock your workstation?

  4. Pierre B. says:

    Joe, I suspect the answer to your second question is also "Check out those links." I excuse you, because I did check out those links and confronted with those walls of text, I went tl;dr.

    (Of course, if I really needed the answer, I’d Google^H^H^H Bing it instead, in the vain hope someone already distilled the information to a simple answer. Assuming the answer is simple.My hunch is that it depends on obscure policy settings, some registry keys, which version of Windows you use and phases of the moon.)

  5. R. Bemrose says:

    I recall that Linux (or one of the other UNIX derivatives) used to have a related bug that trying a username that didn’t exist would return faster than trying a username that does exist with an incorrect password.

    Meaning that you could find out whether a user exists by how long it took to return.

    As I recall, the developers had to introduce a delay to correct the problem.

  6. Billy O'Neal says:

    Joe: That is correct. This has happened to me before. I had to login as a local user and connect to the VPN before my domain password would be accepted again.

  7. pplu says:

    Tarpitting doesn’t work in all scenarios. It stops working, and actually can hurt you more if the offending party starts to do the queries in parallel… If their cost to maintain a connection is low, they will just open more connections, and query on one connection while the other ones are waiting. Now you have YAP (Yet Another Problem): the added concurrency :'(

  8. Voo says:

    Maybe I don’t get it, but the last paragraph sounds like something you really shouldn’t rely on.

    So you can’t use the windows login screen, but nobody stopps you from writing your own software to send the necessary data to the controller and see what it says, right?

  9. Gabe says:

    Voo: There’s nothing stopping the domain controller from not answering you for some amount of time. It could have a delay based on the source or based on the user being queried.

  10. arnshea says:

    @pplu, imho It’s all about defense-in-depth.  No need to make it easy for password crackers even if there are ways around the delay.  Also, as @gabe mentioned, a delay enforced at the server could mitigate an attempt to get around the delay by issuing simultaneous requests.

  11. Keith B says:

    I seem to recall hearing that with some password authentication systems, there’s also a computational delay involved. Normally, the password database just stores a hash, which it checks against the password, but if that fails, it does some other (high-cost) processing to check another way, just in case. Or something like that.

    I could be misremembering, though.

  12. Fuzzy says:

    @Keith, you might be thinking about how authentication systems don’t return immediately after finding an incorrect character in the password. If they did, then a hacker can keep track of the computation times and figure out when he’s found a matching character (the return time will be slightly higher, since the system has to crunch through at least one more character).

  13. Mark says:

    @Fuzzy and Keith:

    Password-based authentication on Windows is not done by comparing the "cleartext" password that the user enters against the expected value. (So there is no risk of returning quickly and giving an attacker a clue as to which character in the password was invalid).

    Passwords are hashed and then stored on the domain controller (and in the local cache too). When a user logs in, the computer checks the hash of the password against the expected hash value. Sometimes the hash is used as input for a second round of hashing, with salt and a random "challenge" value added, so someone can’t just sniff the network traffic traffic and later authenticate as another user.

  14. pplu says:

    @arnshea. Loking a door when the window is open will have no effect. Although the server enforces a delay, the client can still open more connections, thus leaving you with the downside of tarpitting: the added concurrency

    Much care has to be taken when implementing effective tarpitting. The game goes this way: the offender will open connections in parallel because these are cheap for him. This will let him get over the delays. On the other hand, the server has to assign the offender a thread or process per connection. Server processes/threads are a precious resource, and are normally limited by configuration to a max clients setting. The offender will cope the delays with parallelism.

    If the server delays the "denied" responses… it will have idle worker threads/processes doing NOTHING, just sleeping, while there are clients that may be wanting to connect, making your memory occupation go up in f(x) of the time you tarpit the clients.

    Sometimes it’s just better to give the "incorrect password" response inmediately, and use alternative (cheaper) tecniques to mitigate attacks: count the number of denied login attempts per unit of time for a client. If the count reaches a threshold you can do better things than delaying the response: drop the connection, LIE to the client and just deny all login attempts, etc.

    I’ve seen systems max out their connections when tarpitting (causing a DOS for the legitimate clients that want to connect), and return to normal when disabling the tarpit.

    Note: some servers can attend connections without the costs of a thread or process per connection. In this case the game turns around: the cost of the server maintaing the connection drops, and tarpitting can become effective again

    Just my 2cents

    Pplu

  15. Absotively says:

    Pplu: Is there some reason you couldn’t just not accept multiple connections from the same source?

  16. pplu says:

    @Absotively: Yes! Two main reasons:

    1- Two different client connections behind a router will appear to come from the same source (you cannot distinguish one from the other).

    2- You’re a service that must accept parallel legitimate connections from the same source. Db servers, HTTP servers, SMTP servers, etc must accept more than one connection from the same source simultaneously. It’s really hard to think of a service without that requirement.

  17. SteveM says:

    That link for how to disable password caches also contains some really misleading information about how caching is such a security risk. That author needs to take a look at this….

    http://technet.microsoft.com/en-us/magazine/2009.07.windowsconfidential.aspx

  18. mikeb says:

    >> So if you’re not connected to the corporate network and the password cache is disabled it means you can’t unlock your workstation? <<

    Well, since there’s no way to validate the domain credentials without a connection to the domain controller in that case, then the logical answer would be that you can’t unlock your workstation *using domain credentials*.

    It’s still possible to unlock the machine using a machine local account.

  19. Cheong says:

    @pplu: The first reason doesn’t really matter.

    In coparate network environment, there’s usually only one SMTP server allow to go outside. (A policy to prevent infected computer putting company’s IP on blacklist)

    If it’s general environment where a few home computer running local SMTP servers, the amount of mail is low and the emails can wait in the mail queue for a few days, so they’ll eventially be sent. (Usually in this condition the retry will occur very soon, so the delay caused by this tops at about 1-2 hours even in dorm-like environment… anyway, most ISPs come with their SMTP server service for their users at no extra charge…)

    For the second reason, SMTP of course. (Plus a few FTP servers and a few others for good reason.)

  20. Cheong says:

    @Alexander: [quote]2- You’re a service that must accept parallel legitimate connections from the same source. Db servers, HTTP servers, [b]SMTP servers[/b], etc must accept more than one connection from the same source simultaneously. It’s really hard to think of a service without that requirement.[/quote]

  21. Cheong says:

    @Alexander: Btw, I’ll admit that I was in the mindset of "SMTP tarpuit" after reading the wiki like above.

    Back on the topic, I agree that it make sense for accepting parallel connection from single source, but it also make sense to set limit for maximum allowed connection from single source so it doesn’t block others to connect.

    It doesn’t really make sense to allow single IP to block >20% of total allowed connections on usual cases.

  22. Gabe says:

    The way to protect against a DoS caused by a tarpit is to just disallow multiple connections from a source trying lots of bad passwords. A legitimate connection is extremely unlikely to have even 10 bad passwords consecutively, while an illegitimate connection will have thousands, so it’s extremely easy to differentiate them.

    With an SMTP tarpit you differentiate based on spaminess. The more spam you encounter from a host, the slower you communicate with it, and the fewer connections you allow from it.

  23. Cheong says:

    @Gabe: Yes. I remember that something like Bastille firewall from NASA in some very old distro can read verious logs and add IPs for logon failure.

  24. pplu says:

    @Alexander

    Why are the progams that follow this way of handling connections "amateurish"? Does the Apache web server appear in your list of "amateurish" software? I think you have called a very big percent of actual server software "amateurish"…

  25. Alexander Grigoriev says:

    @Pplu,

    *Sane* applications are not using a thread or process per TCP/IP connection. Only amateurish do.

    @Cheong,

    Where SMTP came up from? Nobody even mentioned it.

  26. Mark Wooding says:

    @pplu

    I’ve no idea why you think that handling multiple connections on different threads (or even different processes) means that you can’t tarpit incorrect passwords effectively.  It’s a simple matter of maintaining a single, properly synchronized tarpit penalty per user.

    (I also can’t really see why nobody else has mentioned this.)

  27. Alexandre Grigoriev says:

    @pplu,

    A thread requires certain virtual address space reserved for its stack. Let’s say, 1MB by default. Then you’re limited by <2000 threads per process. That is 2000 connections per process. In the very best case. There are also other considerations that will just kill performance with such architecture.

  28. The right way to do it says:

    Usually login tries are handles by 1 process/thread. When a connection is authenticated it spawns a new process/thread which handles the connection from that point.

  29. does not compute says:

    @Mark: Password-based authentication on Windows is not done by comparing the "cleartext" password that the user enters against the expected value. (So there is no risk of returning quickly and giving an attacker a clue as to which character in the password was invalid).

    The hash comparation has the same timing problems as a password comparation. It can not be compared in a atomic operation.

  30. JonK says:

    @pplu

    Let’s assume we’re talking about server applications on Windows. Now, no-one in their right mind builds a server application on the Windows platform using the one-thread-per-connection model and pretty much all the worthwhile advice given in the last fifteen years has reinforced this point: for maximum throughput you should use overlapped IO or completion ports and the thread pool. Thread-per-connection kills you in about eighteen different ways when you’re operation at scale, among them the cumulative size of all those thread stacks, and the conniptions you cause the Executive (create, say, 3000 runnable threads and watch how the scheduling latency rise), the horrendous impact on memory locality, the cache trashing, yadda yadda yadda.

    Sadly, there’s lots of software that’s been ported to Windows without making the necessary architectural changes: to pick an example, Asterisk (the VoIP server) is such a horrorshow on Windows because it goes with a two-threads-per-conversation model, which scales really well… to about twenty concurrent conversations.

    So yes, "amateurish" is pretty much the perfect description because a professional software developer won’t leave until the job’s done *properly*.

  31. pplu says:

    @Mark Wooding

    I haven’t said that you can’t tarpit because of using threads/processes per connection.

    @Jonk

    I’m more from the unix world, but saying that a server software is amateurly written because it doesn’t use techique A or B is a bit offensive. I’ll just wait a while for the next techinques in writing server software to appear. After that I’ll call the ones that use "overlapped IO or completion ports and the thread pool" amateurish.

    @The right way to do it

    Yeah… it’s a way of lowering the cost of maintaining a connection, and thus making tarpitting "profitable" again. I already said that ;)

    @Alexandre

    Since you have a limited number of available threads to create, the more you pause your threads in idle time (delaying a response) the less connections will be available for the rest of legitimate clients. That’s why I wouldn’t tarpit in that scenario.

  32. Alexandre Grigoriev says:

    @Pplu,

    There is a reason select() exists…

  33. Pplu says:

    In unix it’s proven that few threads with async IO/kqueue or similar mechanisms scale orders of magnitude better than one connection per thread/process. IMHO the servers that are written with the old techniques are not amateur. Of course it’s only my opinion.

    I’m sorry to hear that in Windows the thread per connection scheme doesn’t scale well enough. I’ll read a bit about it…

  34. JM says:

    "I’m more from the unix world, but saying that a server software is amateurly written because it doesn’t use techique A or B is a bit offensive."

    No, we’re saying that it’s amateurishly written because it uses technique C, which is known to not scale. You cannot expect to write (or port) a server without looking at how it will run under load on the OS(es) you’re targeting — that’s the amateurish part. If your server is targeting Windows, then using a thread-per-connection model is acceptable exactly never. Not even if everybody promises it will never handle more than a few connections at a time, ever. Such promises usually turn out to be based on wishful thinking and not enforced architectural constraints.

    "I’ll just wait a while for the next techinques in writing server software to appear. After that I’ll call the ones that use "overlapped IO or completion ports and the thread pool" amateurish."

    That dog won’t hunt. On Windows, we’re talking orders of magnitude difference of scaling between thread-per-connection and overlapped/completion port I/O. New techniques may very well be faster, but probably not orders of magnitude. Even if they are, it will be the case that for most purposes, the existing ones are good enough. Thread-per-connection stops being good enough *very* quickly. As in, you should have seen this during your initial load tests before a single client ever tried to connect.

    I’m not philosophizing from my armchair here, I’m coming out of a two-day broom closet session where I had to write a (rudimentary) server from scratch to replace our existing one which used a thread-per-connection model (two threads per connection, actually). As it turns out, having 400 threads in your process is… suboptimal. Aside from ridiculous memory and CPU usage, throughput on this thing is horrendous.

    To somewhat get back to the original topic, the kicker is the mechanism implemented to make sure very fast clients don’t overload the server: a configurable delay applied before sending back each response. Not quite tarpitting, but close. Of course, making your worker threads sleep in the middle of processing just hurts overall throughput even more.

    Amateurish or not — it’s not pretty.

  35. Gabe says:

    I absolutely refuse to believe that in any modern system you could reliably detect the difference between comparing a whole password and just part of a password.

    A technique you could actually use is to store the password at the end of a memory page where the following page isn’t valid. Then you could detect a page fault and know that the password is correct up to the last byte in the memory page.

    Obviously this whole point is moot because nobody would implement password validation this way anymore, but I believe one system was vulnerable to the page fault detection method once upon a time.

  36. Bob Bobson says:

    An increasing delay on each incorrect password certainly sounds practical and like a good idea, but unfortunately it’s actually kind of specious. Just like teachers who think that theirs is the only class you have (or the only important one), and so assign you lots of homework irrespective of other homework you may already be assigned, every site, company, and device thinks of itself as the only entity in existence, as though they are the only thing in your life, and so you can focus all of your mental faculties on memorizing a long and arcane password. However theirs is not the only password you have to remember, and so most people tend to forget at least the less-frequently used ones.

    I’ve been quite frustrated by the delays and limited-attempt features of some sites and such that required logging in. I can understand if my bank’s site makes it a hassle to keep trying, but an online forum? Even the bank is a huge pain in the butt if I have to sodding call them and go through a 30 min. interview and vetting just to get my account unlocked and get a new password (which I have to change to something else anyway). Blerg!

    Unfortunately biometrics are not good either, so we are back at square-zero: we need a better way of authenticating logins and nobody seems to have a safe and practical way to do it. :(

Comments are closed.

Skip to main content