Reducing DDoS Attack Asymmetry with Self-Checking API Keys

Break&Build Security
10 min readJun 13, 2024

--

Preventing Distributed Denial of Service (DDoS) attacks requires multiple layers of protection. These attacks come in various types and with different levels of sophistication. We will specifically examine DDoS attacks that involve a high volume of Layer 7 HTTP requests originating from numerous IP addresses. Our focus will be on sophisticated attackers targeting authenticated APIs (like using a bearer token) who understand how to authenticate to a target API and could craft requests that are indistinguishable from those made by legitimate clients.

This blog post won’t cover all these layers but will explore some lesser-known ones that are not yet widely documented.

Rate limiting

The most basic, well-known, and widely adopted method to prevent a DDoS attack is implementing a rate limit, typically in a Web Application Firewall (WAF). Examples include AWS WAF and Cloudflare WAF. Cloud-based WAFs are highly scalable so you don’t need to worry about capacity.

WAF rate limits work by counting the number of HTTP requests made from an IP address within a short period of time. If the requests exceed a specified threshold, the WAF blocks the IP address, preventing HTTP requests from that IP from being forwarded to the service. This block remains in place until the rate limit is satisfied either or for an arbitrary defined time.

When setting rate limits you must err on the side of caution and set thresholds well beyond your largest customer’s typical traffic. For instance, if your largest customer regularly exceeds 300 requests per second from a single IP address and your rate limit evaluation window is 5 minutes, you need to allow at least 90,000 requests within that period (5 min x 60 seconds in a minute x 300 requests per second). To ensure you don’t block this and other customers, you might need to double the threshold to 180,000 requests in 5 minutes per IP address.

This rule permits any IP address to make up to 180,000 requests in 5 minutes, whether spread out or concentrated in a single second and only prevents exceeding 180,000 requests within the 5-minute window.

Architecture

Let’s consider a typical diagram of an authentication flow for an API. The WAF could have a rule that blocks HTTP requests if there is no API key present such as checking for the presence of a specific header. More advanced rules could verify if the API key follows a certain format (example regex for Github personal tokens /ghp_[a-zA-Z0–9_]{36,255}/) or length. However, the WAF can’t determine whether the API key is valid by itself. For this example, let’s assume API keys are 144-bit secure random base64 encoded strings that result in exactly 24 characters.

Please note: 144-bit keys provide high entropy and are divisible by 6, so there are no trailing equals signs (‘=’) to manage when base64 encoding.

Authentication is typically handled by an identity platform after the WAF layer. The identity platform checks the structure of the key, verifies its presence in the database, and ensures it is enabled for use on the platform.

Validating a well formed API Key that doesn’t exist in the Database

Withstanding a DDoS Attack

In very large Distributed Denial of Service (DDoS) attacks, the number of IP addresses making requests can reach into the millions (Dyn DDoS).

When a large number of IP addresses make multiple validly formatted HTTP requests, including randomly generated API keys that fit the valid format, the identity platform must perform the API key validation. The first step is to check if the API key is present in the cache. All these requests result in expensive[2] cache misses. Subsequently, the platform must query the database, which will also result in a miss, and then reject the request with a 401 HTTP response code.

If a small DDoS attack involves 10,000 IPs making 10 requests per second, you would need to handle 100,000 requests per second in addition to your regular customer traffic. Since this would only be 3,000 RPS per IP, well below the 180,000 requests per IP allowed in a 5-minute window, no requests would be blocked. This is manageable, however, consider a scenario where there are around 100,000 IPs, each making 30 requests per second. This would require handling 3,000,000 requests per second, which is difficult to manage. Despite this, none of the IP addresses would hit the rate limit and be blocked.

DDoS Protection

It’s likely that your DDoS protection service will initialize but not prove useful or maybe even harmful. Since the requests look legitimate, the system might start blocking legitimate traffic while allowing malicious traffic. The effectiveness of this protection will depend on the vendor and each situation. However, there is another option to prevent those 3 million requests per second from reaching your system.

