Title of Invention	METHOD OF PROTECTING A SERVER FROM DENIAL OF SERVICE ATTACK
Abstract	The invention proposes a challenge-response mechanism to defend systems against Denial of service (DOS)/ Distributed Denial of Service (DDOS), especially resource consumption attack. The system which wants to defend itself from DOS/DDOS attack (server), before committing its resources to system connecting to it (client), throws challenge to client, verifies result generated by client and commits resources only if verification is successful. When client mounts attack against server throwing multiple requests, server will throw multiple challenges to client and client will get loaded in resolving challenges thrown by server. Thus server's resources are free for legitimate users connecting to it. This is based on the fact that the system, which wants to defend itself from resource consumption attack, shall be able to Control cost of challenge and verify response generated for challenge, investing minimal resources.

Title of Invention

METHOD OF PROTECTING A SERVER FROM DENIAL OF SERVICE ATTACK

Abstract

The invention proposes a challenge-response mechanism to defend systems against Denial of service (DOS)/ Distributed Denial of Service (DDOS), especially resource consumption attack. The system which wants to defend itself from DOS/DDOS attack (server), before committing its resources to system connecting to it (client), throws challenge to client, verifies result generated by client and commits resources only if verification is successful. When client mounts attack against server throwing multiple requests, server will throw multiple challenges to client and client will get loaded in resolving challenges thrown by server. Thus server's resources are free for legitimate users connecting to it. This is based on the fact that the system, which wants to defend itself from resource consumption attack, shall be able to Control cost of challenge and verify response generated for challenge, investing minimal resources.

