Server using proof-of-work technique for hardening against denial of service attacks
A computerized device and a process protect against denial-of-service (DoS) attacks by using a memory-time hard problem that a client (e.g., IoT device or mobile app) solves as part of a request such as an initial registration process. The process may use parameters obtained from a public source of randomness. The problem is designed such that all memory allocated for the algorithm is used in a random manner, making it difficult for attackers to use FPGA/ASIC approaches. The client provides a proof-of-work (PoW) value to a server, which performs a more directed version of the calculation done by the client to confirm that the PoW value is correct. When confirmation is not obtained, the server can refrain from further processing of the client request, thwarting DoS attacks.
1. A method of operating a server device in connection with a human interaction service provided to client devices, comprising:
generating, by the server device, an array of hash values by iterating first cryptographic hashing operations, each operation generating a respective hash value of the array and taking as input a respective preceding hash value of the array generated by a respective preceding operation;
receiving, by the server device, a client request containing a proof-of-work value, the proof-of-work value reflecting a count of multiple searches of the same array of hash values at the client device until encountering a predetermined stop value in the array;
performing, by the server device, one search of the array beginning with the last-generated hash value, the one search including iterated second cryptographic hashing operations each taking as inputs (1) the proof-of-work value received from the client device, and (2) a respective intermediate value generated in a respective preceding operation;
comparing, by the server device, a last-generated intermediate value of the one search to the predetermined stop value to generate a verification result; and
when the verification result is positive, then performing further processing of the client request by the server device to provide the human interaction service to a client device that provided the client request, and when the verification result is negative, then refraining from the further processing of the client request;
wherein each of the second cryptographic hashing operations includes generating a respective index to be used to select a hash value of the array in a next succeeding operation, the index being generated by masking a predetermined number of bits of a respective hash value retrieved by the operation, the predetermined number corresponding to an address length for the array.
2. The method of claim 1 , wherein the intermediate value is generated for each second cryptographic hashing operation by masking a predetermined number of bits of a respective hash value retrieved by the operation.
3. The method of claim 2 , wherein the predetermined number is determined by an explicit work factor parameter provided to the server and the client devices.
4. The method of claim 1 , wherein the service is provided based on prior authentication of registered client devices authorized to use the service, and wherein the client request is a registration request seeking registration of a non-authenticated client to use the service.
5. The method of claim 1 , wherein the server is part of a cluster of closely coupled servers sharing environment data and access to records or databases, and wherein the servers employ auto-synchronization between virtual machines (VMs) in a cluster to reduce a load on the records or databases.
6. The method of claim 1 , wherein the first and second cryptographic hashing operations are respective first and second message digest operations, and wherein an initial one of the first message digest operations operates on a predetermined seed value to generate a first hash value of the array.
7. The method of claim 1 , wherein each of the searches is a predetermined number of the iterated second hashing operations, the predetermined number established by an explicit search parameter provided to the server and to the client devices.
8. The method of claim 1 , wherein the verification result is positive; and
wherein the performing further processing of the client request includes:
in response to the verification result that is positive, delivering the human interaction service from the server device to the client device through a network the human interaction service including at least one of a registration service, an authentication service, and a user-level service.
9. A method of operating a server device in connection with a human interaction service provided to client devices, comprising:
generating, by the server device, an array of hash values by iterating first cryptographic hashing operations, each operation generating a respective hash value of the array and taking as input a respective preceding hash value of the array generated by a respective preceding operation;
receiving, by the server device, a client request containing a proof-of-work value, the proof-of-work value reflecting a count of multiple searches of the same array of hash values at the client device until encountering a predetermined stop value in the array;
performing, by the server device, one search of the array beginning with the last-generated hash value, the one search including iterated second cryptographic hashing operations each taking as inputs (1) the proof-of-work value received from the client device, and (2) a respective intermediate value generated in a respective preceding operation;
comparing, by the server device, a last-generated intermediate value of the one search to the predetermined stop value to generate a verification result; and
when the verification result is positive, then performing further processing of the client request by the server device to provide the human interaction service to a client device that provided the client request, and when the verification result is negative, then refraining from the further processing of the client request;
wherein the first and second cryptographic hashing operations are respective first and second message digest operations, and wherein an initial one of the first message digest operations operates on a predetermined seed value to generate a first hash value of the array; and
wherein the second message digest operations takes as an additional input a server random value, the server random value being one of a stream of server random values generated uniquely for the server at respective server times identified by respective server time values.
10. The method of claim 9 , further including receiving the server time value with the client request and using the server time value to identify the server random value to be used in the second message digest operations.
11. The method of claim 9 , further including obtaining the server random value from a trusted public source of randomness.
12. A method of operating a client device in connection with a human interaction service provided by a server device, comprising:
generating, by the client device, an array of hash values by iterating first cryptographic hashing operations, each operation generating a respective hash value of the array and taking as input a respective hash value of the array generated by a respective preceding operation;
performing, by the client device, searches of the array until a stop condition is reached, each search beginning with a last-generated hash value of the array and including iterated second cryptographic hashing operations, each operation taking as inputs (1) a search count value and (2) a respective intermediate value generated in a respective preceding operation, the search count value being incremented to count the number of searches performed, the stop condition being that a last-generated intermediate value of a final search is equal to a predetermined stop value; and
in connection with a client request to the server device, sending, by the client device, the search count value of the final search as a proof-of-work value to the server device to indicate that the client device has performed the method and obtain the human interaction service from the server device;
wherein each of the second cryptographic hashing operations includes generating a respective index to be used to select a hash value of the array in a next succeeding operation, the index being generated by masking a predetermined number of bits of a respective hash value retrieved by the operation, the predetermined number corresponding to an address length for the array.
13. The method of claim 12 , wherein the intermediate value is generated for each second cryptographic hashing operation by masking a predetermined number of bits of a respective hash value retrieved by the operation.
14. The method of claim 12 , wherein the service is provided based on prior authentication of registered client devices authorized to use the service, and wherein the client request is a registration request seeking registration of a non-authenticated client to use the service.
15. The method of claim 12 , wherein the first and second cryptographic hashing operations are respective first and second message digest operations, and wherein an initial one of the first message digest operations operates on a predetermined seed value to generate a first hash value of the array.
16. The method of claim 12 , wherein each of the searches is a predetermined number of the iterated second hashing operations, the predetermined number established by an explicit search parameter provided to the server and to the client devices.
17. A method of operating a client device in connection with a human interaction service provided by a server device, comprising:
generating, by the client device, an array of hash values by iterating first cryptographic hashing operations, each operation generating a respective hash value of the array and taking as input a respective hash value of the array generated by a respective preceding operation;
performing, by the client device, searches of the array until a stop condition is reached, each search beginning with a last-generated hash value of the array and including iterated second cryptographic hashing operations, each operation taking as inputs (1) a search count value and (2) a respective intermediate value generated in a respective preceding operation, the search count value being incremented to count the number of searches performed, the stop condition being that a last-generated intermediate value of a final search is equal to a predetermined stop value; and
in connection with a client request to the server device, sending, by the client device, the search count value of the final search as a proof-of-work value to the server device to indicate that the client device has performed the method and obtain the human interaction service from the server device;
wherein the first and second cryptographic hashing operations are respective first and second message digest operations, and wherein an initial one of the first message digest operations operates on a predetermined seed value to generate a first hash value of the array; and
wherein the second message digest operations takes as an additional input a server random value, the server random value being one of a stream of server random values generated uniquely for the server at respective server times identified by respective server time values.
18. The method of claim 17 , further including obtaining the server time value and server random value from a trusted public source of randomness.
19. A method operating a client device and a server device in connection with a human interaction service provided by the server device, comprising:
A) at a client device:
generating an array of hash values by iterating first cryptographic hashing operations, each operation generating a respective hash value of the array and taking as input a respective hash value of the array generated by a respective preceding operation;
performing searches of the array until a stop condition is reached, each search beginning with a last-generated hash value of the array and including iterated second cryptographic hashing operations, each operation taking as inputs (1) a search count value and (2) a respective intermediate value generated in a respective preceding operation, the search count value being incremented to count the number of searches performed, the stop condition being that a last-generated intermediate value of a final search is equal to a predetermined stop value; and
in connection with a client request to a server device, sending the search count value of the final search as a proof-of-work value to the server device to obtain the human interaction service from the server device;
and
B) at the server device:
gene rating the array of hash values by iterating the first cryptographic hashing operations;
receiving the client request containing the proof-of-work value;
performing one search of the array beginning with the last-generated hash value of the array and including iterated third cryptographic hashing operations, each operation taking as inputs (1) the proof-of-work value received from the client device, and (2) a respective intermediate value generated in a respective preceding operation;
comparing a last-generated intermediate value of the one search to the predetermined stop value to generate a verification result; and
when the verification result is positive, then performing further processing of the client request to provide the human interaction service to the client device, and when the verification result is negative, then refraining from the further processing of the client request;
wherein each of the second cryptographic hashing operations includes generating a respective index to be used to select a hash value of the array in a next succeeding operation, the index being generated by masking a predetermined number of bits of a respective hash value retrieved by the operation, the predetermined number corresponding to an address length for the array.