Some DDoS vendors check if the requests are all of the same type, recognizing that such uniformity is uncommon. However, a sophisticated attacker can randomize or sequence different types of requests, making detection much harder.

Ideally, your WAF supports rate limits based on HTTP response codes, allowing you to set smaller thresholds. Requests with invalid API keys would generate 401 HTTP response codes. You could configure a rule such that if 60 requests in 1 minute return a 401 code, the WAF blocks that IP address for 1 hour. This can be done in Cloudflare, but I don’t believe it’s possible with AWS WAF.

Self-checking API Keys:

Let’s explore another protection layer that may complement a WAF or DDoS protection. What if, when we receive an API key, we could quickly check if it has been issued by our service? Ideally, we could do this without any database queries and in parallel.

HMAC API Key authentication

The easiest way to implement self-checking API keys is to append an HMAC using a static secret key during generation. The API key would then be composed of 24 base64 characters followed by the HMAC-SHA1 (good enough for our use case). For example, AJf1NtNSU9kgSlNAlsNiBnXc.Bb8QqLHGvnc0ESPl8rXJJgJ16D6j.

Every request including an API key can be verified in isolation. Requests containing API keys not generated by the service, those that fail at matching the HMAC, will get rejected.

The fastest way to implement this check is for the “Identity Platform” from the diagram to perform the check. A basic benchmark on a 2019 Macbook pro gives that it can do over 200k HMAC ops/second using 1 CPU, so the solution scales pretty well. Remember that this can scale horizontally indefinitely, it doesn’t require expensive storage or database queries, the only issue is if you can scale fast enough, and that will be discussed too.

Validating a well formed API Key that fails to self-check

Dealing with malicious but self-checking keys

Using HMAC has its own set of issues, which we will discuss later. However, the major concern is: what if the attacker has access to a valid self-checking API key? Couldn’t they just use that key for every request? Let’s assume there are limits on the number of API keys an attacker can obtain. Even if the service allows free users to create their own API keys, there should be some restrictions in place to ensure an attacker cannot gain access to millions of them.

An attacker could potentially acquire API keys that were accidentally leaked by customers. Even if these keys have been revoked, they are still self-checking. Another source of valid API keys is demos and examples, which often use revoked keys that are still capable of self-checking.

You may already have some form of concurrency or rate limits per customer or API key to prevent service abuse, whether intentional or accidental. However, during a DDoS attack, these limits can become very costly. Therefore, an additional layer of defense is necessary.

When you detect requests that trigger your concurrency or rate limits, and they are from revoked self-checking API keys, automatically add them to the WAF for blocking. If they are not revoked, it could be a bursty customer or an attacker using a stolen API key. In such cases, you may want to wait a bit before blocking to avoid accidentally hindering a legitimate customer. Additionally, consider checking whether the customer is large, on a trial, etc., before deciding. Your WAF rule should also block IP addresses using those API keys for at least a couple of hours, in case they have a bunch of self-checking API keys to switch to.

One of the main downsides of this self-checking API key solution is that the WAF cannot hold an unlimited number of API keys to block.

TIP: In the WAF string matching rule you can just use the first 24 characters from the API Key, since they are already unique, making the rule more efficient.

Why HMAC is not a great idea: Asymmetric signatures

The issue with HMAC is that the same cryptographic key is used for both creating and verifying API keys. If the cryptographic key is ever leaked, and assuming the API keys don’t expire, a sophisticated attacker can generate self-checking API keys indefinitely. Your only recourse would be to ask your customers to generate new API keys using a new cryptographic key.

The best way to mitigate this problem is to use a Hardware Security Module (HSM) to generate a Signing Key Pair. In AWS, you can use KMS or CloudHSM. By signing the API keys within the HSM the Private Key never leaves the secure environment. You can then distribute the Public Key to all locations that will perform the API Key self-check. If the Public Key is ever leaked, it’s not a big issue.

