10
$\begingroup$

I'm looking to prevent a DDoS attack on a web service, by making the cost of performing an attack prohibitive. Typical users will only need to call out it once a day, and can afford to spend a few CPU cycles on each call, but I want to make it so an attacker making millions of calls would have spend considerably more than I do hosting the service. There's an inherent cost to the service, so I'd like a "proof of work"-like system where I can know the caller has done a specific amount of computation, and can validate that work for cheaper than it costs them.

The message we sign would be something like a timestamp+nonce. On the server side we validate timestamp is fresh, and nonce isn't reused.

Something like bcrypt has the nice property in that it's designed to be costly, has a sliding cost scale, and is intentionally not easy to optimize in hardware. However, there would be a symmetric cost on my side which is a dealbreaker.

Something like RSA signing seems good, the cost to sign is much much greater than the cost to validate*. However, I'm not sure if it's possible to hardware accelerate RSA, and if you could the protection goes out the window. I want an algorithm where the cost/work is an intentional feature, not a byproduct.

Edit: lots of people are suggesting traditional ways to mitigate DDoS attacks. These are great, and are the best first line of defence for traditional services. I'm adding a more detailed explanation of why I'm asking specifically about POW:

  • This service is anonymous, with no user account/cookies/etc
  • This isn't user facing (no captcha, signups, etc)
  • Serving a valid request is somewhat expensive (computationally) so cheaply rejecting invalid requests before processing will save us significant resources (making the service more resilient to DDoS attacks).
  • We want to change the economics of the equation: if we make abusing our service more costly than just hosting your own version, then it's not likely to be abused. The service is something anyone could clone, they will just abuse ours to save cost/compute.
  • We want to avoid central databases/state-storage as these are typical points of failure/cost in attack/abuse scenarios (and a source of complexity). A "cheap validation" that can be run on cheap and horizontally scaleable edge compute is ideal.

*Source: https://www.fastly.com/blog/is-it-time-for-ecdsa-certificates

$\endgroup$
3
  • $\begingroup$ How would this help against a DDoS? If anything it would make it worse, since attackers could force you to spend cycles signing and validating garbage. $\endgroup$ Oct 27, 2023 at 8:00
  • 3
    $\begingroup$ As mentioned by @BlueRaja-DannyPflughoeft it seems that you are not accounting for the fact that for a DDoS, an attacker will simply send a garbage signature, or a copy of an existing signature. Are you worried about DDoS, or just abuse of the service? $\endgroup$ Oct 27, 2023 at 10:14
  • 1
    $\begingroup$ As mentioned in the title: we're looking for something with asymmetric cost (cheap to validate). This helps in 4 ways: 1) server can stand up to garbage signature attack much better (cheap to detect request isn't valid, validation is much cheaper than the work the service would do, and this horizontally scaleable to edge compute). 2) swings cost of a valid signature attack to be much higher than cost of defending (usually enough to make it infeasible for attacker), 3) increases complexity of generating attack (need custom bot code, not standard botnet), 4) prevents abuse. $\endgroup$
    – scosman
    Oct 27, 2023 at 13:31

5 Answers 5

21
$\begingroup$

The immediately obvious solution would be to do a simple proof-of-work scheme. For example:

  • The server selects two random bitstrings $A$ and $B$, and computes $\text{Hash}(A || B)$.

  • The server sends $B$, $\text{Hash}(A || B)$, and the length of $A$.

  • The client does a search for $A$; when it finds it, it sends it

  • The server validates it.

This is obviously cheap on the server side, and can be made arbitrarily expensive on the client side (by adjusting the length of $A$).

Now, as written, it is vulnerable to be accelerated by a GPU. That can be partially addressed by picking a memory intensive (but otherwise cheap) hash function.

BTW: to answer a question you asked:

However, I'm not sure if it's possible to hardware accelerate RSA

It is certainly quite possible - hardware RSA accelerators are available (and have been for decades).

