Implementing Login Velocity Checks

Question

I need to implement login velocity checking for a web service. The service is in ruby and the database is MySql.

I can imagine bad ways to do this. For example, have a table that stores every login attempt's time and whether or not it was successful, and every time the user tries to log in, query that table for the last n login attempts and run some simple algorithm against it. That seems pretty clearly grossly inefficient, though. Every login attempt does a select and an insert on a pretty large table which will slow down the system as a whole.

A better way might be to say that the value of n is hard-coded to be three or something, and in the user table (wherever password verifiers are stored) add n columns which hold the most recent n login attempts. This removes the extra select statement, and the user table is presumably much shorter than the login attempts table would be. However, it looses a lot of data that could be interesting if the algorithm were to change.

At this point I'm leaning towards a variation on that structure which puts a single text field in the table with the password verifiers, and that text field holds a serialized object which is an array of login attempt records. On a login attempt that field would be parsed and rewritten. This solves the fixed n problem while preventing having to query a very large table. However, reading text fields out of the database of course has poor disk access characteristics which may end up making it a poor solution as well.

Finally, another possibility is to use MySql's log-file-backed database (who's name I don't know), but I know almost nothing about it, except that it is supposed to be efficient at querying log files.

My question for Stack Overflow is: How are login velocity checks normally implemented in industry?

Update 1:

I should have defined velocity check. A velocity check for login attempts keeps track both of the number of consecutive failures and the time frame in which consecutive failures occurred. The first reply does point towards a solution with those properties. I wonder, though, if it retains enough information to allow for flexibility in the velocity checking. Having never built such a system, my concern is that I am overlooking important aspects of velocity checking that I will wish to have considered when I started building it...

Answer 1

I believe in the asp.net default membership provider there is a column on one of the user tables called FailedPasswordAttemptCount, im sure it just increments for every failed attempt, then resets to 0 when successful. With that column and a LastLoginAttemptTimestamp column you can lock out users for a certain amount of time.

Answer 2

I can imagine bad ways to do this. For example, have a table that stores every login attempt's time and whether or not it was successful, and every time the user tries to log in, query that table for the last n login attempts and run some simple algorithm against it. That seems pretty clearly grossly inefficient, though. Every login attempt does a select and an insert on a pretty large table which will slow down the system as a whole.

If you know what the max velocity is then you could easily clean out loads of entries in the "failed login" table on a regular (daily would suffice unless you're expecting tens of thousands of failed logins per day).

It would be good to consider how many logins and bad logins you expect to have per day.

Answer 3

In the end I built something similar to what John Boker suggested. The table used to authenticate users has two new columns -- failed_login_count and first_failed_login which is a DateTime object. Each time the user successfully logs in, the failed_login_count is reset to 0 and the first_failed_login is reset to null if they weren't already. Each time there is a failed login attempt, the failed_login_count is incremented. If it was 0, first_failed_login gets the current time. Each time the user attempts to log in, the velocity check happens before verifying the password. If failed_login_count is greater than 0 it is divided by the difference in time between the current time and first_failed_login. If that value is greater than the maximum allowed velocity, the velocity check fails.

In addition, I aggressively log failed login attempts and failed velocity checks for future offline processing so that I can track attempts to brute force accounts and disable accounts that have too many failed login attempts without having to track the details necessary for those computations in the database itself.