Full Text	FIELD OF THE INVENTION This invention relates, in general, to security and communication in networks and in particular to a method for designing Denial of Service (DOS) and Distributed Denial of Service (DDOS) resilient systems. This invention is about a challenge-response mechanism for DOS/DDOS mitigation, which can be applied in design of protocols [such as security, networking, communication protocols, design of software system and applications (like e-commerce, m-commerce, B2B (Business to Business), B2C (Business to Consumer) applications, etc.] to make them DOS resilient. DESCRIPTION OF RELATED ART Denial of Service commonly known as DOS are the attacks, which aim at denying or degrading legitimate user's access to a service or network resource, or at bringing down servers offering such services. The system under threat may be a server connected to network, a proxy server or any such resource, which is vulnerable to DOS/DDOS attack. The present invention is directed towards a kind of DOS attack called resource consumption attack. The following paragraphs explain about the existing techniques for DDOS (Distributed Denial of Service) mitigation in brief. Listed below are patents related to DOS, granted by USPTO and are included herein by reference. Anti-clogging cookies: Anti-clogging cookies are generally used in IKE (Internet Key Exchange protocol) to protect responders from DDOS and the operations performed comprises of the following. 1. Initiator sends cookie (Cookie-I) to server. 2. Responder concatenates Cookie-I with the secret it owns, to generate Cookie-R using a hash function. Responder does not commit its resources to initiator at this point. 3. Responder sends Cookie-I, Cookie-R to client. 4. Initiator in next request sends Cookie-I and Cookie-R to responder along with other information. 5. Responder uses Cookie-I and repeats operation in step 2 to get a result and if the result matches with Cookie-R sent by initiator than responder its commits resources for initiator. More description of the above is available for reference at http://www.faqs.org/rfcs/rfc2401.html, http://www.faqs.org/rfcs/rfc2408.html, and http://www.faqs.org/rfcs/rfc2409.html Hash Cash, Client puzzles, etc. are other methods to defend servers from DDOS. Client puzzles: Client puzzles, which employ hash algorithms, follows the following steps, 1. Server generates a random value 'random, applies it to hash function to generate hash output randomjiash. 2. Server sends random value with last few bits masked and random_hash to client. 3. Client should find the bits, which are missing, in random value sent by server such that hash of random value along with identified bits results in randomhash value. Client uses brute force or linear search methods to identify missing bits. Some references pertaining to this activity is available at the following addresses, viz. http://www.rsasecuritv.com/rsalabs/node.asp?id=2050 and http://www.dataman.ro/phd/conti2004-3.pdf. DOS resistant authentication with client puzzles: DOS resistant authentication with client puzzles, while the client receives random value Ns and k (number of bits to be guessed) from server and the Client tries to find X, is governed by H(C,Ns,Nc,X) = O00..000(upto k bits) Y (rest of hash), in which X is solution to puzzle H represents hash algorithm C represents client identity Ns represents server's nonce Nc represents client's nonce K represents puzzle difficulty level 000...000 represents first k bits of hash, which mush be zero. Y represents rest of hash value, which can be anything. (http://research.microsoft.com/users/tuomaura/Publications/aura-nikander-leiwo--pr otocols00.pdf for more reference) Hash cash: Hash cash is another method to defend servers from DDOS, and involves the following main operations. Step 1: Server generates PUBLIC and PRIVATE values PUBLIC: n=pq, where p and q are primes and n is public. PRIVATE: q> (n) = (p-1) (q-1) Step 2 : Server generates challenge (CHAL is generated by server in interactive mode). C choose C in range (0,n-1) return (s.c.w). Step 3: Client finds solution for challenge. Client spends considerable CPU resources to find solution. T Compute y Return (s,c,w,y) Step 4: Verification of result in server V Compute z If x٨z = y (mod n) return w Else return 0. Even though the above methods are well established and widely acclaimed, they hold many demerits. One major drawback of 'Anti-clogging cookies' is that in this case all it takes for client to go ahead with attack is to store Cookie-I and matching Cookie-R from server (a light-weight session in initiator which is not costly for attacker). Since initiator stores Cookie-I and Cookie-R, it can send further payloads with certificates and fake signatures, which would make responder to verify certificate chains and signature leading to resource intensive operations, causing denial of service to legitimate users. The problems with client puzzles are listed below. 1. Complexity of solving puzzle increases exponentially with increase in number of bits to be identified. 2. Cost or complexity of solving puzzle cannot be adjusted precisely. i. If client tries to find answer for puzzle using brute force, it may so happen that client ends up not being able to find appropriate bits, which needs to be found, especially when number of bits to be guessed are more. ii. If linear search is used in finding solution (ie, client starts from 0x00000 and goes up to 2٨k-1 where k is number of bits to be found) and if server wants client to spend considerable time in finding solution to puzzle, it basically means reducing challenge to some fixed range. This can be exploited to attack server. 3. Solving this puzzle can be parallelized. There are problems existing with DOS resistant authentication with client puzzles also as listed below. 1. Complexity of solving puzzle increases exponentially with increase in number of bits to be identified. 2. In practical scenario, adopting brute force approach may take indefinitely long to find results when number of bits to be identified is more. 3. Solving puzzle can be parallelized. Similarly there are problems associated with hash cash also. The major problem is that the verification in server requires two exponentiation operations, which are very costly and this may be used to as weakness to attack server. For example, when a challenge is received by client, it does not perform exponentiation operation. Client throws some random output to server and server has to perform two exponentiation operations to verify the result and conclude that it is wrong. 1. Proposed challenge-response method In the light of the foregoing, the invention proposes a challenge-response mechanism to defend systems against DOS/DDOS. The system which wants to defend itself from DOS/DDOS attack (server), before committing its resources to system connecting to it (client), throws challenge to client, verifies result generated by client and commits resources only if verification is successful. When client mounts attack against server throwing multiple requests, server will throw multiple challenges to client and client will get loaded in resolving challenges thrown by server. Thus server's resources are free for legitimate users connecting to it. This is based on the fact that the system, which wants to defend itself from resource consumption attack, shall be able to • Control cost of challenge and • Verify response generated for challenge, investing minimal resources. SUMMARY OF THE INVENTION The primary object of the invention is, therefore, to provide a method for protecting a system from the kind of DOS attack called resource consumption attack, wherein the server throws challenge to client connecting to it, before committing its resources and verifies result generated by client and commits resources only if verification is successful. Another object of the invention is to provide a challenge response mechanism, in which when the client mounts attack against server throwing multiple requests, server will throw multiple challenges to client and client will get loaded in resolving challenges thrown by server thereby making the server resources free for legitimate users connecting to it. It is also an object of the invention to provide a system capable of defending itself from resource consumption attack, control cost of challenge and verify response generated for challenge, investing minimal resources. Accordingly, the invention provides a method for protecting servers from DOS attack with the avoidance of immediate commitment to client, the method comprising the steps of: a) checking the commitment of client in going ahead with protocol, by throwing a challenge to it, forcing client to spend considerable resources in solving the challenge, whose cost is controllable by server; b) verifying the results or responses sent by the client, spending relatively very small effort; c) committing the resources for the serving client only if the above said result or response is valid; and d) controlling the cost of the modular exponentiation operation in client These and other objects, features and advantages of the present invention will become more readily apparent from a reading of the following detailed description taken in conjunction with the drawings. BRIEF DESCRIPTION OF THE ACCOMPANYING DRAWINGS Figure 1 Describes message flow in challenge response method where client and server communicate without intermediate system. For detailed description please refer Deployment Scenarios (section 2) subsection l-A. Figure 2 Describes message flow in challenge response method where client and server communicate with intermediate system(s) between them. For detailed description please refer Deployment Scenarios (section 2) subsection l-B. Figure 3 Describes message flow in challenge response method with minimal change of application in server, where client and server communicate without intermediate system. For detailed description please refer Deployment (section 2) Scenarios subsection I l-A. Figure 4 Describes message flow in challenge response method with minimal change of application in server where client and server communicate with intermediate system(s) between them. For detailed description please refer Deployment Scenarios (section 2) subsection ll-B. Figure 5 Describes message flow in challenge response method with out any change in application on server and client, where client and server communicate without intermediate system. For detailed description please refer Deployment Scenarios (section 2) subsection lll-A. Figure 6 Describes message flow in challenge response method with out any change in application on server and client, where client and server communicate with intermediate system(s) between them. For detailed description please refer Deployment Scenarios (section 2) subsection I ll-B. Figure 7 is a High Level Block Diagram with Operations in the present invention. Brief description of operations: Above block diagram has two parts, namely, Server and Client. "Challenge Parameter Generator" in server generates challenge parameters and stores in data store. "Challenge Parameter Generator" in server is responsible for generation of challenge parameters with varied difficulty levels. Any operation initiated by client, which would involve considerable computing power and resources in server to serve, results in generation of trigger to "Challenge Generator". When Trigger (1) is received by "Challenge Generator" in server, generates challenge set and sends the same to client ((2) Send Challenge) through communication link. Client upon receiving challenge ((3) Receive challenge) resolves the challenge using "Challenge Resolver" and sends back the result to server ((4) Result to server) through communication link. Server upon receiving the result ((5) Receive result) verifies using "Challenge Verifier" module. If results are verified successfully, server commits resources to serve the client. DETAILED DESCRIPTION OF THE INVENTION The preferred embodiments of the present invention will now be explained with reference to the accompanying drawings. It should be understood that the disclosed embodiments are merely exemplary of the invention, which may be embodied in various forms. While specific steps, configurations and arrangements are discussed for illustrative purpose only. A person skilled in the art will recognize that other steps, configurations and arrangements can be used without departing from the spirit and scope of the present invention. Therefore the details disclosed herein are not to be interpreted as limiting but merely as the basis for the claims and as a basis for teaching one skilled in the art how to make or use the invention. The term challenge refers to set of parameters determined by server, using which client has to perform modular exponentiation operation. Cost of operation is defined as effort in terms of CPU cycles and memory that has to be spent by client to resolve the challenge from server. This invention proposes a method for protecting a system from the kind of DOS/DDOS attack called resource consumption attack, which can be mounted against system on network (victim), where in multiple requests from one or more machines are directed to victim simultaneously, resulting in increased load on system under attack, blocking its resources like CPU, memory, disk space thus making victim to deny service to legitimate users. The system may be a server connected to network, a proxy server or any thing, which is vulnerable to DOS/DDOS attack. For the purposes of this specification, any system that is vulnerable to resource consumption attack and needs to be shielded from attack is referred as server, and the system that is capable for mounting resource consumption attack over a targeted system is referred to as client. The term challenge refers to set of parameters determined by server, using which client has to perform modular exponentiation operation. Also the cost of operation is defined as effort in terms of CPU cycles and memory that has to be spent by client to resolve the challenge from server. In security protocols like SSL (Secure Socket Layer), TLS (Transport Layer Security), IKE etc during handshake process, server performs CPU intensive operations like certificate verification and signature verification. A malicious attacker can misuse this feature to attack server wherein server's resources are virtually locked thus denying services to legitimate users. As more and more computers, devices etc get connected to network with higher capabilities (processing power, memory) and increased bandwidth, resource consumption attacks based on vulnerabilities in protocols or software design are very important issues to be addressed. It is because these attacks have the potential to stop or terribly slow down business critical services indefinitely. According to the invention, the system that wants to shield itself from attack (server) • Do not commit resources immediately to client. • Checks the commitment of client in going ahead with protocol, by throwing a challenge to it. (Client should spend considerable resources in solving the challenge, whose cost is controllable by server) • Once correct results are identified by the client, it sends the results to server. • Server verifies result sent by client, spending relatively very small effort and if it result is valid, it commits its resources for serving the client. • Cost of the modular exponentiation operation in client is controllable by server. • Challenge is thrown by the system, which wants to defend itself from attack, or the system, which wants to defend itself from attack, shall designate other system to throw the challenge and validate it. I. Parameters pre-computed and stored in server The following parameters are pre-computed and stored in server as part of the operation of the invention. 1. Generate prime numbers of various sizes. 2. Calculate m such that, m is product of two or more primes. For example if p, q are primes, m = p.q. 3. Calculate φ (m) using Euler's Totient Function. For example, m=p.q where p and q are primes, φ (m) = (p-1)(q-1). (Euler's Totient Function denoted by lower case Phi are relatively prime to m) 4. Calculate exponent, e1 such that e1= x φ (m) + c, where x and c are natural numbers of arbitrary size (say 128 bits and above). 5. Generate e2 such that e2 mod( φ (m)) is not zero. Techniques for generation of e2 are described below in sub sections A,B and C. The value of e2 adds to complexity of challenge. Server shall use this parameter to control the cost of resolving challenge. 6. Letr = e2 mod(φ (m)). 7. Let margin be a small value (say varying from 1 to 30).Calculate d=cr-margin. 8. Generate random number a such that gcd(a,m)=1. 9. Server generates result = a٨ margin mod(m). The operations specified in steps 1-9 shall be performed in any order subject to the condition that all required parameters are available to perform the operations in a specified step. Either the steps from 1-9 shall be performed offline, and stored in server or the lightweight operations shall be performed when required (for example steps 4, 7-9 may be performed when required). In step (4) values of x and c are chosen to be as bigger as possible. Bigger the values of x and c, harder it is to factorize e1 and thus difficult to find (Value of m shall be refreshed periodically for additional security) Following methods explain various approaches to generate e2. A. Exponentiation e2 = rtexp Where n > 0,exp>0 and nexp mod ( B. Factorial method e2 = num!, where num is a natural number such that, e2 (mod (φ(m)) is not zero. C. Hash method 1. Generate a random value of arbitrary size (for example 10 bytes). 2. Identify size depending on cost of challenge. 3. Calculate output = hash(random)\|\|hash(h(1))\|\|hash(h(2)).... \|\|hash(h(r)). where hash is hashing algorithm, h(i)= hash(h(i-1)) for i ranging from 2 to r, h(1) = hash(random), \|\| indicates concatenation. Generate output using hash algorithm and concatenate the hash values generated. 4. e2= most significant 'size' bytes of 'output' where e2 (mod( q> (m)) is not zero, e2 shall be calculated using various methods (as specified in A-C above) offline and stored. All the pre-computations shall be performed using one or more systems and it may or may not be the server, which wants to defend itself from attack. Throwing challenge to client and verifying the response may be performed by server or by the system designated by server. II. Challenge generation in server If challenge is generated using exponentiation method (as above) for generation of e2, the set (a,e1,n,exp,d,m) with operation type exponentiation constitute the challenge. If challenge is generated using factorial method (as above) for generation of e2, the set (a,e1,num,d,m) with operation type factorial constitute the challenge. If challenge is generated using hash method (as above) for generation of e2, the set (a,e1,random,size,d,m) with operation type hash and name of hash algorithm to be used, constitute the challenge. If hash algorithm to be used is fixed in client and server it need not the exchanged. The set formed along with operation type and algorithm (if required) is sent to client. If operation type to be supported is fixed in client and server, operation type need not be exchanged. III. Challenge resolution in client If operation type is exponentiation, client resolves challenge as described below. If operation type is factorial, client resolves challenge as described below. If operation type is hash, client resolves challenge as described below. 1. out = hash(random)\|\|hash(h(1))....\|\|hash(h(r)) where size of out is greater than are equal to size. where hash is hashing algorithm, h(i)= hash(h(i-1)) for i ranging from 2 to r, h(1) = hash(random), \|\| indicates concatenation. Generate output using hash algorithm and concatenate the hash values generated. 2. Leading 'size' bytes from out constitute e2. 3. res = a{c{c2-l\mod(m)) Calculated result, res is sent to server. In order reduce number of bytes sent to server, client depending on agreement with server shall use one of methods explained above to send result. IV. Challenge response verification in server For all operation types discussed above if server and client have not agreed on reducing size of response from client (as explained in section V, below) and if result (generated in step (9) of section I) is equal to value of res received from client, challenge is considered to be resolved successfully. Other wise server concludes that client fails to resolve challenge. If client and server have agreed upon reducing size of response from client (as explained in section V, below), procedure explained in section V is applied to verify result from client. V. Reducing size of response from client In order to enable efficient utilization of network bandwidth, client shall send only the fingerprint of challenge to server, instead of sending complete value of result generated for challenge. Fingerprint will be generated by client and server using following methods: A. Hash mechanism 1. Client and server agree on hash algorithm. 2. The result generated for challenge is applied to hash function to generate hashed output. Here Client sends hashed output to server, and server generates the hashed output using result in step (9) of section I above and compares with the hashed output received from client. If the hashed output generated by server matches with the value sent bye client, server concludes that client has resolved challenge successfully. Alternately in the above-mentioned method, client and server shall agree to exchange only part of hashed output (for example say leading 10 bytes of hashed output) to further reduce number of bytes sent by client. B. Repeated XOR 1. Client and server agree on a block size. 2. If number of bytes in result generated for challenge is not multiple of block size agreed upon, the result value is appended with minimal number of zero bytes (0x00) at the end, so that result generated for challenge along with padding is multiple of block size. If block size is s, number of 0x00 bytes appended at end of result will range from 0 to (s-1). 3. The result generated for challenge is divided into block size agreed. Let res be the result generated for challenge with padding, then res = block(0)\|\| block(1)...\|\|block(n), \|\| indicates concatenation. 4. Perform XOR operation over blocks to generate output. Final output is calculated as out = block(0)٨block(1) ٨block(n). (٨ indicates XOR operation). Client sends output generated in step (4) to server, server follows "Repeated XOR" method explained above and generates output using result in step (9) of section I above and compares with value received from client. If the values match, server concludes that client has resolved challenge successfully. Since a(eXel-d) is congruent to amaig'" under modulo m, reducing a(tlV2"(/)and anm"7 by modulo m would yield same values. 3. Easy way to generate n in section (A) of (I) such that nexp mod( zero. To prove: If n is a prime and n is not perfect divisor of where rem is non zero positive value. Proof: This can be proven by contraction. According to (3) n is a factor of So, equation (2) is invalid and there is some non-zero remainder. If nex? «exp can not be equal to φp (m) because, it contradicts with properly that n is not perfect divisor of φ (m). Thus, n٨exp mod(^ (m)) is always non-zero when n is prime , exp>=0 and n is not perfect divisor of φ (m). VII. Complexity of breaking the method 1. Finding q> (m) cp (m) shall be found either by factorizing m or by deriving equation e1=xφ (m)+c from el Both of them require factorizing big numbers and in practice factorizing big numbers are extremely difficult. 2. Finding order of a If there is some simple algorithm to find order of 'a', costly exponentiation operation can circumvented in client side. But finding order of a number is very costly operation. The challenge-response mechanism explained above shall be turned on when attack is anticipated and in normal conditions it shall be turned off or the cost of challenge-response operation shall be kept as minimal as possible. 2. Deployment Scenarios Applying challenge-response mechanism described in above needs resolving issues related to • Overall operation considering all entities/systems involved • Enabling defense functionality in legacy systems without change in existing protocol/design • Design of protocol/system with defense mechanism • Deployment of challenge-response with effective bandwidth utilization Following sections in document describes about approaches that shall be applied in different scenarios. Intermediate system is a system, which resides in between client and server, performing operations delegated to it. There may be zero or more intermediate systems between client and server. Intermediate system does not invest its resources in resolving challenge and it has enough information to route challenge-response related messages. For example, if web browser is considered as client and HTTP server providing content is considered as server, HTTP proxy residing in between browser and HTTP server is considered as intermediate system. Challenge manager service resides with server or other system and is responsible for managing challenge-response operation carried out. Challenge resolver service in client resolves challenges directed to it, ensuring that system is not over-burdened in resolving challenges. It alerts user if the number of challenges arriving at it reaches or exceeds beyond threshold limit. Threshold limit may be determined by configuration parameters, resources available and other relevant parameters. Challenge resolver service has to be installed in client in order to resolve challenges arriving at it. For example in an environment where there can be larger number of mobile nodes, Challenge resolver service can be installed by service provider or trusted authority using OMA (Open Mobile Alliance) Device management protocol, without causing any burden to user. Sniffer is an application, which resides with server or other system and monitors the traffic of interest and initiates challenge-response operation with the help of "Challenge manager service" and takes appropriate corrective actions when deviation is identified. I. Applying challenge response method to protocol or design A. Client and Server without intermediate system The method explained below describes how challenge-response method shall co-exist with protocol/ design of client and server. In this method client communicates with server without any intermediate system. Server before committing its resources for client, throws a challenge (sequence 2 in Figure 1) to client, verifies response (sequence 3 in Figure 1) and upon successful verification server commits its resources to client. B. Client connecting to server through intermediate systems In some cases as shown in figure 2, client may not directly connect to server, but through intermediate system (for example proxy/gateway). When client connects to server through intermediate system (sequences 1, 2 in Fig. 2), server throws challenge to client (sequence 3 of Fig. 2). Challenge received by intermediate system (sequence 3 fig. 2) is routed to client (sequence 4 of fig. 2) and response from client (sequence 5 in fig. 2) is routed to server (sequence 6 of fig 2). Upon finding response to be valid, server commits resources to serve the client. For messages related to challenge-response operation, intermediate system acts as router and does not commit its resources in resolving challenge. II. Applying challenge response method with minimal change of application in server and services added in client and server The following methods describe about employing challenge-response mechanism with minimal change in application on server and there is no change in application residing on client. Server runs Challenge manager service, which throws challenges and verifies the responses. Client runs Challenge resolver service, which responds to challenges arriving at it. This method enables server to make client perform challenges in proportion to the extent to which client loads server. Since Challenge resolver service in client runs as separate service, it is may be vulnerable to attack which shall be avoided by client warning user if number and complexity of challenges arriving at it exceeds threshold limit. Threshold limit shall be configured by user or trusted authority depending on expected load on client, resources available in client and application relevant parameters. A. Client connecting to Server without intermediate systems In this method client communicates with server without any intermediate system. Server before committing its resources for client, requests Challenge manager service to perform challenge response operation (sequence 2 in Fig. 3). Challenge manager service in server throws challenge to client (sequence 3 in Fig. 3), receives response (sequence 4 in Fig. 3), verifies status of response and returns status of operation (sequence 5 in Fig. 3) to application in server. When challenge response operation is successful, server commits its resources to client to perform further operations (sequence 6 in Fig. 3). B. Client connecting to server through intermediate systems In some cases as shown in figure 4, client may not directly connect to server, but through intermediate system (for example proxy/gateway). In this method server, before committing its resources to serve client, requests Challenge manager service to perform challenge-response operation (sequence 3 in Fig. 4). Challenge manager service in server, throws challenge (sequence 4 of Fig. 4) to client. The intermediate system, which receives the challenge, forwards it to client (sequence 5 in Fig. 4). Challenge resolver service in client resolves the challenge and sends the response to intermediate system (sequence 6 of Fig. 4), and intermediate system forward the response to server (sequence 7 of Fig. 4). Challenge manager service in server verifies the response from client and passes the status of operation to application (sequence 8 in Fig. 4). If challenge is resolved successfully, server commits its resources to service client and responds to client's request (sequence 9, 10 in Fig 4). In case if there are multiple intermediate systems, they perform the operations delegated to them by protocol/design and when a challenge is received by an intermediate system, it shall act as channel to route the challenge and response to appropriate entities and do not invest its resources in resolving challenge. III. Applying challenge response method legacy systems with out change in existing application in server and client In some cases it is quite possible that applications in server and client cannot be changed. In such cases, challenge-response operation should be deployed without any change in application in server and client. The methods described below make use of sniffer to achieve the purpose. Sniffer keeps monitoring the traffic that arrives at Application in server. Upon detecting a request, which would cause server to perform resource intensive operation, sniffer initiates challenge-response operation with the help of Challenge manager service. If the response for challenge is not correct, it shall take appropriate corrective actions like generating system alerts to prompt administrators or configure firewall to drop packets originating from a specific mal-performing client. Since sniffer is independent of application on server, before sniffer detects and completes challenge-response operation, application might have invested its resources to serve client. In order to better utilize server resources, sniffer shall stand a step ahead of server (for example in firewall), where in it is be able to receive the packets before it reaches server, queue it for some time, perform challenge-response operation and when response for challenge is successful, shall forward the appropriate packet in queue to server. A. Client connecting to Server without intermediate systems Upon sniffer detecting a request, which would cause resource intensive operation in server (sequence 1 of Fig. 5), initiates Challenge manager service in server to perform challenge-response operation (sequence 2 of Fig. 5). Challenge manager service throws challenge to client (sequence 3 of Fig. 5), receives response from client (sequence 4 in Fig. 5), verifies if result is valid and returns status to sniffer (sequence 5 in Fig. 5). Sniffer upon finding results to be invalid shall take appropriate corrective actions like alerting system administrators or blocking traffic from client. Application in server after receiving request (seq. 1 in Fig. 5) performs appropriate operations to generate response (seq.6 in Fig. 5). B. Client connecting to server with intermediate systems For messages related to challenge-response operation, intermediate system acts as router and does not commit its resources in resolving challenge. In some cases as shown in figure 6, client may not directly connect to server, but through intermediate system (for example proxy/gateway). Request raised by client reaches server through intermediate system (sequence 1, 2 of Fig. 6). Sniffer upon detecting the request, which could cause resource intensive operation in server, initiates challenge-response operation (sequence 3 in Fig. 6). Challenge manager service in server, throws challenge to client and it passes through intermediate system as shown in sequences 4, 5 of Fig. 6. Challenge resolver service in client, resolves challenge and sends response to server which passes through intermediate system as shown in sequences 6, 7 in Fig. 6. Challenge manager service in server verifies the response from client and passes the status of operation to sniffer (sequence 8 in Fig. 4). Sniffer upon finding results to be invalid, shall take appropriate corrective actions like alerting system administrators or blocking traffic from client. After receiving request application in server (seq. 2 in Fig. 6), perform appropriate operations to generate response (seq. 7 in Fig. 5). In case if there are multiple intermediate systems, they perform the operations delegated to them by protocol/design and they shall act as channel to route the challenge and response to appropriate entities and do not invest their resources in resolving challenge. IV. Applying challenge-response mechanism with effective bandwidth utilization Since challenge-response messages would be exchanged very often before server performing resource intensive operation, it is very important that number of bytes exchanged is kept as minimal as possible. The challenge parameters sent by server contains few parameters that will not be refreshed quite often. Further there are other parameters like algorithm to be used for a particular operation, which will not change quite often. Effective exchange the parameters which do not change quite often will enable efficient network bandwidth utilization. The challenge parameter set is divided into two sub-sets. One set is called fixed challenge parameters and other set is called variable challenge parameters. Fixed challenge parameters are the ones that do not change very often and have considerable lifetime. Variable challenge parameters are the ones that change for almost for every challenge-response operation. Following sections explain about exchange of fixed and variable challenge parameters, mapping between them, validity duration of fixed parameters and how challenge-response operation is performed using fixed and variable set challenge parameters. A. Control parameters Control parameters are the parameters, which enable mapping between fixed challenge parameters and variable challenge parameters unambiguously along with validity parameter, which holds duration for which fixed challenge parameters are valid. System identifier is a control parameter, which uniquely identifies a system that wants to defend itself from attack. System identifier can be Fully Qualified Domain Name, IP address which does not change for longer duration. A system may have one or more system identifiers. Challenge identifier is a parameter, which uniquely identifies fixed challenge parameters thrown by a system. System identifier and challenge identifier uniquely identify a fixed challenge parameter set. Challenge identifier is a unique identifier and does not repeat. Validity is the time duration for which fixed challenge parameters are valid. This enable hosts to flush out out-dated fixed challenge parameters. B. Selection of fixed challenge parameters Following parameters are considered as fixed challenge parameters. These parameters are selected from sub-section I of "Proposed challenge-response method" (section 1). Following parameters shall constitute fixed challenge parameters i. Value m is a part of fixed challenge parameters. Please refer step 2 of section I in Proposed challenge-response method section, ii. If exponentiation method is used, values n, exp (section 1, sub-section I) along with operation type 'exponentiation' is a part of fixed challenge parameters, iii. If factorial method is used (section 1-1), parameters num along with operation type 'factorial' constitute part of fixed challenge parameters. iv. If hash method is used (section 1-1), parameters random, size, hash algorithm and operation type 'hash' constitute part of fixed challenge parameters. v. If reducing size of response from client (section 1-V) is employed with Hash mechanism (section 1-V-A) than a parameter to indicate usage of reducing size of response from client, identifier to indicate hash method, hash algorithm to be used and portion of hashed output to be exchanged (if only part of hashed output is exchanged) constitute part of fixed challenge parameters, vi. If reducing size of response from client (section 1-V) is employed with Repeated XOR mechanism (section 1-V-B) than a parameter to indicate usage of reducing size of response from client, identifier to indicate XOR method, block size constitute part of fixed challenge parameters. Thus server forms fixed cost parameters. Other challenge parameters in section 1-1, apart from above mentioned constitute variable challenge parameter set. C. Communication of fixed challenge parameters along with control parameters The set constituting fixed cost parameters along with control parameters are communicated to clients. The mode of transport is explained section H below. D. Management of fixed challenge parameters and control values in client Clients after having received fixed challenge parameters along with control parameters shall store them till the validity period. Clients shall also be configured to accept fixed challenge parameters along with control parameters only from specific systems identified by System identifier. This enables client to ignore fixed challenge parameters arriving from unknown systems, which may not be of interest to client. E. Challenge message exchange with variable challenge parameters, control parameters and challenge resolving process in client When server wants to perform challenge-response operation, shall send only variable portion of challenge (with some exceptions as explained above) along with system identifier (if required) and challenge identifier to client. Client upon receiving challenge with variable parameters and required control parameters shall map to fixed challenge parameter which is already received, using system identifier and challenge identifier to construct complete challenge parameter set. Once complete set of challenge parameters are identified in client, it shall perform modular exponentiation operation as explained in section 1 —III. Resolved challenge is sent to server for verification. F. Methods to get fixed challenge parameters when required It may so happen, that at the time when variable challenge parameters along with control parameters are received, client may not have appropriate mapping to fixed-challenge parameters. This scenario may arise when client fails to receive fixed challenge parameters from server. Following methods can be used to exchange fixed-challenge parameters at run time: i. Before getting variable challenge parameters, client sends the list of challenge-identifiers possessed by it to server. Server upon detecting appropriate fixed-challenge parameters not present in client shall send the fixed-challenge parameters along with control parameters and variable challenge parameters along with required control parameters to client. Client shall store the fixed challenge parameters in device (so that it need not request again). Once fixed and variable parameters are received client shall follow procedure explained above to resolve the challenge. Server may also send list of all fixed-challenge parameters which are supposed to be known to client along with the ones which are required for on-going challenge-response operation. Client shall store fixed-challenge response in it, so that it need not request for the same in later challenge-response operations. ii. If server can keep track of fixed-challenge parameters sent to client and client's identitv before oerformina challenae-resnonse oneration server shall send fixed-challenge parameters and control variables to client if required( if it is not communicated to client earlier). Server also sends variable challenge parameters along with required control parameters. Using fixed and variable challenge parameters along with required control parameters, client shall follow procedure explained in section 2-IV-E to resolve the challenge. Client shall store the fixed-challenge parameters and its control parameters for future reference. G. Control messages Control messages shall be sent to clients to control change in validity of fixed challenge parameters. Control messages shall be sent to i. Invalidate already sent fixed-challenge parameters along with control parameters If server or relevant authority want to invalidate already sent fixed-challenge parameters, shall send a control message containing operation type which identifies invalidation of particular fixed-challenge parameters along with control parameters, system identifier and challenge identifier of fixed-challenge parameters. Client upon receiving this control message shall delete appropriate fixed challenge parameters and its control parameters identified by system identifier and challenge identifier. ii. Extend the life-time of already sent fixed-challenge parameters along with control parameters If server or relevant authority wants to extend validity period of already transmitted fixed-challenge parameters along with challenge parameters, shall send control message containing operation type which identifies extension of life-time for fixed challenge parameter set, new time till which fixed-challenge parameters are valid, system identifier and challenge identifier of fixed challenge parameters on which change has to be applied. H. Communication of asynchronous messages Server or relevant authority would like to send messages like fixed-challenge parameters along with control parameters (section 2-IV-C) or control message (section 2-IV-G) from time to time. Such asynchronous messages shall be communicated to client over reliable and/or un-reliable transport medium. When asynchronous messages are communicated over reliable transport medium, server shall be able to keep track of its client who has received its asynchronous messages. For example, reliable transport medium can be i. Reliable push over WAP or HTTP. ii. Client shall run a service at a port and server upon knowing that it can reach client, shall send fixed-challenge parameters to it over reliable transport mediums like TCP, HTTP etc. When asynchronous messages are communicated over un-reliable transport layers like for example, IP broadcast, IP multicast, UDP or any connectionless transport means, in order for client to receive message, i. Server may keep sending the messages periodically or ii. Client shall use either of methods explained in section 2-IV-F to get fixed-challenge parameters. Alternatives/other embodiments of the invention 1. Reducing size of d above to save bandwidth: In step (7) of section 1-1, d = cVmargin. If cr is greater than φ(m), d and margin shall be calculated as described below. Let margin be a small value (say varying from 1 to 30). If cr mod { does not reveal (not close to p(m)), then d=(cr mod ( Reduced size of 'd' enables saving few bytes at the cost of performing a modular multiplication operation. Proof in section 1-VI, shall be logically extended for this change. Step (9) in section 1-1 holds good for verification operation in server. 2. When sign in some equations are changed in section I and/or III of section 1, would result in server performing result = a٨(-margin) mod(m) to calculate result for verification. a٨(-margin) mod (m) can be calculated using Extended Euclidean Algorithm. [The extended Euclidean algorithm is a version of the Euclidean algorithm; its input are two integers a and b and the algorithm computes their greatest common divisor (gcd) as well as integers x and y such that ax + by = gcd(a, b). The equation ax + by = gcd(a, b) is particularly useful when a and b are co-prime, x is then the multiplicative inverse of a modulo b] 3. Even when sign in some equations are changed in section I, III of section 1, would result in server performing result=aAmargin mod(m) to calculate result for verification. 4. In section 1-1, step (4) is e1= xφ (m)+c. If x is set to 1 and c = +/- margin where margin is small value, e1 becomes e1 = φ (m)+/-margin. If values of e2 and d are fixed as e2 = 1 and d = 0, main operation becomes a٨( φ (m)+/-margin) mod (m) in client and in server it becomes, a٨margin mod(m) or a٨(-margin) mod(m)[this can be calculated using extended Eucledian algorithm]. This would make server to refresh value of m almost for every transaction, since in the above equation margin is small value, ^(m) can be easily identified from el 5. In the methods described above, server shall delegate separate system to perform challenge response operation, i.e. Challenge manager service shall reside in some other machine and carry out the operation. When application in server decides to perform challenge-response operation, shall request client to contact system delegated by it to perform challenge-response operation. Once client performs challenge response operation, server commits its resources to serve client after verifying if client has successfully performed challenge-response operation with the system delegated by it. 6. In section 2-IV, fixed challenge parameters along with control parameters and control messages may be optionally signed in-order to assert authenticity of messages. 7. In section 2-IV, fixed challenge parameters along with control parameters when updated as a part of DNS resource record can reach clients easily. Advantage(s) of the Invention Challenge-response method proposed above defends system from resource consumption attacks has following advantages. 1. Cost of resolving the challenge shall be controlled by server: Complexity of modular exponentiation operation in client is directly dependent on parameters e1 and e2,.Since values of e1 and e2 are determined by server, it has full control over determining cost of operation in client. 2. Verification is very light weight operation in server, thus saving server's resources for critical operations: Despite cost incurred by client in resolving challenge, server has to perform a٨ margin mod(^ (m)) to verify challenge. Since margin is controlled by server and is very small value, complexity of modular exponentiation operation is always low. 3. Usage of pre-calculated values: All the operations specified in steps (1)-(9) in section 1-1 and operations specified in section 1-V can be pre-calculated. This enables server spending very minimal resources while performing challenge-response operation at run time. 4. Comparison of proposed method with methods described in prior art section: A. Comparison with Anti-clogging cookies Anti-clogging cookies do not make client to go for a resource intensive operation. The method proposed employs challenge-response mechanism in which cost of operation performed in client is controllable by server. B. Comparison with client puzzles Complexity of resolving challenge increases exponentially with increase in a bit. Further even if brute force or linear search mechanism is employed to resolve challenge, controlling cost of operation in client is difficult. In the proposed method, cost of operation in client can be controlled in better way by changing values of e1 and/or e2. C. Comparison with DOS resistant authentication with client puzzles Complexity of resolving challenge increases exponentially with increase in a bit. Cost of operations can be controlled in better way in proposed method by changing values of e1 and/or e2. If number of bits to be guessed is larger, client may end up with not being able to resolve challenge. In the method proposed results are guaranteed upon client performing modular exponentiation to resolve challenge. D. Comparison with hash cash In hash cash method, server performs two modular exponentiation operations in order to verify the result. In the method proposed, server always performs aAmargin mod (m) to verify challenge (step 9 above). Since margin is chosen by server and always it is kept low, verification is simple in server despite cost incurred by client in resolving challenge. The present invention shall ordinarily be used in design of protocols, software/hardware systems for defending system against DOS attack. Further the method shall be applied to protect software or hardware resources, which are connected to network from DOS attack. Apart from DOS/DDOS mitigation, this method can be applied in an environment, where a system wants other system to resolve challenge in-order to proceed with further operations. For example, password cracking has become a common problem and the rate at which password is cracked shall be slowed down by employing challenge-response mechanism i.e., a system (say server) before validating password sent by other system (say client) snaii request client to resoive cnaiienge DeTore going Tor passwora verification operation. When client tries to crack password by throwing multiple requests would get loaded in trying to resolve the challenge thus slowing down the rate at which password is cracked. In the description herein, numerous specific details are provided, such as examples of components and/or methods, to provide a thorough understanding of embodiments of the present invention. One skilled in the relevant art will recognize, however, that an embodiment of the invention can be practiced without one or more of the specific details, or with other apparatus, systems, assemblies, methods, components, materials, parts, and/or the like. In other instances, well-known structures, materials, or operations are not specifically shown or described in detail to avoid obscuring aspects of embodiments of the present invention. While it is apparent that the invention herein disclosed is well calculated to fulfill the objects above stated, it will be appreciated that numerous modifications and embodiments may be devised by those skilled in the art, and it is intended that the appended claims cover all such modifications and embodiments as fall within the true spirit and scope of the present invention. WE CLAIM 1. A method for protecting servers from DOS attack with the avoidance of immediate commitment of server's resources to client, the method comprising the steps of a) checking the commitment of client in going ahead with protocol, by throwing a challenge to it forcing to spend considerable resources in solving the challenge, whose cost is controllable by server; b) verifying the results or responses sent by the client, spending relatively very small effort; c) committing the resources for the serving client only if the above said result or response is valid; and d) controlling the cost of the modular exponentiation operation in client. 2. The method as claimed in claim 1 wherein, the challenge is thrown by the system, which wants to defend itself from attack, or another system that is designated by it throw the challenge and validate it. 3. The method as claimed in claim 1, wherein the challenge and response mechanism comprises Pre-computation of parameters, Challenge generation in server, Challenge resolution in client, Challenge response verification in server and Reducing size of response from client 4. The method as claimed in claim 2, wherein the intermediate system if employed does not commit any resources, but acts only as router to route traffic related to challenge-response messages. 5. The method as claimed in claim 3, wherein the challenge-response mechanism can be deployed with or without minor changes on application in server and without any change in application on client. 6. The method as claimed in claim 1, wherein distribution of challenge parameters to utilize bandwidth efficiently, comprises a method for exchange of fixed challenge parameters along with control parameters, method for exchange of variable challenge parameters along with control parameters, mapping between fixed and variable challenge parameters, management of challenge parameters in client, control messages and communication Channel. 7. A method for protecting servers from DOS attack with the avoidance of immediate commitment to client, substantially as herein above described and illustrated with reference to the accompanying drawings

Full Text

FIELD OF THE INVENTION
This invention relates, in general, to security and communication in networks and in particular to a method for designing Denial of Service (DOS) and Distributed Denial of Service (DDOS) resilient systems. This invention is about a challenge-response mechanism for DOS/DDOS mitigation, which can be applied in design of protocols [such as security, networking, communication protocols, design of software system and applications (like e-commerce, m-commerce, B2B (Business to Business), B2C (Business to Consumer) applications, etc.] to make them DOS resilient.
DESCRIPTION OF RELATED ART
Denial of Service commonly known as DOS are the attacks, which aim at denying or degrading legitimate user's access to a service or network resource, or at bringing down servers offering such services. The system under threat may be a server connected to network, a proxy server or any such resource, which is vulnerable to DOS/DDOS attack. The present invention is directed towards a kind of DOS attack called resource consumption attack. The following paragraphs explain about the existing techniques for DDOS (Distributed Denial of Service) mitigation in brief.
Listed below are patents related to DOS, granted by USPTO and are included herein by reference.

Anti-clogging cookies:
Anti-clogging cookies are generally used in IKE (Internet Key Exchange
protocol) to protect responders from DDOS and the operations performed comprises of the following.
1. Initiator sends cookie (Cookie-I) to server.
2. Responder concatenates Cookie-I with the secret it owns, to generate Cookie-R using a hash function. Responder does not commit its resources to initiator at this point.
3. Responder sends Cookie-I, Cookie-R to client.
4. Initiator in next request sends Cookie-I and Cookie-R to responder along with other information.
5. Responder uses Cookie-I and repeats operation in step 2 to get a result and if the result matches with Cookie-R sent by initiator than responder its commits resources for initiator.
More description of the above is available for reference at http://www.faqs.org/rfcs/rfc2401.html, http://www.faqs.org/rfcs/rfc2408.html, and http://www.faqs.org/rfcs/rfc2409.html
Hash Cash, Client puzzles, etc. are other methods to defend servers from DDOS.
Client puzzles:
Client puzzles, which employ hash algorithms, follows the following steps,
1. Server generates a random value 'random*, applies it to hash function to generate hash output randomjiash.

2. Server sends random value with last few bits masked and random_hash to client.
3. Client should find the bits, which are missing, in random value sent by server such that hash of random value along with identified bits results in randomhash value. Client uses brute force or linear search methods to identify missing bits.
Some references pertaining to this activity is available at the following addresses,
viz. http://www.rsasecuritv.com/rsalabs/node.asp?id=2050 and
http://www.dataman.ro/phd/conti2004-3.pdf.
DOS resistant authentication with client puzzles:
DOS resistant authentication with client puzzles, while the client receives random
value Ns and k (number of bits to be guessed) from server and the Client tries to
find X, is governed by H(C,Ns,Nc,X) = O00..000(upto k bits) Y (rest of hash), in
which
X is solution to puzzle
H represents hash algorithm
C represents client identity
Ns represents server's nonce
Nc represents client's nonce
K represents puzzle difficulty level
000...000 represents first k bits of hash, which mush be zero.

Y represents rest of hash value, which can be anything. (http://research.microsoft.com/users/tuomaura/Publications/aura-nikander-leiwo--pr otocols00.pdf for more reference)
Hash cash:
Hash cash is another method to defend servers from DDOS, and involves the
following main operations.
Step 1: Server generates PUBLIC and PRIVATE values
PUBLIC: n=pq, where p and q are primes and n is public. PRIVATE: q> (n) = (p-1) (q-1)
Step 2 : Server generates challenge
(CHAL is generated by server in interactive mode). C choose C in range (0,n-1)
return (s.c.w).
Step 3: Client finds solution for challenge. Client spends considerable CPU resources to find solution.
T Compute y Return (s,c,w,y)

Step 4: Verification of result in server
V Compute z If x٨z = y (mod n) return w Else return 0.
Even though the above methods are well established and widely acclaimed, they hold many demerits. One major drawback of 'Anti-clogging cookies' is that in this case all it takes for client to go ahead with attack is to store Cookie-I and matching Cookie-R from server (a light-weight session in initiator which is not costly for attacker). Since initiator stores Cookie-I and Cookie-R, it can send further payloads with certificates and fake signatures, which would make responder to verify certificate chains and signature leading to resource intensive operations, causing denial of service to legitimate users.
The problems with client puzzles are listed below.
1. Complexity of solving puzzle increases exponentially with increase in number of bits to be identified.
2. Cost or complexity of solving puzzle cannot be adjusted precisely.
i. If client tries to find answer for puzzle using brute force, it may so happen that client ends up not being able to find appropriate bits, which needs to be found, especially when number of bits to be guessed are more.

ii. If linear search is used in finding solution (ie, client starts from 0x00000 and goes up to 2٨k-1 where k is number of bits to be found) and if server wants client to spend considerable time in finding solution to puzzle, it basically means reducing challenge to some fixed range. This can be exploited to attack server. 3. Solving this puzzle can be parallelized.
There are problems existing with DOS resistant authentication with client puzzles also as listed below.
1. Complexity of solving puzzle increases exponentially with increase in number of bits to be identified.
2. In practical scenario, adopting brute force approach may take indefinitely long to find results when number of bits to be identified is more.
3. Solving puzzle can be parallelized.
Similarly there are problems associated with hash cash also. The major problem is that the verification in server requires two exponentiation operations, which are very costly and this may be used to as weakness to attack server. For example, when a challenge is received by client, it does not perform exponentiation operation. Client throws some random output to server and server has to perform two exponentiation operations to verify the result and conclude that it is wrong.
1. Proposed challenge-response method

In the light of the foregoing, the invention proposes a challenge-response mechanism to defend systems against DOS/DDOS. The system which wants to defend itself from DOS/DDOS attack (server), before committing its resources to system connecting to it (client), throws challenge to client, verifies result generated by client and commits resources only if verification is successful. When client mounts attack against server throwing multiple requests, server will throw multiple challenges to client and client will get loaded in resolving challenges thrown by server. Thus server's resources are free for legitimate users connecting to it.
This is based on the fact that the system, which wants to defend itself from resource consumption attack, shall be able to
• Control cost of challenge and
• Verify response generated for challenge, investing minimal resources.
SUMMARY OF THE INVENTION
The primary object of the invention is, therefore, to provide a method for protecting a system from the kind of DOS attack called resource consumption attack, wherein the server throws challenge to client connecting to it, before committing its resources and verifies result generated by client and commits resources only if verification is successful.
Another object of the invention is to provide a challenge response mechanism, in which when the client mounts attack against server throwing multiple requests,

server will throw multiple challenges to client and client will get loaded in resolving challenges thrown by server thereby making the server resources free for legitimate users connecting to it.
It is also an object of the invention to provide a system capable of defending itself from resource consumption attack, control cost of challenge and verify response generated for challenge, investing minimal resources.
Accordingly, the invention provides a method for protecting servers from DOS attack with the avoidance of immediate commitment to client, the method comprising the steps of:
a) checking the commitment of client in going ahead with protocol, by throwing a challenge to it, forcing client to spend considerable resources in solving the challenge, whose cost is controllable by server;
b) verifying the results or responses sent by the client, spending relatively very small effort;
c) committing the resources for the serving client only if the above said result or response is valid; and
d) controlling the cost of the modular exponentiation operation in client