$\endgroup$
13
  • 4
    $\begingroup$ @scosman: if you want stateless, don't bother with ECDSA. Instead, have the server encrypt the state (and the identity of the client and the current time) using a symmetric AEAD cipher (using a key that only the server knows), and the client responds with that encrypted state. That's a lot cheaper than ECDSA. $\endgroup$
    – poncho
    Oct 26, 2023 at 19:47
  • 8
    $\begingroup$ Precedent: en.wikipedia.org/wiki/Hashcash $\endgroup$
    – Nayuki
    Oct 27, 2023 at 4:03
  • 2
    $\begingroup$ @usul: a nonsense request will be quickly rejected (after a handful of symmetric crypto operations), and so the DDOS possibility is as small as possible. Of course, a sufficiently aggressive DDOS will overwhelm the local network connection - there's nothing crypto on the server can do about that. $\endgroup$
    – poncho
    Oct 27, 2023 at 16:51
  • 2
    $\begingroup$ @Nayuki Hashcash is good addition to thread! They add signing an ID specific to the user (email address for email, or simply public IP address for other services that don't require accounts). Prevents distributing a valid "solution" to many machines for reuse. Add in a timestamp and it's pretty solid. $\endgroup$
    – scosman
    Oct 27, 2023 at 19:50
  • 1
    $\begingroup$ One more contribution to the "how to make POW stateless". After some research, lots of systems seem to use "generate a hash that start with N zeros" approach. The client needs to sign a message with current-timestamp, an ID (their own IP, or the resource ID they are requesting), and a random string. Server can validate cheaply: message hash ends in N zeros, timestamp is recent (last N seconds), and resource ID matches requested resource (or caller IP). Assuming your service has some DDOS protection from mass attack from single IP (Cloudflare) you're all set. $\endgroup$
    – scosman
    Oct 28, 2023 at 15:49
3
$\begingroup$

I think you can safely scrap proof-of-work if your typical pattern is users using the service once per day. Instead you should focus on traditional methods of rate limiting and abuse prevention. Some ideas:

  • require a CAPTCHA for each use of the service
  • if that's not possible, at least require an account and an unique API key
    • require social login for registration (google, github, facebook) - offload the hard work to services that have it figured out already
    • SMS verification, e-mail verification with whitelisted domains to weed out temp mails
    • manually approving accounts, significant delay until account approval to demotivate the attackers
  • IP address insights - block proxies, tor exit nodes, data centers. Good residential IP addresses are quite expensive nowadays.
  • actively monitor bad traffic, block offending accounts, their IP ranges, browser fingerprints, etc.
$\endgroup$
3
  • 3
    $\begingroup$ All good advice, but the service in question isn't user-facing so, most of those options are out. It's also a service type that's typically paid, and frequently abused. My use case is a bit unique and can't use accounts/API keys, hence looking at POW. $\endgroup$
    – scosman
    Oct 27, 2023 at 0:27
  • 1
    $\begingroup$ For mobile another measure is to use platform attestation like Apple App Attest and Android SafetyNet. $\endgroup$
    – user71659
    Oct 27, 2023 at 3:09
  • 1
    $\begingroup$ Note: If you are blocking based on user account, email, SMS, etc, then please don't block IP address as well, because it's less reliable. Only use IP address as a last resort. $\endgroup$
    – user253751
    Oct 27, 2023 at 11:22
2
$\begingroup$

Why make things more complicated than necessary? Just have the server remember the last time the API call was allowed. If it's less than 12 hours ago, reject the call.

The attacker doesn't need to compute your expensive signature - he will just flood the server with wrong signatures, and make the server validate them, which costs the server more work than checking the current time.

$\endgroup$
4
  • 6
    $\begingroup$ And now you've locked out everyone who's behind large-scale NAT. $\endgroup$
    – Mark
    Oct 27, 2023 at 1:52
  • 2
    $\begingroup$ @Mark Who said anything about IP address? Whatever you want to limit, limit based on that. User accounts, most likely. $\endgroup$
    – user253751
    Oct 27, 2023 at 11:21
  • 2
    $\begingroup$ "remember" means a database. A database is usually the first thing to fail during an attack at scale. They either have scaling limits, or get very expensive. POW verification can be done on cheap/horizontally scaleable edge compute. If you can make the cost of using abusing the service greater than the cost of hosting your own version, you remove the inventive to abuse it. $\endgroup$
    – scosman
    Oct 28, 2023 at 15:26
  • $\begingroup$ @scosman The world's least important database. At the point where the POW becomes relevant, you are Cloudflare. If you're not Cloudflare, your bandwidth ran out first... $\endgroup$
    – user253751
    Oct 31, 2023 at 20:54
1
$\begingroup$

I've implemented a PoW-based DoS protection PHP project some time ago. It meets the general requirement of the question, with a few caveats:

  1. it doesn't use nonce - because I believe massive number of request without valid proof might drain server storage due to large number of nonces,

  2. it uses cookies, which you need to prompt users for consent in some jurisdictions.

  3. You need to generate your own key for use in HMAC (which should be easy).

Project Link: https://github.com/dannyniu/powerhash

$\endgroup$
1
  • $\begingroup$ Cool project! But this isn't browser based, and can't use cookies. $\endgroup$
    – scosman
    Oct 27, 2023 at 13:38
0
$\begingroup$

The method I'd recommend is mutual-TLS (mTLS) authentication. Everyone's familiar with HTTPS and TLS certificates, which prove the identity of the server. Mutual TLS sets up the client to have a TLS certificate as well, so they can prove their own identity.

The idea here is that you can have your load balancer or web server validate the client's certificate before the request ever gets to your code. This "pushes security to the left" about as far as you can go.

If a client does not have a valid certificate[*], then redirect them to a sign-up page that takes a long time to load. There used to be a <keygen> element for HTML forms that would generate a public/private key pair, but now cryptograph primatives are handled by the Webcrypto API. For more on the subject, see "How we built Origin CA: Web Crypto" (from the CloudFlare Blog), and the Chromium layout tests for the Webcrypto API. Working example: FreeSSL.Tech.

After that's in place, you can rate-limit individual users and anonymous folks to whatever rates you please.

Footnote:

[*] Make sure to configure your server to only accept certificates that it has signed. If you don't remove the default CAs, then anyone with (e.g.) a free Let'sEncrypt certificate can get through.

$\endgroup$
6
  • 1
    $\begingroup$ That would work for many/most use cases, but the case here is stateless/identity-less. If you have identity/API-keys/etc, there are many ways to tackle this. The goal here is to make the cost of abusing my service significantly more than the cost of just hosting service yourself, while keeping it anonymous/private/stateless. $\endgroup$
    – scosman
    Oct 28, 2023 at 0:50
  • $\begingroup$ DDoS floods can still abuse your service. They can request millions of challenges and submit millions of incorrect guesses as answers. These requests and guesses may not be expensive, but "quantity has a quality all its own". Rate-limiting them requires identifying them, but their identity can be as minimal as a unique random number. Make the identity-generation process computationally intensive. After you've issued certificates, mTLS will minimize the server's CPU load as much as possible. You could even tarpit ip addresses that submit fake certificates. $\endgroup$
    – PFudd
    Oct 28, 2023 at 5:30
  • $\begingroup$ Or use randomness beacons; require the request to include a recent binary blob: csrc.nist.gov/projects/interoperable-randomness-beacons/… /// Or secure timestamping: freetsa.org/index_en.php $\endgroup$
    – PFudd
    Oct 28, 2023 at 5:43
  • $\begingroup$ The problem with proof-of-work is that someone will always have more CPU than you expect. Oooo, I know, force them to use their TPM chip to do the proof-of-work; that way you know it's slow. $\endgroup$
    – PFudd
    Oct 28, 2023 at 5:50
  • $\begingroup$ CloudFlare has looked into this problem and decided to use a javascript challenge, getting the visitor to prove they're a real person, I guess. Sample: gist.github.com/PenelopeFudd/b443efb9592c54ea2afd4441bdecf8ee $\endgroup$
    – PFudd
    Oct 29, 2023 at 5:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.