Using memcached to rate-limit dictionary attacks

Earlier this week, there were a number of high profile Twitter account compromises that were made possible using a common dictionary attack technique. Basically, nothing was in place to keep an attacker from quickly submitting thousands of login attempts against an account, cracking the password in an evening of work.

One tool that can be used to prevent this sort of attack is to rate-limit login attempts, allowing only a few failed attempts per minute, for instance. One problem with this, however, is that it requires tracking login attempts. This is essentially a write operation, and doing this to a database on a high volume site is a major performance bottleneck.

Simon Willison came up with a nice solution to the problem that uses memcached. You can track a counter for requests from an IP and for login attempts against a particular account. Just create the key using a combination of the item you are tracking and the date it is being tracked against:

Let’s say we want to limit a user to 10 hits every minute. A naive implementation would be to create a memcached counter for hits from that user’s IP address in a specific minute. The counter key might look like this:

ratelimit_72.26.203.98_2009-01-07-21:45

Increment that counter for every hit, and if it exceeds 10 block the request.

According to a comment on Simon’s blog, this is essentially the strategy that’s been employed by the Twitter team to rate limit API requests.

Rate Limiting With Memcached