Using an NP-complete problem to deter malicious clients

1. A system for authenticating a user, comprising:

a non-transitory memory storing instructions; and

one or more hardware processors coupled to the non-transitory memory and configured to execute the instructions to cause the system to perform operations comprising:

receiving, from a computing device, a first login request for logging into an account;

retrieving an identity profile associated with the computing device;

determining a first reputation score for the first login request based on the identity profile;

determining a first number of terms for a first challenge-response problem based on the first reputation score, wherein the first challenge-response problem comprises a first NP-complete problem;

configuring the first challenge-response problem to use the first number of terms determined based on the first reputation score;

sending the first challenge-response problem to the computing device;

denying the first login request based on at least one of a first login credential or a first solution to the first challenge-response problem received from the computing device;

subsequent to denying the first login request, receiving, from the computing device, a second login request for logging in to the account;

determining a second reputation score for the second login request based on the first reputation score and a determination that the first login request has been denied;

determining a second number of terms for a second challenge-response problem based on the second reputation score, wherein the second challenge-response problem comprises a second NP-complete problem;

configuring the second challenge-response problem to use the second number of terms determined based on the second reputation score;

sending the second challenge-response problem to the computing device; and

authorizing the second login request in response to verifying a second login credential and a second solution to the second challenge-response problem received from the computing device.

2. The system of claim 1 , wherein every additional number of terms in each of the first and second challenge-response problems causes (i) a first increase in computing power required to produce a response for the challenge-response problem and (ii) a second increase in computing power required to verify the response, wherein the second increase is less than the first increase.

3. The system of claim 1 , wherein at least one of the first challenge-response problem or the second challenge-response problem is a subset-sum problem.

4. The system of claim 1 , wherein the identity profile includes data representing past login attempts made through the computing device.

5. The system of claim 1 , wherein the identity profile includes an internet protocol (IP) address associated with the computing device and types of transactions conducted by the computing device.

6. The system of claim 1 , wherein the first number of terms for the first challenge-response problem is determined to be lower based on a higher reputation score or the first number of terms for the first challenge-response problem is determined to be higher based on a lower reputation score.

7. The system of claim 1 , wherein the operations further comprise:

determining a computing power of the computing device,

wherein the first number of terms for the first challenge-response problem is determined further based on the determined computing power.

8. The system of claim 1 , wherein the operations further comprise:

determining a type of application that generated the first login request, wherein the first number of terms for the first challenge-response problem is determined further based on the determined type of application.

9. A method comprising:

detecting a first login attempt for logging into a user account made through a computing device;

determining a first reputation score for the computing device based on attributes associated with the computing device;

determining a first number of terms for a first challenge-response problem based on the first reputation score, wherein every additional number of terms in the challenge-response problem causes (i) a non-linear increase in computing power required to produce a response for the challenge-response problem and (ii) a linear increase in computing power required to verify the response;

configuring the first challenge-response problem to use the first number of terms determined based on the first reputation score;

denying the first login attempt from proceeding in response to receiving a wrong solution to the first challenge-response problem or determining that a response was not provided within a predetermined period of time;

subsequent to denying the first login attempt, detecting a second login attempt for logging in to the user account made through the computing device;

determining a second reputation score for the second login attempt based on the first reputation score and a determination that the first login attempt has been denied;

determining a second number of terms for a second challenge-response problem based on the second reputation score;

configuring the second challenge-response problem to use the second number of terms determined based on the second reputation score;

sending the second challenge-response problem to the computing device; and

processing the second login attempt in response to verifying a solution to the second challenge-response problem received from the computing device.

10. The method of claim 9 , wherein each of the first and second challenge-response problems is an NP-complete problem.

11. The method of claim 10 , wherein the NP-complete problem is a subset-sum problem.

12. The method of claim 9 , wherein the attributes include a number of past login attempts made through the computing device within a predetermined period of time.

13. The method of claim 9 , wherein the attributes include an IP address associated with the computing device and types of transactions conducted by the computing device.

14. The method of claim 9 , further comprising:

in response to denying the first login attempt, updating an identity profile associated with the computing device to increase a count of failed login attempts.

15. The method of claim 9 , wherein the second login attempt is processed further based on verifying a login credential received from the computing device.

16. The method of claim 9 , further comprising:

determining a computing power of the computing device,

wherein the first number of terms for the first challenge-response problem is determined further based on the determined computing power.

17. The method of claim 9 , further comprising:

determining a type of application from which the first login attempt is received,

wherein the first number of terms for the first challenge-response problem is determined further based on the determined type of application.

18. A non-transitory machine-readable medium having stored thereon machine-readable instructions executable to cause a machine to perform operations comprising:

detecting a first login attempt for logging into an account made through a computing device having an associated identity profile;

determining a first reputation score based on the associated identity profile;

determining a first number of terms for a first NP-complete problem based on the first reputation score;

configuring the first NP-complete problem to use the first number of terms determined based on the first reputation score;

sending the first NP-complete problem to the computing device;

denying the first login attempt from proceeding based on at least one of a first login credential or a first solution to the first challenge-response problem received from the computing device;

subsequent to denying the first login attempt, detecting a second login attempt for logging into the account made through the computing device;

determining a second reputation score for the second login attempt based on the first reputation score and a determination that the first login attempt has been denied;

determining a second number of terms for a second NP-complete problem based on the second reputation score;

configuring the second NP-complete problem to use the second number of terms determined based on the second reputation score;

sending the second NP-complete problem to the computing device; and

authorizing the second login attempt in response to verifying a second solution to the second NP-complete problem received from the computing device.

19. The non-transitory machine-readable medium of claim 18 , wherein the first number of terms for the first NP-complete problem is determined to be lower based on a higher reputation score or the first number of terms for the first NP-complete problem is determined to be higher based on a lower reputation score.

20. The non-transitory machine-readable medium of claim 18 , wherein the operations further comprise:

determining a computing power of the computing device,

wherein the first number of terms for the first NP-complete problem is determined further based on the determined computing power.