These and other objects, features and advantages of the present invention will become more readily apparent from a reading of the following detailed description taken in conjunction with the drawings.
BRIEF DESCRIPTION OF THE ACCOMPANYING DRAWINGS
Figure 1
Describes message flow in challenge response method where client and server communicate without intermediate system. For detailed description please refer Deployment Scenarios (section 2) subsection l-A.
Figure 2
Describes message flow in challenge response method where client and server communicate with intermediate system(s) between them. For detailed description please refer Deployment Scenarios (section 2) subsection l-B.
Figure 3
Describes message flow in challenge response method with minimal change of application in server, where client and server communicate without intermediate system. For detailed description please refer Deployment (section 2) Scenarios subsection I l-A. Figure 4
Describes message flow in challenge response method with minimal change of application in server where client and server communicate with intermediate

system(s) between them. For detailed description please refer Deployment Scenarios (section 2) subsection ll-B. Figure 5
Describes message flow in challenge response method with out any change in application on server and client, where client and server communicate without intermediate system. For detailed description please refer Deployment Scenarios (section 2) subsection lll-A. Figure 6
Describes message flow in challenge response method with out any change in application on server and client, where client and server communicate with intermediate system(s) between them. For detailed description please refer Deployment Scenarios (section 2) subsection I ll-B.

