Per-User Rate Limiting

Posted on 2021-04-14

The Problem

You want to rate limit requests based on application data such as User ID or User Loyalty. However you want to apply rate-limiting before the application layer, so you have no way to trust the client provided values.

This is a common problem, making the industry-standard approach rate limiting by IP (or CIDR block). In fact some popular CDNs only support rate-limits keyed by IP. Unfortunately IP-based limiting usually insufficient as it either allows too much malicious traffic or blocks a significant number of legitimate users (imagine a lot of users behind a carrier-grade or office NAT).

The Solution

1. Pass the application info in a proxy-visible part of the request such as a cookie.
2. Configure the rate limiter to use the application info. (likely falling back to IP-based keys)
3. The application must validate the info and provide a “useless” response if it isn’t accurate.

Step 1 and 2 are quite obvious but step 3 is the secret ingredient to allow a “dumb” proxy to apply rate-limiting based on application values. Step 3 ensues that spoofed values don’t provide any value to the attacker, defeating the purpose of spoofing them in the first place.

Note that “value to the attacker” can be very broad, so make sure that it reflects your rate limiting goals.

• If you are trying to prevent DoS attacks ensure that the validation is sufficiently cheap.
• If you are trying to prevent scraping ensure that you don’t return any valuable data.

Common actions upon a failed authentication may be:

• If the information is being passed in a cookie unset (or correct) the cookie and redirect the user to the same URL.
• Redirect to a login page which only rate-limits by IP.

NGINX Example

NGINX can support this quite easily. Here is an example of rate limiting by User ID which is passed in the uid cookie.

map $cookie_uid $rate_limit_key {
	"" $binary_remote_addr;
	default $cookie_uid;
}
limit_req_zone $rate_limit_key zone=auth:10m rate=10/s;

This snippet applies the same limit to users and IPs but two limit_req_zones can be used to enforce different limits for each group.

Concerns

Lock-out on Mismatch

Be sure that you don’t lock out a user based on a mismatch. For example if you use an auth-token in the cookie to validate the user ID don’t return a 401 if the auth token is expired or revoked. This will result in the user having all request blocked with no obvious way to fix the problem. (Your support team will probably need to ask them to clear their cookies).

As mentioned above a better option would be to clear the untrusted data so that the user reverts to the regular IP-based filtering.

Cost of Validation

The cost of validation is likely low. This is because you will generally want to validate the auth-token for authenticated requests anyways and validating the auth-token will often give you enough information to validate the rate-limiting settings anyways (for example the user ID). However for requests for public information this validation may be otherwise unnecessary and raise the overall cost of serving the requests.

Unfortunately I don’t know of any great solutions, this is a cost of rate limiting based on authentication, you actually need to perform the authentication! One workaround is excluding requests for public data from rate limiting, then you don’t need to validate the authentication information. However be sure that the requests that bypass the rate-limit in sync between the rate-limiter and the application as any endpoint that isn’t validated is effectively unlimited (as an attacker can send a random rate-limit key for each request). One easy way to keep this in-sync is to strip the rate-limit key from the request before passing it to the application, then the application doesn’t have anything to validate. This approach will reduce the cost but will leave the application exposed to scrapers, using a very high IP-based rate limit may be enough to prevent the worst attacks without affecting many legitimate requests.

Possible Tweaks

Key Passing

Passing the rate-limiting info via cookie is an easy option because it is automatically added by the browser to all subsequent requests, however basically any method will work, including URL parameters or custom headers. Just be careful about locking a user out. If you are using a custom method to pass the rate-limiting information you need to ensure that all of your clients will gracefully handle a request that has been rejected due to mismatched rate-limiting information.

Variable Limits

If you have a flexible enough rate-limiting system you can even set the rate limit based on the application data. For example logged-in users may get 10r/s but logged in users who have spent at least $20 can make 20r/s. This can be a good way to prevent the effectiveness of account-spamming while serving your most loyal customers reliably.