We are also assuming that you will not be generating thousands of API keys per second — just a few each time a customer creates an account or rotates one. AWS KMS or CloudHSM can handle this without any issues, and the cost is manageable.

At this point, I suggest using the JWT standard with ES256 or EdDSA. These algorithms are efficient, secure, and produce short signatures. Using JWT is advantageous because you may have logic in various places written in different programming languages to verify the signature. Delegating this task to an established set of libraries is more convenient and reliable than writing your own.

My benchmarks, using the same setup as before, give me around 12,500 and 15,500 verifications per second per CPU for ES256 and EdDSA respectively. This is an order of magnitude slower than HMAC. Therefore, scale your infrastructure accordingly.

An EdDSA token can look like this, it includes an API Key as “sub”:

eyJhbGciOiJFZERTQSIsInR5cCI6IkpXVCJ9.eyJzdWIiOiJBSmYxTnROU1U5a2dTbE5BbHNOaUJuWGMifQ.CfEp8yjF-qP6Pb52TBN5EbBZdsa_MeRQHbm5CgPdKjijAM-oiyVBw9t4RyDXRGHHSmMZ-mZQ0SNZJNKT2R9sCw

It’s quite longer than an HMAC API Key. Since the header is static you could get rid of it and add it right before verifying the JWT if you want to make it shorter.

Scaling

We discussed that the easiest way to implement the self-check key verification is within the identity platform itself. Since you already have this in place, it’s simply a matter of adding one more check.

In everyday operations, you don’t need to perform self-checking for every API key, as over 99% of your keys will pass validation. Begin self-checking when you notice a spike in traffic. Just consider suddenly enabling verification can overwhelm the system. Ensure your fleet is sized appropriately before enabling this feature.

A better approach is to move the verification logic outside of your managed infrastructure. In AWS, the best solution is CloudFront Functions, followed by Lambda@Edge. Additional options include Lambda integration with API Gateway. In Cloudflare, you have Cloudflare Workers, similar to CloudFront Functions. Both services support global key-value stores, which can store the revoked self-checking API keys used in a DDoS. This approach not only reduces the load on your identity platform but also on your reverse proxy, WAF and any other layers you may have on top.

AWS documentation mentions JWT validation in Cloudfront Functions. This service has size and duration restrictions — 10KB for code and 1ms for execution — but this is more than sufficient for JWT verification. On the bright side, CloudFront Functions can scale up to 10,000,000 requests per second and is cheaper than Lambda@Edge, which offers more flexibility. You can see a comparison made by AWS here.

Validating a well formed API Key that fails to self-check in an Edge function

Signing Key tiers

Until now we considered just using one signing key to do all the signing but it doesn’t need to be the case. One way is tiering customers with different signing keys, let’s say you have Tier 1 for big customers, Tier 2 for paying customers, and Tier 3 for free/trial customers.

Assume you just implemented HMAC authentication in your Identity Platform, no edge verifications, during a DDoS you may still be overwhelmed with invalid API Keys, so you can decide to just let through Tier 1 customers and only after verification check your DB to check it’s a valid customer. You would be sacrificing smaller customers, but it’s better Tier 1 customers than no customers at all. The attacker could figure out what’s the Tier 1 identifier, but still you are dealing with a small set of customers compared to all of them.

Conclusion

DDoS attacks exploit the asymmetry of compute, traffic, and cost that an attacker can leverage using a botnet against a legitimate service. I developed this solution to reduce that asymmetry. While the asymmetry still exists, I believe this approach helps to shrink it significantly, especially when combined with other existing DDoS prevention layers. The solution has its complexities, advantages, and disadvantages, so be sure to perform your own assessment. This is particularly important if you already have a service with many API keys that would need to be rotated.

We didn’t touch the concern of formatting API Keys to be easy to identify to detect unintentional leaks. I recommend a Github blog post about it.

--

--

Break&Build Security

https://www.linkedin.com/in/santikanto/ I’m Santiago Kantorowicz, Principal Associate Security Architect @ Twilio. Passionate about CyberSecurity.