Figure 7 is a High Level Block Diagram with Operations in the present invention.
Brief description of operations:
Above block diagram has two parts, namely, Server and Client.
"Challenge Parameter Generator" in server generates challenge parameters and
stores in data store. "Challenge Parameter Generator" in server is responsible for
generation of challenge parameters with varied difficulty levels.
Any operation initiated by client, which would involve considerable computing
power and resources in server to serve, results in generation of trigger to
"Challenge Generator".
When Trigger (1) is received by "Challenge Generator" in server, generates
challenge set and sends the same to client ((2) Send Challenge) through
communication link.
Client upon receiving challenge ((3) Receive challenge) resolves the challenge
using "Challenge Resolver" and sends back the result to server ((4) Result to
server) through communication link.
Server upon receiving the result ((5) Receive result) verifies using "Challenge
Verifier" module.
If results are verified successfully, server commits resources to serve the client.
DETAILED DESCRIPTION OF THE INVENTION
The preferred embodiments of the present invention will now be explained with reference to the accompanying drawings. It should be understood that the disclosed embodiments are merely exemplary of the invention, which may be

embodied in various forms. While specific steps, configurations and arrangements are discussed for illustrative purpose only. A person skilled in the art will recognize that other steps, configurations and arrangements can be used without departing from the spirit and scope of the present invention. Therefore the details disclosed herein are not to be interpreted as limiting but merely as the basis for the claims and as a basis for teaching one skilled in the art how to make or use the invention.
The term challenge refers to set of parameters determined by server, using which client has to perform modular exponentiation operation.
Cost of operation is defined as effort in terms of CPU cycles and memory that has to be spent by client to resolve the challenge from server.
This invention proposes a method for protecting a system from the kind of DOS/DDOS attack called resource consumption attack, which can be mounted against system on network (victim), where in multiple requests from one or more machines are directed to victim simultaneously, resulting in increased load on system under attack, blocking its resources like CPU, memory, disk space thus making victim to deny service to legitimate users. The system may be a server connected to network, a proxy server or any thing, which is vulnerable to DOS/DDOS attack.
For the purposes of this specification, any system that is vulnerable to resource consumption attack and needs to be shielded from attack is referred as server, and

