Do Key-Derivation Functions pose a Denial-of-Service Threat for APIs?

Question

Imagine a simple API, which offers an endpoint POST /account/authenticate, which takes a username and password, then returns a JWT on success and an error on failure. In the backend, the endpoint uses some key-derivation function like Argon2 or PBKDF2, with the parameters tuned to be difficult to crack.

Wouldn't such an endpoint allow a very simple resource exhaustion attack? An attacker can cause a high workload on the server without having to do a lot of work themselves. Depending on how the KDF is configured, many parallel requests can consume large amounts of server memory.

Is this actually an issue? And if so, how can this be mitigated? Since this is an API, typical front-end measures like CAPTCHA are not possible.

Answer 1

Yes, that is a valid concern. As for how to mitigate it, you have several (not mutually exclusive) options:

1. One thing that you've already implemented is not doing slow key derivation on every request, but rather having an authentication endpoint that takes a passphrase (or equivalent), applies a slow key-stretching KDF, verifies the correctness of the result and returns a (typically time-limited) token that can be used for fast authentication of subsequent requests.

   What such a token should contain depends on your backend implementation. If you can easily and securely store session data on the backend, probably the easiest solution is to simply generate a (cryptographically) random token of, say, 128 or 256 bits and return it to the client. You can then store any sensitive information needed for backend processing — possibly including the master pseudorandom key output by the KDF, or one or more subkeys derived from it — in the backend session storage keyed by the random token.

   If you want your backend to be stateless, things get more complicated. One option, if you can arrange your backend to have access to a secret encryption key, is to use something like a JWE token directly encrypted with the secret key (using an authenticated encryption algorithm — but fortunately all the encryption algorithms supported by JWE are authenticated!) and containing any information the backend needs for fast authentication. Depending on what you're doing in the backend, that might include one or more keys derived from the KDF output, but for applications that don't need to do any per-user encryption or decryption on the server, even just the ID of the authenticated account may be sufficient.

   Now, obviously, just restricting slow key derivation to a single endpoint won't prevent that endpoint from being DoSed. But it does reduce the server load from key derivation in normal usage, and it also paves the way for further DoS countermeasures, such as:

2. Rate limit your authentication endpoint. With appropriate rate limits in place, a DoS attack on your authentication endpoint should only be able to deny access to that endpoint, but not interfere with clients that have already authenticated. While that's still not ideal, it's a significant improvement, especially if you allow your clients to establish fairly long-lived sessions (say, 1 day).

   For some simple types of DoS attacks, finer-grained rate limiting based on e.g. source IP address can be even more effective than just a single global rate limit. Yes, distributed attacks e.g. via botnets can circumvent such rate limiting, but the reason why server-side KDFs can be tempting DoS targets in the first place is because they can allow easy DoS without the massive bandwidth of a botnet. If your attacker has a botnet, they probably don't need to target your KDF.

3. If you cannot or don't want to implement explicit rate limiting, a "soft" alternative can be to run your authentication endpoint on a separate server, or at least in a separate resource-limited container. This also prevents a DoS attack on the authentication code from taking down the rest of the service. Of course, for this to work, the authentication server and the rest of the endpoints need to share access to the same session storage, and/or to the same token encryption keys.

4. As noted in ThoriumBR's answer, you could also require the client to submit a proof of work as part of the authentication request. Essentially, this forces the client to spend as much effort on the request as the server will spend on computing the KDF, or at least some reasonable fraction thereof, thus eliminating or reducing the attacker's leverage. However, I would not actually recommend this approach, since if you can do this, there's an even better alternative:

5. IMO the absolute best way to avoid DoS via slow KDFs is to offload the slow key derivation to the client. Basically, instead of having the client send a passphrase to the server, which then uses a slow KDF (such as PBKDF2 or Argon2, etc.) to derive a pseudorandom master key from it, just have the client run the slow KDF and send its output as part of the request.

   This does require somehow ensuring that the client knows which salt, iteration count and other KDF parameters it needs to use. Probably the easiest way to handle this is simply to have the client request these parameters from the server in a separate request. For most parameters this is no problem (although the client should definitely at least enforce a minimum iteration count!), but the salt does require some extra consideration:

   • If you don't want your pre-authentication endpoint to disclose which user IDs exist on your system, you'll have to generate fake salts for nonexistent usernames, e.g. by hashing the username together with a server-side secret. (Of course, preventing the leakage of user IDs is not always either desirable or practical anyway.)
   • In any case, you'll leak the user's salt, which means that an attacker may observer any changes to it. If you follow the standard procedure of changing the salt whenever the user changes their passphrase, this can allow an attacker to both confirm that a user ID exists (assuming your fake salts don't change) and that the user has (or has not) changed their passphrase since the attacker's last query. In general, this leak seems more or less unavoidable, except by using a fixed salt for each user (which has its own issues).
   • You may also want to have the client augment the salt sent by the server e.g. by appending the user ID and possibly some server- or application-specific string to it. This is to prevent a MiTM attacker from tricking the client into using a salt and KDF parameters belonging to the same user on another service, which could be an issue if the user used the same passphrase for both services.

   Also, you'll probably still want to run the KDF output sent by the client through a second KDF on the server — but this second KDF can be a fast KBKDF such as HKDF (RFC 5869). Depending on your application, this may not be strictly required, but it doesn't hurt and can have various advantages. In particular:

   • it allows you to derive multiple subkeys and/or check values of any desired length from the KDF output, without the client needing to be aware of this;
   • if you're using (part of) the KDF output for user authentication, by comparing it with a "password hash" string stored in your user database, having a server-side KDF step prevents an attacker who compromises your database from using the stored hash directly to authenticate;
   • it protects you against potential attacks using malformed input by ensuring that, whatever the client sends you, it goes through HKDF before it touches any other cryptographic code on your server.

Answer 2

Yes, they can potentially be a DoS issue (either for CPU or memory) if you don't have any kind of rate limiting in place. But then if you're not rate-limiting login requests, you have all kinds of other security issues as well.

Rate limiting, CAPTCHA, IP blocking, etc can also be used to protect against this. You also need to find an appropriate balance when you tune your hashing algorithm - the harder you make it to crack the hashes, the more expensive logins become, and thus the easier you are to run into resource exhaustion issues (either from an intentional attack or just high volumes of traffic).

There have also been cases where allowing very long password inputs could lead to a DoS (as the hashing of these was much more expensive). Django published an advisory on this back in 2013, and implemented a 4096 byte maximum password length to protect against it.

Answer 3

You don't need captcha, you can make the client send a proof of work token along with the username and password.

It would go like this:

1. Client GET /account/challenge and receive a nonce

2. Client have to MD5(nonce + random string) until he finds a hash with the first (or last) 4 digits as zeroes

3. Client POST /account/authenticate with nonce, random string, username and passord

4. If you calculate the hash and it checks out, you can execute the KDF

I am sugesting MD5 here because it's a fast hash, and you want a fast hash on the server side to spend little time calculating it. You can increase the difficulty of the proof of work if needed, and it won't change the load on the server, only on the client.

Answer 4

Your endpoint presumably checks that the username exists in your account database (an inexpensive check) before proceeding with the more expensive key derivation function. Presumably your attacker does not know a large number of usernames to hammer away at your endpoint with. So, you should be able to mitigate this type of attack to some degree by rate-limiting the number of attempts per username.