JS challenge based on computational complexity

Question

Assuming I have a website with a button that sends AJAX requests to my server which will be expensive to process. I suppose that mostly cookie or JavaScript + cookie challenges are used to prevent (most) attacks from bots. This way, only requests sent by bots who can process cookies (and JavaScript) would be processed by my service. However, requests by bots using headless browsers that support cookies and JavaScript will still be processed, so the system will still be vulnerable to this kind of attack.

I came up with another idea that uses a JavaScript challenge with more computational complexity to mitigate attacks. Like when hashing passwords, a higher number of hashing iterations will not be a problem for a legitimate user (because a few milliseconds won't hurt when hashing one password), but will prevent an attacker who gained access to a database from brute-forcing the hash (as those milliseconds add up to years).

My idea is that I give the user a script to compute a token that is needed to access the service, exactly like in a JS cookie challenge. But as opposed to a JS cookie challenge, I would give the user a script to solve a cryptographic problem that will take a few milliseconds on fast systems (and like 100ms on slow ones). After a legitimate request the user will get a new script/problem to compute in the background. A legitimate user wouldn't notice a script running for about 100ms in the background after loading the website and after each click on the button. However, an attacker would be limited to send about 100 requests per second per processor, and they would need a lot more resources to launch an effective attack. With a scalable design, I could scale the complexity of the problem with my current server load, and I could give heavier tasks to users whose IP addresses generate excessive traffic. This design would also work without cookies, so I wouldn't have to show a banner when targeting EU states.

My questions are:

1. Does a system like that make sense? Is this used in practice and if not, why?
2. What would be a good scalable challenge for this? I would need a one-way-function that can be reversed with a simple algorithm (which of course is not efficient by definition). I am thinking about letting the user compute a prime factorization of a product of random prime numbers.

I would also appreciate literature recommendations about stuff like JS cookie challenges, as I couldn't find any.

Answer 1

Simplest way to make this is to create a hash (not too complicated) on server side consisting from per-hash-random bytes appended with per-hash-random difficulty-related secret bytes like this (in PHP):

function make_hash_challenge() : array {
    $shared_bogus = base64_encode(random_bytes(16));
    $secret_bogus = random_bytes(3);

    $shared_hash = sha1($shared_bogus.$secret_bogus);

    return [$shared_bogus, $shared_hash, $secret_bogus];
}

Then you just share the $shared_bogus and $shared_hash with the client and ask him/her to calculate or bruteforce the $secret_bogus (it really does not matter how he/she solves the challenge as long as he/she is forced to do so before getting any service). To get service from your server client must first send the calculated $secret_bogus to the server so it can be verified.

The client solves the challenge with his/her computer (ie. with javascript) using the same kind of method. The greater the secret bytes is the greater the time and cost consumed by the client is. You can make this happen on the background so the human user won't easily detect the challenge. Please note that when you exceed 24 bits in difficulty (3 bytes) calculating turns into something very difficult to solve fast with regular computers.

Also it is important to create a new random $shared_bogus for every challenge so it is more challenging to use hashtable attacks. Increasing the size of $shared_bogus makes it harder to do so and has only a small impact on performance.

Answer 2

If you want to deter bots and headless browsers, you need a CAPTCHA. It's made exact for that: easily allowing humans to access the resource, but making almost impossible to computers to do so.

If you want to disallow anyone making 100 requests per second, you use rate-limiting. You can use a cookie to identify each user, and use exponential wait times (or outright block) after a number of requests per second.

You can use cookies and not need to inform the users in this case:

the ability to route information over a network, by identifying the communication ‘endpoints’ – devices that accept communications across that network;

So if your site have any load-balancing server that needs cookies to work, you can use cookies and don't need to inform the user.

If your data is valuable enough, attackers will get it. If something can be automated, it will be. So using a proof of work solution may not work on your case, as an attacker can pool lots of computers and calculate your challenge pretty easily.

Answer 3

Does a system like that make sense?

No, it doesn't make any sense.

You cannot force an attacker to do any computations. The attacker can just generate tokens by brute-forcing without spending any resources on your computation. Instead, you will spend resources on the server side to check if the token is correct, or, if you precomputed it and saved in the database, by looking up the token in the database.

What would be a good scalable challenge for this?

Again, you cannot force the attacker to do any computations you want. You cannot prevent the attacker from sending any random token.

What can you use instead? For instance, you may want to use signed tokens like JWT. Then you don't need database. When you receive a token, first check the signature. If invalid, then just ignore the request.