the system that is capable for mounting resource consumption attack over a targeted system is referred to as client. The term challenge refers to set of parameters determined by server, using which client has to perform modular exponentiation operation. Also the cost of operation is defined as effort in terms of CPU cycles and memory that has to be spent by client to resolve the challenge from server.
In security protocols like SSL (Secure Socket Layer), TLS (Transport Layer Security), IKE etc during handshake process, server performs CPU intensive operations like certificate verification and signature verification. A malicious attacker can misuse this feature to attack server wherein server's resources are virtually locked thus denying services to legitimate users. As more and more computers, devices etc get connected to network with higher capabilities (processing power, memory) and increased bandwidth, resource consumption attacks based on vulnerabilities in protocols or software design are very important issues to be addressed. It is because these attacks have the potential to stop or terribly slow down business critical services indefinitely.
According to the invention, the system that wants to shield itself from attack (server)
• Do not commit resources immediately to client.
• Checks the commitment of client in going ahead with protocol, by throwing a challenge to it. (Client should spend considerable resources in solving the challenge, whose cost is controllable by server)

• Once correct results are identified by the client, it sends the results to server.
• Server verifies result sent by client, spending relatively very small effort and if it result is valid, it commits its resources for serving the client.
• Cost of the modular exponentiation operation in client is controllable by server.
• Challenge is thrown by the system, which wants to defend itself from attack, or the system, which wants to defend itself from attack, shall designate other system to throw the challenge and validate it.
I. Parameters pre-computed and stored in server
The following parameters are pre-computed and stored in server as part of the
operation of the invention.
1. Generate prime numbers of various sizes.
2. Calculate m such that, m is product of two or more primes. For example if p, q are primes, m = p.q.
3. Calculate φ (m) using Euler's Totient Function. For example, m=p.q
where p and q are primes, φ (m) = (p-1)(q-1).
(Euler's Totient Function denoted by lower case Phi are relatively prime to m)
4. Calculate exponent, e1 such that e1= x* φ (m) + c, where x and c are
natural numbers of arbitrary size (say 128 bits and above).
5. Generate e2 such that e2 mod( φ (m)) is not zero. Techniques for
generation of e2 are described below in sub sections A,B and C. The

value of e2 adds to complexity of challenge. Server shall use this parameter to control the cost of resolving challenge.
6. Letr = e2 mod(φ (m)).
7. Let margin be a small value (say varying from 1 to 30).Calculate d=c*r-margin.
8. Generate random number a such that gcd(a,m)=1.
9. Server generates result = a٨ margin mod(m).
The operations specified in steps 1-9 shall be performed in any order subject to the condition that all required parameters are available to perform the operations in a specified step. Either the steps from 1-9 shall be performed offline, and stored in server or the lightweight operations shall be performed when required (for example steps 4, 7-9 may be performed when required).
In step (4) values of x and c are chosen to be as bigger as possible. Bigger the values of x and c, harder it is to factorize e1 and thus difficult to find

(Value of m shall be refreshed periodically for additional security) Following methods explain various approaches to generate e2.
A. Exponentiation
e2 = rtexp
Where n > 0,exp>0 and nexp mod (

B. Factorial method

e2 = num!, where num is a natural number such that, e2 (mod (φ(m)) is not
zero.
C. Hash method
1. Generate a random value of arbitrary size (for example 10 bytes).
2. Identify size depending on cost of challenge.
3. Calculate output = hash(random)||hash(h(1))||hash(h(2)).... ||hash(h(r)). where hash is hashing algorithm,
h(i)= hash(h(i-1)) for i ranging from 2 to r, h(1) = hash(random), || indicates concatenation.
Generate output using hash algorithm and concatenate the hash values generated.
4. e2= most significant 'size' bytes of 'output'
where e2 (mod( q> (m)) is not zero,
e2 shall be calculated using various methods (as specified in A-C above) offline and stored.
All the pre-computations shall be performed using one or more systems and it may or may not be the server, which wants to defend itself from attack. Throwing challenge to client and verifying the response may be performed by server or by the system designated by server.
II. Challenge generation in server

If challenge is generated using exponentiation method (as above) for generation of e2, the set (a,e1,n,exp,d,m) with operation type exponentiation constitute the challenge.
If challenge is generated using factorial method (as above) for generation of e2, the set (a,e1,num,d,m) with operation type factorial constitute the challenge.
If challenge is generated using hash method (as above) for generation of e2, the set (a,e1,random,size,d,m) with operation type hash and name of hash algorithm to be used, constitute the challenge. If hash algorithm to be used is fixed in client and server it need not the exchanged.
The set formed along with operation type and algorithm (if required) is sent to client. If operation type to be supported is fixed in client and server, operation type need not be exchanged.
III. Challenge resolution in client
If operation type is exponentiation, client resolves challenge as described below.

If operation type is factorial, client resolves challenge as described below.

If operation type is hash, client resolves challenge as described below.
1. out = hash(random)||hash(h(1))....||hash(h(r)) where size of out is
greater than are equal to size.
where hash is hashing algorithm,
h(i)= hash(h(i-1)) for i ranging from 2 to r, h(1) = hash(random), || indicates concatenation. Generate output using hash algorithm and concatenate the hash values generated.
2. Leading 'size' bytes from out constitute e2.
3. res = a{c{*c2-l\mod(m))
Calculated result, res is sent to server. In order reduce number of bytes sent to server, client depending on agreement with server shall use one of methods explained above to send result.
IV. Challenge response verification in server
For all operation types discussed above if server and client have not agreed on reducing size of response from client (as explained in section V, below) and if result (generated in step (9) of section I) is equal to value of res received from client, challenge is considered to be resolved successfully. Other wise server concludes that client fails to resolve challenge.

If client and server have agreed upon reducing size of response from client (as explained in section V, below), procedure explained in section V is applied to verify result from client.
V. Reducing size of response from client
In order to enable efficient utilization of network bandwidth, client shall send only the fingerprint of challenge to server, instead of sending complete value of result generated for challenge.
Fingerprint will be generated by client and server using following methods:
A. Hash mechanism
1. Client and server agree on hash algorithm.
2. The result generated for challenge is applied to hash function to generate hashed output.
Here Client sends hashed output to server, and server generates the hashed output using result in step (9) of section I above and compares with the hashed output received from client. If the hashed output generated by server matches with the value sent bye client, server concludes that client has resolved challenge successfully.

Alternately in the above-mentioned method, client and server shall agree to exchange only part of hashed output (for example say leading 10 bytes of hashed output) to further reduce number of bytes sent by client.
B. Repeated XOR
1. Client and server agree on a block size.
2. If number of bytes in result generated for challenge is not multiple of block size agreed upon, the result value is appended with minimal number of zero bytes (0x00) at the end, so that result generated for challenge along with padding is multiple of block size. If block size is s, number of 0x00 bytes appended at end of result will range from 0 to (s-1).
3. The result generated for challenge is divided into block size agreed. Let res be the result generated for challenge with padding, then
res = block(0)|| block(1)...||block(n), || indicates concatenation.
4. Perform XOR operation over blocks to generate output. Final
output is calculated as out = block(0)٨block(1) ٨block(n). (٨
indicates XOR operation).
Client sends output generated in step (4) to server, server follows "Repeated XOR" method explained above and generates output using result in step (9) of section I above and compares with value received from client. If the values match, server concludes that client has resolved challenge successfully.

Since a(eX*el-d) is congruent to amaig'" under modulo m, reducing a(tlV2"(/)and anm*"7 by modulo m would yield same values.
3. Easy way to generate n in section (A) of (I) such that nexp mod(

zero. To prove:
If n is a prime and n is not perfect divisor of

where rem is non zero positive value.
Proof:

This can be proven by contraction.

According to (3) n is a factor of

So, equation (2) is invalid and there is some non-zero remainder. If nex? «exp can not be equal to φp (m) because, it contradicts with properly that n is not perfect divisor of φ (m).
Thus, n٨exp mod(^ (m)) is always non-zero when n is prime , exp>=0 and n is not perfect divisor of φ (m).
VII. Complexity of breaking the method
1. Finding q> (m)

cp (m) shall be found either by factorizing m or by deriving equation e1=x*φ (m)+c
from el Both of them require factorizing big numbers and in practice factorizing big numbers are extremely difficult.
2. Finding order of a
If there is some simple algorithm to find order of 'a', costly exponentiation operation can circumvented in client side. But finding order of a number is very costly operation.
The challenge-response mechanism explained above shall be turned on when attack is anticipated and in normal conditions it shall be turned off or the cost of challenge-response operation shall be kept as minimal as possible.
2. Deployment Scenarios
Applying challenge-response mechanism described in above needs resolving issues related to
• Overall operation considering all entities/systems involved
• Enabling defense functionality in legacy systems without change in existing protocol/design
• Design of protocol/system with defense mechanism
• Deployment of challenge-response with effective bandwidth utilization
Following sections in document describes about approaches that shall be applied in

different scenarios.
Intermediate system is a system, which resides in between client and server, performing operations delegated to it. There may be zero or more intermediate systems between client and server. Intermediate system does not invest its resources in resolving challenge and it has enough information to route challenge-response related messages.
For example, if web browser is considered as client and HTTP server providing content is considered as server, HTTP proxy residing in between browser and HTTP server is considered as intermediate system.
Challenge manager service resides with server or other system and is responsible for managing challenge-response operation carried out.
Challenge resolver service in client resolves challenges directed to it, ensuring that system is not over-burdened in resolving challenges. It alerts user if the number of challenges arriving at it reaches or exceeds beyond threshold limit. Threshold limit may be determined by configuration parameters, resources available and other relevant parameters. Challenge resolver service has to be installed in client in order to resolve challenges arriving at it. For example in an environment where there can be larger number of mobile nodes, Challenge resolver service can be installed by service provider or trusted authority using OMA (Open Mobile Alliance) Device management protocol, without causing any burden to user.

Sniffer is an application, which resides with server or other system and monitors the traffic of interest and initiates challenge-response operation with the help of "Challenge manager service" and takes appropriate corrective actions when deviation is identified.
I. Applying challenge response method to protocol or design
A. Client and Server without intermediate system
The method explained below describes how challenge-response method shall co-exist with protocol/ design of client and server. In this method client communicates with server without any intermediate system. Server before committing its resources for client, throws a challenge (sequence 2 in Figure 1) to client, verifies response (sequence 3 in Figure 1) and upon successful
*
verification server commits its resources to client.
B. Client connecting to server through intermediate systems
In some cases as shown in figure 2, client may not directly connect to server, but through intermediate system (for example proxy/gateway). When client connects to server through intermediate system (sequences 1, 2 in Fig. 2), server throws challenge to client (sequence 3 of Fig. 2). Challenge received by intermediate system (sequence 3 fig. 2) is routed to client (sequence 4 of fig. 2) and response from client (sequence 5 in fig. 2) is routed to server (sequence 6 of

fig 2). Upon finding response to be valid, server commits resources to serve the client.
For messages related to challenge-response operation, intermediate system acts as router and does not commit its resources in resolving challenge.
II. Applying challenge response method with minimal change of application in server and services added in client and server
The following methods describe about employing challenge-response mechanism with minimal change in application on server and there is no change in application residing on client. Server runs Challenge manager service, which throws challenges and verifies the responses. Client runs Challenge resolver service, which responds to challenges arriving at it. This method enables server to make client perform challenges in proportion to the extent to which client loads server. Since Challenge resolver service in client runs as separate service, it is may be vulnerable to attack which shall be avoided by client warning user if number and complexity of challenges arriving at it exceeds threshold limit. Threshold limit shall be configured by user or trusted authority depending on expected load on client, resources available in client and application relevant parameters.
A. Client connecting to Server without intermediate systems

In this method client communicates with server without any intermediate system. Server before committing its resources for client, requests Challenge manager service to perform challenge response operation (sequence 2 in Fig. 3). Challenge manager service in server throws challenge to client (sequence 3 in Fig. 3), receives response (sequence 4 in Fig. 3), verifies status of response and returns status of operation (sequence 5 in Fig. 3) to application in server. When challenge response operation is successful, server commits its resources to client to perform further operations (sequence 6 in Fig. 3).
B. Client connecting to server through intermediate systems
In some cases as shown in figure 4, client may not directly connect to server, but through intermediate system (for example proxy/gateway). In this method server, before committing its resources to serve client, requests Challenge manager service to perform challenge-response operation (sequence 3 in Fig. 4). Challenge manager service in server, throws challenge (sequence 4 of Fig. 4) to client. The intermediate system, which receives the challenge, forwards it to client (sequence 5 in Fig. 4).
Challenge resolver service in client resolves the challenge and sends the response to intermediate system (sequence 6 of Fig. 4), and intermediate system forward the response to server (sequence 7 of Fig. 4). Challenge manager service in server verifies the response from client and passes the status of operation to application (sequence 8 in Fig. 4). If challenge is resolved successfully, server commits its

resources to service client and responds to client's request (sequence 9, 10 in Fig 4). In case if there are multiple intermediate systems, they perform the operations delegated to them by protocol/design and when a challenge is received by an intermediate system, it shall act as channel to route the challenge and response to appropriate entities and do not invest its resources in resolving challenge.
III. Applying challenge response method legacy systems with out change in existing application in server and client
In some cases it is quite possible that applications in server and client cannot be changed. In such cases, challenge-response operation should be deployed without any change in application in server and client. The methods described below make use of sniffer to achieve the purpose. Sniffer keeps monitoring the traffic that arrives at Application in server. Upon detecting a request, which would cause server to perform resource intensive operation, sniffer initiates challenge-response operation with the help of Challenge manager service. If the response for challenge is not correct, it shall take appropriate corrective actions like generating system alerts to prompt administrators or configure firewall to drop packets originating from a specific mal-performing client.
Since sniffer is independent of application on server, before sniffer detects and completes challenge-response operation, application might have invested its resources to serve client. In order to better utilize server resources, sniffer shall stand a step ahead of server (for example in firewall), where in it is be able to

receive the packets before it reaches server, queue it for some time, perform challenge-response operation and when response for challenge is successful, shall forward the appropriate packet in queue to server.
A. Client connecting to Server without intermediate systems
Upon sniffer detecting a request, which would cause resource intensive operation in server (sequence 1 of Fig. 5), initiates Challenge manager service in server to perform challenge-response operation (sequence 2 of Fig. 5). Challenge manager service throws challenge to client (sequence 3 of Fig. 5), receives response from client (sequence 4 in Fig. 5), verifies if result is valid and returns status to sniffer (sequence 5 in Fig. 5). Sniffer upon finding results to be invalid shall take appropriate corrective actions like alerting system administrators or blocking traffic from client. Application in server after receiving request (seq. 1 in Fig. 5) performs appropriate operations to generate response (seq.6 in Fig. 5).
B. Client connecting to server with intermediate systems
For messages related to challenge-response operation, intermediate system acts as router and does not commit its resources in resolving challenge. In some cases as shown in figure 6, client may not directly connect to server, but through intermediate system (for example proxy/gateway). Request raised by client reaches server through intermediate system (sequence 1, 2 of Fig. 6). Sniffer upon detecting the request, which could cause resource intensive operation in server, initiates

challenge-response operation (sequence 3 in Fig. 6). Challenge manager service in server, throws challenge to client and it passes through intermediate system as shown in sequences 4, 5 of Fig. 6. Challenge resolver service in client, resolves challenge and sends response to server which passes through intermediate system as shown in sequences 6, 7 in Fig. 6.
Challenge manager service in server verifies the response from client and passes the status of operation to sniffer (sequence 8 in Fig. 4). Sniffer upon finding results to be invalid, shall take appropriate corrective actions like alerting system administrators or blocking traffic from client. After receiving request application in server (seq. 2 in Fig. 6), perform appropriate operations to generate response (seq. 7 in Fig. 5).
In case if there are multiple intermediate systems, they perform the operations delegated to them by protocol/design and they shall act as channel to route the challenge and response to appropriate entities and do not invest their resources in resolving challenge.
IV. Applying challenge-response mechanism with effective bandwidth utilization
Since challenge-response messages would be exchanged very often before server performing resource intensive operation, it is very important that number of bytes exchanged is kept as minimal as possible. The challenge parameters sent by

server contains few parameters that will not be refreshed quite often. Further there are other parameters like algorithm to be used for a particular operation, which will not change quite often. Effective exchange the parameters which do not change quite often will enable efficient network bandwidth utilization.
The challenge parameter set is divided into two sub-sets. One set is called fixed challenge parameters and other set is called variable challenge parameters. Fixed challenge parameters are the ones that do not change very often and have considerable lifetime. Variable challenge parameters are the ones that change for almost for every challenge-response operation.
Following sections explain about exchange of fixed and variable challenge parameters, mapping between them, validity duration of fixed parameters and how challenge-response operation is performed using fixed and variable set challenge parameters.
A. Control parameters
Control parameters are the parameters, which enable mapping between fixed challenge parameters and variable challenge parameters unambiguously along with validity parameter, which holds duration for which fixed challenge parameters are valid.
System identifier is a control parameter, which uniquely identifies a system that

wants to defend itself from attack. System identifier can be Fully Qualified Domain Name, IP address which does not change for longer duration. A system may have one or more system identifiers.
Challenge identifier is a parameter, which uniquely identifies fixed challenge parameters thrown by a system. System identifier and challenge identifier uniquely identify a fixed challenge parameter set. Challenge identifier is a unique identifier and does not repeat.
Validity is the time duration for which fixed challenge parameters are valid. This enable hosts to flush out out-dated fixed challenge parameters.
B. Selection of fixed challenge parameters
Following parameters are considered as fixed challenge parameters. These parameters are selected from sub-section I of "Proposed challenge-response method" (section 1). Following parameters shall constitute fixed challenge parameters
i. Value m is a part of fixed challenge parameters. Please refer step 2 of
section I in Proposed challenge-response method section, ii. If exponentiation method is used, values n, exp (section 1, sub-section I) along with operation type 'exponentiation' is a part of fixed challenge parameters, iii. If factorial method is used (section 1-1), parameters num along with operation type 'factorial' constitute part of fixed challenge parameters.

iv. If hash method is used (section 1-1), parameters random, size, hash algorithm and operation type 'hash' constitute part of fixed challenge parameters.
v. If reducing size of response from client (section 1-V) is employed with Hash mechanism (section 1-V-A) than a parameter to indicate usage
of reducing size of response from client, identifier to indicate hash method, hash algorithm to be used and portion of hashed output to be exchanged (if only part of hashed output is exchanged) constitute part of fixed challenge parameters, vi. If reducing size of response from client (section 1-V) is employed with
Repeated XOR mechanism (section 1-V-B) than a parameter to indicate usage of reducing size of response from client, identifier to indicate XOR method, block size constitute part of fixed challenge parameters.
Thus server forms fixed cost parameters. Other challenge parameters in section 1-1, apart from above mentioned constitute variable challenge parameter set.
C. Communication of fixed challenge parameters along with control
parameters
The set constituting fixed cost parameters along with control parameters are communicated to clients. The mode of transport is explained section H below.
D. Management of fixed challenge parameters and control values in client

Clients after having received fixed challenge parameters along with control parameters shall store them till the validity period. Clients shall also be configured to accept fixed challenge parameters along with control parameters only from specific systems identified by System identifier. This enables client to ignore fixed challenge parameters arriving from unknown systems, which may not be of interest to client.
E. Challenge message exchange with variable challenge parameters,
control parameters and challenge resolving process in client
When server wants to perform challenge-response operation, shall send only variable portion of challenge (with some exceptions as explained above) along with system identifier (if required) and challenge identifier to client. Client upon receiving challenge with variable parameters and required control parameters shall map to fixed challenge parameter which is already received, using system identifier and challenge identifier to construct complete challenge parameter set. Once complete set of challenge parameters are identified in client, it shall perform modular exponentiation operation as explained in section 1 —III. Resolved challenge is sent to server for verification.
F. Methods to get fixed challenge parameters when required
It may so happen, that at the time when variable challenge parameters along with

control parameters are received, client may not have appropriate mapping to fixed-challenge parameters. This scenario may arise when client fails to receive fixed challenge parameters from server.
Following methods can be used to exchange fixed-challenge parameters at run
time:
i. Before getting variable challenge parameters, client sends the list of challenge-identifiers possessed by it to server. Server upon detecting appropriate fixed-challenge parameters not present in client shall send the fixed-challenge parameters along with control parameters and variable challenge parameters along with required control parameters to client. Client shall store the fixed challenge parameters in device (so that it need not request again). Once fixed and variable parameters are received client shall follow procedure explained above to resolve the challenge.
Server may also send list of all fixed-challenge parameters which are supposed to be known to client along with the ones which are required for on-going challenge-response operation. Client shall store fixed-challenge response in it, so that it need not request for the same in later challenge-response operations.
ii. If server can keep track of fixed-challenge parameters sent to client and client's identitv before oerformina challenae-resnonse oneration server

shall send fixed-challenge parameters and control variables to client if required( if it is not communicated to client earlier). Server also sends variable challenge parameters along with required control parameters. Using fixed and variable challenge parameters along with required control parameters, client shall follow procedure explained in section 2-IV-E to resolve the challenge. Client shall store the fixed-challenge parameters and its control parameters for future reference.
G. Control messages
Control messages shall be sent to clients to control change in validity of fixed challenge parameters.
Control messages shall be sent to
i. Invalidate already sent fixed-challenge parameters along with control parameters
If server or relevant authority want to invalidate already sent fixed-challenge parameters, shall send a control message containing operation type which identifies invalidation of particular fixed-challenge parameters along with control parameters, system identifier and challenge identifier of fixed-challenge parameters. Client upon receiving this control message shall delete appropriate fixed challenge parameters and its control parameters identified by system identifier and challenge identifier.

ii. Extend the life-time of already sent fixed-challenge parameters along with control parameters
If server or relevant authority wants to extend validity period of already transmitted fixed-challenge parameters along with challenge parameters, shall send control message containing operation type which identifies extension of life-time for fixed challenge parameter set, new time till which fixed-challenge parameters are valid, system identifier and challenge identifier of fixed challenge parameters on which change has to be applied.
H. Communication of asynchronous messages
Server or relevant authority would like to send messages like fixed-challenge parameters along with control parameters (section 2-IV-C) or control message
(section 2-IV-G) from time to time.
Such asynchronous messages shall be communicated to client over reliable and/or un-reliable transport medium.
When asynchronous messages are communicated over reliable transport medium, server shall be able to keep track of its client who has received its asynchronous messages. For example, reliable transport medium can be i. Reliable push over WAP or HTTP.

ii. Client shall run a service at a port and server upon knowing that it can reach client, shall send fixed-challenge parameters to it over reliable transport mediums like TCP, HTTP etc.
When asynchronous messages are communicated over un-reliable transport layers like for example, IP broadcast, IP multicast, UDP or any connectionless transport means, in order for client to receive message,
i. Server may keep sending the messages periodically or
ii. Client shall use either of methods explained in section 2-IV-F to get
fixed-challenge parameters.
Alternatives/other embodiments of the invention
1. Reducing size of d above to save bandwidth:
In step (7) of section 1-1, d = cVmargin. If c*r is greater than φ(m), d and
margin shall be calculated as described below.
Let margin be a small value (say varying from 1 to 30). If c*r mod {

does not reveal (not close to p(m)), then d=(c*r mod (

Reduced size of 'd' enables saving few bytes at the cost of performing a modular multiplication operation. Proof in section 1-VI, shall be logically extended for this change. Step (9) in section 1-1 holds good for verification operation in server.

2. When sign in some equations are changed in section I and/or III of section 1, would result in server performing result = a٨(-margin) mod(m) to calculate result for verification. a٨(-margin) mod (m) can be calculated using Extended Euclidean Algorithm. [The extended Euclidean algorithm is a version of the Euclidean algorithm; its input are two integers a and b and the algorithm computes their greatest common divisor (gcd) as well as integers x and y such that ax + by = gcd(a, b). The equation ax + by = gcd(a, b) is particularly useful when a and b are co-prime, x is then the multiplicative inverse of a modulo b]
3. Even when sign in some equations are changed in section I, III of section 1, would result in server performing result=aAmargin mod(m) to calculate result for verification.
4. In section 1-1, step (4) is e1= x*φ (m)+c. If x is set to 1 and c = +/- margin
where margin is small value, e1 becomes e1 = φ (m)+/-margin. If values of e2
and d are fixed as e2 = 1 and d = 0, main operation becomes a٨( φ
(m)+/-margin) mod (m) in client and in server it becomes, a٨margin mod(m) or a٨(-margin) mod(m)[this can be calculated using extended Eucledian algorithm]. This would make server to refresh value of m almost for every transaction, since in the above equation margin is small value, ^(m) can be
easily identified from el
5. In the methods described above, server shall delegate separate system to
perform challenge response operation, i.e. Challenge manager service shall

reside in some other machine and carry out the operation. When application in server decides to perform challenge-response operation, shall request client to contact system delegated by it to perform challenge-response operation. Once client performs challenge response operation, server commits its resources to serve client after verifying if client has successfully performed challenge-response operation with the system delegated by it.
6. In section 2-IV, fixed challenge parameters along with control parameters and control messages may be optionally signed in-order to assert authenticity of messages.
7. In section 2-IV, fixed challenge parameters along with control parameters when updated as a part of DNS resource record can reach clients easily.
Advantage(s) of the Invention
Challenge-response method proposed above defends system from resource consumption attacks has following advantages.
1. Cost of resolving the challenge shall be controlled by server:
Complexity of modular exponentiation operation in client is directly dependent on parameters e1 and e2,.Since values of e1 and e2 are determined by server, it has full control over determining cost of operation in client.
2. Verification is very light weight operation in server, thus saving server's
resources for critical operations:

Despite cost incurred by client in resolving challenge, server has to perform a٨ margin mod(^ (m)) to verify challenge. Since margin is controlled by server and
is very small value, complexity of modular exponentiation operation is always low.
3. Usage of pre-calculated values:
All the operations specified in steps (1)-(9) in section 1-1 and operations specified in section 1-V can be pre-calculated. This enables server spending very minimal resources while performing challenge-response operation at run time.
4. Comparison of proposed method with methods described in prior art section:
A. Comparison with Anti-clogging cookies
Anti-clogging cookies do not make client to go for a resource intensive operation. The method proposed employs challenge-response mechanism in which cost of operation performed in client is controllable by server.
B. Comparison with client puzzles
Complexity of resolving challenge increases exponentially with increase in a bit. Further even if brute force or linear search mechanism is employed to resolve challenge, controlling cost of operation in client is difficult. In the proposed method, cost of operation in client can be controlled in better way by changing values of e1 and/or e2.
C. Comparison with DOS resistant authentication with client puzzles

Complexity of resolving challenge increases exponentially with increase in a bit. Cost of operations can be controlled in better way in proposed method by changing values of e1 and/or e2.
If number of bits to be guessed is larger, client may end up with not being able to resolve challenge. In the method proposed results are guaranteed upon client performing modular exponentiation to resolve challenge.
D. Comparison with hash cash
In hash cash method, server performs two modular exponentiation operations in order to verify the result. In the method proposed, server always performs aAmargin mod (m) to verify challenge (step 9 above). Since margin is chosen by server and always it is kept low, verification is simple in server despite cost incurred by client in resolving challenge.
The present invention shall ordinarily be used in design of protocols, software/hardware systems for defending system against DOS attack. Further the method shall be applied to protect software or hardware resources, which are connected to network from DOS attack. Apart from DOS/DDOS mitigation, this method can be applied in an environment, where a system wants other system to resolve challenge in-order to proceed with further operations. For example, password cracking has become a common problem and the rate at which password is cracked shall be slowed down by employing challenge-response mechanism i.e., a system (say server) before validating password sent by other system (say client)

snaii request client to resoive cnaiienge DeTore going Tor passwora verification operation. When client tries to crack password by throwing multiple requests would get loaded in trying to resolve the challenge thus slowing down the rate at which password is cracked.
In the description herein, numerous specific details are provided, such as examples of components and/or methods, to provide a thorough understanding of embodiments of the present invention. One skilled in the relevant art will recognize, however, that an embodiment of the invention can be practiced without one or more of the specific details, or with other apparatus, systems, assemblies, methods, components, materials, parts, and/or the like. In other instances, well-known structures, materials, or operations are not specifically shown or described in detail to avoid obscuring aspects of embodiments of the present invention.
While it is apparent that the invention herein disclosed is well calculated to fulfill the objects above stated, it will be appreciated that numerous modifications and embodiments may be devised by those skilled in the art, and it is intended that the appended claims cover all such modifications and embodiments as fall within the true spirit and scope of the present invention.

WE CLAIM
1. A method for protecting servers from DOS attack with the avoidance of
immediate commitment of server's resources to client, the method comprising
the steps of
a) checking the commitment of client in going ahead with protocol, by throwing a challenge to it forcing to spend considerable resources in solving the challenge, whose cost is controllable by server;
b) verifying the results or responses sent by the client, spending relatively very small effort;
c) committing the resources for the serving client only if the above said result or response is valid; and
d) controlling the cost of the modular exponentiation operation in client.

2. The method as claimed in claim 1 wherein, the challenge is thrown by the system, which wants to defend itself from attack, or another system that is designated by it throw the challenge and validate it.
3. The method as claimed in claim 1, wherein the challenge and response mechanism comprises Pre-computation of parameters, Challenge generation in server, Challenge resolution in client, Challenge response verification in server and Reducing size of response from client
4. The method as claimed in claim 2, wherein the intermediate system if employed

does not commit any resources, but acts only as router to route traffic related to challenge-response messages.
5. The method as claimed in claim 3, wherein the challenge-response mechanism can be deployed with or without minor changes on application in server and without any change in application on client.
6. The method as claimed in claim 1, wherein distribution of challenge parameters to utilize bandwidth efficiently, comprises a method for exchange of fixed challenge parameters along with control parameters, method for exchange of variable challenge parameters along with control parameters, mapping between fixed and variable challenge parameters, management of challenge parameters in client, control messages and communication Channel.
7. A method for protecting servers from DOS attack with the avoidance of immediate commitment to client, substantially as herein above described and illustrated with reference to the accompanying drawings

Documents:

1954-CHE-2005 AMENDED PAGES OF SPECIFICATION 28-08-2012.pdf

1954-CHE-2005 AMENDED CLAIMS 28-08-2012.pdf

1954-CHE-2005 FORM-1 28-08-2012.pdf

1954-CHE-2005 FORM-13 28-08-2012.pdf

1954-CHE-2005 FORM-3 28-08-2012.pdf

1954-CHE-2005 FORM-5 28-08-2012.pdf

1954-CHE-2005 POWER OF ATTORNEY 28-08-2012.pdf

1954-CHE-2005 AMENDED CLAIMS 03-10-2012.pdf

1954-CHE-2005 AMENDED PAGEDS OF SPECIFICATION 03-10-2012.pdf

1954-CHE-2005 EXAMINATION REPORT REPLY RECEIVED 28-08-2012.pdf

1954-CHE-2005 EXAMINATION REPORT REPLY RECEIVED 03-10-2012.pdf

1954-CHE-2005 FORM-13 28-08-2012.pdf

1954-CHE-2005 OTHER PATENT DOCUMENT 03-10-2012.pdf

1954-CHE-2005 OTHER PATENT DOCUMENT 28-08-2012.pdf

1954-CHE-2005 POWER OF ATTORNEY 03-10-2012.pdf

1954-che-2005-abstract.pdf

1954-che-2005-claims.pdf

1954-che-2005-correspondnece-others.pdf

1954-che-2005-description(complete).pdf

1954-che-2005-drawings.pdf

1954-che-2005-form 1.pdf

1954-che-2005-form 13.pdf

1954-che-2005-form 26.pdf

« Previous Patent

Next Patent »

Patent Number

254399

Indian Patent Application Number

1954/CHE/2005

PG Journal Number

44/2012

Publication Date

02-Nov-2012

Grant Date

31-Oct-2012

Date of Filing

29-Dec-2005

Name of Patentee

SAMSUNG INDIA SOFTWARE OPERATIONS PRIVATE LIMITED

Applicant Address

BAGMANE LAKEVIEW,BLOCK B NO.66/1 BAGMANE TECH PARK,C.V.RAMAN NAGAR,BYRASANDRA BANGALORE 560 093

Inventors:

#	Inventor's Name	Inventor's Address
1	PERUMAL RAJ S	EMPLOYED AT SAMSUNG ELECTRONICS CO.LTD.,INDIA SOFTWARE OPERATIONS(SISO), HAVING ITS OFFICE AT, J.P TECHNO PARK, 3/1, MILLERS ROAD, BANGALORE 560 052

PCT International Classification Number

G06F9/00

PCT International Application Number

N/A

PCT International Filing date

PCT Conventions:

#	PCT Application Number	Date of Convention	Priority Country
1			NA