1

Clients (actually software pieces developed by some random dudes all over the Internet) are authenticating on a web server using "basic" authentication scheme and to do so they are passing the username and password with each request. Every time a non-empty username and password is passed the server it has to hash the password and check the username and hash against the database. This puts extra load on the database.

The typical approach to reduce the database load is to cache authentication results in the server memory. It's easy for successful attempts - just cache username, password hash and an internal object representing the user for say 20 seconds. Yes, the user will be able to use the old password for no more than 20 seconds but it doesn't sound like a big deal most of the time.

What about unsuccessful attempts? If I cache them for too long users will see that entering a correct password "doesn't work". Also I'm not sure if I need to cache exactly the pairs of usernames and incorrect passwords (so that altering a password causes a cache miss immediately) or I need to cache just the fact that a specific user failed to authenticate (so that altering a password causes a cache hit and the user cannot authenticate with any password until the cache entry expires).

What's the typical approach to caching incorrect authentication attempts?

1

The generic approach for a cache is to keep it in sync with the database. Right now you have some system, with RAM, that can decide whether a username+password is correct or not by checking with regards to its RAM contents, letting it flow to the database if the information is not in RAM (or is deemed too old in some way). If you can arrange for password updates to go through the same way, then you can make sure that whenever a password is changed, then the RAM contents are up to date; a simple implementation would look like this:

  • The RAM cache contains tuples (user, password, ok, age) where "ok" is a boolean value ("true" for: user+password match, "false" for a known mismatch), and "age" is the date at which the information was last used.

  • When a login attempt for user "Bob" and password "p@ssw0rd1" is made:

    • If the RAM cache contains a triplet ("Bob", "p@ssw0rd1", z, age) then update age to the current date and time, and return z ("true" on authentication success, "false" on authentication failure)
    • Otherwise, do the verification with the hash value stored on the database, yielding the result z ("true" or "false"); store ("Bob", "p@assw0rd1", z, now) in the cache, and return z.
  • When user "Bob" changes his password, remove all tuples ("Bob", *, *, *) from the cache.

  • The cache has a limited size. If the cache is full and you want to insert a new tuple, remove the oldest one (the one for which the "age" field is farthest in the past). This is called LRU caching (as in "Least Recently Used").

There is no specific reason to treat positive and negative hits differently; either contains an interesting information. Note that there is no need for a time limit here; as long as the cache is updated (or merely flushed) when there is a password change, there is no problem in keeping cache entries for arbitrary amounts of time.


If you cannot update the cache upon password changes, then you need to set a short timeout so that cached information is not used if it is older than, say, 20 seconds (as you envision). There again, positive and negative hits need not be handled differently; in fact, it can be argued that caching negative hits (user+password mismatch) is necessarily safe since, at worst, it keeps users out; caching positive hits can, on the other hand, allow people entry with a password that has been invalidated (though with a 20 seconds timeout, the vulnerability window is quite small).


Summary: caching authentication failures is good, because it is fail-safe (it won't grant entry when it should not). Keep in mind, though, that it won't thwart DDoS: a DDoS-ing attacker will simply send many requests with random passwords, i.e. requests which are never in the cache in any case. Caching authentication failures helps against involuntary DDoS, when a user has entered the wrong password but does not understand it, and clicks on "refresh" repeatedly.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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