# US 10,872,136 B2 · Using an NP-complete problem to deter malicious clients > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 10,872,136 B2 - Document ID: US10872136B2 - Status: Granted - Kind: B2 - Application number: 15/857,172 - Filed: 2017-12-28 - Published: 2019-07-04 - Granted: 2020-12-22 - Earliest claimed: 2017-12-28 - Assignees: Paypal, Inc. - Applicants: Paypal, Inc. - Inventors: John Franco - Web page: https://patentgrep.com/patent/US10872136B2 ## CPC - G06F 21/316: {by observing the pattern of computer usage, e.g. typical user behaviour} - G06F 16/903: Querying (for retrieval from the web G06F16/953) - G06F 17/10: Complex mathematical operations {(function generation by table look-up G06F1/03; evaluation of elementary functions by calculation G06F7/544)} - G06F 21/44: Program or device authentication - G06F 21/554: {involving event detection and direct action} - H04L 9/088: {Usage controlling of secret information, e.g. techniques for restricting cryptographic keys to pre-authorized uses, different access levels, validity of crypto-period, different key- or password length, or different strong and weak cryptographic algorithms (network architectures or network communication protocols for using time-dependent keys in a packet data network H04L63/068)} - H04L 9/3271: {using challenge-response} - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) - H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M) ## Abstract Methods and systems for using a challenge-response problem to deter malicious clients are described. A login attempt from a computing device with an associated identity profile is detected. A reputation score is determined based on the identity profile, and a strength of a challenge-response problem for use with the login attempt is set based on the determined reputation score. The challenge-response problem with the set strength is then sent to the computing device. The login attempt is permitted to proceed when a solution to the challenge-response problem received from the computing device is verified. ## Claims ### Claim 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. ### Claim 2 (depends on 1) 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. ### Claim 3 (depends on 1) 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. ### Claim 4 (depends on 1) The system of claim 1, wherein the identity profile includes data representing past login attempts made through the computing device. ### Claim 5 (depends on 1) 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. ### Claim 6 (depends on 1) 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. ### Claim 7 (depends on 1) 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. ### Claim 8 (depends on 1) 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. ### Claim 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. ### Claim 10 (depends on 9) The method of claim 9, wherein each of the first and second challenge-response problems is an NP-complete problem. ### Claim 11 (depends on 10) The method of claim 10, wherein the NP-complete problem is a subset-sum problem. ### Claim 12 (depends on 9) 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. ### Claim 13 (depends on 9) 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. ### Claim 14 (depends on 9) 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. ### Claim 15 (depends on 9) The method of claim 9, wherein the second login attempt is processed further based on verifying a login credential received from the computing device. ### Claim 16 (depends on 9) 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. ### Claim 17 (depends on 9) 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. ### Claim 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. ### Claim 19 (depends on 18) 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. ### Claim 20 (depends on 18) 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.