1

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.

6
  • Similar to: security.stackexchange.com/questions/222930/…
    – mti2935
    Dec 15, 2020 at 21:13
  • I would send them a password hash and make them respond with the password, using JS I shipped to crack it. Throw an extra step in there to curtail low-effort crackers from proxying your password to an asic or GPU, ex: password>sha3>base64>sha2(x999). The main issue is that everyone can see your js, and thus algo, so targeted hardware-accelerated attacks will always be possible, but hopefully acceptably rare. Use OS-provided crypto/hashing (window.crypto) so that you don't do all the heavy lifting in JS, which would put you at a disadvantage in terms of Ptime.
    – dandavis
    Dec 15, 2020 at 22:39
  • @mti2935, thank you. So this concept is used in practice and I can now find a lot more information about this topic when searching for proof-of-work algorithms.
    – Erik
    Dec 15, 2020 at 23:41
  • @dandavis, thank you too. Using OS-provided crypto/hashing sounds like a great way to mitigate performance advantages of more efficient implementations (compared to writing my own JS code). I guess that my best option would be to stick to established problems/algorithms that are used for example for crypto coins.
    – Erik
    Dec 15, 2020 at 23:42
  • I say to use standard functions, but mix it up a little bit so there's not pre-rolled exploits. You're literally just wasting time, so it doesn't have to be cryptographically secure per-se (as in don't RYO crypto), so long as there is work in the chain to be done.
    – dandavis
    Dec 15, 2020 at 23:50

2 Answers 2

0

An attacker can generate a token randomly without spending any resources on your computation. Thus it will not prevent attackers from brute-forcing.

For simplicity, suppose your tokens consist of 4 alphanumeric characters. An attacker will not waste time computing your algorithm and will instead generate all possible tokens directly: 0000, 0001, ..., 000a, ..., 000z, 0010, 0011, ..., 001a, ..., 001z, ..., 002z, ..., zzzz, ..., ZZZZ.

If you have longer tokens, the approach remains the same. You cannot force the attacker use your algorithm.

There can be many solutions for your problem. For instance:

  • You can generate tokens randomly and they should be long enough. Formally, make sure they have entropy 90 - 100 bits. If you use 64-characters set, then tokens should consist of 16 or more characters. You can store tokens in the database. Validation would mean checking if the token is available in the database and if it is not expired. Brute-forcing such long tokens will take much resources and a lot of time.
  • You can use signed tokens. E.g. use JWT. Then you don't need database. When you receive a token, first check signature. If invalid, then just ignore the request.
2
  • I changed your first point. Regarding your second point, the token must obviously be the correct solution for the problem I provided. I would probably store problems/solutions in a database for verification.
    – Erik
    Dec 15, 2020 at 23:20
  • @Erik: I have updated the answer.
    – mentallurg
    Dec 16, 2020 at 1:20
0

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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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